Wednesday, May 30, 2007

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 E1 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 Im be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E1 be the matrix Im after the rows i,j are interchanged.

(5) Then, A' = E1A. [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 E2 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 Im be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E2 be the matrix Im after the row i is multiplied by α.

(5) Then, A' = E2A. [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 E3 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 Im be the m x m identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E3 be the matrix Im where position i in row j is replaced by α instead of 0.

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

QED

Lemma 4: E1, E2, and E3 in the above lemmas are all invertible.

Proof:

(1) (E1)-1 = E1

(2) (E2)-1 = E2 with α replaced by 1/α.

(3) (E3)-1 = E3 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 = Ea*Eb*...*Ez 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 A0 = A.

(4) Let A1 = A0 after the first elementary operation. Using Lemma 1, Lemma 2, or Lemma 3, we know that there exists Ea such that A1=EaA0

(5) Let A2 = A1 after the second elementary operation. Again, it is clear that there exists Eb such that A2 = EbA1.

(6) Using substitution, we have:

A2 = EbEaA

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

An = Ez*...*EaA

(8) Assume that B = PA where P is the product of elementary matrices P = Ea*Eb*...*Ez

(9) Clearly, each of the Ei is equivalent to an elementary operation and we can see that B consists of a series of elementary operations since we have:

B = Ea(Eb[Ec...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 Ei is invertible (see Lemma 4 above) and therefore any product of these elements is also invertible (see Lemma 3, here)

QED

References