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

Problem B1 (20 pts). Let U1, . . . , Up be any p 2 subspaces of some vector space E.Prove that U1 + + Up is a direct sum iffUi Xi1j=1Uj

= (0), i = 2, . . . , p.Problem B2 (50 pts). Given any vector space E, a linear map f : E E is an involutionif f f = id.(1) Prove that an involution f is invertible. What is its inverse?(2) Let E1 and E1 be the subspaces of E defined as follows:E1 = {u E | f(u) = u}E1 = {u E | f(u) = u}.Prove that we have a direct sumE = E1 E1.Hint. For every u E, writeu =u + f(u)2+u f(u)2.(3) If E is finite-dimensional and f is an involution, prove that there is some basis of Eover which the matrix of f is of the formIk,nk =

Ik 00 Ink

,where Ik is the k k identity matrix (similarly for Ink) and k = dim(E1). Can you give ageometric interpretation of the action of f (especially when k = n 1)?1Problem B3 (50 pts). A rotation R in the plane R2is given by the matrixR =

cos sin sin cos

.(1) Use Matlab to show the action of a rotation R on a simple figure such as a triangleor a rectangle, for various values of , including = /6, /4, /3, /2.(2) Prove that R is invertible and that its inverse is R.(3) For any two rotations R and R, prove thatR R = R R = R+.Use (2)-(3) to prove that the rotations in the plane form a commutative group denotedSO(2).Problem B4 (110 pts). Consider the affine map R,(a1,a2)in R2 given by

y1y2

=

cos sin sin cos x1x2

a1a2

.(1) Prove that if 6= k2, with k Z, then R,(a1,a2) has a unique fixed point (c1, c2),that is, there is a unique point (c1, c2) such that

c1c2

= R,(a1,a2)

c1c2

,and this fixed point is given by

c1c2

=12 sin(/2)cos(/2 /2) sin(/2 /2)sin(/2 /2) cos(/2 /2) a1a2

.(2) In this question, we still assume that 6= k2, with k Z. By translating thecoordinate system with origin (0, 0) to the new coordinate system with origin (c1, c2), whichmeans that if (x1, x2) are the coordinates with respect to the standard origin (0, 0) and if(x01, x02) are the coordinates with respect to the new origin (c1, c2), we havex1 = x01 + c1x2 = x02 + c2and similarly for (y1, y2) and (y01, y02), then show that

y1y2

= R,(a1,a2)

x1x2

2becomes

y01y02

= R

x01x02

