## Thursday, June 14, 2007

### Column Equivalence

In today's blog, I present the concept of column equivalence. This topic is based on a previous blog on row equivalence.

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

Definition 1: Type I Column Operation A(Ci ↔ Cj)

A Type I column operation consists of the interchange of any two distinct columns.

Definition 2: Type II Column Operation A(kCi) where k ≠ 0.

A Type II column operation consists of the multiplication of any column by a nonzero scalar.

Definition 3: Type III Column Operation A(kCi + Cj).

A Type III column operation consists of a scalar multiple of some column to another column.

Definition 4: Elementary Column Operation

An elementary column operation is any Type I, Type II, or Type III Column Operation or any combination of these operations.

Definition 5: Column Equivalence

Two matrices A,B are column equivalent if and only if A can be obtained from B by elementary column operations.

Lemma 1:

The interchange of two columns in a given matrix A is equivalent to a multiplication between a matrix A and E1 .

Proof:

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

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

(3) Let In be the n x n identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E1 be the matrix In after the columns i,j are interchanged.

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

QED

Lemma 2:

The multiplication of any column in a matrix A by a nonzero scalar α is equivalent to a multiplication between a matrix A and E2.

Proof:

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

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

(3) Let In be the n x n identity matrix. [See Definition 1 here for definition of the identity matrix]

(4) Let E2 be the matrix In after the column i is multiplied by α.

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

QED

Lemma 3:

The addition of a scalar multiple α of some column i to another column j in the matrix A is equivalent to a multiplication between a matrix A and E3.

Proof:

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

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

(3) Let In be the n x n identity matrix. [See Definition 1 here for definition of the identity matrix]

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

(5) Then, A' = AE3. [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 Column Equivalence

A is column equivalent to B if and only if B = AP where P is the product of elementary matrices P = Ea*Eb*...*Ez and P is invertible.

Proof:

(1) Assume that A is column equivalent to B. [See Definition 5 above for definition of column equivalence]

(2) Then A can be derived from B using n elementary operations

(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=A0Ea

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

(6) Using substitution, we have:

A2 = AEbEa

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

An = AEz*...*Ea

(8) Assume that B = AP 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 = ([A...Ec]Eb)Ea)

(10) So, by definition of column equivalence (see Definition 4 above), we can conclude that A is column 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
• Hans Schneider, George Philip Barker, , 1989.