Every finite-dimensional matrix has a rank decomposition: Let
A
be an
m
×
n
matrix whose column rank is
r
. Therefore, there are
r
linearly independent columns in
A
; equivalently, the dimension of the column space of
A
is
r
. Let
c
1
,
c
2
,
…
,
c
r
be any basis for the column space of
A
and place them as column vectors to form the
m
×
r
matrix
C
=
[
c
1
:
c
2
:
…
:
c
r
]
. Therefore, every column vector of
A
is a linear combination of the columns of
C
. To be precise, if
A
=
[
a
1
:
a
2
:
…
:
a
n
]
is an
m
×
n
matrix with
a
j
as the
j
-th column, then
a
j
=
f
1
j
c
1
+
f
2
j
c
2
+
⋯
+
f
r
j
c
r
,
where
f
i
j
's are the scalar coefficients of
a
j
in terms of the basis
c
1
,
c
2
,
…
,
c
r
. This implies that
A
=
C
F
, where
f
i
j
is the
(
i
,
j
)
-th element of
F
.
If
A
=
C
1
F
1
is rank factorization, taking
C
2
=
C
1
R
and
F
2
=
R
−
1
F
1
gives another rank factorization for any invertible matrix
R
of compatible dimensions.
Conversely, if
A
=
F
1
G
1
=
F
2
G
2
are two rank factorizations of
A
, then there exists an invertible matrix
R
such that
F
1
=
F
2
R
and
G
1
=
R
−
1
G
2
.
In practice, we can construct one specific rank factorization as follows: we can compute
B
, the reduced row echelon form of
A
. Then
C
is obtained by removing from
A
all non-pivot columns, and
F
by eliminating all zero rows of
B
.
Consider the matrix
A
=
[
1
3
1
4
2
7
3
9
1
5
3
1
1
2
0
8
]
∼
[
1
0
−
2
0
0
1
1
0
0
0
0
1
0
0
0
0
]
=
B
.
B
is in reduced echelon form. Then
C
is obtained by removing the third column of
A
, the only one which is not a pivot column, and
F
by getting rid of the last row of zeroes, so
C
=
[
1
3
4
2
7
9
1
5
1
1
2
8
]
,
F
=
[
1
0
−
2
0
0
1
1
0
0
0
0
1
]
.
It is straightforward to check that
A
=
[
1
3
1
4
2
7
3
9
1
5
3
1
1
2
0
8
]
=
[
1
3
4
2
7
9
1
5
1
1
2
8
]
[
1
0
−
2
0
0
1
1
0
0
0
0
1
]
=
C
F
.
Let
P
be an
n
×
n
permutation matrix such that
A
P
=
(
C
,
D
)
in block partitioned form, where the columns of
C
are the
r
pivot columns of
A
. Every column of
D
is a linear combination of the columns of
C
, so there is a matrix
G
such that
D
=
C
G
, where the columns of
G
contain the coefficients of each of those linear combinations. So
A
P
=
(
C
,
C
G
)
=
C
(
I
r
,
G
)
,
I
r
being the
r
×
r
identity matrix. We will show now that
(
I
r
,
G
)
=
F
P
.
Transforming
A
P
into its reduced row echelon form amounts to left-multiplying by a matrix
E
which is a product of elementary matrices, so
E
A
P
=
B
P
=
E
C
(
I
r
,
G
)
, where
E
C
=
(
I
r
0
)
. We then can write
B
P
=
(
I
r
G
0
0
)
, which allows us to identify
(
I
r
,
G
)
=
F
P
, i.e. the nonzero
r
rows of the reduced echelon form, with the same permutation on the columns as we did for
A
. We thus have
A
P
=
C
F
P
, and since
P
is invertible this implies
A
=
C
F
, and the proof is complete.
One can also construct a full rank factorization of
A
by using its singular value decomposition
A
=
U
Σ
V
∗
=
[
U
1
U
2
]
[
Σ
r
0
0
0
]
[
V
1
∗
V
2
∗
]
=
U
1
(
Σ
r
V
1
∗
)
.
Since
U
1
is a full column rank matrix and
Σ
r
V
1
∗
is a full row rank matrix, we can take
C
=
U
1
and
F
=
Σ
r
V
1
∗
.
An immediate consequence of rank factorization is that the rank of
A
is equal to the rank of its transpose
A
T
. Since the columns of
A
are the rows of
A
T
, the column rank of
A
equals its row rank.
Proof: To see why this is true, let us first define rank to mean column rank. Since
A
=
C
F
, it follows that
A
T
=
F
T
C
T
. From the definition of matrix multiplication, this means that each column of
A
T
is a linear combination of the columns of
F
T
. Therefore, the column space of
A
T
is contained within the column space of
F
T
and, hence, rank(
A
T
) ≤ rank(
F
T
). Now,
F
T
is
n
×
r
, so there are
r
columns in
F
T
and, hence, rank(
A
T
) ≤
r
= rank(
A
). This proves that rank(
A
T
)
≤ rank(
A
). Now apply the result to
A
T
to obtain the reverse inequality: since
(
A
T
)
T
=
A
, we can write rank(
A
) = rank(
(
A
T
)
T
)
≤ rank(
A
T
). This proves rank(
A
)
≤ rank(
A
T
). We have, therefore, proved rank(
A
T
)
≤ rank(
A
) and rank(
A
) ≤ rank(
A
T
), so rank(
A
) = rank(
A
T
). (Also see the first proof of column rank = row rank under rank).
