18.2. ROW OPERATIONS AND LINEAR EQUATIONS 387
Proof: Let A equal the following matrix in which the ak are the columns(a1 a2 · · · an
)and let B equal the following matrix in which the columns are given by the bk(
b1 b2 · · · bn)
Then by Theorem 18.2.11 on Page 384 bk =Eak where E is an elementary matrix. Supposethen that one of the columns of A ak is a linear combination of some other columns of A.Say ak = ∑
rk=1 cikaik . Then multiplying by E, bk = Eak = ∑
rk=1 cik Eaik = ∑
rk=1 cikbik .
How do you know when to stop doing row operations in solving a system of equations?This involves the row reduced echelon form.
Definition 18.2.19 Let ei denote the column vector which has all zero entries ex-cept for the ith slot which is one. An m×n matrix is said to be in row reduced echelon formif, in viewing successive columns from left to right, the first nonzero column encountered ise1 and if you have encountered e1,e2, · · · ,ek, the next column is either ek+1 or is a linearcombination of the vectors, e1,e2, · · · ,ek.
Theorem 18.2.20 Let A be an m× n matrix. Then A has a row reduced echelonform determined by a simple process.
Proof: Viewing the columns of A from left to right take the first nonzero column. Picka nonzero entry in this column and switch the row containing this entry with the top row ofA. Now divide this new top row by the value of this nonzero entry to get a 1 in this positionand then use row operations to make all entries below this equal to zero. Thus the firstnonzero column is now e1. Denote the resulting matrix by A1. Consider the sub-matrix ofA1 to the right of this column and below the first row. Do exactly the same thing for thissub-matrix that was done for A. This time the e1 will refer to Fm−1. Use the first 1 obtainedby the above process which is in the top row of this sub-matrix and row operations to zeroout every entry above it in the rows of A1. Call the resulting matrix A2. Thus A2 satisfiesthe conditions of the above definition up to the column just encountered. Continue this waytill every column has been dealt with and the result must be in row reduced echelon form.
The process of doing this is completely routine and involves elementary school arith-metic and being careful. I have found that you are less likely to make a mistake if you do iton a blackbord and erase and replace as you go. Here is an example.
Example 18.2.21 Find the row reduced echelon form for the matrix 3 2 1 11 −1 3 21 4 3 2
I will switch the first two rows because I don’t like to work with fractions. This yields 1 −1 3 2
3 2 1 11 4 3 2