---
# System prepended metadata

title: svd_4_team

---

---
title: svd_4_team
---
***great job! 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\\  \end{bmatrix}[a~~a~~c~~c~~e~~e~~       ]$

Example 3(a): Fill in the gaps

WHAT ABOUT 3a?
No solution.

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

$\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}w\\ x\\   \end{bmatrix}[~y~~z~]$

$\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}
wy&wz\\xy&xz\\\end{bmatrix}$

If $wz=0$, then either $w=0$, $z=0$, or they both equal $0$. However, $wy=1$ and $xz=1$, so if $w$ or $z$ equal $0$, both of these could not be true at the same time. 

Example 3(b): Fill in the gaps

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

Draw some conclusions.

In order for there to be a solution, the rows must be linearly dependent. In other words, since the matrices are square the rank would have to be 1 in order for there to be a solution.

**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

$\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}-\begin{bmatrix}
a&b\\ka&kb\\   \end{bmatrix}=\begin{bmatrix}30-a&28-b\\28-ka&30-kb\\\end{bmatrix}$

Frobenius Norm = $\sqrt{(30-a)^2+(28-b)^2+(28-ka)^2+(30-kb)^2}$

$\frac{d}{da}=-2(30-a)-2k(28-ka)=0$

$\frac{d}{db}=-2(28-b)-2k(30-kb)=0$

$\frac{d}{dk}=-2a(28-ka)-2b(30-kb)=0$

$a=1, b=-1, k=-1$
$a=29, b=29, k=1$

$\tilde A=\begin{bmatrix} 29&29\\29&29\\\end{bmatrix}$



2. Then compute $E=A-\tilde A$, and write $A$ as a sum of $\tilde A$ and $E$.

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


$\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}=\begin{bmatrix}29&29\\29&29\\\end{bmatrix}+\begin{bmatrix}1&-1\\-1&1\\\end{bmatrix}$

3. 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? 
Can this decomposition be obtained for any matrix?
E.g. Example 3.

In this case, all of the entries in $\tilde A$ are half of the largest eigenvalue of $A$. 
We can see, $\tilde A$ is related to the largest eigenvalue and unit eigenvector because $\tilde A=\lambda_1\cdot{v_1}\cdot{v^T_1}$, where $v_1$ is the unit eigenvector associated with the largest eigenvalue, $\lambda_1$. 
$\tilde A=58\cdot\begin{bmatrix} 1/\sqrt{2}\\1/\sqrt{2}\\\end{bmatrix}\cdot\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2}\\\end{bmatrix}=\begin{bmatrix} 29&29\\29&29\\\end{bmatrix}$

$E$ is related to the smallest eigenvalue and unit eigenvector because $E=\lambda_2\cdot{v_2}\cdot{v^T_2}$, where $v_2$ is the unit eigenvector associated with the smallest eigenvalue, $\lambda_2$.
This is the spectral decomposition. 
This decomposition can be obtained only for  symmetric matrices.

**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}$

$\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}-\begin{bmatrix}
a&b\\ka&kb\\   \end{bmatrix}=\begin{bmatrix}1-a&-b\\1-ka&1-kb\\\end{bmatrix}$

Frobenius Norm = $\sqrt{(1-a)^2+b^2+(1-ka)^2+(1-kb)^2}$

$\frac{d}{da}=-2(1-a)-2k(1-ka)=0$

$\frac{d}{db}=2(b)-2k(1-kb)=0$

$\frac{d}{dk}=-2a(1-ka)-2b(1-kb)=0$

$a=\frac{5-\sqrt{5}}{10}, b=\frac{-1}{\sqrt5}, k=\frac{1-\sqrt{5}}{2}$

$a=\frac{5+\sqrt{5}}{10}, b=\frac{1}{\sqrt5}, k=\frac{1+\sqrt{5}}{2}$

$\tilde A=\begin{bmatrix}a&b\\ka&kb\\\end{bmatrix}$ using the 2nd set of a, b, and k values above. 
$\tilde A=\begin{bmatrix}0.72361&0.44721\\1.1708&0.72361\\\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\cdot{A^T}=\begin{bmatrix} 1&1\\1&2\\\end{bmatrix},
\lambda_1= \frac{3+\sqrt{5}}{2},\lambda_2= \frac{3-\sqrt{5}}{2}$ 

