Matrix Operations

The prior section shows how matrices represent linear maps. We now explore how this representation interacts with things that we already know. First we will see how the representation of a scalar product $r \cdot f$ of a linear map relates to the representation of $f$ , and also how the representation of a sum $f + g$ relates to the representations of the two summands. Later we will do the same comparison for the map operations of composition and inverse.

Sums and Scalar Products

Example 1.1 Let $f : V \to W$ be a linear function represented with respect to some bases by this matrix.

${Rep}_{B, D} (f) = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$

Consider the map that is the scalar multiple $5 f : V \to W$ . We will relate the representation ${Rep}_{B, D} (5 f)$ with ${Rep}_{B, D} (f)$ .

Let $f$ associate $\vec{v} \mapsto \vec{w}$ with these representations.

${Rep}_{B} (\vec{v}) = (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) {Rep}_{D} (\vec{w}) = (\begin{matrix} w_{1} \\ w_{2} \end{matrix})$

Where the codomain’s basis is $D = ⟨ {\vec{δ}}_{1}, {\vec{δ}}_{2} ⟩$ , that representation gives that the output vector is $\vec{w} = w_{1} {\vec{δ}}_{1} + w_{2} {\vec{δ}}_{2}$ .

The action of the map $5 f$ is $\vec{v} \mapsto 5 \vec{w}$ and $5 \vec{w} = 5 \cdot (w_{1} {\vec{δ}}_{1} + w_{2} {\vec{δ}}_{2}) = (5 w_{1}) {\vec{δ}}_{1} + (5 w_{2}) {\vec{δ}}_{2}$ . So $5 f$ associates the input vector $\vec{v}$ with the output vector having this representation.

${Rep}_{D} (5 \vec{w}) = (\begin{matrix} 5 w_{1} \\ 5 w_{2} \end{matrix})$

Changing from the map $f$ to the map $5 f$ has the effect on the representation of the output vector of multiplying each entry by $5$ .

Because of that, ${Rep}_{B, D} (5 f)$ is this matrix.

${Rep}_{B, D} (5 f) \cdot (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) = (\begin{matrix} 5 v_{1} \\ 5 v_{1} + 5 v_{2} \end{matrix}) {Rep}_{B, D} (5 f) = (\begin{matrix} 5 & 0 \\ 5 & 5 \end{matrix})$

Therefore, going from the matrix representing $f$ to the one representing $5 f$ means multiplying all the matrix entries by $5$ .

Example 1.2 We can do a similar exploration for the sum of two maps. Suppose that two linear maps with the same domain and codomain $f, g : ℝ^{2} \to ℝ^{2}$ are represented with respect to bases $B$ and $D$ by these matrices.

${Rep}_{B, D} (f) = (\begin{matrix} 1 & 3 \\ 2 & 0 \end{matrix}) {Rep}_{B, D} (g) = (\begin{matrix} - 2 & - 1 \\ 2 & 4 \end{matrix})$

Recall the definition of sum: if $f$ does $\vec{v} \mapsto \vec{u}$ and $g$ does $\vec{v} \mapsto \vec{w}$ then $f + g$ is the function whose action is $\vec{v} \mapsto \vec{u} + \vec{w}$ . Let these be the representations of the input and output vectors.

${Rep}_{B} (\vec{v}) = (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) {Rep}_{D} (\vec{u}) = (\begin{matrix} u_{1} \\ u_{2} \end{matrix}) {Rep}_{D} (\vec{w}) = (\begin{matrix} w_{1} \\ w_{2} \end{matrix})$

Where $D = ⟨ {\vec{δ}}_{1}, {\vec{δ}}_{2} ⟩$ we have $\vec{u} + \vec{w} = (u_{1} {\vec{δ}}_{1} + u_{2} {\vec{δ}}_{2}) + (w_{1} {\vec{δ}}_{1} + w_{2} {\vec{δ}}_{2}) = (u_{1} + w_{1}) {\vec{δ}}_{1} + (u_{2} + w_{2}) {\vec{δ}}_{2}$ and so this is the representation of the vector sum.

${Rep}_{D} (\vec{u} + \vec{w}) = (\begin{matrix} u_{1} + w_{1} \\ u_{2} + w_{2} \end{matrix})$

Thus, since these represent the actions of of the maps $f$ and $g$ on the input $\vec{v}$

$(\begin{matrix} 1 & 3 \\ 2 & 0 \end{matrix}) (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) = (\begin{matrix} v_{1} + 3 v_{2} \\ 2 v_{1} \end{matrix}) (\begin{matrix} - 2 & - 1 \\ 2 & 4 \end{matrix}) (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) = (\begin{matrix} - 2 v_{1} - v_{2} \\ 2 v_{1} + 4 v_{2} \end{matrix})$

adding the entries represents the action of the map $f + g$ .

${Rep}_{B, D} (f + g) \cdot (\begin{matrix} v_{1} \\ v_{2} \end{matrix}) = (\begin{matrix} - v_{1} + 2 v_{2} \\ 4 v_{1} + 4 v_{2} \end{matrix})$

Therefore, we compute the matrix representing the function sum by adding the entries of the matrices representing the functions.

${Rep}_{B, D} (f + g) = (\begin{matrix} - 1 & 2 \\ 4 & 4 \end{matrix})$

Definition 1.3 The scalar multiple of a matrix is the result of entry-by-entry scalar multiplication. The sum of two same-sized matrices is their entry-by-entry sum.

These operations extend the first chapter’s operations of addition and scalar multiplication of vectors.

We need a result that proves these matrix operations do what the examples suggest that they do.

Theorem 1.4 Let $h, g : V \to W$ be linear maps represented with respect to bases $B, D$ by the matrices $H$ and $G$ and let $r$ be a scalar. Then with respect to $B, D$ the map $r \cdot h : V \to W$ is represented by $r H$ and the map $h + g : V \to W$ is represented by $H + G$ .

Proof Generalize the examples. This is Exercise 1.10.

QED

Remark 1.5 These two operations on matrices are simple, but we did not define them in this way because they are simple. We defined them this way because they represent function addition and function scalar multiplication. That is, our program is to define matrix operations by referencing function operations. Simplicity is a bonus.

We will see this again in the next subsection, where we will define the operation of multiplying matrices. Since we’ve just defined matrix scalar multiplication and matrix sum to be entry-by-entry operations, a naive thought is to define matrix multiplication to be the entry-by-entry product. In theory we could do whatever we please but we will instead be practical and combine the entries in the way that represents the function operation of composition.

A special case of scalar multiplication is multiplication by zero. For any map $0 \cdot h$ is the zero homomorphism and for any matrix $0 \cdot H$ is the matrix with all entries zero.

Definition 1.6 A zero matrix has all entries $0$ . We write $Z_{n \times m}$ or simply $Z$ (another common notation is $0_{n \times m}$ or just $0$ ).

Example 1.7 The zero map from any three-dimensional space to any two-dimensional space is represented by the $2 \times 3$ zero matrix

$Z = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$

no matter what domain and codomain bases we use.

Exercises

Exercise 1.8 Worked answer

Recommended. Perform the indicated operations, if defined, or state “not defined.”
1. $(\begin{matrix} 5 & - 1 & 2 \\ 6 & 1 & 1 \end{matrix}) + (\begin{matrix} 2 & 1 & 4 \\ 3 & 0 & 5 \end{matrix})$
2. $6 \cdot (\begin{matrix} 2 & - 1 & - 1 \\ 1 & 2 & 3 \end{matrix})$
3. $(\begin{matrix} 2 & 1 \\ 0 & 3 \end{matrix}) + (\begin{matrix} 2 & 1 \\ 0 & 3 \end{matrix})$
4. $4 (\begin{matrix} 1 & 2 \\ 3 & - 1 \end{matrix}) + 5 (\begin{matrix} - 1 & 4 \\ - 2 & 1 \end{matrix})$
5. $3 (\begin{matrix} 2 & 1 \\ 3 & 0 \end{matrix}) + 2 (\begin{matrix} 1 & 1 & 4 \\ 3 & 0 & 5 \end{matrix})$
Back to Exercise 1.8

Answer.
1. $(\begin{matrix} 7 & 0 & 6 \\ 9 & 1 & 6 \end{matrix})$
2. $(\begin{matrix} 12 & - 6 & - 6 \\ 6 & 12 & 18 \end{matrix})$
3. $(\begin{matrix} 4 & 2 \\ 0 & 6 \end{matrix})$
4. $(\begin{matrix} - 1 & 28 \\ 2 & 1 \end{matrix})$
5. Not defined.
Exercise 1.9 Worked answer

Give the matrix representing the zero map from $ℝ^{4}$ to $ℝ^{2}$ , with respect to the standard bases.

Back to Exercise 1.9

Answer. The bases don’t matter. The only thing that matters is getting the dimensions right.

$(\begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})$
Exercise 1.10 Worked answer

Prove Theorem 1.4.
1. Prove that matrix addition represents addition of linear maps.
2. Prove that matrix scalar multiplication represents scalar multiplication of linear maps.
Back to Exercise 1.10

Answer. Represent the domain vector $\vec{v} \in V$ and the maps $g, h : V \to W$ with respect to bases $B, D$ in the usual way.
1. The representation of $(g + h) (\vec{v}) = g (\vec{v}) + h (\vec{v})$
  
  $\begin{matrix} ((g_{1, 1} v_{1} + \dots + g_{1, n} v_{n}) {\vec{δ}}_{1} + \dots + (g_{m, 1} v_{1} + \dots + g_{m, n} v_{n}) {\vec{δ}}_{m}) \\ + ((h_{1, 1} v_{1} + \dots + h_{1, n} v_{n}) {\vec{δ}}_{1} + \dots + (h_{m, 1} v_{1} + \dots + h_{m, n} v_{n}) {\vec{δ}}_{m}) \end{matrix}$
  
  regroups
  
  $\begin{matrix} = ((g_{1, 1} + h_{1, 1}) v_{1} + \dots + (g_{1, 1} + h_{1, n}) v_{n}) \cdot {\vec{δ}}_{1} \\ + \dots + ((g_{m, 1} + h_{m, 1}) v_{1} + \dots + (g_{m, n} + h_{m, n}) v_{n}) \cdot {\vec{δ}}_{m} \end{matrix}$
  
  to the entry-by-entry sum of the representation of $g (\vec{v})$ and the representation of $h (\vec{v})$ .
2. The representation of $(r \cdot h) (\vec{v}) = r \cdot (h (\vec{v}))$
  
  $\begin{aligned} r \cdot & ((h_{1, 1} v_{1} + h_{1, 2} v_{2} + \dots + h_{1, n} v_{n}) {\vec{δ}}_{1} \\ + \dots + (h_{m, 1} v_{1} + h_{m, 2} v_{2} + \dots + h_{m, n} v_{n}) {\vec{δ}}_{m}) \\ = (r h_{1, 1} v_{1} + \dots + r h_{1, n} v_{n}) \cdot {\vec{δ}}_{1} \\ + \dots + (r h_{m, 1} v_{1} + \dots + r h_{m, n} v_{n}) \cdot {\vec{δ}}_{m} \end{aligned}$
  
  is the entry-by-entry multiple of $r$ and the representation of $h$ .
Exercise 1.11 Worked answer

Recommended. Prove each, assuming that the operations are defined, where $G$ , $H$ , and $J$ are matrices, where $Z$ is the zero matrix, and where $r$ and $s$ are scalars.
1. Matrix addition is commutative $G + H = H + G$ .
2. Matrix addition is associative $G + (H + J) = (G + H) + J$ .
3. The zero matrix is an additive identity $G + Z = G$ .
4. $0 \cdot G = Z$
5. $(r + s) G = r G + s G$
6. Matrices have an additive inverse $G + (- 1) \cdot G = Z$ .
7. $r (G + H) = r G + r H$
8. $(r s) G = r (s G)$
Back to Exercise 1.11

Answer. First, each of these properties is easy to check in an entry-by-entry way. For example, writing

$G = (\begin{matrix} g_{1, 1} & \dots & g_{1, n} \\ ⋮ & ⋮ \\ g_{m, 1} & \dots & g_{m, n} \end{matrix}) H = (\begin{matrix} h_{1, 1} & \dots & h_{1, n} \\ ⋮ & ⋮ \\ h_{m, 1} & \dots & h_{m, n} \end{matrix})$

then, by definition we have

$G + H = (\begin{matrix} g_{1, 1} + h_{1, 1} & \dots & g_{1, n} + h_{1, n} \\ ⋮ & ⋮ \\ g_{m, 1} + h_{m, 1} & \dots & g_{m, n} + h_{m, n} \end{matrix})$

and

$H + G = (\begin{matrix} h_{1, 1} + g_{1, 1} & \dots & h_{1, n} + g_{1, n} \\ ⋮ & ⋮ \\ h_{m, 1} + g_{m, 1} & \dots & h_{m, n} + g_{m, n} \end{matrix})$

and the two are equal since their entries are equal $g_{i, j} + h_{i, j} = h_{i, j} + g_{i, j}$ . That is, each of these is easy to check by using Definition 1.3 alone.

However, each property is also easy to understand in terms of the represented maps, by applying Theorem 1.4 as well as the definition.
1. The two maps $g + h$ and $h + g$ are equal because $g (\vec{v}) + h (\vec{v}) = h (\vec{v}) + g (\vec{v})$ , as addition is commutative in any vector space. Because the maps are the same, they must have the same representative.
2. As with the prior answer, except that here we apply that vector space addition is associative.
3. As before, except that here we note that $g (\vec{v}) + z (\vec{v}) = g (\vec{v}) + \vec{0} = g (\vec{v})$ .
4. Apply that $0 \cdot g (\vec{v}) = \vec{0} = z (\vec{v})$ .
5. Apply that $(r + s) \cdot g (\vec{v}) = r \cdot g (\vec{v}) + s \cdot g (\vec{v})$ .
6. Apply the prior two items with $r = 1$ and $s = - 1$ .
7. Apply that $r \cdot (g (\vec{v}) + h (\vec{v})) = r \cdot g (\vec{v}) + r \cdot h (\vec{v})$ .
8. Apply that $(r s) \cdot g (\vec{v}) = r \cdot (s \cdot g (\vec{v}))$ .
Exercise 1.12 Worked answer

Fix domain and codomain spaces. In general, one matrix can represent many different maps with respect to different bases. However, prove that a zero matrix represents only a zero map. Are there other such matrices?

Back to Exercise 1.12

Answer. For any $V, W$ with bases $B, D$ , the (appropriately-sized) zero matrix represents this map.

${\vec{β}}_{1} \mapsto 0 \cdot {\vec{δ}}_{1} + \dots + 0 \cdot {\vec{δ}}_{m} \dots {\vec{β}}_{n} \mapsto 0 \cdot {\vec{δ}}_{1} + \dots + 0 \cdot {\vec{δ}}_{m}$

This is the zero map.

There are no other matrices that represent only one map. For, suppose that $H$ is not the zero matrix. Then it has a nonzero entry; assume that $h_{i, j} \neq 0$ . With respect to bases $B, D$ , it represents $h_{1} : V \to W$ sending

${\vec{β}}_{j} \mapsto h_{1, j} {\vec{δ}}_{1} + \dots + h_{i, j} {\vec{δ}}_{i} + \dots + h_{m, j} {\vec{δ}}_{m}$

and with respect to $B, 2 \cdot D$ it also represents $h_{2} : V \to W$ sending

${\vec{β}}_{j} \mapsto h_{1, j} \cdot (2 {\vec{δ}}_{1}) + \dots + h_{i, j} \cdot (2 {\vec{δ}}_{i}) + \dots + h_{m, j} \cdot (2 {\vec{δ}}_{m})$

(the notation $2 \cdot D$ means to double all of the members of D). These maps are easily seen to be unequal.
Exercise 1.13 Worked answer

Recommended. Let $V$ and $W$ be vector spaces of dimensions $n$ and $m$ . Show that the space $ℒ (V, W)$ of linear maps from $V$ to $W$ is isomorphic to $ℳ_{m \times n}$ .

Back to Exercise 1.13

Answer. Fix bases $B$ and $D$ for $V$ and $W$ , and consider ${Rep}_{B, D} : ℒ (V, W) \to ℳ_{m \times n}$ associating each linear map with the matrix representing that map $h \mapsto {Rep}_{B, D} (h)$ . From the prior section we know that (under fixed bases) the matrices correspond to linear maps, so the representation map is one-to-one and onto. That it preserves linear operations is Theorem 1.4.
Exercise 1.14 Worked answer

Recommended. Show that it follows from the prior question that for any six transformations $t_{1}, \dots, t_{6} : ℝ^{2} \to ℝ^{2}$ there are scalars $c_{1}, \dots, c_{6} \in ℝ$ such that not every $c_{i}$ equals $0$ but $c_{1} t_{1} + \dots + c_{6} t_{6}$ is the zero map. (Hint: the six is slightly misleading.)

Back to Exercise 1.14

Answer. Fix bases and represent the transformations with $2 \times 2$ matrices. The space of matrices $ℳ_{2 \times 2}$ has dimension four, and hence any six-element set is linearly dependent. By the prior exercise that extends to a dependence of maps. (The misleading part is only that there are six transformations, not five, so that we have more than we need to give the existence of the dependence.)
Exercise 1.15 Worked answer

The trace of a square matrix is the sum of the entries on the main diagonal (the $1, 1$ entry plus the $2, 2$ entry, etc.; we will see the significance of the trace in Chapter Five). Show that $trace (H + G) = trace (H) + trace (G)$ . Is there a similar result for scalar multiplication?

Back to Exercise 1.15

Answer. That the trace of a sum is the sum of the traces holds because both $trace (H + G)$ and $trace (H) + trace (G)$ are the sum of $h_{1, 1} + g_{1, 1}$ with $h_{2, 2} + g_{2, 2}$ , etc. For scalar multiplication we have $trace (r \cdot H) = r \cdot trace (H)$ ; the proof is easy. Thus the trace map is a homomorphism from $ℳ_{n \times n}$ to $ℝ$ .
Exercise 1.16 Worked answer

Recall that the transpose of a matrix $M$ is another matrix, whose $i, j$ entry is the $j, i$ entry of $M$ . Verify these identities.
1. ${(G + H)}^{𝖳} = G^{𝖳} + H^{𝖳}$
2. ${(r \cdot H)}^{𝖳} = r \cdot H^{𝖳}$
Back to Exercise 1.16

Answer.
1. The $i, j$ entry of ${(G + H)}^{𝖳}$ is $g_{j, i} + h_{j, i}$ . That is also the $i, j$ entry of $G^{𝖳} + H^{𝖳}$ .
2. The $i, j$ entry of ${(r \cdot H)}^{𝖳}$ is $r h_{j, i}$ , which is also the $i, j$ entry of $r \cdot H^{𝖳}$ .
Exercise 1.17 Worked answer

Recommended. A square matrix is symmetric if each $i, j$ entry equals the $j, i$ entry, that is, if the matrix equals its transpose.
1. Prove that for any square $H$ , the matrix $H + H^{𝖳}$ is symmetric. Does every symmetric matrix have this form?
2. Prove that the set of $n \times n$ symmetric matrices is a subspace of $ℳ_{n \times n}$ .
Back to Exercise 1.17

Answer.
1. For $H + H^{𝖳}$ , the $i, j$ entry is $h_{i, j} + h_{j, i}$ and the $j, i$ entry of is $h_{j, i} + h_{i, j}$ . The two are equal and thus $H + H^{𝖳}$ is symmetric.
  
  Every symmetric matrix does have that form, since we can write $H = (1 / 2) \cdot (H + H^{𝖳})$ .
2. The set of symmetric matrices is nonempty as it contains the zero matrix. Clearly a scalar multiple of a symmetric matrix is symmetric. A sum $H + G$ of two symmetric matrices is symmetric because $h_{i, j} + g_{i, j} = h_{j, i} + g_{j, i}$ (since $h_{i, j} = h_{j, i}$ and $g_{i, j} = g_{j, i}$ ). Thus the subset is nonempty and closed under the inherited operations, and so it is a subspace.
Exercise 1.18 Worked answer

Recommended.
1. How does matrix rank interact with scalar multiplication—can a scalar product of a rank $n$ matrix have rank less than $n$ ? Greater?
2. How does matrix rank interact with matrix addition—can a sum of rank $n$ matrices have rank less than $n$ ? Greater?
Back to Exercise 1.18

