Homework 11

1. Find the singular value decomposition of the following two matrices.

(a) $$\begin{bmatrix}1 & -2 \\-3 & 6\end{bmatrix}$$

Let $A=\begin{bmatrix}1 & -2 \\-3 & 6\end{bmatrix}$.

$$A^\top A=\begin{bmatrix} 1 & -3 \\ -2 & 6 \end{bmatrix}\begin{bmatrix} 1 & -2 \\ -3 & 6 \end{bmatrix} =\begin{bmatrix} 10 & -20 \\ -20 & 40 \end{bmatrix} \\ \begin{align*} \det(A^\top A-\lambda I) &= \begin{bmatrix} 10-\lambda & -20 \\ -20 & 40-\lambda \end{bmatrix} &= 0 \\ &= (10-\lambda)(40-\lambda) - (-20)(-20) &= 0 \\ &= \lambda^2 - 50\lambda &= 0 \\ &= \lambda(\lambda - 50) &= 0 \end{align*} \\ \therefore \lambda = 0, 50$$

$\lambda_1 = 0$ and $\lambda_2=50$ are the eigenvalues of $A^\top A$.

$$\begin{array}{c} \lambda_1 = 0 &\implies &\sigma_1 = 0 \\ \lambda_2 = 50 &\implies &\sigma_2 = \sqrt{50} = 5\sqrt{2} \end{array} \\[1em] \boxed{\therefore\Sigma = \begin{bmatrix} 0 & 0 \\ 0 & 5\sqrt{2} \end{bmatrix} }$$

And so:

$$\operatorname{rref}(A^\top A - \lambda_1 I) = \operatorname{rref} \begin{bmatrix} 10-0 & -20 \\ -20 & 40-0 \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 0 & 0 \end{bmatrix} \\ \therefore \ker(A^\top A - \lambda_1 I) = \ker\begin{bmatrix} 1 & -2 \\ 0 & 0 \end{bmatrix} = \operatorname{span}\Set{ \begin{bmatrix} 2 \\ 1 \end{bmatrix} }$$

As such, $\vector{v}_1 = \displaystyle\frac{1}{\sqrt{5}}\begin{bmatrix} 2 \\ 1 \end{bmatrix}$ is an eigenvector corresponding to $\lambda_1=0$.

$$\operatorname{rref}(A^\top A - \lambda_2 I) = \operatorname{rref} \begin{bmatrix} 10-50 & -20 \\ -20 & 40-50 \end{bmatrix} = \begin{bmatrix} 1 & 1/2 \\ 0 & 0 \end{bmatrix} \\ \therefore \ker(A^\top A - \lambda_2 I) = \ker\begin{bmatrix} 1 & 1/2 \\ 0 & 0 \end{bmatrix} = \operatorname{span}\Set{ \begin{bmatrix} -1/2 \\ 1 \end{bmatrix} }$$

As such, $\vector{v}_2 = \displaystyle\frac{2}{\sqrt{5}}\begin{bmatrix} -1/2 \\ 1 \end{bmatrix}$ is an eigenvector corresponding to $\lambda_2=50$.

$$\boxed{ \therefore V = \begin{bmatrix} 2/\sqrt{5} & -1/\sqrt{5} \\ 1/\sqrt{5} & 2/\sqrt{5} \end{bmatrix} = \frac{1}{\sqrt{5}} \begin{bmatrix} 2 & -1 \\ 1 & 2 \end{bmatrix} }$$

Then, $\vector{u}_i = \displaystyle\frac{1}{\sigma_i}A\vector{v}_i$ for $i=1,2$:

Note $\sigma_1 = 0$, so we move on to $\vector{u}_2$.

$$\begin{align*} \vector{u}_2 &= \frac{1}{5\sqrt{2}}\begin{bmatrix} 1 & -2 \\ -3 & 6 \end{bmatrix} \frac{2}{\sqrt{5}}\begin{bmatrix} -1/2 \\ 1 \end{bmatrix} \\ &= \frac{1}{\sqrt{10}}\begin{bmatrix} -1 \\ 3 \end{bmatrix} \end{align*}$$

