Skip to main content

Linear Algebra: Companion notes

Abhay Soman

Section 1.4 Uniqueness of row reduced echelon form

Recall from the class that given a matrix \(A\text{,}\) by applying a sequence of elementary row operations, can be reduced to a row-reduced echelon form \(B\) of \(A\text{.}\) The matrix \(B\) has the following properties.
  1. If a row of \(B\) is nonzero then the first nonzero entry is \(1\text{.}\)
  2. All zero rows occurs at the bottom of \(B\text{.}\)
  3. In any two successive nonzero rows of \(B\text{,}\) the leading \(1\) in the lower row occurs to the right of the leading \(1\) in the higher row.
  4. Each column of \(B\) that contains the leading \(1\) (this term is explained in an illustrative example below) has zero everywhere else.
The natural question arises: Does the sequence in which row operations are performed change the resulting row-reduced echelon form of \(A?\) The answer is no!
We present a proof of this fact following Thomas Yuster’s article ‘The reduced row echelon form of a matrix is unique: a simple proof’ 1  from Mathematics Magazine.
We begin with the following example.
The last column of the row-reduced echelon form does not contain the leading \(1\text{.}\) The solution of \(A(x_1,x_2,x_3)^t=0\) can be obtained by assigning an arbitrary value to the last variable \(x_3\text{.}\) Following T. Yuster we call the last column a free column.
Let \(A\) be an \(m\times n\) matrix over a field \(F\text{.}\) Following T. Yuster, we proceed by induction on \(n\text{.}\)
If \(n=1\text{,}\) i.e., \(A\) is an \(m\times 1\) matrix, then the result is true.
Now assume that \(n\geq 2\text{.}\) Let \(A^\prime\in M_{m\times(n-1)}(F)\) be the matrix obtained from \(A\) by deleting the \(n\)-th column of \(A\text{.}\) Note that any sequence of elementary row operations that reduces \(A\) to a row-reduced echelon form also reduces \(A^\prime\) to the row-reduced echelon form. We assume that \(B,C\) are two row-reduced echelon forms of \(A\text{.}\) By induction the row-reduced echelon forms \(B,C\) of \(A\) differs only in their \(n\)-th column. In other words, the first \(n-1\) columns of \(B\) and \(C\) are the same.
Suppose that \(B\neq C\text{.}\) Therefore, the \(j\)-th row of \(B\) will be different from the \(j\)-th row of \(C\) for some \(j\text{.}\) Now if \(v\) is a column vector such that \(Bv=0\) then \(Cv=0\text{,}\) because the solutions of \(AX=0\) coincides with solutions of \(BX=0\) as well as solutions of \(CX=0\text{.}\) Hence, \((B-C)v=0\text{.}\) Since the first \(n-1\) columns of \(B-C\) are zero, the \(j\)-th coordinate of \((B-C)v\) is \((b_{jn}-c_{jn})v_n\text{.}\) As \(b_{jn}\neq c_{jn}\) we must have \(v_n=0\text{.}\) Therefore, the \(n\)-th column of both \(B\) and \(C\) contains the leading \(1\text{;}\) otherwise the \(n\)-th column of both \(B\) and \(C\) will become free column and then, we could choose an arbitrary value for \(v_n\text{.}\)
Since the first \(n-1\) columns of \(B\) and \(C\) are identical the leading \(1\) of the \(n\)-th column must occur in the first zero row of the row-reduced echelon form of \(A^\prime\text{.}\) Since the remaining entries of the \(n\)-th column are all zero we get that \(B=C\text{,}\) a contradiction. Hence, the result is proved.

Remark 1.4.2.

The Theorem 1.4.1 ensures that the row-reduced echelon form of a matrix obtained by you or someone else, or a computer program like SageMath will always give the same result, irrespective of the sequence of row operations.
www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/the-reduced-row-echelon-form-of-a-matrix-is-unique-a-simple-proof
<Prev^TopNext>