Proof of lower-rank matrix factorization

Let U = \begin{bmatrix} u^{T}_{1}\\ u^{T}_{2}\\ ...\\ u^{T}_{m} \end{bmatrix} \in \mathbb{R}^{m \times k}, u_{i} \in \mathbb{R}^{k} and  V = \begin{bmatrix} v^{T}_{1}\\ v^{T}_{2}\\ ...\\ v^{T}_{n} \end{bmatrix} \in \mathbb{R}^{n \times k}, v_{j} \in \mathbb{R}^{k} and  k < \min(m, n), prove that \text{rank}(UV^{T}) \leq k.

We can determine \text{rank}(UV^{T}) by applying row operations on UV^{T}.

First, we will let the second row of UV^{T} after the first row operation be:  (u^{T}_{2} - \alpha u^{T}_{1})V^{T}.

Next, the third row of UV^{T} after the second row operation would be:  (u^{T}_{3} - \beta(u^{T}_{2} - \alpha u^{T}_{1}) - \gamma u^{T}_{1})V^{T}.

Soon, we will come to u_{i} (i < k) which is a linear combination of u_{1} , ... , u_{i-1}, so the ith row of UV^{T} after the i - 1th row operation would be: 0^{T}V^{T} = 0^{T}. We can swap row here but basically we have \text{rank}(U) \leq k, hence  \text{rank}(UV^{T}) cannot exceed k.

It is worth noting that  \text{rank}(UV^{T}) \leq \text{rank}(U). For example, if v_{1} = v_{2} = ... = v_{n}, there is no doubt that \text{rank}(UV^{T}) = 1  \leq \text{rank}(U). I also don’t think that  \text{rank}(UV^{T}) = \min(\text{rank}(U), \text{rank}(V)), however, I will not go too deep into this matter.


Leave a Reply

Your email address will not be published. Required fields are marked *