The rank of a matrix X E Rnxiamp; is at most: min{n,p}. A matrix is called full-rank if it has this maximum possible rank: rank(X) = min{n,...

The rank of a matrix X ∈ R n×p is at most: min{n, p}. A matrix is called full-rank if it has this maximum possible rank: rank(X) = min{n, p}. Recall that for a vector y ∈ R n the Euclidean (or `2) norm is kyk = qPn i=1 y 2 i . Problem 2.2 Assume p ≤ n and let X ∈ R n×p be a full-rank matrix1 , and H = X(XT X) −1XT (1) Note that H is a square n × n matrix. This problem is devoted to understanding the properties H. (a) Show that H is symmetric (HT = H) and idempotent (H2 = H). Hint: (AB) T = B T A T . Use this to derive (ABC) T = C T B T A T . Also (A −1 ) T = (A T ) −1 , hence an invertible matrix is symmetric if and only if its inverse is symmetric. 1This together with p ≤ n guarantees that X T X is invertible, which makes H well-defined. 1 Any matrix that satisfies conditions in (a) is an orthogonal projection matrix. In this problem, we will verify this directly for the H given in (1). Let V = Im(X). (b) Show that for any y ∈ R n , Hy ∈ V . (c) Let e = y − Hy = (I − H)y and show that e ∈ V ⊥. Hint: Use [Im(X)]⊥ = ker(X T ) The combination of parts (b) and (c) show that Hy is the projection of y onto V . (d) Show that I−H is symmetric and idempotent (hence an orthogonal projection matrix). Can you guess what subspace it projects onto? Since H is symmetric, it has a spectral decomposition of the form H = UΛU T , where U is orthogonal and Λ is diagonal. (e) Show that Λ2 = Λ. What does this tell you about the eigenvalues of H? Pick any vector y ∈ R n and let yb = Hy be the projection of y onto Im(X) and e = (I − H)y the error (or residual). (f) Show that kyk 2 = kybk 2 + kek 2 . Hint: Recall that kyk 2 = y T y, expand and use properties of H and I − H. (g) Show that for any y ∈ R n , we have y T Hy = kHyk 2 . Is H a PSD matrix? The projection matrix H in (1) only depends on the Im(X) and not the particular basis used to describe it. Let us consider the following concrete examples: X1 =   0 1 −2 1 0 0 1 0   , X2 =   0 2 −2 0 0 0 1 1   Here Im(X1) = Im(X2) (can you see why?). (h) Let H1 and H2 be defined based on X1 and X2 using (1). Verify that H1 = H2. (i) Find the projection of y = [4 2 0 1]T onto Im(X1) and compute kek 2 (the squared norm of the residual). Can you explain what is going on?