Selected Solutions to Linear Algebra Done Wrong PDF

Preview

Summary

강의교재 솔루션...

Description

Selected Solutions to Linear Algebra Done Wrong Jing Huang August 2018

Introduction Linear Algebra Done Wrong by Sergei Treil is a well-known linear algebra reference book for collage students. While when I read this book and did the exercises, I found no solution manual available online. In contrast, the solution manual for the other famous book Linear Algebra Done Right is readily available for its greater popularity than Dong Wrong (without any doubt, Dong Wrong is an excellent book worth reading). However, reference solutions are important. Insights tend to hide behind mistakes and ambiguity, which may be missed if there does not exist a good way to check our answers. Reference solutions also help to give inspiration and save time when there is no hint or the hint is obscure. I scanned all and did most problems of the first 7 chapters (2014 version) and share those I think valuable here (those are relatively hard or insightful from my perspective. I read this book for kind of reviewing and deeper mathematical understanding). The rest problems should be tractable even for a newbie in linear algebra. In chapter 7, there are only very few easy problems and none is selected here. The last chapter, Chapter 8, deals with dual spaces and tensors, which could be advanced for most readers and is also not included. Note that as references, the correctness and optimality of the solutions are not guaranteed, and the readers need be critical. Last but not least, this manual intends to facilitate readers’ learning process, especially self-learning process. Do not copy the contents for homework use since it will violate your college’s academic codes. I’m now a PhD student with limited time in crafting the contents. Contact me at [email protected] if any advice or feedback to make the project better and more helpful. Cheers.

Chapter 1. Basic Notations 1.4. Prove that a zero vector of a vector space V is unique. Proof Suppose there exist 2 different zero vectors 01 and 02 . So for any 1

v ∈ V , we have v + 01 = v v + 02 = v. Find the difference of the equations above, we get 02 − 01 = v − v = 01 /(or) 02 , then 02 = 01 + 01 /02 = 01 . So the zero vector is unique. 1.6. Prove that the additive inverse, defined in Axiom 4 of a vector space is unique. Proof Assume there exist 2 different additive inverses w1 and w2 of vector v ∈ V . Then v + w1 = 0 v + w2 = 0. Obtain the difference of the two equations, we get w1 − w2 = 0, then w1 = w2 . So the additive inverse is unique. 1.7. Prove that 0v = 0 for any vector v ∈ V . Proof 0v = (0α)v = α(0v) for any scalar α, so (1 − α)0v = 0 for all scalar (1 − α). Then 0v = 0. 1.8. Prove that for any vector v its additive inverse −v is given by (−1)v. Proof v + (−1)v = (1 − 1)v = 0v = 0 and we know form Problem 1.6 that the additive inverse is unique. So −v = (−1)v. 2.5. Let a system of vectors v1 , v2 , ..., vr be linearly independent but not generating. Show that it is possible to find a vector vr+1 such that the system v1 , v2 , ..., vr , vr+1 is linear independent. P Proof Take vr+1 that can not be represented as rk=1 αk vk . It is possible because v1 , v2 , ..., vr is not generating. Now we need to show v1 , v2 , ..., vr , vr+1 is linear independent. Suppose that v1 , v2 , ..., vr , vr+1 is linear dependent, i.e. α1 v1 + α2 v2 + ... + αr vr + αr+1 vr+1 = 0, 2

and

Pr+1

k=1 |αk |

6= 0. If αr+1 = 0, then α1 v1 + α2 v2 + ... + αr vr = 0,

Pr |αk | 6= 0. This contradicts that v1 , v2 , ..., vr is linearly indepenand k=1 dent. So αr+1 6= 0. Thus vr+1 can be represented as vr+1 = −

1 αr+1

r X

αk vk .

k=1

