18.06 Linear Algebra, Problem Set 4 Solutions

18.06 Problem Set 4 Solution Total: 100 points Section 3.5. Problem 2: (Recommended) Find the largest possible number of independent vectors among ⎡ ⎤ 1 ⎢−1⎥ ⎥ v1 = ⎢ ⎣0⎦ 0 ⎡ ⎤ 1 ⎢0⎥ ⎥ v2 = ⎢ ⎣−1⎦ 0 ⎡ ⎤ 1 ⎢0⎥ ⎥ v3 = ⎢ ⎣0⎦ −1 ⎡ ⎤ )0 ⎢1⎥ ⎥ v4 = ⎢ ⎣−1⎦ 0 ⎡ ⎤ )0 ⎢1⎥ ⎥ v5 = ⎢ ⎣0⎦ −1 ⎡ ⎤ )0 ⎢0⎥ ⎥ v6 = ⎢ ⎣ 1 ⎦. −1 Solution (4 points): Since v4 = v2 − v1 , v5 = v3 − v1 , and v6 = v3 − v2 , there are at most three independent vectors among these: furthermore, applying row reduction to the matrix [v1 v2 v3 ] gives three pivots, showing that v1 , v2 , and v3 are independent. Section 3.5. Problem 20: Find a basis for the plane x − 2y + 3z = 0 in R3 . Then find a basis for the intersection of that plane with the xy plane. Then find a basis for all vectors perpendicular to the plane. Solution (4 points): This plane is the nullspace of the matrix ⎡ ⎤ 1 −2 3 A = ⎣0 0 0⎦ 0 0 0 The special solutions ⎡ ⎤ 2 ⎣ v1 = 1⎦ 0 ⎡ ⎤ −3 v2 = ⎣ 0 ⎦ 1 give a basis for the nullspace, and thus for the plane. The intersection of this plane with the xy plane is a line: since the first vector lies in the xy plane, it must lie on the line and thus gives a basis for it. Finally, the vector ⎡ ⎤ 1 v3 = ⎣−2⎦ 3 is obviously perpendicular to both vectors: since the space of vectors perpendicular to a plane in R3 is one-dimensional, it gives a basis. Section 3.5. Problem 37: If AS = SA for the shift matrix S, show that A must have this special form: ⎡ ⎤⎡ ⎤ ⎡ ⎤⎡ ⎤ ⎡ ⎤ a b c 0 1 0 0 1 0 a b c a b c If ⎣d e f ⎦ ⎣0 0 1⎦ = ⎣0 0 1⎦ ⎣d e f ⎦ , then A = ⎣0 a b ⎦ g h i 0 0 0 0 0 0 g h i 0 0 ai “The subspace of matrices that commute with the shift S has dimension .” Solution (4 points): Multiplying out both ⎡ 0 a ⎣0 d 0 g sides gives ⎤ ⎡ ⎤ b d e f e ⎦ = ⎣g h i ⎦ h 0 0 0 Equating them gives d = g = h = 0, e = i = a, f = b, i.e. the matrix with the form above. Since there are three free variables, the subspace of these matrices has dimension 3. Section 3.5. Problem 41: Write a 3 by 3 identity matrix as a combination of the other five permutation matrices. Then show that those five matrices are linearly indpendent. (Assume a combination gives c1 P1 + · · · + c5 P5 = 0, and check entries to prove ci is zero.) The five permutation matrices are a basis for the subspace of 3 by 3 matrices with row and column sums all equal. Solution (12 points): The other ⎡ ⎤ ⎡ 1 ⎦ , P31 = ⎣ 1 P21 = ⎣1 1 1 five permutation matrices are ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ 1 1 1 ⎦ , P32 = ⎣ 1⎦ , P32 P21 = ⎣ 1⎦ , P21 P32 = ⎣1 1 1 1 ⎤ ⎦ 1 Since P21 + P31 + P32 is the all 1s matrix and P32 P21 + P21 P32 is the matrix with 0s on the diagonal and 1s elsewhere, I = P21 + P31 + P32 − P32 P21 − P21 P32 . For the second part, the combination above gives ⎡ ⎤ c3 c1 + c4 c2 + c5 ⎣c1 + c5 c2 c3 + c4 ⎦ = 0 c2 + c4 c3 + c5 c1 Setting each element equal to 0 first gives c1 = c2 = c3 = 0 along the diagonal, then c4 = c5 = 0 on the off-diagonal entries. Section 3.5. Problem 44: (An aside in the text, followed by) dimension of outputs + dimension of nullspace = dimension of inputs. For an m by n matrix of rank r, what are those 3 dimensions? Outputs = column space. This question wil be answered in Section 3.6, can you do it now? Solution (12 points): You should think about the aside in the text, as well as problem 43: the actual question asked, here, however is quite simple. The dimension of inputs for an m by n matrix is n (the matrix takes n-vectors to m-vectors), while the dimension of the nullspace is n − r and the dimension of outputs = dimension of column space is r. Since n − r + r = n, we have the given relation. Section 3.6. Problem 11: A is an m by n matrix of rank r. Suppose there are right sides b for which Ax = b has no solution. (a) What are all the inequalities (< or ≤) that must be true between m, n, and r? (b) How do you know that AT y = 0 has solutions other than y = 0? Solution (4 points): (a) The rank of a matrix is always less than or equal to the number of rows and columns, so r ≤ m and r ≤ n. Moreover, by the second statement, the column space is smaller than the space of possible output matrices, i.e. r < m. (b) These solutions make up the left nullspace, which has dimension m − r > 0 (that is, there are nonzero vectors in it). Section 3.6. Problem 24: AT y = d is solvable when d is in which of the four subspaces? The solution is unique when the contains only the zero vector. Solution (4 points): It is solvable when d is in the row space, which consists of all vectors AT y, and is unique when the left nullspace contains only the zero vector (as any two solutions differ by an element in the left nullspace). Section 3.6. Problem matrix C: ⎡ 1 0 ⎢0 1 ⎢ ⎢1 0 ⎢ ⎢0 1 B=⎢ ⎢1 0 ⎢ ⎢0 1 ⎢ ⎣1 0 0 1 28: Find the ranks of the 8 by 8 checkerboard matrix B and the chess 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 ⎤ ⎡ 0 r n b q ⎥ ⎢ 1⎥ ⎢p p p p ⎢0 0 0 0 0⎥ ⎥ ⎢ ⎥ ⎢0 0 0 0 1⎥ and C = ⎢ ⎥ ⎢0 0 0 0 0⎥ ⎢ ⎥ ⎢0 0 0 0 1⎥ ⎢ ⎣p p p p 0⎦ 1 r n b q k p 0 0 0 0 p k b p 0 0 0 0 p b n p 0 0 0 0 p n ⎤ r p⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ 0⎥ ⎥ p⎦ r The numbers r, n, b, k, q, p are all different. Find bases for the rowspace and left nullspace of B and C. Challenge problem: Find a basis for the nullspace of C. Solution (4 points): In both cases, elimination kills all but the top two rows, so, if p �= 0, both matrices have rank 2 as well as rowspace bases given by the top two rows (or course, if p = 0, C has rank 1 with rowspace generated by the top row). B is symmetric, so its left nullspace is the same as the nullspace, and the special solutions are: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −1 −1 −1 0 0 0 ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢−1⎥ ⎢−1⎥ ⎢−1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ v1 = ⎢ ⎥ , v2 = ⎢ ⎥ , v3 = ⎢ ⎥ , v4 = ⎢ ⎥ , v5 = ⎢ ⎥ , v6 = ⎢ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣0⎦ ⎣1⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ 0 0 0 0 0 1 Finally, the nullspace of C T is given by ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −1 0 0 0 0 0 ⎢0⎥ ⎢−1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ w1 = ⎢ ⎥ , w2 = ⎢ ⎥ , w3 = ⎢ ⎥ , w4 = ⎢ ⎥ , w5 = ⎢ ⎥ , w6 = ⎢ ⎢0⎥ 0 0 0 0 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣1⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ 1 0 0 0 0 0 if p �= 0, and ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −1 0 0 0 0 0 0 ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ w1 = ⎢ ⎥ , w2 = ⎢ ⎥ , w3 = ⎢ ⎥ , w4 = ⎢ ⎥ , w5 = ⎢ ⎥ , w6 = ⎢ ⎥ , w7 = ⎢ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣1⎦ 1 0 0 0 0 0 0 if p = 0. Solution (12 points): (Challenge subpart) There are three obvious special solutions of C: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ −1 0 0 ⎢0⎥ ⎢−1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢−1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎥ u1 = ⎢ ⎥ , u2 = ⎢ ⎥ , u3 = ⎢ ⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢ ⎥ ⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣1⎦ ⎣0⎦ 1 0 0 If p = 0, the other solutions are similarly straightforward: ⎡ n⎤ ⎡ b⎤ ⎡ k⎤ ⎡ q⎤ −r −r −r −r ⎢ 1 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 1 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 1 ⎥ ⎢ 0 ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎥ u4 = ⎢ ⎥ , u5 = ⎢ ⎥ , u6 = ⎢ ⎥ , u7 = ⎢ ⎢ 1 ⎥ 0 0 0 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0 ⎦ ⎣ 0 ⎦ ⎣ 0 ⎦ ⎣ 0 ⎦ 0 0 0 0 Otherwise, simultaneously solving c1 r + c2 n + b = 0 and (c1 + c2 + 1)p = 0 (and similarly for q and k instead of b), we get ⎡ ⎤ ⎡ n−q ⎤ ⎡ ⎤ n−b r−n r−n n−k r−n ⎢ b−r ⎥ ⎢ q−r ⎥ ⎢ k−r ⎥ ⎢ r−n ⎥ ⎢ r−n ⎥ ⎢ r−n ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 1 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ 1 ⎥ ⎢ 0 ⎥ u4 = ⎢ ⎥ , u5 = ⎢ ⎥ , u6 = ⎢ ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0 ⎦ ⎣ 0 ⎦ ⎣ 0 ⎦ 0 0 0 Section 3.6. Problem 30: If A = uvT is a 2 by 2 matrix of rank 1, redraw Figure 3.5 to show clearly the Four Fundamental Subspaces. If B produces those same four subspaces, what is the exact relation of B to A? Solution (12 points): One draws the same diagram as in the book, but now each space has dimension 1, the column space is the set of multiples of u, the row space is the set of multiples of vT , the nullspace is the plane perpendicular to v, and the left nullspace is the plane perpendicular to u. If B = u� v� T produces the same four subspaces, u� is a multiple of u and v� is a multiple of v, i.e. B is a multiple of A. Section 3.6. Problem 31: M is the space of 3 by 3 matrices. Multiply each matrix X in M by ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ 1 0 −1 1 0 0 ⎦ . Notice: A ⎣1⎦ = ⎣0⎦ . A = ⎣−1 1 1 0 0 −1 1 (a) Which matrices X lead to AX = 0? (b) Which matrices have the form AX for some matrix X? (a) finds the “nullspace” of that operation AX and (b) finds the “column space”. What are the dimensions of those two subspaces of M? Why do the dimensions add to (n − r) + r = 9? Solution (12 points): (a) A clearly has rank 2, with nullspace having the basis [111]T . AX = 0 precisely when the columns of X are in the nullspace of A, i.e. when they are multiples of the all 1s vector. ⎡ ⎤ a b c X = ⎣a b c⎦ a b c (b) On the other hand, the columns of any matrix of the form AX are linear combinations of the columns of A. That is, they are vectors whose components all sum to 0, so a matrix has the form AX if and only if all of its columns individually sum to 0. ⎡ ⎤ a b c e f ⎦ AX = B if and only if B = ⎣ d −a − d −b − e −c − f The dimension of the “nullspace” is 3, while the dimension of the “column space” is 6. They add up to 9, which is the dimension of the space of “inputs” of this matrix, when treated as a linear map on matrices.