Using SVD to write an eigendecomposition

Question

Let $A\in\mathbb{R}^{n\times n}$. Use the SVD of A to write down an explicit eigendecomposition of $$H = \begin{bmatrix}0 &A^{T}\\A & 0\end{bmatrix}.$$ Hint: If $\sigma$ is a singular value of $A$ then $±\sigma$ are eigenvalues of $H$.
I do not understand how to proceed. My idea is to set $U=V=I$ so that $$H = \begin{bmatrix}0 &\Sigma\\\Sigma & 0\end{bmatrix}$$ And try to find a matrix $X$ such that $$\begin{bmatrix}0 &\Sigma\\\Sigma & 0\end{bmatrix}=X\Sigma X^{-1}$$ Is there a more straighforward way to solve it?

Answer 1

It is possible to find a matrix $X$ such that $$ X^{-1}HX = \pmatrix{0 & \Sigma\\ \Sigma & 0}. $$ In particular, if $A = U \Sigma V^T$ is the singular value decomposition of $A$, we can take $$ X = \pmatrix{V & 0\\0 & U}. $$ On the other hand, the matrix $$ Y = \frac{1}{\sqrt{2}} \pmatrix{I & I\\I & -I} $$ Is such that $$ Y^{-1}\pmatrix{0 & \Sigma\\\Sigma & 0}Y = \pmatrix{\Sigma&0\\0& -\Sigma}. $$ Put these together to get the eigendecomposition of $H$.

Answer 2

The characteristic polynomial of $H$ is given by

$$p_H(\lambda)=\det(\lambda I-H)=\det(\lambda I)\det(\lambda I-\lambda^{-1}A^TA)=\det(\lambda^2I-A^TA)$$

where the second equality comes from the Schur complement (see also https://en.wikipedia.org/wiki/Block_matrix#Block_matrix_determinant).

So, we can see that $\lambda^2$ must be an eigenvalue of $A^TA$ for $p_H(\lambda)$ to be zero. This means that the eigenvalues of $H$ consist of the singular values of $A$ and their additive inverse.

This means that the matrix $H$ can be expressed in diagonal form modulo some suitable basis change with diagonal matrix

$$D=\begin{bmatrix}\Sigma & 0\\0 & -\Sigma\end{bmatrix}.$$

The basis change $P$ obeys $HP=PD$, so let

$$P=\begin{bmatrix}P_1 & P_2\\ P_3 & P_4\end{bmatrix}.$$

This yields

$$\begin{bmatrix}0 & V\Sigma U^T\\U\Sigma V^T & 0 \end{bmatrix}\begin{bmatrix}P_1 & P_2\\ P_3 & P_4\end{bmatrix}=\begin{bmatrix}P_1 & P_2\\ P_3 & P_4\end{bmatrix}\begin{bmatrix}\Sigma & 0\\0 & -\Sigma\end{bmatrix}.$$

Solving for this system of equations yields

$$P=\begin{bmatrix}V & -V\\ U & U\end{bmatrix}\ \mathrm{and}\ P^{-1}=\dfrac{1}{2}\begin{bmatrix}V^T & U^T\\ -V^T & U^T\end{bmatrix}$$

where we have used the fact that $U^TU=UU^T=I$ and $V^TV=VV^T=I$.

We can then easily verify that $PHP^{-1}=D$.