Since $\sigma_1=0$ and we need one more vector, we need to choose a vector $\vector{u}_1$ such that it is orthogonal to $\vector{u}_2$. Since it’s just $\R^2$, we can just eyeball and make $\displaystyle\vector{u}_1 = \frac{1}{\sqrt{10}}\begin{bmatrix} 3 \\ 1 \end{bmatrix}$.

Sanity check: $\displaystyle\langle\vector{u}_1,\vector{u}_2\rangle = \frac{1}{\sqrt{10}}((-1)(3) + 3(1)) = 0$.

$$\boxed{ \therefore U = \begin{bmatrix} 3/\sqrt{10} & -1/\sqrt{10} \\ 1/\sqrt{10} & 3/\sqrt{10} \end{bmatrix} = \frac{1}{\sqrt{10}} \begin{bmatrix} 3 & -1 \\ 1 & 3 \end{bmatrix} }$$

And so, we have that the SVD for $A=\begin{bmatrix}1 & -2 \\-3 & 6\end{bmatrix}$ is:

$$\begin{align*} A &= U\Sigma V^\top \\ &= \begin{bmatrix} 3/\sqrt{10} & -1/\sqrt{10} \\ 1/\sqrt{10} & 3/\sqrt{10} \end{bmatrix}\begin{bmatrix} 0 & 0 \\ 0 & 5\sqrt{2} \end{bmatrix}\begin{bmatrix} 2/\sqrt{5} & -1/\sqrt{5} \\ 1/\sqrt{5} & 2/\sqrt{5} \end{bmatrix}^\top \\ &= \frac{1}{\sqrt{10}}\begin{bmatrix} 3 & -1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} 0 & 0 \\ 0 & 5\sqrt{2} \end{bmatrix}\frac{1}{\sqrt{5}}\begin{bmatrix} 2 & 1 \\ -1 & 2 \end{bmatrix} \\ &= \begin{bmatrix} 1 & -2 \\ -3 & 6 \end{bmatrix} \end{align*}$$

(b) $$\begin{bmatrix}2 & 1 & 0 & -1 \\0 & -1 & 1 & -1\end{bmatrix}$$

Let $A=\begin{bmatrix}2 & 1 & 0 & -1 \\0 & -1 & 1 & -1\end{bmatrix}$.

$$A^\top A = \begin{bmatrix} 4 & 2 & 0 & -2 \\ 2 & 2 & -1 & 0 \\ 0 & -1 & 1 & -1 \\ -2 & 0 & -1 & 2 \end{bmatrix} \\ \begin{align*} \det(A^\top A-\lambda I) &= \begin{bmatrix} 4-\lambda & 2 & 0 & -2 \\ 2 & 2-\lambda & -1 & 0 \\ 0 & -1 & 1-\lambda & -1 \\ -2 & 0 & -1 & 2-\lambda \end{bmatrix} &= 0 \\ &= \lambda^4 - 9\lambda^3 + 18\lambda^2 &= 0 \\ &= \lambda^2(\lambda - 3)(\lambda - 6) &= 0 \end{align*} \\ \therefore \lambda = 0,3,6$$

$\lambda_1=0$, $\lambda_2=3$, and $\lambda_3=6$ are eigenvalues of $A^\top A$.

$$\begin{array}{c} \lambda_1 = 0 &\implies &\sigma_1 = 0 \\ \lambda_2 = 3 &\implies &\sigma_2 = \sqrt{3} \\ \lambda_3 = 6 &\implies &\sigma_3 = \sqrt{6} \end{array} \\[1em] \boxed{ \therefore\Sigma = \begin{bmatrix} \sqrt{3} & 0 & 0 & 0 \\ 0 & \sqrt{6} & 0 & 0 \end{bmatrix} }$$

