math111_logo Row Operation

The three operations do not change solutions

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.