UNIQUENESS OF ROW ECHELON FORM

David B. Surowski and Yuhua Wang

The following definition is familiar to every student having had any exposure to linear algebra or matrix theory:

\underline{Definition}. Let A = (a_{ij}) be an n × m matrix over a field k. We say that A is in row echelon form if:

(a) The first non–zero entry of each row is 1.

(b) Rows 1, 2, …, r are the non–zero rows and rows r +1, r +2, … n are zero rows.

(c) If a_{1,i_{1}}, a_{2,i_{2}}, …, a_{r,i_{r}} are the first non–zero entries in rows 1, 2, … r, respectively, then i_{1} < i_{2} < ⋯ < i_{r}.

(d) For all j = 1, 2, …, r and for all k < j, we have a_{k,i_{j}} = 0.

Students learn that by using Gauss–Jordan elimination, any matrix is row– equivalent to a matrix in row echelon form. However, while linear algebra or matrix theory textbooks often assert the uniqueness of row echelon form of a matrix, relatively few actually provide a proof. The most commonly found proof [2,3,4] shows first that the columns i_{1}, i_{2}, …, i_{r} carrying the initial 1s of (a) above are uniquely determined, and then goes on to show that the remaining entries all coincide. A second proof, found in [1], interprets the matrix as the matrix of a linear transformation T: U → V, where row equivalence is manifested through changes of ordered bases in V. Furthermore, if the matrix is in row echelon form, then the representing ordered basis in V is necessarily uniquely determined by T and a fixed ordered basis of U.

While neither proof above is difficult, both are “microscopic,” involving a close scrutiny of matrix entries. The present approach, on the other hand, is based on more holistic properties of matrix products.

The key ingredient of the present approach is to use the notion of Hermite normal form, defined below.

\underline{Definition}. Let A = (a_{ij}) be an n × n matrix, i.e., a square matrix and assume that

1. The first non–zero entry of each row is 1.

2. The first non–zero entry of each row is on the diagonal.

3. If a_{jj} ≠ 0, then for all k < j we have a_{kj} = 0.

Then we say that the matrix A is in Hermite normal form. Note that unlike a matrix in row echelon form, a matrix in Hermite normal form may have zero rows interspersed among the non–zero rows. However, note that by a permutation of rows, a matrix in Hermite normal form is clearly row equivalent to a matrix in row echelon form.

Next we investigate the holistic properties of matrices in Hermite normal form.

\underline{Lemma 1}. Let A, A′ be matrices in Hermite normal form having the same diagonal elements. Then AA′ = A′.

\underline{Proof}. Let A = (α_{ij}), A′ = (α′_{ij}), AA′ = (α′′_{ij}); since A, A′ are upper– triangular, so is AA′, and so if i > j, α′′_{ij} = 0. If i ≤ j,

α′′_{ij} = ∑_{k=i}^{j} α_{ik}α′_{kj}.

If α_{ii} = 0, then α_{ik} = 0, for all k. Therefore α′′_{ij} = 0 for all j ≥ i. However, since α_{ii} = 0, we have α′_{ii} = 0 and so α′_{ij} = 0 = α′′_{ij}. If α_{ii} = 1 then α_{ik} ≠ 0 implies that α_{kk} = 0. Therefore, α′_{kk} = 0 and so α′_{kj} = 0 for all j ≥ k. Therefore,

α′′_{ij} = ∑_{k=i}^{j} α_{ik}α′_{kj} = α_{ii}α′_{ij} = α′_{ij}.

The proof follows.

The following is immediate.

\underline{Corollary}. If A is in Hermite normal form, then A is idempotent, i.e., A^{2} = A.

As already indicated above, by using Gauss–Jordan elimination any matrix is row–equivalent to a matrix in row echelon form, and that any square matrix is row equivalent to a matrix in Hermite normal form.

\underline{Lemma 2}. Assume that the square matrices A_{1}, A_{2} are in Hermite normal form and are row equivalent. Then A_{1}A_{2} = A_{1}.

\underline{Proof}. We have A_{2} = P A_{1} for some nonsingular matrix P. Therefore P A_{1}P A_{1} = P A_{1}; since P is nonsingular we have A_{1}P A_{1} = A_{1}, i.e., A_{1}A_{2} = A_{1}.

\underline{Corollary}. Let A_{1}, A_{2} be as in Lemma 2, above. Then A_{1}, A_{2} have the same diagonal elements.

\underline{Proof}. We have (A_{1} −A_{2})^{2} = A_{1}^{2} −A_{1}A_{2} −A_{2}A_{1} +A_{2}^{2} = A_{1} −A_{1} −A_{2} +A_{2} = 0. Thus, A_{1} −A_{2} is nilpotent; since A_{1} −A_{2} is upper triangular, the diagonal elements are zero. The result follows.

\underline{Corollary}. If A is a square matrix, then A has a unique Hermite normal form.

\underline{Proof}. If A has Hermite normal forms A_{1}, A_{2}, then A_{1}, A_{2} are row equivalent and so

A_{1} = A_{1}A_{2} = A_{2}.

We now return to the question of uniqueness of row echelon form. Given an n × m matrix A, we set r = max{m, n}, and let A_{H} be the r × r matrix by adding rows (or columns) of 0’s to make A into an r × r matrix. Thus, if

A = [ \begin{matrix}∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \end{matrix} ] then A_{H} = [ \begin{matrix}∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \\ 0 & 0 & 0 \end{matrix} ] .

Similarly, if

A = [ \begin{matrix}∗ & ∗ \\ ∗ & ∗ \\ ∗ & ∗ \end{matrix} ] then A_{H} = [ \begin{matrix}∗ & ∗ & 0 \\ ∗ & ∗ & 0 \\ ∗ & ∗ & 0 \end{matrix} ] .

\underline{Theorem}. Let A be an n × m matrix. Then A is row equivalent to a unique matrix in row echelon form.

\underline{Proof}. Let A be row equivalent to matrices A_{1}, A_{2}, where A_{1}, A_{2} are in row echelon form. Then A_{1} and A_{2} are row equivalent; hence, so are (A_{1})_{H} and (A_{2})_{H}. Furthermore, by simple permutations of the rows of (A_{1})_{H} and (A_{2})_{H}, we may obtain matrices in Hermite normal form, which must coincide. This clearly implies that (A_{1})_{H} = (A_{2})_{H}, and so A_{1} = A_{2}.

\underline{References}

1. E. D. Nering, Linear Algebra and Matrix Theory, John Wiley & Sons, Inc., New York, 1970.

2. K. Nomizu, Fundamentals of Linear Algebra, McGraw–Hill Book Company, New York, 1966.

3. H. Schneider and G. P. Barker, Matrices and Linear Algebra, Holt Rinehart and Winston, Inc., New York, 1968.

4. J. E. Scroggs, Linear Algebra, Brooks/Cole Publishing Company, Belmont, California, 1970.

David B. Surowski Department of Mathematics Kansas State University Manhattan, KS 66506–2602 email: dbski@math.ksu.edu

Yuhua Wang Quintiles, Inc. Kansas City, MO 64134–0708 email: yuhua.wang@quintiles.com