Row Equivalence

In today's blog, I will revisit the concept of row equivalence. This topic was covered in a previous blog on Gauss-Jordan Elimination.

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₁ 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₁ be the matrix I_m after the rows i,j are interchanged.

(5) Then, A' = E₁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₂ 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₂ be the matrix I_m after the row i is multiplied by α.

(5) Then, A' = E₂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₃ 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₃ be the matrix I_m where position i in row j is replaced by α instead of 0.

(5) Then, A' = E₃A. [See here for review of matrix multiplication if needed]

QED

Lemma 4: E₁, E₂, and E₃ in the above lemmas are all invertible.

Proof:

(1) (E₁)^-1 = E₁

(2) (E₂)^-1 = E₂ with α replaced by 1/α.

(3) (E₃)^-1 = E₃ 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₀ = A.

(4) Let A₁ = A₀ after the first elementary operation. Using Lemma 1, Lemma 2, or Lemma 3, we know that there exists E_a such that A₁=E_aA₀

(5) Let A₂ = A₁ after the second elementary operation. Again, it is clear that there exists E_b such that A₂ = E_bA₁.

(6) Using substitution, we have:

A₂ = E_bE_aA

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

A_n = E_z*...*E_aA

(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.