Theorem The following three operations do not change the solutions of systems of linear equations.
Proof For the first operation, let x = (x_{1}, x_{2}, ..., x_{n}) be a solution of the following system (denoted Ax = b).
a_{11}x_{1} | + a_{12}x_{2} | + ... + a_{1n}x_{n} | = | b_{1} |
a_{21}x_{1} | + a_{22}x_{2} | + ... + a_{2n}x_{n} | = | b_{2} |
... | ... | ... | ||
a_{m1}x_{1} | + a_{m2}x_{2} | + ... + a_{mn}x_{n} | = | b_{m} |
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
(ra_{i1}+a_{j1})x_{1} + (ra_{i2}+a_{j2})x_{2} + ... + (ra_{in}+a_{jn})x_{n} = rb_{i} + b_{j}.
To show x satisfies this, we note that x satisfies the i-th and the j-th equations in the old system.
a_{i1}x_{1} + a_{i2}x_{2}
+ ... + a_{in}x_{n} = b_{i},
a_{i1}x_{1} + a_{j2}x_{2}
+ ... + a_{jn}x_{n} = b_{j}.
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
a_{i1}x_{1} + a_{i2}x_{2} + ... + a_{in}x_{n} = b_{i}.
Then it also satisfies the i-th equation after the third operation
da_{i1}x_{1} + da_{i2}x_{2} + ... + da_{in}x_{n} = db_{i}.
Conversely, if x satisfies the new i-th equation, then by dividing d, we see that x satisfies the old i-th equation.