eigenvector for $\lambda_1=\begin{bmatrix} -1+\sqrt{5}\\2\\\end{bmatrix}$
unit eigenvector $= \begin{bmatrix} \frac{-1+\sqrt{5}}{\sqrt{10-2\sqrt{5}}}\\\frac{2}{\sqrt{10-2\sqrt{5}}}\\\end{bmatrix}=\begin{bmatrix}0.52573\\0.85065\\\end{bmatrix}$

eigenvector for $\lambda_2=\begin{bmatrix} -1-\sqrt{5}\\2\\\end{bmatrix}$
unit eigenvector  $= \begin{bmatrix} \frac{-1-\sqrt{5}}{\sqrt{10+2\sqrt{5}}}\\\frac{2}{\sqrt{10+2\sqrt{5}}}\\\end{bmatrix}=\begin{bmatrix}-0.85065\\0.52573\\\end{bmatrix}$


$A^T\cdot{A}=\begin{bmatrix} 2&1\\1&1\\\end{bmatrix},  \lambda_1=\frac{3+\sqrt{5}}{2}, \lambda_2=\frac{3-\sqrt{5}}{2}$

eigenvector for $\lambda_1=\begin{bmatrix} 1+\sqrt{5}\\2\\\end{bmatrix}$
unit eigenvector $= \begin{bmatrix} \frac{1+\sqrt{5}}{\sqrt{10+2\sqrt{5}}}\\\frac{2}{\sqrt{10+2\sqrt{5}}}\\\end{bmatrix}=\begin{bmatrix}0.85065\\0.52573\\\end{bmatrix}$

eigenvector for $\lambda_2=\begin{bmatrix} 1-\sqrt{5}\\2\\\end{bmatrix}$
unit eigenvector $= \begin{bmatrix} \frac{1-\sqrt{5}}{\sqrt{10-2\sqrt{5}}}\\\frac{2}{\sqrt{10-2\sqrt{5}}}\\\end{bmatrix}=\begin{bmatrix}-0.52573\\0.85065\\\end{bmatrix}$

$A\cdot{A^T}$ and $A^T\cdot{A}$ have the same eigenvalues.

3. Let $\lambda_1$ be the larget 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$$
 
$\sigma_1=\sqrt{\frac{3+\sqrt{5}}{2}}=1.68103$

$u_1=\begin{bmatrix} 0.52573\\0.85065\\\end{bmatrix}$

$v_1^T=\begin{bmatrix} 0.85065&0.52573\\\end{bmatrix}$

$A_1=1.68103\cdot\begin{bmatrix}0.44721&0.27639\\0.72361&0.44721\end{bmatrix}=\begin{bmatrix}0.72361&0.44721\\1.1708&0.72361\\\end{bmatrix}$
 
 4. Compare $\tilde A$ and $A_1$
 
 $\tilde A$ and $A_1$ are equal. 
 
 5. Prove that for any non-zero vectors ${\bf u}$ and ${\bf v}$, the matrix ${\bf u}{\bf v}^T$ has rank 1. 
 
Suppose vector $u$ has $m$ entries $u_1, u_2,...,u_m$, and vector $v$ has $n$ entries $v_1, v_2,...,v_n$. 
Then, $u\cdot{v^T}$ will be an $m$x$n$ matrix with columns $v_1u~~v_2u...v_nu$ 
All columns are linear combinations of the vector $u$. Therefore, they are all linearly dependent with span $u$, so $u\cdot{v^T}$ is rank one. 

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.

If $M$ is a non-square matrix, then $MM^T$ and $M^TM$ are square symmetric matrices. After finding both of these, you would find the non-zero eigenvalues, which would be the same for both. We will call these $\lambda_1\lambda_2...\lambda_n or \lambda_m$ where $\lambda_1>\lambda_2>...\lambda_n or \lambda_m$. Then, $u_1...u_m$ are the unit eigenvectors of $MM^T$ and $v_1...v_n$ are the unit eigenvectors of $M^TM$. Let $\sigma_1$ be the square root of the largest eigenvalue, $\lambda_1$. Then, 
$M_1=\sigma_1u_1v_1^T$ is the matrix closest to $M$ with rank 1. 