# The reduction of SVD to an eigenvalue problem

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$$?

## 1 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.

• Okay, so I was able to prove that if $Q$ has the form $Q = \begin{pmatrix} X&X\\Y&-Y\end{pmatrix}$, then we necessarily have that $X$ and $Y$ are orthogonal (after scaling by a factor of $\sqrt{2}$), and it follows easily that $A=Y \Sigma X^T$. But what allows for us to ensure that $Q$ has this form in the first place? Commented Jul 27, 2019 at 23:03
• Nevermind. I guess the point of your second sentence is that given $Q = \begin{pmatrix} Q_{11} & Q_{12} \\ Q_{21} & Q_{22} \end{pmatrix}$, we can let $Q'=\begin{pmatrix} Q_{11} & Q_{11} \\ Q_{21} & -Q_{21} \end{pmatrix}$, and then it's not hard to show that $HQ'=Q'D$ and $Q'$ is orthogonal. I'll think this over and accept your answer once I'm confident that this does indeed work. Commented Jul 27, 2019 at 23:27