Solutions to Homework 4.
Math 110, Fall 2006. Prob 2.3.13. Let A = [aij ]. Then At = [aji ], and
n n
tr(A) =
i=1
aii =
j=1
ajj = tr(At ).
The elements of A = [aij ], B = [bij ], AB = [cij ] and BA = [dij ] are connected by the formulas
n n
cij =
k=1
aik bkj ,
dij =
k=1
bik akj .
So,
n n n n n n
tr(AB) =
i=1
cii =
i=1 k=1
aik bki =
i=1 k=1
bik aki =
i=1
dii = tr(BA).
The second-last equality is obtained by interchanging indices i and k. Prob 2.3.15. Suppose A has n columns {Ai : i = 1, . . . , n}, and write A = [A1 , A2 , . . . , An ]. Then M A = [M A1 , . . . , M An ], i.e., the columns of M A are column-vectors M A1 , . . . , M An . So if Aj = i=j ai Ai , then M Aj = M ( ai Ai ) = ai M Ai ,
i=j i=j
i.e., the jth column of M A is a linear combination of its other columns with the same coecients. Prob 2.3.17. For any vector x, we have x = T x + (x T x). Note that T x is in the range R(T ) of T and x T x is in the kernel N (T ), since T (x T x) = T x T 2 x = T x T x = 0. This shows that V = R(T ) + N (T ). By the Rank-Nullity theorem, we can therefore conclude that this sum is direct (see Prob. 2.1.35a). Also note that T acts as the identity on R(T ). This is in fact a characterization of all maps T with the property T 2 = T . Precisely, given a direct sum V = V1 V2 , any vector v V is decomposed uniquely into a sum v = v1 + v2 , v1 V1 , v2 V2 . By dening T v := v1 , we will obtain a linear map satisfying T 2 = T whose range is V1 , where it acts as the identity, and whose kernel is V2 . Remark: Such maps are called linear projectors. As we just saw, they are completely characterized by their range, onto which they project, and their kernel, which they annihilate. Prob 2.3.20. (a) There are no cliques in this relation. To see that, matrix B corresponding to the given incidence matrix A is 0 1 0 1 0 2 1 0 0 0 2 0 3 B= so B = 0 0 0 1 , 0 1 1 0 1 0 3 0 Since the diagonal entries of B 3 are all zero, there are no cliques. use the result of Problem 19. The 0 1 0 2 3 0 . 2 0
(b) The clique consists of vertices 0 0 B= 1 1
1, 3 and 4. To see this, use the same method to obtain 2 0 3 3 0 1 1 0 0 0 0 0 0 0 , B3 = 3 0 2 3 . 0 0 1 3 0 3 2 0 1 0
Remark: Alternatively, these conclusions could be reached by simply drawing the graphs. Prob 2.4.1. (a) False. The bases and must be interchanged, i.e., ([T ] )1 = [T 1 ] . (b) True. (c) False. Recall the diagram in class. T maps V to W , whereas LA maps IFn to IFm where n is the dimension of V and m is the dimension of W . So, LA is not the same map even though LA represents T . (d) False. The dimensions do not match. (e) True, since thats when the dimensions match. (f) False. Take, for example, 1 0 1 0 0 A= , B = 0 1 . 0 1 0 0 0 (g) True. (h) True. (i) True. Prob 2.4.2. (a) No, the dimensions of the domain and the target do not match. (b) No. Same reason as in (a). (c) Yes, the inverse is given by T 1 (b1 , b2 , b3 ) = ((b3 4b2 )/3, b2 , (b3 b1 4b2 )/2). Alternatively, it is easy to check that the kernel of T is trivial, i.e., T is 1 1. Since the dimensions of the domain and the target match, this implies that T is onto as well, hence is invertible. (d) No. Same as in (a). (e) No. Same as in (a). (f) Yes. The dimensions agree and the kernel of T is trivial. Prob 2.4.6. If A is invertible and AB = 0, then A1 (AB) = A1 AB = B = 0. Prob 2.4.17. (a) Since V0 is closed under linear combinations and since T is linear, the image T (V0 ) of V0 is also close dunder linear combinations. (Note that we did not use the fact that T is an isomorphism here, only that it is a linear map.) (b) Let = {u1 , . . . , un } be a basis for V0 . Let us show that T = {T u1 , . . . , T un } is a basis for T (V0 ). We already know T spans T (V0 ), so we just need to check that the set T is linearly independent. Indeed, since T is an isomorphism, its kernel is trivial, hence no nontrivi Prob 2.4.22. The dimensions of Pn (IF) and IFn+1 match, so it is enough to prove that the kernel of T is trivial. Use the Lagrange polynomials fj (x), j = 0, . . . , n, associated with c0 , c1 , . . . , cn . By the Lagrange interpolation formula, any polynomial f can be represented in the form
n
f (x) =
j=0
f (cj )fj (x).
So, if f (cj ) = 0 for all j = 0, . . . , n, this implies f = 0. Thus N (T ) = {0} and we are done.
