4Matrices and linear equations
IA Vectors and Matrices
4.4 Matrix rank
Consider a linear map
α
:
R
n
→ R
m
. Recall the rank
r
(
α
) is the dimension of
the image. Suppose that the matrix
A
is associated with the linear map. We
also call r(A) the rank of A.
Recall that if the standard basis is
e
1
, ···e
n
, then
Ae
1
, ··· , Ae
n
span the
image (but not necessarily linearly independent).
Further,
Ae
1
, ··· , Ae
n
are the columns of the matrix
A
. Hence
r
(
A
) is the
number of linearly independent columns.
Definition
(Column and row rank of linear map)
.
The column rank of a matrix
is the maximum number of linearly independent columns.
The row rank of a matrix is the maximum number of linearly independent
rows.
Theorem. The column rank and row rank are equal for any m × n matrix.
Proof.
Let
r
be the row rank of
A
. Write the biggest set of linearly independent
rows as
v
T
1
, v
T
2
, ···v
T
r
or in component form
v
T
k
= (
v
k1
, v
k2
, ··· , v
kn
) for
k
=
1, 2, ··· , r.
Now denote the ith row of A as r
T
i
= (A
i1
, A
i2
, ···A
in
).
Note that every row of
A
can be written as a linear combination of the
v
’s.
(If
r
i
cannot be written as a linear combination of the
v
’s, then it is independent
of the
v
’s and
v
is not the maximum collection of linearly independent rows)
Write
r
T
i
=
r
X
k=1
C
ik
v
T
k
.
For some coefficients C
ik
with 1 ≤ i ≤ m and 1 ≤ k ≤ r.
Now the elements of A are
A
ij
= (r
i
)
T
j
=
r
X
k=1
C
ik
(v
k
)
j
,
or
A
1j
A
2j
.
.
.
A
mj
=
r
X
k=1
v
k
j
C
1k
C
2k
.
.
.
C
mk
So every column of
A
can be written as a linear combination of the
r
column
vectors c
k
. Then the column rank of A ≤ r, the row rank of A.
Apply the same argument to
A
T
to see that the row rank is
≤
the column
rank.