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: Span
- Let α1, α2, ..., αn be an arbitrary vector space V.
- The smallest subspace of V containing all the given vectors is called the subspace spanned by the α or the subspace generated by αi.
- This subspace will be denoted Span{α1, α2, ..., αn}
- If Span {α1, α2, ..., αk} = V, then we say that {α1, α2, ..., αk} spans V.
Span {α1, α2, ..., αn} ⊆ W.
Definition 2: Column Space of a matrix M
The Column Space of a matrix M is the subspace of Fn x 1 spanned by the columns of M. This is denoted as CS(M).
Lemma 1:
For any n x m matrix A and any matrix Q such that AQ is defined we have:
CS(AQ) ⊆ CS(A) and if Q is invertible, CS(AQ) = CS(A)
Proof:
(1) Let B = AQ
(2) The columns of B are linear combinations of the columns of A. [See Lemma 3, here]
(3) Since the columns of B are linear combinations of the columns of A:
C(B) ⊆ C(A) [See Corollary 1.1, here]
(4) Using step #1 above gives us:
C(AQ) ⊆ C(A)
(5) If Q is invertible, then there exists a value Q-1 such that Q-1Q = 1.
[Review: see Definition 1 here for definition of invertible.]
(6) So that:
BQ-1 = AQQ-1 = A(Q-1Q) = A*I = A
(7) From this, the columns of A are linear combinations of the columns of B. [See Lemma 3, here]
(8) So that:
C(A) ⊆ C(B) [See Corollary 1.1, here]
(9) Using step #1 above gives us:
C(A) ⊆ C(AQ)
(10) Thus, if Q is invertible, then:
C(A) ⊆ C(AQ) (step #4) and C(AQ) ⊆ C(A) (step #9) which gives us C(AQ)=C(A)
QED
Corollary 1.1: If B is column equivalent to A, then C(B) = C(A)
Proof:
(1) If B is column equivalent to A, then B = AQ and Q is invertible. [See Theorem 5, here]
(2) Using Lemma 1 above, we can then conclude that C(AQ) = C(A)
(3) But since B=AQ, this gives us that C(B) = C(A)
QED
Definition 3: Column rank
The column rank of a matrix A is the dimension of the column space, that is, dim C(A).
[Review: see Definition 2 here for definition of the dimension of a vector space which is abbreviated as dim V.]
Corollary 1.2:
For any matrix Q for which AQ is defined:
(1) Column rank AQ ≤ column rank A
(2) If Q is invertible, then column rank AQ = column rank A
Proof:
(1) Using Lemma 1 above, we have:
C(AQ) ⊆ C(A)
(2) Then Column rank AQ ≤ column rank A [See Lemma 4, here]
(3) If Q is invertible, then C(AQ) = C(A)
(4) This then gives us that Column rank AQ = column rank A.
QED
Theorem 2: For any matrix A, row rank A = column rank A
Proof:
(1) Let A be an m x n matrix.
(2) Let r = the row rank of A
(3) By the definition of row rank (see Definition 2, here), we can choose r rows of A to form a basis (see Definition 2, here) for R(A) [See Definition 1, here for review of the notation R(A)]
(4) Let X =
(5) So, we can see that X is an r x n matrix since each ai,* represents a row of the matrix A.
(6) By the definition of R(A), it is clear that each row of A is a linear combination of the X which is a basis:
(See Definition 5, here for review of linear combinations; By ai,* notation, I mean the entire row, that is, [ ai,1 ai,2 ... ai,n ] )
(7) Let Y =
(8) Now, A =
where r ≤ m.
(9) Using step #6, we have that A =
(10) If we carry out the summation, we get A =
(11) So, we can see that:
A = YX
since Y is an m x r matrix and X is an r x n matrix so YX is an m x n matrix.
(12) From this equation, we can see that each column of A is a linear combination of the r columns y*,1, ..., y*,r. [See Lemma 3, here]
(13) So, we can conclude that C(A) ⊆ C(Y). [See Corollary 1.1, here]
(14) Since Y has r columns (see step #7 above), it follows that column rank A = dim C(A) ≤ dim C(Y) ≤ r = row rank A.
(15) Let c = the column rank A
(16) By the definition of column rank (see Definition 3 above), we can choose c columns of A to form a basis for C(A)
(17) Let U =
(18) So, we can see that U is an m x c matrix since each a*,j represents a column of the matrix A.
(19) By the definition of C(A) [See Definition 2 above], it is clear that each column of A is a linear combination of U which is a basis:
(20) Let Y =
(21) Now, A =
(22) So, we can see that:
A = UY
since U is an m x c matrix and Y is an c x n matrix so UY is an m x n matrix.
(23) From this equation, we can see that each row A is a linear combination of the c rows y1,*, ..., yc,*. [See Lemma 2, here]
(24) So, we can conclude that R(A) ⊆ R(Y). [See Lemma 1, here]
(25) Since Y has c rows (see step #20 above), it follows that row rank A = dim R(A) ≤ dim R(Y) ≤ c = column rank A.
(26) So we have that row rank A ≤ column rank A and column rank A ≤ row rank A. It follows that column rank A = row rank A.
QED
References
- Charles G. Cullen, Matrices and Linear Transformations
, Dover Publications, Inc., 1972.
- Hans Schneider, George Philip Barker, Matrices and Linear Algebra
, 1989.
