REDUCED ROW ECHELON FORM

PETE L. CLARK

1. Reduced Row Echelon Form We work over the real numbers (but everything we say would be valid for matrices with coecients in any eld of scalars). For positive integers m, n we denote by Mm,n the set of m n matrices. Two matrices A, B Mm,n are row equivalent, and write A B , if we can get from A to B by performing a nite sequence of elementary row operations. If A B , then for any column vectors x = (x1 , . . . , xn ) and d = (d1 , . . . , dm ), we have Ax = d if and only if Bx = d. This is just matrix notation for the fact that the elementary row operations preserve the solution set of a linear system. Row equivalence is indeed an equivalence relation on Mm,n , hence it partitions Mm,n into equivalence classes. One can motivate the main result of this note by asking for a canonical way of choosing one matrix from each equivalence class. For M Mm,n , an entry mij is a leading entry if, reading from left to right, it is nonzero and is the rst nonzero entry in its row. Thus a row has a leading entry if and only if it is not a zero row, and every row has at most one leading entry. Thus the number of leading entries of M is at most m, the number of rows. A matrix A Mm,n is in row echelon form if (REF1) Every zero row of A lies below every nonzero row of A, and (REF2) Every leading entry occurs to the right of every leading entry in the rows above it. Exercise 1: a) Show that (REF2) is equivalent to: if 1 i1 < i2 m and 1 j1 , j2 n, ai1 j1 is a leading entry and ai2 j2 = 0, then j2 > j1 . b) Show that (REF2) implies that every entry lying directly below a leading entry is 0. More precisely, if aij is a leading entry, then for all i i m, ai j = 0. A matrix A Mm,n is in reduced row echelon form (or rref ) if it is in row echelon form and moreover (RREF1) Every entry lying directly above a leading entry is 0 and (RREF2) Every leading entry is equal to 1.
c Pete L. Clark, 2013.
1

PETE L. CLARK

Proposition 1.1. Every A Mm,n is row equivalent to a rref matrix. Proof. The proof is constructive: that is, we give an explicit procedure. Step 1: We use elementary row operations to put A Mm,n in row echelon form. We begin by looking at the rst column. Case 1: If every entry of the rst column is 0, we move on to the m (n 1) submatrix A obtained by removing the rst column of A. Any row operations that put A in row echelon form will also put A in row echelon form (moreover if a matrix has a zero column, then so does any row equivalent matrix). Case 2: Suppose that some entry of the rst column is nonzero. Case 2a: Suppose a11 = 0. Then by using the type (III) row operation, for all am1 2 i m, we multiply row 1 by a and add it to row i, thus making the 11 (i, 1) entry equal to zero. Thus we end up with a matrix with a1,1 nonzero (thus a leading entry) and ai,1 = 0 for all 2 i m. We then proceed inward to the (m 1) (n 1) submatrix A formed by removing the rst row and column of A, observing that any sequence of row operations that puts A in row echelon form does the same for our matrix.1 Case 2b: Suppose that a11 = 0. Since we are in Case 2, there is some i such that ai1 = 0. For the sake of deniteness2 take the smallest such i and perform the type (I) row operation switching the rst and ith rows. This places us back in Case 2a. We now have a smaller either m (n 1) or (m 1) (n 1) matrix to put in row echelon form, so we can apply the above procedure to this matrix. (In other words, the algorithm is recursive : we do something very simple and then allow the algorithm to call on itself for smaller parameter values.) Step 2: We have now replaced A by a row equivalent matrix which in row echelon form. We may easily go further and put in reduced row echelong form. First, in each row containing a leading entry aij , we use the type (III) row operation to make all the entries in that column above aij equal to zero just as we did for the entries below to get to row echelon form. (It is worth thinking about why this process necessarily preserves row echelon form: e.g. how do we know we dont produce any zero rows lying above nonzero rows by doing this?) Finally, for every row containing a leading entry aij we use the type (II) row operation to multiply the ith row by a1 , which makes the leading entry equal to 1 (and does not change ij which entries are zero or nonzero so preserves everything weve done so far). Exercise 2: a) Suppose that A Mm,n has entries in the rational numbers Q i.e., numbers of the form a b with a, b Z and b = 0. Show that our algorithm produces a row echelon form and then a reduced row echelon form with entries in Q. b) Suppose A Mm,n has entries in Z. Show that our algorithm does not in general produce a row echelon form or a reduced row echelon form with entries in Z. c) Show however that a modied algorithm will take any A with entries in Z and yield a row echelon form with entries in Z. (Hint: when you want to divide by something, multiply a dierent row by that thing instead.) In fact, show that we can start with any A with entries in Q and nd a row equivalent matrix in row echelon form with entries in Z.
1This is straightforward to check but not, I think, immediately obvious. It is also very important...so please do check it. 2We do actually want to give an algorithm. An algorithm is not allowed to make choices: it must do the same thing every time.

