Theorem The following three operations do not change the solutions of systems of linear equations.
Proof For the first operation, let x = (x1, x2, ..., xn) be a solution of the following system (denoted Ax = b).
|a11x1||+ a12x2||+ ... + a1nxn||=||b1|
|a21x1||+ a22x2||+ ... + a2nxn||=||b2|
|am1x1||+ am2x2||+ ... + amnxn||=||bm|
The new system (denoted A'x = b') obtained by the first operation is the same as the old one except that the j-th equation becomes
(rai1+aj1)x1 + (rai2+aj2)x2 + ... + (rain+ajn)xn = rbi + bj.
To show x satisfies this, we note that x satisfies the i-th and the j-th equations in the old system.
ai1x1 + ai2x2
+ ... + ainxn = bi,
ai1x1 + aj2x2 + ... + ajnxn = bj.
By multiplying r to the 1st equality and then add to the 2nd equality, we see that x satisfies the j-th equation in the new system.
We have shown that any solution of Ax = b is a solution of A'x = b'. Conversely, the system Ax = b can be recovered from the system A'x = b' by the operation (-r)[equation i] + [equation j]. Therefore any solution of A'x = b' is also a solution of Ax = b. This completes the proof that the solutions of the two systems Ax = b and A'x = b' are the same.
Since the order of the equations is irrelevant in whether or not x is a solution, the solution is not changed by the second operation.
For the third operations, let x satisfy the i-th equation
ai1x1 + ai2x2 + ... + ainxn = bi.
Then it also satisfies the i-th equation after the third operation
dai1x1 + dai2x2 + ... + dainxn = dbi.
Conversely, if x satisfies the new i-th equation, then by dividing d, we see that x satisfies the old i-th equation.