This contradicts the premise that vr+1 can not be represented by v1 , v2 , ..., vr . Thus, the system v1 , v2 , ..., vr , vr+1 is linearly independent. 3.2. Let a linear transformation in R2 be in the line x1 = x2 . Find its matrix. Solution 1. Reflection is a linear transformation. It is completely defined T T = r1 = [0 1]T , e2 = [0 1]T ⇒ on the standard basis. And e1 = [1 0]T ⇒ = r2 = [1 0]T . So the matrix is the combination of the two transformed standard basis as its first and second column. i.e.   0 1 . T = [r1 r2 ] = 1 0 Solution 2. (A more general method) Let α be the angle between the x-axis and the line. The reflection can be achieved through following steps: first, rotate the line around the origin (z-axis in 3D space) −α so the line aligns with the x-axis (This line happen to pass through the origin, if not, translation is needed in advance to make the line pass through the origin and we need to use homogeneous coordinates since translation is not a linear transformation if represented in standard coordinates). Secondly, perform reflection about the x-axis. Lastly, we need to rotate the current frame back to its original location or perform other corresponding inverse transformation. So T = Rotz (−α) · Ref · Rotz(α). That is 

   cos(−α) − sin(−α) 1 0 cos(α) − sin(α) T = 0 −1 sin(α) cos(α) sin(−α) cos(−α)    π  π cos(− 4 ) − sin(− 4 ) 1 0 cos( π4 ) − sin( π4 ) = sin(− π4 ) cos(− π4 ) 0 −1 sin( π4 ) cos( π4 )   0 1 = . 1 0 3.7. Show that any linear transformation in C (treated as a complex vector 3

space) is a multiplication by α ∈ C. Proof Suppose a linear transformation T : C ⇒ = C. T (1) = a + ib and then T (−1) = −T (1) = −a − ib. Note that i2 = −1. Then T (−1) = T (i2 ) = iT (i). Thus −a − ib = i(a + ib). T (i) = i So for any ω = x + iy ∈ C, T (ω) = T (x + iy) = xT (1) + yT (i) = x(a + ib) + yi(a + ib) = (x + iy)(a + ib) = ωT (1) = ωα, and α = T (1). 5.4. Find the matrix of the orthogonal projection in R2 onto the line x1 = −2x2 . Solution T = R(α)P R(−α)   1 0 = R(α) R(−α). 0 0 α = tan−1 (− 12 ), so we can get the matrix is  4  −52 5 T = . 1 − 25 5 5.7. Find the matrix of the reflection through the line y = −2x/3. Perform all the multiplications. Solution (Similar to 5.4 though not exactly the same.) T = R(α)RefR(−α)   1 0 = R(α) R(−α). 0 −1 α = tan−1 (− 23 ), so we can get the matrix is T =



5 13 − 12 13

 12 − 13 . −135

6.1. Prove that if A : V → W is an isomorphism (i.e. an invertible linear 4

transformation) and v1 , v2 , ..., vn is a basis in V , then Av1 , Av2 , ..., Avn is a basis in W . Proof For any w ∈ W , A−1 w = v ∈ V , w = Av = A[v1 v2 ... vn ][v1 v2 ... vn ]T = [Av1 Av2 ... Avn ][v1 v2 ... vn ]T . So we can see [Av1 Av2 ... Avn ] is in the form of a basis in W . Next we show that Av1 Av2 ... Avn is linearly independent. If not, suppose Av1 can be expressed as a linear combination of Av2 Av3 ... Avn without loss of generality. Multiplying them with A in the left side, it results in that v1 can be expressed by v2 ... vn , which contradicts the fact that v1 , v2 , ..., vn is a basis in V . So the proposition is proved. 7.4. Let X and Y be subspaces of a vector space V. Using the previous exercise, show that X ∪ Y is a subspace if and only if X ⊂ Y or Y ⊂ X. Proof The sufficiency is obvious and easy to verify. For the necessity, suppose X * Y nor Y * X and X ∪ Y is a subspace of V. Then there are vectors x ∈ X, y ∈ Y and x ∈ / Y, y ∈ / X. According to Problem 7.3, x+y ∈ / X, x + y ∈ / Y. So, x + y ∈ / X ∪ Y. i.e., x ∈ X ∪ Y, y ∈ X ∪ Y, but x + y ∈ / X ∪ Y, which contradicts X ∪ Y is a subspace. Thus, X ⊂ Y or Y ⊂ X. 8.5. A transformation T in R3 is a rotation about the line y = x + 3 in the x-y plane through an angle γ. Write a 4 × 4 matrix corresponding to this transformation. You can leave the result as a product of matrices. Solution For a general spatial rotation around a given direction (suppose the direction is given by a vector) through an angle γ, the 3 × 3 rotation matrix can be given by: R = Rx−1R−1 y Rz (γ)Ry Rx , where the rotation by γ is assumed to be performed around z-axis. Rx and Ry are rotations used to align the direction with z-axis and can be determined by simple trigonometry. For the problem given, the line y = x + 3 doesn’t go through the origin, so extra step T0 is needed to translate the line to make it pass the origin and homogeneous coordinates are applied: R = T 0−1 Rx−1R−1 y Rz (γ)Ry Rx T0 . According to the description,   T 0 = Rx−1Ry−1Rz (γ)Ry Rx . 0 1 5

