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 E₁ .

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

(5) Then, A' = AE₁. [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₂.

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₂ be the matrix I_n after the column i is multiplied by α.

(5) Then, A' = AE₂. [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₃.

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₃ be the matrix I_n where position i in column j is replaced by α instead of 0.

(5) Then, A' = AE₃. [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 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₀ = 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₁=A₀E_a

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

(6) Using substitution, we have:

A₂ = AE_bE_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.

Row-Column Equivalence

In today's blog, I show that the concept of row-column equivalence (row equivalence and/or column equivalence) can demonstrate that all n x m matrices are products of elementary matrices. I will later use this result to demonstrate that cofactor expansion can be used a method to evaluate the determinant of an n x m matrix.

The content in today's blog is taken from Matrices and Linear Transformations by Charles G. Cullen and also from Matrices and Linear Algebra by Hans Schneider and George Phillip Barker.

Definition 1: Row-Column Equivalence

Two matrices A,B are row-column equivalent if and only if A can be obtained from B by a sequence of operations each of which is an elementary row operation (see Definition 4, here) or an elementary column operation (see Definition 4, here).

Definition 2: RC-Canonical Form

An n x m matrix C is in RC-Canonical Form if for some 0 ≤ r ≤ min(n,m):

if i ≤ r and i = j, then c_i,j = 1

otherwise: c_i,j = 0.

This is similar to reduced echelon form (see Definition 2, here) except that all values are either 0 or 1 and the only nonzero values are leading entries (see Definition 2, here). If 0_s is an n x n matrix that consists entirely of 0's, then we can think of a matrix in RC-canonical form as:




Theorem 1:

If A is row-column equivalent to B, then there exists invertible matrices P,Q such that:

C = PAQ

Proof:

(1) Assume that A is row-column equivalent to B.

(2) Thus, B is obtained from A by a sequence of elementary row operations and elementary column operations.

(3) Let us separate out the row operations so that we have E₁E₂*...*E_n

[See Theorem 5, here for proof that applying elementary row operations is equivalent to a product of elementary matrices.]

(4) Let us separate out the column operations so that we have:
F₁F₂*...*F_n

[See Theorem 5, here for proof that applying elementary column operations is equivalent to a product of elementary matrices.]

(5) Thus, B = E₁*...*E_nAF₁*...*F_n

(6) Let P = E₁*...*E_n

(7) Let Q = F₁*...*F_n

(8) It is clear that P is invertible since it is the product (see Corollary 3.1, here) of E_i which are each invertible (See Lemma 4, here).

(9) It is also clear that Q is invertible since it is the product (see Corollary 3.1, here) of F_i which are each invertible (see Lemma 4, here).

QED

Corollary 1.1: If A and C are row-column equivalent, then there exists a matrix B such that A is row equivalent to B and B is column equivalent to C.

Proof:

(1) Let A be row-column equivalent to C.

(2) Then, there exists P,Q that are invertible such that C = PAQ where P is a product of elementary row operations and Q is a product of elementary column operations. [By Theorem 1 above]

(3) Let B = PA. It is clear that A is row equivalent to B since P is a product of elementary row operations. [See Theorem 5, here]

(4) It is also clear that C = (PA)Q = BQ. Since Q is a product of elementary column operations, so that C is column equivalent to B. [See Theorem 5, here]

QED

Definition 3: I_r+0

This is an m x n matrix where r ≤ min(m,n) and:

a_i,j = 1 if i ≤ r and i=j

otherwise, a_i,j = 0

As should be clear, I_r+0 is an m x n matrix that is in RC-Canonical Form.

Definition 4: rank

Since the row rank of a matrix A = the column rank of matrix A (see Theorem 2, here) we can refer to this value as the rank of A.

Lemma 2: For each r where 0 ≤ r ≤ min(m,n), there is precisely one m x n matrix in RC-canonical form of rank r that equals I_r+0.

Proof:

(1) I_r+0 is an m x n matrix in RC-canonical form of rank r so there is at least one.

(2) Let C be an m x n matrix in RC-canonical form of rank r.

(3) Let's assume that C corresponds to I_s+0

(4) Then the row rank of C is s since the first s rows of I_s+0 are linearly independent.

[See Definition 1, here for definition of linear independence; see Definition 2, here for definition of row rank]

(5) But then s=r since the row rank of C is r and we have shown that C=I_s+0 = I_r+0 since both I_s+0 and I_r+0 are n x m matrices.

