CS229-Linear Algebra and Multivariable Calculus Solved

Notes: (1) These questions require thought, but do not require long answers. Please be as concise as possible. (2) If you have a question about this homework, we encourage you to post your question on our Piazza forum, at https://piazza.com/stanford/fall2018/cs229. (3) If you missed the first lecture or are unfamiliar with the collaboration or honor code policy, please read the policy on Handout #1 (available from the course website) before starting work. (4) This specific homework is not graded, but we encourage you to solve each of the problems to brush up on your linear algebra. Some of them may even be useful for subsequent problem sets. It also serves as your introduction to using Gradescope for submissions.

1.    Gradients and Hessians
Recall that a matrix A ∈ Rn×n is symmetric if AT = A, that is, Aij = Aji for all i,j. Also recall the gradient ∇f(x) of a function f : Rn → R, which is the n-vector of partial derivatives

                                                               where   .

The hessian ∇2f(x) of a function f : Rn → R is the n × n symmetric matrix of twice partial

derivatives,

 .

(a)    Let , where A is a symmetric matrix and b ∈ Rn is a vector. What is ∇f(x)?

(b)    Let f(x) = g(h(x)), where g : R → R is differentiable and h : Rn → R is differentiable. What is ∇f(x)?

(c)    Let , where A is symmetric and b ∈ Rn is a vector. What is ∇2f(x)?

(d)   Let f(x) = g(aTx), where g : R → R is continuously differentiable and a ∈ Rn is a vector. What are ∇f(x) and ∇2f(x)? (Hint: your expression for ∇2f(x) may have as few as 11 symbols, including 0 and parentheses.)

2.     Positive definite matrices
A matrix A ∈ Rn×n is positive semi-definite (PSD), denoted  and xTAx ≥ 0 for all x ∈ Rn. A matrix A is positive definite, denoted  and xTAx > 0 for all x 6= 0, that is, all non-zero vectors x. The simplest example of a positive definite matrix is the identity I (the diagonal matrix with 1s on the diagonal and 0s elsewhere), which satisfies

 .

CS229 Problem Set #0                                                                                                                                               2

(a)    Let z ∈ Rn be an n-vector. Show that A = zzT is positive semidefinite.

(b)    Let z ∈ Rn be a non-zero n-vector. Let A = zzT. What is the null-space of A? What is the rank of A?

(c)    Let A ∈ Rn×n be positive semidefinite and B ∈ Rm×n be arbitrary, where m,n ∈ N. Is BABT PSD? If so, prove it. If not, give a counterexample with explicit A,B.

3.     Eigenvectors, eigenvalues, and the spectral theorem
The eigenvalues of an n × n matrix A ∈ Rn×n are the roots of the characteristic polynomial pA(λ) = det(λI − A), which may (in general) be complex. They are also defined as the the values λ ∈ C for which there exists a vector x ∈ Cn such that Ax = λx. We call such a pair (x,λ) an eigenvector, eigenvalue pair. In this question, we use the notation diag(λ1,...,λn) to denote the diagonal matrix with diagonal entries λ1,...,λn, that is,

 

 diag(  .

(a) Suppose that the matrix A ∈ Rn×n is diagonalizable, that is, A = TΛT−1 for an invertible matrix T ∈ Rn×n, where Λ = diag(λ1,...,λn) is diagonal. Use the notation t(i) for the columns of T, so that T = [t(1) ··· t(n)], where t(i) ∈ Rn. Show that At(i) = λit(i), so that the eigenvalues/eigenvector pairs of A are (t(i),λi).

A matrix U ∈ Rn×n is orthogonal if UTU = I. The spectral theorem, perhaps one of the most important theorems in linear algebra, states that if A ∈ Rn×n is symetric, that is, A = AT, then A is diagonalizable by a real orthogonal matrix. That is, there are a diagonal matrix Λ ∈ Rn×n and orthogonal matrix U ∈ Rn×n such that UTAU = Λ, or, equivalently,

A = UΛUT.

Let λi = λi(A) denote the ith eigenvalue of A.

(b)    Let A be symmetric. Show that if U = [u(1) ··· u(n)] is orthogonal, where u(i) ∈ Rn and A = UΛUT, then u(i) is an eigenvector of A and Au(i) = λiu(i), where Λ = diag(λ1,...,λn).

(c)    Show that if A is PSD, then λi(A) ≥ 0 for each i.