Answer.
1. Scalar multiplication leaves the rank of a matrix unchanged except that multiplication by zero leaves the matrix with rank zero. (This follows from the first theorem of the book, that multiplying a row by a nonzero scalar doesn’t change the solution set of the associated linear system.)
2. A sum of rank $n$ matrices can have rank less than $n$ . For instance, for any matrix $H$ , the sum $H + (- 1) \cdot H$ has rank zero.
  
  A sum of rank $n$ matrices can have rank greater than $n$ . Here are rank one matrices that sum to a rank two matrix.
  
  $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) + (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$

Matrix Multiplication

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

Lemma 2.1 The composition of linear maps is linear.

Proof (Note: this argument has already appeared, as part of the proof of Theorem I.2.2.) Let $h : V \to W$ and $g : W \to U$ be linear. The calculation

$\begin{matrix} g \circ h (c_{1} \cdot {\vec{v}}_{1} + c_{2} \cdot {\vec{v}}_{2}) = g (h (c_{1} \cdot {\vec{v}}_{1} + c_{2} \cdot {\vec{v}}_{2})) = g (c_{1} \cdot h ({\vec{v}}_{1}) + c_{2} \cdot h ({\vec{v}}_{2})) \\ = c_{1} \cdot g (h ({\vec{v}}_{1})) + c_{2} \cdot g (h ({\vec{v}}_{2})) = c_{1} \cdot (g \circ h) ({\vec{v}}_{1}) + c_{2} \cdot (g \circ h) ({\vec{v}}_{2}) \end{matrix}$

shows that $g \circ h : V \to U$ preserves linear combinations, and so is linear.

QED

As we did with the operation of matrix addition and scalar multiplication, we will see how the representation of the composite relates to the representations of the compositors by first considering an example.

Example 2.2 Let $h : ℝ^{4} \to ℝ^{2}$ and $g : ℝ^{2} \to ℝ^{3}$ , fix bases $B \subset ℝ^{4}$ , $C \subset ℝ^{2}$ , $D \subset ℝ^{3}$ , and let these be the representations.

$H = {Rep}_{B, C} (h) = {(\begin{matrix} 4 & 6 & 8 & 2 \\ 5 & 7 & 9 & 3 \end{matrix})}_{B, C} G = {Rep}_{C, D} (g) = {(\begin{matrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{matrix})}_{C, D}$

To represent the composition $g \circ h : ℝ^{4} \to ℝ^{3}$ we start with a $\vec{v}$ , represent $h$ of $\vec{v}$ , and then represent $g$ of that. The representation of $h (\vec{v})$ is the product of $h$ ’s matrix and $\vec{v}$ ’s vector.

${Rep}_{C} (h (\vec{v})) = {(\begin{matrix} 4 & 6 & 8 & 2 \\ 5 & 7 & 9 & 3 \end{matrix})}_{B, C} {(\begin{matrix} v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \end{matrix})}_{B} = {(\begin{matrix} 4 v_{1} + 6 v_{2} + 8 v_{3} + 2 v_{4} \\ 5 v_{1} + 7 v_{2} + 9 v_{3} + 3 v_{4} \end{matrix})}_{C}$

The representation of $g (h (\vec{v}))$ is the product of $g$ ’s matrix and $h (\vec{v})$ ’s vector.

$\begin{matrix} {Rep}_{D} (g (h (\vec{v}))) = {(\begin{matrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{matrix})}_{C, D} {(\begin{matrix} 4 v_{1} + 6 v_{2} + 8 v_{3} + 2 v_{4} \\ 5 v_{1} + 7 v_{2} + 9 v_{3} + 3 v_{4} \end{matrix})}_{C} \\ = {(\begin{matrix} 1 \cdot (4 v_{1} + 6 v_{2} + 8 v_{3} + 2 v_{4}) + 1 \cdot (5 v_{1} + 7 v_{2} + 9 v_{3} + 3 v_{4}) \\ 0 \cdot (4 v_{1} + 6 v_{2} + 8 v_{3} + 2 v_{4}) + 1 \cdot (5 v_{1} + 7 v_{2} + 9 v_{3} + 3 v_{4}) \\ 1 \cdot (4 v_{1} + 6 v_{2} + 8 v_{3} + 2 v_{4}) + 0 \cdot (5 v_{1} + 7 v_{2} + 9 v_{3} + 3 v_{4}) \end{matrix})}_{D} \end{matrix}$

Distributing and regrouping on the $v$ ’s gives

$= {(\begin{matrix} (1 \cdot 4 + 1 \cdot 5) v_{1} + (1 \cdot 6 + 1 \cdot 7) v_{2} + (1 \cdot 8 + 1 \cdot 9) v_{3} + (1 \cdot 2 + 1 \cdot 3) v_{4} \\ (0 \cdot 4 + 1 \cdot 5) v_{1} + (0 \cdot 6 + 1 \cdot 7) v_{2} + (0 \cdot 8 + 1 \cdot 9) v_{3} + (0 \cdot 2 + 1 \cdot 3) v_{4} \\ (1 \cdot 4 + 0 \cdot 5) v_{1} + (1 \cdot 6 + 0 \cdot 7) v_{2} + (1 \cdot 8 + 0 \cdot 9) v_{3} + (1 \cdot 2 + 0 \cdot 3) v_{4} \end{matrix})}_{D}$

which is this matrix-vector product.

$= {(\begin{matrix} 1 \cdot 4 + 1 \cdot 5 & 1 \cdot 6 + 1 \cdot 7 & 1 \cdot 8 + 1 \cdot 9 & 1 \cdot 2 + 1 \cdot 3 \\ 0 \cdot 4 + 1 \cdot 5 & 0 \cdot 6 + 1 \cdot 7 & 0 \cdot 8 + 1 \cdot 9 & 0 \cdot 2 + 1 \cdot 3 \\ 1 \cdot 4 + 0 \cdot 5 & 1 \cdot 6 + 0 \cdot 7 & 1 \cdot 8 + 0 \cdot 9 & 1 \cdot 2 + 0 \cdot 3 \end{matrix})}_{B, D} {(\begin{matrix} v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \end{matrix})}_{B}$

The matrix representing $g \circ h$ has the rows of $G$ combined with the columns of $H$ .

Definition 2.3 The matrix-multiplicative product of the $m \times r$ matrix $G$ and the $r \times n$ matrix $H$ is the $m \times n$ matrix $P$ , where

$p_{i, j} = g_{i, 1} h_{1, j} + g_{i, 2} h_{2, j} + \dots + g_{i, r} h_{r, j}$

so that the $i, j$ -th entry of the product is the dot product of the $i$ -th row of the first matrix with the $j$ -th column of the second.

$G H = (\begin{matrix} ⋮ \\ g_{i, 1} & g_{i, 2} & \dots & g_{i, r} \\ ⋮ \end{matrix}) (\begin{matrix} h_{1, j} \\ \dots & h_{2, j} & \dots \\ ⋮ \\ h_{r, j} \end{matrix}) = (\begin{matrix} ⋮ \\ \dots & p_{i, j} & \dots \\ ⋮ \end{matrix})$

Example 2.4 $(\begin{matrix} 2 & 0 \\ 4 & 6 \\ 8 & 2 \end{matrix}) (\begin{matrix} 1 & 3 \\ 5 & 7 \end{matrix}) = (\begin{matrix} 2 \cdot 1 + 0 \cdot 5 & 2 \cdot 3 + 0 \cdot 7 \\ 4 \cdot 1 + 6 \cdot 5 & 4 \cdot 3 + 6 \cdot 7 \\ 8 \cdot 1 + 2 \cdot 5 & 8 \cdot 3 + 2 \cdot 7 \end{matrix}) = (\begin{matrix} 2 & 6 \\ 34 & 54 \\ 18 & 38 \end{matrix})$

Example 2.5 Some products are not defined, such as the product of a $2 \times 3$ matrix with a $2 \times 2$ , because the number of columns in the first matrix must equal the number of rows in the second. But the product of two $n \times n$ matrices is always defined. Here are two $2 \times 2$ ’s.

$(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} - 1 & 0 \\ 2 & - 2 \end{matrix}) = (\begin{matrix} 1 \cdot (- 1) + 2 \cdot 2 & 1 \cdot 0 + 2 \cdot (- 2) \\ 3 \cdot (- 1) + 4 \cdot 2 & 3 \cdot 0 + 4 \cdot (- 2) \end{matrix}) = (\begin{matrix} 3 & - 4 \\ 5 & - 8 \end{matrix})$

Example 2.6 The matrices from Example 2.2 combine in this way.

$\begin{matrix} (\begin{matrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 4 & 6 & 8 & 2 \\ 5 & 7 & 9 & 3 \end{matrix}) \\ \begin{aligned} = (\begin{array}{c} 1 \cdot 4 + 1 \cdot 5 & 1 \cdot 6 + 1 \cdot 7 & 1 \cdot 8 + 1 \cdot 9 & 1 \cdot 2 + 1 \cdot 3 \\ 0 \cdot 4 + 1 \cdot 5 & 0 \cdot 6 + 1 \cdot 7 & 0 \cdot 8 + 1 \cdot 9 & 0 \cdot 2 + 1 \cdot 3 \\ 1 \cdot 4 + 0 \cdot 5 & 1 \cdot 6 + 0 \cdot 7 & 1 \cdot 8 + 0 \cdot 9 & 1 \cdot 2 + 0 \cdot 3 \end{array}) \\ = (\begin{array}{c} 9 & 13 & 17 & 5 \\ 5 & 7 & 9 & 3 \\ 4 & 6 & 8 & 2 \end{array}) \end{aligned} \end{matrix}$

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

Proof This argument generalizes Example 2.2. Let $h : V \to W$ and $g : W \to X$ be represented by $H$ and $G$ with respect to bases $B \subset V$ , $C \subset W$ , and $D \subset X$ , of sizes $n$ , $r$ , and $m$ . For any $\vec{v} \in V$ the $k$ -th component of ${Rep}_{C} (h (\vec{v}))$ is

$h_{k, 1} v_{1} + \dots + h_{k, n} v_{n}$

and so the $i$ -th component of ${Rep}_{D} (g \circ h (\vec{v}))$ is this.

$\begin{matrix} g_{i, 1} \cdot (h_{1, 1} v_{1} + \dots + h_{1, n} v_{n}) + g_{i, 2} \cdot (h_{2, 1} v_{1} + \dots + h_{2, n} v_{n}) \\ + \dots + g_{i, r} \cdot (h_{r, 1} v_{1} + \dots + h_{r, n} v_{n}) \end{matrix}$

Distribute and regroup on the $v$ ’s.

$\begin{matrix} = (g_{i, 1} h_{1, 1} + g_{i, 2} h_{2, 1} + \dots + g_{i, r} h_{r, 1}) \cdot v_{1} \\ + \dots + (g_{i, 1} h_{1, n} + g_{i, 2} h_{2, n} + \dots + g_{i, r} h_{r, n}) \cdot v_{n} \end{matrix}$

Finish by recognizing that the coefficient of each $v_{j}$

$g_{i, 1} h_{1, j} + g_{i, 2} h_{2, j} + \dots + g_{i, r} h_{r, j}$

matches the definition of the $i, j$ entry of the product $G H$ .

QED

This arrow diagram pictures the relationship between maps and matrices (‘wrt’ abbreviates ‘with respect to’).

Commutative triangle: V with basis B maps by h, represented by H, to W with basis C, then by g, represented by G, to X with basis D. The direct path is g composed with h, represented by GH.

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

$\vec{v} \overset{g \circ h}{⟼} g (h (\vec{v})) \vec{v} \overset{h}{⟼} h (\vec{v}) \overset{g}{⟼} g (h (\vec{v}))$

(this is just the definition of composition). Below the arrows, the matrices indicate that multiplying $G H$ into the column vector ${Rep}_{B} (\vec{v})$ has the same effect as multiplying the column vector first by $H$ and then multiplying the result by $G$ .

${Rep}_{B, D} (g \circ h) = G H {Rep}_{C, D} (g) {Rep}_{B, C} (h) = G H$

As mentioned in Example 2.5, because the number of columns on the left does not equal the number of rows on the right, the product as here of a $2 \times 3$ matrix with a $2 \times 2$ matrix is not defined.

$(\begin{matrix} - 1 & 2 & 0 \\ 0 & 10 & 1.1 \end{matrix}) (\begin{matrix} 0 & 0 \\ 0 & 2 \end{matrix})$

The definition requires that the sizes match because we want that the underlying function composition is possible.

$\begin{matrix} dimension n space \overset{h}{⟶} dimension r space \overset{g}{⟶} dimension m space & (*) \end{matrix}$

Thus, matrix product combines the $m \times r$ matrix $G$ with the $r \times n$ matrix $F$ to yield the $m \times n$ result $G F$ . Briefly: $m \times r times r \times n equals m \times n$ .

Remark 2.8 The order of the dimensions can be confusing. In ‘ $m \times r times r \times n equals m \times n$ ’ the number written first is $m$ . But $m$ appears last in the map dimension description line ( $*$ ) above, and the other dimensions also appear in reverse. The explanation is that while $h$ is done first, followed by $g$ , we write the composition as $g \circ h$ , with $g$ on the left (arising from the notation $g (h (\vec{v}))$ ). That carries over to matrices, so that $g \circ h$ is represented by $G H$ .

We can get insight into matrix-matrix product operation by studying how the entries combine. For instance, an alternative way to understand why we require above that the sizes match is that the row of the left-hand matrix must have the same number of entries as the column of the right-hand matrix, or else some entry will be left without a matching entry from the other matrix.

Another aspect of the combinatorics of matrix multiplication, in the sum defining the $i, j$ entry, is brought out here by the boxing the equal subscripts.

$p_{i, j} = g_{i, 1} h_{1, j} + g_{i, 2} h_{2, j} + \dots + g_{i, r} h_{r, j}$

The highlighted subscripts on the $g$ ’s are column indices while those on the $h$ ’s are for rows. That is, the summation takes place over the columns of $G$ but over the rows of $H$ — the definition treats left differently than right. So we may reasonably suspect that $G H$ can be unequal to $H G$ .

Example 2.9 Matrix multiplication is not commutative.

$(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix}) = (\begin{matrix} 19 & 22 \\ 43 & 50 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) = (\begin{matrix} 23 & 34 \\ 31 & 46 \end{matrix})$

Example 2.10 Commutativity can fail more dramatically:

$(\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix}) (\begin{matrix} 1 & 2 & 0 \\ 3 & 4 & 0 \end{matrix}) = (\begin{matrix} 23 & 34 & 0 \\ 31 & 46 & 0 \end{matrix})$

while

$(\begin{matrix} 1 & 2 & 0 \\ 3 & 4 & 0 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix})$

isn’t even defined.

Remark 2.11 The fact that matrix multiplication is not commutative can seem odd at first, perhaps because most mathematical operations in prior courses are commutative. But matrix multiplication represents function composition and function composition is not commutative: if $f (x) = 2 x$ and $g (x) = x + 1$ then $g \circ f (x) = 2 x + 1$ while $f \circ g (x) = 2 (x + 1) = 2 x + 2$ .

Except for the lack of commutativity, matrix multiplication is algebraically well-behaved. The next result gives some nice properties and more are in Exercise 2.25 and Exercise 2.26.

Theorem 2.12 If $F$ , $G$ , and $H$ are matrices, and the matrix products are defined, then the product is associative $(F G) H = F (G H)$ and distributes over matrix addition $F (G + H) = F G + F H$ and $(G + H) F = G F + H F$ .

Proof Associativity holds because matrix multiplication represents function composition, which is associative: the maps $(f \circ g) \circ h$ and $f \circ (g \circ h)$ are equal as both send $\vec{v}$ to $f (g (h (\vec{v})))$ .

Distributivity is similar. For instance, the first one goes $f \circ (g + h) (\vec{v}) = f ((g + h) (\vec{v})) = f (g (\vec{v}) + h (\vec{v})) = f (g (\vec{v})) + f (h (\vec{v})) = f \circ g (\vec{v}) + f \circ h (\vec{v})$ (the third equality uses the linearity of $f$ ). Right-distributivity goes the same way.

QED

Remark 2.13 We could instead prove that result by slogging through indices. For example, for associativity the $i, j$ entry of $(F G) H$ is

$\begin{aligned} (f_{i, 1} g_{1, 1} + f_{i, 2} g_{2, 1} + \dots + f_{i, r} g_{r, 1}) h_{1, j} \\ + (f_{i, 1} g_{1, 2} + f_{i, 2} g_{2, 2} + \dots + f_{i, r} g_{r, 2}) h_{2, j} \\ ⋮ \\ + (f_{i, 1} g_{1, s} + f_{i, 2} g_{2, s} + \dots + f_{i, r} g_{r, s}) h_{s, j} \end{aligned}$

where $F$ , $G$ , and $H$ are $m \times r$ , $r \times s$ , and $s \times n$ matrices. Distribute

$\begin{aligned} f_{i, 1} g_{1, 1} h_{1, j} + f_{i, 2} g_{2, 1} h_{1, j} + \dots + f_{i, r} g_{r, 1} h_{1, j} \\ + f_{i, 1} g_{1, 2} h_{2, j} + f_{i, 2} g_{2, 2} h_{2, j} + \dots + f_{i, r} g_{r, 2} h_{2, j} \\ ⋮ \\ + f_{i, 1} g_{1, s} h_{s, j} + f_{i, 2} g_{2, s} h_{s, j} + \dots + f_{i, r} g_{r, s} h_{s, j} \end{aligned}$

and regroup around the $f$ ’s

$\begin{aligned} f_{i, 1} (g_{1, 1} h_{1, j} + g_{1, 2} h_{2, j} + \dots + g_{1, s} h_{s, j}) \\ + f_{i, 2} (g_{2, 1} h_{1, j} + g_{2, 2} h_{2, j} + \dots + g_{2, s} h_{s, j}) \\ ⋮ \\ + f_{i, r} (g_{r, 1} h_{1, j} + g_{r, 2} h_{2, j} + \dots + g_{r, s} h_{s, j}) \end{aligned}$

to get the $i, j$ entry of $F (G H)$ .

Contrast the two proofs. The index-heavy argument is hard to understand in that while the calculations are easy to check, the arithmetic seems unconnected to any idea. The argument in the proof is shorter and also says why this property “really” holds. This illustrates the comments made at the start of the chapter on vector spaces—at least sometimes an argument from higher-level constructs is clearer.

We have now seen how to represent the composition of linear maps. The next subsection will continue to explore this operation.

Exercises

Exercise 2.14 Worked answer

Recommended. Compute, or state “not defined”.
1. $(\begin{matrix} 3 & 1 \\ - 4 & 2 \end{matrix}) (\begin{matrix} 0 & 5 \\ 0 & 0.5 \end{matrix})$
2. $(\begin{matrix} 1 & 1 & - 1 \\ 4 & 0 & 3 \end{matrix}) (\begin{matrix} 2 & - 1 & - 1 \\ 3 & 1 & 1 \\ 3 & 1 & 1 \end{matrix})$
3. $(\begin{matrix} 2 & - 7 \\ 7 & 4 \end{matrix}) (\begin{matrix} 1 & 0 & 5 \\ - 1 & 1 & 1 \\ 3 & 8 & 4 \end{matrix})$
4. $(\begin{matrix} 5 & 2 \\ 3 & 1 \end{matrix}) (\begin{matrix} - 1 & 2 \\ 3 & - 5 \end{matrix})$
Back to Exercise 2.14

Answer.
1. $(\begin{matrix} 0 & 15.5 \\ 0 & - 19 \end{matrix})$
2. $(\begin{matrix} 2 & - 1 & - 1 \\ 17 & - 1 & - 1 \end{matrix})$
3. Not defined.
4. $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$
Exercise 2.15 Worked answer

Recommended. Where

$A = (\begin{matrix} 1 & - 1 \\ 2 & 0 \end{matrix}) B = (\begin{matrix} 5 & 2 \\ 4 & 4 \end{matrix}) C = (\begin{matrix} - 2 & 3 \\ - 4 & 1 \end{matrix})$

compute or state “not defined.”
1. $A B$
2. $(A B) C$
3. $B C$
4. $A (B C)$
Back to Exercise 2.15

Answer.
1. $(\begin{matrix} 1 & - 2 \\ 10 & 4 \end{matrix})$
2. $(\begin{matrix} 1 & - 2 \\ 10 & 4 \end{matrix}) (\begin{matrix} - 2 & 3 \\ - 4 & 1 \end{matrix}) = (\begin{matrix} 6 & 1 \\ - 36 & 34 \end{matrix})$
3. $(\begin{matrix} - 18 & 17 \\ - 24 & 16 \end{matrix})$
4. $(\begin{matrix} 1 & - 1 \\ 2 & 0 \end{matrix}) (\begin{matrix} - 18 & 17 \\ - 24 & 16 \end{matrix}) = (\begin{matrix} 6 & 1 \\ - 36 & 34 \end{matrix})$
Exercise 2.16 Worked answer

