---
title: svd_3_team
---
***perfect! score 30/30***
**Section 1**

Example 1: Fill in the gaps

$\begin{bmatrix} 1&1&1&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\1&1&1&1&1&1\\\end{bmatrix}=\begin{bmatrix}1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \end{bmatrix}[~1~~1~~1~~1~~1 ~~1~ ]$

Example 2: Fill in the gaps

$\begin{bmatrix} a&a&c&c&e&e\\a&a&c&c&e&e\\a&a&c&c&e&e\\a&a&c&c&e&e\\a&a&c&c&e&e\\a&a&c&c&e&e\\\end{bmatrix}=\begin{bmatrix}1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\end{bmatrix}[~a~~a~~c ~~c~~e ~~e ~ ]$

Example 3(a): Fill in the gaps

$\begin{bmatrix}
1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}\\ \\ \end{bmatrix}[~~~~~]$ IMPOSSIBLE!

$\begin{bmatrix}
1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}a\\ b\\ \end{bmatrix}[~c~~d~~]$

Then, $ac=1, ad=0, bc=1$, and $bd=1$, which implies that either $a=0$ or $d=0$, which isn't possible, because then $ad$ and $ac$ would both be $0$ and we need $ac=1$.

Example 3(b): Fill in the gaps

$\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}1\\ 0\\ \end{bmatrix}[~1~~0~~]+\begin{bmatrix}0\\ 1\\ \end{bmatrix}[~1~~1~~]$

Draw some conclusions.

For there to be a solution, the rows must be linearly dependent. In the first two examples the $1$ x $n$ matrix is the Span of all the rows.

**Section 2**

1. Find rank one 2 by 2 matrix $\tilde A$ closest to $A$. Use Frobenius norm. To solve the arising system of equations use
https://www.wolframalpha.com/input/?i=solve+system+of+equations

The Frobenius norm of a matrix A, is defined as the square root of the sum of the squares of all its entries.

$$A=\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}$$

$\tilde A=\begin{bmatrix} a&b\\ca&cb\\\end{bmatrix}$ for some scaler $c$.

$$A-\tilde A=\begin{bmatrix} 30-a&28-b\\28-ca&30-cb\\\end{bmatrix}$$

Compute the Frobenius norm.

$$d=\sqrt{(30-a)^2+(28-b)^2+(28-ca)^2+(30-cb)^2}$$

Minimize $(30-a)^2+(28-b)^2+(28-ca)^2+(30-cb)^2$ by taking the derrivative and set it equal to $0$.

$$\frac{d}{da}=-2(30-a)-56c+2c^2a=0$$

$$\frac{d}{db}=-2(28-b)-60b+2c^2b=0$$

$$\frac{d}{dc}=-56a+2a^2c-60b+2b^2c=0$$

Solve the system of equations:

$$a=1, 29$$

$$b=-1, 29$$

$$c=-1, 1$$

Choose $a=29, b=29, c=1$ because those are the values closest to our values in $A$.

3. Then compute $E=A-\tilde A$, and write $A$ as a sum of $\tilde A$ and $E$.
$$A=\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}$$

$$E=A-\tilde A=\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}-\begin{bmatrix} 29&29\\29&29\\\end{bmatrix}=\begin{bmatrix} 1&-1\\-1&1\\\end{bmatrix}$$

2. How are $\tilde A$ and $E$ are related to the eigenvalues and eigenvectors of $A$? Try to compute $\tilde A$ using eigenvalues and eigenvectors. This is a famous kind of decomposition, called how?

This is called the spectral decomposition and is...

$$PDP^T=\lambda_1v_1v_1^T+\lambda_2v_2v_2^T+...+\lambda_nv_nv_n^T$$

Can this decomposition be obtained for any matrix?
E.g. Example 3.

**Section 3**

Use Wolphram Alpha for all computations

1. Find rank one 2 by 2 matrix $\tilde A$ closest to $A$. Use Frobenius norm.
$$A=\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}$$

$$\tilde A=\begin{bmatrix} a&b\\ca&cb\\\end{bmatrix}$$

$$A-\tilde A=\begin{bmatrix} 1-a&0-b\\1-ca&1-cb\\\end{bmatrix}$$

Compute the Frobenius norm.

$$d=\sqrt{(1-a)^2+(-b)^2+(1-ca)^2+(1-cb)^2}$$

Minimize $(1-a)^2+(-b)^2+(1-ca)^2+(1-cb)^2$ by taking the derrivative with respect to each variable and set it equal to $0$.

$$\frac{d}{da}=-2(1-a)-2c+2c^2a=0$$

$$\frac{d}{db}=2b-2c+2c^2b=0$$

$$\frac{d}{dc}=-2a+2a^2c-2b+2b^2c=0$$

Solve the system of equations:

$$a=\frac{1}{10}(5-\sqrt{5}),\frac{1}{10}(5+\sqrt{5}) $$

$$b=\frac{-1}{\sqrt{5}},\frac{1}{\sqrt{5}}$$

$$c=\frac{1}{2}(1-\sqrt{5}),\frac{1}{2}(1+\sqrt{5}) $$