REDUCED ROW ECHELON FORM

d) Show that if A has entries in Mm,n , then a modied algorithm will yield a row echelon form which satises (RREF1).3 Let A be a matrix in row echelon form. Then the variables corresponding to the columns which contain leading entries are called pivot variables, whereas the variables corresponding to the other columns are called free variables. Theorem 1.2. The reduced row echelon form is unique. More precisely, for each A Mm,n , there is exactly one matrix R Mm,n with A R and R in reduced row echelon form. Proof. We follow T. Yuster [Y] by inducting on n, the number of columns. Base Case (n = 1): Suppose A has only one column. If A is the all zero matrix, it is row equivalent only to itself and is in reduced row echelon form. Every nonzero matrix with one column has a nonzero entry, and all such matrices have reduced row echelon form the column vector (1, 0, . . . , 0) and no other row echelon form. Induction Step: Suppose now that n > 1, that the result holds for all m n matrices, and let A Mm,n+1 . For any M Mm,n+1 , we let M Mm,n be obtained by removing the last column from M . Let B and C be reduced row echelon forms of A. Here is the key observation: the matrices B and C are in reduced row echelon form and row equivalent to A . By induction, we have B = C . In other words, we know that the reduced row echelon matrices B and C are equal except possibly in the last column. Seeking a contradiction we suppose that their last columns are not equal: i.e., there is some 1 i m such that bi,n+1 = ci,n+1 . Now let x = (x1 , . . . , xn+1 ) be any vector with Bx = 0, i.e., a solution of the associated homogeneous linear system. Because B and C are row equivalent, x is also a solution to the homogeneous system Cx = 0. It follows that (B C )x = 0. Since the matrix B C is zero except in its last column, performing the multiplication of the ith row of B C by x simply gives (bi,n+1 ci,n+1 )xn+1 = 0. Since bi,n+1 = ci,n+1 we deduce that xn+1 = 0. Thus xn+1 is not a free variable for either B or C , so in each of these matrices the last column must contain a leading entry of 1 and have all the other entries 0. Moreover, in both B and C the 1 must lie in the rst zero row of B and C . Thus B = C . The uniqueness of reduced row echelon form has several important consequences. For now we point the following one. Corollary 1.3. Let A Mm,n , and let B and C be row equivalent matrices each in row echelon form. Then the pivot variables with respect to the matrix B are the same as the pivot variables with respect to the matrix C . Proof. We gave an algorithm to take the matrix B and put it in reduced row echelon form. At every step this algorithm preserves the positions of the leading entries, so it preserves pivot variables. Thus the pivot variables with respect to B are the same as the pivot variables for some reduced row echelon form matrix RB which is row equivalent to A. Similarly, the pivot variables with respect to C are the same as the pivot variables for some reduced row echelon form matrix RC which is row equivalent to A. But by Theorem 1.2, RB = RC , and thus the pivot variables with respect to B are the same as the pivot variables with respect o C .
3Perhaps we should call this almost reduced row echelon form?

PETE L. CLARK

This allows us to make the following important denition. For a matrix A Mm,n , we dene the rank of A to be the number of pivot variables in any row echelon form of A and the nullity of A to be the number of free variables in any row echelon form of A. Corollary 1.3 ensures that this is well-dened, i.e., independent of the row echelon form chosen. The following result follows immediately but, when translated into other contexts, is in fact important and quite powerful. Theorem 1.4. (Rank-Nullity Theorem) For any A Mm,n we have rank(A) + nullity(A) = n. Exercise 3: Prove the Rank-Nullity Theorem. (Hint: its very easy!) Exercise 4: Find all rref matrices R M2,2 . (Hint: what are the possibilities for the rst column?) References
[Y] T. Yuster, The Reduced Row Echelon Form of a Matrix is Unique: A Simple Proof. Math. Mag. 57 (1984), 93-94.

Department of Mathematics, Boyd Graduate Studies Research Center, University of Georgia, Athens, GA 30602-7403, USA E-mail address : [email protected]