Let $A$ be a square $n \times n$ matrix with SVD $A = U \Sigma V^T$. In Numerical Linear Algebra (Trefethen and Bau) it is shown that the symmetric $2n \times 2n$ matrix
$$H = \begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix}$$
satisfies the eigendecomposition
$$
\begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix} \begin{pmatrix} V & V \\ U & -U \end{pmatrix} = \begin{pmatrix} V & V \\ U & -U \end{pmatrix} \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}. \tag{1}
$$
In particular, the singular values of $A$ are the absolute values of the eigenvalues of $H$.
After establishing this the authors seem to imply that by computing an eigendecomposition of $H$, we can compute an SVD of $A$. I fail to see how this is the case. Suppose that we have computed (say by QR iteration) an eigendecomposition $H = Q D Q^T$ where $D$ is a diagonal matrix and $Q$ is an orthogonal $2n \times 2n$ matrix. Since $D$ contains the eigenvalues of $H$, by permuting the columns of $Q$ if necessary we can assume that
$$D = \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}.$$
If we write
$$Q = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix}$$
where the $Q_{ij}$'s are $n \times n$ blocks, then our computed eigendecomposition tells us that
$$
\begin{pmatrix} 0 & A^T \\ A & 0\end{pmatrix} \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix} = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix} \begin{pmatrix} \Sigma & 0 \\ 0 & -\Sigma \end{pmatrix}. \tag{2}
$$
Comparing $(1)$ and $(2)$, it's tempting to conclude that
$$Q_{11}=V=Q_{12}, Q_{21}=U=-Q_{22},$$
but obviously this need not be the case, since eigendecompositions are not unique. Of course, SVDs are not unique either, so perhaps it nevertheless holds that $A=Q_{21} \Sigma Q_{11}^T$. I have tried to prove (or disprove) whether this is the case, but I haven't had any luck. In fact, it's not even clear to me whether the $Q_{ij}$'s are orthogonal matrices.
Does anybody know how this $Q$ matrix can be used to get an SVD for $A$?
Best Answer
Hy, like you said if we compute the eigenvectors of $H$ nothing ensures that we will get the same $U$, $V$. However if we restrict our eigenvector matrix to be of the form $\begin{pmatrix} X&X\\Y&-Y\end{pmatrix}$ then it should work, if a vector $\begin{pmatrix}x_1\\y_1\end{pmatrix}$ is an eigenvector for $\lambda$, $\begin{pmatrix}x_1\\ -y_1\end{pmatrix}$ is an eigenvector corresponding to $-\lambda$. The matrix is also orthogonal so $X$ and $Y$ are orthogonal.