Choose $a=\frac{1}{10}(5+\sqrt{5}), b=\frac{1}{\sqrt{5}}, c=\frac{1}{2}(1+\sqrt{5})$ because those are the values closest to our values in $A$.

$$\tilde A=\begin{bmatrix} \frac{1}{10}(5+\sqrt{5})&\frac{1}{\sqrt{5}}\\\frac{1}{10}(5+3\sqrt{5})&\frac{1+\sqrt{5}}{2\sqrt{5}}\\\end{bmatrix}$$

2. Compute the eigenvalues and the unit eigenvectors of $AA^T$ and $A^TA$. What do you notice about the eigenvalues of $A^TA$ and $AA^T$?

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

$$\lambda_1=\frac{3+\sqrt{5}}{2}, \lambda_2=\frac{3-\sqrt{5}}{2}$$

$$v_1=\begin{bmatrix} 1+\sqrt{5}\\2\\\end{bmatrix}, v_2=\begin{bmatrix} 1-\sqrt{5}\\2\\\end{bmatrix}$$

$$AA^T=\begin{bmatrix} 1&1\\1&2\\\end{bmatrix}$$

$$\lambda_1=\frac{3+\sqrt{5}}{2}, \lambda_2=\frac{3-\sqrt{5}}{2}$$

$$v_1=\begin{bmatrix} -1+\sqrt{5}\\2\\\end{bmatrix}, v_2=\begin{bmatrix} -1-\sqrt{5}\\2\\\end{bmatrix}$$

3. Let $\lambda_1$ be the largest eigenvalue, and let ${\bf u_1}$ be the unit eigenvector of $AA^T$ corresponding to $\lambda_1$, let ${\bf v_1}$ be the unit eigenvector of $A^TA$ corresponding to $\lambda_1$. Let $\sigma_1$ be the square root of $\lambda_1$. Compute
$$A_1=\sigma_1{\bf u_1}{\bf v_1}^T$$

$$\lambda_1=\frac{3+\sqrt{5}}{2}, {\bf u_1}=\frac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix} -1+\sqrt{5}\\2\\\end{bmatrix}, {\bf v_1}^T=\frac{1}{\sqrt{10+2\sqrt{5}}}\begin{bmatrix} 1+\sqrt{5}&2\\\end{bmatrix}$$

$$A_1=\sigma_1{\bf u_1}{\bf v_1}^T= \sqrt{2.61803}\begin{bmatrix} 0.52573\\0.85065\\\end{bmatrix}\begin{bmatrix} 0.85065&0.52573\\\end{bmatrix}$$
$$A_1=\sqrt{2.61803}\begin{bmatrix} 0.44721&0.27639\\0.72361&0.44721\\\end{bmatrix}$$

$$A_1=\begin{bmatrix} 0.72360&0.44721\\1.17082&0.72360\\\end{bmatrix}$$

4. Compare $\tilde A$ and $A_1$

$$\tilde A=\begin{bmatrix} \frac{1}{10}(5+\sqrt{5})&\frac{1}{\sqrt{5}}\\\frac{1}{10}(5+3\sqrt{5})&\frac{1+\sqrt{5}}{2\sqrt{5}}\\\end{bmatrix}\approx\begin{bmatrix} 0.72361&0.44721\\1.17082&0.72361\\\end{bmatrix}\approx A_1$$

We can conclude that $\tilde A=A_1$ and the slight difference in their value is a result of rounding error, when we computed $A_1$.

5. Prove that for any non-zero vectors ${\bf u}$ and ${\bf v}$, the matrix ${\bf u}{\bf v}^T$ has rank 1.

Let ${\bf u}=\begin{bmatrix}a_1\\a_2\\\vdots\\a_m\\\end{bmatrix}\neq{\bf 0}$, ${\bf v}^T=\begin{bmatrix}b_1&b_2&...&b_n\\\end{bmatrix}\neq{\bf 0}$.

For any ${\bf x}$, $A{\bf x} = {\bf u}{\bf v}^T{\bf x} = {\bf u}({\bf v}^T{\bf x}) = k{\bf u}$ for some $k$. Therefore, Col($A$) $=$ Span{${\bf u}$}, which is a 1-dimensional space. So, the matrix ${\bf u}{\bf v}^T$ has rank 1.

6. Suppose you have an $m\times n$ matrix $M$. Suggest a linear algebra procedure for obtaining the matrix $M_1$, which is the closest rank 1 matrix to $M$ in Frobenius norm.

Step 1: Compute $MM^T$ and $M^TM$.

Step 2: Find the eigenvalues and corresponding eigenvectors for $MM^T$ and $M^TM$. Note, $MM^T$ and $M^TM$ will have the same eigenvalues, but not the same eigenvectors.

Step 3: Let $\lambda_1$ be the largest eigenvalue, and let ${\bf u_1}$ be the unit eigenvector of $MM^T$ corresponding to $\lambda_1$, let ${\bf v_1}$ be the unit eigenvector of $M^TM$ corresponding to $\lambda_1$. Let $\sigma_1$ be the square root of $\lambda_1$. Compute $M_1=\sigma_1{\bf u_1}{\bf v_1}^T$.