The corresponding matrix is then R=

T0−1



 T 0 T . 0 1 0

T0 is not unique for the translation to make two parallel lines align.

Chapter 2. Systems of Linear Equations 3.8. Show that if the equation Ax = 0 has unique solution (i.e. if echelon form of A has pivot in every column), then A is left invertible. Proof Ax = 0 has unique solution, then the solution is trivial solution. The echelon form of A has pivot at every column. A is m × n matrix, then m ≥ n. The row number is greater or equal to the column number. The reduced echelon form of A is denoted as   In×n . Are = 0(m−n)×n And suppose Are is obtained by a sequence of elementary row operation E1 , E2 , ..., Ek , Are = Ek ... E2 E1 A Ei is m × m. The left inverse of A is the first n rows of the product of Ei . i.e. Elef t = In×m Ek ... E2 E1 , where In×m

 1 0 0 0 1 0  =  .. .. .. . . . 0 0 ...

... ... .. . 1

 0 0  ...  

...

,

n×m

is used to extract the In×n identity matrix in Are . Elef tA = I so A is left invertible. 5.5. Let vectors u, v, w be a basis in V . Show that u + v + w, u + v, w is also a basis in V . Solution For any vector x ∈ V , suppose x = x1 u + x2 v + x3 w. Then it is easy to figure out the x = x1 (u + v + w)+(x2 − x1 )(v + w)+(x3 −x2 − x1 )w. Thus u + v + w, u + v, w is also a basis in V . 7.4. Prove that if A : X → Y and V is a subspace of X then dim AV ≤ rank A. (AV here means the subspace V transformed by the transformation A, i.e., any vector in AV can be represented as Av, v ∈ V ). Deduce from here that rank(AB) ≤ rankA. 6

Proof dimAV ≤ dimAX ≤ dim RanA = rankA Suppose that the column vectors of B compose a basis of space V . Then rank(AB) ≤ rankA. 7.5. Prove that if A : X → Y and V is a subspace of X then dim AV ≤ dim V . Deduce from here that rank(AB) ≤ rank B . Proof Suppose dim V = k and let v1 , v2 , ..., vk be a basis of V . AV is defined by Av1 , Av2 , ..., Avk . dim AV = rank [Av1 , Av2 , ..., Avk ] ≤ k = dim V . Similarly, assume rank B = k and b1 , b2 , ..., bk are linearly independent column vectors in B. Then rank AB = rank [Ab1 , Ab2 , ..., Abk ] ≤ k = rank B. 7.6. Prove that if the product AB of two n × n matrices is invertible, then both A and B are invertible. Do not use determinant for this problem. Proof AB is invertible, rank(AB) = n. From Problem 7.5, we have rank(AB) = n 6 rank(A) 6 n. Thus rank(A) = n. So is B. A, B have full rank and are invertible. 7.7. Prove that if Ax = 0 has unique solution, then the equation AT x = b has a solution for every right side b. (Hint: count pivots) Proof Suppose A ∈ Rm × Rn . Note that for Ax = 0, there is always a trivial solution x = 0 ∈ Rn . And we know the trivial solution is unique, which also indicates that the echelon form of A has a pivot at every column. Accordingly, the echelon form of AT has a pivot at every row (Think that the echelon form of AT is completed by column reduction that corresponds to the row reduction of A). So Ax = b is consistent for any b. 7.14. Is it possible for a real matrix A that Ran A = Ker AT ? Is it possible for a complex A? Solution Both are not possible. Suppose A is m × n and Ran A = Ker AT . Then Ran A ⊂ Ker AT , i.e., AT Av = 0 for any v ∈ Rn . This holds only when AT A = 0n×n . Then A = 0m×n . (Use the row vectors of AT and check the diagonal entries of AT A equal to 0. It will lead to the conclusion that the row vectors are all zero vector.) On the other hand, if Ran A = Ker AT , Ker AT ⊂ Ran A. i.e., if T A b = 0, then the function Ax = b has a solution. But we have A = 0m×n , then for arbitrary b ∈ Rm , AT b = 0 holds. But for b 6= 0, Ax = b does not have a solution. This is contradictory. So it is not possible for the real or complex matrix A that Ran A = Ker AT . 8.5. Prove that if A and B are similar matrices then trace A = trace B. (Hint: recall how trace(XY ) and trace(Y X ) are related.) Proof trace(A) = trace(Q−1 BQ) = trace(Q−1 QB) = trace(B). (Note that 7

trace(AB) = trace(BA) as long as AB, BA can be performed.)