And so:

$$\operatorname{rref}(A^\top A - \lambda_1 I) = \operatorname{rref} \begin{bmatrix} 4-0 & 2 & 0 & -2 \\ 2 & 2-0 & -1 & 0 \\ 0 & -1 & 1-0 & -1 \\ -2 & 0 & -1 & 2-0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1/2 & -1 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \therefore \ker(A^\top A - \lambda_1 I) = \ker\begin{bmatrix} 1 & 0 & 1/2 & -1 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \operatorname{span}\Set{ \begin{bmatrix} -1/2 \\ 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 0 \\ 1 \end{bmatrix} }$$

As such, $\displaystyle\frac{2}{3}\begin{bmatrix} -1/2 \\ 1 \\ 1 \\ 0 \end{bmatrix},\frac{1}{\sqrt{3}} \begin{bmatrix} 1 \\ -1 \\ 0 \\ 1 \end{bmatrix}$ are eigenvectors corresponding to $\lambda_1=0$.

$$\operatorname{rref}(A^\top A - \lambda_2 I) = \operatorname{rref} \begin{bmatrix} 4-3 & 2 & 0 & -2 \\ 2 & 2-3 & -1 & 0 \\ 0 & -1 & 1-3 & -1 \\ -2 & 0 & -1 & 2-3 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \therefore \ker(A^\top A - \lambda_2 I) = \ker\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \operatorname{span}\Set{ \begin{bmatrix} 0 \\ 1 \\ -1 \\ 1 \end{bmatrix} }$$

As such, $\vector{v}_2 = \displaystyle\frac{1}{\sqrt{3}}\begin{bmatrix} 0 \\ 1 \\ -1 \\ 1 \end{bmatrix}$ is an eigenvector corresponding to $\lambda_2=3$.

$$\operatorname{rref}(A^\top A - \lambda_3 I) = \operatorname{rref} \begin{bmatrix} 4-6& 2 & 0 & -2 \\ 2 & 2-6& -1 & 0 \\ 0 & -1 & 1-6& -1 \\ -2 & 0 & -1 & 2-6 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \\ \therefore \ker(A^\top A - \lambda_3 I) = \ker\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \operatorname{span}\Set{ \begin{bmatrix} -2 \\ -1 \\ 0 \\ 1 \end{bmatrix} }$$

As such, $\vector{v}_3 = \displaystyle\frac{1}{\sqrt{6}} \begin{bmatrix} -2 \\ -1 \\ 0 \\ 1 \end{bmatrix}$ is an eigenvector corresponding to $\lambda_3=6$.

$$\boxed{ \therefore V = \begin{bmatrix} -1/3 & 1/\sqrt{3} & 0 &-\sqrt{2/3} \\ 2/3 & -1/\sqrt{3} & 1/\sqrt{3} & -1/\sqrt{6} \\ 2/3 & 0 & -1/\sqrt{3} & 0 \\ 0 & 1/\sqrt{3} & 1/\sqrt{3} & 1/\sqrt{6} \end{bmatrix} }\\ \;$$

Then, $\vector{u}_i = \displaystyle\frac{1}{\sigma_i}A\vector{v}_i$ for $i=2,3$:

$$\begin{align*} \vector{u}_2 &= \frac{1}{\sqrt{3}}\begin{bmatrix} 2 & 1 & 0 & -1 \\ 0 & -1 & 1 & -1 \end{bmatrix} \frac{1}{\sqrt{3}}\begin{bmatrix} 0 \\ 1 \\ -1 \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} 0 \\ -1 \end{bmatrix} \\ \vector{u}_3 &= \frac{1}{\sqrt{6}}\begin{bmatrix} 2 & 1 & 0 & -1 \\ 0 & -1 & 1 & -1 \end{bmatrix}\frac{1}{\sqrt{6}} \begin{bmatrix} -2 \\ -1 \\ 0 \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} -1 \\ 0 \end{bmatrix} \end{align*} \\[1em] \boxed{ \therefore U = \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} }$$

