Rank of product of two orthogonal matrices

Question

For $U,V\in\mathbb{R}^{n\times r}$, where each column $u_i$ satisfies that $u_i^Tu_j=0,j\ne i, u_i^Tu_i=1,\forall i=1,...,r$. So is $v_i$. Suppose we have $$\Vert UU^T-VV^T \Vert<1$$ My question is how to prove the following: $$U^TV\text{ is full rank.}$$ Thanks!

Answer 1

We can show the following:

$U^TV$ is rank-deficient $\implies$ $\rho(UU^T-VV^T)\geq 1$,

where $\rho$ is the spectral radius of a matrix.

Since $UU^T-VV^T$ is symmetric, the eigenvalues of this matrix are real and for any symmetric matrix $X$ we have $\rho^2(X)=\rho(X^2)$. We can expand $$\tag{1} (UU^T-VV^T)^2=UU^T+VV^T-U(U^TV)V^T-V(V^TU)U^T $$ and see the $U^TV$ terms to pop out. Since $U^TV$ is rank-deficient, there is a nonzero vector $x$ such that $U^TVx=0$. We can express this vector as a combination of rows of $V$, that is, $x=V^Ty$ for some (nonzero) $y$. We can choose $x$ and $y$ such that $y^Ty=1$. We take this $y$ and compute the associated Rayleigh quotient of the squared matrix in (1) and see that $$ \begin{split} \rho^2(UU^T-VV^T) &\geq y^T(UU^T-VV^T)^2y \\&= y^TUU^Ty+x^Tx-y^TU(U^TVx)-(U^TVx)^TU^Ty \\&= y^TUU^Ty+x^Tx\geq x^Tx. \end{split} $$ So if $x^Tx\geq 1$, we are done. Indeed, we have $$ 1=y^Ty=y^T(I-VV^T)y+y^TVV^Ty\leq y^TVV^Ty=x^Tx. $$ Hence $\rho(UU^T-VV^T)\geq 1$.

We showed the following equivalent statement:

$\rho(UU^T-VV^T)<1$ $\implies$ $U^TV$ is not rank-deficient.

Any matrix norm $\|\cdot\|$ consistent with some vector norm is an upper bound on $\rho$ so we also have

$\|UU^T-VV^T\|<1$ $\implies$ $\rho(UU^T-VV^T)<1$ $\implies$ $U^TV$ is not rank-deficient.

Answer 2

Let $A=U^TV$. As $U$ has orthonormal columns, $UU^T$ is an orthogonal projection. Therefore \begin{aligned} \|UU^T-UAA^TU^T\|_2 &=\|UU^T(UU^T-VV^T)UU^T\|_2\\ &\le\|UU^T-VV^T\|_2\|UU^T\|_2^2\\ &=\|UU^T-VV^T\|_2\\ &=\rho(UU^T-VV^T)\\ &\le\|UU^T-VV^T\|<1. \end{aligned} (Note that we have used both the induced $2$-norm $\|\cdot\|_2$ and the given norm $\|\cdot\|$ above.)

Now suppose the contrary that $A$ is singular. Then $A^T$ is singular and $A^Tx=0$ for some nonzero vector $x$. Since $U$ has full column rank, $Ux\ne0$. Thus $\|(UU^T-UAA^TU^T)Ux\|_2=\|Ux\|_2\ne0$, which is a contradiction to $\|UU^T-UAA^TU^T\|_2<1$. Hence $A=U^TV$ must be nonsingular.