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 E

_{1}.

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 I

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

(4) Let E

_{1}be the matrix I

_{n}after the columns i,j are interchanged.

(5) Then, A' = AE

_{1}. [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 E

_{2}.

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 I

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

(4) Let E

_{2}be the matrix I

_{n}after the column i is multiplied by α.

(5) Then, A' = AE

_{2}. [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 E

_{3}.

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 I

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

(4) Let E

_{3}be the matrix I

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

(5) Then, A' = AE

_{3}. [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 Column Equivalence

A is column equivalent to B if and only if B = AP 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 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 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}=

_{}A

_{0}E

_{a}

(5) Let A

_{2}= A

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

_{b}such that A

_{2}=

_{}A

_{1}E

_{b}.

(6) Using substitution, we have:

A

_{2}= AE

_{b}E

_{a}

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

A

_{n}= AE

_{z}*...*E

_{a}

(8) Assume that B = AP 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 =

_{}(

_{}[A...E

_{c}]E

_{b})E

_{a})

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