In Section 2.2, we learned how to associate a matrix with a linear transformation in such a way that both sums and scalar multiples of matrices are associated with the corresponding sums and scalar multiples of the transformations. The question now arises as to how the matrix representation of a composite of linear transformations is related to the matrix representation of each of the associated linear transformations. The attempt to answer this question leads to a definition of matrix multiplication. We use the more convenient notation of UT rather than U∘T
Our first result shows that the composite of linear transformations is linear.
Let V, W, and Z be vector spaces over the same field F, and let T:V→W
Proof.
Let x, y∈V
The following theorem lists some of the properties of the composition of linear transformations.
Let V be a vector space. Let T, U1, U2∈L(V)
(a) T(U1+U2)=TU1+TU2
(b) T(U1U2)=(TU1)U2
(c) TI=IT=T
(d) a(U1U2)=(aU1)U2=U1(aU2)
Proof.
Exercise.
A more general result holds for linear transformations that have domains unequal to their codomains. (See Exercise 8.)
If T∈L(V)
If T∈L(V)
We now turn our attention to the multiplication of matrices. Let V, W, and Z be finite-dimensional vector spaces and T|:V→W
where
This computation motivates the following definition of matrix multiplication.
Let A be an m×n
Note that (AB)ij
The reader should observe that in order for the product AB to be defined, there are restrictions regarding the relative sizes of A and B. The following mnemonic device is helpful: “(m×n)·(n×p)=(m×p)
We have
Notice again the symbolic relationship (2×3)·(3×1)=2×1
As in the case with composition of functions, we have that matrix multiplication is not commutative. Consider the following two products:
Hence we see that even if both of the matrix products AB and BA are defined, it need not be true that AB=BA
Recalling the definition of the transpose of a matrix from Section 1.3, we show that if A is an m×n
and
we are finished. Therefore the transpose of a product is the product of the transposes in the opposite order.
Our definition of matrix multiplication was chosen so that the next theorem is true.
Let V, W, and Z be finite-dimensional vector spaces with ordered bases α, β
Let V be a finite-dimensional vector space with an ordered basis β
We illustrate Theorem 2.11 in the next example.
Let U:P3(R)→P2(R)
Let α
The next theorem provides analogs of (a), (c), and (d) of Theorem 2.10. Theorem 2.10(b) has its analog in Theorem 2.16. Observe also that part (c) of the next theorem illustrates that the identity matrix acts as a multiplicative identity in Mn×n(F)
Let A be an m×n
(a) A(B+C)=AB+AC
(b) a(AB)=(aA)B=A(aB)
(c) ImA=A=AIn
Proof.
We prove the first half of (a) and (c) and leave the remaining proofs as an exercise. (See Exercise 5.)
(a) We have
So A(B+C)=AB+AC
(c) We have
Let A be an m×n
and
Proof.
Exercise.
For an n×n
With this notation, we see that if
then A2=O
Let A be an m×n
(a) uj=Avj
(b) vj=Bej
Proof.
(a) We have
Hence (a) is proved. The proof of (b) is left as an exercise. (See Exercise 6.)
It follows (see Exercise 14) from Theorem 2.13 that column j of AB is a linear combination of the columns of A with the coefficients in the linear combination being the entries of column j of B. An analogous result holds for rows; that is, row i of AB is a linear combination of the rows of B with the coefficients in the linear combination being the entries of row i of A.
The next result justifies much of our past work. It utilizes both the matrix representation of a linear transformation and matrix multiplication in order to evaluate the transformation at any given vector.
Let V and W be finite-dimensional vector spaces having ordered bases β
Proof.
Fix u∈V
Let T:P3(R)→P2(R)
We illustrate Theorem 2.14 by verifying that [T(p(x))]γ=[T]γβ[p(x)]β
but also
We complete this section with the introduction of the left-multiplication transformation LA
Let A be an m×n
Let
Then A∈M2×3(R)
then
We see in the next theorem that not only is LA
Let A be an m×n
(a) [LA]γβ=A
(b) LA=LB
(c) LA+B=LA+LB
(d) If T:Fn→Fm
(e) If E is an n×p
(f) If m=n
Proof.
The fact that LA
(a) The jth column of [LA]γβ
(b) If LA=LB
(c) The proof is left as an exercise. (See Exercise 7.)
(d) Let C=[T]γβ
(e) For any j(1≤j≤p)
Hence LAE=LALE
(f) The proof is left as an exercise. (See Exercise 7.)
We now use left-multiplication transformations to establish the associativity of matrix multiplication.
Let A, B, and C be matrices such that A(BC) is defined. Then (AB)C is also defined and A(BC)=(AB)C
Proof.
It is left to the reader to show that (AB)C is defined. Using (e) of Theorem 2.15 and the associativity of functional composition (see Appendix B), we have
So from (b) of Theorem 2.15, it follows that A(BC)=(AB)C
Needless to say, this theorem could be proved directly from the definition of matrix multiplication (see Exercise 19). The proof above, however, provides a prototype of many of the arguments that utilize the relationships between linear transformations and matrices.
For an application of matrix multiplication to the study of population growth, visit goo.gl/
A large and varied collection of interesting applications arises in connection with special matrices called incidence matrices. An incidence matrix is a square matrix in which all the entries are either zero or one and, for convenience, all the diagonal entries are zero. If we have a relationship on a set of n objects that we denote by 1, 2, …, n
To make things concrete, suppose that we have four people, each of whom owns a communication device. If the relationship on this group is “can transmit to,” then Aij=1
Then since A34=1
We obtain an interesting interpretation of the entries of A2. Consider, for instance,
Note that any term A3kAk1
we see that there are two ways 3 can send to 1 in two stages. In general, (A+A2+⋯+Am)ij
A maximal collection of three or more people with the property that any two can send to each other is called a clique. The problem of determining cliques is difficult, but there is a simple method for determining if someone belongs to a clique. If we define a new matrix B by Bij=1
To determine which people belong to cliques, we form the matrix B, described earlier, and compute B3
Since all the diagonal entries of B3
Our final example of the use of incidence matrices is concerned with the concept of dominance. A relation among a group of people is called a dominance relation if the associated incidence matrix A has the property that for all distinct pairs i and j, Aij=1
The reader should verify that this matrix corresponds to a dominance relation. Now
Thus persons 1, 3, 4, and 5 dominate (can send messages to) all the others in at most two stages, while persons 1, 2, 3, and 4 are dominated by (can receive messages from) all the others in at most two stages.
Label the following statements as true or false. In each part, V, W, and Z denote vector spaces with ordered (finite) bases α, β
(a) [UT]γα=[T]βα[U]γβ
(b) [T(v)]β=[T]βα[v]α
(c) [U(w)]β=[U]βα[w]β
(d) [IV]α=I
(e) [T2]βα=([T]βα)2
(f) A2=I
(g) T=LA
(h) A2=O
(i) LA+B=LA+LB
(j) If A is square and Aij=δij
(a) Let
Compute A(2B+3C), (AB)D
(b) Let
Compute At, AtB, BCt, CB
Let g(x)=3+x
Let β
(a) Compute [U]γβ, [T]β
(b) Let h(x)=3−2x+x2
For each of the following parts, let T be the linear transformation defined in the corresponding part of Exercise 5 of Section 2.2. Use Theorem 2.14 to compute the following vectors:
(a) [T(A)]α
(b) [T(f(x))]α
(c) [T(A)]γ
(d) [T(f(x))]γ
Complete the proof of Theorem 2.12 and its corollary.
Prove (b) of Theorem 2.13.
Prove (c) and (f) of Theorem 2.15.
Prove Theorem 2.10. Now state and prove a more general result involving linear transformations with domains unequal to their codomains.
Find linear transformations U, T:F2→F2
Let A be an n×n
Let V be a vector space, and let T:V→V
Let V, W, and Z be vector spaces, and let T:V→W
(a) Prove that if UT is one-to-one, then T is one-to-one. Must U also be one-to-one?
(b) Prove that if UT is onto, then U is onto. Must T also be onto?
(c) Prove that if U and T are one-to-one and onto, then UT is also.
Let A and B be n×n
Prove that tr(AB)=tr(BA)
Assume the notation in Theorem 2.13.
(a) Suppose that z is a (column) vector in Fp
(b) Extend (a) to prove that column j of AB is a linear combination of the columns of A with the coefficients in the linear combination being the entries of column j of B.
(c) For any row vector w∈Fm
(d) Prove the analogous result to (b) about rows: Row i of AB is a linear combination of the rows of B with the coefficients in the linear combination being the entries of row i of A.
† Let A and B be matrices for which the product matrix AB is defined, and let uj
Let V be a finite-dimensional vector space, and let T:V→V
(a) If rank(T)=rank(T2)
(b) Prove that V=R(Tk)⊕N(Tk)
Let β
Using only the definition of matrix multiplication, prove that, multiplication of matrices is associative.
For an incidence matrix A with related matrix B defined by Bij=1
Use Exercise 20 to determine the cliques in the relations corresponding to the following incidence matrices.
(a) (0101100001011010)
(b) (0011100110011010)
Let A be an incidence matrix that is associated with a dominance relation. Prove that the matrix A+A2
Prove that the matrix
corresponds to a dominance relation. Use Exercise 22 to determine which persons dominate [are dominated by] each of the others within two stages.
Let A be an n×n