# Linear Algebra/Matrix Multiplication

After representing addition and scalar multiplication of linear maps in the prior subsection, the natural next map operation to consider is composition.

- Lemma 2.1

A composition of linear maps is linear.

- Proof

*(This argument has appeared earlier, as part of the proof that isomorphism is an equivalence relation between spaces.)*
Let and be linear.
The calculation

shows that preserves linear combinations.

To see how the representation of the composite arises out of the representations of the two compositors, consider an example.

- Example 2.2

Let and , fix bases , , , and let these be the representations.

To represent the composition we fix a , represent of , and then represent of that. The representation of is the product of 's matrix and 's vector.

The representation of is the product of 's matrix and 's vector.

Distributing and regrouping on the 's gives

which we recognizing as the result of this matrix-vector product.

Thus, the matrix representing has the rows of combined with the columns of .

- Definition 2.3

The **matrix-multiplicative product** of the matrix and the matrix is the matrix , where

that is, the -th entry of the product is the dot product of the -th row and the -th column.

- Example 2.5

- Theorem 2.6

A composition of linear maps is represented by the matrix product of the representatives.

- Proof

*(This argument parallels Example 2.2.)*
Let and be represented by
and with respect to bases
, , and , of sizes
, , and .
For any , the -th component of
is

and so the -th component of is this.

Distribute and regroup on the 's.

Finish by recognizing that the coefficient of each

matches the definition of the entry of the product .

The theorem is an example of a result that supports
a definition.
We can picture what the definition and theorem together say with this
**arrow diagram** ("wrt" abbreviates "with respect to").

Above the arrows, the maps show that the two ways of going from to , straight over via the composition or else by way of , have the same effect

(this is just the definition of composition). Below the arrows, the matrices indicate that the product does the same thing— multiplying into the column vector has the same effect as multiplying the column first by and then multiplying the result by .

The definition of the matrix-matrix product operation does not restrict us to view it as a representation of a linear map composition. We can get insight into this operation by studying it as a mechanical procedure. The striking thing is the way that rows and columns combine.

One aspect of that combination is that the sizes of the matrices involved is significant. Briefly, .

- Example 2.7

This product is not defined

because the number of columns on the left does not equal the number of rows on the right.

In terms of the underlying maps, the fact that the sizes must match up reflects the fact that matrix multiplication is defined only when a corresponding function composition

is possible.

- Remark 2.8

The order in which these things are written can be confusing. In the "" equation, the number written first is the dimension of 's codomain and is thus the number that appears last in the map dimension description above. The explanation is that while is done first and then is applied, that composition is written , from the notation "". (Some people try to lessen confusion by reading "" aloud as " following ".) That order then carries over to matrices: is represented by .

Another aspect of the way that rows and columns combine in the matrix product operation is that in the definition of the entry

the red subscripts on the 's are column indicators while those on the 's indicate rows. That is, summation takes place over the columns of but over the rows of ; left is treated differently than right, so may be unequal to . Matrix multiplication is not commutative.

- Example 2.9

Matrix multiplication hardly ever commutes. Test that by multiplying randomly chosen matrices both ways.

- Example 2.10

Commutativity can fail more dramatically:

while

isn't even defined.

- Remark 2.11

The fact that matrix multiplication is not commutative may be puzzling at first sight, perhaps just because most algebraic operations in elementary mathematics are commutative. But on further reflection, it isn't so surprising. After all, matrix multiplication represents function composition, which is not commutative— if and then while . True, this is not linear and we might have hoped that linear functions commute, but this perspective shows that the failure of commutativity for matrix multiplication fits into a larger context.

Except for the lack of commutativity, matrix multiplication is algebraically well-behaved. Below are some nice properties and more are in Problem 10 and Problem 11.

- Theorem 2.12

If , , and are matrices, and the matrix products are defined, then the product is associative and distributes over matrix addition and .

- Proof

Associativity holds because matrix multiplication represents function composition, which is associative: the maps and are equal as both send to .

Distributivity is similar. For instance, the first one goes (the third equality uses the linearity of ).

- Remark 2.13

We could alternatively prove that result by slogging through the indices. For example, associativity goes: the -th entry of is

(where , , and are , , and matrices), distribute

and regroup around the 's

to get the entry of .

Contrast these two ways of verifying associativity, the one in the proof and the one just above. The argument just above is hard to understand in the sense that, while the calculations are easy to check, the arithmetic seems unconnected to any idea (it also essentially repeats the proof of Theorem 2.6 and so is inefficient). The argument in the proof is shorter, clearer, and says why this property "really" holds. This illustrates the comments made in the preamble to the chapter on vector spaces— at least some of the time an argument from higher-level constructs is clearer.

