Previously in section, we discussed the row space
spanned on rows of an m×n matrix A. Its dimension
is called the row-rank. Similarly, we worked in
section with columns and showed that, for any
m×n matrix A, the dimension of its range (which
is also called the column space) is called column-rank. Now we show that these
two ranks are actually equal to each other in the following theorem.
Recall that a set of vectors β is said to generate or span a
vector space V if every element from
V can be represented as a linear combination of vectors from β.
Theorem:
For any m×n matrix A, its column rank and the row
rank are always equal.
Let A be a matrix of size m × n (with m rows and
n columns). Let the column rank of A be r and let
c1, c2, ... , cr
be any basis for the column space of A. Place these as the columns of
an m × r matrix C. Every column of A can be
expressed as a linear combination of the r columns in C. This
means that there is an r × n matrix R such that A
= CR. R is the matrix whose i-th column is formed from
the coefficients giving the i-th column of A as a linear combination of
the r columns of C. Now, each row of A is given by a
linear combination of the r rows of R. Therefore, the rows of
R form a spanning set of the row space of A and, by the
Steinitz exchange lemma, the row rank of A cannot exceed r. This proves that
the row rank of A is less than or equal to the column rank of A.
This result can be applied to any matrix, so apply the result to the transpose
of A. Since the row rank of the transpose of A is the column
rank of A and the column rank of the transpose of A is the row
rank of A, this establishes the reverse inequality and we obtain the
equality of the row rank and the column rank of A. (Also see rank factorization.)
Another proof:
Let A be a matrix of size m × n (with m rows and
n columns) with entries from ℝ whose row rank is r.
Therefore, the dimension of the row space of A is r. Let
x1, x2, ... , xr
be a basis of the row space of A. We claim that the vectors
Ax1, Ax2, ... ,
Axr are linearly independent. To see why, consider a linear
homogeneous relation involving these vectors with scalar coefficients
c1, c2, ... , cr:
where v = c1x1 +
c2x2 + ... +
crxr.
We make two observations: (a) v is a linear combination of vectors in
the row space of A, which implies that v belongs to the row space of
A, and (b) since Av = 0, the vector v is
orthogonal to every row vector of A and, hence, is orthogonal to every
vector in the row space of A. The facts (a) and (b) together imply that
v is orthogonal to itself, which proves that v = 0 or,
by the definition of v,
But recall that the xi were chosen as a basis of the row
space of A and so are linearly independent. This implies that
\( c_1 = c_2 = \cdots = c_r =0 . \) It follows that
Ax1, Ax2, ... ,
Axr are linearly independent.
Now, each Axi is obviously a vector in the column
space of A. So
Ax1, Ax2, ... ,
Axr is a set of r linearly independent vectors in the
column space of A and, hence, the dimension of the column space of
A (i.e., the column rank of A) must be at least as big as
r. This proves that row rank of A is no larger than the column
rank of A. Now apply this result to the transpose of A to get
the reverse inequality and conclude as in the previous proof.
Another proof:
If A = 0, then both row space and column space of A are
zero dimensional. Suppose A ≠ 0 and its rank is r.
Then its column space is spanned on r column vectors of A:
\[
{\bf c}_1 , {\bf c}_2 , \ldots , {\bf c}_r
\]
that comprise a basis for the range of A. We build
m×r matrix B of these basis column vectors.
Since each column vector of A is a linear combination of the columns of
B, there exits an r×n matrix X such that
A = BX. next we partition n×r matrix
XT into its column vectors:
Hence, the dimension of row space of A is less or equal to the
dimension of its column space. We can repeat the reverse combination and obtain
the required identity.
If A is an m×n matrix, then its
rank is the maximum number of linearly independent row vectors or column vectors.
This integer is denoted rank(A) or rankA.
Observation:
Elementary row operations and elementary column operations on a matrix are
rank preserving.
Observation:
The rank of any matrix equals the maximum number of its linearly independent
columns or rows; that is, the rank of a matrix is the dimension of the
subspace generated either by its columns or by its rows.
Observation:
The rank of any matrix equals the number of pivots; that is, the rank of a
matrix is the number of leading 1's in its Gauss-Jordan form.
Theorem:
Let A and B be two matrices of dimensions
m×n and n×k, so their product
AB exists. Then
Rank r of any n×k matrix B is the number of
its linearly independent rows or columns. The range of any matrix cannot exceed
the dimension of its image because r ≤ max{k, n}.
So matrix B maps n linearly independent vectors from space
ℝn into r linearly independent vectors. Next
application of matrix A deals with r linearly independent vectors
and therefore it maps into certain number of linearly independent vectors that
is less or equal to r.
has rank zero. However, ranks of each of these matrices are ones.
Theorem:
Let A be an m×n matrix. If p×m
matrix S has full column rank and n×q matrix
T has full row rank, then
rank(AT) = rank(A);
rank(SA) = rank(A);
rank(SAT) = rank(A).
All these statements follow from one observation that an invertible matrix
multiplication is an isomorphism and as so it does not change the dimension of
a space it acts on. Recall that an isomorphism maps linearly independent sets
into linearly independent sets.
On the other hand, products of matrix A with S1 and
T1 give
MatrixRank[S1.A]
2
MatrixRank[A.T1]
2
■
We preset some theoretical results that fasilitate proving important
observations about ranks of matrices.
Theorem:
Let A be an m×n matrix of rank r. By means of
a finite number of elementary row and column operations A can be
transformed into the "diagonal" matrix
where I is the identity matrix of dimension r and three matrices
0 are rectangular matrices with all zero entries.
We suppose that A ≠ 0 and r = rankA > 0. The
proof is by mathematical induction on m, the number of rows of A.
Suppose that m = 1. By means of interchanging any two rows or columns
and multiplying columns by a nonzero number, matrix A can be transformed into a matrix with a 1 in the (1,1) position. By means of at most n-1
elementary operations (adding rows or columns with some multiples) this matrix
can in turn be transformed into the matrix
Note that there is one linearly independent column in Λ. So its rank is
equal to rank of A, that is, 1.
Next assume that the theorem hlds for any matrix with at most m-1 rows
(for some m>1). We must prove that the theorem holds for any matrix
with m rows.
Corollary:
Let A be an m×n matrix of rank r. Then there
exist invertible matrices X and Y of sizes m×m and n×n, respectively, such that Λ =
XAY, where the "diagonal" matrix Λ is described in the
previous theorem.
Corollary:
Let A be an m×n matrix. Then rank(A) =
rank(AT).
Corollary:
Every invertible matrix is a product of elementary matrices.
If A is an invertible n×n matrix, then rank(A)
= n. Hence, by Corollary, there exist invertible matrices X
and Y such that Λ = XAY, where Λ is
the identity matrix of size n, that is Λ = I.
As in the previous proof, not that X = EpEp-1 ... E1 and Y =
G1G2 ... Gq, where
Ei's and Gj's are elementary matrices.
Hence,
Example: The set of monomials \( \left\{ 1, x, x^2 , \ldots , x^n \right\} \)
form a basis in the set of all polynomials of degree up to n. It has dimension n+1.
■
Example: The infinite set of monomials \( \left\{ 1, x, x^2 , \ldots , x^n , \ldots \right\} \)
form a basis in the set of all polynomials.
■
