Transcription of CS 229, Fall 2018 ProblemSet#0: …
1 cs229 problem Set #01CS 229, Fall 2018 problem Set #0: Linear Algebra and MultivariableCalculusNotes:(1) These questions require thought, but do not require long answers. Please be asconcise as possible. (2) If you have a question about this homework, we encourage you to postyour question on our Piazza forum, (3) Ifyou missed the first lecture or are unfamiliar with the collaboration or honor code policy, pleaseread the policy on Handout #1 (available from the course website) before starting work. (4)This specific homework isnot graded, but we encourage you to solve each of the problems tobrush up on your linear algebra. Some of them may even be useful for subsequent problem also serves as your introduction to using Gradescope for [0 points] Gradients and HessiansRecall that a matrixA Rn nissymmetricifAT=A, that is,Aij=Ajifor alli,j.
2 Alsorecall the gradient f(x) of a functionf:Rn R, which is then-vector of partial derivatives f(x) = x1f(x).. xnf(x) wherex= .The hessian 2f(x) of a functionf:Rn Ris then nsymmetric matrix of twice partialderivatives, 2f(x) = 2 x21f(x) 2 x1 x2f(x) 2 x1 xnf(x) 2 x2 x1f(x) 2 x22f(x) 2 x2 xnf(x).. 2 xn x1f(x) 2 xn x2f(x) 2 x2nf(x) .(a) Letf(x) =12xTAx+bTx, whereAis a symmetric matrix andb Rnis a vector. Whatis f(x)?(b) Letf(x) =g(h(x)), whereg:R Ris differentiable andh:Rn Ris is f(x)?(c) Letf(x) =12xTAx+bTx, whereAis symmetric andb Rnis a vector. What is 2f(x)?(d) Letf(x) =g(aTx), whereg:R Ris continuously differentiable anda Rnis a are f(x) and 2f(x)? (Hint:your expression for 2f(x) may have as few as 11symbols, including and parentheses.)2.[0 points] Positive definite matricesA matrixA Rn nispositive semi-definite(PSD), denotedA 0, ifA=ATandxTAx 0for allx Rn.
3 A matrixAispositive definite, denotedA 0, ifA=ATandxTAx >0 forallx6= 0, that is, all non-zero vectorsx. The simplest example of a positive definite matrix isthe identityI(the diagonal matrix with 1s on the diagonal and 0s elsewhere), which satisfiesxTIx= x 22= ni= problem Set #02(a) Letz Rnbe ann-vector. Show thatA=zzTis positive semidefinite.(b) Letz Rnbe anon-zeron-vector. LetA=zzT. What is the null-space ofA? What isthe rank ofA?(c) LetA Rn nbe positive semidefinite andB Rm nbe arbitrary, wherem,n N. IsBABTPSD? If so, prove it. If not, give a counterexample with explicitA, [0 points] Eigenvectors, eigenvalues, and the spectral theoremThe eigenvalues of ann nmatrixA Rn nare the roots of the characteristic polynomialpA( ) = det( I A), which may (in general) be complex. They are also defined as the thevalues Cfor which there exists a vectorx Cnsuch thatAx= x.
4 We call such a pair(x, ) aneigenvector, eigenvaluepair. In this question, we use the notation diag( 1,.., n)to denote the diagonal matrix with diagonal entries 1,.., n, that is,diag( 1,.., n) = 100 00 20 000 3 n .(a) Suppose that the matrixA Rn nis diagonalizable, that is,A=T T 1for an invertiblematrixT Rn n, where = diag( 1,.., n) is diagonal. Use the notationt(i)for thecolumns ofT, so thatT= [t(1) t(n)], wheret(i) Rn. Show thatAt(i)= it(i), sothat the eigenvalues/eigenvector pairs ofAare (t(i), i).A matrixU Rn nis orthogonal ifUTU=I. The spectral theorem, perhaps one of the mostimportant theorems in linear algebra, states that ifA Rn nis symetric, that is,A=AT,thenAisdiagonalizable by a real orthogonal matrix. That is, there are a diagonal matrix Rn nand orthogonal matrixU Rn nsuch thatUTAU= , or, equivalently,A=U i= i(A) denote theith eigenvalue ofA.
5 (b) LetAbe symmetric. Show that ifU= [u(1) u(n)] is orthogonal, whereu(i) RnandA=U UT, thenu(i)is an eigenvector ofAandAu(i)= iu(i), where =diag( 1,.., n).(c) Show that ifAis PSD, then i(A) 0 for eachi.
