18.06 Linear Algebra, Problem Set 3 Solutions

18.06 PSET 3 SOLUTIONS FEBRUARY 22, 2010 Problem 1. (§3.2, #18) The plane x − 3y − z = 12 is parallel to the plane x − 3y − z = 0 in Problem 17. One particular point on this plane is (12, 0, 0). All points on the plane have the form (fill in the first components)         x y  = 0 + y 1 + z 0 . z 0 0 1 Solution. (4 points) The equation x = 12 + 3y + z says it all:           x 12 + 3y + z 12 3 1 y  =   =  0  + y  1  + z  0  . y z z 0 0 1 � Problem 2. (§3.2, #24) (If possible. . . ) Construct a matrix whose column space contains (1, 1, 0) and (0, 1, 1) and whose nullspace contains (1, 0, 1) and (0, 0, 1). Solution. (4 points) Not possible : Such a matrix A must be 3 × 3. Since the nullspace is supposed to contain two independent vectors, A can have at most 3 − 2 = 1 pivots. Since the column space is supposed to contain two independent vectors, A must have at least 2 pivots. These conditions cannot both be met! �   A Problem 3. (§3.2, #36) How is the nullspace N(C) related to the spaces N(A) and N(B), if C = ? B Solution. (12 points) N(C) = N(A) ∩ N(B) just the intersection: Indeed,   Ax Cx = Bx so that Cx = 0 if and only if Ax = 0 and Bx = 0. (...and as a nitpick, it wouldn’t be quite sloppy instead write “if and only if Ax = Bx = 0”—those are zero vectors of potentially different length, hardly equal). � Problem 4. (§3.2, #37) Kirchoff’s Law says that current in = current out at every node. This network has six currents y1 , . . . , y6 (the arrows show the positive direction, each yi could be positive or negative). Find the four equations Ay = 0 for Kirchoff’s Law at the four nodes. Find three special solutions in the nullspace of A. Solution. (12 points) The four equations are, in order by node, y1 − y3 + y4 = 0 −y1 + y2 + y5 = 0 −y2 + y3 + y6 = 0 −y4 − y5 − y6 = 0 1 or in matrix form Ay = 0 for  1 0−1 −1 1 A= 0 −1 0 0 1 0 1 0  0 0 0 1 0  0 0 1 −1 −1 −1 Adding the last three rows to the first eliminates it, and shows that we have three “pivot variables” y1 , y2 , y4 and three “free variables” y3 , y5 , y6 . We find the special solutions by back-substitution from (y3 , y5 , y6 ) = (1, 0, 0), (0, 1, 0), (0, 0, 1):         1 1 y1 1 1  0   1   y2                 y3    = 1 ,  0  ,  0  � 0 −1 −1  y4          0  1   0   y5  0 0 y6 1 Problem 5. (§3.3, #19) Suppose A and B are n by n matrices, and AB = I. Prove from rank(AB) ≤ rank(A) that the rank of A is n. So A is invertible and B must be its two-sided inverse (Section 2.5). Therefore BA = I (which is not so obvious!). Solution. (4 points) Since A is n by n, rank(A) ≤ n and conversely n = rank(In ) = rank(AB) ≤ rank(A). The rest of the problem statement seems to be “commentary,” and not further things to do. � Problem 6. (§3.3, #25) Neat fact Every m by n matrix of rank r reduces to (m by r) times (r by n): A = (pivot columns of A) (first r rows of R)) = (COL) (ROW) . Write the 3 by 4 matrix A in equation (1) at the start of this section as the product of the 3 by 2 matrix from the pivot columns and the 2 by 4 matrix from R. Solution. (4 points)  1 1 A = 1 2 1 3 2 2 2   4 1 5 = 1 6 1  1  1 2 0 3 0 1 2 3 0 1  � Problem 7. (§3.3, #27) Suppose R is m by n of rank r, with pivot columns first:   I F 0 0 (a) What are the shapes of those four blocks? (b) Find a right-inverse B with RB = I if r = m. (c) Find a left-inverse C with CR = I if r = n. (d) What is the reduced row echelon form of RT (with shapes)? (e) What is the reduced row echelon form of RT R (with shapes)? Prove that RT R has the same nullspace as R. Later we show that AT A always has the same nullspace as A (a valuable fact). Solution. (12 points) (a)  r×r (m − r) × r r × (n − r) (m − r) × (n − r) 2  (b) In this case  R= I F  so we can take B=  Ir×r 0(n−r)×r  (c) In this case (d) Note that  I T R = r×r FT  R= I 0   C = Ir×r so we can take 0r×(m−r) 0(n−r)×(m−r)  T so that rref (R ) =  0r×(m−r)  Ir×r 0r×(m−r) 0(n−r)×r 0(n−r)×(m−r)  (e) Note that  I R R = r×r FT T F 0  so that T rref (R R) =  Ir×r Fr×(n−r) 0(m−r)×r 0(m−r)×(n−r)  =R Performing row operations doesn’t change the nullspace, so that N(A) = N(rref (A)) for any matrix A. So, N(A) = N(RT R) by (e). � Problem 8. (§3.3, #28) Suppose you allow elementary column operations on A as well as elementary row operations (which get to R). What is the “row-and-column reduced form” for an m by n matrix of rank r? Solution. (12 points) After getting to R we can use the column operations to get rid of F , and get to   Ir×r 0r×(n−r) 0(m−r)×r 0(m−r)×(n−r) � Problem 9. (§3.3, #17 – Optional) (a) Suppose column j of B is a combination of previous columns of B. Show that column j of AB is the same combination of previous columnd of AB. Then AB cannot have new pivot columns, so rank(AB) ≤ rank(B).   1 1 (b) Find A1 and A2 so that rank(A1 B) = 1 and rank(A2 B) = 0 for B = . 1 1 Solution. (Optional) (a) That column j of B is a combination of previous columns of B means precisely that there exist numbers a1 , . . . , aj−1 so that each row vector x = (xi ) of B satisfies the linear relation xj = j−1 X i=1 ai xi = a1 x1 + · · · + aj−1 xj−1 The rows of the matrix AB are all linear combinations of the rows of B, and so also satisfy this linear relation. So, column j is the same combination of previous columns of AB, as desired. Since a column is pivot column precisely when it is not a combination of previous columns, this shows that AB cannot have previous columns and the rank inequality.   1 −1 (b) Take A1 = I2 and A2 = 02 (or for a less trivial example A2 = ). � 1 −1 Problem 10. (§3.4, #13) Explain why these are all false: (a) The complete solution is any linear combination of xp and xn . (b) A system Ax = b has at most one particular solution. (c) The solution xp with all free variables zero is the shortest solution (minimum length kxk). Find a 2 by 2 counterexample. (d) If A is invertible there is no solution xn in the nullspace. 3 Solution. (4 points) (a) The coefficient of xp must be one. (b) If xn ∈ N(A) is in the nullspace of A and xp is one particular solution, then xp + xn is also a particular solution. (c) Lots of counterexamples are possible. Let’s talk about the 2 by 2 case geometrically: If A is a 2 by 2 matrix of rank 1, then the solutions to Ax = b form a line parallel to the line that is the nullspace. We’re asking that this line’s closest point to the origin be somewhere not along an axis. The line x + y = 1 gives such an example. Explicitly, let       1 1 1 A= b= and xp = 12 12 1 1 1 √ Then, kxp k = 1/ 2 < 1 while the particular solutions having some coordinate equal to zero are (1, 0) and (0, 1) and they both have k · k = 1. (d) There’s always xn = 0. � Problem 11. (§3.4, #25) Write down all known relations between r and m and n if Ax = b has (a) no solution for some b (b) infinitely many solutions for every b (c) exactly one solution for some b, no solution for other b (d) exactly one solution for every b. Solution. (4 points) (a) (b) (c) (d) The The The The system system system system has has has has less than full row rank: r < m. full row rank, and less than full column rank: m = r < n. full column rank, and less than full row rank: n = r < m. full row and column rank (i.e., is invertible): n = r = m. � Problem 12. (§3.4, #28) Apply Gauss-Jordan elimination to U x = 0 and U x = c. Reach Rx = 0 and Rx = d:         1 2 3 0 1 2 3 5 U 0 = U c = and . 0 0 4 0 0 0 4 8 Solve Rx = 0 to find xn (its free variable is x2 = 1). Solve Rx = d to find xp (its free variable is x2 = 0). Solution. (4 points) Let me just say to whoever’s reading: The problem statement is confusing as written!! In any case, I think the desired response is:     1 2 0 0 1 2 0 −1 and 0 0 1 0 0 0 1 2 so that R=  1 0 2 0 0 1  and d=   −1 2 and   −2 xn =  1  0 and   −1 xp =  0  . 2 � Problem 13. (§3.4, #35) Suppose K is the 9 by 9 second difference matrix (2’s on the diagonal, -1’s on the diagonal above and also below). Solve the equation Kx = b = (10, . . . , 10). If you graph x1 , . . . , x9 above the points 1, . . . , 9 on the x axis, I think the nine points fall on a parabola. Solution. (12 points) Here’s some MATLAB code that should do this: 4 K = 2*eye(9) + diag(-1*ones(1,8),1) + b = 10*ones(9,1); x = K \ b diag(-1*ones(1,8),-1); It gives back that   x1 x2    x3    x4    x5  =   x6    x7    x8  x9 And for fun, the graph is indeed parabola-like:   45  80    105   120   125   120   105    80  45 130 120 110 100 90 80 70 60 50 40 1 2 3 4 5 6 7 8 9 � Problem 14. (§3.4, #36) Suppose Ax = b and Cx = b have the same (complete) solutions for every b. Is it true that A = C? Solution. (12 points) Yes . In order to check that A = C as matrices, it’s enough to check that Ay = Cy for all vectors y of the correct size (or just for the standard basis vectors, since multiplication by them “picks out the columns”). So let y be any vector of the correct size, and set b = Ay. Then y is certainly a solution to Ax = b, and so by our hypothesis must also be a solution to Cx = b; in other words, Cy = b = Ay. � 5