Let: $$ A = \left[ \begin{array}{cc} I & B \\ B^T & I \end{array} \right] $$
where:
$$\text{$B$ is $m \times m$ matrix with $||B||_2 < 1 $}$$
Let: $$B = U \Sigma V^T $$ denote the singular value decomposition of $B$.
I am trying to find the left singular vectors of $A$.
I know in order to do so I need to find eigenvalues of $A^T A $ and then their eigenvectors would be our left singular vectors. But how can I compute eigenvalues of block matrices? According to my prof, the left singular vectors of $A$ are the columns of the matrix
$$ X = \frac{1}{\sqrt{2}} \left[ \begin{array}{cc} U & U \\ V & -V \end{array} \right] $$
How is this possible ?
Best Answer
Presumably $B$ is real.
Since $B^T$ commute with $I$,
we have: $$ \det(\lambda I-A) = \det((\lambda-1)^2I-BB^T) = \det((\lambda-1)^2I-\Sigma^2). $$ Hence the eigenvalue matrix of $A$ is given by $(I+\Sigma)\oplus(I-\Sigma)$.
Since $A$ is real symmetric, its singular values are the absolute values of its eigenvalues.
At any rate, we have: \begin{align} A&=\pmatrix{UU^T&U\Sigma V^T\\ V\Sigma U^T&VV^T}\\ &=\pmatrix{U\\ &V} \pmatrix{I&\Sigma\\ \Sigma&I} \pmatrix{U^T\\ &V^T}\\ &=\pmatrix{U\\ &V} \frac1{\sqrt{2}}\pmatrix{I&I\\ I&-I} \pmatrix{I+\Sigma\\ &I-\Sigma} \frac1{\sqrt{2}}\pmatrix{I&I\\ I&-I} \pmatrix{U^T\\ &V^T}\\ &=X\pmatrix{I+\Sigma\\ &I-\Sigma}X^T \end{align} and hence a SVD of $A$ is given by: $$ A=X\pmatrix{I+\Sigma\\ &|I-\Sigma|}\left(\pmatrix{I\\ &D}X^T\right), $$ where
$$ \begin{cases} d_{ii}=1, & \text{if $\sigma_i\le1$} \\ d_{ii}=-1, & otherwise. \end{cases} $$