---
title: svd_2_team
---
****Perfect! every detail is there, 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}\begin{bmatrix} 1&1&1&1&1&1\end{bmatrix}$

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}\begin{bmatrix} a&a&c&c&e&e\end{bmatrix}$

Example 3(a): Fill in the gaps

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

Proof:
Assume $\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix} a\\b\end{bmatrix}\begin{bmatrix} c&d\end{bmatrix}$ has a solution for some $a$, $b$, $c$ and $d$ in $\mathbb {R}^2$. By the poperties of matrix multiplication, this means that $ac=1$, $ad=0$, $bc=1$ and $bd=1$. Since $ad=0$, the Zero Product Property states that either $a$ or $d$ must be equal to zero.

Case 1: Let $a=0$. Then $ac=0$ which is a contradiction becuase $ac=1$.
Case 2: Let $d=0$. Then $bd=0$ which is a contradiction becuase $bd=1$.

Neither case is possible and therefore the original assumption must be false by contradiction. Thus $\begin{bmatrix} 1&0\\1&1\\\end{bmatrix}=\begin{bmatrix} a\\b\end{bmatrix}\begin{bmatrix} c&d\end{bmatrix}$ has no solution.

Example 3(b): Fill in the gaps

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

Draw some conclusions.

A $m \times n$ matrix can only be broken down into multiplication of a $m \times 1$ matrix and a $1 \times n$ if the rows of the initial $m\times n$ are linearly dependent.

**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\\na&nb\\\end{bmatrix}$$

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

$$D(a,b,n)=\|A-\tilde A\| = \sqrt{(30-a)^2+(28-b)^2+(28-na)^2+(30-nb)^2}$$

$$\frac{\partial D}{\partial a}=-2(30-a)-2n(28-na)=0$$
$$\frac{\partial D}{\partial b}=-2(28-b)-2n(30-nb)=0$$
$$\frac{\partial D}{\partial n}=-2a(28-na)-2b(30-nb)=0$$

Solving this system of equations yeilds two solutions:
$a=29$, $b=29$, and $n=1$
$a=1$, $b=-1$, and $n=-1$.

The closest matrix to $A$ will be abtained using the solution of $a=29$, $b=29$, and $n=1$, thus

$$\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}=\begin{bmatrix} 29&29\\29&29\\\end{bmatrix}+\begin{bmatrix} 1&-1\\-1&1\\\end{bmatrix}$$
so $E=\begin{bmatrix} 1&-1\\-1&1\\\end{bmatrix}$ is the Error matrix.

Note that $E$ is the matrix obtained using the $a=1$, $b=-1$, and $n=-1$ solution to the system of partial derivatives above.

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?

The eigenvalues of $A$ are $\lambda_1 = 58$ and $\lambda_2 = 2$.

The eigenvector for $\lambda_1= 58$ is ${\bf x}_1=\begin{bmatrix}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{bmatrix}$

The eigenvector for $\lambda_2 = 2$ is ${\bf x}_2= \begin{bmatrix}\frac{-1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{bmatrix}$

Notice that the values obtained for $a$ obtained to create the matricies $\tilde A$ and $E$ are both directly related to the eigenvalues of $A$ since $29 = \frac{1}{2} 58$ and $1 = \frac{1}{2} 2$, so the entries in $\tilde A$ and $E$ can be found using the eigenvalues and eigenvectiors.

$$\lambda_1 {\bf x}_1 {\bf x}_1^T = 58\begin{bmatrix}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{bmatrix} = 58 \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 29&29\\29&29\\\end{bmatrix}= \tilde A $$

$$\lambda_2 {\bf x}_2 {\bf x}_2^T = 2\begin{bmatrix}\frac{-1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix}\frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{bmatrix} = 2\begin{bmatrix} \frac{1}{2} & \frac{-1}{2} \\ \frac{-1}{2} & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} 1&-1\\-1&1\\\end{bmatrix}= E $$

Thus $\tilde A = \lambda_1 {\bf x}_1 {\bf x}_1^T$ and $E = \lambda_2 {\bf x}_2 {\bf x}_2^T$.

This is called Spectral Decomposition, and it can only be done on Square Symmetric Maticies.

**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\\na&nb\end{bmatrix}$$

$$A-\tilde A =\begin{bmatrix} 1-a&-b\\1-na&1-nb\end{bmatrix}$$

$$D(a,b,n)=\|A-\tilde A\| = \sqrt{(1-a)^2+(-b)^2+(1-na)^2+(1-nb)^2}$$