Chapter 3. Determinants 3.4. A square matrix (n × n) is called skew-symmetric (or antisymmetric) if AT = A. Prove that if A is skew-symmetric and n is odd, then det A = 0. Is this true for even n? Proof det A = det AT = det(−A) = (−1)n det A by using the the properties of determinant and skew-symmetric matrices. If n is odd, (−1)n = −1, we have det A = − det A, thus det A = 0. If n is even, we just have det A = det A so this conclusion generally is not true. 3.5. A square matrix is called nilpotent if Ak = 0 for some positive integer k. Show that for a nilpotent matrix A, det A = 0. Proof det Ak = (det A)k = det 0 = 0, thus det A = 0. 3.6. Prove that if A and B are similar, then det A = det B . proof A and B are similar, then A = Q−1 BQ for an invertible matrix Q. Then det A = det Q−1 BQ = (det Q−1 )(det B)(det Q) = (det Q−1 )(det Q)(det B ) = (det Q−1 Q)(det B ) = (det I)(det B ) = det B. 3.7. A real square matrix Q is called orthogonal if QT Q = I. Prove that if Q is an orthogonal matrix then det Q = ±1. Proof det QT Q = (det QT )(det Q) = (det Q)2 = det I = 1. Thus det Q = ±1. 3.9. Let points A, B and C in the plane R2 have coordinates (x1 , y1 ), (x2 , y2 ) and (x3 , y3 ) respectively. Show that the area of triangle ABC is the absolute value of   1 x1 y1   1 1 x2 y2  .  2 1 x3 y3 

Hint: use row operation and geometric interpretation of 2 × 2 determinants (area). Proof The area of triangle ABC is half of the parallelogram defined by 8

neighbouring sides AB, AC. which also can be computed by   1 x2 − x1 y2 − y1 S△ABC =  2 x3 − x1 y3 − y1  1 = |(x2 − x1 )(y3 − y1 ) − (x3 − x1 )(y2 − y1 )|, 2 In the same  1 1  1 2  1

time, if we use row reduction to check the determinant     1 x1 y1  x y 1 1  1   x2 y2  = 0 x2 − x1 y2 − y1  2 x3 y3  0 x3 − x1 y3 − y1     1 x1 y1  .  1  y2 − y1 = 0 x2 − x1  2 1  0 0 y3 − y1 − (y2 − y1 ) xx32−x −x1 1 = ((x2 − x1 )(y3 − y1 ) − (x3 − x1 )(y2 − y1 )), 2

We assume that x2 − x1 6= 0 and it can be verified if x2 − x1 = 0, the result still holds. Thus we can see the conclusion holds. 3.10. Let A be a square matrix. Show that block triangular matrices         A ∗ I 0 A 0 I ∗ 0 A 0 I ∗ A ∗ I all have determinant equal to det A. Here ∗ can be anything. Proof Considering performing row reduction to make A be triangular, the whole matrix will also be triangular and the rest part on the diagonal is just I. Thus the determinant of the block matrix equals to det A. (Problem 3.11 and 3.12 are just applications of the conclusion of Problem 3.10. The hint just tells the answer.) 4.2. Let P be a permutation matrix, i.e., an n × n matrix consisting of zeros and ones and such that there is exactly one 1 in every row and every column. a) Can you describe the corresponding linear transformation? That will explain the name. b) Show that P is invertible. Can you describe P −1 ? c) Show that for some N > 0 P N := |P P{z... P} = I. N times

9

