3
$\begingroup$

Let's say a zero-diagonal $4\times4$ symmetric matrix, $$ \begin{bmatrix} 0 & 1 & 3 & 3 \\ 1 & 0 & 3 & 3 \\ 3 & 3 & 0 & 1 \\ 3 & 3 & 1 & 0 \end{bmatrix} $$

Does anyone know how to obtain SVD from the above matrix mathematically? as $A = U W V^*$ Note: eigenvectors of $A^*A$ will make up $V$ with associate eigenvalues of the diagonal of $W^*W$. Similarly, $D^*D = U^*(WW^*)U$

Thank you very much!

$\endgroup$
  • $\begingroup$ Perhaps this is a somewhat related question. $\endgroup$ – Michael Hardy Mar 27 '12 at 15:16
  • $\begingroup$ Why do you want the singular value decomposition for an invertible, diagonalizable, square matrix? In any case, see Wikipedia. $\endgroup$ – TMM Mar 27 '12 at 19:58
  • $\begingroup$ Your question is unclear. Are you looking for a singular value decomposition for the matrix in your question, or SVDs for a general class of matrices? Are you looking for some numerical methods, or some theoretical methods that allow you to hand-calculate the SVDs? $\endgroup$ – user1551 Dec 20 '17 at 15:17
2
$\begingroup$

The notation I'm used to using with singular value decomposition is $$A=U\Sigma V^T,$$ so pardon the different notation I'll use here. ($\Sigma$ is the matrix of singular values, like what I assume $W$ is in your question; everything else is the same, aside from the transpose, which I denote by $\ ^T$.)

We start any singular value decomposition by calculating $A^T A$, which in this case is equal to $A^2$, because $A$ is symmetrical. $$A^T A=A^2=\begin{bmatrix}0&1&3&3\\1&0&3&3\\3&3&0&1\\3&3&1&0\end{bmatrix}^2=\begin{bmatrix}19&18&6&6\\18&19&6&6\\6&6&19&18\\6&6&18&19\end{bmatrix}$$

We then find the eigenvalues and eigenvectors using the characteristic polynomial of $A^T A$, as follows: $$\det(A-\lambda I_4)=\begin{vmatrix}19-\lambda&18&6&6\\18&19-\lambda&6&6\\6&6&19-\lambda&18\\6&6&18&19-\lambda\end{vmatrix}=$$

(skipping some tedious algebra that, I'll be honest, I used a website for)

$$\begin{align}\lambda^4-76\lambda^3+1374\lambda^2-2524\lambda+1225&=0\\(\lambda-1)(\lambda-1)(\lambda-25)(\lambda-49)&=0\end{align}$$ $$\lambda_1=1,\;\lambda_2=1,\;\lambda_3=25,\,\lambda_4=49$$

Now that we have the eigenvalues of $A^T A$, we know $\Sigma$, since it's defined to be the same shape as $A$ and to have entries only on the diagonal, which are given by $\sigma_i=\sqrt{\lambda_i}$: $$\bbox[5px,border:2px solid red]{\Sigma=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&5&0\\0&0&0&7\end{bmatrix}}$$

We can now begin to calculate $V$, whose columns will be orthonormal eigenvectors of $A^T A$. There are quite a lot of row operations to be performed here, for which I used the same website. You can refer to it to check their validity if you so desire. The first two columns of $V$, $\vec{v_1}$ and $\vec{v_2}$, will compose the null space of the matrix $A^T A-\lambda_1 I_4$. To find them, we solve the following system and normalize the resulting basis vectors: $$A^T A-\lambda_1 I_4=\vec{0}$$ $$\begin{bmatrix}18&18&6&6\\18&18&6&6\\6&6&18&18\\6&6&18&18\end{bmatrix}\vec{v}=\begin{bmatrix}0\\0\\0\\0\end{bmatrix}$$

The general solution of this system tells us that $$\text{span}\left(\text{null}\left(A^T A-\lambda_1 I_4\right)\right)=\left\{\begin{bmatrix}0\\0\\-1\\1\end{bmatrix},\begin{bmatrix}-1\\1\\0\\0\end{bmatrix}\right\}.$$

Therefore, the first two columns of $V$ are $$\vec{v_1}=\frac{1}{\sqrt{2}}\begin{bmatrix}0\\0\\-1\\1\end{bmatrix},\;\vec{v_2}=\frac{1}{\sqrt{2}}\begin{bmatrix}-1\\1\\0\\0\end{bmatrix}.$$

Similarly, the normalized basis vector of the null space of $A^T A-\lambda_3 I_4$ will be $\vec{v_3}$, and the normalized basis vector of the null space of $A^T A-\lambda_4 I_4$ will be $\vec{v_4}$. $$A^T A-\lambda_3 I_4=\vec{0}$$ $$\begin{bmatrix}-6&18&6&6\\18&-6&6&6\\6&6&-6&18\\6&6&18&-6\end{bmatrix}\vec{v}=\begin{bmatrix}0\\0\\0\\0\end{bmatrix}$$ $$\implies \vec{v_3}=\frac{1}{2}\begin{bmatrix}-1\\-1\\1\\1\end{bmatrix}$$ $$A^T A-\lambda_4 I_4=\vec{0}$$ $$\begin{bmatrix}-30&18&6&6\\18&-30&6&6\\6&6&-30&18\\6&6&18&-30\end{bmatrix}\vec{v}=\begin{bmatrix}0\\0\\0\\0\end{bmatrix}$$ $$\implies \vec{v_4}=\frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}$$

