The content in today's blog is taken from Hans Schneider and George Phillip Barker's Matrices and Linear Algebra.

Lemma 1:

The interchange of two rows in a given matrix A is equivalent to a multiplication between a matrix E

_{1}and A.

Proof:

(1) Let A be an m x n matrix with rows i,j where i ≠ j.

(2) Let A' be the matrix A after rows i,j are interchanged.

(3) Let I

_{m}be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E

_{1}be the matrix I

_{m}after the rows i,j are interchanged.

(5) Then, A' = E

_{1}A. [See here for review of matrix multiplication if needed]

QED

Lemma 2:

The multiplication of any row in a matrix A by a nonzero scalar α is equivalent to a multiplication between a matrix E

_{2}and A.

Proof:

(1) Let A be an m x n matrix and let i be any row.

(2) Let A' be the matrix A after row i is multiplied by α

(3) Let I

_{m}be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E

_{2}be the matrix I

_{m}after the row i is multiplied by α.

(5) Then, A' = E

_{2}A. [See here for review of matrix multiplication if needed]

QED

Lemma 3:

The addition of a scalar multiple α of some row i to another row j in the matrix A is equivalent to a multiplication between a matrix E

_{3}and A.

Proof:

(1) Let A be an m x n matrix with rows i,j where i ≠ j.

(2) Let A' be the matrix A after a scalar multiple α of the row i is added to the row j.

(3) Let I

_{m}be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E

_{3}be the matrix I

_{m}where position i in row j is replaced by α instead of 0.

(5) Then, A' = E

_{3}A. [See here for review of matrix multiplication if needed]

QED

Lemma 4: E

_{1}, E

_{2}, and E

_{3}in the above lemmas are all invertible.

Proof:

(1) (E

_{1})

^{-1}= E

_{1}

(2) (E

_{2})

^{-1}= E

_{2}with α replaced by 1/α.

(3) (E

_{3})

^{-1}= E

_{3}with α replaced by -α.

QED

Theorem 5: Implication of Row Equivalence

A is row equivalent to B if and only if B = PA where P is the product of elementary matrices P = E

_{a}*E

_{b}*...*E

_{z}and P is invertible.

Proof:

(1) Assume that A is row equivalent to B. [See Definition 3 here for definition of row equivalence]

(2) Then A can be derived from B using n elementary operations (see Definition 3 here)

(3) Let A

_{0}= A.

(4) Let A

_{1}= A

_{0}after the first elementary operation. Using Lemma 1, Lemma 2, or Lemma 3, we know that there exists E

_{a}such that A

_{1}=E

_{a}A

_{0}

(5) Let A

_{2}= A

_{1}after the second elementary operation. Again, it is clear that there exists E

_{b}such that A

_{2}= E

_{b}A

_{1}.

(6) Using substitution, we have:

A

_{2}= E

_{b}E

_{a}A

(7) We can continue in this way for each of the remaining elementary operations until we get:

A

_{n}= E

_{z}*...*E

_{a}A

(8) Assume that B = PA where P is the product of elementary matrices P = E

_{a}*E

_{b}*...*E

_{z}

(9) Clearly, each of the E

_{i}is equivalent to an elementary operation and we can see that B consists of a series of elementary operations since we have:

B = E

_{a}(E

_{b}[E

_{c}...A]))

(10) So, by definition of row equivalent (see Definition 3 here), we can conclude that A is row equivalent to B.

(11) We know that P is invertible since each E

_{i}is invertible (see Lemma 4 above) and therefore any product of these elements is also invertible (see Lemma 3, here)

QED

References

- Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.