[Solved] SOLVED: Fundamentals of Linear Algebra and Optimization Homework 2

Problem B5 (120 pts). (Haar extravaganza) Consider the matrixW3,3 =Problem B1 (10 pts). Given any m n matrix A and any n p matrix B, if we denote the columns of A by A1, . . . , An and the rows of B by B1, . . . , Bn, prove thatAB = A1B1 + + AnBn.Problem B2 (10 pts). Let f : E F be a linear map which is also a bijection (it isinjective and surjective). Prove that the inverse function f1: F E is linear.Problem B3 (10 pts). Given two vectors spaces E and F, let (ui)iI be any basis of E and let (vi)iI be any family of vectors in F. Prove that the unique linear map f : E Fsuch that f(ui) = vifor all i I is surjective iff (vi)iI spans F.Problem B4 (10 pts). Let f : E F be a linear map with dim(E) = n and dim(F) = m.Prove that f has rank 1 iff f is represented by an m n matrix of the formA = uvwith u a nonzero column vector of dimension m and v a nonzero column vector of dimensionn.1 0 0 0 1 0 0 01 0 0 0 1 0 0 00 1 0 0 0 1 0 00 1 0 0 0 1 0 00 0 1 0 0 0 1 00 0 1 0 0 0 1 00 0 0 1 0 0 0 10 0 0 1 0 0 0 1(1) Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,3c of applyingW3,3 to c isW3,3c = (c1 + c5, c1 c5, c2 + c6, c2 c6, c3 + c7, c3 c7, c4 + c8, c4 c8),1the last step in reconstructing a vector from its Haar coefficients.(2) Prove that the inverse of W3,3 is (1/2)W3,3. Prove that the columns and the rows ofW3,3 are orthogonal.(3) Let W3,2 and W3,1 be the following matrices:W3,2 =1 0 1 0 0 0 0 01 0 1 0 0 0 0 00 1 0 1 0 0 0 00 1 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 00 0 0 0 0 0 0 1, W3,1 =1 1 0 0 0 0 0 01 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 00 0 0 0 0 0 0 1.Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,2c of applying W3,2to c isW3,2c = (c1 + c3, c1 c3, c2 + c4, c2 c4, c5, c6, c7, c8),the second step in reconstructing a vector from its Haar coefficients, and the result W3,1c ofapplying W3,1 to c isW3,1c = (c1 + c2, c1 c2, c3, c4, c5, c6, c7, c8),the first step in reconstructing a vector from its Haar coefficients.Conclude thatW3,3W3,2W3,1 = W3,the Haar matrixW3 =1 1 1 0 1 0 0 01 1 1 0 1 0 0 01 1 1 0 0 1 0 01 1 1 0 0 1 0 01 1 0 1 0 0 1 01 1 0 1 0 0 1 01 1 0 1 0 0 0 11 1 0 1 0 0 0 1.Hint. First, check thatW3,2W3,1 =

W2 04,404,4 I4

,whereW2 =1 1 1 01 1 1 01 1 0 11 1 0 1 .2(4) Prove that the columns and the rows of W3,2 and W3,1 are orthogonal. Deduce fromthis that the columns of W3 are orthogonal, and the rows of W13are orthogonal. Are therows of W3 orthogonal? Are the columns of W13orthogonal? Find the inverse of W3,2 andthe inverse of W3,1.(5) For any n 2, the 2n 2n matrix Wn,n is obtained form the two rows1, 0, . . . , 0| {z }2n1, 1, 0, . . . , 0| {z }2n11, 0, . . . , 0| {z }2n1, 1, 0, . . . , 0| {z }2n1by shifting them 2n1 1 times over to the right by inserting a zero on the left each time.Given any vector c = (c1, c2, . . . , c2n ), show that Wn,nc is the result of the last step in theprocess of reconstructing a vector from its Haar coefficients c. Prove that W1n,n = (1/2)Wn,n,and that the columns and the rows of Wn,n are orthogonal.Extra credit (30 pts.)Given a m n matrix A = (aij ) and a p q matrix B = (bij ), the Kronecker product (ortensor product) A B of A and B is the mp nq matrixA B =a11B a12B a1nBa21B a22B a2nB…………am1B am2B amnB.It can be shown (and you may use these facts without proof) that is associative and that(A B)(C D) = AC BD(A B)= A B,whenever AC and BD are well defined.Check thatWn,n =

I2n1

11

I2n1

11,and thatWn =

Wn1

11

I2n1

11.Use the above to reprove thatWn,nWn,n = 2I2n .3LetB1 = 21 00 1=

2 00 2and for n 1,Bn+1 = 2Bn 00 I2n

.Prove thatWn Wn = Bn, for all n 1.(6) The matrix Wn,i is obtained from the matrix Wi,i (1 i n 1) as follows:Wn,i =

Wi,i 02i,2n2i02n2i,2i I2n2i

.It consists of four blocks, where 02i,2n2i and 02n2i,2i are matrices of zeros and I2n2i is theidentity matrix of dimension 2n 2i.Explain what Wn,i does to c and prove thatWn,nWn,n1 Wn,1 = Wn,where Wn is the Haar matrix of dimension 2n.Hint. Use induction on k, with the induction hypothesisWn,kWn,k1 Wn,1 =

Wk 02k,2n2k02n2k,2k I2n2k

.Prove that the columns and rows of Wn,k are orthogonal, and use this to prove that thecolumns of Wn and the rows of W1nare orthogonal. Are the rows of Wn orthogonal? Arethe columns of W1northogonal? Prove thatW1n,k =12Wk,k 02k,2n2k02n2k,2k I2n2k

.Problem B6 (20 pts). Prove that for every vector space E, if f : E E is an idempotentlinear map, i.e., f f = f, then we have a direct sumE = Ker f Im f,so that f is the projection onto its image Im f.Problem B7 (20 pts). Let U1, . . . , Up be any p 2 subspaces of some vector space E andrecall that the linear mapa: U1 Up E4is given bya(u1, . . . , up) = u1 + + up,with ui Uifor i = 1, . . . , p.(1) If we let Zi U1 Up be given byZi =

u1, . . . , ui1, Xpj=1,j6=iuj, ui+1, . . . , up

Xpj=1,j6=iuj Ui Xpj=1,j6=iUj,for i = 1, . . . , p, then prove thatKer a = Z1 = = Zp.In general, for any given i, the condition Ui Ppj=1,j6=i Uj

= (0) does not necessarilyimply that Zi = (0). Thus, letZ =

u1, . . . , ui1, ui, ui+1, . . . , up

ui = Xpj=1,j6=iuj, ui Ui Xpj=1,j6=iUj

, 1 i p

.Since Ker a = Z1 = = Zp, we have Z = Ker a. Prove that ifUi Xpj=1,j6=iUj

= (0) 1 i p,then Z = Ker a = (0).(2) Prove that U1 + + Up is a direct sum iffUi Xpj=1,j6=iUj

= (0) 1 i p.(3) Extra credit (40 pts). Assume that E is finite-dimensional, and let fi: E E be anyp 2 linear maps such thatf1 + + fp = idE.Prove that the following properties are equivalent:(1) f2i = fi, 1 i p.(2) fj fi = 0, for all i 6= j, 1 i, j p.TOTAL: 200 + 70 points.5