$U^TA_1V$ is a rank-one matrix?

Question

To give a little bit of context, the question I am asking is related to SVD decomposition. More specifically, we are trying to prove that the best rank one approximation for $A_1$ is $\sigma_1 u_{1} v_{1}^{T}$

let $A_1$ be some rank one matrix.

Let $\|\|$ represent the Frobenius Norm of a matrix.

$$\|A-A_{1}\|=\|U\Sigma V^{T}-A_{1}\|= \|\Sigma -U^TA_1V\|$$

In the paper (pg 19) http://www.math.umn.edu/~lerman/math5467/svd.pdf, they let $U^TA_1V=\alpha x y^{T}$, where $\alpha$ is positive and $x$ and $y$ are both unit vectors of lengths $m$ and $n$ respectively.

My question is how do they know that $U^TA_1V$ is a rank-one matrix such that they can make that general substitution.

Answer 1

One can use the following property of rank and matrix multiplication:

For any two matrices of appropriate size, the rank of the product is less than or equal to the rank of either of multiplicands: $ \forall A \in \mathbb R^{m\times n}, \ B \in \mathbb R^{n\times k} \ \operatorname{rank}\left(AB\right) \le \min \big(\!\operatorname{rank} \left(A\right), \operatorname{rank} \left(B\right)\! \big). $

Recall also Sylvester rank inequality:

$ \forall A \in \mathbb R^{m\times n}, \ B \in \mathbb R^{n\times k} \quad \operatorname{rank}\left(A\right) + \operatorname{rank}\left(B\right) - n \le \operatorname{rank}\left(AB\right) . $

---

Since $A_1$ is a rank $1$ matrix, and $U, V$ are unitary $n\times n$ matrices (i.e. of rank $n$), we have $$ \operatorname{rank}\left(U^T A_1 V\right) \le \min \big(\!\operatorname{rank}\left(U^T A_1\right),\operatorname{rank} V \big) = \min\Big(\!\min\big(\!\operatorname{rank}U^T,\operatorname{rank}A_1\big),n\Big). \\ \operatorname{rank}\left(U^T A_1 V\right) \le \min \Big(\!\min \big(n ,1 \big) , n\Big) = \min \big(1, n\big) = 1. $$ Therefore $$ \boxed{\ \operatorname{rank}\left(U^T A_1 V\right) \le 1\ } \label{1} \tag{*} $$

On the other handy, by Sylvester inequality we have $$ \operatorname{rank}\left(U^T A_1 V\right) \ge \operatorname{rank}\left(U^T A_1\right) + \operatorname{rank}\left(V\right) - n = \operatorname{rank}\left(U^T A_1\right) \\ \operatorname{rank}\left(U^T A_1 V\right) \ge \operatorname{rank}\left(U^T\right) + \operatorname{rank}\left(A_1\right) - n = 1 $$

Thus, $$\boxed{\ \operatorname{rank}\left(U^T A_1 V\right) \ge 1\ } \label{2} \tag{**} $$

Combining $\eqref{1}$ and $\eqref{2}$, we conclude that $$ \boxed{\boxed{\ \operatorname{rank}\left(U^T A_1 V\right) = 1\ }} $$