- Source: Rank factorization
In mathematics, given a field
F
{\displaystyle \mathbb {F} }
, nonnegative integers
m
,
n
{\displaystyle m,n}
, and a matrix
A
∈
F
m
×
n
{\displaystyle A\in \mathbb {F} ^{m\times n}}
, a rank decomposition or rank factorization of A is a factorization of A of the form A = CF, where
C
∈
F
m
×
r
{\displaystyle C\in \mathbb {F} ^{m\times r}}
and
F
∈
F
r
×
n
{\displaystyle F\in \mathbb {F} ^{r\times n}}
, where
r
=
rank
A
{\displaystyle r=\operatorname {rank} A}
is the rank of
A
{\displaystyle A}
.
Existence
Every finite-dimensional matrix has a rank decomposition: Let
A
{\textstyle A}
be an
m
×
n
{\textstyle m\times n}
matrix whose column rank is
r
{\textstyle r}
. Therefore, there are
r
{\textstyle r}
linearly independent columns in
A
{\textstyle A}
; equivalently, the dimension of the column space of
A
{\textstyle A}
is
r
{\textstyle r}
. Let
c
1
,
c
2
,
…
,
c
r
{\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}
be any basis for the column space of
A
{\textstyle A}
and place them as column vectors to form the
m
×
r
{\textstyle m\times r}
matrix
C
=
[
c
1
c
2
⋯
c
r
]
{\textstyle C={\begin{bmatrix}\mathbf {c} _{1}&\mathbf {c} _{2}&\cdots &\mathbf {c} _{r}\end{bmatrix}}}
. Therefore, every column vector of
A
{\textstyle A}
is a linear combination of the columns of
C
{\textstyle C}
. To be precise, if
A
=
[
a
1
a
2
⋯
a
n
]
{\textstyle A={\begin{bmatrix}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}
is an
m
×
n
{\textstyle m\times n}
matrix with
a
j
{\textstyle \mathbf {a} _{j}}
as the
j
{\textstyle j}
-th column, then
a
j
=
f
1
j
c
1
+
f
2
j
c
2
+
⋯
+
f
r
j
c
r
,
{\displaystyle \mathbf {a} _{j}=f_{1j}\mathbf {c} _{1}+f_{2j}\mathbf {c} _{2}+\cdots +f_{rj}\mathbf {c} _{r},}
where
f
i
j
{\textstyle f_{ij}}
's are the scalar coefficients of
a
j
{\textstyle \mathbf {a} _{j}}
in terms of the basis
c
1
,
c
2
,
…
,
c
r
{\textstyle \mathbf {c} _{1},\mathbf {c} _{2},\ldots ,\mathbf {c} _{r}}
. This implies that
A
=
C
F
{\textstyle A=CF}
, where
f
i
j
{\textstyle f_{ij}}
is the
(
i
,
j
)
{\textstyle (i,j)}
-th element of
F
{\textstyle F}
.
Non-uniqueness
If
A
=
C
1
F
1
{\textstyle A=C_{1}F_{1}}
is a rank factorization, taking
C
2
=
C
1
R
{\textstyle C_{2}=C_{1}R}
and
F
2
=
R
−
1
F
1
{\textstyle F_{2}=R^{-1}F_{1}}
gives another rank factorization for any invertible matrix
R
{\textstyle R}
of compatible dimensions.
Conversely, if
A
=
F
1
G
1
=
F
2
G
2
{\textstyle A=F_{1}G_{1}=F_{2}G_{2}}
are two rank factorizations of
A
{\textstyle A}
, then there exists an invertible matrix
R
{\textstyle R}
such that
F
1
=
F
2
R
{\textstyle F_{1}=F_{2}R}
and
G
1
=
R
−
1
G
2
{\textstyle G_{1}=R^{-1}G_{2}}
.
Construction
= Rank factorization from reduced row echelon forms
=In practice, we can construct one specific rank factorization as follows: we can compute
B
{\textstyle B}
, the reduced row echelon form of
A
{\textstyle A}
. Then
C
{\textstyle C}
is obtained by removing from
A
{\textstyle A}
all non-pivot columns (which can be determined by looking for columns in
B
{\textstyle B}
which do not contain a pivot), and
F
{\textstyle F}
is obtained by eliminating any all-zero rows of
B
{\textstyle B}
.
Note: For a full-rank square matrix (i.e. when
n
=
m
=
r
{\textstyle n=m=r}
), this procedure will yield the trivial result
C
=
A
{\textstyle C=A}
and
F
=
B
=
I
n
{\textstyle F=B=I_{n}}
(the
n
×
n
{\textstyle n\times n}
identity matrix).
Example
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
.
{\displaystyle A={\begin{bmatrix}1&3&1&4\\2&7&3&9\\1&5&3&1\\1&2&0&8\end{bmatrix}}\sim {\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}}=B{\text{.}}}
B
{\textstyle B}
is in reduced echelon form.
Then
C
{\textstyle C}
is obtained by removing the third column of
A
{\textstyle A}
, the only one which is not a pivot column, and
F
{\textstyle F}
by getting rid of the last row of zeroes from
B
{\textstyle B}
, 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
]
.
{\displaystyle C={\begin{bmatrix}1&3&4\\2&7&9\\1&5&1\\1&2&8\end{bmatrix}}{\text{,}}\qquad F={\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\end{bmatrix}}{\text{.}}}
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
.
{\displaystyle A={\begin{bmatrix}1&3&1&4\\2&7&3&9\\1&5&3&1\\1&2&0&8\end{bmatrix}}={\begin{bmatrix}1&3&4\\2&7&9\\1&5&1\\1&2&8\end{bmatrix}}{\begin{bmatrix}1&0&-2&0\\0&1&1&0\\0&0&0&1\end{bmatrix}}=CF{\text{.}}}
Proof
Let
P
{\textstyle P}
be an
n
×
n
{\textstyle n\times n}
permutation matrix such that
A
P
=
(
C
,
D
)
{\textstyle AP=(C,D)}
in block partitioned form, where the columns of
C
{\textstyle C}
are the
r
{\textstyle r}
pivot columns of
A
{\textstyle A}
. Every column of
D
{\textstyle D}
is a linear combination of the columns of
C
{\textstyle C}
, so there is a matrix
G
{\textstyle G}
such that
D
=
C
G
{\textstyle D=CG}
, where the columns of
G
{\textstyle G}
contain the coefficients of each of those linear combinations. So
A
P
=
(
C
,
C
G
)
=
C
(
I
r
,
G
)
{\textstyle AP=(C,CG)=C(I_{r},G)}
,
I
r
{\textstyle I_{r}}
being the
r
×
r
{\textstyle r\times r}
identity matrix. We will show now that
(
I
r
,
G
)
=
F
P
{\textstyle (I_{r},G)=FP}
.
Transforming
A
{\textstyle A}
into its reduced row echelon form
B
{\textstyle B}
amounts to left-multiplying by a matrix
E
{\textstyle E}
which is a product of elementary matrices, so
E
A
P
=
B
P
=
E
C
(
I
r
,
G
)
{\textstyle EAP=BP=EC(I_{r},G)}
, where
E
C
=
(
I
r
0
)
{\textstyle EC={\begin{pmatrix}I_{r}\\0\end{pmatrix}}}
. We then can write
B
P
=
(
I
r
G
0
0
)
{\textstyle BP={\begin{pmatrix}I_{r}&G\\0&0\end{pmatrix}}}
, which allows us to identify
(
I
r
,
G
)
=
F
P
{\textstyle (I_{r},G)=FP}
, i.e. the nonzero
r
{\textstyle r}
rows of the reduced echelon form, with the same permutation on the columns as we did for
A
{\textstyle A}
. We thus have
A
P
=
C
F
P
{\textstyle AP=CFP}
, and since
P
{\textstyle P}
is invertible this implies
A
=
C
F
{\textstyle A=CF}
, and the proof is complete.
= Singular value decomposition
=If
F
∈
{
R
,
C
}
,
{\displaystyle \mathbb {F} \in \{\mathbb {R} ,\mathbb {C} \},}
then one can also construct a full-rank factorization of
A
{\textstyle A}
via a singular value decomposition
A
=
U
Σ
V
∗
=
[
U
1
U
2
]
[
Σ
r
0
0
0
]
[
V
1
∗
V
2
∗
]
=
U
1
(
Σ
r
V
1
∗
)
.
{\displaystyle A=U\Sigma V^{*}={\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}}{\begin{bmatrix}\Sigma _{r}&0\\0&0\end{bmatrix}}{\begin{bmatrix}V_{1}^{*}\\V_{2}^{*}\end{bmatrix}}=U_{1}\left(\Sigma _{r}V_{1}^{*}\right).}
Since
U
1
{\textstyle U_{1}}
is a full-column-rank matrix and
Σ
r
V
1
∗
{\textstyle \Sigma _{r}V_{1}^{*}}
is a full-row-rank matrix, we can take
C
=
U
1
{\textstyle C=U_{1}}
and
F
=
Σ
r
V
1
∗
{\textstyle F=\Sigma _{r}V_{1}^{*}}
.
Consequences
= rank(A) = rank(AT)
=An immediate consequence of rank factorization is that the rank of
A
{\textstyle A}
is equal to the rank of its transpose
A
T
{\textstyle A^{\textsf {T}}}
. Since the columns of
A
{\textstyle A}
are the rows of
A
T
{\textstyle A^{\textsf {T}}}
, the column rank of
A
{\textstyle 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
{\textstyle A=CF}
, it follows that
A
T
=
F
T
C
T
{\textstyle A^{\textsf {T}}=F^{\textsf {T}}C^{\textsf {T}}}
. From the definition of matrix multiplication, this means that each column of
A
T
{\textstyle A^{\textsf {T}}}
is a linear combination of the columns of
F
T
{\textstyle F^{\textsf {T}}}
. Therefore, the column space of
A
T
{\textstyle A^{\textsf {T}}}
is contained within the column space of
F
T
{\textstyle F^{\textsf {T}}}
and, hence,
rank
(
A
T
)
≤
rank
(
F
T
)
{\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(F^{\textsf {T}}\right)}
.
Now,
F
T
{\textstyle F^{\textsf {T}}}
is
n
×
r
{\textstyle n\times r}
, so there are
r
{\textstyle r}
columns in
F
T
{\textstyle F^{\textsf {T}}}
and, hence,
rank
(
A
T
)
≤
r
=
rank
(
A
)
{\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq r=\operatorname {rank} \left(A\right)}
. This proves that
rank
(
A
T
)
≤
rank
(
A
)
{\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}
.
Now apply the result to
A
T
{\textstyle A^{\textsf {T}}}
to obtain the reverse inequality: since
(
A
T
)
T
=
A
{\textstyle \left(A^{\textsf {T}}\right)^{\textsf {T}}=A}
, we can write
rank
(
A
)
=
rank
(
(
A
T
)
T
)
≤
rank
(
A
T
)
{\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(\left(A^{\textsf {T}}\right)^{\textsf {T}}\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}
. This proves
rank
(
A
)
≤
rank
(
A
T
)
{\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}
.
We have, therefore, proved
rank
(
A
T
)
≤
rank
(
A
)
{\textstyle \operatorname {rank} \left(A^{\textsf {T}}\right)\leq \operatorname {rank} \left(A\right)}
and
rank
(
A
)
≤
rank
(
A
T
)
{\textstyle \operatorname {rank} \left(A\right)\leq \operatorname {rank} \left(A^{\textsf {T}}\right)}
, so
rank
(
A
)
=
rank
(
A
T
)
{\textstyle \operatorname {rank} \left(A\right)=\operatorname {rank} \left(A^{\textsf {T}}\right)}
.