And so, we have that the SVD for $A=\begin{bmatrix}1 & -2 \\-3 & 6\end{bmatrix}$ is:

$$\begin{align*} A &= U\Sigma V^\top \\ &= \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \begin{bmatrix} \sqrt{3} & 0 & 0 & 0 \\ 0 & \sqrt{6} & 0 & 0 \end{bmatrix} \begin{bmatrix} -1/3 & 1/\sqrt{3} & 0 &-\sqrt{2/3} \\ 2/3 & -1/\sqrt{3} & 1/\sqrt{3} & -1/\sqrt{6} \\ 2/3 & 0 & -1/\sqrt{3} & 0 \\ 0 & 1/\sqrt{3} & 1/\sqrt{3} & 1/\sqrt{6} \end{bmatrix}^\top \\ &= \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \begin{bmatrix} \sqrt{3} & 0 & 0 & 0 \\ 0 & \sqrt{6} & 0 & 0 \end{bmatrix} \begin{bmatrix} -1/3 & 2/3 & 2/3 & 0 \\ 1/\sqrt{3} & -1/\sqrt{3} & 0 & 1/\sqrt{3} \\ 0 & 1/\sqrt{3} & -1/\sqrt{3} & 1/\sqrt{3} \\ -\sqrt{2/3} & -1/\sqrt{6} & 0 & 1/\sqrt{6} \end{bmatrix} \\ &= \begin{bmatrix} 2 & 1 & 0 & -1 \\ 0 & -1 & 1 & -1 \end{bmatrix} \end{align*}$$

2. A famous application of spectral theorem and SVD is the spectral graph theory. A graph $(V, E)$ is a set of vertices $V$ with edge set $E$. We say that for $x, y \in V , x \sim y$ if $x$ and $y$ are connected by an edge in $E$. The Graph Laplacian is defined to be a matrix $A$ of size $|V|\times|V|$

$$A_{x,y} = \begin{cases} 1 & \text{if $x \sim y$} \\ -\text{(number of edges starting from $x$)} & \text{if $x = y$} \\ 0 & \text{otherwise} \end{cases}$$

For example, a triangle with three vertices

$$A = \begin{bmatrix} -2 & 1 & 1 \\ 1 & -2 & 1 \\ 1 & 1 & -2 \end{bmatrix}$$

(a) Find the SVD for the Laplacian of the triangle graph.

Using an online calculator, we find $A = U\Sigma V^\top$ for

$$U = \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{6} & 1/\sqrt{3} \\ 0 & -\sqrt{2/3} & 1/\sqrt{3} \\ -1/\sqrt{2} & 1/\sqrt{6} & 1/\sqrt{3} \end{bmatrix},\quad \Sigma = \begin{bmatrix} 3 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix},\quad V = \begin{bmatrix} -1/\sqrt{2} & -1/\sqrt{6} & 1/\sqrt{3} \\ 0 & \sqrt{2/3} & 1/\sqrt{3} \\ 1/\sqrt{2} & -1/\sqrt{6} & 1/\sqrt{3} \end{bmatrix}.$$

(b) Write down the graph Laplacian matrix for the square graph and then find its SVD.

Using the definition above, the Laplacian matrix $A$ for a square graph is:

$$A = \begin{bmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}$$

Again, sparing the computation. The SVD for the square graph $A = U\Sigma V^\top$ is given by:

$$U = V = \begin{bmatrix} -1/2 & 0 & -1/\sqrt{2} & 1/2 \\ 1/2 & -1/\sqrt{2} & 0 & 1/2 \\ -1/2 & 0 & 1/\sqrt{2} & 1/2 \\ 1/2 & 1/\sqrt{2} & 0 & 1/2 \end{bmatrix},\quad \Sigma = \begin{bmatrix} 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$