Which products are defined?
1. $3 \times 2$ times $2 \times 3$
2. $2 \times 3$ times $3 \times 2$
3. $2 \times 2$ times $3 \times 3$
4. $3 \times 3$ times $2 \times 2$
Back to Exercise 2.16

Answer.
1. Yes.
2. Yes.
3. No.
4. No.
Exercise 2.17 Worked answer

Recommended. Give the size of the product or state “not defined”.
1. a $2 \times 3$ matrix times a $3 \times 1$ matrix
2. a $1 \times 12$ matrix times a $12 \times 1$ matrix
3. a $2 \times 3$ matrix times a $2 \times 1$ matrix
4. a $2 \times 2$ matrix times a $2 \times 2$ matrix
Back to Exercise 2.17

Answer.
1. $2 \times 1$
2. $1 \times 1$
3. Not defined.
4. $2 \times 2$
Exercise 2.18 Worked answer

Recommended. Find the system of equations resulting from starting with

$\begin{array}{rcrcrcr} h_{1, 1} x_{1} & + & h_{1, 2} x_{2} & + & h_{1, 3} x_{3} & = & d_{1} \\ h_{2, 1} x_{1} & + & h_{2, 2} x_{2} & + & h_{2, 3} x_{3} & = & d_{2} \end{array}$

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

$\begin{array}{rcrcr} x_{1} & = & g_{1, 1} y_{1} & + & g_{1, 2} y_{2} \\ x_{2} & = & g_{2, 1} y_{1} & + & g_{2, 2} y_{2} \\ x_{3} & = & g_{3, 1} y_{1} & + & g_{3, 2} y_{2} \end{array}$

Back to Exercise 2.18

Answer. We have

$\begin{array}{rcrcrcr} h_{1, 1} \cdot (g_{1, 1} y_{1} + g_{1, 2} y_{2}) & + & h_{1, 2} \cdot (g_{2, 1} y_{1} + g_{2, 2} y_{2}) & + & h_{1, 3} \cdot (g_{3, 1} y_{1} + g_{3, 2} y_{2}) & = & d_{1} \\ h_{2, 1} \cdot (g_{1, 1} y_{1} + g_{1, 2} y_{2}) & + & h_{2, 2} \cdot (g_{2, 1} y_{1} + g_{2, 2} y_{2}) & + & h_{2, 3} \cdot (g_{3, 1} y_{1} + g_{3, 2} y_{2}) & = & d_{2} \end{array}$

which, after expanding and regrouping about the $y$ ’s yields this.

$\begin{array}{rcrcr} (h_{1, 1} g_{1, 1} + h_{1, 2} g_{2, 1} + h_{1, 3} g_{3, 1}) y_{1} & + & (h_{1, 1} g_{1, 2} + h_{1, 2} g_{2, 2} + h_{1, 3} g_{3, 2}) y_{2} & = & d_{1} \\ (h_{2, 1} g_{1, 1} + h_{2, 2} g_{2, 1} + h_{2, 3} g_{3, 1}) y_{1} & + & (h_{2, 1} g_{1, 2} + h_{2, 2} g_{2, 2} + h_{2, 3} g_{3, 2}) y_{2} & = & d_{2} \end{array}$

We can express the starting system and the system used for the substitutions in matrix language, as

$(\begin{matrix} h_{1, 1} & h_{1, 2} & h_{1, 3} \\ h_{2, 1} & h_{2, 2} & h_{2, 3} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = H (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} d_{1} \\ d_{2} \end{matrix})$

and

$(\begin{matrix} g_{1, 1} & g_{1, 2} \\ g_{2, 1} & g_{2, 2} \\ g_{3, 1} & g_{3, 2} \end{matrix}) (\begin{matrix} y_{1} \\ y_{2} \end{matrix}) = G (\begin{matrix} y_{1} \\ y_{2} \end{matrix}) = (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix})$

and with this, the substitution is $\vec{d} = H \vec{x} = H (G \vec{y}) = (H G) \vec{y}$ .
Exercise 2.19 Worked answer

Recommended. Consider the two linear functions $h : ℝ^{3} \to 𝒫_{2}$ and $g : 𝒫_{2} \to ℳ_{2 \times 2}$ given as here.

$(\begin{matrix} a \\ b \\ c \end{matrix}) \mapsto (a + b) x^{2} + (2 a + 2 b) x + c p x^{2} + q x + r \mapsto (\begin{matrix} p & p - 2 q \\ q & 0 \end{matrix})$

Use these bases for the spaces.

$\begin{matrix} B = ⟨ (\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) ⟩ C = ⟨ 1 + x, 1 - x, x^{2} ⟩ \\ D = ⟨ (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 2 \\ 0 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 3 & 0 \end{matrix}), (\begin{matrix} 0 & 0 \\ 0 & 4 \end{matrix}) ⟩ \end{matrix}$
1. Give the formula for the composition map $g \circ h : ℝ^{3} \to ℳ_{2 \times 2}$ derived directly from the above definition.
2. Represent $h$ and $g$ with respect to the appropriate bases.
3. Represent the map $g \circ h$ computed in the first part with respect to the appropriate bases.
4. Check that the product of the two matrices from the second part is the matrix from the third part.
Back to Exercise 2.19

Answer.
1. Following the definitions gives this.
  
  $\begin{aligned} (\begin{array}{c} a \\ b \\ c \end{array}) & \mapsto (a + b) x^{2} + (2 a + 2 b) x + c \\ \mapsto (\begin{array}{c} a + b & (a + b) - 2 (2 a + 2 b) \\ 2 a + 2 b & 0 \end{array}) = (\begin{array}{c} a + b & - 3 a - 3 b \\ 2 a + 2 b & 0 \end{array}) \end{aligned}$
2. Because
  
  $(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}) \mapsto 2 x^{2} + 4 x + 1 (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) \mapsto x^{2} + 2 x + 1 (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) \mapsto 0 x^{2} + 0 x + 1$
  
  we get this representation for $h$ .
  
  ${Rep}_{B, C} (h) = (\begin{matrix} 5 / 2 & 3 / 2 & 1 / 2 \\ - 3 / 2 & - 1 / 2 & 1 / 2 \\ 2 & 1 & 0 \end{matrix})$
  
  Similarly, because
  
  $1 + x \mapsto (\begin{matrix} 0 & - 2 \\ 1 & 0 \end{matrix}) 1 - x \mapsto (\begin{matrix} 0 & 2 \\ - 1 & 0 \end{matrix}) x^{2} \mapsto (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$
  
  this is the representation of $g$ .
  
  ${Rep}_{C, D} (g) = (\begin{matrix} 0 & 0 & 1 \\ - 1 & 1 & 1 / 2 \\ 1 / 3 & - 1 / 3 & 0 \\ 0 & 0 & 0 \end{matrix})$
3. The action of $g \circ h$ on the domain basis is this.
  
  $(\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}) \mapsto (\begin{matrix} 2 & - 6 \\ 4 & 0 \end{matrix}) (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) \mapsto (\begin{matrix} 1 & - 3 \\ 2 & 0 \end{matrix}) (\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) \mapsto (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$
  
  We have this.
  
  ${Rep}_{B, D} (g \circ h) = (\begin{matrix} 2 & 1 & 0 \\ - 3 & - 3 / 2 & 0 \\ 4 / 3 & 2 / 3 & 0 \\ 0 & 0 & 0 \end{matrix})$
4. The matrix multiplication is routine, just take care with the order.
  
  $(\begin{matrix} 0 & 0 & 1 \\ - 1 & 1 & 1 / 2 \\ 1 / 3 & - 1 / 3 & 0 \\ 0 & 0 & 0 \end{matrix}) (\begin{matrix} 5 / 2 & 3 / 2 & 1 / 2 \\ - 3 / 2 & - 1 / 2 & 1 / 2 \\ 2 & 1 & 0 \end{matrix}) = (\begin{matrix} 2 & 1 & 0 \\ - 3 & - 3 / 2 & 0 \\ 4 / 3 & 2 / 3 & 0 \\ 0 & 0 & 0 \end{matrix})$
Exercise 2.20 Worked answer

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

Back to Exercise 2.20

Answer. Technically, no. The dot product operation yields a scalar while the matrix product yields a $1 \times 1$ matrix. However, we usually will ignore the distinction.
Exercise 2.21 Worked answer

Recommended. Represent the derivative map on $𝒫_{n}$ with respect to $B, B$ where $B$ is the natural basis $⟨ 1, x, \dots, x^{n} ⟩$ . Show that the product of this matrix with itself is defined; what map does it represent?

Back to Exercise 2.21

Answer. The action of $d / d x$ on $B$ is $1 \mapsto 0$ , $x \mapsto 1$ , $x^{2} \mapsto 2 x$ , …and so this is its $(n + 1) \times (n + 1)$ matrix representation.

${Rep}_{B, B} (\frac{d}{d x}) = (\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ ⋱ \\ 0 & 0 & 0 & n \\ 0 & 0 & 0 & 0 \end{matrix})$

The product of this matrix with itself is defined because the matrix is square.

${(\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ ⋱ \\ 0 & 0 & 0 & n \\ 0 & 0 & 0 & 0 \end{matrix})}^{2} = (\begin{matrix} 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 6 & 0 \\ ⋱ \\ 0 & 0 & 0 & n (n - 1) \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})$

The map so represented is the composition

$p \overset{\frac{d}{d x}}{⟼} \frac{d p}{d x} \overset{\frac{d}{d x}}{⟼} \frac{d^{2} p}{d x^{2}}$

which is the second derivative operation.
Exercise 2.22 Worked answer

[Cleary] Match each type of matrix with all these descriptions that could fit, say ‘None’ if it applies: (i) can be multiplied by its transpose to make a $1 \times 1$ matrix, (ii) can represent a linear map from $ℝ^{3}$ to $ℝ^{2}$ that is not onto, (iii) can represent an isomorphism from $ℝ^{3}$ to $𝒫^{2}$ .
1. a $2 \times 3$ matrix whose rank is $1$
2. a $3 \times 3$ matrix that is nonsingular
3. a $2 \times 2$ matrix that is singular
4. an $n \times 1$ column vector
Back to Exercise 2.22

Answer.
1. ii
2. iii
3. None
4. None, or (i) if we include multiplication from the left.
Exercise 2.23 Worked answer

Show that composition of linear transformations on $ℝ^{1}$ is commutative. Is this true for any one-dimensional space?

Back to Exercise 2.23

Answer. It is true for all one-dimensional spaces. Let $f$ and $g$ be transformations of a one-dimensional space. We must show that $g \circ f (\vec{v}) = f \circ g (\vec{v})$ for all vectors. Fix a basis $B$ for the space and then the transformations are represented by $1 \times 1$ matrices.

$F = {Rep}_{B, B} (f) = (\begin{matrix} f_{1, 1} \end{matrix}) G = {Rep}_{B, B} (g) = (\begin{matrix} g_{1, 1} \end{matrix})$

Therefore, the compositions can be represented as $G F$ and $F G$ .

$G F = {Rep}_{B, B} (g \circ f) = (\begin{matrix} g_{1, 1} f_{1, 1} \end{matrix}) F G = {Rep}_{B, B} (f \circ g) = (\begin{matrix} f_{1, 1} g_{1, 1} \end{matrix})$

These two matrices are equal and so the compositions have the same effect on each vector in the space.
Exercise 2.24 Worked answer

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

Back to Exercise 2.24

Answer. It would not represent linear map composition; Theorem 2.7 would fail.
Exercise 2.25 Worked answer
1. Prove that $H^{p} H^{q} = H^{p + q}$ and $(H^{p})^{q} = H^{p q}$ for positive integers $p, q$ .
2. Prove that $(r H)^{p} = r^{p} \cdot H^{p}$ for any positive integer $p$ and scalar $r \in ℝ$ .
Back to Exercise 2.25

Answer. Each follows easily from the associated map fact. For instance, $p$ applications of the transformation $h$ , following $q$ applications, is simply $p + q$ applications.
Exercise 2.26 Worked answer

Recommended.
1. How does matrix multiplication interact with scalar multiplication: is $r (G H) = (r G) H$ ? Is $G (r H) = r (G H)$ ?
2. How does matrix multiplication interact with linear combinations: is $F (r G + s H) = r (F G) + s (F H)$ ? Is $(r F + s G) H = r F H + s G H$ ?
Back to Exercise 2.26

Answer. Although we can do these by going through the indices, they are best understood in terms of the represented maps. That is, fix spaces and bases so that the matrices represent linear maps $f, g, h$ .
1. Yes; we have both $r \cdot (g \circ h) (\vec{v}) = r \cdot g (h (\vec{v})) = (r \cdot g) \circ h (\vec{v})$ and $g \circ (r \cdot h) (\vec{v}) = g (r \cdot h (\vec{v})) = r \cdot g (h (\vec{v})) = r \cdot (g \circ h) (\vec{v})$ (the second equality holds because of the linearity of $g$ ).
2. Both answers are yes. First, $f \circ (r g + s h)$ and $r \cdot (f \circ g) + s \cdot (f \circ h)$ both send $\vec{v}$ to $r \cdot f (g (\vec{v})) + s \cdot f (h (\vec{v}))$ ; the calculation is as in the prior item (using the linearity of $f$ for the first one). For the other, $(r f + s g) \circ h$ and $r \cdot (f \circ h) + s \cdot (g \circ h)$ both send $\vec{v}$ to $r \cdot f (h (\vec{v})) + s \cdot g (h (\vec{v}))$ .
Exercise 2.27 Worked answer

We can ask how the matrix product operation interacts with the transpose operation.
1. Show that ${(G H)}^{𝖳} = H^{𝖳} G^{𝖳}$ .
2. A square matrix is symmetric if each $i, j$ entry equals the $j, i$ entry, that is, if the matrix equals its own transpose. Show that the matrices $H H^{𝖳}$ and $H^{𝖳} H$ are symmetric.
Back to Exercise 2.27

Answer. We have not seen a map interpretation of the transpose operation, so we will verify these by considering the entries.
1. The $i, j$ entry of ${G H}^{𝖳}$ is the $j, i$ entry of $G H$ , which is the dot product of the $j$ -th row of $G$ and the $i$ -th column of $H$ . The $i, j$ entry of $H^{𝖳} G^{𝖳}$ is the dot product of the $i$ -th row of $H^{𝖳}$ and the $j$ -th column of $G^{𝖳}$ , which is the dot product of the $i$ -th column of $H$ and the $j$ -th row of $G$ . Dot product is commutative and so these two are equal.
2. By the prior item each equals its transpose, e.g., ${(H H^{𝖳})}^{𝖳} = {H^{𝖳}}^{𝖳} H^{𝖳} = H H^{𝖳}$ .
Exercise 2.28 Worked answer

Recommended. Rotation of vectors in $ℝ^{3}$ about an axis is a linear map. Show that linear maps do not commute by showing geometrically that rotations do not commute.

Back to Exercise 2.28

Answer. Consider $r_{x}, r_{y} : ℝ^{3} \to ℝ^{3}$ rotating all vectors $π / 2$ radians counterclockwise about the $x$ and $y$ axes (counterclockwise in the sense that a person whose head is at ${\vec{e}}_{1}$ or ${\vec{e}}_{2}$ and whose feet are at the origin sees, when looking toward the origin, the rotation as counterclockwise).

Rotating $r_{x}$ first and then $r_{y}$ is different than rotating $r_{y}$ first and then $r_{x}$ . In particular, $r_{x} ({\vec{e}}_{3}) = - {\vec{e}}_{2}$ so $r_{y} \circ r_{x} ({\vec{e}}_{3}) = - {\vec{e}}_{2}$ , while $r_{y} ({\vec{e}}_{3}) = {\vec{e}}_{1}$ so $r_{x} \circ r_{y} ({\vec{e}}_{3}) = {\vec{e}}_{1}$ , and hence the maps do not commute.
Exercise 2.29 Worked answer

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

Back to Exercise 2.29

Answer. It doesn’t matter (as long as the spaces have the appropriate dimensions).

For associativity, suppose that $F$ is $m \times r$ , that $G$ is $r \times n$ , and that $H$ is $n \times k$ . We can take any $r$ dimensional space, any $m$ dimensional space, any $n$ dimensional space, and any $k$ dimensional space—for instance, $ℝ^{r}$ , $ℝ^{m}$ , $ℝ^{n}$ , and $ℝ^{k}$ will do. We can take any bases $A$ , $B$ , $C$ , and $D$ , for those spaces. Then, with respect to $C, D$ the matrix $H$ represents a linear map $h$ , with respect to $B, C$ the matrix $G$ represents a $g$ , and with respect to $A, B$ the matrix $F$ represents an $f$ . We can use those maps in the proof.

The second half is similar, except that we add $G$ and $H$ and so we must take them to represent maps with the same domain and codomain.
Exercise 2.30 Worked answer

How does matrix rank interact with matrix multiplication?
1. Can the product of rank $n$ matrices have rank less than $n$ ? Greater?
2. Show that the rank of the product of two matrices is less than or equal to the minimum of the rank of each factor.
Back to Exercise 2.30

Answer.
1. The product of rank $n$ matrices can have rank less than or equal to $n$ but not greater than $n$ .
  
  To see that the rank can fall, consider the maps $π_{x}, π_{y} : ℝ^{2} \to ℝ^{2}$ projecting onto the axes. Each is rank one but their composition $π_{x} \circ π_{y}$ , which is the zero map, is rank zero. That translates over to matrices representing those maps in this way.
  
  ${Rep}_{ℰ_{2}, ℰ_{2}} (π_{x}) \cdot {Rep}_{ℰ_{2}, ℰ_{2}} (π_{y}) = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$
  
  To prove that the product of rank $n$ matrices cannot have rank greater than $n$ , we can apply the map result that the image of a linearly dependent set is linearly dependent. That is, if $h : V \to W$ and $g : W \to X$ both have rank $n$ then a set in the range $ℛ (g \circ h)$ of size larger than $n$ is the image under $g$ of a set in $W$ of size larger than $n$ and so is linearly dependent (since the rank of $h$ is $n$ ). Now, the image of a linearly dependent set is dependent, so any set of size larger than $n$ in the range is dependent. (By the way, observe that the rank of $g$ was not mentioned. See the next part.)
2. Fix spaces and bases and consider the associated linear maps $f$ and $g$ . Recall that the dimension of the image of a map (the map’s rank) is less than or equal to the dimension of the domain, and consider the arrow diagram.
  
  $\begin{matrix} V & \overset{f}{⟼} & ℛ (f) & \overset{g}{⟼} & ℛ (g \circ f) \end{matrix}$
  
  First, the image of $ℛ (f)$ must have dimension less than or equal to the dimension of $ℛ (f)$ , by the prior sentence. On the other hand, $ℛ (f)$ is a subset of the domain of $g$ , and thus its image has dimension less than or equal the dimension of the domain of $g$ . Combining those two, the rank of a composition is less than or equal to the minimum of the two ranks.
  
  The matrix fact follows immediately.
Exercise 2.31 Worked answer

Is ‘commutes with’ an equivalence relation among $n \times n$ matrices?

Back to Exercise 2.31

Answer. The ‘commutes with’ relation is reflexive and symmetric. However, it is not transitive: for instance, with

$G = (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) H = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) J = (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix})$

$G$ commutes with $H$ and $H$ commutes with $J$ , but $G$ does not commute with $J$ .
Exercise 2.32 Worked answer

(We will use this exercise in the Matrix Inverses exercises.) Here is another property of matrix multiplication that might be puzzling at first sight.
1. Prove that the composition of the projections $π_{x}, π_{y} : ℝ^{3} \to ℝ^{3}$ onto the $x$ and $y$ axes is the zero map despite that neither one is itself the zero map.
2. Prove that the composition of the derivatives $d^{2} / d x^{2}, d^{3} / d x^{3} : 𝒫_{4} \to 𝒫_{4}$ is the zero map despite that neither is the zero map.
3. Give a matrix equation representing the first fact.
4. Give a matrix equation representing the second.
When two things multiply to give zero despite that neither is zero we say that each is a zero divisor.
Back to Exercise 2.32

Answer.
1. Either of these.
  
  $(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{π_{x}}{⟼} (\begin{matrix} x \\ 0 \\ 0 \end{matrix}) \overset{π_{y}}{⟼} (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}) (\begin{matrix} x \\ y \\ z \end{matrix}) \overset{π_{y}}{⟼} (\begin{matrix} 0 \\ y \\ 0 \end{matrix}) \overset{π_{x}}{⟼} (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix})$
