Prove that the reduced row echelon form of a matrix is uniqu

Prove that the reduced row echelon form of a matrix is unique. That is, U and V are both the reduced row echelon forms of A then U = V.

Solution

Let A be an m X n matrix.

We willuse induction on n (the number of columns of A) to prove the result

If n = 1 then we are through. Now suppose that n > 1.

Let B be the matrix obtained from A by deleting the nth column. We observe that any sequence of elementary row operations which reduces A into row echelon form also reduces B into row echelon form. Thus by induction, if U and V are reduced row echelon forms of A, they can differ in the nth column only. Assume U is not equal to V. Then there is an integer j such that the jth row of U is not equal to the jth row of V. Let b be any column vector such that Ub = 0. Then Vb= 0 and hence (U -V) b = 0. We observe that the first n - 1 columns of U-V are zero columns. Thus the jth coordinate of (U -V)b is (u_jn -v_jn)b_n. Sinceu_jn is not equal to v_jn we must have b_n = 0. Thus any solution to Ux = 0 or Vx = 0 must have x_n =0 . It follows that both the nth columns of U and V must contain leading l\'s, for otherwise those columns would be free columns and we could arbitrarily choose the value of x_n. But since the first n - 1 columns of U and V are identical, the row in which this leading 1 must appear must be the same for both U and V, namely the row which is the first zero row of the reduced row echelon form of B. Because the remaining entries in the n th columns of U and V must all be zero, we have U = V, which is a contradiction. This establishes the result we required.