.Conclude that with respect to the new origin (c1, c2), the affine map R,(a1,a2) becomesthe rotation R. We say that R,(a1,a2)is a rotation of center (c1, c2).(3) Use Matlab to show the action of the affine map R,(a1,a2) on a simple figure such as atriangle or a rectangle, for = /3 and various values of (a1, a2). Display the center (c1, c2)of the rotation.What kind of transformations correspond to = k2, with k Z?(4) Prove that the inverse of R,(a1,a2)is of the form R,(b1,b2), and find (b1, b2) in termsof and (a1, a2).(5) Given two affine maps R,(a1,a2) and R,(b1,b2), prove thatR,(b1,b2) R,(a1,a2) = R+,(t1,t2)for some (t1, t2), and find (t1, t2) in terms of , (a1, a2) and (b1, b2).Even in the case where (a1, a2) = (0, 0), prove that in generalR,(b1,b2) R 6= R R,(b1,b2).Use (4)-(5) to show that the affine maps of the plane defined in this problem form anonabelian group denoted SE(2).Prove that R,(b1,b2) R,(a1,a2)is not a translation (possibly the identity) iff + 6= k2,for all k Z. Find its center of rotation when (a1, a2) = (0, 0).If + = k2, then R,(b1,b2) R,(a1,a2)is a pure translation. Find the translation vectorof R,(b1,b2) R,(a1,a2).Problem B5 (80 pts). A subset A of Rnis called an affine subspace if either A = , orthere is some vector a Rn and some subspace U of Rnsuch thatA = a + U = {a + u | u U}.We define the dimension dim(A) of A as the dimension dim(U) of U.(1) If A = a + U, why is a A?What are affine subspaces of dimension 0? What are affine subspaces of dimension 1(begin with R2)? What are affine subspaces of dimension 2 (begin with R3)?Prove that any nonempty affine subspace is closed under affine combinations.(2) Prove that if A = a + U is any nonempty affine subspace, then A = b + U for anyb A.3(3) Let A be any nonempty subset of Rnclosed under affine combinations. For anya A, prove thatUa = {x a Rn| x A}is a (linear) subspace of Rnsuch thatA = a + Ua.Prove that Ua does not depend on the choice of a A; that is, Ua = Ub for all a, b A. Infact, prove thatUa = U = {y x Rn| x, y A}, for all a A,and soA = a + U, for any a A.Remark: The subspace U is called the direction of A.(4) Two nonempty affine subspaces A and B are said to be parallel iff they have the samedirection. Prove that that if A 6= B and A and B are parallel, then A B = .Remark: The above shows that affine subspaces behave quite differently from linear subspaces.Problem B6 (120 pts). (Affine frames and affine maps) For any vector v = (v1, . . . , vn) Rn, let vb Rn+1 be the vector vb = (v1, . . . , vn, 1). Equivalently, vb = (vb1, . . . , vbn+1) Rn+1 isthe vector defined byvbi =(viif 1 i n,1 if i = n + 1.(1) For any m + 1 vectors (u0, u1, . . . , um) with ui Rn and m n, prove that if the mvectors (u1 u0, . . . , um u0) are linearly independent, then the m + 1 vectors (ub0, . . . , ubm)are linearly independent.(2) Prove that if the m + 1 vectors (ub0, . . . , ubm) are linearly independent, then for anychoice of i, with 0 i m, the m vectors uj uifor j {0, . . . , m} with j i 6= 0 arelinearly independent.Any m + 1 vectors (u0, u1, . . . , um) such that the m + 1 vectors (ub0, . . . , ubm) are linearlyindependent are said to be affinely independent.From (1) and (2), the vector (u0, u1, . . . , um) are affinely independent iff for any any choiceof i, with 0 i m, the m vectors uj uifor j {0, . . . , m} with j i 6= 0 are linearlyindependent. If m = n, we say that n + 1 affinely independent vectors (u0, u1, . . . , un) forman affine frame of Rn.4(3) if (u0, u1, . . . , un) is an affine frame of Rn, then prove that for every vector v Rn,there is a unique (n+ 1)-tuple (0, 1, . . . , n) Rn+1, with 0 +1 + +n = 1, such thatv = 0u0 + 1u1 + + nun.The scalars (0, 1, . . . , n) are called the barycentric (or affine) coordinates of v w.r.t. theaffine frame (u0, u1, . . . , un).If we write ei = ui u0, for i = 1, . . . , n, then prove that we havev = u0 + 1e1 + + nen,and since (e1, . . . , en) is a basis of Rn(by (1) & (2)), the n-tuple (1, . . . , n) consists of thestandard coordinates of v u0 over the basis (e1, . . . , en).Conversely, for any vector u0 Rn and for any basis (e1, . . . , en) of Rn, let ui = u0 + eifor i = 1, . . . , n. Prove that (u0, u1, . . . , un) is an affine frame of Rn, and for any v Rn, ifv = u0 + x1e1 + + xnen,with (x1, . . . , xn) Rn(unique), thenv = (1 (x1 + + xx))u0 + x1u1 + + xnun,so that (1(x1 + +xx)), x1, , xn), are the barycentric coordinates of v w.r.t. the affineframe (u0, u1, . . . , un).The above shows that there is a one-to-one correspondence between affine frames (u0, . . .,un) and pairs (u0,(e1, . . . , en)), with (e1, . . . , en) a basis. Given an affine frame (u0, . . . , un),we obtain the basis (e1, . . . , en) with ei = ui u0, for i = 1, . . . , n; given the pair (u0,(e1, . . .,en)) where (e1, . . . , en) is a basis, we obtain the affine frame (u0, . . . , un), with ui = u0 + ei,for i = 1, . . . , n. There is also a one-to-one correspondence between barycentric coordinatesw.r.t. the affine frame (u0, . . . , un) and standard coordinates w.r.t. the basis (e1, . . . , en).The barycentric cordinates (0, 1, . . . , n) of v (with 0 + 1 + + n = 1) yield thestandard coordinates (1, . . . , n) of v u0; the standard coordinates (x1, . . . , xn) of v u0yield the barycentric coordinates (1 (x1 + + xn), x1, . . . , xn) of v.(4) Let (u0, . . . , un) be any affine frame in Rn and let (v0, . . . , vn) be any vectors in Rm.Prove that there is a unique affine map f : Rn Rm such thatf(ui) = vi, i = 0, . . . , n.(5) Let (a0, . . . , an) be any affine frame in Rn and let (b0, . . . , bn) be any n + 1 points inRn. Prove that the (n + 1) (n + 1) matrix A corresponding to the unique affine map fsuch thatf(ai) = bi, i = 0, . . . , n,5is given byA =

bb0bb1 bbn

ba0 ba1 ban1.In the special case where (a0, . . . , an) is the canonical affine frame with ai = ei+1 fori = 0, . . . , n 1 and an = (0, . . . , 0) (where eiis the ith canonical basis vector), show that

ba0 ba1 ban

=1 0 0 00 1 0 0……… 0 00 0 1 01 1 1 1and

ba0 ba1 ban1=1 0 0 00 1 0 0……… 0 00 0 1 01 1 1 1.For example, when n = 2, if we write bi = (xi, yi), then we haveA =x1 x2 x3y1 y2 y31 1 11 0 00 1 01 1 1 =x1 x3 x2 x3 x3y1 y3 y2 y3 y30 0 1 .(6) Recall that a nonempty affine subspace A of Rnis any nonempty subset of Rnclosedunder affine combinations. For any affine map f : Rn Rm, for any affine subspace A ofRn, and any affine subspace B of Rm, prove that f(A) is an affine subspace of Rm, and thatf1(B) is an affine subspace of Rn.Problem B7 (30 pts). Let A be any n k matrix(1) Prove that the k k matrix AA and the matrix A have the same nullspace. Usethis to prove that rank(AA) = rank(A). Similarly, prove that the n n matrix AA andthe matrix A have the same nullspace, and conclude that rank(AA) = rank(A).We will prove later that rank(A) = rank(A).(2) Let a1, . . . , ak be k linearly independent vectors in Rn(1 k n), and let A be then k matrix whose ith column is ai. Prove that AA has rank k, and that it is invertible.Let P = A(AA)1A (an n n matrix). Prove thatP2 = PP= P.What is the matrix P when k = 1?6(3) Prove that the image of P is the subspace V spanned by a1, . . . , ak, or equivalentlythe set of all vectors in Rn of the form Ax, with x Rk. Prove that the nullspace U of P isthe set of vectors u Rnsuch that Au = 0. Can you give a geometric interpretation of U?Conclude that P is a projection of Rn onto the subspace V spanned by a1, . . . , ak, andthatRn = U V.Hint. You may use results from HW2.TOTAL: 460 points.7