# Proof of lower-rank matrix factorization

Let and and , prove that .

We can determine by applying row operations on .

First, we will let the second row of after the first row operation be: .

Next, the third row of after the second row operation would be: .

Soon, we will come to () which is a linear combination of , so the th row of after the th row operation would be: . We can swap row here but basically we have , hence cannot exceed .

It is worth noting that . For example, if , there is no doubt that . I also don’t think that , however, I will not go too deep into this matter.