Given $A \in \mathbb{R}^{n \times m}$, consider the symmetric matrix
$M = \begin{pmatrix} 0 & A \\ A^{t} & 0 \end{pmatrix} \in \mathbb{R}^{(n+m) \times (n+m)}$.
Show that a simple relationship exists between the singular vectors of $A$ and the eingenvectors of $M$. Show how to build an orthbogonal basis of $\mathbb{R}^{n+m}$ consisting of eigenvectors of $M$, given the singular vectors of $A$.
My attempt: Consider the singular decomposition $A=U\Sigma V^{t}$, where $U_{n\times n} $, $V_{m \times m}$ are orthogonal and $\Sigma$ is rectangular diagonal matrix of singular values.
$\displaystyle \det M = \det((-\lambda I)(-\lambda I) – AA^{t}) = \det(\lambda^2I – AA^{t}) = \det(\lambda^2I – U\Sigma V^{t}V\Sigma^{t}U^{t})=\det(\lambda^2I – U\Sigma^{2}U^{t}) = \det \begin{pmatrix}(\lambda^2 – \sigma_1^2 & 0 & \dots & \dots &0 \\0 & \lambda^2 – \sigma_2^2 & 0 & \dots & 0 \\ \vdots & \ddots & \ddots & \ddots& \vdots \\ 0 & \dots & \dots & 0 & \lambda^2 – \sigma_n^2 \end{pmatrix}=\prod_{k=1}^{n} (\lambda^2 – \sigma_k^2)=0 \implies \lambda = \pm \sigma_k$
for some $k \in\{1,…,n\}$
Let $v_k$ be the eigenvector associated to $\lambda$.
$Mv_k = \lambda v_k = \pm \sigma_k v_k $, and $\sigma_kv_k$ is equal to either $Av_k, A^{t}v_k$ or $0$ (By a theorem in the book), depending on which index $k$.
I'm insecure, specially at the last part, it doesn't feel right. Also, I'd like to some orientation on how to build this basis of orthogonal eigenvectors. I know Gram-schmidt, but not when singular vectors are involved…
Please verify what I did and show me how to improve, or maybe start all over…
Thanks.
Best Answer
I would start the same way you did: let $A = U \Sigma V^t$ be the SVD of $A$. Then, the SVD of $A^t$ is given by $A^t = V \Sigma^t U^t$. Inserting into $M$:
$$M = \begin{bmatrix} 0_{n \times n} & U \Sigma V^t \\ V \Sigma^t U^t & 0_{m \times m} \end{bmatrix}.$$
Now, let us try the eigenvectors $q_k = [u_k^t, \pm v_k^t]^t$. Inserting into $M$ yields
$$M \cdot q_k = \begin{bmatrix} U \Sigma V^t v_k \\ V \Sigma^t U^t u_k \end{bmatrix} =\begin{bmatrix} \sigma_k u_k \\ \pm \sigma_k v_k \end{bmatrix} = \sigma_k q_k.$$
This shows that $q_k$ are eigenvectors. Note that for $n\neq m$ you will also get some zero eigenvalues. This is due to the fact that then either $A$ or $A^t$ will have a non-empty kernel and thus we can find nonzero vectors that give $M \cdot q = 0$.