(1) SVD of Symmetric and PSD matrices

(a) Compute the SVD of the symmetric matrix (using Julia or otherwise)

B = 【(【) 2   4

3 Ⅰ(n)

Ⅰ

Ⅰ

6 Ⅰ

(b) If A is a symmetric matrix of size n x n, argue that σi = iλi i for all i. Here σi  is the ith singular value of A and λi  is the ith eigenvalue of A.

(c) Based on what you just did, how would you convert a diagonalization of a     general symmetric matrix C to the SVD of C? Say in words what steps need to be taken.

(d) If A is a PSD matrix of size n x n then what is the relationship between its singular values and eigenvalues? What is the SVD of A?

(2) Rank one matrices

(a) Argue that for any two matrices A and B, rank|A + B; s rank|A; + rank|B;.   Hint: What can you say about the columns of A + B and the column space of A + B in relation to the column spaces of A and B? How does the dimension of Col|A + B; relate to the sum of the dimensions of Col|A; and Col|B;. You     can use the fact that if S and T are two sets of vectors in Rn  then                     dim|span{S v T}; s dim|span{S}; + dim|span{T};.

(b) Use SVD to argue that every rank one matrix in Rm ×n  is of the form uvT  for u e Rm  and v e Rn .

(c) Find two rank one matrices whose sum is still rank 1 and two rank one matrices whose sum has rank 2.

(d) If the columns of A e Rm ×k  are al , . . . , ak  and the rows of B e Rk ×n  are b l(T) , . . . , bk(T)  argue that AB = al b l(T) + a2 b2(T) + … + ak bk(T) .

Hint: You could show that the |i, j;-entry on the left side is the same at the |i, j;-entry on the right side. Warm up by checking that if

A = |c   d|

then

AB = |c(a)| [e

and   B = |h   i   j |

f   g] + |d(b)| [h   i   j] .

(3) Rank one decomposition of symmetric and PSD matrices

(a) Argue that all rank one PSD matrices of size n x n can be written as bbT  for a vector b e Rn .

(b) Describe 3 x 3 PSD matrices of rank 1 that have 0s and 1s on the diagonal.     Hint: Use part (a) to deduce what any rank one matrix looks like, then find  necessary conditions for the diagonals of your psd matrix to be 0 or 1. You do not need to explicitly give all matrices but you should argue how many you    could get (double counting is ok) and explain how you get them.

(c) Argue that a PSD matrix of rank r is the sum of r rank one PSD matrices.      This means that you can get an expression of the form Ml + M2 + … + Mr  where each Mi  is PSD and rank one.

(d) Can a symmetric matrix of rank r also be written as Ml + M2 + … + Mr  where each Mi  is PSD and rank one? Explain your answer.