Pulling together the the columns of $V$, we find that $$V=\begin{bmatrix}0&-\frac{1}{\sqrt{2}}&-\frac{1}{2}&\frac{1}{2}\\0&\frac{1}{\sqrt{2}}&-\frac{1}{2}&\frac{1}{2}\\-\frac{1}{\sqrt{2}}&0&\frac{1}{2}&\frac{1}{2}\\\frac{1}{\sqrt{2}}&0&\frac{1}{2}&\frac{1}{2}\end{bmatrix}\implies \bbox[5px,border:2px solid red]{V^T=\begin{bmatrix}0&0&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0&0\\-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\end{bmatrix}}$$

Finally, now that we know the columns of $V$, we can calculate the columns of $U$, which are given by $\vec{u_i}=\frac{A\vec{v_i}}{\sigma_i}$. $$\vec{u_1}=\left(\frac{1}{1}\right)\left(\frac{1}{\sqrt{2}}\right)\begin{bmatrix}0&1&3&3\\1&0&3&3\\3&3&0&1\\3&3&1&0\end{bmatrix}\begin{bmatrix}0\\0\\-1\\1\end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}0\\0\\1\\-1\end{bmatrix}$$ $$\vec{u_2}=\left(\frac{1}{1}\right)\left(\frac{1}{\sqrt{2}}\right)\begin{bmatrix}0&1&3&3\\1&0&3&3\\3&3&0&1\\3&3&1&0\end{bmatrix}\begin{bmatrix}-1\\1\\0\\0\end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\\0\end{bmatrix}$$ $$\vec{u_3}=\left(\frac{1}{5}\right)\left(\frac{1}{2}\right)\begin{bmatrix}0&1&3&3\\1&0&3&3\\3&3&0&1\\3&3&1&0\end{bmatrix}\begin{bmatrix}-1\\-1\\1\\1\end{bmatrix}=\frac{1}{10}\begin{bmatrix}5\\5\\-5\\-5\end{bmatrix}=\frac{1}{2}\begin{bmatrix}1\\1\\-1\\-1\end{bmatrix}$$ $$\vec{u_4}=\left(\frac{1}{7}\right)\left(\frac{1}{2}\right)\begin{bmatrix}0&1&3&3\\1&0&3&3\\3&3&0&1\\3&3&1&0\end{bmatrix}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}=\frac{1}{14}\begin{bmatrix}7\\7\\7\\7\end{bmatrix}=\frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}$$ $$\implies \bbox[5px,border:2px solid red]{U=\begin{bmatrix}0&\frac{1}{\sqrt{2}}&\frac{1}{2}&\frac{1}{2}\\0&-\frac{1}{\sqrt{2}}&\frac{1}{2}&\frac{1}{2}\\\frac{1}{\sqrt{2}}&0&-\frac{1}{2}&\frac{1}{2}\\-\frac{1}{\sqrt{2}}&0&-\frac{1}{2}&\frac{1}{2}\end{bmatrix}}$$

After all that work, we have the singular value decomposition of $A$: $$A=U\Sigma V^T=\begin{bmatrix}0&\frac{1}{\sqrt{2}}&\frac{1}{2}&\frac{1}{2}\\0&-\frac{1}{\sqrt{2}}&\frac{1}{2}&\frac{1}{2}\\\frac{1}{\sqrt{2}}&0&-\frac{1}{2}&\frac{1}{2}\\-\frac{1}{\sqrt{2}}&0&-\frac{1}{2}&\frac{1}{2}\end{bmatrix} \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&5&0\\0&0&0&7\end{bmatrix} \begin{bmatrix}0&0&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0&0\\-\frac{1}{2}&-\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&\frac{1}{2}&\frac{1}{2}&\frac{1}{2}\end{bmatrix}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.