Use the fact that there are only finitely many permutations. Solution a) Consider the linear transformation y = P x and each row of P . There is only one 1 in each row of P . Suppose in the first row of P , P1,j = 1, then y1 = p1 x = xj , where p1 is the first row of P . Namely xj is moved to the 1st place after the linear transformation. Similarly, for the 2nd row of P , suppose P2,k = 1, then y2 = xk , xk is moved to the 2nd place, so on and so forth. There is also only 1 for each column, then we know after multiplying by the permutation matrix P , the elements in x change their order. b) Suppose P is invertible, by multiplying P −1 , x = P −1 y. But we know −1 y1 = xj , then we have Pj,1 = 1 so that xj can return to its original position. −1 = 1. Following this we can see that P −1 Similarly, y2 = xk , then P k,2 i,j = Pj,i −1 if Pj,i = 1 and the rest are all 0. So we can see P is invertible and P = P T . c) Note that P x, P 2 x, P 3 x ... P N x are all permutations of (x1 , x2 , ..., xn ). If P N can never equal to I, P x, P 2 x, P 3 x ... P N x will be different permutations. And N can be infinitely big, so there will be infinitely many permutations of (x1 , x2 , ..., xn ), which is impossible. Thus there must be some N > 0, P N = I. Exercises Prat 5 and Part 7 in this chapter are normal. So I try to give some ideas and answers for reference: • Problem 5.3, we can use the last column expansion and the left matrix (A + tI)i,j is a triangular matrix. The final expression is det(A + tI) = a0 + a1 t + a2 t2 + ... + an−1 tn−1 . The order of −1 in each term is even. • Problem 5.7, n! multiplications is needed. We can use induction to prove it. • Problem 7.4 and Problem 7.5, consider det RA = (det R)(det A) = det A, where R is the rotation matrix with its determinant equal to 1. For proof of the parallelogram area, we can also use parameter angle, i.e., v1 = [x1 , y1 ]T = [v1 cos α, v1 sin α]T , v2 = [x2 , y2 ]T = [v2 cos β, v2 sin β ]T . v1 , v2 are the lengths of v1 , v2 , respectively. α, β represents the angle between the vector and x-axis positive direction. Then    x x2  = x1 y2 − x2 y1 det A =  1 y1 y2  = v1 v2 (cos α sin β − cos β sin α) = v1 v2 sin(β − α). β − α is the angle from v1 to v2 .

10

Chapter 4. Introduction to Spectral Theory (Eigenvalues and Eigenvectors) 1.1. (Part) True or false: b) If a matrix has one eigenvector, it has infinitely many eigenvectors; True, if Ax = λx, A(αx) = λ(αx), α is an arbitrary scalar. c) There exists a square matrix with no real eigenvalues; True, like the 2D rotation matrix Rα, α 6= nπ. d) There exists a square matrix with no (complex) eigenvectors; False, when discussing in complex space, there are always eigenvalues and as a result A − λI has nonempty null space. f) Similar matrices always have the same eigenvectors; False, if A, B are similar and A = SBS −1 . If Ax = λx, then SBS −1 x = λx. i.e., B(S −1 x) = λ(S −1 x), S −1 x is an eigenvector of B, not x. g) The sum of two eigenvectors of a matrix A is always an eigenvector; False 1.6. An operator A is called nilpotent if Ak = 0 for some K. Prove that if A is nilpotent, then σ(A) = {0} (i.e. that 0 is the only eigenvalue of A). Proof Note that if λ is a nonzero eigenvalue of A and Ax = λx. Then A2 x = A(λx) = λ2 x, A3 x = A(λ2 x) = λ3 x ... Ak x = λk x. That is to say if λ ∈ σ(A), λk ∈ σ(Ak ). Now Ak = 0, σ(Ak ) = {0}. Then 0 is the only eigenvalue of A. 1.8. Let v1 , v2 , ..., vn be a basis in a vector space V . Assume also that the first k vectors v1 , v2 , ..., vk of the basis are eigenvectors of an operator A, corresponding to an eigenvalue λ (i.e. that Avj = λvj , j = 1, 2, ..., k). Show that in this basis the matrix of the operator A has block triangular form   λIk ∗ 0 B Proof AV V = [I]V S ASS [I ]SV , where S represents the standard basis. [I ] is the coordinate change matrix and [I]SV = [vT1 , v2T, ..., vnT]. [I]SV AV V = T T T T T ASS [I]SV = ASS [v1T , vT 2 , ..., v n ] = [λv1 , λv2 , ..., λvk , ..., ASS vn ]. Denote the i-th column of AV V with ai . Consider a1 , then [I]SV a1 = λvT1 . Since v1 , v2 , ..., vn is a basis, then a1 can only be the form a1 = [λ, 0, 0, ..., 0]T . Similarly, check the first k columns of AV V , they are λ times the first k standard base vector. So ASS has the block triangular form above. 1.9. Use the two previous exercises to prove that geometric multiplicity 11

of an eigenvalue cannot exceed its algebraic multiplicity. Proof We consider the problem in the basis v1 , v2 , ..., vn and A has the block triangular form shown in Problem 1.8. Note k is the number of linearly independent eigenvectors corresponding to λk , which is also the dimension of Ker(A − λk I) (consider the queation (A − λk I)x = 0). Namely, k is the geometric multiplicity of λk . For the algebraic multiplicity, conside...