2. The composition is the fifth derivative map $d^{5} / d x^{5}$ on the space of fourth-degree polynomials.
3. With respect to the natural bases,
  
  ${Rep}_{ℰ_{3}, ℰ_{3}} (π_{x}) = (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) {Rep}_{ℰ_{3}, ℰ_{3}} (π_{y}) = (\begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix})$
  
  and their product (in either order) is the zero matrix.
4. Where $B = ⟨ 1, x, x^{2}, x^{3}, x^{4} ⟩$ ,
  
  ${Rep}_{B, B} (\frac{d^{2}}{d x^{2}}) = (\begin{matrix} 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 12 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) {Rep}_{B, B} (\frac{d^{3}}{d x^{3}}) = (\begin{matrix} 0 & 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 24 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})$
  
  and their product (in either order) is the zero matrix.
Exercise 2.33 Worked answer

Show that, for square matrices, $(S + T) (S - T)$ need not equal $S^{2} - T^{2}$ .

Back to Exercise 2.33

Answer. Note that $(S + T) (S - T) = S^{2} - S T + T S - T^{2}$ , so a reasonable try is to look at matrices that do not commute so that $- S T$ and $T S$ don’t cancel: with

$S = (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) T = (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix})$

we have the desired inequality.

$(S + T) (S - T) = (\begin{matrix} - 56 & - 56 \\ - 88 & - 88 \end{matrix}) S^{2} - T^{2} = (\begin{matrix} - 60 & - 68 \\ - 76 & - 84 \end{matrix})$
Exercise 2.34 Worked answer

Recommended. Represent the identity transformation $id : V \to V$ with respect to $B, B$ for any basis $B$ . This is the identity matrix $I$ . Show that this matrix plays the role in matrix multiplication that the number $1$ plays in real number multiplication: $H I = I H = H$ (for all matrices $H$ for which the product is defined).

Back to Exercise 2.34

Answer. Because the identity map acts on the basis $B$ as ${\vec{β}}_{1} \mapsto {\vec{β}}_{1}$ , …, ${\vec{β}}_{n} \mapsto {\vec{β}}_{n}$ , the representation is this.

$(\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ ⋱ \\ 0 & 0 & 0 & 1 \end{matrix})$

The second part of the question is obvious from Theorem 2.7.
Exercise 2.35 Worked answer
1. Prove that for any $2 \times 2$ matrix $T$ there are scalars $c_{0}, \dots, c_{4}$ that are not all $0$ such that the combination $c_{4} T^{4} + c_{3} T^{3} + c_{2} T^{2} + c_{1} T + c_{0} I$ is the zero matrix (where $I$ is the $2 \times 2$ identity matrix, with $1$ ’s in its $1, 1$ and $2, 2$ entries and zeroes elsewhere; see Exercise 2.34).
2. Let $p (x)$ be a polynomial $p (x) = c_{n} x^{n} + \dots + c_{1} x + c_{0}$ . If $T$ is a square matrix we define $p (T)$ to be the matrix $c_{n} T^{n} + \dots + c_{1} T + c_{0} I$ (where $I$ is the appropriately-sized identity matrix). Prove that for any square matrix there is a polynomial such that $p (T)$ is the zero matrix.
3. The minimal polynomial $m (x)$ of a square matrix is the polynomial of least degree, and with leading coefficient $1$ , such that $m (T)$ is the zero matrix. Find the minimal polynomial of this matrix.
  
  $(\begin{matrix} \sqrt{3} / 2 & - 1 / 2 \\ 1 / 2 & \sqrt{3} / 2 \end{matrix})$
  
  (This is the representation with respect to $ℰ_{2}, ℰ_{2}$ , the standard basis, of a rotation through $π / 6$ radians counterclockwise.)
Back to Exercise 2.35

Answer.
1. The vector space $ℳ_{2 \times 2}$ has dimension four. The set ${T^{4}, \dots, T, I}$ has five elements and thus is linearly dependent.
2. Where $T$ is $n \times n$ , generalizing the argument from the prior item shows that there is such a polynomial of degree $n^{2}$ or less, since ${T^{n^{2}}, \dots, T, I}$ is a $n^{2} + 1$ -member subset of the $n^{2}$ -dimensional space $ℳ_{n \times n}$ .
3. First compute the powers
  
  $T^{2} = (\begin{matrix} 1 / 2 & - \sqrt{3} / 2 \\ \sqrt{3} / 2 & 1 / 2 \end{matrix}) T^{3} = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) T^{4} = (\begin{matrix} - 1 / 2 & - \sqrt{3} / 2 \\ \sqrt{3} / 2 & - 1 / 2 \end{matrix})$
  
  (observe that rotating by $π / 6$ three times results in a rotation by $π / 2$ , which is indeed what $T^{3}$ represents). Then set $c_{4} T^{4} + c_{3} T^{3} + c_{2} T^{2} + c_{1} T + c_{0} I$ equal to the zero matrix
  
  $\begin{matrix} (\begin{matrix} - 1 / 2 & - \sqrt{3} / 2 \\ \sqrt{3} / 2 & - 1 / 2 \end{matrix}) c_{4} + (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) c_{3} + (\begin{matrix} 1 / 2 & - \sqrt{3} / 2 \\ \sqrt{3} / 2 & 1 / 2 \end{matrix}) c_{2} \\ + (\begin{matrix} \sqrt{3} / 2 & - 1 / 2 \\ 1 / 2 & \sqrt{3} / 2 \end{matrix}) c_{1} + (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) c_{0} = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) \end{matrix}$
  
  to get this linear system.
  
  $\begin{array}{rcrcrcrcrcr} - (1 / 2) c_{4} & + & (1 / 2) c_{2} & + & (\sqrt{3} / 2) c_{1} & + & c_{0} & = & 0 \\ - (\sqrt{3} / 2) c_{4} & - & c_{3} & - & (\sqrt{3} / 2) c_{2} & - & (1 / 2) c_{1} & = & 0 \\ (\sqrt{3} / 2) c_{4} & + & c_{3} & + & (\sqrt{3} / 2) c_{2} & + & (1 / 2) c_{1} & = & 0 \\ - (1 / 2) c_{4} & + & (1 / 2) c_{2} & + & (\sqrt{3} / 2) c_{1} & + & c_{0} & = & 0 \end{array}$
  
  Apply Gaussian reduction.
  
  $\begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{1} + ρ_{4}} ⟶_{\begin{matrix} \end{matrix}}^{ρ_{2} + ρ_{3}} \begin{array}{rcrcrcrcrcr} - (1 / 2) c_{4} & + & (1 / 2) c_{2} & + & (\sqrt{3} / 2) c_{1} & + & c_{0} & = & 0 \\ - (\sqrt{3} / 2) c_{4} & - & c_{3} & - & (\sqrt{3} / 2) c_{2} & - & (1 / 2) c_{1} & = & 0 \\ 0 & = & 0 \\ 0 & = & 0 \end{array} \\ ⟶_{\begin{matrix} \end{matrix}}^{- \sqrt{3} ρ_{1} + ρ_{2}} \begin{array}{rcrcrcrcrcr} - (1 / 2) c_{4} & + & (1 / 2) c_{2} & + & (\sqrt{3} / 2) c_{1} & + & c_{0} & = & 0 \\ - & c_{3} & - & \sqrt{3} c_{2} & - & 2 c_{1} & - & \sqrt{3} c_{0} & = & 0 \\ 0 & = & 0 \\ 0 & = & 0 \end{array} \end{aligned}$
  
  Setting $c_{4}$ , $c_{3}$ , and $c_{2}$ to zero makes $c_{1}$ and $c_{0}$ also come out to be zero so no degree one or degree zero polynomial will do. Setting $c_{4}$ and $c_{3}$ to zero (and $c_{2}$ to one) gives a linear system
  
  $\begin{array}{rcrcrcr} (1 / 2) & + & (\sqrt{3} / 2) c_{1} & + & c_{0} & = & 0 \\ - \sqrt{3} & - & 2 c_{1} & - & \sqrt{3} c_{0} & = & 0 \end{array}$
  
  with solution $c_{1} = - \sqrt{3}$ and $c_{0} = 1$ . Conclusion: the polynomial $m (x) = x^{2} - \sqrt{3} x + 1$ is minimal for the matrix $T$ .
Exercise 2.36 Worked answer

The infinite-dimensional space $𝒫$ of all finite-degree polynomials gives a memorable example of the non-commutativity of linear maps. Let $d / d x : 𝒫 \to 𝒫$ be the usual derivative and let $s : 𝒫 \to 𝒫$ be the shift map.

$a_{0} + a_{1} x + \dots + a_{n} x^{n} \overset{s}{⟼} 0 + a_{0} x + a_{1} x^{2} + \dots + a_{n} x^{n + 1}$

Show that the two maps don’t commute $d / d x \circ s \neq s \circ d / d x$ ; in fact, not only is $(d / d x \circ s) - (s \circ d / d x)$ not the zero map, it is the identity map.

Back to Exercise 2.36

Answer. The check is routine:

$a_{0} + a_{1} x + \dots + a_{n} x^{n} \overset{s}{⟼} a_{0} x + a_{1} x^{2} + \dots + a_{n} x^{n + 1} \overset{d / d x}{⟼} a_{0} + 2 a_{1} x + \dots + (n + 1) a_{n} x^{n}$

while

$a_{0} + a_{1} x + \dots + a_{n} x^{n} \overset{d / d x}{⟼} a_{1} + \dots + n a_{n} x^{n - 1} \overset{s}{⟼} a_{1} x + \dots + a_{n} x^{n}$

so that under the map $(d / d x \circ s) - (s \circ d / d x)$ we have $a_{0} + a_{1} x + \dots + a_{n} x^{n} \mapsto a_{0} + a_{1} x + \dots + a_{n} x^{n}$ .
Exercise 2.37 Worked answer

Recall the notation for the sum of the sequence of numbers $a_{1}, a_{2}, \dots, a_{n}$ .

$\sum_{i = 1}^{n} a_{i} = a_{1} + a_{2} + \dots + a_{n}$

In this notation, the $i, j$ entry of the product of $G$ and $H$ is this.

$p_{i, j} = \sum_{k = 1}^{r} g_{i, k} h_{k, j}$

Using this notation,
1. reprove that matrix multiplication is associative;
2. reprove Theorem 2.7.
Back to Exercise 2.37

Answer.
1. Tracing through the remark at the end of the subsection gives that the $i, j$ entry of $(F G) H$ is this
  
  $\begin{matrix} \sum_{t = 1}^{s} (\sum_{k = 1}^{r} f_{i, k} g_{k, t}) h_{t, j} = \sum_{t = 1}^{s} \sum_{k = 1}^{r} (f_{i, k} g_{k, t}) h_{t, j} = \sum_{t = 1}^{s} \sum_{k = 1}^{r} f_{i, k} (g_{k, t} h_{t, j}) \\ = \sum_{k = 1}^{r} \sum_{t = 1}^{s} f_{i, k} (g_{k, t} h_{t, j}) = \sum_{k = 1}^{r} f_{i, k} (\sum_{t = 1}^{s} g_{k, t} h_{t, j}) \end{matrix}$
  
  (the first equality comes from using the distributive law to multiply through the $h$ ’s, the second equality is the associative law for real numbers, the third is the commutative law for reals, and the fourth equality follows on using the distributive law to factor the $f$ ’s out), which is the $i, j$ entry of $F (G H)$ .
2. The $k$ -th component of $h (\vec{v})$ is
  
  $\sum_{j = 1}^{n} h_{k, j} v_{j}$
  
  and so the $i$ -th component of $g \circ h (\vec{v})$ is this
  
  $\begin{matrix} \sum_{k = 1}^{r} g_{i, k} (\sum_{j = 1}^{n} h_{k, j} v_{j}) = \sum_{k = 1}^{r} \sum_{j = 1}^{n} g_{i, k} h_{k, j} v_{j} = \sum_{k = 1}^{r} \sum_{j = 1}^{n} (g_{i, k} h_{k, j}) v_{j} \\ = \sum_{j = 1}^{n} \sum_{k = 1}^{r} (g_{i, k} h_{k, j}) v_{j} = \sum_{j = 1}^{n} (\sum_{k = 1}^{r} g_{i, k} h_{k, j}) v_{j} \end{matrix}$
  
  (the first equality holds by using the distributive law to multiply the $g$ ’s through, the second equality represents the use of associativity of reals, the third follows by commutativity of reals, and the fourth comes from using the distributive law to factor the $v$ ’s out).

Mechanics of Matrix Multiplication

We can consider matrix multiplication as a mechanical process, putting aside for the moment any implications about the underlying maps.

The striking thing about this operation is the way that rows and columns combine. The $i, j$ entry of the matrix product is the dot product of row $i$ of the left matrix with column $j$ of the right one. For instance, here a second row and a third column combine to make a $2, 3$ entry.

$(\begin{matrix} \begin{array}{cc} 1 & 1 \end{array} \\ \begin{array}{cc} 0 & 1 \end{array} \\ \begin{array}{cc} 1 & 0 \end{array} \end{matrix}) (\begin{matrix} \begin{matrix} 4 \\ 5 \end{matrix} & \begin{matrix} 6 \\ 7 \end{matrix} & \begin{matrix} 8 \\ 9 \end{matrix} & \begin{matrix} 2 \\ 3 \end{matrix} \end{matrix}) = (\begin{matrix} 9 & 13 & 17 & 5 \\ 5 & 7 & 9 & 3 \\ 4 & 6 & 8 & 2 \end{matrix})$

We can view this as the left matrix acting by multiplying its rows into the columns of the right matrix. Or, it is the right matrix using its columns to act on the rows of the left matrix. Below, we will examine actions from the left and from the right for some simple matrices.

Simplest is the zero matrix.

Example 3.1 Multiplying by a zero matrix from the left or from the right results in a zero matrix.

$(\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 1 & 3 & 2 \\ - 1 & 1 & - 1 \end{matrix}) = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) (\begin{matrix} 2 & 3 \\ 1 & 4 \end{matrix}) (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$

The next easiest matrices are the ones with a single nonzero entry.

Definition 3.2 A matrix with all $0$ ’s except for a $1$ in the $i, j$ entry is an $i, j$ unit matrix (or matrix unit).

Example 3.3 This is the $1, 2$ unit matrix with three rows and two columns, multiplying from the left.

$(\begin{matrix} 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix}) = (\begin{matrix} 7 & 8 \\ 0 & 0 \\ 0 & 0 \end{matrix})$

Acting from the left, an $i, j$ unit matrix copies row $j$ of the multiplicand into row $i$ of the result. From the right an $i, j$ unit matrix picks out column $i$ of the multiplicand and copies it into column $j$ of the result.

$(\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}) (\begin{matrix} 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 1 \\ 0 & 4 \\ 0 & 7 \end{matrix})$

Example 3.4 Rescaling unit matrices simply rescales the result. This is the action from the left of the matrix that is twice the one in the prior example.

$(\begin{matrix} 0 & 2 \\ 0 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix}) = (\begin{matrix} 14 & 16 \\ 0 & 0 \\ 0 & 0 \end{matrix})$

Next in complication are matrices with two nonzero entries.

Example 3.5 There are two cases. If a left-multiplier has entries in different rows then their actions don’t interact.

$\begin{aligned} (\begin{array}{c} 1 & 0 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{array}) (\begin{array}{c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}) & = ((\begin{array}{c} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) + (\begin{array}{c} 0 & 0 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{array})) (\begin{array}{c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}) \\ = (\begin{array}{c} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) + (\begin{array}{c} 0 & 0 & 0 \\ 14 & 16 & 18 \\ 0 & 0 & 0 \end{array}) \\ = (\begin{array}{c} 1 & 2 & 3 \\ 14 & 16 & 18 \\ 0 & 0 & 0 \end{array}) \end{aligned}$

But if the left-multiplier’s nonzero entries are in the same row then that row of the result is a combination.

$\begin{aligned} (\begin{array}{c} 1 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) (\begin{array}{c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}) & = ((\begin{array}{c} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) + (\begin{array}{c} 0 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array})) (\begin{array}{c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array}) \\ = (\begin{array}{c} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) + (\begin{array}{c} 14 & 16 & 18 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) \\ = (\begin{array}{c} 15 & 18 & 21 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}) \end{aligned}$

Right-multiplication acts in the same way, but with columns.

Lemma 3.6 In a product of two matrices $G$ and $H$ , the columns of $G H$ are formed by taking $G$ times the columns of $H$

$G \cdot (\begin{array}{ccccc} ⋮ & ⋮ \\ {\vec{h}}_{1} & \dots & {\vec{h}}_{n} \\ ⋮ & ⋮ \end{array}) = (\begin{array}{ccccc} ⋮ & ⋮ \\ G \cdot {\vec{h}}_{1} & \dots & G \cdot {\vec{h}}_{n} \\ ⋮ & ⋮ \end{array})$

and the rows of $G H$ are formed by taking the rows of $G$ times $H$

$(\begin{matrix} \dots {\vec{g}}_{1} \dots \\ ⋮ \\ \dots {\vec{g}}_{r} \dots \end{matrix}) \cdot H = (\begin{matrix} \dots {\vec{g}}_{1} \cdot H \dots \\ ⋮ \\ \dots {\vec{g}}_{r} \cdot H \dots \end{matrix})$

Proof We will check that in a product of $2 \times 2$ matrices, the rows of the product equal the product of the rows of $G$ with the entire matrix $H$ ; other cases worh the same way.

$\begin{aligned} (\begin{array}{c} g_{1, 1} & g_{1, 2} \\ g_{2, 1} & g_{2, 2} \end{array}) (\begin{array}{c} h_{1, 1} & h_{1, 2} \\ h_{2, 1} & h_{2, 2} \end{array}) & = (\begin{array}{c} (\begin{matrix} g_{1, 1} & g_{1, 2} \end{matrix}) H \\ (\begin{matrix} g_{2, 1} & g_{2, 2} \end{matrix}) H \end{array}) \\ = (\begin{array}{c} (\begin{matrix} g_{1, 1} h_{1, 1} + g_{1, 2} h_{2, 1} & g_{1, 1} h_{1, 2} + g_{1, 2} h_{2, 2} \end{matrix}) \\ (\begin{matrix} g_{2, 1} h_{1, 1} + g_{2, 2} h_{2, 1} & g_{2, 1} h_{1, 2} + g_{2, 2} h_{2, 2} \end{matrix}) \end{array}) \end{aligned}$

(We ignore the extra parentheses.)

QED

Example 3.7 Consider the columns of the product of two $2 \times 2$ matrices.

$(\begin{matrix} g_{1, 1} & g_{1, 2} \\ g_{2, 1} & g_{2, 2} \end{matrix}) (\begin{matrix} h_{1, 1} & h_{1, 2} \\ h_{2, 1} & h_{2, 2} \end{matrix}) = (\begin{matrix} g_{1, 1} h_{1, 1} + g_{1, 2} h_{2, 1} & g_{1, 1} h_{1, 2} + g_{1, 2} h_{2, 2} \\ g_{2, 1} h_{1, 1} + g_{2, 2} h_{2, 1} & g_{2, 1} h_{1, 2} + g_{2, 2} h_{2, 2} \end{matrix})$

Each column is the result of multiplying $G$ by the corresponding column of $H$ .

$G (\begin{matrix} h_{1, 1} \\ h_{2, 1} \end{matrix}) = (\begin{matrix} g_{1, 1} h_{1, 1} + g_{1, 2} h_{2, 1} \\ g_{2, 1} h_{1, 1} + g_{2, 2} h_{2, 1} \end{matrix}) G (\begin{matrix} h_{1, 2} \\ h_{2, 2} \end{matrix}) = (\begin{matrix} g_{1, 1} h_{1, 2} + g_{1, 2} h_{2, 2} \\ g_{2, 1} h_{1, 2} + g_{2, 2} h_{2, 2} \end{matrix})$

An application of those observations is that there is a matrix that just copies out the rows and columns.

Definition 3.8 The main diagonal (or principal diagonal or simply diagonal) of a square matrix goes from the upper left to the lower right.

Definition 3.9 An identity matrix is square and every entry is $0$ except for $1$ ’s in the main diagonal.

$I_{n \times n} = (\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ \\ 0 & 0 & \dots & 1 \end{matrix})$

Example 3.10 Here is the $2 \times 2$ identity matrix leaving its multiplicand unchanged when it acts from the right.

$(\begin{matrix} 1 & - 2 \\ 0 & - 2 \\ 1 & - 1 \\ 4 & 3 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 1 & - 2 \\ 0 & - 2 \\ 1 & - 1 \\ 4 & 3 \end{matrix})$