QED

Lemma 3: If A is row column equivalent to B, then rank A = rank C.

Proof:

(1) If A is row column equivalent to B, then there exists a matrix C such that A is row equivalent to C and C is column equivalent to B. [See Corollary 1.1 above]

(2) Now, A has the same row rank as C.

[See Corollary 1.1, here for proof that they have the same row space; See Definition 2 here to see that same row space implies same row rank]

(3) C has the same column rank as B.

[See Corollary 1.1, here for proof that they have the same column space; See Definition 3 here to see that same column space implies same column rank]

(4) The column rank of C = the row rank of C [See Theorem 2, here]

(5) So we can conclude that that the row rank of A = column rank of C which is the same as saying that the rank of A = rank of C.

QED

Theorem 4: Existence of RC-canonical form equivalent

Every m x n matrix is row-column equivalent to a matrix in RC-canonical form

Proof:

(1) Every m x n matrix is row equivalent to a unique matrix in reduced echelon form. [See Corollary 3.1, here]

(2) We can assume that a matrix B is in reduced echelon form and that it has a nonzero element b_h,k which is not a leading entry.

If a reduced echelon form does not have such an element, then it is already in RC-canonical form.

(3) Let l(i) be the column for each leading entry in row i.

(4) We can now apply the elementary column operation: A_{(kCj + Ci)} with k = -b_h,k and j = l(i) to column i.

(5) Since B is in reduced echelon form, we know that column l(i) is all zeros except for row i where it is 1.

(6) In this way we can see that the column operation A_{((-bh,k)Cl(i) + Ci)} results in b_h,k=0 but does not change any other value in the column.

(7) After repeatedly applying this column operation, we have removed all nonzero values which are not leading entries.

(8) Since these nonzero elements which were not leading entries could not occur in the same column as a leading entry (see Definition 2, here for definition of reduced echelon form), we now are left with columns that are entirely zero.

(9) We can use the column operation A_{(Ci ↔ Cj)} to move all the zero columns after the nonzero columns.

(10) We now have r nonzero rows where 1 ≤ l(1) is less than l(2) is less than ... is less than l(r) ≤ r.

(11) It is clear that B is in RC-canonical form.

QED

Theorem 5: For every matrix, there is only one unique RC-canonical form that is row-column equivalent.

Proof:

(1) Let B,C be two matrixes in RC-canonical form that are row-column equivalent to a matrix A.

(2) Let r = the rank of A.

(3) By Lemma 3 above, it is clear that rank of B = rank of A and likewise rank of C = rank of A so therefore rank of B = rank of C = r.

(4) But then, by Lemma 2 above, B = C since there is only one m x n matrix in rc-canonical form with rank = r.

(5) This shows that there is only one matrix in RC-canonical form which is RC-equivalent to A.

QED

Theorem 6:

All matrices are the product of elementary matrices

Proof:

(1) Let A be an m x n matrix.

(2) Let A_rc be the unique rc-canonical form of A. [See Theorem 4 above for proof of its existence and Theorem 5 above for proof of its uniqueness]

(3) If the rank of A_rc = r, then A_rc=I_r+0.

(4) Now, I_r+0 = I_m*I_(0Rr+1)*I_(0Rr+2)*...*I_(0Rm).

(5) So, we can see that I_r+0 is the product of elementary matrices.

(6) Since A is row column equivalent to A_rc, it follows that there exists invertible matrices P,Q such that A = P(A_rc)Q. [See Theorem 1 above]

(7) Since P,Q are invertible, then they are composed of elementary matrices. [See Theorem 5, here]

(8) Therefore, we can conclude A = P(A_rc)Q is composed of elementary matrices since P is composed of elementary matrices, A_rc is composed of elementary matrices, and Q is composed of elementary matrices.

QED

References

• Charles G. Cullen, Matrices and Linear Transformations, Dover Publications, Inc., 1972.
• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.

Elementary Matrices

In a previous blog, I talked elementary matrices and showed that if two matrices A,B are row equivalent, then there exists a matrix P such that A = PB where P is a product of elementary matrices (see Theorem 5, here).

Today, I will extend this result and show that if a matrix A is invertible (see Definition 1, here), then it is equal to product of elementary matrices.

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

Lemma 1: Only square matrices are invertible.

Proof:

(1) Let A be an n x m matix where n ≠ m.

(2) To be invertible, there must exist a matrix B such that AB = BA = I (see Definition 1, here)

