15-496/859X: Computer Science Theory for the Information Age Spring 2012Carnegie Mellon University V. Guruswami & R. KannanProblem Set 2Due by 6 pm, Friday, February 17Instructions• You should think about each problem by yourself for at least 30 minutes before choosing tocollaborate with others.• You are allowed to collaborate with fellow students taking the class in solving the problems (ingroups of at most 3 people for each problem). In fact this is encouraged so that you interactwith and learn from each other. However, you must write up your solutions on your own.If you collaborate in solving problems, you should clearly acknowledge your collaborators foreach problem.• Reference to any external material besides the course text and material covered in lecture isnot allowed. In particular, you are not allowed to search for answers or hints on the web.You are encouraged to contact the instructors or the TA for a possible hint if you feel stuckon a problem and require some assistance.• Solutions typeset in LATEX are preferred.• Feel free to email the instructors or the TA if you have any questions or would like anyclarifications about the problems.• You are urged to start work on the problem set early.1. (10 points) Let A be an n × d matrix (for n ≥ d) with orthogonal columns w1.w2, . . . , wdof positive lengths `1, `2, . . . , `dno two of which are equal. What is the Singular ValueDecomposition of A? Justify your answer.2. (10 points) Let A be a square n × n matrix whose rows are orthonormal. Prove that thecolumns of A must also be orthonormal. Is this necessarily true for m × n matrices whenm < n?3. (15 points) Suppose you are given an overdetermined system of linear equations Ax = b whereA is an m × n matrix with m > n, and b ∈ Rm, which we would like to solve for x ∈ Rn.That is, we have more equations (m) than variables (n), so there may be no solution to thesystem. Thus a natural goal is to find a ”solution” x that minimizes the error kAx − bk2.(a) First, let us assume that A has rank n. Show that the x that minimizes kAx − bk2isunique and given by (ATA)−1ATb.(b) Now consider the general case when the rank r of A may be less than n. Let A =Pri=1σiuivTibe a SVD of A with nonzero singular values σ1, σ2, . . . , σr. Prove thatx∗=rXi=1hb, uiiσivisatisfies kAx∗− bk2= minx∈RnkAx − bk2.4. (20 points) In this problem, we will explore a different way to decompose matrices (focusingon square matrices for concreteness). Along the way we will encounter the very importantnotion of positive semidefiniteness.(a) A real symmetric matrix M ∈ Rn×nis said to be positive semidefinite (psd) if all itseigenvalues λ1≥ λ2≥ · · · ≥ λnare non-negative. What are the singular values of sucha positive semidefinite matrix M?(b) Prove that a real symmetric matrix M ∈ Rn×nis positive semidefinite if and only ifxTMx ≥ 0 for all x ∈ Rn.(c) Prove that if a real symmetric matrix M is positive semidefinite, then so is V M VTforany n × n matrix V .(d) Prove that every n × n matrix A can be decomposed as A = W P for n × n matricesW, P satisfying the conditions (i) WTW = W WT= I, and (ii) P is real symmetric andpositive semidefinite.5. (15 points) Let G = (V, E) be a d-regular simple, undirected graph1with V = {1, 2, . . . , n}.Define the n × n matrix L as follows:Lij=d if i = j−1 (i, j) ∈ E0 otherwise(a) By definition L is a real, symmetric matrix. Prove that L is positive semidefinite.(Hint: Expand the quadratic form xTLx for x ∈ Rn.)(b) What is the smallest eigenvalue of L? Is L invertible?(c) Prove that kLk2≤ 2d. When is equality attained?1This means there are no loops or multiple edges, and each vertex is adjacent to exactly d other