Example 3.11 Here the $3 \times 3$ identity leaves its multiplicand unchanged both from the left

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 2 & 3 & 6 \\ 1 & 3 & 8 \\ - 7 & 1 & 0 \end{matrix}) = (\begin{matrix} 2 & 3 & 6 \\ 1 & 3 & 8 \\ - 7 & 1 & 0 \end{matrix})$

and from the right.

$(\begin{matrix} 2 & 3 & 6 \\ 1 & 3 & 8 \\ - 7 & 1 & 0 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix} 2 & 3 & 6 \\ 1 & 3 & 8 \\ - 7 & 1 & 0 \end{matrix})$

In short, an identity matrix is the identity element of the set of $n \times n$ matrices with respect to the operation of matrix multiplication.

We can generalize the identity matrix by relaxing the ones to arbitrary reals. The resulting matrix rescales whole rows or columns.

Definition 3.12 A diagonal matrix is square and has $0$ ’s off the main diagonal.

$(\begin{matrix} a_{1, 1} & 0 & \dots & 0 \\ 0 & a_{2, 2} & \dots & 0 \\ ⋮ \\ 0 & 0 & \dots & a_{n, n} \end{matrix})$

Example 3.13 From the left, the action of multiplication by a diagonal matrix is to rescales the rows.

$(\begin{matrix} 2 & 0 \\ 0 & - 1 \end{matrix}) (\begin{matrix} 2 & 1 & 4 & - 1 \\ - 1 & 3 & 4 & 4 \end{matrix}) = (\begin{matrix} 4 & 2 & 8 & - 2 \\ 1 & - 3 & - 4 & - 4 \end{matrix})$

From the right such a matrix rescales the columns.

$(\begin{matrix} 1 & 2 & 1 \\ 2 & 2 & 2 \end{matrix}) (\begin{matrix} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & - 2 \end{matrix}) = (\begin{matrix} 3 & 4 & - 2 \\ 6 & 4 & - 4 \end{matrix})$

We can also generalize identity matrices by putting a single one in each row and column in ways other than putting them down the diagonal.

Definition 3.14 A permutation matrix is square and is all $0$ ’s except for a single $1$ in each row and column.

Example 3.15 From the left these matrices permute rows.

$(\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}) = (\begin{matrix} 7 & 8 & 9 \\ 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix})$

From the right they permute columns.

$(\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}) (\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) = (\begin{matrix} 2 & 3 & 1 \\ 5 & 6 & 4 \\ 8 & 9 & 7 \end{matrix})$

We finish this subsection by applying these observations to get matrices that perform Gauss’s Method and Gauss-Jordan reduction. We have already seen how to produce a matrix that rescales rows, and a row swapper.

Example 3.16 Multiplying by this matrix rescales the second row by three.

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 0 & 2 & 1 & 1 \\ 0 & 1 / 3 & 1 & - 1 \\ 1 & 0 & 2 & 0 \end{matrix}) = (\begin{matrix} 0 & 2 & 1 & 1 \\ 0 & 1 & 3 & - 3 \\ 1 & 0 & 2 & 0 \end{matrix})$

Example 3.17 This multiplication swaps the first and third rows.

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

To see how to perform a row combination, we observe something about those two examples. The matrix that rescales the second row by a factor of three arises in this way from the identity.

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{3 ρ_{2}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{matrix})$

Similarly, the matrix that swaps first and third rows arises in this way.

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{3}} (\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$

Example 3.18 The $3 \times 3$ matrix that arises as

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{3}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 2 & 1 \end{matrix})$

will, when it acts from the left, perform the combination operation $- 2 ρ_{2} + ρ_{3}$ .

$(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 2 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 2 & 0 \\ 0 & 1 & 3 & - 3 \\ 0 & 2 & 1 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 & 2 & 0 \\ 0 & 1 & 3 & - 3 \\ 0 & 0 & - 5 & 7 \end{matrix})$

Definition 3.19 The elementary reduction matrices (or just elementary matrices) result from applying a single Gaussian operation to an identity matrix.

$I ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i}} M_{i} (k)$ for $k \neq 0$
$I ⟶_{\begin{array}{l} \end{array}}^{ρ_{i} \leftrightarrow ρ_{j}} P_{i, j}$ for $i \neq j$
$I ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i} + ρ_{j}} C_{i, j} (k)$ for $i \neq j$

Lemma 3.20 Matrix multiplication can do Gaussian reduction.

If $H ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i}} G$ then $M_{i} (k) H = G$ .
If $H ⟶_{\begin{array}{l} \end{array}}^{ρ_{i} \leftrightarrow ρ_{j}} G$ then $P_{i, j} H = G$ .
If $H ⟶_{\begin{array}{l} \end{array}}^{k ρ_{i} + ρ_{j}} G$ then $C_{i, j} (k) H = G$ .

Proof Clear.

QED

Example 3.21 This is the first system, from the first chapter, on which we performed Gauss’s Method.

$\begin{array}{rcrcrcr} 3 x_{3} & = & 9 \\ x_{1} & + & 5 x_{2} & - & 2 x_{3} & = & 2 \\ (1 / 3) x_{1} & + & 2 x_{2} & = & 3 \end{array}$

We can reduce it with matrix multiplication. Swap the first and third rows,

$(\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) (\begin{array}{cccr} 0 & 0 & 3 & 9 \\ 1 & 5 & - 2 & 2 \\ 1 / 3 & 2 & 0 & 3 \end{array}) = (\begin{array}{cccr} 1 / 3 & 2 & 0 & 3 \\ 1 & 5 & - 2 & 2 \\ 0 & 0 & 3 & 9 \end{array})$

triple the first row,

$(\begin{matrix} 3 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{array}{cccr} 1 / 3 & 2 & 0 & 3 \\ 1 & 5 & - 2 & 2 \\ 0 & 0 & 3 & 9 \end{array}) = (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 1 & 5 & - 2 & 2 \\ 0 & 0 & 3 & 9 \end{array})$

and then add $- 1$ times the first row to the second.

$(\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 1 & 5 & - 2 & 2 \\ 0 & 0 & 3 & 9 \end{array}) = (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 0 & - 1 & - 2 & - 7 \\ 0 & 0 & 3 & 9 \end{array})$

Now back substitution will give the solution.

Example 3.22 Gauss-Jordan reduction works the same way. For the matrix ending the prior example, first turn the leading entries to ones,

$(\begin{matrix} 1 & 0 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & 1 / 3 \end{matrix}) (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 0 & - 1 & - 2 & - 7 \\ 0 & 0 & 3 & 9 \end{array}) = (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 0 & 1 & 2 & 7 \\ 0 & 0 & 1 & 3 \end{array})$

then clear the third column, and then the second column.

$(\begin{matrix} 1 & - 6 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & - 2 \\ 0 & 0 & 1 \end{matrix}) (\begin{array}{cccr} 1 & 6 & 0 & 9 \\ 0 & 1 & 2 & 7 \\ 0 & 0 & 1 & 3 \end{array}) = (\begin{array}{cccr} 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 3 \end{array})$

Corollary 3.23 For any matrix $H$ there are elementary reduction matrices $R_{1}$ , …, $R_{r}$ such that $R_{r} \cdot R_{r - 1} \dots R_{1} \cdot H$ is in reduced echelon form.

Until now we have taken the point of view that our primary objects of study are vector spaces and the maps between them, and we seemed to have adopted matrices only for computational convenience. This subsection shows that this isn’t the entire story.

Understanding matrix operations by understanding the mechanics of how the entries combine is also useful. In the rest of this book we shall continue to focus on maps as the primary objects but we will be pragmatic—if the matrix point of view gives some clearer idea then we will go with it.

Exercises

Exercise 3.24 Worked answer

Recommended. Predict the result of each product with a permutation matrix and then check by multiplying it out.
1. $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
2. $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$
3. $(\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix})$
Back to Exercise 3.24

Answer.
1. Acting from the left, the $P_{1, 2}$ matrix swaps the first and second rows. $(\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix})$
2. Acting from the right, $P_{1, 2}$ swaps the first and second columns. $(\begin{matrix} 2 & 1 \\ 4 & 3 \end{matrix})$
3. From the left, $P_{2, 3}$ swaps the second and third rows. $(\begin{matrix} 1 & 2 & 3 \\ 7 & 8 & 9 \\ 4 & 5 & 6 \end{matrix})$
Exercise 3.25 Worked answer

Recommended. Predict the result of each multiplication by an elementary reduction matrix, and then check by multiplying it out.
1. $(\begin{matrix} 3 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
2. $(\begin{matrix} 1 & 0 \\ 0 & 2 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
3. $(\begin{matrix} 1 & 0 \\ - 2 & 1 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
4. $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix})$
5. $(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$
Back to Exercise 3.25

Answer.
1. The second matrix has its first row multiplied by $3$ .
  
  $(\begin{matrix} 3 & 6 \\ 3 & 4 \end{matrix})$
2. The second matrix has its second row multiplied by $2$ .
  
  $(\begin{matrix} 1 & 2 \\ 6 & 8 \end{matrix})$
3. The second matrix undergoes the combination operation of replacing the second row with $- 2$ times the first row added to the second.
  
  $(\begin{matrix} 1 & 2 \\ 1 & 0 \end{matrix})$
4. The first matrix undergoes the column operation of: replace the second column by $- 1$ times the first column plus the second.
  
  $(\begin{matrix} 1 & 1 \\ 3 & 1 \end{matrix})$
5. The first matrix has its columns swapped.
  
  $(\begin{matrix} 2 & 1 \\ 4 & 3 \end{matrix})$
Exercise 3.26 Worked answer

Predict the result of each multiplication by a diagonal matrix, and then check by multiplying it out.
1. $(\begin{matrix} - 3 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
2. $(\begin{matrix} 4 & 0 \\ 0 & 2 \end{matrix}) (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$
Back to Exercise 3.26

Answer.
1. The second matrix has its first row multiplied by $- 3$ and its second row multiplied by $0$ .
  
  $(\begin{matrix} - 3 & - 6 \\ 0 & 0 \end{matrix})$
2. The second matrix has its first row multiplied by $4$ and its second row multiplied by $2$ .
  
  $(\begin{matrix} 4 & 8 \\ 6 & 8 \end{matrix})$
Exercise 3.27 Worked answer

Produce each.
1. a $3 \times 3$ matrix that, acting from the left, swaps rows one and two
2. a $2 \times 2$ matrix that, acting from the right, swaps column one and two
Back to Exercise 3.27

Answer.
1. This matrix swaps row one and row three.
  
  $(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} a & b & c \\ d & e & f \\ g & h & i \end{matrix}) = (\begin{matrix} d & e & f \\ a & b & c \\ g & h & i \end{matrix})$
2. This matrix swaps column one and two.
  
  $(\begin{matrix} a & b \\ c & d \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} b & a \\ d & c \end{matrix})$
Exercise 3.28 Worked answer

Recommended. Show how to use matrix multiplication to bring this matrix to echelon form.

$(\begin{matrix} 1 & 2 & 1 & 0 \\ 2 & 3 & 1 & - 1 \\ 7 & 11 & 4 & - 3 \end{matrix})$

Back to Exercise 3.28

Answer. Multiply by $C_{1, 2} (- 2)$ , then by $C_{1, 3} (- 7)$ , and then by $C_{2, 3} (- 3)$ , paying attention to the right-to-left order.

$\begin{matrix} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 3 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 7 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 2 & 1 & 0 \\ 2 & 3 & 1 & - 1 \\ 7 & 11 & 4 & - 3 \end{matrix}) \\ = (\begin{matrix} 1 & 2 & 1 & 0 \\ 0 & - 1 & - 1 & - 1 \\ 0 & 0 & 0 & 0 \end{matrix}) \end{matrix}$
Exercise 3.29 Worked answer

Find the product of this matrix with its transpose.

$(\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix})$

Back to Exercise 3.29

Answer. The product is the identity matrix (recall that $\cos^{2} θ + \sin^{2} θ = 1$ ). An explanation is that the given matrix represents, with respect to the standard bases, a rotation in $ℝ^{2}$ of $θ$ radians while the transpose represents a rotation of $- θ$ radians. The two cancel.
Exercise 3.30 Worked answer

The need to take linear combinations of rows and columns in tables of numbers arises often in practice. For instance, this is a map of part of Vermont and New York.

In part because of Lake Champlain, there are no roads directly connecting some pairs of towns. For instance, there is no way to go from Winooski to Grand Isle without going through Colchester. (To simplify the graph many other roads and towns have been omitted. From top to bottom of this map is about forty miles.)
1. The adjacency matrix of a map is the square matrix whose $i, j$ entry is the number of roads from city $i$ to city $j$ (all $(i, i)$ entries are $0$ ). Produce the adjacency matrix of this map, taking the cities in alphabetical order.
2. A matrix is symmetric if it equals its transpose. Show that an adjacency matrix is symmetric. (These are all two-way streets. Vermont doesn’t have many one-way streets.)
3. What is the significance of the square of the adjacency matrix? The cube?
Back to Exercise 3.30

Answer.
1. The adjacency matrix is this (e.g, the first row shows that there is only one connection including Burlington, the road to Winooski).
  
  $(\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{matrix})$
2. Because these are two-way roads, any road connecting city $i$ to city $j$ gives a connection between city $j$ and city $i$ .
3. The square of the adjacency matrix tells how cities are connected by trips involving two roads.
Exercise 3.31 Worked answer

Recommended. This table gives the number of hours of each type done by each worker, and the associated pay rates. Use matrices to compute the wages due.

regular overtime

Alan 40 12

Betty 35 6

Catherine 40 18

Donald 28 0

wage

regular $$ 25.00$

overtime $$ 45.00$

Remark. This illustrates that in practice we often want to compute linear combinations of rows and columns in a context where we really aren’t interested in any associated linear maps.

Back to Exercise 3.31

Answer. The pay due each person appears in the matrix product of the two arrays.
Exercise 3.32 Worked answer

Express this nonsingular matrix as a product of elementary reduction matrices.

$T = (\begin{matrix} 1 & 2 & 0 \\ 2 & - 1 & 0 \\ 3 & 1 & 2 \end{matrix})$

Back to Exercise 3.32

Answer. The Gauss-Jordan reduction is routine.

$(\begin{matrix} 1 & 2 & 0 \\ 2 & - 1 & 0 \\ 3 & 1 & 2 \end{matrix}) ⟶_{\begin{array}{l} - 3 ρ_{1} + ρ_{3} \end{array}}^{- 2 ρ_{1} + ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- ρ_{2} + ρ_{3}} ⟶_{\begin{array}{l} (1 / 2) ρ_{3} \end{array}}^{- (1 / 5) ρ_{2}} ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{2} + ρ_{1}} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$

Thus we know elementary reduction matrices $R_{1}, \dots, R_{6}$ such that $R_{6} \cdot R_{5} \dots R_{1} \cdot T = I$ . Move the matrices to the other side, paying attention to order. For instance, first multiply both sides from the left by $R_{6}^{- 1}$ to get $(R_{6}^{- 1} R_{6}) \cdot R_{5} \dots R_{1} \cdot T = R_{6}^{- 1} I$ , which simplifies to $R_{5} \dots R_{1} \cdot T = R_{6}^{- 1}$ , etc.

$\begin{aligned} T = & {(\begin{array}{c} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ 0 & 0 & 1 \end{array})}^{- 1} {(\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 3 & 0 & 1 \end{array})}^{- 1} {(\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 1 & 1 \end{array})}^{- 1} \\ \cdot {(\begin{array}{c} 1 & 0 & 0 \\ 0 & - 1 / 5 & 0 \\ 0 & 0 & 1 \end{array})}^{- 1} {(\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 / 2 \end{array})}^{- 1} {(\begin{array}{c} 1 & - 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array})}^{- 1} \end{aligned}$

Taking the inverse of an elementary reduction matrix is easy. For instance, to undo adding $k$ times row $i$ to row $j$ , you should take $- k$ times row $i$ and add it to row $j$ . With that, Lemma 3.20 says that $C_{i, j} (k)^{- 1} = C_{i, j} (- k)$ .

$= (\begin{matrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & - 5 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{matrix}) (\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$
Exercise 3.33 Worked answer

Express

$(\begin{matrix} 1 & 0 \\ - 3 & 3 \end{matrix})$

as the product of two elementary reduction matrices.

Back to Exercise 3.33

Answer. One way to produce this matrix from the identity is to use the column operations of first multiplying the second column by three, and then adding the negative of the resulting second column to the first.

$(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{} (\begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix}) ⟶_{\begin{array}{l} \end{array}}^{} (\begin{matrix} 1 & 0 \\ - 3 & 3 \end{matrix})$

In contrast with row operations, column operations are written from left to right, so this matrix product expresses doing the above two operations.

$(\begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix}) (\begin{matrix} 1 & 0 \\ - 1 & 1 \end{matrix})$

Remark. Alternatively, we could get the required matrix with row operations. Starting with the identity, first adding the negative of the first row to the second, and then multiplying the second row by three will work. Because we write successive row operations as matrix products from right to left, doing these two row operations is expressed with: the same matrix product.
Exercise 3.34 Worked answer

Recommended. Prove that the diagonal matrices form a subspace of $ℳ_{n \times n}$ . What is its dimension?

Back to Exercise 3.34

Answer. The set of diagonal matrices is nonempty as the zero matrix is diagonal. Clearly it is closed under scalar multiples and sums. Therefore it is a subspace. The dimension is $n$ ; here is a basis.

${(\begin{matrix} 1 & 0 & \dots \\ 0 & 0 \\ ⋱ \\ 0 & 0 & 0 \end{matrix}), \dots, (\begin{matrix} 0 & 0 & \dots \\ 0 & 0 \\ ⋱ \\ 0 & 0 & 1 \end{matrix})}$
Exercise 3.35 Worked answer

Does the identity matrix represent the identity map if the bases are unequal?

Back to Exercise 3.35

Answer. No. In $𝒫_{1}$ , with respect to the unequal bases $B = ⟨ 1, x ⟩$ and $D = ⟨ 1 + x, 1 - x ⟩$ , the identity transformation is represented by this matrix.

${Rep}_{B, D} (id) = {(\begin{matrix} 1 / 2 & 1 / 2 \\ 1 / 2 & - 1 / 2 \end{matrix})}_{B, D}$
Exercise 3.36 Worked answer

Show that every multiple of the identity commutes with every square matrix. Are there other matrices that commute with all square matrices?

Back to Exercise 3.36

Answer. For any scalar $r$ and square matrix $H$ we have $(r I) H = r (I H) = r H = r (H I) = (H r) I = H (r I)$ .

There are no other such matrices; here is an argument for $2 \times 2$ matrices that is easily extended to $n \times n$ . If a matrix commutes with all others then it commutes with this unit matrix.

$(\begin{matrix} 0 & a \\ 0 & c \end{matrix}) = (\begin{matrix} a & b \\ c & d \end{matrix}) (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) (\begin{matrix} a & b \\ c & d \end{matrix}) = (\begin{matrix} c & d \\ 0 & 0 \end{matrix})$

From this we first conclude that the upper left entry $a$ must equal its lower right entry $d$ . We also conclude that the lower left entry $c$ is zero. The argument for the upper right entry $b$ is similar.
Exercise 3.37 Worked answer

Prove or disprove: nonsingular matrices commute.

Back to Exercise 3.37

Answer. It is false; these two don’t commute.

$(\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) (\begin{matrix} 5 & 6 \\ 7 & 8 \end{matrix})$
Exercise 3.38 Worked answer

Recommended. Show that the product of a permutation matrix and its transpose is an identity matrix.

Back to Exercise 3.38

Answer. A permutation matrix has a single one in each row and column, and all its other entries are zeroes. Fix such a matrix. Suppose that the $i$ -th row has its one in its $j$ -th column. Then no other row has its one in the $j$ -th column; every other row has a zero in the $j$ -th column. Thus the dot product of the $i$ -th row and any other row is zero.

The $i$ -th row of the product is made up of the dot products of the $i$ -th row of the matrix and the columns of the transpose. By the last paragraph, all such dot products are zero except for the $i$ -th one, which is one.
Exercise 3.39 Worked answer

Show that if the first and second rows of $G$ are equal then so are the first and second rows of $G H$ . Generalize.

Back to Exercise 3.39

Answer. The generalization is to go from the first and second rows to the $i_{1}$ -th and $i_{2}$ -th rows. Row $i$ of $G H$ is made up of the dot products of row $i$ of $G$ and the columns of $H$ . Thus if rows $i_{1}$ and $i_{2}$ of $G$ are equal then so are rows $i_{1}$ and $i_{2}$ of $G H$ .
Exercise 3.40 Worked answer

Describe the product of two diagonal matrices.

Back to Exercise 3.40

Answer. If the product of two diagonal matrices is defined—if both are $n \times n$ —then the product of the diagonals is the diagonal of the products: where $G, H$ are equal-sized diagonal matrices, $G H$ is all zeros except each that $i, i$ entry is $g_{i, i} h_{i, i}$ .
Exercise 3.41 Worked answer

Recommended. Show that if $G$ has a row of zeros then $G H$ (if defined) has a row of zeros. Does that work for columns?

Back to Exercise 3.41

Answer. The $i$ -th row of $G H$ is made up of the dot products of the $i$ -th row of $G$ with the columns of $H$ . The dot product of a zero row with a column is zero.

It works for columns if stated correctly: if $H$ has a column of zeros then $G H$ (if defined) has a column of zeros. The proof is easy.
Exercise 3.42 Worked answer

Show that the set of unit matrices forms a basis for $ℳ_{n \times m}$ .

Back to Exercise 3.42

Answer. Perhaps the easiest way is to show that each $n \times m$ matrix is a linear combination of unit matrices in one and only one way:

$c_{1} (\begin{matrix} 1 & 0 & \dots \\ 0 & 0 \\ ⋮ \end{matrix}) + \dots + c_{n, m} (\begin{matrix} 0 & 0 & \dots \\ ⋮ \\ 0 & \dots & 1 \end{matrix}) = (\begin{matrix} a_{1, 1} & a_{1, 2} & \dots \\ ⋮ \\ a_{n, 1} & \dots & a_{n, m} \end{matrix})$

has the unique solution $c_{1} = a_{1, 1}$ , $c_{2} = a_{1, 2}$ , etc.
Exercise 3.43 Worked answer

Find the formula for the $n$ -th power of this matrix.

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

Back to Exercise 3.43

Answer. Call that matrix $F$ . We have

$F^{2} = (\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix}) F^{3} = (\begin{matrix} 3 & 2 \\ 2 & 1 \end{matrix}) F^{4} = (\begin{matrix} 5 & 3 \\ 3 & 2 \end{matrix})$