(3) Let's assume that B is a p x q matrix.

(4) In order for A to multiply with B, then p = m and the result AB is an n x q matrix. (See here for review of matrix multiplication)

(5) In order for B to multiply with A, q must = n and BA is then a p x m matrix.

(6) Since p must = m and q must = n, AB is an n x n matrix and BA is an m x m matrix.

(7) But AB ≠ BA since m ≠ n so there is no such B that satisfies the conditions in step #2.

(8) So, we reject our assumption in step #1 and conclude that n = m and A is therefore a square matrix.

QED

From a previous result, we know that each m x n matrix has a unique reduced echelon form (see Corollary 3.1, here).

Definition 1: A_r

I will denote the unique reduced echelon form of a given m x n matrix A as A_r.

[For review of reduced echelon form, see Definition 2, here]

Definition 2: Rank

The rank r of an m x n matrix A is the number of nonzero rows in its reduced echelon form A_r

Lemma 2: If A is invertible, then A_r is invertible.

Proof:

(1) A_r = E₁E₂...E_nA where E_i is an elementary matrix [See Theorem 5, here]

(2) Since each elementary matrix is invertible [see Lemma 4, here], we know that E₁E₂....E_n is invertible. [See Lemma 3, here]

(3) So, we can multiply the inverse of E₁*...*E_n to both sides to get:

(E₁*...*E_n)^-1A = I*A_r=A_r

(4) But since (E₁*...*E_n)^-1 is invertible and A is invertible, then A_r must also be invertible [See Lemma 3, here].

QED

Lemma 3: If a matrix A is invertible, then its rank is equal to its number of rows.

Proof:

(1) Assume that A is invertible.

(2) Since A is invertible, we know that A_r is invertible. [See Lemma 2 above]

(3) Let X = A_r^-1, B = A_r

(4) From Lemma 1 above, we know that A,A_r is an n x n matrix.

(5) Let e_*,n = B*x_*,n [NOTE: By e_*,n, I mean the vector of values including e_1,n ... e_n,n]

(6) Since BX = I_n, we know that e_n,n = 1 [See here for review of I_n]

(7) But we also know that e_n,n = ∑ (i=1,n) b_n,i*x_i,n [See here for review of matrix multiplication]

(8) So, therefore, it follows that the last row of A_r is nonzero.

(9) Since A_r is in reduced echelon form, it follows that all rows must be nonzero. [see Definition 2, here]

(10) Therefore, it follows that rank of A_r is n. [See Definition 2 above]

QED

Corollary 3.1: If a matrix A is invertible and has n rows, then A is row equivalent to I_n

Proof:

(1) Assume that A is invertible.

(2) Let n = the number of rows of A.

(3) By Lemma 3 above, its rank = n.

(4) Since its rank is n, we know that each row of A_r is nonzero and therefore contains a leading coefficient.

(5) But since A,A_r are square matricies (see Lemma 1 above), we know that they have n columns each since they have n rows each.

(6) Let l(i) = the column of leading nonzero element for A_r.

(7) l(i) = i for each row i since 1 ≤ l(1) ≤ l(2) is less than l(3) is less than ... is less than l(n) ≤ n.

(8) Thus a_i,i = 1 for i = 1 .. n

(9) Hence, every column of A_r contains a leading coefficient, and all other entries of A are 0.

(10) It therefore follows that A_r = I_n (See here for review of I_n, see Definition 2, here for review of reduced echelon form.)

QED

Lemma 4: If a matrix A is row equivalent to I_n, then it is equal to a product of elementary matrices.

Proof:

(1) Assume that A is row equivalent to I_n.

(2) Then there exists P such that A = PI_n where P is a product of elementary matrices. [See Theorem 5, here]

(3) But I_n = the elementary matrix = I_(1R1) [See Defintion 1, here]

(4) So A is a product of elementary matrices.

QED

Theorem 5: A matrix M is invertible if and only if it is a product of elementary matrices

Proof:

(1) Assume that a matrix M is invertible.

(2) Let n = the number of rows of M.

(3) Using Corollary 3.1 above, it follows that M is row equivalent to I_n.

(4) Using Lemma 4 above, this means that M is a product of elementary matrices.

(5) Assume that M is the product of elementary matrices so that A = E₁*E₂*...*E_n

(6) Since each elementary matrix is invertible [see Lemma 4, here], it follows that their product is also invertible [see Lemma 3, here].

QED

References

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