$$\frac{\partial D}{\partial a}=-2(1-a)-2n(1-na)=0$$
$$\frac{\partial D}{\partial b}=-2b-2n(1-nb)=0$$
$$\frac{\partial D}{\partial n}=-2a(1-na)-2b(1-nb)=0$$

Solving this system of equations yeilds two solutions:
$a=\frac{1}{10}(5-\sqrt{5}) \approx 0.27639$, $b=\frac{-1}{\sqrt{5}} \approx -0.44721$, and $n=\frac{1}{2}(1-\sqrt{5}) \approx -0.61803$
$a=\frac{1}{10}(5+\sqrt{5}) \approx 0.72361$, $b=\frac{1}{\sqrt{5}} \approx 0.44721$, and $n=\frac{1}{2}(1+\sqrt{5}) \approx 1.61803$

The closest matrix to $A$ will be abtained using the second solution, thus

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

$$E =\begin{bmatrix} \frac{1}{10}(5-\sqrt{5})&\frac{-1}{\sqrt{5}}\\\frac{1}{10}(5-3\sqrt{5})&\frac{1}{2}(1+\frac{1}{\sqrt{5}})\end{bmatrix} \approx \begin{bmatrix} 0.27639&-0.44721\\-0.17082&-.27639\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$

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

The eigen values for both of these matrices are $\lambda_1 = \frac{3+\sqrt{5}}{2} \approx 2.61803$ and $\lambda_2 = \frac{3-\sqrt{5}}{2} \approx 0.38197$

The unit eigenvectors of $AA^T$ are $u_1 \approx \begin{bmatrix} 0.52573\\0.85065\end{bmatrix}$ and $u_2 \approx \begin{bmatrix} -0.85065\\0.52573\end{bmatrix}$

The unit eigenvectors of $A^TA$ are $v_1 \approx \begin{bmatrix} 0.85065\\0.52573\end{bmatrix}$ and $v_2 \approx \begin{bmatrix} 0.52573\\-0.85065\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$$

$$A_1=\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.72361&0.44721\\1.17082&0.72361\end{bmatrix}$$

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

$$\tilde A = A_1$$
Thus, you can use the eigenvalues and eigenvectors of $AA^T$ and $A^TA$ to find the rank 1 matrix closest to $A$ without having to do any partial derivatives or nonlinear systems of equations.

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

Proof:

Let ${\bf u}$ and ${\bf v}$ be any two non-zero vectors. Let $n$ be the number of elements in ${\bf u}$, thus ${\bf u}=<u_1, u_2, ... u_n>$. Let $m$ be the numbr of elements in ${\bf v}$, thus ${\bf v}=<v_1, v_2, ... v_m>$. Multiplying ${\bf u}$ by ${\bf v}^T$ gives:

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

This multiplication yields a matrix where each row is all of the elements of vector ${\bf v}$ multiplied by a single element of vector ${\bf u}$. This gives the relationship that $row_i = \frac{u_i}{u_1}row_1$, thus every row is proportional to the first one, and the matrix will have 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.

First, calculate the matricies $MM^T$ and $M^TM$. These will both be square, symmetric matricies so they are diagonalizable. $MM^T$ is a square matrix of size $m \times m$ and will thus have $m$ real eigenvalues. $M^TM$ is a square matrix of size $n \times n$ and will thus have $n$ real eigenvalues. Let $r$ be the smaller of the two dimensions, $m$ and $n$.

Next, find the eigenvalues of each of these two matricies. Order the eigenvalues such that $$\lambda_1 > \lambda_2 >...> \lambda_r$$ These first $r$ eigenvalues will be the same for both matricies, and the remaining eigenvalues for the larger matrix will be so small they are insignificant.

Then, find the corresponding eigenvector to each of the eigenvalues in both $MM^T$ and $M^TM$. Let the eigenvectors of $MM^T$ be ${\bf u_1}, {\bf u_2},...,{\bf u_r}$ and the eigenvactors of $M^TM$ be ${\bf v_1}, {\bf v_2},...,{\bf v_r}$

Finally calculate the matrix $M_1$, which is the closest rank 1 matrix to $M$ in Frobenius norm, using the following setup:

$$M_1=\sqrt{\lambda_1}{\bf u_1}{\bf v_1} + \sqrt{\lambda_2}{\bf u_2}{\bf v_2} + ... \sqrt{\lambda_r}{\bf u_r}{\bf v_r}$$

If you let $\sigma_i = \sqrt{\lambda_i}$, then this formula can be written as:

$$M_1=\sigma_1{\bf u_1}{\bf v_1} + \sigma_2{\bf u_2}{\bf v_2} + ... \sigma_r{\bf u_r}{\bf v_r}$$