In general,

$F^{n} = (\begin{matrix} f_{n + 1} & f_{n} \\ f_{n} & f_{n - 1} \end{matrix})$

where $f_{i}$ is the $i$ -th Fibonacci number $f_{i} = f_{i - 1} + f_{i - 2}$ and $f_{0} = 0$ , $f_{1} = 1$ , which we verify by induction, based on this equation.

$(\begin{matrix} f_{i - 1} & f_{i - 2} \\ f_{i - 2} & f_{i - 3} \end{matrix}) (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} f_{i} & f_{i - 1} \\ f_{i - 1} & f_{i - 2} \end{matrix})$
Exercise 3.44 Worked answer

Recommended. The trace of a square matrix is the sum of the entries on its diagonal (its significance appears in Chapter Five). Show that $Tr (G H) = Tr (H G)$ .

Back to Exercise 3.44

Answer. Chapter Five gives a less computational reason—the trace of a matrix is the second coefficient in its characteristic polynomial—but for now we can use indices. We have

$\begin{aligned} Tr (G H) & = (g_{1, 1} h_{1, 1} + g_{1, 2} h_{2, 1} + \dots + g_{1, n} h_{n, 1}) \\ + (g_{2, 1} h_{1, 2} + g_{2, 2} h_{2, 2} + \dots + g_{2, n} h_{n, 2}) \\ + \dots + (g_{n, 1} h_{1, n} + g_{n, 2} h_{2, n} + \dots + g_{n, n} h_{n, n}) \end{aligned}$

while

$\begin{aligned} Tr (H G) & = (h_{1, 1} g_{1, 1} + h_{1, 2} g_{2, 1} + \dots + h_{1, n} g_{n, 1}) \\ + (h_{2, 1} g_{1, 2} + h_{2, 2} g_{2, 2} + \dots + h_{2, n} g_{n, 2}) \\ + \dots + (h_{n, 1} g_{1, n} + h_{n, 2} g_{2, n} + \dots + h_{n, n} g_{n, n}) \end{aligned}$

and the two are equal.
Exercise 3.45 Worked answer

A square matrix is upper triangular if its only nonzero entries lie above, or on, the diagonal. Show that the product of two upper triangular matrices is upper triangular. Does this hold for lower triangular also?

Back to Exercise 3.45

Answer. A matrix is upper triangular if and only if its $i, j$ entry is zero whenever $i > j$ . Thus, if $G, H$ are upper triangular then $h_{i, j}$ and $g_{i, j}$ are zero when $i > j$ . An entry in the product $p_{i, j} = g_{i, 1} h_{1, j} + \dots + g_{i, n} h_{n, j}$ is zero unless at least some of the terms are nonzero, that is, unless for at least some of the summands $g_{i, r} h_{r, j}$ both $i \leq r$ and $r \leq j$ . Of course, if $i > j$ this cannot happen and so the product of two upper triangular matrices is upper triangular. (A similar argument works for lower triangular matrices.)
Exercise 3.46 Worked answer

A square matrix is a Markov matrix if each entry is between zero and one and the sum along each row is one. Prove that a product of Markov matrices is Markov.

Back to Exercise 3.46

Answer. The sum along the $i$ -th row of the product is this.

$\begin{aligned} p_{i, 1} + \dots + p_{i, n} & = (h_{i, 1} g_{1, 1} + h_{i, 2} g_{2, 1} + \dots + h_{i, n} g_{n, 1}) \\ + (h_{i, 1} g_{1, 2} + h_{i, 2} g_{2, 2} + \dots + h_{i, n} g_{n, 2}) \\ + \dots + (h_{i, 1} g_{1, n} + h_{i, 2} g_{2, n} + \dots + h_{i, n} g_{n, n}) \\ = h_{i, 1} (g_{1, 1} + g_{1, 2} + \dots + g_{1, n}) \\ + h_{i, 2} (g_{2, 1} + g_{2, 2} + \dots + g_{2, n}) \\ + \dots + h_{i, n} (g_{n, 1} + g_{n, 2} + \dots + g_{n, n}) \\ = h_{i, 1} \cdot 1 + \dots + h_{i, n} \cdot 1 \\ = 1 \end{aligned}$
Exercise 3.47 Worked answer

Give an example of two matrices of the same rank and size with squares of differing rank.

Back to Exercise 3.47

Answer. Fix a basis $B = ⟨ {\vec{β}}_{1}, {\vec{β}}_{2} ⟩$ . Matrices representing the maps that send

${\vec{β}}_{1} \overset{h}{⟼} {\vec{β}}_{1} {\vec{β}}_{2} \overset{h}{⟼} \vec{0}$

and

${\vec{β}}_{1} \overset{g}{⟼} {\vec{β}}_{2} {\vec{β}}_{2} \overset{g}{⟼} \vec{0}$

will do. For instance, if for we use the standard basis then the two above give these matrices.

$H = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) G = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$

Notice that $H^{2}$ has rank $1$ while $G^{2}$ has rank $0$ .

Exercise 3.48 Worked answer

Matrix multiplication is performed often on computers. Researchers trying to understand its performance, and improve on it, count the number of operations that it takes.

Definition 2.3 gives $p_{i, j} = g_{i, 1} h_{1, j} + g_{i, 2} h_{2, j} + \dots + g_{i, r} h_{r, j}$ . How many real number multiplications are in that expression? Using it, how many do we need for the product of a $m \times r$ matrix and a $r \times n$ matrix?
Matrix multiplication is associative, so in computing $H_{1} H_{2} H_{3} H_{4}$ we can expect to get the same answer no matter where we put the parentheses. The cost in number of multiplications, however, varies. Find the association requiring the fewest real number multiplications to compute the matrix product of a $5 \times 10$ matrix, a $10 \times 20$ matrix, a $20 \times 5$ matrix, and a $5 \times 1$ matrix. Use the same formula as in the prior part.
(Very hard.) Find a way to multiply two $2 \times 2$ matrices using only seven multiplications instead of the eight suggested by the prior approach.

Back to Exercise 3.48

Answer.

Each entry $p_{i, j} = g_{i, 1} h_{1, j} + \dots + g_{1, r} h_{r, 1}$ takes $r$ multiplications and there are $m \cdot n$ entries. Thus there are $m \cdot n \cdot r$ multiplications.

Let $H_{1}$ be $5 \times 10$ , let $H_{2}$ be $10 \times 20$ , let $H_{3}$ be $20 \times 5$ , let $H_{4}$ be $5 \times 1$ . Then

this association	uses this many multiplications
$((H_{1} H_{2}) H_{3}) H_{4}$	$1000 + 500 + 25 = 1525$
$(H_{1} (H_{2} H_{3})) H_{4}$	$1000 + 250 + 25 = 1275$
$(H_{1} H_{2}) (H_{3} H_{4})$	$1000 + 100 + 100 = 1200$
$H_{1} (H_{2} (H_{3} H_{4}))$	$100 + 200 + 50 = 350$
$H_{1} ((H_{2} H_{3}) H_{4})$	$1000 + 50 + 50 = 1100$

shows which is cheapest.

This is an improvement by S. Winograd of a formula due to V. Strassen: let $w = a A - (a - c - d) (A - C + D)$ and then

$(\begin{matrix} a & b \\ c & d \end{matrix}) (\begin{matrix} A & B \\ C & D \end{matrix}) = (\begin{matrix} α & β \\ γ & δ \end{matrix})$

where $α = a A + b B$ , and $β = w + (c + d) (C - A) + (a + b - c - d) D$ , and $γ = w + (a - c) (D - C) - d (A - B - C + D)$ , and $δ = w + (a - c) (D - C) + (c + d) (C - A)$ . This takes seven multiplications and fifteen additions (save the intermediate results).

Exercise 3.49 Worked answer

Puzzle. [Putnam, 1990, A-5] If $A$ and $B$ are square matrices of the same size such that $A B A B = 0$ , does it follow that $B A B A = 0$ ?

Back to Exercise 3.49

Answer. This is how the answer was given in the cited source. No, it does not. Let $A$ and $B$ represent, with respect to the standard bases, these transformations of $ℝ^{3}$ .

$(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{a}{⟼} (\begin{matrix} x \\ y \\ 0 \end{matrix}) (\begin{matrix} x \\ y \\ z \end{matrix}) \overset{b}{⟼} (\begin{matrix} 0 \\ x \\ y \end{matrix})$

Observe that

$(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{a b a b}{⟼} (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}) but (\begin{matrix} x \\ y \\ z \end{matrix}) \overset{b a b a}{⟼} (\begin{matrix} 0 \\ 0 \\ x \end{matrix}) .$
Exercise 3.50 Worked answer

[Am. Math. Mon., Dec. 1966] Demonstrate these four assertions to get an alternate proof that column rank equals row rank.
1. $\vec{y} \cdot \vec{y} = 0$ iff $\vec{y} = \vec{0}$ .
2. $A \vec{x} = \vec{0}$ iff $A^{𝖳} A \vec{x} = \vec{0}$ .
3. $\dim (ℛ (A)) = \dim (ℛ (A^{𝖳} A))$ .
4. $col rank (A) = col rank (A^{𝖳}) = row rank (A)$ .
Back to Exercise 3.50

Answer. This is how the answer was given in the cited source.
1. Obvious.
2. If $A^{𝖳} A \vec{x} = \vec{0}$ then $\vec{y} \cdot \vec{y} = 0$ where $\vec{y} = A \vec{x}$ . Hence $\vec{y} = \vec{0}$ by (a).
  
  The converse is obvious.
3. By (b), $A {\vec{x}}_{1}$ ,…, $A {\vec{x}}_{n}$ are linearly independent iff $A^{𝖳} A {\vec{x}}_{1}$ ,…, $A^{𝖳} A {\vec{x}}_{n}$ are linearly independent.
4. We have
  
  $\begin{matrix} col rank (A) = col rank (A^{𝖳} A) = \dim {A^{𝖳} (A \vec{x}) ∣ all \vec{x}} \\ \leq \dim {A^{𝖳} \vec{y} ∣ all \vec{y}} = col rank (A^{𝖳}) . \end{matrix}$
  
  Thus also $col rank (A^{𝖳}) \leq col rank ({A^{𝖳}}^{𝖳})$ and so $col rank (A) = col rank (A^{𝖳}) = row rank (A)$ .
Exercise 3.51 Worked answer

[Ackerson] Prove (where $A$ is an $n \times n$ matrix and so defines a transformation of any $n$ -dimensional space $V$ with respect to $B, B$ where $B$ is a basis) that $\dim (ℛ (A) \cap 𝒩 (A)) = \dim (ℛ (A)) - \dim (ℛ (A^{2}))$ . Conclude
1. $𝒩 (A) \subset ℛ (A)$ iff $\dim (𝒩 (A)) = \dim (ℛ (A)) - \dim (ℛ (A^{2}))$ ;
2. $ℛ (A) \subseteq 𝒩 (A)$ iff $A^{2} = 0$ ;
3. $ℛ (A) = 𝒩 (A)$ iff $A^{2} = 0$ and $\dim (𝒩 (A)) = \dim (ℛ (A))$ ;
4. $\dim (ℛ (A) \cap 𝒩 (A)) = 0$ iff $\dim (ℛ (A)) = \dim (ℛ (A^{2}))$ ;
5. (Requires the Direct Sum subsection, which is optional.) $V = ℛ (A) \oplus 𝒩 (A)$ iff $\dim (ℛ (A)) = \dim (ℛ (A^{2}))$ .
Back to Exercise 3.51

Answer. This is how the answer was given in the cited source. Let $⟨ {\vec{z}}_{1}, \dots, {\vec{z}}_{k} ⟩$ be a basis for $ℛ (A) \cap 𝒩 (A)$ ( $k$ might be $0$ ). Let ${\vec{x}}_{1}, \dots, {\vec{x}}_{k} \in V$ be such that $A {\vec{x}}_{i} = {\vec{z}}_{i}$ . Note ${A {\vec{x}}_{1}, \dots, A {\vec{x}}_{k}}$ is linearly independent, and extend to a basis for $ℛ (A)$ : $A {\vec{x}}_{1}, \dots, A {\vec{x}}_{k}, A {\vec{x}}_{k + 1}, \dots, A {\vec{x}}_{r_{1}}$ where $r_{1} = \dim (ℛ (A))$ .

Now take $\vec{x} \in V$ . Write

$A \vec{x} = a_{1} (A {\vec{x}}_{1}) + \dots + a_{r_{1}} (A {\vec{x}}_{r_{1}})$

and so

$A^{2} \vec{x} = a_{1} (A^{2} {\vec{x}}_{1}) + \dots + a_{r_{1}} (A^{2} {\vec{x}}_{r_{1}}) .$

But $A {\vec{x}}_{1}, \dots, A {\vec{x}}_{k} \in 𝒩 (A)$ , so $A^{2} {\vec{x}}_{1} = \vec{0}, \dots, A^{2} {\vec{x}}_{k} = \vec{0}$ and we now know

$A^{2} {\vec{x}}_{k + 1}, \dots, A^{2} {\vec{x}}_{r_{1}}$

spans $ℛ (A^{2})$ .

To see ${A^{2} {\vec{x}}_{k + 1}, \dots, A^{2} {\vec{x}}_{r_{1}}}$ is linearly independent, write

$\begin{aligned} b_{k + 1} A^{2} {\vec{x}}_{k + 1} + \dots + b_{r_{1}} A^{2} {\vec{x}}_{r_{1}} & = \vec{0} \\ A [b_{k + 1} A {\vec{x}}_{k + 1} + \dots + b_{r_{1}} A {\vec{x}}_{r_{1}}] & = \vec{0} \end{aligned}$

and, since $b_{k + 1} A {\vec{x}}_{k + 1} + \dots + b_{r_{1}} A {\vec{x}}_{r_{1}} \in 𝒩 (A)$ we get a contradiction unless it is $\vec{0}$ (clearly it is in $ℛ (A)$ , but $A {\vec{x}}_{1}, \dots, A {\vec{x}}_{k}$ is a basis for $ℛ (A) \cap 𝒩 (A)$ ).

Hence $\dim (ℛ (A^{2})) = r_{1} - k = \dim (ℛ (A)) - \dim (ℛ (A) \cap 𝒩 (A))$ .

Inverses

We finish this section by considering how to represent the inverse of a linear map. We first recall some things about inverses. Where $π : ℝ^{3} \to ℝ^{2}$ is the projection map and $ι : ℝ^{2} \to ℝ^{3}$ is the embedding

$(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{π}{⟼} (\begin{matrix} x \\ y \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) \overset{ι}{⟼} (\begin{matrix} x \\ y \\ 0 \end{matrix})$

then the composition $π \circ ι$ is the identity map $π \circ ι = id$ on $ℝ^{2}$ .

$(\begin{matrix} x \\ y \end{matrix}) \overset{ι}{⟼} (\begin{matrix} x \\ y \\ 0 \end{matrix}) \overset{π}{⟼} (\begin{matrix} x \\ y \end{matrix})$

We say that $ι$ is a right inverse of $π$ or, what is the same thing, that $π$ is a left inverse of $ι$ . However, composition in the other order $ι \circ π$ doesn’t give the identity map—here is a vector that is not sent to itself under $ι \circ π$ .

$(\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}) \overset{π}{⟼} (\begin{matrix} 0 \\ 0 \end{matrix}) \overset{ι}{⟼} (\begin{matrix} 0 \\ 0 \\ 0 \end{matrix})$

In fact, $π$ has no left inverse at all. For, if $f$ were to be a left inverse of $π$ then we would have

$(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{π}{⟼} (\begin{matrix} x \\ y \end{matrix}) \overset{f}{⟼} (\begin{matrix} x \\ y \\ z \end{matrix})$

for all of the infinitely many $z$ ’s. But a function $f$ cannot send a single argument $(\binom{x}{y})$ to more than one value.

So a function can have a right inverse but no left inverse, or a left inverse but no right inverse. A function can also fail to have an inverse on either side; one example is the zero transformation on $ℝ^{2}$ .

Some functions have a two-sided inverse, another function that is the inverse both from the left and from the right. For instance, the transformation given by $\vec{v} \mapsto 2 \cdot \vec{v}$ has the two-sided inverse $\vec{v} \mapsto (1 / 2) \cdot \vec{v}$ . The appendix shows that a function has a two-sided inverse if and only if it is both one-to-one and onto. The appendix also shows that if a function $f$ has a two-sided inverse then it is unique, so we call it ‘the’ inverse and write $f^{- 1}$ .

In addition, recall that we have shown in Theorem II.2.20 that if a linear map has a two-sided inverse then that inverse is also linear.

Thus, our goal in this subsection is, where a linear $h$ has an inverse, to find the relationship between ${Rep}_{B, D} (h)$ and ${Rep}_{D, B} (h^{- 1})$ .

Definition 4.1 A matrix $G$ is a left inverse matrix of the matrix $H$ if $G H$ is the identity matrix. It is a right inverse if $H G$ is the identity. A matrix $H$ with a two-sided inverse is an invertible matrix. That two-sided inverse is denoted $H^{- 1}$ .

Because of the correspondence between linear maps and matrices, statements about map inverses translate into statements about matrix inverses.

Lemma 4.2 If a matrix has both a left inverse and a right inverse then the two are equal.

Theorem 4.3 A matrix is invertible if and only if it is nonsingular.

Proof (For both results.) Given a matrix $H$ , fix spaces of appropriate dimension for the domain and codomain and fix bases for these spaces. With respect to these bases, $H$ represents a map $h$ . The statements are true about the map and therefore they are true about the matrix.

QED

Lemma 4.4 A product of invertible matrices is invertible: if $G$ and $H$ are invertible and $G H$ is defined then $G H$ is invertible and $(G H)^{- 1} = H^{- 1} G^{- 1}$ .

Proof Because the two matrices are invertible they are square, and because their product is defined they must both be $n \times n$ . Fix spaces and bases—say, $ℝ^{n}$ with the standard bases— to get maps $g, h : ℝ^{n} \to ℝ^{n}$ that are associated with the matrices, $G = {Rep}_{ℰ_{n}, ℰ_{n}} (g)$ and $H = {Rep}_{ℰ_{n}, ℰ_{n}} (h)$ .

Consider $h^{- 1} g^{- 1}$ . By the prior paragraph this composition is defined. This map is a two-sided inverse of $g h$ since $(h^{- 1} g^{- 1}) (g h) = h^{- 1} (id) h = h^{- 1} h = id$ and $(g h) (h^{- 1} g^{- 1}) = g (id) g^{- 1} = g g^{- 1} = id$ . The matrices representing the maps reflect this equality.

QED

This is the arrow diagram giving the relationship between map inverses and matrix inverses. It is a special case of the diagram relating function composition to matrix multiplication.

Inverse-map triangle: V with basis B maps by h, represented by H, to W with basis C, then by h inverse, represented by H inverse, back to V with basis B. The direct path is the identity map, represented by I.

Beyond its place in our program of seeing how to represent map operations, another reason for our interest in inverses comes from linear systems. A linear system is equivalent to a matrix equation, as here.

$\begin{array}{rcrcr} x_{1} & + & x_{2} & = & 3 \\ 2 x_{1} & - & x_{2} & = & 2 \end{array} ⟺ (\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \end{matrix}) = (\begin{matrix} 3 \\ 2 \end{matrix})$

By fixing spaces and bases (for instance, $ℝ^{2}, ℝ^{2}$ with the standard bases), we take the matrix $H$ to represent a map $h$ . The matrix equation then becomes this linear map equation.

$h (\vec{x}) = \vec{d}$

If we had a left inverse map $g$ then we could apply it to both sides $g \circ h (\vec{x}) = g (\vec{d})$ to get $\vec{x} = g (\vec{d})$ . Restating in terms of the matrices, we want to multiply by the inverse matrix ${Rep}_{C, B} (g) \cdot {Rep}_{C} (\vec{d})$ to get ${Rep}_{B} (\vec{x})$ .

Example 4.5 We can find a left inverse for the matrix just given

$(\begin{matrix} m & n \\ p & q \end{matrix}) (\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$

by using Gauss’s Method to solve the resulting linear system.

$\begin{array}{rcrcrcrcr} m & + & 2 n & = & 1 \\ m & - & n & = & 0 \\ p & + & 2 q & = & 0 \\ p & - & q & = & 1 \end{array}$

Answer: $m = 1 / 3$ , $n = 1 / 3$ , $p = 2 / 3$ , and $q = - 1 / 3$ . (This matrix is actually the two-sided inverse of $H$ ; the check is easy.) With it, we can solve the system from the prior example.

$(\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} 1 / 3 & 1 / 3 \\ 2 / 3 & - 1 / 3 \end{matrix}) (\begin{matrix} 3 \\ 2 \end{matrix}) = (\begin{matrix} 5 / 3 \\ 4 / 3 \end{matrix})$

Remark 4.6 Why solve systems with inverse matrices when we have Gauss’s Method? Beyond the conceptual appeal of representing the map inverse operation, solving linear systems this way has two advantages.

First, once we have done the work of finding an inverse then solving a system with the same coefficients but different constants is fast: if we change the constants on the right of the system above then we get a related problem

$(\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix}) (\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} 5 \\ 1 \end{matrix})$

