Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

2.3 Composition of Linear Transformations and Matrix Multiplication

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 $U \circ T$ for the composite of linear transformations U and T. (See Appendix B.)

Our first result shows that the composite of linear transformations is linear.

Theorem 2.9.

Let V, W, and Z be vector spaces over the same field F, and let T:V→W $T : V \to W$ and U:W→Z $U : W \to Z$ be linear. Then UT:V→Z $UT : V \to Z$ is linear.

Proof.

Let x, y∈V $x, y \in V$ and a∈F $a \in F$ . Then

UT (a x + y) = = U (T (a x + y)) = U (a T (x) + T (y)) a U (T (x)) + U (T (y)) = a (UT) (x) + UT (y) .

$\begin{array}{l} UT (a x + y) & = & U (T (a x + y)) = U (a T (x) + T (y)) \\ = & a U (T (x)) + U (T (y)) = a (UT) (x) + UT (y) . \end{array}$

The following theorem lists some of the properties of the composition of linear transformations.

Theorem 2.10.

Let V be a vector space. Let T, U1, U2∈L(V) $T, U_{1}, U_{2} \in L (V)$ . Then

(a) T(U1+U2)=TU1+TU2 $T (U_{1} + U_{2}) = {TU}_{1} + {TU}_{2}$ and (U1+U2)T=U1T+U2T $(U_{1} + U_{2}) T = U_{1} T + U_{2} T$
(b) T(U1U2)=(TU1)U2 $T (U_{1} U_{2}) = ({TU}_{1}) U_{2}$
(c) TI=IT=T $TI = IT = T$
(d) a(U1U2)=(aU1)U2=U1(aU2) $a (U_{1} U_{2}) = (a U_{1}) U_{2} = U_{1} (a U_{2})$ for all scalars a.

Proof.

Exercise.

A more general result holds for linear transformations that have domains unequal to their codomains. (See Exercise 8.)

