---
title: svd_team_1
---
graded by email 27/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~~c ~~e ~~ e ]$

Example 3(a): Fill in the gaps

$\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix}\\ \\ \end{bmatrix}[~\_~~\_~~ ]$ Cannot be done in one step multiplication

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}0\\1 \\ \end{bmatrix}[~0~~1~~ ]$

Draw some conclusions.
Why 3(a) did not work?

Multiplying by a column matrix of all 1's gives equal columns values. One column space.
Example 3 has rank 2.

You cannot create a matrix of higher rank from a linear combination of a lower rank matrix.

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

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

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

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

Frobenius norm:
$\|E\|_f^2=(30-a)^2+(28-b)^2+(28-ca)^2+(30-cb)^2=F(a,b,c)$

To minimize distance between $A$ and $\tilde A$:

$\partial F/\partial a =-2(30-a)-2c(28-ca)=0$
$\partial F/\partial b =-2(28-b)-2c(30-cb)=0$
$\partial F/\partial c =-2a(28-ac)-2b(30-cb)=0$

$a=29, b=29, c=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$.
$A=\begin{bmatrix} 30&28\\28&30\\\end{bmatrix}$

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

$A=E+\tilde A=\begin{bmatrix} 1&-1\\-1&1\\\end{bmatrix}+\begin{bmatrix} 29&29\\29&29\\\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.

Eigenvalues of A: $\lambda_1=58, \lambda_2=2$
$\begin{bmatrix}1/\sqrt{2} &-1/\sqrt{2} \\ 1/\sqrt{2}&1/\sqrt{2} \end{bmatrix}$

$\tilde A=58\begin{bmatrix}1/\sqrt{2} \\1/\sqrt{2} \end{bmatrix}\begin{bmatrix}1/\sqrt{2} &1/\sqrt{2} \end{bmatrix}$

$E=2\begin{bmatrix}-1/\sqrt{2} \\1/\sqrt{2} \end{bmatrix}\begin{bmatrix}-1/\sqrt{2} &1/\sqrt{2} \end{bmatrix}$

$\tilde A$ corresponds with the largest eigenvalue and its corresponding eigenvector. $E$ corresponds with the smallest eigenvalue and its corresponding eigenvector. Spectral Decomposition only works with 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}$

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

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

Frobenius norm:
$\|E\|_f^2=(1-a)^2+b^2+(1-ca)^2+(1-cb)^2=F(a,b,c)$

To minimize distance between $A$ and $\tilde A$:

$\partial F/\partial a =-2(1-a)-2c(1-ca)=0$
$\partial F/\partial b =2b-2c(1-cb)=0$
$\partial F/\partial c =-2a(1-ac)-2b(1-cb)=0$

$a_1= (5-\sqrt5)/10, b_1=-1/\sqrt5, c_1=(1-\sqrt5)/2$
$a_2= (5+\sqrt5)/10, b_2=1/\sqrt5, c_2=(1+\sqrt5)/2$

$\tilde A_1=\begin{bmatrix} (5-\sqrt5)/10&-1/\sqrt5\\(5-3\sqrt5)/10&(\sqrt5 -1)/(2\sqrt5)\\\end{bmatrix}$

$\tilde A_2=\begin{bmatrix} (5+\sqrt5)/10&1/\sqrt5\\(5+3\sqrt5)/10&(\sqrt5+1)/(2\sqrt5)\\\end{bmatrix}$

$\tilde E_1=\begin{bmatrix} (5+\sqrt5)/10&1/\sqrt5\\(5+3\sqrt5)/10&(\sqrt5 +1)/(2\sqrt5)\\\end{bmatrix}$

$\tilde E_2=\begin{bmatrix} (5-\sqrt5)/10&-1/\sqrt5\\(5-3\sqrt5)/10&(\sqrt5-1)/(2\sqrt5)\\\end{bmatrix}$

2. Can you compute $\tilde A$ and $E$ using eigenvectors and eigenvalues of $A$?

Eigenvalue of $A = 1$
Eigenvector of $A = \begin{bmatrix}0\\ 1\\ \end{bmatrix}$

No

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$?

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

Eigenvalue of $AA^T$ and $A^TA = 2.618034,0.381966$
Unit eigenvectors of $AA^T = \begin{bmatrix}0.5257311\\ 0.8506508\\ \end{bmatrix},\begin{bmatrix}-0.8506508\\ 0.5257311\\ \end{bmatrix}$

Unit eigenvectors of $A^TA = \begin{bmatrix}-0.8506508\\ -0.5257311\\ \end{bmatrix},\begin{bmatrix}0.5257311\\ -0.8506508\\ \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$$

$\sigma_1= \sqrt{2.618}$
${\bf u_1}=\begin{bmatrix}0.5257311\\ 0.8506508\\ \end{bmatrix}$
${\bf v_1}^T=\begin{bmatrix}-0.8506508& -0.5257311\\ \end{bmatrix}$

$A_1 = 1.618034 * \begin{bmatrix}0.5257311\\ 0.8506508\\ \end{bmatrix}\begin{bmatrix}-0.8506508& -0.5257311\\ \end{bmatrix}$

$A_1 = \begin{bmatrix}-0.7236068 & -0.4472136 \\ -1.1708204 & -0.7236068\end{bmatrix}$

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

$A_1 = -1 * \tilde A_2$ and $A_1 = A-\tilde 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.

$u=\begin{bmatrix} u_1\\u_2\\...\\u_n\end{bmatrix},v=\begin{bmatrix} v_1\\v_2\\...\\v_m\end{bmatrix},uv^T=\begin{bmatrix} u_1v_1&u_1v_2&...&u_1v_m\\u_2v_1&u_2v_2&...&u_2v_m\\...&...&...&...\\u_nv_1&u_2v_m&...&u_nv_m\end{bmatrix}$

By taking row i for all rows >=2 and multiplying by $u_1/u_i$ then subtracting row 1, you will discover the REF is $\begin{bmatrix} u_1v_1&u_1v_2&...&u_1v_m\\0&0&...&0\\...&...&...&...\\0&0&...&0\end{bmatrix}$

With 1 pivot, this matrix, $uv^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.

Take the square root of the largest eigenvalue and corresponsing unit eigenvector of $MM^T$ and $M^TM$ and use the equation from problem 3 $A_1=\sigma_1{\bf u_1}{\bf v_1}^T$ to generate the closest rank 1 matrix to M