that our inverse method solves quickly.

$(\begin{matrix} x \\ y \end{matrix}) = (\begin{matrix} 1 / 3 & 1 / 3 \\ 2 / 3 & - 1 / 3 \end{matrix}) (\begin{matrix} 5 \\ 1 \end{matrix}) = (\begin{matrix} 2 \\ 3 \end{matrix})$

Another advantage of inverses is that we can explore a system’s sensitivity to changes in the constants. For example, tweaking the $3$ on the right of the prior example’s system to

$(\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \end{matrix}) = (\begin{matrix} 3.01 \\ 2 \end{matrix})$

and solving with the inverse

$(\begin{matrix} 1 / 3 & 1 / 3 \\ 2 / 3 & - 1 / 3 \end{matrix}) (\begin{matrix} 3.01 \\ 2 \end{matrix}) = (\begin{matrix} (1 / 3) (3.01) + (1 / 3) (2) \\ (2 / 3) (3.01) - (1 / 3) (2) \end{matrix})$

shows that the first component of the solution changes by $1 / 3$ of the tweak, while the second component moves by $2 / 3$ of the tweak. This is sensitivity analysis. We could use it to decide how accurately we must specify the data in a linear model to ensure that the solution has a desired accuracy.

Lemma 4.7 A matrix $H$ is invertible if and only if it can be written as the product of elementary reduction matrices. We can compute the inverse by applying to the identity matrix the same row steps, in the same order, that Gauss-Jordan reduce $H$ .

Proof The matrix $H$ is invertible if and only if it is nonsingular and thus Gauss-Jordan reduces to the identity. By Corollary 3.23 we can do this reduction with elementary matrices.

$\begin{matrix} R_{r} \cdot R_{r - 1} \dots R_{1} \cdot H = I & (*) \end{matrix}$

For the first sentence of the result, note that elementary matrices are invertible because elementary row operations are reversible, and that their inverses are also elementary. Apply $R_{r}^{- 1}$ from the left to both sides of ( $*$ ). Then apply $R_{r - 1}^{- 1}$ , etc. The result gives $H$ as the product of elementary matrices $H = R_{1}^{- 1} \dots R_{r}^{- 1} \cdot I$ . (The $I$ there covers the case $r = 0$ .)

For the second sentence, group ( $*$ ) as $(R_{r} \cdot R_{r - 1} \dots R_{1}) \cdot H = I$ and recognize what’s in the parentheses as the inverse $H^{- 1} = R_{r} \cdot R_{r - 1} \dots R_{1} \cdot I$ . Restated: applying $R_{1}$ to the identity, followed by $R_{2}$ , etc., yields the inverse of $H$ .

QED

Example 4.8 To find the inverse of

$(\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix})$

do Gauss-Jordan reduction, meanwhile performing the same operations on the identity. For clerical convenience we write the matrix and the identity side-by-side and do the reduction steps together.

$\begin{aligned} (\begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 2 & - 1 & 0 & 1 \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 0 & - 3 & - 2 & 1 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- 1 / 3 ρ_{2}} (\begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 0 & 1 & 2 / 3 & - 1 / 3 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{2} + ρ_{1}} (\begin{array}{rrrr} 1 & 0 & 1 / 3 & 1 / 3 \\ 0 & 1 & 2 / 3 & - 1 / 3 \end{array}) \end{aligned}$

This calculation has found the inverse.

${(\begin{matrix} 1 & 1 \\ 2 & - 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 / 3 & 1 / 3 \\ 2 / 3 & - 1 / 3 \end{matrix})$

Example 4.9 This one happens to start with a row swap.

$\begin{aligned} (\begin{array}{rrrrrr} 0 & 3 & - 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & - 1 & 0 & 0 & 0 & 1 \end{array}) & ⟶_{\begin{matrix} \end{matrix}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 3 & - 1 & 1 & 0 & 0 \\ 1 & - 1 & 0 & 0 & 0 & 1 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{1} + ρ_{3}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 3 & - 1 & 1 & 0 & 0 \\ 0 & - 1 & - 1 & 0 & - 1 & 1 \end{array}) \\ ⋮ \\ ⟶_{\begin{matrix} \end{matrix}}^{} (\begin{array}{rrrrrr} 1 & 0 & 0 & 1 / 4 & 1 / 4 & 3 / 4 \\ 0 & 1 & 0 & 1 / 4 & 1 / 4 & - 1 / 4 \\ 0 & 0 & 1 & - 1 / 4 & 3 / 4 & - 3 / 4 \end{array}) \end{aligned}$

Example 4.10 This algorithm detects a non-invertible matrix when the left half won’t reduce to the identity.

$(\begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 2 & 2 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- 2 ρ_{1} + ρ_{2}} (\begin{array}{rrrr} 1 & 1 & 1 & 0 \\ 0 & 0 & - 2 & 1 \end{array})$

With this procedure we can give a formula for the inverse of a general $2 \times 2$ matrix, which is worth memorizing.

Corollary 4.11 The inverse for a $2 \times 2$ matrix exists and equals

${(\begin{matrix} a & b \\ c & d \end{matrix})}^{- 1} = \frac{1}{a d - b c} (\begin{matrix} d & - b \\ - c & a \end{matrix})$

if and only if $a d - b c \neq 0$ .

Proof This computation is Exercise 4.21.

QED

We have seen in this subsection, as in the subsection on Mechanics of Matrix Multiplication, how to exploit the correspondence between linear maps and matrices. We can fruitfully study both maps and matrices, translating back and forth to use whichever is handiest.

Over the course of this entire section we have developed an algebra system for matrices. We can compare it with the familiar algebra of real numbers. Matrix addition and subtraction work in much the same way as the real number operations except that they only combine same-sized matrices. Scalar multiplication is in some ways an extension of real number multiplication. We also have a matrix multiplication operation and its inverse that are somewhat like the familiar real number operations (associativity, and distributivity over addition, for example), but there are differences (failure of commutativity). This section provides an example that algebra systems other than the usual real number one can be interesting and useful.

Exercises

Exercise 4.12 Worked answer

Supply the intermediate steps in Example 4.9.

Back to Exercise 4.12

Answer. Here is one way to proceed. Follow

$⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 3 & - 1 & 1 & 0 & 0 \\ 1 & - 1 & 0 & 0 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- ρ_{1} + ρ_{3}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 3 & - 1 & 1 & 0 & 0 \\ 0 & - 1 & - 1 & 0 & - 1 & 1 \end{array})$

with

$\begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{(1 / 3) ρ_{2} + ρ_{3}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 3 & - 1 & 1 & 0 & 0 \\ 0 & 0 & - 4 / 3 & 1 / 3 & - 1 & 1 \end{array}) \\ ⟶_{\begin{matrix} - (3 / 4) ρ_{3} \end{matrix}}^{(1 / 3) ρ_{2}} (\begin{array}{rrrrrr} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & - 1 / 3 & 1 / 3 & 0 & 0 \\ 0 & 0 & 1 & - 1 / 4 & 3 / 4 & - 3 / 4 \end{array}) \\ ⟶_{\begin{matrix} - ρ_{3} + ρ_{1} \end{matrix}}^{(1 / 3) ρ_{3} + ρ_{2}} (\begin{array}{rrrrrr} 1 & 0 & 0 & 1 / 4 & 1 / 4 & 3 / 4 \\ 0 & 1 & 0 & 1 / 4 & 1 / 4 & - 1 / 4 \\ 0 & 0 & 1 & - 1 / 4 & 3 / 4 & - 3 / 4 \end{array}) \end{aligned}$

and read the answer off of the right side.
Exercise 4.13 Worked answer

Recommended. Use Corollary 4.11 to decide if each matrix has an inverse.
1. $(\begin{matrix} 2 & 1 \\ - 1 & 1 \end{matrix})$
2. $(\begin{matrix} 0 & 4 \\ 1 & - 3 \end{matrix})$
3. $(\begin{matrix} 2 & - 3 \\ - 4 & 6 \end{matrix})$
Back to Exercise 4.13

Answer.
1. Yes, it has an inverse: $a d - b c = 2 \cdot 1 - 1 \cdot (- 1) \neq 0$ .
2. Yes.
3. No.
Exercise 4.14 Worked answer

Recommended. For each invertible matrix in the prior problem, use Corollary 4.11 to find its inverse.
Back to Exercise 4.14

Answer.
1. $\frac{1}{2 \cdot 1 - 1 \cdot (- 1)} \cdot (\begin{matrix} 1 & - 1 \\ 1 & 2 \end{matrix}) = \frac{1}{3} \cdot (\begin{matrix} 1 & - 1 \\ 1 & 2 \end{matrix}) = (\begin{matrix} 1 / 3 & - 1 / 3 \\ 1 / 3 & 2 / 3 \end{matrix})$
2. $\frac{1}{0 \cdot (- 3) - 4 \cdot 1} \cdot (\begin{matrix} - 3 & - 4 \\ - 1 & 0 \end{matrix}) = (\begin{matrix} 3 / 4 & 1 \\ 1 / 4 & 0 \end{matrix})$
3. The prior question shows that no inverse exists.
Exercise 4.15 Worked answer

Recommended. Find the inverse, if it exists, by using the Gauss-Jordan Method. Check the answers for the $2 \times 2$ matrices with Corollary 4.11.
1. $(\begin{matrix} 3 & 1 \\ 0 & 2 \end{matrix})$
2. $(\begin{matrix} 2 & 1 / 2 \\ 3 & 1 \end{matrix})$
3. $(\begin{matrix} 2 & - 4 \\ - 1 & 2 \end{matrix})$
4. $(\begin{matrix} 1 & 1 & 3 \\ 0 & 2 & 4 \\ - 1 & 1 & 0 \end{matrix})$
5. $(\begin{matrix} 0 & 1 & 5 \\ 0 & - 2 & 4 \\ 2 & 3 & - 2 \end{matrix})$
6. $(\begin{matrix} 2 & 2 & 3 \\ 1 & - 2 & - 3 \\ 4 & - 2 & - 3 \end{matrix})$
Back to Exercise 4.15

Answer.
1. The reduction is routine.
  
  $\begin{aligned} (\begin{array}{rrrr} 3 & 1 & 1 & 0 \\ 0 & 2 & 0 & 1 \end{array}) & ⟶_{\begin{matrix} (1 / 2) ρ_{2} \end{matrix}}^{(1 / 3) ρ_{1}} (\begin{array}{rrrr} 1 & 1 / 3 & 1 / 3 & 0 \\ 0 & 1 & 0 & 1 / 2 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (1 / 3) ρ_{2} + ρ_{1}} (\begin{array}{rrrr} 1 & 0 & 1 / 3 & - 1 / 6 \\ 0 & 1 & 0 & 1 / 2 \end{array}) \end{aligned}$
  
  This answer agrees with the answer from the check.
  
  ${(\begin{matrix} 3 & 1 \\ 0 & 2 \end{matrix})}^{- 1} = \frac{1}{3 \cdot 2 - 0 \cdot 1} \cdot (\begin{matrix} 2 & - 1 \\ 0 & 3 \end{matrix}) = \frac{1}{6} \cdot (\begin{matrix} 2 & - 1 \\ 0 & 3 \end{matrix})$
2. This reduction is easy.
  
  $\begin{matrix} (\begin{array}{rrrr} 2 & 1 / 2 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (3 / 2) ρ_{1} + ρ_{2}} (\begin{array}{rrrr} 2 & 1 / 2 & 1 & 0 \\ 0 & 1 / 4 & - 3 / 2 & 1 \end{array}) \\ ⟶_{\begin{array}{l} 4 ρ_{2} \end{array}}^{(1 / 2) ρ_{1}} (\begin{array}{rrrr} 1 & 1 / 4 & 1 / 2 & 0 \\ 0 & 1 & - 6 & 4 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (1 / 4) ρ_{2} + ρ_{1}} (\begin{array}{rrrr} 1 & 0 & 2 & - 1 \\ 0 & 1 & - 6 & 4 \end{array}) \end{matrix}$
  
  The check agrees.
  
  $\frac{1}{2 \cdot 1 - 3 \cdot (1 / 2)} \cdot (\begin{matrix} 1 & - 1 / 2 \\ - 3 & 2 \end{matrix}) = 2 \cdot (\begin{matrix} 1 & - 1 / 2 \\ - 3 & 2 \end{matrix})$
3. Trying the Gauss-Jordan reduction
  
  $(\begin{array}{rrrr} 2 & - 4 & 1 & 0 \\ - 1 & 2 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{(1 / 2) ρ_{1} + ρ_{2}} (\begin{array}{rrrr} 2 & - 4 & 1 & 0 \\ 0 & 0 & 1 / 2 & 1 \end{array})$
  
  shows that the left side won’t reduce to the identity, so no inverse exists. The check $a d - b c = 2 \cdot 2 - (- 4) \cdot (- 1) = 0$ agrees.
4. This produces an inverse.
  
  $\begin{matrix} (\begin{array}{rrrrrr} 1 & 1 & 3 & 1 & 0 & 0 \\ 0 & 2 & 4 & 0 & 1 & 0 \\ - 1 & 1 & 0 & 0 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{1} + ρ_{3}} (\begin{array}{rrrrrr} 1 & 1 & 3 & 1 & 0 & 0 \\ 0 & 2 & 4 & 0 & 1 & 0 \\ 0 & 2 & 3 & 1 & 0 & 1 \end{array}) \\ \begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{2} + ρ_{3}} (\begin{array}{rrrrrr} 1 & 1 & 3 & 1 & 0 & 0 \\ 0 & 2 & 4 & 0 & 1 & 0 \\ 0 & 0 & - 1 & 1 & - 1 & 1 \end{array}) ⟶_{\begin{matrix} - ρ_{3} \end{matrix}}^{(1 / 2) ρ_{2}} (\begin{array}{rrrrrr} 1 & 1 & 3 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 / 2 & 0 \\ 0 & 0 & 1 & - 1 & 1 & - 1 \end{array}) \\ ⟶_{\begin{matrix} - 3 ρ_{3} + ρ_{1} \end{matrix}}^{- 2 ρ_{3} + ρ_{2}} (\begin{array}{rrrrrr} 1 & 1 & 0 & 4 & - 3 & 3 \\ 0 & 1 & 0 & 2 & - 3 / 2 & 2 \\ 0 & 0 & 1 & - 1 & 1 & - 1 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- ρ_{2} + ρ_{1}} (\begin{array}{rrrrrr} 1 & 0 & 0 & 2 & - 3 / 2 & 1 \\ 0 & 1 & 0 & 2 & - 3 / 2 & 2 \\ 0 & 0 & 1 & - 1 & 1 & - 1 \end{array}) \end{aligned} \end{matrix}$
5. This is one way to do the reduction.
  
  $\begin{matrix} (\begin{array}{rrrrrr} 0 & 1 & 5 & 1 & 0 & 0 \\ 0 & - 2 & 4 & 0 & 1 & 0 \\ 2 & 3 & - 2 & 0 & 0 & 1 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{ρ_{3} \leftrightarrow ρ_{1}} (\begin{array}{rrrrrr} 2 & 3 & - 2 & 0 & 0 & 1 \\ 0 & - 2 & 4 & 0 & 1 & 0 \\ 0 & 1 & 5 & 1 & 0 & 0 \end{array}) \\ \begin{aligned} ⟶_{\begin{matrix} \end{matrix}}^{(1 / 2) ρ_{2} + ρ_{3}} (\begin{array}{rrrrrr} 2 & 3 & - 2 & 0 & 0 & 1 \\ 0 & - 2 & 4 & 0 & 1 & 0 \\ 0 & 0 & 7 & 1 & 1 / 2 & 0 \end{array}) \\ ⟶_{\begin{matrix} - (1 / 2) ρ_{2} \\ (1 / 7) ρ_{3} \end{matrix}}^{(1 / 2) ρ_{1}} (\begin{array}{rrrrrr} 1 & 3 / 2 & - 1 & 0 & 0 & 1 / 2 \\ 0 & 1 & - 2 & 0 & - 1 / 2 & 0 \\ 0 & 0 & 1 & 1 / 7 & 1 / 14 & 0 \end{array}) \\ ⟶_{\begin{matrix} ρ_{3} + ρ_{1} \end{matrix}}^{2 ρ_{3} + ρ_{2}} (\begin{array}{rrrrrr} 1 & 3 / 2 & 0 & 1 / 7 & 1 / 14 & 1 / 2 \\ 0 & 1 & 0 & 2 / 7 & - 5 / 14 & 0 \\ 0 & 0 & 1 & 1 / 7 & 1 / 14 & 0 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (3 / 2) ρ_{2} + ρ_{1}} (\begin{array}{rrrrrr} 1 & 0 & 0 & - 2 / 7 & 17 / 28 & 1 / 2 \\ 0 & 1 & 0 & 2 / 7 & - 5 / 14 & 0 \\ 0 & 0 & 1 & 1 / 7 & 1 / 14 & 0 \end{array}) \end{aligned} \end{matrix}$
6. There is no inverse.
  
  $\begin{aligned} (\begin{array}{rrrrrr} 2 & 2 & 3 & 1 & 0 & 0 \\ 1 & - 2 & - 3 & 0 & 1 & 0 \\ 4 & - 2 & - 3 & 0 & 0 & 1 \end{array}) & ⟶_{\begin{matrix} - 2 ρ_{1} + ρ_{3} \end{matrix}}^{- (1 / 2) ρ_{1} + ρ_{2}} (\begin{array}{rrrrrr} 2 & 2 & 3 & 1 & 0 & 0 \\ 0 & - 3 & - 9 / 2 & - 1 / 2 & 1 & 0 \\ 0 & - 6 & - 9 & - 2 & 0 & 1 \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- 2 ρ_{2} + ρ_{3}} (\begin{array}{rrrrrr} 2 & 2 & 3 & 1 & 0 & 0 \\ 0 & - 3 & - 9 / 2 & - 1 / 2 & 1 & 0 \\ 0 & 0 & 0 & - 1 & - 2 & 1 \end{array}) \end{aligned}$
  
  As a check, note that the third column of the starting matrix is $3 / 2$ times the second, and so it is indeed singular and therefore has no inverse.
Exercise 4.16 Worked answer

Recommended. What matrix has this one for its inverse?

$(\begin{matrix} 1 & 3 \\ 2 & 5 \end{matrix})$

Back to Exercise 4.16

Answer. We can use Corollary 4.11.

$\frac{1}{1 \cdot 5 - 2 \cdot 3} \cdot (\begin{matrix} 5 & - 3 \\ - 2 & 1 \end{matrix}) = (\begin{matrix} - 5 & 3 \\ 2 & - 1 \end{matrix})$
Exercise 4.17 Worked answer

How does the inverse operation interact with scalar multiplication and addition of matrices?
1. What is the inverse of $r H$ ?
2. Is $(H + G)^{- 1} = H^{- 1} + G^{- 1}$ ?
Back to Exercise 4.17

Answer.
1. The proof that the inverse is $r^{- 1} H^{- 1} = (1 / r) \cdot H^{- 1}$ (provided, of course, that the matrix is invertible) is easy.
2. No. For one thing, the fact that $H + G$ has an inverse doesn’t imply that $H$ has an inverse or that $G$ has an inverse. Neither of these matrices is invertible but their sum is.
  
  $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix})$
  
  Another point is that just because $H$ and $G$ each has an inverse doesn’t mean $H + G$ has an inverse; here is an example.
  
  $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix})$
  
  Still a third point is that, even if the two matrices have inverses, and the sum has an inverse, doesn’t imply that the equation holds:
  
  ${(\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix})}^{- 1} = {(\begin{matrix} 1 / 2 & 0 \\ 0 & 1 / 2 \end{matrix})}^{- 1} {(\begin{matrix} 3 & 0 \\ 0 & 3 \end{matrix})}^{- 1} = {(\begin{matrix} 1 / 3 & 0 \\ 0 & 1 / 3 \end{matrix})}^{- 1}$
  
  but
  
  ${(\begin{matrix} 5 & 0 \\ 0 & 5 \end{matrix})}^{- 1} = {(\begin{matrix} 1 / 5 & 0 \\ 0 & 1 / 5 \end{matrix})}^{- 1}$
  
  and $(1 / 2)_{+} (1 / 3)$ does not equal $1 / 5$ .