If T∈L(V) $T \in L (V)$ , there are circumstances where it is natural to compose T with itself one or more times. In Example 6 of Section 2.1, for instance, we considered the linear transformation T:V→V $T : V \to V$ defined by T(f)=f′ $T (f) = f^{'}$ , where V denotes the set of all real-valued functions on the real line that have derivatives of every order. In this context, TT(f)=T(f′)=(f′)′=f′′ $TT (f) = T (f^{'}) = (f^{'})^{'} = {f^{'}}^{'}$ is the second derivative of f, and TTT(f)=f′′′ $TTT (f) = {f^{'}}^{'}^{'}$ is the third derivative of f. In this type of situation, the following notation is useful.

If T∈L(V) $T \in L (V)$ , we define T1=T, T2=TT, T3=T2T $T^{1} = T, T^{2} = TT, T^{3} = T^{2} T$ , and, in general, Tk=Tk−1T $T^{k} = T^{k - 1} T$ for k=2, 3, … $k = 2, 3, \dots$ For convenience, we also define T0=IV $T^{0} = I_{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 $T | : V \to W$ and U:W→Z $U : W \to Z$ be linear transformations. Suppose that A=[U]γβ $A = {[U]}_{β}^{γ}$ and B=[T]βα $B = {[T]}_{α}^{β}$ , where α={v1, v2, …, vn}, β={w1, w2, …, wm} $α = {v_{1}, v_{2}, \dots, v_{n}}, β = {w_{1}, w_{2}, \dots, w_{m}}$ , and γ={z1, z2, …, zp} $γ = {z_{1}, z_{2}, \dots, z_{p}}$ are ordered bases for V, W, and Z, respectively. We would like to define the product AB of two matrices so that AB=[UT]γα $A B = {[UT]}_{α}^{γ}$ . Consider the matrix [UT]γα ${[UT]}_{α}^{γ}$ . For j=1, 2, …, n $j = 1, 2, \dots, n$ , we have

(UT) (v j) = U (T (v j)) = U (\sum k = 1 m B k j w k) = \sum k = 1 m B k j U (w k) = \sum k = 1 m B k j (\sum i = 1 p A i k z i) = \sum i = 1 p (\sum k = 1 m A i k B k j) z i = \sum i = 1 p C i j z i,

$\begin{array}{l} (UT) (v_{j}) & = U (T (v_{j})) = U (\sum_{k = 1}^{m} B_{k j} w_{k}) = \sum_{k = 1}^{m} B_{k j} U (w_{k}) \\ = \sum_{k = 1}^{m} B_{k j} (\sum_{i = 1}^{p} A_{i k} z_{i}) = \sum_{i = 1}^{p} (\sum_{k = 1}^{m} A_{i k} B_{k j}) z_{i} \\ = \sum_{i = 1}^{p} C_{i j} z_{i}, \end{array}$

where

C i j = \sum k = 1 m A i k B k j .

$C_{i j} = \sum_{k = 1}^{m} A_{i k} B_{k j} .$

This computation motivates the following definition of matrix multiplication.

Definition.

Let A be an m×n $m \times n$ matrix and B be an n×p $n \times p$ matrix. We define the product of A and B, denoted AB, to be the m×p $m \times p$ matrix such that

(A B) i j = \sum k = 1 n A i k B k j for 1 \leq i \leq m, 1 \leq j \leq p .

${(A B)}_{i j} = \sum_{k = 1}^{n} A_{i k} B_{k j} for 1 \leq i \leq m, 1 \leq j \leq p .$

Note that (AB)ij ${(A B)}_{i j}$ is the sum of products of corresponding entries from the ith row of A and the jth column of B. Some interesting applications of this definition are presented at the end of this section.

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) $(m \times n) \cdot (n \times p) = (m \times p)$ ”; that is, in order for the product AB to be defined, the two “inner” dimensions must be equal, and the two “outer” dimensions yield the size of the product.

Example 1

We have

(1024 1 - 1) ⎛ ⎝ ⎜ 425 ⎞ ⎠ ⎟ = (1.4 + 2.2 + 1.5 0.4 + 4.2 + (- 1) .5) = (133) .

$(\begin{array}{r} 1 & 2 & 1 \\ 0 & 4 & - 1 \end{array}) (\begin{matrix} 4 \\ 2 \\ 5 \end{matrix}) = (\begin{matrix} 1.4 + 2.2 + 1.5 \\ 0.4 + 4.2 + (- 1) .5 \end{matrix}) = (\begin{matrix} 13 \\ 3 \end{matrix}) .$

Notice again the symbolic relationship (2×3)⋅(3×1)=2×1 $(2 \times 3) \cdot (3 \times 1) = 2 \times 1$ .

As in the case with composition of functions, we have that matrix multiplication is not commutative. Consider the following two products:

(1010) (0110) = (1010) and (0110) (1010) = (0101) .

$(\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) and (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 1 & 1 \end{matrix}) .$

Hence we see that even if both of the matrix products AB and BA are defined, it need not be true that AB=BA $A B = B A$ .

Recalling the definition of the transpose of a matrix from Section 1.3, we show that if A is an m×n $m \times n$ matrix and B is an n×p $n \times p$ matrix, then (AB)t=BtAt ${(A B)}^{t} = B^{t} A^{t}$ . Since

(A B) t i j = (A B) j i = \sum k = 1 n A j k B k i

${(A B)}_{i j}^{t} = {(A B)}_{j i} = \sum_{k = 1}^{n} A_{j k} B_{k i}$

and

(B t A t) i j = \sum k = 1 n (B t) i k (A t) k j = \sum k = 1 n B k i A j k,

${(B^{t} A^{t})}_{i j} = \sum_{k = 1}^{n} {(B^{t})}_{i k} {(A^{t})}_{k j} = \sum_{k = 1}^{n} B_{k i} A_{j k},$

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.

Theorem 2.11.

Let V, W, and Z be finite-dimensional vector spaces with ordered bases α, β $α, β$ , and γ $γ$ , respectively. Let T:V→W $T : V \to W$ and U:W→Z $U : W \to Z$ be linear transformations. Then

[UT] γ α = [U] γ β [T] β α .

${[UT]}_{α}^{γ} = {[U]}_{β}^{γ} {[T]}_{α}^{β} .$

Corollary.

Let V be a finite-dimensional vector space with an ordered basis β $β$ . Let T, U∈L(V) $T, U \in L (V)$ . Then [UT]β=[U]β[T]β ${[UT]}_{β} = {[U]}_{β} {[T]}_{β}$ .

We illustrate Theorem 2.11 in the next example.

Example 2

Let U:P3(R)→P2(R) $U : P_{3} (R) \to P_{2} (R)$ and T:P2(R)→P3(R) $T : P_{2} (R) \to P_{3} (R)$ be the linear transformations respectively defined by

U (f (x)) = f' (x) and T (f (x)) = \int 0 x f (t) d t .

$U (f (x)) = f^{'} (x) and T (f (x)) = \int_{0}^{x} f (t) d t .$

Let α $α$ and β $β$ be the standard ordered bases of P3(R) $P_{3} (R)$ and P2(R) $P_{2} (R)$ , respectively. From calculus, it follows that UT=I $UT = I$ , the identity transformation on P2(R) $P_{2} (R)$ . To illustrate Theorem 2.11, observe that

[UT] β = [U] β α [T] α β = ⎛ ⎝ ⎜ 000100020003 ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 0100 00 1 2 0 000 1 3 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ 100010001 ⎞ ⎠ ⎟ = [I] β .

${[UT]}_{β} = {[U]}_{α}^{β} {[T]}_{β}^{α} = (\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{matrix}) (\begin{matrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{3} \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) = {[I]}_{β} .$

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) $M_{n \times n} (F)$ . When the context is clear, we sometimes omit the subscript n from In $I_{n}$ .

Theorem 2.12.

Let A be an m×n $m \times n$ matrix, B and C be n×p $n \times p$ matrices, and D and E be q×m $q \times m$ matrices. Then

(a) A(B+C)=AB+AC $A (B + C) = A B + A C$ and (D+E)A=DA+EA $(D + E) A = D A + E A$ .
(b) a(AB)=(aA)B=A(aB) $a (A B) = (a A) B = A (a B)$ for any scalar a.
(c) ImA=A=AIn $I_{m} A = A = A I_{n}$ .

Proof.

We prove the first half of (a) and (c) and leave the remaining proofs as an exercise. (See Exercise 5.)

(a) We have

[A (B + C)] i j = \sum k = 1 n A i k (B + C) k j = \sum k = 1 n A i k (B k j + C k j) = \sum k = 1 n (A i k B k j + A i k C k j) = \sum k = 1 n A i k B k j + \sum k = 1 n A i k C k j = (A B) i j + (A C) i j = [A B + A C] i j .

$\begin{array}{l} {[A (B + C)]}_{i j} & = \sum_{k = 1}^{n} A_{i k} {(B + C)}_{k j} = \sum_{k = 1}^{n} A_{i k} (B_{k j} + C_{k j}) \\ = \sum_{k = 1}^{n} (A_{i k} B_{k j} + A_{i k} C_{k j}) = \sum_{k = 1}^{n} A_{i k} B_{k j} + \sum_{k = 1}^{n} A_{i k} C_{k j} \\ = {(A B)}_{i j} + {(A C)}_{i j} = {[A B + A C]}_{i j} . \end{array}$

So A(B+C)=AB+AC $A (B + C) = A B + A C$ .

(I m A) i j = \sum k = 1 m (I m) i k A k j = \sum k = 1 m δ i k A k j = A i j .

${(I_{m} A)}_{i j} = \sum_{k = 1}^{m} {(I_{m})}_{i k} A_{k j} = \sum_{k = 1}^{m} δ_{i k} A_{k j} = A_{i j} .$

Corollary.

Let A be an m×n $m \times n$ matrix, B1, B2, …, Bk $B_{1}, B_{2}, \dots, B_{k}$ be n×p $n \times p$ matrices, C1, C2, …, Ck $C_{1}, C_{2}, \dots, C_{k}$ be q×m $q \times m$ matrices, and a1, a2, …, ak $a_{1}, a_{2}, \dots, a_{k}$ be scalars. Then

A (\sum i = 1 k a i B i) = \sum i = 1 k a i A B i

$A (\sum_{i = 1}^{k} a_{i} B_{i}) = \sum_{i = 1}^{k} a_{i} A B_{i}$

and

(\sum i = 1 k a i C i) A = \sum i = 1 k a i C i A .

$(\sum_{i = 1}^{k} a_{i} C_{i}) A = \sum_{i = 1}^{k} a_{i} C_{i} A .$

Proof.

Exercise.

For an n×n $n \times n$ matrix A, we define A1=A, A2=AA, A3=A2A $A^{1} = A, A^{2} = A A, A^{3} = A^{2} A$ , and, in general, Ak=Ak−1A $A^{k} = A^{k - 1} A$ for k=2, 3, …. $k = 2, 3, \dots.$ We define A0=In $A^{0} = I_{n}$ .

With this notation, we see that if

A = (0100),

$A = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}),$

then A2=O $A^{2} = O$ (the zero matrix) even though A≠O $A \neq O$ . Thus the cancellation property for multiplication in fields is not valid for matrices. To see why, assume that the cancellation law is valid. Then, from A⋅A=A2=O=A⋅O $A \cdot A = A^{2} = O = A \cdot O$ , we would conclude that A=O $A = O$ , which is false.

Theorem 2.13.

Let A be an m×n $m \times n$ matrix and B be an n×p $n \times p$ matrix. For each j, j=1, 2, …, p $j, j = 1, 2, \dots, p$ let uj $u_{j}$ and vj $v_{j}$ denote the jth columns of AB and B, respectively. Then

(a) uj=Avj $u_{j} = A v_{j}$
(b) vj=Bej $v_{j} = B e_{j}$ , where ej $e_{j}$ is the jth standard vector of Fp $F^{p}$ .

Proof.

(a) We have

u j = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ (A B) 1 j (A B) 2 j ⋮ (A B) m j ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ \sum k = 1 n A 1 k B k j \sum k = 1 n A 2 k B k j ⋮ \sum k = 1 n A m k B k j ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = A ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ B 1 j B 2 j ⋮ B n j ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ = A v j .

$u_{j} = (\begin{matrix} {(A B)}_{1 j} \\ {(A B)}_{2 j} \\ ⋮ \\ {(A B)}_{m j} \end{matrix}) = (\begin{matrix} \sum_{k = 1}^{n} A_{1 k} B_{k j} \\ \sum_{k = 1}^{n} A_{2 k} B_{k j} \\ ⋮ \\ \sum_{k = 1}^{n} A_{m k} B_{k j} \end{matrix}) = A (\begin{matrix} B_{1 j} \\ B_{2 j} \\ ⋮ \\ B_{n j} \end{matrix}) = A v_{j} .$

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.

Theorem 2.14.

Let V and W be finite-dimensional vector spaces having ordered bases β $β$ and γ $γ$ , respectively, and let T:V→W $T : V \to W$ be linear. Then, for each u∈V $u \in V$ , we have

[T (u)] γ = [T] γ β [u] β .

${[T (u)]}_{γ} = {[T]}_{β}^{γ} {[u]}_{β} .$

Proof.

Fix u∈V $u \in V$ , and define the linear transformations f:F→V $f : F \to V$ by f(a)=au $f (a) = a u$ and g:F→W $g : F \to W$ by g(a)=aT(u) $g (a) = a T (u)$ for all a∈F $a \in F$ . Let α={1} $α = {1}$ be the standard ordered basis for F. Notice that g=Tf $g = T f$ . Identifying column vectors as matrices and using Theorem 2.11, we obtain

[T (u)] γ = [g (1)] γ = [g] γ α = [T f] γ α = [T] γ β [f] β α = [T] γ β [f (1)] β = [T] γ β [u] β .

${[T (u)]}_{γ} = {[g (1)]}_{γ} = {[g]}_{α}^{γ} = {[T f]}_{α}^{γ} = {[T]}_{β}^{γ} {[f]}_{α}^{β} = {[T]}_{β}^{γ} {[f (1)]}_{β} = {[T]}_{β}^{γ} {[u]}_{β} .$

Example 3

Let T:P3(R)→P2(R) $T : P_{3} (R) \to P_{2} (R)$ be the linear transformation defined by T(f(x))=f′(x) $T (f (x)) = f^{'} (x)$ , and let β $β$ and γ $γ$ be the standard ordered bases for P3(R) $P_{3} (R)$ and P2(R) $P_{2} (R)$ , respectively. If A=[T]γβ $A = {[T]}_{β}^{γ}$ , then, from Example 4 of Section 2.2, we have

A = ⎛ ⎝ ⎜ 000100020003 ⎞ ⎠ ⎟ .

$A = (\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{matrix}) .$

We illustrate Theorem 2.14 by verifying that [T(p(x))]γ=[T]γβ[p(x)]β ${[T (p (x))]}_{γ} = {[T]}_{β}^{γ} {[p (x)]}_{β}$ , where p(x)∈P3(R) $p (x) \in P_{3} (R)$ is the polynomial p(x)=2−4x+x2+3x3 $p (x) = 2 - 4 x + x^{2} + 3 x^{3}$ . Let q(x)=T(p(x)) $q (x) = T (p (x))$ ; then q(x)=p′(x)=−4+2x+9x2 $q (x) = p^{'} (x) = - 4 + 2 x + 9 x^{2}$ . Hence

[T (p (x))] γ = [q (x)] γ = ⎛ ⎝ ⎜ - 4 29 ⎞ ⎠ ⎟,

${[T (p (x))]}_{γ} = {[q (x)]}_{γ} = (\begin{array}{r} - 4 \\ 2 \\ 9 \end{array}),$

but also

[T] γ β [p (x)] β = A [p (x)] β = ⎛ ⎝ ⎜ 000100020003 ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ 2 - 4 13 ⎞ ⎠ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ - 4 29 ⎞ ⎠ ⎟ .

${[T]}_{β}^{γ} {[p (x)]}_{β} = A {[p (x)]}_{β} = (\begin{array}{r} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{array}) (\begin{array}{r} 2 \\ - 4 \\ 1 \\ 3 \end{array}) = (\begin{array}{r} - 4 \\ 2 \\ 9 \end{array}) .$

We complete this section with the introduction of the left-multiplication transformation LA $L_{A}$ , where A is an m×n $m \times n$ matrix. This transformation is probably the most important tool for transferring properties about transformations to analogous properties about matrices and vice versa. For example, we use it to prove that matrix multiplication is associative.

Definition.

Let A be an m×n $m \times n$ matrix with entries from a field F. We denote by LA $L_{A}$ the mapping LA:Fn→Fm $L_{A} : F^{n} \to F^{m}$ defined by LA(x)=Ax $L_{A} (x) = A x$ (the matrix product of A and x) for each column vector x∈Fn $x \in F^{n}$ . We call LA $L_{A}$ a left-multiplication transformation.

Example 4

Let

A = (102112) .

$A = (\begin{matrix} 1 & 2 & 1 \\ 0 & 1 & 2 \end{matrix}) .$

Then A∈M2×3(R) $A \in M_{2 \times 3} (R)$ and LA:R3→R2 $L_{A} : R^{3} \to R^{2}$ . If

x = ⎛ ⎝ ⎜ 13 - 1 ⎞ ⎠ ⎟,

$x = (\begin{array}{r} 1 \\ 3 \\ - 1 \end{array}),$

then

L A (x) = A x = (102112) ⎛ ⎝ ⎜ 13 - 1 ⎞ ⎠ ⎟ = (61) .

$L_{A} (x) = A x = (\begin{matrix} 1 & 2 & 1 \\ 0 & 1 & 2 \end{matrix}) (\begin{array}{r} 1 \\ 3 \\ - 1 \end{array}) = (\begin{matrix} 6 \\ 1 \end{matrix}) .$

We see in the next theorem that not only is LA $L_{A}$ linear, but, in fact, it has a great many other useful properties. These properties are all quite natural and so are easy to remember.

Theorem 2.15.

Let A be an m×n $m \times n$ matrix with entries from F. Then the left-multiplication transformation LA:Fn→Fm $L_{A} : F^{n} \to F^{m}$ is linear. Furthermore, if B is any other m×n $m \times n$ matrix (with entries from F) and β $β$ and γ $γ$ are the standard ordered bases for Fn $F^{n}$ and Fm $F^{m}$ , respectively, then we have the following properties.

(a) [LA]γβ=A ${[L_{A}]}_{β}^{γ} = A$
(b) LA=LB $L_{A} = L_{B}$ if and only if A=B $A = B$ .
(c) LA+B=LA+LB $L_{A + B} = L_{A} + L_{B}$ and LaA=aLA $L_{a A} = a L_{A}$ for all a∈F $a \in F$ .
(d) If T:Fn→Fm $T : F^{n} \to F^{m}$ is linear, then there exists a unique m×n $m \times n$ matrix C such that T=LC $T = L_{C}$ . In fact, C=[T]γβ $C = {[T]}_{β}^{γ}$ .
(e) If E is an n×p $n \times p$ matrix, then LAE=LALE $L_{A E} = L_{A} L_{E}$ .
(f) If m=n $m = n$ , then LIn=IFn $L_{I_{n}} = I_{F^{n}}$ .

Proof.

The fact that LA $L_{A}$ is linear follows immediately from Theorem 2.12.

(a) The jth column of [LA]γβ ${[L_{A}]}_{β}^{γ}$ is equal to LA(ej) $L_{A} (e_{j})$ . However LA(ej)=Aej $L_{A} (e_{j}) = A e_{j}$ , which is also the jth column of A by Theorem 2.13(b). So [LA]γβ=A ${[L_{A}]}_{β}^{γ} = A$ .
(b) If LA=LB $L_{A} = L_{B}$ , then we may use (a) to write A=[LA]γβ=[LB]γβ=B $A = {[L_{A}]}_{β}^{γ} = {[L_{B}]}_{β}^{γ} = B$ . Hence A=B $A = B$ . The proof of the converse is trivial.
(c) The proof is left as an exercise. (See Exercise 7.)
(d) Let C=[T]γβ $C = {[T]}_{β}^{γ}$ . By Theorem 2.14, we have [T(x)]γ=[T]γβ[x]β ${[T (x)]}_{γ} = {[T]}_{β}^{γ} {[x]}_{β}$ , or T(x)=Cx=LC(x) $T (x) = C x = L_{C} (x)$ for all x∈Fn $x \in F^{n}$ . So T=LC $T = L_{C}$ . The uniqueness of C follows from (b).
(e) For any j(1≤j≤p) $j (1 \leq j \leq p)$ , we may apply Theorem 2.13 several times to note that (AE)ej $(A E) e_{j}$ is the jth column of AE and that the jth column of AE is also equal to A(Eej) $A (E e_{j})$ . So (AE)ej=A(Eej) $(A E) e_{j} = A (E e_{j})$ . Thus

$L A E (e j) = (A E) e j = A (E e j) = L A (E e j) = L A (L E (e j)) .$ $L_{A E} (e_{j}) = (A E) e_{j} = A (E e_{j}) = L_{A} (E e_{j}) = L_{A} (L_{E} (e_{j})) .$

Hence LAE=LALE $L_{A E} = L_{A} L_{E}$ by the corollary to Theorem 2.6 (p. 73).
(f) The proof is left as an exercise. (See Exercise 7.)

We now use left-multiplication transformations to establish the associativity of matrix multiplication.

Theorem 2.16.

Let A, B, and C be matrices such that A(BC) is defined. Then (AB)C is also defined and A(BC)=(AB)C $A (B C) = (A B) C$ ; that is, matrix multiplication is associative.

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

L A (B C) = L A L B C = L A (L B L C) = (L A L B) L C = L A B L C = L (A B) C .

$L_{A} (B C) = L_{A} L_{B C} = L_{A} (L_{B} L_{C}) = (L_{A} L_{B}) L_{C} = L_{A B} L_{C} = L_{(A B) C} .$

So from (b) of Theorem 2.15, it follows that A(BC)=(AB)C $A (B C) = (A B) 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.

Applications*

For an application of matrix multiplication to the study of population growth, visit goo.gl/x5XDLw.

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 $1, 2, \dots, n$ then we define the associated incidence matrix A by Aij=1 $A_{i j} = 1$ if i is related to j, and Aij=0 $A_{i j} = 0$ otherwise.

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 $A_{i j} = 1$ if i can send a message to j, and Aij=0 $A_{i j} = 0$ otherwise. Suppose that

A = ⎛ ⎝ ⎜ ⎜ ⎜ 0101101100000110 ⎞ ⎠ ⎟ ⎟ ⎟ .

$A = (\begin{array}{r} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{array}) .$

Then since A34=1 $A_{34} = 1$ and A14=0 $A_{14} = 0$ , we see that person 3 can send to 4 but 1 cannot send to 4.

We obtain an interesting interpretation of the entries of A². Consider, for instance,

(A 2) 31 = A 31 A 11 + A 32 A 21 + A 33 A 31 + A 34 A 41 .

${(A^{2})}_{31} = A_{31} A_{11} + A_{32} A_{21} + A_{33} A_{31} + A_{34} A_{41} .$

Note that any term A3kAk1 $A_{3 k} A_{k 1}$ equals 1 if and only if both A3k $A_{3 k}$ and Ak1 $A_{k 1}$ equal 1, that is, if and only if 3 can send to k and k can send to 1. Thus (A2)31 ${(A^{2})}_{31}$ gives the number of ways in which 3 can send to 1 in two stages (namely, 3 to 2 to 1 and 3 to 4 to 1). Since

A 2 = ⎛ ⎝ ⎜ ⎜ ⎜ 1121021100001011 ⎞ ⎠ ⎟ ⎟ ⎟,

$A^{2} = (\begin{matrix} 1 & 0 & 0 & 1 \\ 1 & 2 & 0 & 0 \\ 2 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{matrix}),$

we see that there are two ways 3 can send to 1 in two stages. In general, (A+A2+⋯+Am)ij ${(A + A^{2} + \dots + A^{m})}_{i j}$ is the number of ways in which i can send to j in at most m stages.

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 $B_{i j} = 1$ if i and j can send to each other, and Bij=0 $B_{i j} = 0$ otherwise, then it can be shown (see Exercise 20) that person i belongs to a clique if and only if (B3)ii>0 ${(B^{3})}_{i i} > 0$ . For example, suppose that the incidence matrix associated with some relationship is

A = ⎛ ⎝ ⎜ ⎜ ⎜ 0111101101011010 ⎞ ⎠ ⎟ ⎟ ⎟ .

$A = (\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{matrix}) .$

To determine which people belong to cliques, we form the matrix B, described earlier, and compute B3 $B^{3}$ . In this case,

B = ⎛ ⎝ ⎜ ⎜ ⎜ 0101101001011010 ⎞ ⎠ ⎟ ⎟ ⎟ and B 3 = ⎛ ⎝ ⎜ ⎜ ⎜ 0404404004044040 ⎞ ⎠ ⎟ ⎟ ⎟ .

$B = (\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}) and B^{3} = (\begin{matrix} 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \\ 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \end{matrix}) .$

Since all the diagonal entries of B3 $B^{3}$ are zero, we conclude that there are no cliques in this relationship.

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 $A_{i j} = 1$ if and only if Aji=0 $A_{j i} = 0$ , that is, given any two people, exactly one of them dominates (or, using the terminology of our first example, can send a message to) the other. Since A is an incidence matrix, Aii=0 $A_{i i} = 0$ for all i. For such a relation, it can be shown (see Exercise 22) that the matrix A+A2 $A + A^{2}$ has a row [column] in which each entry is positive except for the diagonal entry. In other words, there is at least one person who dominates [is dominated by] all others in one or two stages. In fact, it can be shown that any person who dominates [is dominated by] the greatest number of people in the first stage has this property. Consider, for example, the matrix

A = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 0010110011010011010000010 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ .

$A = (\begin{matrix} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{matrix}) .$

The reader should verify that this matrix corresponds to a dominance relation. Now

A + A 2 = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 0111220222110221120210110 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ .

$A + A^{2} = (\begin{matrix} 0 & 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 2 & 0 & 2 & 1 \\ 1 & 2 & 2 & 0 & 1 \\ 2 & 2 & 2 & 2 & 0 \end{matrix}) .$

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.

Exercises

Label the following statements as true or false. In each part, V, W, and Z denote vector spaces with ordered (finite) bases α, β $α, β$ , and γ $γ$ , respectively; T:V→W $T : V \to W$ and U:W→Z $U : W \to Z$ denote linear transformations; and A and B denote matrices.
1. (a) [UT]γα=[T]βα[U]γβ ${[UT]}_{α}^{γ} = {[T]}_{α}^{β} {[U]}_{β}^{γ}$ .
2. (b) [T(v)]β=[T]βα[v]α ${[T (v)]}_{β} = {[T]}_{α}^{β} {[v]}_{α}$ for all v∈V $v \in V$ .
3. (c) [U(w)]β=[U]βα[w]β ${[U (w)]}_{β} = {[U]}_{α}^{β} {[w]}_{β}$ for all w∈W $w \in W$ .
4. (d) [IV]α=I ${[I_{V}]}_{α} = I$ .
5. (e) [T2]βα=([T]βα)2 ${[T^{2}]}_{α}^{β} = {({[T]}_{α}^{β})}^{2}$ .
6. (f) A2=I $A^{2} = I$ implies that A=I or A=−I $A = I or A = - I$ .
7. (g) T=LA $T = L_{A}$ for some matrix A.
8. (h) A2=O $A^{2} = O$ implies that A=O $A = O$ , where O denotes the zero matrix.
9. (i) LA+B=LA+LB $L_{A + B} = L_{A} + L_{B}$ .
10. (j) If A is square and Aij=δij $A_{i j} = δ_{i j}$ for all i and j, then A=I $A = I$ .
1. (a) Let
  
  $A = (12 3 - 1), B = (1401 - 3 2), C = (1 - 1 1 - 2 40), and D = ⎛ ⎝ ⎜ 2 - 2 3 ⎞ ⎠ ⎟ .$ $\begin{array}{l} A = (\begin{array}{r} 1 & 3 \\ 2 & - 1 \end{array}), B = (\begin{array}{r} 1 & 0 & - 3 \\ 4 & 1 & 2 \end{array}), \\ C = (\begin{array}{r} 1 & 1 & 4 \\ - 1 & - 2 & 0 \end{array}), and D = (\begin{array}{r} 2 \\ - 2 \\ 3 \end{array}) . \end{array}$
  
  Compute A(2B+3C), (AB)D $A (2 B + 3 C), (A B) D$ and A(BD).
2. (b) Let
  
  $A = ⎛ ⎝ ⎜ 2 - 3 4 512 ⎞ ⎠ ⎟, B = ⎛ ⎝ ⎜ 315 - 2 - 1 5 043 ⎞ ⎠ ⎟, and C= (403) .$ $A = (\begin{array}{r} 2 & 5 \\ - 3 & 1 \\ 4 & 2 \end{array}), B = (\begin{array}{r} 3 & - 2 & 0 \\ 1 & - 1 & 4 \\ 5 & 5 & 3 \end{array}), and C= (\begin{matrix} 4 & 0 & 3 \end{matrix}) .$
  
  Compute At, AtB, BCt, CB $A^{t}, A^{t} B, B C^{t}, C B$ and CA $C A$ .
Let g(x)=3+x $g (x) = 3 + x$ . Let T:P2(R)→P2(R) $T : P_{2} (R) \to P_{2} (R)$ and U:P2(R)→R3 $U : P_{2} (R) \to R^{3}$ be the linear transformations respectively defined by

$T (f (x)) = f' (x) g (x) + 2 f (x) and U (a + b x + c x 2) = (a + b, c, a - b) .$ $T (f (x)) = f^{'} (x) g (x) + 2 f (x) and U (a + b x + c x^{2}) = (a + b, c, a - b) .$

Let β $β$ and γ $γ$ be the standard ordered bases of P2(R) $P_{2} (R)$ and R3 $R^{3}$ , respectively.
1. (a) Compute [U]γβ, [T]β ${[U]}_{β}^{γ}, {[T]}_{β}$ and [UT]γβ ${[UT]}_{β}^{γ}$ directly. Then use Theorem 2.11 to verify your result.
2. (b) Let h(x)=3−2x+x2 $h (x) = 3 - 2 x + x^{2}$ . Compute [h(x)]β ${[h (x)]}_{β}$ and [U(h(x))]γ ${[U (h (x))]}_{γ}$ . Then use [U]γβ ${[U]}_{β}^{γ}$ from (a) and Theorem 2.14 to verify your result.
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:
1. (a) [T(A)]α ${[T (A)]}_{α}$ , where A=(1−146) $A = (\begin{array}{r} 1 & 4 \\ - 1 & 6 \end{array})$ .
2. (b) [T(f(x))]α ${[T (f (x))]}_{α}$ , where f(x)=4−6x+3x2 $f (x) = 4 - 6 x + 3 x^{2}$ .
3. (c) [T(A)]γ ${[T (A)]}_{γ}$ , where A=(1234) $A = (\begin{matrix} 1 & 3 \\ 2 & 4 \end{matrix})$ .
4. (d) [T(f(x))]γ ${[T (f (x))]}_{γ}$ , where f(x)=6−x+2x2 $f (x) = 6 - x + 2 x^{2}$ .
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 $U, T : F^{2} \to F^{2}$ such that UT=T0 $UT = T_{0}$ (the zero transformation) but TU≠T0 $TU \neq T_{0}$ . Use your answer to find matrices A and B such that AB=O $A B = O$ but BA≠O $B A \neq O$ .
Let A be an n×n $n \times n$ matrix. Prove that A is a diagonal matrix if and only if Aij=δijAij $A_{i j} = δ_{i j} A_{i j}$ for all i and j.
Let V be a vector space, and let T:V→V $T : V \to V$ be linear. Prove that T2=T0 $T^{2} = T_{0}$ if and only if R(T)⊆N(T) $R (T) \subseteq N (T)$ .
Let V, W, and Z be vector spaces, and let T:V→W $T : V \to W$ and U:W→Z $U : W \to Z$ be linear.
1. (a) Prove that if UT is one-to-one, then T is one-to-one. Must U also be one-to-one?
2. (b) Prove that if UT is onto, then U is onto. Must T also be onto?
3. (c) Prove that if U and T are one-to-one and onto, then UT is also.
Let A and B be n×n $n \times n$ matrices. Recall that the trace of A is defined by

$tr (A) = \sum i = 1 n A i i .$ $tr (A) = \sum_{i = 1}^{n} A_{i i} .$

Prove that tr(AB)=tr(BA) $tr (A B) = tr (B A)$ and tr(A)=tr(At) $tr (A) = tr (A^{t})$ .
Assume the notation in Theorem 2.13.
1. (a) Suppose that z is a (column) vector in Fp $F^{p}$ . Use Theorem 2.13(b) to prove that Bz is a linear combination of the columns of B. In particular, if z=(a1, a2, …, ap)t $z = {(a_{1}, a_{2}, \dots, a_{p})}^{t}$ , then show that
  
  $B z = \sum j = 1 p a j v j .$ $B z = \sum_{j = 1}^{p} a_{j} v_{j} .$
2. (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.
3. (c) For any row vector w∈Fm $w \in F^{m}$ , prove that wA $w A$ is a linear combination of the rows of A with the coefficients in the linear combination being the coordinates of w. Hint: Use properties of the transpose operation applied to (a).
4. (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 $u_{j}$ and vj $v_{j}$ denote the jth columns of AB and B, respectively. If vp=c1vj1+c2vj2+⋯+ckvjk $v_{p} = c_{1} v_{j 1} + c_{2} v_{j 2} + \dots + c_{k} v_{j k}$ for some scalars c1, c2, …, ck $c_{1}, c_{2}, \dots, c_{k}$ prove that up=c1uj1+c2uj2+⋯+ckujk $u_{p} = c_{1} u_{j 1} + c_{2} u_{j 2} + \dots + c_{k} u_{j k}$ . Visit goo.gl/sRpves for a solution.
Let V be a finite-dimensional vector space, and let T:V→V $T : V \to V$ be linear.
1. (a) If rank(T)=rank(T2) $rank (T) = rank (T^{2})$ , prove that R(T)∩N(T)={0} $R (T) \cap N (T) = {0}$ . Deduce that V=R(T)⊕N(T) $V = R (T) \oplus N (T)$ (see the exercises of Section 1.3).
2. (b) Prove that V=R(Tk)⊕N(Tk) $V = R (T^{k}) \oplus N (T^{k})$ for some positive integer k.
For the definition of projection and related facts, see pages 76–77. Let V be a vector space and T:V→V $T : V \to V$ be a linear transformation. Prove that T=T2 $T = T^{2}$ if and only if T is a projection on W1={y:T(y)=y} $W_{1} = {y : T (y) = y}$ along N(T).
Let β $β$ be an ordered basis for a finite-dimensional vector space V, and let T:V→V $T : V \to V$ be linear. Prove that, for any nonnegative integer k, [Tk]β=([T]β)k ${[T^{k}]}_{β} = {({[T]}_{β})}^{k}$ .
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 $B_{i j} = 1$ if i is related to j and j is related to i, and Bij=0 $B_{i j} = 0$ otherwise, prove that i belongs to a clique if and only if (B3)ii>0 ${(B^{3})}_{i i} > 0$ .
Use Exercise 20 to determine the cliques in the relations corresponding to the following incidence matrices.
1. (a) ⎛⎝⎜⎜⎜0101101000011010⎞⎠⎟⎟⎟ $(\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix})$
2. (b) ⎛⎝⎜⎜⎜0111000010011110⎞⎠⎟⎟⎟ $(\begin{matrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix})$
Let A be an incidence matrix that is associated with a dominance relation. Prove that the matrix A+A2 $A + A^{2}$ has a row [column] in which each entry is positive except for the diagonal entry.
Prove that the matrix

$A = ⎛ ⎝ ⎜ 001100010 ⎞ ⎠ ⎟$ $A = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{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 $n \times n$ incidence matrix that corresponds to a dominance relation. Determine the number of nonzero entries of A.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 2.3 Composition of Linear Transformations and Matrix Multiplication

Create new playlist

Sign In

Sign Up

Table of Contents for
2.3 Composition of Linear Transformations and Matrix Multiplication