We have now seen how the representation of the composition of two linear maps is derived from the representations of the two maps. We have called the combination the product of the two matrices. This operation is extremely important. Before we go on to study how to represent the inverse of a linear map, we will explore it some more in the next subsection.

## Exercises

edit*This exercise is recommended for all readers.*

- Problem 1

Compute, or state "not defined".

*This exercise is recommended for all readers.*

- Problem 2

Where

compute or state "not defined".

- Problem 3

Which products are defined?

- times
- times
- times
- times

*This exercise is recommended for all readers.*

- Problem 4

Give the size of the product or state "not defined".

- a matrix times a matrix
- a matrix times a matrix
- a matrix times a matrix
- a matrix times a matrix

*This exercise is recommended for all readers.*

- Problem 5

Find the system of equations resulting from starting with

and making this change of variable (i.e., substitution).

- Problem 6

As Definition 2.3 points out, the matrix product operation generalizes the dot product. Is the dot product of a row vector and a column vector the same as their matrix-multiplicative product?

*This exercise is recommended for all readers.*

- Problem 7

Represent the derivative map on with respect to where is the natural basis . Show that the product of this matrix with itself is defined; what the map does it represent?

- Problem 8

Show that composition of linear transformations on is commutative. Is this true for any one-dimensional space?

- Problem 9

Why is matrix multiplication not defined as entry-wise multiplication? That would be easier, and commutative too.

*This exercise is recommended for all readers.*

- Problem 10

- Prove that and for positive integers .
- Prove that for any positive integer and scalar .

*This exercise is recommended for all readers.*

- Problem 11

- How does matrix multiplication interact with scalar multiplication: is ? Is ?
- How does matrix multiplication interact with linear combinations: is ? Is ?

- Problem 12

We can ask how the matrix product operation interacts with the transpose operation.

- Show that .
- A square matrix is
**symmetric**if each entry equals the entry, that is, if the matrix equals its own transpose. Show that the matrices and are symmetric.

*This exercise is recommended for all readers.*

- Problem 13

Rotation of vectors in about an axis is a linear map. Show that linear maps do not commute by showing geometrically that rotations do not commute.

- Problem 14

In the proof of Theorem 2.12 some maps are used. What are the domains and codomains?

- Problem 15

How does matrix rank interact with matrix multiplication?

- Can the product of rank matrices have rank less than ? Greater?
- Show that the rank of the product of two matrices is less than or equal to the minimum of the rank of each factor.

- Problem 16

Is "commutes with" an equivalence relation among matrices?

*This exercise is recommended for all readers.*

- Problem 17

*(This will be used in the Matrix Inverses exercises.)*
Here is another property of matrix multiplication that might be
puzzling at first sight.

- Prove that the composition of the projections onto the and axes is the zero map despite that neither one is itself the zero map.
- Prove that the composition of the derivatives is the zero map despite that neither is the zero map.
- Give a matrix equation representing the first fact.
- Give a matrix equation representing the second.

When two things multiply to give zero despite that neither is zero, each is
said to be a **zero divisor**.

- Problem 18

Show that, for square matrices, need not equal .

*This exercise is recommended for all readers.*

- Problem 19

Represent the identity transformation
with respect to for any
basis .
This is the **identity matrix** .
Show that this matrix plays the role in matrix multiplication that the
number plays in real number multiplication: (for all matrices
for which the product is defined).

- Problem 20

In real number algebra, quadratic equations have at most two solutions. That is not so with matrix algebra. Show that the matrix equation has more than two solutions, where is the identity matrix (this matrix has ones in its and entries and zeroes elsewhere; see Problem 19).

- Problem 21

- Prove that for any matrix there are scalars that are not all such that the combination is the zero matrix (where is the identity matrix, with 's in its and entries and zeroes elsewhere; see Problem 19).
- Let be a polynomial . If is a square matrix we define to be the matrix (where is the appropriately-sized identity matrix). Prove that for any square matrix there is a polynomial such that is the zero matrix.
- The
**minimal polynomial**of a square matrix is the polynomial of least degree, and with leading coefficient , such that is the zero matrix. Find the minimal polynomial of this matrix.

- Problem 22

The infinite-dimensional space
of all finite-degree polynomials
gives a memorable example of the non-commutativity of
linear maps.
Let be the usual derivative
and let be the **shift** map.

Show that the two maps don't commute ; in fact, not only is not the zero map, it is the identity map.

- Problem 23

Recall the notation for the sum of the sequence of numbers .

In this notation, the entry of the product of and is this.

Using this notation,

- reprove that matrix multiplication is associative;
- reprove Theorem 2.6.