Exercise 4.18 Worked answer

Recommended. Is $(T^{k})^{- 1} = (T^{- 1})^{k}$ ?

Back to Exercise 4.18

Answer. Yes: $T^{k} (T^{- 1})^{k} = (T T \dots T) \cdot (T^{- 1} T^{- 1} \dots T^{- 1}) = T^{k - 1} (T T^{- 1}) (T^{- 1})^{k - 1} = \dots = I$ .
Exercise 4.19 Worked answer

Is $H^{- 1}$ invertible?

Back to Exercise 4.19

Answer. Yes, the inverse of $H^{- 1}$ is $H$ .
Exercise 4.20 Worked answer

For each real number $θ$ let $t_{θ} : ℝ^{2} \to ℝ^{2}$ be represented with respect to the standard bases by this matrix.

$(\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix})$

Show that $t_{θ_{1} + θ_{2}} = t_{θ_{1}} \cdot t_{θ_{2}}$ . Show also that ${t_{θ}}^{- 1} = t_{- θ}$ .

Back to Exercise 4.20

Answer. One way to check that the first is true is with the angle sum formulas from trigonometry.

$\begin{matrix} (\begin{matrix} \cos (θ_{1} + θ_{2}) & - \sin (θ_{1} + θ_{2}) \\ \sin (θ_{1} + θ_{2}) & \cos (θ_{1} + θ_{2}) \end{matrix}) \\ \begin{aligned} = (\begin{array}{c} \cos θ_{1} \cos θ_{2} - \sin θ_{1} \sin θ_{2} & - \sin θ_{1} \cos θ_{2} - \cos θ_{1} \sin θ_{2} \\ \sin θ_{1} \cos θ_{2} + \cos θ_{1} \sin θ_{2} & \cos θ_{1} \cos θ_{2} - \sin θ_{1} \sin θ_{2} \end{array}) \\ = (\begin{array}{c} \cos θ_{1} & - \sin θ_{1} \\ \sin θ_{1} & \cos θ_{1} \end{array}) (\begin{array}{c} \cos θ_{2} & - \sin θ_{2} \\ \sin θ_{2} & \cos θ_{2} \end{array}) \end{aligned} \end{matrix}$

Checking the second equation in this way is similar.

Of course, the equations can be not just checked but also understood by recalling that $t_{θ}$ is the map that rotates vectors about the origin through an angle of $θ$ radians.
Exercise 4.21 Worked answer

Do the calculations for the proof of Corollary 4.11.

Back to Exercise 4.21

Answer. There are two cases. For the first case we assume that $a$ is nonzero. Then

$⟶_{\begin{array}{l} \end{array}}^{- (c / a) ρ_{1} + ρ_{2}} (\begin{array}{cccc} a & b & 1 & 0 \\ 0 & - (b c / a) + d & - c / a & 1 \end{array}) = (\begin{array}{cccc} a & b & 1 & 0 \\ 0 & (a d - b c) / a & - c / a & 1 \end{array})$

shows that the matrix is invertible (in this $a \neq 0$ case) if and only if $a d - b c \neq 0$ . To find the inverse, we finish with the Jordan half of the reduction.

$\begin{aligned} ⟶_{\begin{matrix} (a / a d - b c) ρ_{2} \end{matrix}}^{(1 / a) ρ_{1}} (\begin{array}{cccc} 1 & b / a & 1 / a & 0 \\ 0 & 1 & - c / (a d - b c) & a / (a d - b c) \end{array}) \\ ⟶_{\begin{matrix} \end{matrix}}^{- (b / a) ρ_{2} + ρ_{1}} (\begin{array}{cccc} 1 & 0 & d / (a d - b c) & - b / (a d - b c) \\ 0 & 1 & - c / (a d - b c) & a / (a d - b c) \end{array}) \end{aligned}$

The other case is the $a = 0$ case. We swap to get $c$ into the $1, 1$ position.

$⟶_{\begin{array}{l} \end{array}}^{ρ_{1} \leftrightarrow ρ_{2}} (\begin{array}{cccc} c & d & 0 & 1 \\ 0 & b & 1 & 0 \end{array})$

This matrix is nonsingular if and only if both $b$ and $c$ are nonzero (which, under the case assumption that $a = 0$ , holds if and only if $a d - b c \neq 0$ ). To find the inverse we do the Jordan half.

$⟶_{\begin{array}{l} (1 / b) ρ_{2} \end{array}}^{(1 / c) ρ_{1}} (\begin{array}{cccc} 1 & d / c & 0 & 1 / c \\ 0 & 1 & 1 / b & 0 \end{array}) ⟶_{\begin{array}{l} \end{array}}^{- (d / c) ρ_{2} + ρ_{1}} (\begin{array}{cccc} 1 & 0 & - d / b c & 1 / c \\ 0 & 1 & 1 / b & 0 \end{array})$

(Note that this is what is required, since $a = 0$ gives that $a d - b c = - b c$ ).
Exercise 4.22 Worked answer

Show that this matrix

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

has infinitely many right inverses. Show also that it has no left inverse.

Back to Exercise 4.22

Answer. With $H$ a $2 \times 3$ matrix, in looking for a matrix $G$ such that the combination $H G$ acts as the $2 \times 2$ identity we need $G$ to be $3 \times 2$ . Setting up the equation

$(\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} m & n \\ p & q \\ r & s \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$

and solving the resulting linear system

$\begin{array}{rcrcrcrcrcrcr} m & + r & = & 1 \\ n & + s & = & 0 \\ p & = & 0 \\ q & = & 1 \end{array}$

gives infinitely many solutions.

${(\begin{matrix} m \\ n \\ p \\ q \\ r \\ s \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}) + r \cdot (\begin{matrix} - 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{matrix}) + s \cdot (\begin{matrix} 0 \\ - 1 \\ 0 \\ 0 \\ 0 \\ 1 \end{matrix}) ∣ r, s \in ℝ}$

Thus $H$ has infinitely many right inverses.

As for left inverses, the equation

$(\begin{matrix} a & b \\ c & d \end{matrix}) (\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$

gives rise to a linear system with nine equations and four unknowns.

$\begin{array}{rcrcrcrcrcrcr} a & = & 1 \\ b & = & 0 \\ a & = & 0 \\ c & = & 0 \\ d & = & 1 \\ c & = & 0 \\ e & = & 0 \\ f & = & 0 \\ e & = & 1 \end{array}$

This system is inconsistent (the first equation conflicts with the third, as do the seventh and ninth) and so there is no left inverse.
Exercise 4.23 Worked answer

In the review of inverses example, starting this subsection, how many left inverses has $ι$ ?

Back to Exercise 4.23

Answer. With respect to the standard bases we have

${Rep}_{ℰ_{2}, ℰ_{3}} (ι) = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix})$

and setting up the equation to find the matrix inverse

$(\begin{matrix} a & b & c \\ d & e & f \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) = {Rep}_{ℰ_{2}, ℰ_{2}} (id)$

gives rise to a linear system.

$\begin{array}{rcrcrcrcrcrcr} a & = & 1 \\ b & = & 0 \\ d & = & 0 \\ e & = & 1 \end{array}$

There are infinitely many solutions in $a, \dots, f$ to this system because two of these variables are entirely unrestricted

${(\begin{matrix} a \\ b \\ c \\ d \\ e \\ f \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{matrix}) + c \cdot (\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) + f \cdot (\begin{matrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{matrix}) ∣ c, f \in ℝ}$

and so there are infinitely many solutions to the matrix equation.

${(\begin{matrix} 1 & 0 & c \\ 0 & 1 & f \end{matrix}) ∣ c, f \in ℝ}$

With the bases still fixed at $ℰ_{2}, ℰ_{2}$ , for instance taking $c = 2$ and $f = 3$ gives a matrix representing this map.

$(\begin{matrix} x \\ y \\ z \end{matrix}) \overset{f_{2, 3}}{⟼} (\begin{matrix} x + 2 z \\ y + 3 z \end{matrix})$

The check that $f_{2, 3} \circ ι$ is the identity map on $ℝ^{2}$ is easy.
Exercise 4.24 Worked answer

If a matrix has infinitely many right-inverses, can it have infinitely many left-inverses? Must it have?

Back to Exercise 4.24

Answer. By Lemma 4.2 it cannot have infinitely many left inverses, because a matrix with both left and right inverses has only one of each (and that one of each is one of both—the left and right inverse matrices are equal).
Exercise 4.25 Worked answer

Assume that $g : V \to W$ is linear. One of these is true, the other is false. Which is which?
1. If $f : W \to V$ is a left inverse of $g$ then $f$ must be linear.
2. If $f : W \to V$ is a right inverse of $g$ then $f$ must be linear.
Back to Exercise 4.25

Answer.
1. True, It must be linear, as the proof from Theorem II.2.20 shows.
2. False. It may be linear, but it need not be. Consider the projection map $π : ℝ^{3} \to ℝ^{2}$ described at the start of this subsection. Define $η : ℝ^{2} \to ℝ^{3}$ in this way.
  
  $(\begin{matrix} x \\ y \end{matrix}) \mapsto (\begin{matrix} x \\ y \\ 1 \end{matrix})$
  
  It is a right inverse of $π$ because $π \circ η$ does this.
  
  $(\begin{matrix} x \\ y \end{matrix}) \mapsto (\begin{matrix} x \\ y \\ 1 \end{matrix}) \mapsto (\begin{matrix} x \\ y \end{matrix})$
  
  It is not linear because it does not map the zero vector to the zero vector.
Exercise 4.26 Worked answer

Recommended. Assume that $H$ is invertible and that $H G$ is the zero matrix. Show that $G$ is a zero matrix.

Back to Exercise 4.26

Answer. The associativity of matrix multiplication gives $H^{- 1} (H G) = H^{- 1} Z = Z$ and also $H^{- 1} (H G) = (H^{- 1} H) G = I G = G$ .
Exercise 4.27 Worked answer

Prove that if $H$ is invertible then the inverse commutes with a matrix $G H^{- 1} = H^{- 1} G$ if and only if $H$ itself commutes with that matrix $G H = H G$ .

Back to Exercise 4.27

Answer. Multiply both sides of the first equation by $H$ .
Exercise 4.28 Worked answer

Recommended. Show that if $T$ is square and if $T^{4}$ is the zero matrix then $(I - T)^{- 1} = I + T + T^{2} + T^{3}$ . Generalize.

Back to Exercise 4.28

Answer. Checking that when $I - T$ is multiplied on both sides by that expression (assuming that $T^{4}$ is the zero matrix) then the result is the identity matrix is easy. The obvious generalization is that if $T^{n}$ is the zero matrix then $(I - T)^{- 1} = I + T + T^{2} + \dots + T^{n - 1}$ ; the check again is easy.
Exercise 4.29 Worked answer

Recommended. Let $D$ be diagonal. Describe $D^{2}$ , $D^{3}$ , …, etc. Describe $D^{- 1}$ , $D^{- 2}$ , …, etc. Define $D^{0}$ appropriately.

Back to Exercise 4.29

Answer. The powers of the matrix are formed by taking the powers of the diagonal entries. That is, $D^{2}$ is all zeros except for diagonal entries of ${d_{1, 1}}^{2}$ , ${d_{2, 2}}^{2}$ , etc. This suggests defining $D^{0}$ to be the identity matrix.
Exercise 4.30 Worked answer

Prove that any matrix row-equivalent to an invertible matrix is also invertible.

Back to Exercise 4.30

Answer. Assume that $B$ is row equivalent to $A$ and that $A$ is invertible. Because they are row-equivalent, there is a sequence of row steps to reduce one to the other. We can do that reduction with matrices, for instance, $A$ can change by row operations to $B$ as $B = R_{n} \dots R_{1} A$ . This equation gives $B$ as a product of invertible matrices and by Lemma 4.4 then, $B$ is also invertible.
Exercise 4.31 Worked answer

The first question below appeared as Exercise 2.30.
1. Show that the rank of the product of two matrices is less than or equal to the minimum of the rank of each.
2. Show that if $T$ and $S$ are square then $T S = I$ if and only if $S T = I$ .
Back to Exercise 4.31

Answer.
1. See the answer to Exercise 2.30.
2. We will show that both conditions are equivalent to the condition that the two matrices be nonsingular.
  
  As $T$ and $S$ are square and their product is defined, they are equal-sized, say $n \times n$ . Consider the $T S = I$ half. By the prior item the rank of $I$ is less than or equal to the minimum of the rank of $T$ and the rank of $S$ . But the rank of $I$ is $n$ , so the rank of $T$ and the rank of $S$ must each be $n$ . Hence each is nonsingular.
  
  The same argument shows that $S T = I$ implies that each is nonsingular.
Exercise 4.32 Worked answer

Show that the inverse of a permutation matrix is its transpose.

Back to Exercise 4.32

Answer. Inverses are unique, so we need only show that it works. The check appears above as Exercise 3.38.
Exercise 4.33 Worked answer
1. Show that ${(G H)}^{𝖳} = H^{𝖳} G^{𝖳}$ .
2. A square matrix is symmetric if each $i, j$ entry equals the $j, i$ entry (that is, if the matrix equals its transpose). Show that the matrices $H H^{𝖳}$ and $H^{𝖳} H$ are symmetric.
3. Show that the inverse of the transpose is the transpose of the inverse.
4. Show that the inverse of a symmetric matrix is symmetric.
Back to Exercise 4.33

Answer.
1. See the answer for Exercise 2.27.
2. See the answer for Exercise 2.27.
3. Apply the first part to $I = A A^{- 1}$ to get $I = I^{𝖳} = {(A A^{- 1})}^{𝖳} = {(A^{- 1})}^{𝖳} A^{𝖳}$ .
4. Apply the prior item with $A^{𝖳} = A$ , as $A$ is symmetric.
Exercise 4.34 Worked answer

Recommended.
1. Prove that the composition of the projections $π_{x}, π_{y} : ℝ^{3} \to ℝ^{3}$ is the zero map despite that neither is the zero map.
2. Prove that the composition of the derivatives $d^{2} / d x^{2}, d^{3} / d x^{3} : 𝒫_{4} \to 𝒫_{4}$ is the zero map despite that neither map is the zero map.
3. Give matrix equations representing each of the prior two items.
When two things multiply to give zero despite that neither is zero, each is said to be a zero divisor. Prove that no zero divisor is invertible.

Back to Exercise 4.34

Answer. For the answer to the items making up the first half, see Exercise 2.32. For the proof in the second half, assume that $A$ is a zero divisor so there is a nonzero matrix $B$ with $A B = Z$ (or else $B A = Z$ ; this case is similar), If $A$ is invertible then $A^{- 1} (A B) = (A^{- 1} A) B = I B = B$ but also $A^{- 1} (A B) = A^{- 1} Z = Z$ , contradicting that $B$ is nonzero.
Exercise 4.35 Worked answer

In the algebra of real numbers, quadratic equations have at most two solutions. Matrix algebra is different. Show that the $2 \times 2$ matrix equation $T^{2} = I$ has more than two solutions.

Back to Exercise 4.35

Answer. There are infinitely many $2 \times 2$ matrices $T$ that square to the identity. Here are four.

$(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} - 1 & 0 \\ 0 & - 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}) (\begin{matrix} - 1 & 0 \\ 0 & 1 \end{matrix})$

Two more are

$(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 0 & - 1 \\ - 1 & 0 \end{matrix})$

and here is another

$\frac{1}{5} (\begin{matrix} 3 & 4 \\ 4 & - 3 \end{matrix})$

(in this last one the pattern involves Pythagorean triples, numbers $r, s, t \in ℝ$ such that $r^{2} + s^{2} = t^{2}$ ). Remark: see also https://en.wikipedia.org/wiki/Square_root_of_a_2_by_2_matrix.
Exercise 4.36 Worked answer

Is the relation ‘is a two-sided inverse of’ transitive? Reflexive? Symmetric?

Back to Exercise 4.36

Answer. It is not reflexive since, for instance,

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

is not a two-sided inverse of itself. The same example shows that it is not transitive. That matrix has this two-sided inverse

$G = (\begin{matrix} 1 & 0 \\ 0 & 1 / 2 \end{matrix})$

and while $H$ is a two-sided inverse of $G$ and $G$ is a two-sided inverse of $H$ , we know that $H$ is not a two-sided inverse of $H$ . However, the relation is symmetric: if $G$ is a two-sided inverse of $H$ then $G H = I = H G$ and therefore $H$ is also a two-sided inverse of $G$ .
Exercise 4.37 Worked answer

[Am. Math. Mon., Nov. 1951] Prove: if the sum of the elements of each row of a square matrix is $k$ , then the sum of the elements in each row of the inverse matrix is $1 / k$ .

Back to Exercise 4.37

Answer. This is how the answer was given in the cited source. Let $A$ be $m \times m$ , non-singular, with the stated property. Let $B$ be its inverse. Then for $n \leq m$ ,

$1 = \sum_{r = 1}^{m} δ_{n r} = \sum_{r = 1}^{m} \sum_{s = 1}^{m} b_{n s} a_{s r} = \sum_{s = 1}^{m} \sum_{r = 1}^{m} b_{n s} a_{s r} = k \sum_{s = 1}^{m} b_{n s}$

( $A$ is singular if $k = 0$ ).

References cited in this section

Cleary

R. Cleary, private communication, Nov. 2011.

Putnam, 1990, A-5

William Lowell Putnam Mathematical Competition, Problem A-5, 1990.

Am. Math. Mon., Dec. 1966

Hans Liebeck, A Proof of the Equality of Column Rank and Row Rank of a Matrix American Mathematical Monthly, vol. 73 no. 10 (Dec. 1966), p. 1114.

Ackerson

R. H. Ackerson, A Note on Vector Spaces, American Mathematical Monthly, vol. 62 no. 10 (Dec. 1955), p. 721.

Am. Math. Mon., Nov. 1951

Albert Wilansky, The Row-Sums of the Inverse Matrix, American Mathematical Monthly, vol. 58 no. 9 (Nov. 1951), p. 614.

	regular	overtime
Alan	40	12
Betty	35	6
Catherine	40	18
Donald	28	0

	wage
regular	$$ 25.00$
overtime	$$ 45.00$