86 CHAPTER 4. MATRICES

When you find a solution to the system of equations, you are really finding the scalarsx,y,z,w such that the vector on the right is the above linear combination of the columns.

We considered writing this system as an augmented matrix 1 0 −3 −5 11 1 1 2 21 1 1 2 3

and then row reducing it to get a matrix in row reduced echelon form from which it waseasy to see the solution, finding the last column as a linear combination of the precedingcolumns. However, this process of row reduction also shows the fourth column as a linearcombination of the first three and the third as a linear combination of the first two, so whenyou reduce to row reduced echelon form, you are really solving many systems of equationsat the same time. The important thing was the observation that the row operations did notchange the solution set of the system.

However, this could be said differently. The row operations did not change the set ofscalars which yield the last column as a linear combination of the first four. Similarly, therow operations did not change the scalars to obtain the fourth column as a linear combina-tion of the first three, and so forth. In other words, if a column is a linear combination ofthe preceding columns, then after doing row operations, that column will still be the samelinear combination of the preceding columns. By permuting the columns, placing a cho-sen column on the right, the same argument shows that any column after the row operationis the same linear combination of the other columns as it was before the row operation.

Such a relation between a column and other columns will be called a linear relation.Thus we have the following significant observation which is stated here as a theorem.

Theorem 4.3.1 Row operations preserve all linear relations between columns.

Now here is a slightly different description of the row reduced echelon form.

Definition 4.3.2 Let ei denote the column vector which has all zero entries except for theith slot which is one. An m× n matrix is said to be in row reduced echelon form if, inviewing successive columns from left to right, the first nonzero column encountered is e1and if you have encountered e1,e2, · · · ,ek, the next column is either ek+1 or is a linearcombination of the vectors, e1,e2, · · · ,ek.

Earlier an algorithm was presented which will produce a matrix in row reduced echelonform. A natural question is whether there is only one row reduced echelon form. In fact,there is only one and this follows easily from the above definition.

Suppose you had two B,C in row reduced echelon form and these came from the samematrix A through row operations. Then they have zero columns in the same positionsbecause row operations preserve all zero columns. Also B,C have e1 in the same positionbecause its position is that of the first column of A which is not zero. Similarly e2,e3and so forth must be in the same positions because of the above definition where thesepositions are defined in terms of a column being the first in A when viewed from the leftto the right which is not a linear combination of the columns before it. As to a columnafter ek and before ek+1 if there is such, these columns are an ordered list top to bottom ofthe scalars which give this column in A as a linear combination of the columns to its leftbecause all linear relations between columns are preserved by doing row operations. Thus