2.4 Matrix multiplication · Matrix Theory

Once bases are fixed, a linear map and its matrix carry the same information (Theorem 2.3.20). Linear maps can be composed (Proposition 2.1.17), so matrices should be able to multiply, and the product of two matrices should be the matrix of the composite. This section takes that as the definition of the product. The formula for the entries, the algebraic laws, and the failures of commutativity and cancellation all follow from it, and each of them is the shadow of a fact about composition.

Throughout, $𝑈$ , $𝑉$ , and $𝑊$ are vector spaces over $𝐹$ with bases $𝒜︀ = 𝐮_{1}, \dots, 𝐮_{𝑛}$ of $𝑈$ , $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑚}$ of $𝑉$ , and $𝒞︀ = 𝐰_{1}, \dots, 𝐰_{ℓ}$ of $𝑊$ , where $𝑛, 𝑚, ℓ \geq 1$ . As in Notation 2.1.18, we write $𝑇 𝑆$ for the composite $𝑇 \circ 𝑆$ .

2.4.1The product of two matrices

Intuition (Computing $[𝑇 𝑆]$ from $[𝑇]$ and $[𝑆]$ ). Let $𝑆 \in L (𝑈, 𝑉)$ and $𝑇 \in L (𝑉, 𝑊)$ , so that $𝑇 𝑆 \in L (𝑈, 𝑊)$ . The $𝑗$ -th column of ${[𝑇 𝑆]}_{𝒞︀ 𝒜︀}$ is the coordinate vector of $(𝑇 𝑆) (𝐮_{𝑗}) =$ $𝑇 (𝑆 (𝐮_{𝑗}))$ . By Theorem 2.3.9, applied to $𝑇$ at the vector $𝑆 (𝐮_{𝑗})$ ,

{[𝑇 (𝑆 (𝐮_{𝑗}))]}_{𝒞︀} = {[𝑇]}_{𝒞︀ ℬ︀} {[𝑆 (𝐮_{𝑗})]}_{ℬ︀},

and ${[𝑆 (𝐮_{𝑗})]}_{ℬ︀}$ is the $𝑗$ -th column of ${[𝑆]}_{ℬ︀ 𝒜︀}$ . So the $𝑗$ -th column of ${[𝑇 𝑆]}_{𝒞︀ 𝒜︀}$ is ${[𝑇]}_{𝒞︀ ℬ︀}$ times the $𝑗$ -th column of ${[𝑆]}_{ℬ︀ 𝒜︀}$ . As with the matrix–vector product in Section 2.3.2, the answer no longer mentions $𝑆$ , $𝑇$ , the spaces, or the bases. It is computed from the two matrices alone, so it is an operation on matrices, and we give it a name.

Definition 2.4.1 (Matrix product). Let $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ , and let $𝐛_{1}, \dots, 𝐛_{𝑛} \in 𝐹^{𝑚}$ be the columns of $𝐵$ . The product $𝐴 𝐵$ is the $ℓ \times 𝑛$ matrix whose $𝑗$ -th column is $𝐴 𝐛_{𝑗}$ :

𝐴 𝐵 = (\begin{matrix} 𝐴 𝐛_{1} & 𝐴 𝐛_{2} & \dots & 𝐴 𝐛_{𝑛} \end{matrix}) .

It is defined only when the number of columns of $𝐴$ equals the number of rows of $𝐵$ . By Proposition 2.3.11, applied to the $𝑗$ -th column, the entry of $𝐴 𝐵$ in row $𝑖$ and column $𝑗$ is

𝑎_{𝑖 1} 𝑏_{1 𝑗} + 𝑎_{𝑖 2} 𝑏_{2 𝑗} + \dots + 𝑎_{𝑖 𝑚} 𝑏_{𝑚 𝑗} = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} .

The sizes behave like dominoes: an $ℓ \times 𝑚$ matrix times an $𝑚 \times 𝑛$ matrix is an $ℓ \times 𝑛$ matrix, and the two inner sizes must match. A column $𝐱 \in 𝐹^{𝑚}$ is an $𝑚 \times 1$ matrix, and the product of $𝐴$ with it in the sense of Definition 2.4.1 has the single column $𝐴 𝐱$ . So the matrix–vector product of Definition 2.3.8 is the special case $𝑛 = 1$ , and the notation $𝐴 𝐱$ is unambiguous.

Theorem 2.4.2 (The matrix of a composite).

(a)For $𝑆 \in L (𝑈, 𝑉)$ and $𝑇 \in L (𝑉, 𝑊)$ ,
${[𝑇 𝑆]}_{𝒞︀ 𝒜︀} = {[𝑇]}_{𝒞︀ ℬ︀} {[𝑆]}_{ℬ︀ 𝒜︀} .$
(b)For $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ , $𝑇_{𝐴 𝐵} = 𝑇_{𝐴} 𝑇_{𝐵}$ . That is, $(𝐴 𝐵) 𝐱 = 𝐴 (𝐵 𝐱)$ for every $𝐱 \in 𝐹^{𝑛}$ .

Proof.routine

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.3.9 (The matrix of a map computes the map), Definition 2.4.1 (Matrix product), Proposition 2.3.16 (The matrix of $𝑇_{𝐴}$ ), Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ ), Proposition 2.1.17 (Compositions of linear maps are linear)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Two matrices of the same size are equal when their columns are. What is the

𝑗

-th column of each side of (a)?

Hint 2. The

𝑗

-th column of

{[𝑇 𝑆]}_{𝒞︀ 𝒜︀}

{[𝑇 (𝑆 (𝐮_{𝑗}))]}_{𝒞︀}

. Apply Theorem 2.3.9 to

𝑇

at the vector

𝑆 (𝐮_{𝑗})

Hint 3. For (b), apply (a) with the standard bases, and then use that a linear map

𝐹^{𝑛} \to 𝐹^{ℓ}

is determined by its standard matrix.

Sketch. (a) The

𝑗

-th column of

{[𝑇 𝑆]}_{𝒞︀ 𝒜︀}

{[𝑇 (𝑆 (𝐮_{𝑗}))]}_{𝒞︀} =

{[𝑇]}_{𝒞︀ ℬ︀} {[𝑆 (𝐮_{𝑗})]}_{ℬ︀}

, which is

{[𝑇]}_{𝒞︀ ℬ︀}

times the

𝑗

-th column of

{[𝑆]}_{ℬ︀ 𝒜︀}

, the

𝑗

-th column of the product. (b) By (a) with standard bases,

{[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀} =

𝐴 𝐵

, so

𝑇_{𝐴} 𝑇_{𝐵} = 𝑇_{𝐴 𝐵}

by Proposition 2.3.17.

(a) Both sides are $ℓ \times 𝑛$ matrices. By Definition 2.3.1, the $𝑗$ -th column of ${[𝑇 𝑆]}_{𝒞︀ 𝒜︀}$ is ${[(𝑇 𝑆) (𝐮_{𝑗})]}_{𝒞︀}$ . By the definition of composition and Theorem 2.3.9,

\begin{aligned} {[(𝑇 𝑆) (𝐮_{𝑗})]}_{𝒞︀} & = {[𝑇 (𝑆 (𝐮_{𝑗}))]}_{𝒞︀} \\ = {[𝑇]}_{𝒞︀ ℬ︀} {[𝑆 (𝐮_{𝑗})]}_{ℬ︀} . \end{aligned}

The vector ${[𝑆 (𝐮_{𝑗})]}_{ℬ︀}$ is the $𝑗$ -th column of ${[𝑆]}_{ℬ︀ 𝒜︀}$ (Definition 2.3.1), so by Definition 2.4.1 this is the $𝑗$ -th column of ${[𝑇]}_{𝒞︀ ℬ︀} {[𝑆]}_{ℬ︀ 𝒜︀}$ . The two matrices have the same columns, so they are equal.

(b) The map $𝑇_{𝐴} 𝑇_{𝐵} : 𝐹^{𝑛} \to 𝐹^{ℓ}$ is linear (Proposition 2.1.17). By (a) with the standard bases of $𝐹^{𝑛}$ , $𝐹^{𝑚}$ , and $𝐹^{ℓ}$ , and by Proposition 2.3.16,

{[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀} = {[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} {[𝑇_{𝐵}]}_{ℰ︀ ℰ︀} = 𝐴 𝐵 .

By Proposition 2.3.17, every linear map $𝐹^{𝑛} \to 𝐹^{ℓ}$ is multiplication by its standard matrix, so $𝑇_{𝐴} 𝑇_{𝐵} = 𝑇_{𝐴 𝐵}$ . Evaluating at $𝐱$ gives $𝐴 (𝐵 𝐱) = (𝐴 𝐵) 𝐱$ . □

The subscripts in (a) behave like the sizes: in ${[𝑇]}_{𝒞︀ ℬ︀} {[𝑆]}_{ℬ︀ 𝒜︀}$ the two inner bases agree and drop out, leaving ${[𝑇 𝑆]}_{𝒞︀ 𝒜︀}$ . Also notice the order. $𝑇 𝑆$ means “first $𝑆$ , then $𝑇$ ”, and the matrix of the map applied first stands on the right, as $𝑆$ does in $𝑇 (𝑆 (𝐮))$ . This is the price of writing functions to the left of their arguments, and it is why products of matrices are read from right to left.

As with the matrix–vector product (Proposition 2.3.10), the definition is not a convention. Even the special case of standard bases leaves no other choice.

Proposition 2.4.3 (The product is forced). Suppose that for all $ℓ, 𝑚, 𝑛 \geq 1$ we are given a rule that assigns to each $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ a matrix $𝐴 ⋆ 𝐵 \in 𝐹^{ℓ \times 𝑛}$ , such that for all $𝑆 \in L (𝐹^{𝑛}, 𝐹^{𝑚})$ and $𝑇 \in L (𝐹^{𝑚}, 𝐹^{ℓ})$ ,

{[𝑇 𝑆]}_{ℰ︀ ℰ︀} = {[𝑇]}_{ℰ︀ ℰ︀} ⋆ {[𝑆]}_{ℰ︀ ℰ︀} .

Then $𝐴 ⋆ 𝐵 = 𝐴 𝐵$ for all $𝐴$ and $𝐵$ .

Proof.routine

Uses. Proposition 2.3.16 (The matrix of $𝑇_{𝐴}$ ), Theorem 2.4.2 (The matrix of a composite)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Given

𝐴

and

𝐵

, find linear maps whose standard matrices are

𝐴

and

𝐵

Hint 2. Take

𝑇 = 𝑇_{𝐴}

and

𝑆 = 𝑇_{𝐵}

, and compute

{[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀}

in two ways.

Sketch. With

𝑇 = 𝑇_{𝐴}

and

𝑆 = 𝑇_{𝐵}

, the hypothesis gives

𝐴 ⋆ 𝐵 =

{[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀}

, and Theorem 2.4.2 gives

{[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀} =

𝐴 𝐵

Let $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ . By Proposition 2.3.16, ${[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} = 𝐴$ and ${[𝑇_{𝐵}]}_{ℰ︀ ℰ︀} = 𝐵$ . Applying the hypothesis to $𝑇 = 𝑇_{𝐴}$ and $𝑆 = 𝑇_{𝐵}$ , and then Theorem 2.4.2,

\begin{aligned} 𝐴 ⋆ 𝐵 & = {[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} ⋆ {[𝑇_{𝐵}]}_{ℰ︀ ℰ︀} = {[𝑇_{𝐴} 𝑇_{𝐵}]}_{ℰ︀ ℰ︀} \\ = {[𝑇_{𝐴}]}_{ℰ︀ ℰ︀} {[𝑇_{𝐵}]}_{ℰ︀ ℰ︀} = 𝐴 𝐵 . \end{aligned}

□

Figure 2.4.1 shows Theorem 2.4.2(b) in the plane. The grid in the last panel of each row is the image of the square grid under the composite, and the two colored arrows are the columns of the product.

Figure 2.4.1. Composition in the plane, with

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

(a shear) and

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

(rotation by a right angle). Blue and ochre arrows are the images of

𝐞_{1}

and

𝐞_{2}

. Top row: first

𝐵

, then

𝐴

. The result is

𝑇_{𝐴} 𝑇_{𝐵} = 𝑇_{𝐴 𝐵}

, and its arrows are the columns

(1, 1)

and

(- 1, 0)

𝐴 𝐵 = (\begin{matrix} 1 & - 1 \\ 1 & 0 \end{matrix})

. Bottom row: the same two maps in the other order, giving

𝐵 𝐴 = (\begin{matrix} 0 & - 1 \\ 1 & 1 \end{matrix})

. The final grids differ, so

𝐴 𝐵 \neq 𝐵 𝐴

Example 2.4.4 (A product by columns). Let $𝐴 = (\begin{matrix} 1 & - 1 & 2 \\ 0 & 3 & 1 \end{matrix}) \in ℝ^{2 \times 3}$ and $𝐵 = (\begin{matrix} 2 & 1 \\ 1 & 0 \\ - 1 & 4 \end{matrix}) \in ℝ^{3 \times 2}$ . The columns of $𝐴 𝐵$ are $𝐴 (2, 1, - 1)$ and $𝐴 (1, 0, 4)$ , which by Definition 2.3.8 are

\begin{aligned} 2 (\begin{matrix} 1 \\ 0 \end{matrix}) + (\begin{matrix} - 1 \\ 3 \end{matrix}) - (\begin{matrix} 2 \\ 1 \end{matrix}) & = (\begin{matrix} - 1 \\ 2 \end{matrix}), \\ (\begin{matrix} 1 \\ 0 \end{matrix}) + 4 (\begin{matrix} 2 \\ 1 \end{matrix}) & = (\begin{matrix} 9 \\ 4 \end{matrix}), \end{aligned}

so $𝐴 𝐵 = (\begin{matrix} - 1 & 9 \\ 2 & 4 \end{matrix})$ . The product $𝐵 𝐴$ is also defined, but it is a $3 \times 3$ matrix:

𝐵 𝐴 = (\begin{matrix} 2 & 1 & 5 \\ 1 & - 1 & 2 \\ - 1 & 13 & 2 \end{matrix}),

whose columns are $𝐵 (\begin{matrix} 1 \\ 0 \end{matrix})$ , $𝐵 (\begin{matrix} - 1 \\ 3 \end{matrix})$ , and $𝐵 (\begin{matrix} 2 \\ 1 \end{matrix})$ . Even the sizes of $𝐴 𝐵$ and $𝐵 𝐴$ differ.

Example 2.4.5 (Composites through their matrices).

(a)Let $𝐷 \in L ({𝐹 [𝑥]}_{\leq 2})$ be differentiation and $ℬ︀ = 1, 𝑥, 𝑥^{2}$ , so that $𝑁 =$ ${[𝐷]}_{ℬ︀ ℬ︀} =$ $(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{matrix})$ (Example 2.3.4). By Theorem 2.4.2, ${[𝐷^{2}]}_{ℬ︀ ℬ︀} = 𝑁 𝑁$ and ${[𝐷^{3}]}_{ℬ︀ ℬ︀} = 𝑁 𝑁 𝑁$ , and indeed
$𝑁 𝑁 = (\begin{matrix} 0 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}), 𝑁 𝑁 𝑁 = (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) .$
The first says $𝐷^{2} (𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}) =$ $2 𝑐$ . The second is the matrix form of $𝐷^{3} = 0$ , which we could only observe one vector at a time in Intuition (One basis or two).
(b)Rotating by $𝛽$ and then by $𝛼$ is rotating by $𝛼 + 𝛽$ , so $𝑅_{𝛼} 𝑅_{𝛽} = 𝑅_{𝛼 + 𝛽}$ (Exercise 2.1.43). By Theorem 2.4.2 and Example 2.3.3,
$\begin{matrix} {[𝑅_{𝛼 + 𝛽}]}_{ℰ︀ ℰ︀} \\ = (\begin{matrix} cos 𝛼 & - sin 𝛼 \\ sin 𝛼 & cos 𝛼 \end{matrix}) (\begin{matrix} cos 𝛽 & - sin 𝛽 \\ sin 𝛽 & cos 𝛽 \end{matrix}) . \end{matrix}$
The first column of the left side is $(cos (𝛼 + 𝛽), sin (𝛼 + 𝛽))$ , and by the column view of the product, the first column of the right side is
$\begin{matrix} cos 𝛽 (\begin{matrix} cos 𝛼 \\ sin 𝛼 \end{matrix}) + sin 𝛽 (\begin{matrix} - sin 𝛼 \\ cos 𝛼 \end{matrix}) \\ = (\begin{matrix} cos 𝛼 cos 𝛽 - sin 𝛼 sin 𝛽 \\ sin 𝛼 cos 𝛽 + cos 𝛼 sin 𝛽 \end{matrix}) . \end{matrix}$
These are the angle addition formulas for $cos (𝛼 + 𝛽)$ and $sin (𝛼 + 𝛽)$ . In Example 2.1.11 we used those formulas to show that rotations are linear, so here they are recovered rather than proved. But if one accepts from geometry that rotations are linear, then their matrices come from Corollary 2.2.17 without any trigonometric identity, as noted in Section 2.2.5, and this computation is a proof of the angle addition formulas.
(c)Let $ℬ︀ = (1, 1), (1, - 1)$ , a basis of $𝐹^{2}$ when $1 + 1 \neq 0$ . In Example 2.3.24 we found ${[id]}_{ℰ︀ ℬ︀} = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ and ${[id]}_{ℬ︀ ℰ︀} =$ $\frac{1}{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ . Since $id id = id$ , Theorem 2.4.2 gives
${[id]}_{ℰ︀ ℬ︀} {[id]}_{ℬ︀ ℰ︀} = {[id]}_{ℰ︀ ℰ︀} = 𝐼_{2},$
and indeed $(\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) =$ $(\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix})$ , which becomes $𝐼_{2}$ after multiplying by $\frac{1}{2}$ . Converting standard coordinates into $ℬ︀$ -coordinates and back changes nothing. Matrices whose products are $𝐼$ in this way are the invertible matrices of Section 2.5, and those of the form ${[id]}_{𝒞︀ ℬ︀}$ are studied in Section 4.5.

Exercise 2.4.6.routine

(a)Over $𝔽_{5}$ , let $𝐴 = (\begin{matrix} 1 & 2 & 0 \\ 3 & 1 & 4 \end{matrix})$ and $𝐵 = (\begin{matrix} 2 & 1 \\ 0 & 3 \\ 1 & 1 \end{matrix})$ . Compute $𝐴 𝐵$ and $𝐵 𝐴$ . Which of $𝐴^{2} = 𝐴 𝐴$ and $𝐵^{2} = 𝐵 𝐵$ are defined?
(b)Over $ℂ$ , compute $(\begin{matrix} 1 & 𝑖 \\ 0 & 2 \end{matrix}) (\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix})$ and $(\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix}) (\begin{matrix} 1 & 𝑖 \\ 0 & 2 \end{matrix})$ .

Solution.

Uses. Definition 2.4.1 (Matrix product), Definition 2.3.8 (Matrix–vector product)

Hint 1. Compute column by column: column

𝑗

𝐴 𝐵

𝐴

times column

𝑗

𝐵

. Or use the entry formula: row

𝑖

𝐴

against column

𝑗

𝐵

Hint 2. Work with integers and reduce modulo

5

at the end. In (b), use

𝑖^{2} = - 1

Sketch. (a)

𝐴 𝐵 =

(\begin{matrix} 2 & 7 \\ 10 & 10 \end{matrix}) =

(\begin{matrix} 2 & 2 \\ 0 & 0 \end{matrix})

and

𝐵 𝐴 =

(\begin{matrix} 5 & 5 & 4 \\ 9 & 3 & 12 \\ 4 & 3 & 4 \end{matrix}) =

(\begin{matrix} 0 & 0 & 4 \\ 4 & 3 & 2 \\ 4 & 3 & 4 \end{matrix})

𝔽_{5}

𝐴^{2}

needs

3 = 2

and

𝐵^{2}

needs

2 = 3

, so neither is defined. (b)

(\begin{matrix} 2 𝑖 & 2 \\ 2 & - 2 𝑖 \end{matrix})

and

(\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix})

(a) By columns, $𝐴 (2, 0, 1) =$ $2 (1, 3) +$ $(0, 4) =$ $(2, 10)$ and $𝐴 (1, 3, 1) =$ $(1, 3) +$ $3 (2, 1) +$ $(0, 4) =$ $(7, 10)$ . Reducing modulo $5$ ,

𝐴 𝐵 = (\begin{matrix} 2 & 2 \\ 0 & 0 \end{matrix}) .

The columns of $𝐵 𝐴$ are $𝐵 (1, 3) =$ $(2 + 3, 0 + 9, 1 + 3)$ , $𝐵 (2, 1) =$ $(4 + 1, 0 + 3, 2 + 1)$ , and $𝐵 (0, 4) =$ $(0 + 4, 0 + 12, 0 + 4)$ , so

𝐵 𝐴 = (\begin{matrix} 5 & 5 & 4 \\ 9 & 3 & 12 \\ 4 & 3 & 4 \end{matrix}) = (\begin{matrix} 0 & 0 & 4 \\ 4 & 3 & 2 \\ 4 & 3 & 4 \end{matrix}) in 𝔽_{5} .

A product $𝑋 𝑌$ needs as many columns in $𝑋$ as rows in $𝑌$ . $𝐴$ is $2 \times 3$ , so $𝐴 𝐴$ is not defined, and $𝐵$ is $3 \times 2$ , so $𝐵 𝐵$ is not defined either.

(b) By the entry formula, the first product has entries $1 \cdot 𝑖 + 𝑖 \cdot 1 = 2 𝑖$ , $1 \cdot 1 + 𝑖 (- 𝑖) = 2$ , $0 \cdot 𝑖 + 2 \cdot 1 = 2$ , and $0 \cdot 1 + 2 (- 𝑖) = - 2 𝑖$ , and the second has entries $𝑖$ , $𝑖^{2} + 2 = 1$ , $1$ , and $𝑖 - 2 𝑖 = - 𝑖$ :

\begin{matrix} (\begin{matrix} 1 & 𝑖 \\ 0 & 2 \end{matrix}) (\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix}) = (\begin{matrix} 2 𝑖 & 2 \\ 2 & - 2 𝑖 \end{matrix}), \\ (\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix}) (\begin{matrix} 1 & 𝑖 \\ 0 & 2 \end{matrix}) = (\begin{matrix} 𝑖 & 1 \\ 1 & - 𝑖 \end{matrix}) . \end{matrix}

The two products differ.

2.4.2Four views of the product

The definition describes $𝐴 𝐵$ one column at a time, but a product can be read in several other ways, and choosing the right one often makes a problem easy. We first fix some notation.

Notation 2.4.7 (Entries, rows, and columns). For a matrix $𝑀$ given by an expression, such as $𝐴 𝐵$ , we write ${(𝑀)}_{𝑖 𝑗}$ or $𝑀_{𝑖 𝑗}$ for its entry in row $𝑖$ and column $𝑗$ , and

𝑀_{𝑖, \cdot} = row 𝑖 of 𝑀, 𝑀_{\cdot, 𝑗} = column 𝑗 of 𝑀 .

A row of an $ℓ \times 𝑚$ matrix is a $1 \times 𝑚$ matrix, and a column is an $ℓ \times 1$ matrix, that is, an element of $𝐹^{ℓ}$ . We identify a $1 \times 1$ matrix $(𝑐)$ with the scalar $𝑐$ . The Kronecker delta is

𝛿_{𝑖 𝑗} = {\begin{cases} 1 & if 𝑖 = 𝑗 \\ 0 & if 𝑖 \neq 𝑗 \end{cases},

so that $𝐼_{𝑛} = (𝛿_{𝑖 𝑗})$ and $𝐞_{𝑗} =$ $(𝛿_{1 𝑗}, \dots, 𝛿_{𝑛 𝑗})$ .

Proposition 2.4.8 (Four views of the product). Let

𝐴 \in 𝐹^{ℓ \times 𝑚}

and

𝐵 \in 𝐹^{𝑚 \times 𝑛}

, and let

1 \leq 𝑖 \leq ℓ

and

1 \leq 𝑗 \leq 𝑛

(a)Entries. The $(𝑖, 𝑗)$ entry of $𝐴 𝐵$ is row $𝑖$ of $𝐴$ times column $𝑗$ of $𝐵$ :
${(𝐴 𝐵)}_{𝑖 𝑗} = 𝐴_{𝑖, \cdot} 𝐵_{\cdot, 𝑗} = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} .$
(b)Columns. Column $𝑗$ of $𝐴 𝐵$ is a combination of the columns of $𝐴$ , with coefficients from column $𝑗$ of $𝐵$ :
$\begin{aligned} {(𝐴 𝐵)}_{\cdot, 𝑗} & = 𝐴 𝐵_{\cdot, 𝑗} \\ = 𝑏_{1 𝑗} 𝐴_{\cdot, 1} + \dots + 𝑏_{𝑚 𝑗} 𝐴_{\cdot, 𝑚} . \end{aligned}$
(c)Rows. Row $𝑖$ of $𝐴 𝐵$ is a combination of the rows of $𝐵$ , with coefficients from row $𝑖$ of $𝐴$ :
$\begin{aligned} {(𝐴 𝐵)}_{𝑖, \cdot} & = 𝐴_{𝑖, \cdot} 𝐵 \\ = 𝑎_{𝑖 1} 𝐵_{1, \cdot} + \dots + 𝑎_{𝑖 𝑚} 𝐵_{𝑚, \cdot} . \end{aligned}$
(d)Columns times rows. $𝐴 𝐵$ is a sum of $𝑚$ products of a column with a row:
$𝐴 𝐵 = 𝐴_{\cdot, 1} 𝐵_{1, \cdot} + \dots + 𝐴_{\cdot, 𝑚} 𝐵_{𝑚, \cdot} .$

Proof.routine

Uses. Definition 2.4.1 (Matrix product), Definition 2.3.8 (Matrix–vector product), Definition 1.2.7 (Matrices)

Hint 1. (a) and (b) are restatements of Definition 2.4.1. For (c) and (d), compare entries using (a).

Hint 2. In (d),

𝐴_{\cdot, 𝑘} 𝐵_{𝑘, \cdot}

is an

ℓ \times 1

matrix times a

1 \times 𝑛

matrix. Its inner size is

1

, so the sum in (a) has a single term. What is its

(𝑖, 𝑗)

entry?

Sketch. (a) is the entry formula of Definition 2.4.1, read for a

1 \times 𝑚

times

𝑚 \times 1

product. (b) is the definition together with Definition 2.3.8. In (c) and (d), the

(𝑖, 𝑗)

entry of each side is

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

: the matrix

𝐴_{\cdot, 𝑘} 𝐵_{𝑘, \cdot}

has

(𝑖, 𝑗)

entry

𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

, and the operations on matrices are entrywise.

(a) The formula ${(𝐴 𝐵)}_{𝑖 𝑗} =$ $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ is part of Definition 2.4.1. Applied to the $1 \times 𝑚$ matrix $𝐴_{𝑖, \cdot}$ and the $𝑚 \times 1$ matrix $𝐵_{\cdot, 𝑗}$ , the same formula says that $𝐴_{𝑖, \cdot} 𝐵_{\cdot, 𝑗}$ is the $1 \times 1$ matrix with entry $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ .

(b) By Definition 2.4.1, column $𝑗$ of $𝐴 𝐵$ is $𝐴 𝐛_{𝑗}$ with $𝐛_{𝑗} =$ $𝐵_{\cdot, 𝑗} =$ $(𝑏_{1 𝑗}, \dots, 𝑏_{𝑚 𝑗})$ , and by Definition 2.3.8, $𝐴 𝐛_{𝑗} =$ $𝑏_{1 𝑗} 𝐴_{\cdot, 1} +$ $\dots +$ $𝑏_{𝑚 𝑗} 𝐴_{\cdot, 𝑚}$ .

(c) By (a), applied to $𝐴_{𝑖, \cdot} \in 𝐹^{1 \times 𝑚}$ and $𝐵$ , the $1 \times 𝑛$ matrix $𝐴_{𝑖, \cdot} 𝐵$ has $𝑗$ -th entry $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ . Matrices are added and scaled entrywise (Definition 1.2.7), so the $𝑗$ -th entry of $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝐵_{𝑘, \cdot}$ is also $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ . By (a), both equal the $𝑗$ -th entry of ${(𝐴 𝐵)}_{𝑖, \cdot}$ .

(d) By (a), applied with inner size $1$ , the $ℓ \times 𝑛$ matrix $𝐴_{\cdot, 𝑘} 𝐵_{𝑘, \cdot}$ has $(𝑖, 𝑗)$ entry $𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}$ . Adding these matrices entrywise over $𝑘 = 1, \dots, 𝑚$ gives the matrix with $(𝑖, 𝑗)$ entry $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} =$ ${(𝐴 𝐵)}_{𝑖 𝑗}$ . □

Each view is the right one for some job.

The entry view (a) is the quickest way to compute a product by hand, and the one to use in proofs about individual entries, such as the shape of a product of triangular matrices (Proposition 2.4.36).
The column view (b) answers questions about columns. Since every column of $𝐴 𝐵$ is a linear combination of the columns of $𝐴$ , the span of the columns of $𝐴 𝐵$ is contained in the span of the columns of $𝐴$ (Proposition 1.4.14): multiplying $𝐴$ on the right cannot produce new directions. This is the first step towards $rank (𝐴 𝐵) \leq rank 𝐴$ (Section 4.3). It also says that multiplying on the right recombines columns, which is how column operations become matrix products (Section 3.2).
The row view (c) is the mirror image: multiplying $𝐵$ on the left recombines its rows. This is why row operations, and Gauss–Jordan elimination as a whole, are left multiplications (Section 3.2, Section 3.3).
The column–row view (d) writes $𝐴 𝐵$ as a sum of $𝑚$ simple pieces, each built from one column and one row. It is the view to use when $𝐴$ has few columns, for block multiplication (Theorem 2.4.34), and for decompositions of a matrix into simple pieces (Section 4.3, Section 9.1).

Example 2.4.9 (One product, four ways). Let $𝐴 = (\begin{matrix} 1 & 2 \\ - 1 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 3 & 1 & 0 \\ 1 & - 2 & 4 \end{matrix})$ over $ℝ$ .

Entries. ${(𝐴 𝐵)}_{11} =$ $1 \cdot$ $3 +$ $2 \cdot$ $1 =$ $5$ , ${(𝐴 𝐵)}_{12} = 1 - 4 = - 3$ , and so on, giving $𝐴 𝐵 = (\begin{matrix} 5 & - 3 & 8 \\ - 3 & - 1 & 0 \end{matrix})$ .

Columns. ${(𝐴 𝐵)}_{\cdot, 1} =$ $3 (\begin{matrix} 1 \\ - 1 \end{matrix}) +$ $1 (\begin{matrix} 2 \\ 0 \end{matrix}) =$ $(\begin{matrix} 5 \\ - 3 \end{matrix})$ , and similarly for the other two columns.

Rows. Row $1$ of $𝐴$ is $(\begin{matrix} 1 & 2 \end{matrix})$ , so

\begin{aligned} {(𝐴 𝐵)}_{1, \cdot} & = 1 (\begin{matrix} 3 & 1 & 0 \end{matrix}) + 2 (\begin{matrix} 1 & - 2 & 4 \end{matrix}) \\ = (\begin{matrix} 5 & - 3 & 8 \end{matrix}) . \end{aligned}

Row $2$ of $𝐴$ is $(\begin{matrix} - 1 & 0 \end{matrix})$ , so row $2$ of $𝐴 𝐵$ is $- 1$ times row $1$ of $𝐵$ , that is, $(\begin{matrix} - 3 & - 1 & 0 \end{matrix})$ . The row view gave this row with no computation at all.

Columns times rows.

\begin{matrix} 𝐴 𝐵 = (\begin{matrix} 1 \\ - 1 \end{matrix}) (\begin{matrix} 3 & 1 & 0 \end{matrix}) \\ + (\begin{matrix} 2 \\ 0 \end{matrix}) (\begin{matrix} 1 & - 2 & 4 \end{matrix}) . \end{matrix}

The two terms are $(\begin{matrix} 3 & 1 & 0 \\ - 3 & - 1 & 0 \end{matrix})$ and $(\begin{matrix} 2 & - 4 & 8 \\ 0 & 0 & 0 \end{matrix})$ , and their sum is $𝐴 𝐵$ .

Example 2.4.10 (Diagonal matrices). A square matrix $𝐷$ is diagonal if $𝑑_{𝑖 𝑗} = 0$ whenever $𝑖 \neq 𝑗$ . We write $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ for the diagonal matrix with diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ . Row $𝑖$ of $𝐷$ is $𝑑_{𝑖} 𝐞_{𝑖}$ written as a row, so by the row view, row $𝑖$ of $𝐷 𝐴$ is $𝑑_{𝑖} 𝐴_{𝑖, \cdot}$ : multiplying by $𝐷$ on the left scales row $𝑖$ by $𝑑_{𝑖}$ . Column $𝑗$ of $𝐷$ is $𝑑_{𝑗} 𝐞_{𝑗}$ , so by the column view, column $𝑗$ of $𝐴 𝐷$ is $𝑑_{𝑗} 𝐴_{\cdot, 𝑗}$ : multiplying on the right scales columns. In particular

\begin{matrix} diag (𝑐_{1}, \dots, 𝑐_{𝑛}) diag (𝑑_{1}, \dots, 𝑑_{𝑛}) \\ = diag (𝑐_{1} 𝑑_{1}, \dots, 𝑐_{𝑛} 𝑑_{𝑛}), \end{matrix}

so diagonal matrices multiply entry by entry and commute with each other.

Exercise 2.4.11.routine Let $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)Show that if column $𝑗$ of $𝐵$ is zero, then so is column $𝑗$ of $𝐴 𝐵$ , and that if row $𝑖$ of $𝐴$ is zero, then so is row $𝑖$ of $𝐴 𝐵$ .
(b)Show that if $𝐵_{\cdot, 3} =$ $𝐵_{\cdot, 1} +$ $2 𝐵_{\cdot, 2}$ , then ${(𝐴 𝐵)}_{\cdot, 3} =$ ${(𝐴 𝐵)}_{\cdot, 1} +$ $2 {(𝐴 𝐵)}_{\cdot, 2}$ .
(c)Give an example in which $𝐴 𝐵$ has a zero column but $𝐵$ has none.

Solution.

Uses. Proposition 2.4.8 (Four views of the product), Proposition 2.3.13 (Linearity of the product)

Hint 1. Use the column view for statements about columns of

𝐴 𝐵

, and the row view for rows.

Hint 2. Column

𝑗

𝐴 𝐵

𝐴 𝐵_{\cdot, 𝑗}

, and

𝐱 \mapsto 𝐴 𝐱

is linear. For (c), you need a nonzero column

𝐛

with

𝐴 𝐛 = 𝟎

Sketch. (a)

{(𝐴 𝐵)}_{\cdot, 𝑗} =

𝐴 𝟎 =

𝟎

, and

{(𝐴 𝐵)}_{𝑖, \cdot} =

𝐴_{𝑖, \cdot} 𝐵

is a combination of rows of

𝐵

with all coefficients

0

. (b) Apply the linear map

𝐱 \mapsto 𝐴 𝐱

to the relation. (c)

𝐴 = (\begin{matrix} 1 & 1 \end{matrix})

and

𝐵 = (\begin{matrix} 1 \\ - 1 \end{matrix})

give

𝐴 𝐵 = (0)

(a) By the column view (Proposition 2.4.8(b)), ${(𝐴 𝐵)}_{\cdot, 𝑗} =$ $𝐴 𝐵_{\cdot, 𝑗} =$ $𝐴 𝟎 =$ $𝟎$ . By the row view (Proposition 2.4.8(c)), ${(𝐴 𝐵)}_{𝑖, \cdot} =$ $𝑎_{𝑖 1} 𝐵_{1, \cdot} +$ $\dots +$ $𝑎_{𝑖 𝑚} 𝐵_{𝑚, \cdot}$ , and every coefficient $𝑎_{𝑖 𝑘}$ is $0$ , so this row is zero.

(b) By the column view and the linearity of $𝐱 \mapsto 𝐴 𝐱$ (Proposition 2.3.13),

\begin{aligned} {(𝐴 𝐵)}_{\cdot, 3} & = 𝐴 (𝐵_{\cdot, 1} + 2 𝐵_{\cdot, 2}) = 𝐴 𝐵_{\cdot, 1} + 2 𝐴 𝐵_{\cdot, 2} \\ = {(𝐴 𝐵)}_{\cdot, 1} + 2 {(𝐴 𝐵)}_{\cdot, 2} . \end{aligned}

In words: every linear relation among the columns of $𝐵$ also holds among the columns of $𝐴 𝐵$ .

(c) We need a nonzero column $𝐛$ with $𝐴 𝐛 = 𝟎$ . Take $𝐴 = (\begin{matrix} 1 & 1 \end{matrix}) \in ℝ^{1 \times 2}$ and $𝐵 = (\begin{matrix} 1 \\ - 1 \end{matrix}) \in ℝ^{2 \times 1}$ . Then $𝐴 𝐵 = (1 - 1) = (0)$ , a zero column, while $𝐵$ has none. A square example: $(\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & 2 \\ - 1 & - 2 \end{matrix}) =$ $(\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix})$ .

2.4.3Sums and scalar multiples

Matrices of the same size can also be added and scaled entrywise (Definition 1.2.7), and linear maps can be added and scaled pointwise (Proposition 2.1.23). These operations correspond to each other as well.

Proposition 2.4.12 (Matrices of sums and scalar multiples). Let $𝑆, 𝑇 \in L (𝑉, 𝑊)$ and $𝑎 \in 𝐹$ . Then

\begin{matrix} {[𝑆 + 𝑇]}_{𝒞︀ ℬ︀} = {[𝑆]}_{𝒞︀ ℬ︀} + {[𝑇]}_{𝒞︀ ℬ︀}, \\ {[𝑎 𝑇]}_{𝒞︀ ℬ︀} = 𝑎 {[𝑇]}_{𝒞︀ ℬ︀} . \end{matrix}

So $𝑇 \mapsto {[𝑇]}_{𝒞︀ ℬ︀}$ is a linear bijection from $L (𝑉, 𝑊)$ onto $𝐹^{ℓ \times 𝑚}$ .

Proof.routine

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 2.1.21 (Pointwise operations), Proposition 1.6.19 (Coordinates respect linear combinations), Definition 1.2.7 (Matrices), Theorem 2.3.20 (Linear maps correspond to matrices)

Hint 1. Compare the

𝑗

-th columns of the two sides.

Hint 2.

(𝑆 + 𝑇) (𝐯_{𝑗}) =

𝑆 (𝐯_{𝑗}) +

𝑇 (𝐯_{𝑗})

by the definition of

𝑆 + 𝑇

. Taking coordinates is linear.

Sketch. The

𝑗

-th column of

{[𝑆 + 𝑇]}_{𝒞︀ ℬ︀}

{[𝑆 (𝐯_{𝑗}) + 𝑇 (𝐯_{𝑗})]}_{𝒞︀} =

{[𝑆 (𝐯_{𝑗})]}_{𝒞︀} +

{[𝑇 (𝐯_{𝑗})]}_{𝒞︀}

, the sum of the

𝑗

-th columns of

[𝑆]

and

[𝑇]

. Scalars are the same. Bijectivity is Theorem 2.3.20.

By Definition 2.3.1, Definition 2.1.21, and the linearity of ${[\cdot]}_{𝒞︀}$ (Proposition 1.6.19), the $𝑗$ -th column of ${[𝑆 + 𝑇]}_{𝒞︀ ℬ︀}$ is

\begin{aligned} {[(𝑆 + 𝑇) (𝐯_{𝑗})]}_{𝒞︀} & = {[𝑆 (𝐯_{𝑗}) + 𝑇 (𝐯_{𝑗})]}_{𝒞︀} \\ = {[𝑆 (𝐯_{𝑗})]}_{𝒞︀} + {[𝑇 (𝐯_{𝑗})]}_{𝒞︀} . \end{aligned}

Matrices are added entrywise (Definition 1.2.7), so the $𝑗$ -th column of ${[𝑆]}_{𝒞︀ ℬ︀} +$ ${[𝑇]}_{𝒞︀ ℬ︀}$ is the sum of their $𝑗$ -th columns, which is the same vector. Likewise the $𝑗$ -th column of ${[𝑎 𝑇]}_{𝒞︀ ℬ︀}$ is ${[𝑎 𝑇 (𝐯_{𝑗})]}_{𝒞︀} =$ $𝑎 {[𝑇 (𝐯_{𝑗})]}_{𝒞︀}$ , the $𝑗$ -th column of $𝑎 {[𝑇]}_{𝒞︀ ℬ︀}$ . So $𝑇 \mapsto {[𝑇]}_{𝒞︀ ℬ︀}$ is linear, and it is a bijection by Theorem 2.3.20. □

So the dictionary of Section 2.3.6 has three more entries: sums, scalar multiples, and composites of maps correspond to sums, scalar multiples, and products of matrices. In the language of Section 4.5, the proposition says that $L (𝑉, 𝑊)$ and $𝐹^{ℓ \times 𝑚}$ are isomorphic vector spaces, and dimension counting there gives $dim L (𝑉, 𝑊) = ℓ 𝑚$ .

Example 2.4.13 (The difference operator). Let $𝑇 \in L ({𝐹 [𝑥]}_{\leq 2})$ be the substitution $𝑇 (𝑝) = 𝑝 (𝑥 + 1)$ , and $ℬ︀ = 1, 𝑥, 𝑥^{2}$ . From $𝑇 (1) = 1$ , $𝑇 (𝑥) = 1 + 𝑥$ , and $𝑇 (𝑥^{2}) = 1 + 2 𝑥 + 𝑥^{2}$ ,

{[𝑇]}_{ℬ︀ ℬ︀} = (\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{matrix}) .

The difference operator of Example 2.3.28 is $Δ = 𝑇 - id$ , so by Proposition 2.4.12 and Example 2.3.6,

{[Δ]}_{ℬ︀ ℬ︀} = {[𝑇]}_{ℬ︀ ℬ︀} - 𝐼_{3} = (\begin{matrix} 0 & 1 & 1 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{matrix}),

which is the matrix computed there column by column.

2.4.4The algebraic laws

Proposition 2.4.14 (Algebra of matrices). Let

𝐴, 𝐴^{'} \in 𝐹^{ℓ \times 𝑚}

𝐵, 𝐵^{'} \in 𝐹^{𝑚 \times 𝑛}

𝐶 \in 𝐹^{𝑛 \times 𝑝}

, and

𝑎 \in 𝐹

(a)Associativity. $(𝐴 𝐵) 𝐶 = 𝐴 (𝐵 𝐶)$ .
(b)Identities. $𝐼_{ℓ} 𝐴 = 𝐴 = 𝐴 𝐼_{𝑚}$ .
(c)Distributivity. $𝐴 (𝐵 + 𝐵^{'}) =$ $𝐴 𝐵 +$ $𝐴 𝐵^{'}$ and $(𝐴 + 𝐴^{'}) 𝐵 =$ $𝐴 𝐵 +$ $𝐴^{'} 𝐵$ .
(d)Scalars. $(𝑎 𝐴) 𝐵 =$ $𝑎 (𝐴 𝐵) =$ $𝐴 (𝑎 𝐵)$ .

Intuition (The laws come from composition). Read a product of matrices as a sequence of maps, applied from right to left:

𝐹^{𝑝} \overset{𝑇_{𝐶}}{⟶} 𝐹^{𝑛} \overset{𝑇_{𝐵}}{⟶} 𝐹^{𝑚} \overset{𝑇_{𝐴}}{⟶} 𝐹^{ℓ} .

Both $(𝐴 𝐵) 𝐶$ and $𝐴 (𝐵 𝐶)$ are the matrix of “first $𝑇_{𝐶}$ , then $𝑇_{𝐵}$ , then $𝑇_{𝐴}$ ”. The parentheses only record which two of the three steps were combined first, and the composite of three functions does not depend on that: both are $𝐱 \mapsto$ $𝑇_{𝐴} (𝑇_{𝐵} (𝑇_{𝐶} (𝐱)))$ . So associativity of matrix multiplication should follow from associativity of composition (Proposition 2.1.24) with no computation, once we can translate in both directions. That translation is Technique 2.3.27, and the dictionary we need is now complete: $𝑇_{𝐴 𝐵} = 𝑇_{𝐴} 𝑇_{𝐵}$ (Theorem 2.4.2), $𝑇_{𝑎 𝐴 + 𝐴^{'}} =$ $𝑎 𝑇_{𝐴} +$ $𝑇_{𝐴^{'}}$ and $𝑇_{𝐼_{ℓ}} = id$ (Proposition 2.3.13), and $𝐴$ is determined by $𝑇_{𝐴}$ (Proposition 2.3.17).

Proof (via composition).routine

Uses. Theorem 2.4.2 (The matrix of a composite), Proposition 2.1.24 (Algebra of composition), Proposition 2.3.13 (Linearity of the product), Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ )

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Two matrices of the same size are equal when the maps

𝑇_{𝑋}

they define are equal (Proposition 2.3.17). So compute

𝑇_{(𝐴 𝐵) 𝐶}

and

𝑇_{𝐴 (𝐵 𝐶)}

Hint 2.

𝑇_{(𝐴 𝐵) 𝐶} =

𝑇_{𝐴 𝐵} 𝑇_{𝐶} =

(𝑇_{𝐴} 𝑇_{𝐵}) 𝑇_{𝐶}

. Now use associativity of composition and go back.

Hint 3. For (b), (c), and (d) you also need

𝑇_{𝐼_{ℓ}} = id

𝑇_{𝐵 + 𝐵^{'}} =

𝑇_{𝐵} +

𝑇_{𝐵^{'}}

, and

𝑇_{𝑎 𝐴} = 𝑎 𝑇_{𝐴}

, all from Proposition 2.3.13.

Sketch. Translate each side into a composite of maps

𝑇_{𝑋}

with Theorem 2.4.2 and Proposition 2.3.13, apply the matching identity of Proposition 2.1.24, and translate back. For instance

𝑇_{(𝐴 𝐵) 𝐶} =

(𝑇_{𝐴} 𝑇_{𝐵}) 𝑇_{𝐶} =

𝑇_{𝐴} (𝑇_{𝐵} 𝑇_{𝐶}) =

𝑇_{𝐴 (𝐵 𝐶)}

, so

(𝐴 𝐵) 𝐶 = 𝐴 (𝐵 𝐶)

by the uniqueness in Proposition 2.3.17.

By Proposition 2.3.17, two matrices $𝑋, 𝑌 \in 𝐹^{𝑟 \times 𝑠}$ with $𝑇_{𝑋} = 𝑇_{𝑌}$ are equal. So in each case it suffices to show that the two sides define the same linear map. We use Theorem 2.4.2(b), $𝑇_{𝑋 𝑌} = 𝑇_{𝑋} 𝑇_{𝑌}$ , and Proposition 2.3.13, which says that $𝑇_{𝑐 𝑋 + 𝑋^{'}} =$ $𝑐 𝑇_{𝑋} +$ $𝑇_{𝑋^{'}}$ and that $𝑇_{𝐼_{𝑟}} = {id}_{𝐹^{𝑟}}$ .

(a) By Theorem 2.4.2 and part (a) of Proposition 2.1.24,

\begin{aligned} 𝑇_{(𝐴 𝐵) 𝐶} & = 𝑇_{𝐴 𝐵} 𝑇_{𝐶} = (𝑇_{𝐴} 𝑇_{𝐵}) 𝑇_{𝐶} \\ = 𝑇_{𝐴} (𝑇_{𝐵} 𝑇_{𝐶}) = 𝑇_{𝐴} 𝑇_{𝐵 𝐶} = 𝑇_{𝐴 (𝐵 𝐶)} . \end{aligned}

(b) $𝑇_{𝐼_{ℓ} 𝐴} =$ $𝑇_{𝐼_{ℓ}} 𝑇_{𝐴} =$ $id 𝑇_{𝐴} =$ $𝑇_{𝐴}$ , and $𝑇_{𝐴 𝐼_{𝑚}} =$ $𝑇_{𝐴} id =$ $𝑇_{𝐴}$ , by part (b) of Proposition 2.1.24.

(c) By part (c) of Proposition 2.1.24,

\begin{aligned} 𝑇_{𝐴 (𝐵 + 𝐵^{'})} & = 𝑇_{𝐴} (𝑇_{𝐵} + 𝑇_{𝐵^{'}}) = 𝑇_{𝐴} 𝑇_{𝐵} + 𝑇_{𝐴} 𝑇_{𝐵^{'}} \\ = 𝑇_{𝐴 𝐵} + 𝑇_{𝐴 𝐵^{'}} = 𝑇_{𝐴 𝐵 + 𝐴 𝐵^{'}}, \end{aligned}

and in the same way $𝑇_{(𝐴 + 𝐴^{'}) 𝐵} =$ $(𝑇_{𝐴} + 𝑇_{𝐴^{'}}) 𝑇_{𝐵}$ equals $𝑇_{𝐴 𝐵 + 𝐴^{'} 𝐵}$ .

(d) By part (d) of Proposition 2.1.24,

\begin{aligned} 𝑇_{(𝑎 𝐴) 𝐵} & = (𝑎 𝑇_{𝐴}) 𝑇_{𝐵} = 𝑎 (𝑇_{𝐴} 𝑇_{𝐵}) \\ = 𝑇_{𝐴} (𝑎 𝑇_{𝐵}) = 𝑇_{𝐴 (𝑎 𝐵)}, \end{aligned}

and the middle expression is $𝑎 𝑇_{𝐴 𝐵} =$ $𝑇_{𝑎 (𝐴 𝐵)}$ . □

The first proof never looks at an entry. The second proof works with entries only, and it is the prototype of a move we will use constantly.

Technique 2.4.15 (Compute entry by entry). To prove an identity between matrices, show that the $(𝑖, 𝑗)$ entries of the two sides agree for all $𝑖$ and $𝑗$ . Write each entry of a product with Proposition 2.4.8(a), using a new summation index for every product, then rearrange: pull constant factors out of sums, exchange the order of two finite sums, $\sum_{𝑘} \sum_{𝑙} = \sum_{𝑙} \sum_{𝑘}$ , and collapse sums containing a Kronecker delta, $\sum_{𝑘} 𝛿_{𝑖 𝑘} 𝑥_{𝑘} =$ $𝑥_{𝑖}$ .

Reach for it when the statement is about the entries themselves (transposes, traces, triangular or block shapes), or when there is no linear map in sight, for example for matrices whose entries are integers, polynomials, or other matrices. Two things go wrong in practice. Reusing a summation index in a nested sum silently identifies two different indices. And moving a factor past another needs commutativity of the entries, which holds for scalars but not for blocks (Section 2.4.8). The canonical example is the second proof of associativity below.

Used in 18 places and 2 practice exercises

Proposition 2.4.14, Proposition 2.4.23, Proposition 2.4.28, Theorem 2.4.34, Proposition 2.4.36, Proposition 2.4.39, Exercise 2.6.46, Exercise 2.8.6, Exercise 2.8.11, Problem 2.4, Problem 2.12, Theorem 5.5.9, Proposition 6.3.27, Exercise 6.3.60, Proposition 7.1.3, Theorem 7.6.28, Exercise 8.2.45, Proposition 8.3.25; 2 practice exercises.

Proof (entry by entry).routine

Uses. Proposition 2.4.8 (Four views of the product), Definition 1.1.1 (Field), Notation 2.4.7 (Entries, rows, and columns)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Write

{((𝐴 𝐵) 𝐶)}_{𝑖 𝑗}

as a double sum, using the entry formula twice with two different summation indices.

Hint 2.

{((𝐴 𝐵) 𝐶)}_{𝑖 𝑗} =

\sum_{𝑙} (\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑙}) 𝑐_{𝑙 𝑗}

. Distribute, exchange the two sums, and factor out

𝑎_{𝑖 𝑘}

Sketch. Both

{((𝐴 𝐵) 𝐶)}_{𝑖 𝑗}

and

{(𝐴 (𝐵 𝐶))}_{𝑖 𝑗}

equal

\sum_{𝑘} \sum_{𝑙} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑙} 𝑐_{𝑙 𝑗}

, after distributing and exchanging the finite sums. The other laws follow in the same way from the field axioms, with

{(𝐼_{ℓ})}_{𝑖 𝑘} = 𝛿_{𝑖 𝑘}

for (b).

(a) For $1 \leq 𝑖 \leq ℓ$ and $1 \leq 𝑗 \leq 𝑝$ , by Proposition 2.4.8(a) twice,

\begin{aligned} {((𝐴 𝐵) 𝐶)}_{𝑖 𝑗} & = \sum_{𝑙 = 1}^{𝑛} {(𝐴 𝐵)}_{𝑖 𝑙} 𝑐_{𝑙 𝑗} = \sum_{𝑙 = 1}^{𝑛} (\sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑙}) 𝑐_{𝑙 𝑗} \\ = \sum_{𝑙 = 1}^{𝑛} \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑙} 𝑐_{𝑙 𝑗} = \sum_{𝑘 = 1}^{𝑚} \sum_{𝑙 = 1}^{𝑛} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑙} 𝑐_{𝑙 𝑗} \\ = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} (\sum_{𝑙 = 1}^{𝑛} 𝑏_{𝑘 𝑙} 𝑐_{𝑙 𝑗}) = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} {(𝐵 𝐶)}_{𝑘 𝑗} \\ = {(𝐴 (𝐵 𝐶))}_{𝑖 𝑗} . \end{aligned}

The steps used distributivity and associativity in $𝐹$ and the reordering of a finite sum.

(b) ${(𝐼_{ℓ} 𝐴)}_{𝑖 𝑗} =$ $\sum_{𝑘} 𝛿_{𝑖 𝑘} 𝑎_{𝑘 𝑗} =$ $𝑎_{𝑖 𝑗}$ , since only the term $𝑘 = 𝑖$ survives, and similarly ${(𝐴 𝐼_{𝑚})}_{𝑖 𝑗} =$ $\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝛿_{𝑘 𝑗} =$ $𝑎_{𝑖 𝑗}$ .

(c) By distributivity in $𝐹$ ,

\begin{aligned} {(𝐴 (𝐵 + 𝐵^{'}))}_{𝑖 𝑗} & = \sum_{𝑘} 𝑎_{𝑖 𝑘} (𝑏_{𝑘 𝑗} + 𝑏_{𝑘 𝑗}^{'}) \\ = \sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} + \sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}^{'} \\ = {(𝐴 𝐵 + 𝐴 𝐵^{'})}_{𝑖 𝑗}, \end{aligned}

and the other law is the same with the factors on the other side.

(d) Using commutativity of $𝐹$ to move $𝑎$ to the front,

\begin{aligned} {((𝑎 𝐴) 𝐵)}_{𝑖 𝑗} & = \sum_{𝑘} (𝑎 𝑎_{𝑖 𝑘}) 𝑏_{𝑘 𝑗} = 𝑎 \sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} \\ = \sum_{𝑘} 𝑎_{𝑖 𝑘} (𝑎 𝑏_{𝑘 𝑗}) = {(𝐴 (𝑎 𝐵))}_{𝑖 𝑗}, \end{aligned}

and the middle expression is ${(𝑎 (𝐴 𝐵))}_{𝑖 𝑗}$ . □

The two proofs teach different things. The first explains why the laws hold: matrices multiply like composites because they are composites in disguise, and composition of functions is associative for trivial reasons. All the work went into the dictionary between maps and matrices. The second is self-contained and mechanical. Look at what it used in (a): the laws of addition, associativity of multiplication, and distributivity, but nothing about inverses or commutativity of multiplication. So the same computation proves associativity for matrices with entries in $ℤ$ , in $𝐹 [𝑥]$ , or in any other number system with these laws, even one whose multiplication is not commutative, where there may be no vector spaces and linear maps to translate into. This is what makes block multiplication associative (Section 2.4.8), since blocks are matrices whose “entries” are matrices.

By associativity, products of three or more matrices need no parentheses.

Notation 2.4.16 (Powers of a matrix). For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and an integer $𝑘 \geq 1$ , $𝐴^{𝑘} = 𝐴 𝐴 \dots 𝐴$ ( $𝑘$ factors), and $𝐴^{0} = 𝐼_{𝑛}$ . Then $𝐴^{𝑗} 𝐴^{𝑘} = 𝐴^{𝑗 + 𝑘}$ , and if $𝑇 \in L (𝑉)$ and $ℬ︀$ is a basis of $𝑉$ , then ${[𝑇^{𝑘}]}_{ℬ︀ ℬ︀} =$ ${({[𝑇]}_{ℬ︀ ℬ︀})}^{𝑘}$ by Theorem 2.4.2 and induction on $𝑘$ . Together with Proposition 2.4.12,

\begin{matrix} {[𝑎_{0} id + 𝑎_{1} 𝑇 + \dots + 𝑎_{𝑘} 𝑇^{𝑘}]}_{ℬ︀ ℬ︀} \\ = 𝑎_{0} 𝐼_{𝑛} + 𝑎_{1} 𝐴 + \dots + 𝑎_{𝑘} 𝐴^{𝑘}, \end{matrix}

where $𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}$ .

Exercise 2.4.17.routine Let

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

. Show that

{(𝐴 + 𝐵)}^{2} =

𝐴^{2} +

𝐴 𝐵 +

𝐵 𝐴 +

𝐵^{2}

, and deduce that

{(𝐴 + 𝐵)}^{2} =

𝐴^{2} +

2 𝐴 𝐵 +

𝐵^{2}

if and only if

𝐴 𝐵 = 𝐵 𝐴

. (Here

2 𝐴 𝐵 = 𝐴 𝐵 + 𝐴 𝐵

Solution.

Uses. Proposition 2.4.14 (Algebra of matrices), Definition 1.2.7 (Matrices)

Hint 1. Expand

(𝐴 + 𝐵) (𝐴 + 𝐵)

with both distributive laws. Do not reorder any product.

Hint 2. Subtract

𝐴^{2} + 𝐴 𝐵 + 𝐵^{2}

from both expressions and compare what is left.

Sketch. Distributivity gives

{(𝐴 + 𝐵)}^{2} =

𝐴^{2} +

𝐴 𝐵 +

𝐵 𝐴 +

𝐵^{2}

. This equals

𝐴^{2} + 𝐴 𝐵 + 𝐴 𝐵 + 𝐵^{2}

exactly when

𝐵 𝐴 = 𝐴 𝐵

, by cancelling in the vector space

𝐹^{𝑛 \times 𝑛}

By the two distributive laws of Proposition 2.4.14,

\begin{aligned} (𝐴 + 𝐵) (𝐴 + 𝐵) & = 𝐴 (𝐴 + 𝐵) + 𝐵 (𝐴 + 𝐵) \\ = 𝐴^{2} + 𝐴 𝐵 + 𝐵 𝐴 + 𝐵^{2} . \end{aligned}

So ${(𝐴 + 𝐵)}^{2} =$ $𝐴^{2} +$ $2 𝐴 𝐵 +$ $𝐵^{2}$ holds if and only if $𝐴^{2} +$ $𝐴 𝐵 +$ $𝐵 𝐴 +$ $𝐵^{2} =$ $𝐴^{2} +$ $𝐴 𝐵 +$ $𝐴 𝐵 +$ $𝐵^{2}$ . Adding $- (𝐴^{2} + 𝐴 𝐵 + 𝐵^{2})$ to both sides in the vector space $𝐹^{𝑛 \times 𝑛}$ , this holds if and only if $𝐵 𝐴 = 𝐴 𝐵$ . The familiar identity from high school algebra secretly uses commutativity.

2.4.5What fails

Matrix multiplication shares associativity and distributivity with the multiplication of numbers, but three other familiar properties fail. In each case the failure is already visible for composition of maps.

Example 2.4.18 ( $𝐴 𝐵 \neq 𝐵 𝐴$ ). Let

𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}), 𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) .

Then

𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), 𝐵 𝐴 = (\begin{matrix} 0 & 0 \\ 0 & 1 \end{matrix}) .

In terms of maps, $𝑇_{𝐴}$ sends $𝐞_{2} \mapsto 𝐞_{1} \mapsto 𝟎$ and $𝑇_{𝐵}$ sends $𝐞_{1} \mapsto 𝐞_{2} \mapsto 𝟎$ . Following $𝐞_{1}$ through $𝑇_{𝐴} 𝑇_{𝐵}$ returns it to $𝐞_{1}$ , but following it through $𝑇_{𝐵} 𝑇_{𝐴}$ kills it. For a geometric example, let $𝑃$ be the projection onto the $𝑥$ -axis and $𝑅$ the rotation by a right angle, so that $𝑃 𝑅 \neq 𝑅 𝑃$ by Example 2.1.19. In matrices,

\begin{matrix} (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) = (\begin{matrix} 0 & - 1 \\ 0 & 0 \end{matrix}), \\ (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) . \end{matrix}

Figure 2.4.1 is a third example. When $𝐴 𝐵$ is defined, $𝐵 𝐴$ may not be, and if both are defined they may have different sizes (Example 2.4.4). So “ $𝐴 𝐵 = 𝐵 𝐴$ ” is a strong condition, which we express by saying that $𝐴$ and $𝐵$ commute.

Example 2.4.19 (Zero divisors and the failure of cancellation). With $𝐴$ as above and $𝑃 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ ,

𝐴^{2} = 𝐴 𝑃 = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}), 𝑃 𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}) .

So a product of nonzero matrices can be zero, and even a nonzero square can be zero. In the language of Proposition 1.1.17, $𝐹^{2 \times 2}$ has zero divisors. Note also that $𝐴 𝑃 = 0$ while $𝑃 𝐴 \neq 0$ .

Cancellation fails with them: $𝐴 𝑃 = 𝐴 0$ with $𝐴 \neq 0$ , but $𝑃 \neq 0$ . In general, $𝐴 𝐵 = 𝐴 𝐶$ means $𝐴 (𝐵 - 𝐶) = 0$ (Proposition 2.4.14(c)), so cancelling $𝐴$ is legitimate exactly when $𝐴 𝑋 = 0$ forces $𝑋 = 0$ . For $𝐴$ that are left-invertible (Section 2.5) this holds; for the $𝐴$ above it does not, since $𝑇_{𝐴}$ kills $𝐞_{1}$ , and any $𝑋$ whose columns lie in $span (𝐞_{1})$ satisfies $𝐴 𝑋 = 0$ .

These examples are $2 \times 2$ , which is the smallest size where anything can go wrong: $𝐹^{1 \times 1}$ is just $𝐹$ , where multiplication is commutative and there are no zero divisors. For $𝑛 \geq 2$ , put the $2 \times 2$ examples in the top left corner of an $𝑛 \times 𝑛$ matrix that is zero elsewhere. By block multiplication (Theorem 2.4.34) the products are computed in that corner, so $𝐹^{𝑛 \times 𝑛}$ has the same failures. Finding such examples is an instance of Technique 1.4.18: the first place to look is $2 \times 2$ matrices whose entries are $0$ and $1$ .

Some matrices do commute. A scalar matrix $𝑐 𝐼_{𝑛}$ commutes with every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , since $(𝑐 𝐼_{𝑛}) 𝐴 =$ $𝑐 𝐴 =$ $𝐴 (𝑐 𝐼_{𝑛})$ by Proposition 2.4.14. Any $𝐴$ commutes with its own powers, since $𝐴 𝐴^{𝑘} =$ $𝐴^{𝑘 + 1} =$ $𝐴^{𝑘} 𝐴$ , and hence with every $𝑎_{0} 𝐼_{𝑛} +$ $𝑎_{1} 𝐴 +$ $\dots +$ $𝑎_{𝑘} 𝐴^{𝑘}$ . Diagonal matrices commute with each other (Example 2.4.10), and so do the rotation matrices $[𝑅_{𝛼}]$ and $[𝑅_{𝛽}]$ , since both products equal $[𝑅_{𝛼 + 𝛽}]$ . Which matrices commute with a given one is a recurring question; see Exercise 2.4.42 and Exercise 2.4.43.

Exercise 2.4.20.standard Find

𝐴, 𝐵 \in ℝ^{2 \times 2}

, none of whose eight entries is

0

, with

𝐴 𝐵 = 0

but

𝐵 𝐴 \neq 0

Solution.

Uses. Proposition 2.4.8 (Four views of the product), Definition 2.3.8 (Matrix–vector product)

Hint 1. By the column view,

𝐴 𝐵 = 0

means

𝐴 𝐛 = 𝟎

for each column

𝐛

𝐵

. Start from an

𝐴

that kills some nonzero vector.

Hint 2. Try

𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix})

. Which vectors does it kill? Build

𝐵

from such columns, and then compute

𝐵 𝐴

Sketch.

𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix})

kills

(2, - 1)

, so

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

gives

𝐴 𝐵 = 0

, while

𝐵 𝐴 = (\begin{matrix} 4 & 8 \\ - 2 & - 4 \end{matrix}) \neq 0

By the column view (Proposition 2.4.8(b)), $𝐴 𝐵 = 0$ means that $𝐴$ sends each column of $𝐵$ to $𝟎$ . Let $𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \end{matrix})$ . By Definition 2.3.8, $𝐴 (𝑥, 𝑦) =$ $(𝑥 + 2 𝑦, 𝑥 + 2 𝑦)$ , so $𝐴 (2, - 1) = 𝟎$ . Let $𝐵 = (\begin{matrix} 2 & 2 \\ - 1 & - 1 \end{matrix})$ , whose columns are both $(2, - 1)$ . Then $𝐴 𝐵 = 0$ , and

\begin{matrix} 𝐵 𝐴 = (\begin{matrix} 2 + 2 & 4 + 4 \\ - 1 - 1 & - 2 - 2 \end{matrix}) \\ = (\begin{matrix} 4 & 8 \\ - 2 & - 4 \end{matrix}) \neq 0 . \end{matrix}

No entry of $𝐴$ or $𝐵$ is $0$ .

2.4.6The transpose

The row view and the column view are mirror images of each other. The transpose makes the mirror precise.

Definition 2.4.21 (Transpose). The transpose of $𝐴 =$ $(𝑎_{𝑖 𝑗}) \in$ $𝐹^{𝑚 \times 𝑛}$ is the matrix $𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ with

{(𝐴^{𝖳})}_{𝑖 𝑗} = 𝑎_{𝑗 𝑖} (1 \leq 𝑖 \leq 𝑛, 1 \leq 𝑗 \leq 𝑚) .

That is, row $𝑖$ of $𝐴^{𝖳}$ is column $𝑖$ of $𝐴$ written as a row, and column $𝑗$ of $𝐴^{𝖳}$ is row $𝑗$ of $𝐴$ written as a column. A square matrix $𝐴$ is symmetric if $𝐴^{𝖳} = 𝐴$ and skew-symmetric if $𝐴^{𝖳} = - 𝐴$ .

For example,

\begin{matrix} {(\begin{matrix} 1 & 0 & - 2 \\ 3 & 5 & 4 \end{matrix})}^{𝖳} = (\begin{matrix} 1 & 3 \\ 0 & 5 \\ - 2 & 4 \end{matrix}), \\ {(\begin{matrix} 1 & 2 \\ 2 & 7 \end{matrix})}^{𝖳} = (\begin{matrix} 1 & 2 \\ 2 & 7 \end{matrix}), \\ {(\begin{matrix} 0 & 3 \\ - 3 & 0 \end{matrix})}^{𝖳} = (\begin{matrix} 0 & - 3 \\ 3 & 0 \end{matrix}) . \end{matrix}

The second matrix is symmetric and the third skew-symmetric; symmetric matrices form the subspace of Example 1.4.11. A vector $𝐱 \in 𝐹^{𝑛}$ is a column, so $𝐱^{𝖳} = (\begin{matrix} 𝑥_{1} & \dots & 𝑥_{𝑛} \end{matrix})$ is a row, and for $𝐱, 𝐲 \in 𝐹^{𝑛}$ the $1 \times 1$ product

𝐱^{𝖳} 𝐲 = 𝑥_{1} 𝑦_{1} + 𝑥_{2} 𝑦_{2} + \dots + 𝑥_{𝑛} 𝑦_{𝑛}

is a scalar. In the other order, for $𝐮 \in 𝐹^{𝑚}$ and $𝐯 \in 𝐹^{𝑛}$ , the column–row product $𝐮 𝐯^{𝖳} \in 𝐹^{𝑚 \times 𝑛}$ has $(𝑖, 𝑗)$ entry $𝑢_{𝑖} 𝑣_{𝑗}$ , as in Proposition 2.4.8(d).

Proposition 2.4.22 (Transpose is a linear involution). For $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ and $𝑎 \in 𝐹$ ,

\begin{matrix} {(𝐴^{𝖳})}^{𝖳} = 𝐴, 𝐼_{𝑛}^{𝖳} = 𝐼_{𝑛}, \\ {(𝑎 𝐴 + 𝐵)}^{𝖳} = 𝑎 𝐴^{𝖳} + 𝐵^{𝖳} . \end{matrix}

So $𝐴 \mapsto 𝐴^{𝖳}$ is a linear bijection $𝐹^{𝑚 \times 𝑛} \to 𝐹^{𝑛 \times 𝑚}$ , whose inverse is transposition $𝐹^{𝑛 \times 𝑚} \to 𝐹^{𝑚 \times 𝑛}$ .

Proof.routine

Uses. Definition 2.4.21 (Transpose), Definition 1.2.7 (Matrices), Definition 2.3.5 (Identity matrix)

Hint 1. Compare entries. The

(𝑖, 𝑗)

entry of

{(𝐴^{𝖳})}^{𝖳}

is the

(𝑗, 𝑖)

entry of

𝐴^{𝖳}

Hint 2. For the last claim, transposing twice gives back the matrix you started with, whichever of the two directions you apply first.

Sketch.

{({(𝐴^{𝖳})}^{𝖳})}_{𝑖 𝑗} =

{(𝐴^{𝖳})}_{𝑗 𝑖} =

𝑎_{𝑖 𝑗}

{({(𝑎 𝐴 + 𝐵)}^{𝖳})}_{𝑖 𝑗} =

𝑎 𝑎_{𝑗 𝑖} +

𝑏_{𝑗 𝑖}

, and

𝛿_{𝑗 𝑖} = 𝛿_{𝑖 𝑗}

. The two transposition maps

𝐹^{𝑚 \times 𝑛} \to 𝐹^{𝑛 \times 𝑚}

and back are inverse to each other.

By Definition 2.4.21, ${({(𝐴^{𝖳})}^{𝖳})}_{𝑖 𝑗} =$ ${(𝐴^{𝖳})}_{𝑗 𝑖} =$ $𝑎_{𝑖 𝑗}$ , and since matrices are added and scaled entrywise,

\begin{aligned} {({(𝑎 𝐴 + 𝐵)}^{𝖳})}_{𝑖 𝑗} & = {(𝑎 𝐴 + 𝐵)}_{𝑗 𝑖} = 𝑎 𝑎_{𝑗 𝑖} + 𝑏_{𝑗 𝑖} \\ = {(𝑎 𝐴^{𝖳} + 𝐵^{𝖳})}_{𝑖 𝑗} . \end{aligned}

The $(𝑖, 𝑗)$ entry of $𝐼_{𝑛}^{𝖳}$ is $𝛿_{𝑗 𝑖} = 𝛿_{𝑖 𝑗}$ . So transposition is linear, and applying it twice gives the identity map. Hence it is a bijection from $𝐹^{𝑚 \times 𝑛}$ to $𝐹^{𝑛 \times 𝑚}$ , with transposition $𝐹^{𝑛 \times 𝑚} \to 𝐹^{𝑚 \times 𝑛}$ as its inverse. □

Intuition (Why the order reverses). Before guessing a formula for

{(𝐴 𝐵)}^{𝖳}

, check sizes. If

𝐴 \in 𝐹^{ℓ \times 𝑚}

and

𝐵 \in 𝐹^{𝑚 \times 𝑛}

, then

{(𝐴 𝐵)}^{𝖳}

𝑛 \times ℓ

, while

𝐴^{𝖳} \in 𝐹^{𝑚 \times ℓ}

and

𝐵^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

. So

𝐴^{𝖳} 𝐵^{𝖳}

is not even defined unless

ℓ = 𝑛

, and the only product of the two transposes with the right size is

𝐵^{𝖳} 𝐴^{𝖳}

. The same reversal will appear for inverses of composites (Section 2.5) and for adjoints (Section 6.6).

Proposition 2.4.23 (Transpose of a product). For $𝐴 \in 𝐹^{ℓ \times 𝑚}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ ,

{(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳} .

Proof (entry by entry).routine

Uses. Definition 2.4.21 (Transpose), Proposition 2.4.8 (Four views of the product), Definition 1.1.1 (Field)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Compute the

(𝑖, 𝑗)

entry of each side with Definition 2.4.21 and the entry formula.

Hint 2.

{({(𝐴 𝐵)}^{𝖳})}_{𝑖 𝑗} =

{(𝐴 𝐵)}_{𝑗 𝑖} =

\sum_{𝑘} 𝑎_{𝑗 𝑘} 𝑏_{𝑘 𝑖}

. Write each factor as an entry of a transpose, and reorder each product.

Sketch. The

(𝑖, 𝑗)

entry of

{(𝐴 𝐵)}^{𝖳}

\sum_{𝑘} 𝑎_{𝑗 𝑘} 𝑏_{𝑘 𝑖}

. Since

𝑎_{𝑗 𝑘} 𝑏_{𝑘 𝑖} =

𝑏_{𝑘 𝑖} 𝑎_{𝑗 𝑘} =

{(𝐵^{𝖳})}_{𝑖 𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗}

, this sum is the

(𝑖, 𝑗)

entry of

𝐵^{𝖳} 𝐴^{𝖳}

Both sides are $𝑛 \times ℓ$ . Let $1 \leq 𝑖 \leq 𝑛$ and $1 \leq 𝑗 \leq ℓ$ . By Definition 2.4.21 and Proposition 2.4.8(a), then commutativity of multiplication in $𝐹$ , then Definition 2.4.21 and Proposition 2.4.8(a) again,

\begin{aligned} {({(𝐴 𝐵)}^{𝖳})}_{𝑖 𝑗} & = {(𝐴 𝐵)}_{𝑗 𝑖} = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑗 𝑘} 𝑏_{𝑘 𝑖} = \sum_{𝑘 = 1}^{𝑚} 𝑏_{𝑘 𝑖} 𝑎_{𝑗 𝑘} \\ = \sum_{𝑘 = 1}^{𝑚} {(𝐵^{𝖳})}_{𝑖 𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} = {(𝐵^{𝖳} 𝐴^{𝖳})}_{𝑖 𝑗} . \end{aligned}

□

The first proof used commutativity of $𝐹$ at one step, and that step is where the order of the factors flips. The second proof explains the reversal through the views of the product: the row view of $𝐴 𝐵$ is the column view of $𝐵^{𝖳} 𝐴^{𝖳}$ in a mirror.

Proof (rows become columns).routine

Uses. Proposition 2.4.8 (Four views of the product), Proposition 2.4.22 (Transpose is a linear involution), Definition 2.4.21 (Transpose), Definition 2.3.8 (Matrix–vector product)

Hint 1. Column

𝑖

{(𝐴 𝐵)}^{𝖳}

is row

𝑖

𝐴 𝐵

, written as a column. What is row

𝑖

𝐴 𝐵

in the row view?

Hint 2. Column

𝑖

𝐵^{𝖳} 𝐴^{𝖳}

𝐵^{𝖳}

times column

𝑖

𝐴^{𝖳}

. Expand this with the column view, and compare with the transpose of the row-view expansion.

Sketch. By the row view, row

𝑖

𝐴 𝐵

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝐵_{𝑘, \cdot}

; transposing (a linear operation) gives

\sum_{𝑘} 𝑎_{𝑖 𝑘} {(𝐵^{𝖳})}_{\cdot, 𝑘}

. By the column view, column

𝑖

𝐵^{𝖳} 𝐴^{𝖳}

𝐵^{𝖳} {(𝐴^{𝖳})}_{\cdot, 𝑖} =

\sum_{𝑘} 𝑎_{𝑖 𝑘} {(𝐵^{𝖳})}_{\cdot, 𝑘}

, since

{(𝐴^{𝖳})}_{𝑘 𝑖} = 𝑎_{𝑖 𝑘}

. The two matrices have the same columns.

By Definition 2.4.21, column $𝑖$ of ${(𝐴 𝐵)}^{𝖳}$ is the transpose of row $𝑖$ of $𝐴 𝐵$ . By the row view (Proposition 2.4.8(c)) and the linearity of transposition (Proposition 2.4.22),

\begin{aligned} {({(𝐴 𝐵)}_{𝑖, \cdot})}^{𝖳} & = {(\sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝐵_{𝑘, \cdot})}^{𝖳} = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} {(𝐵_{𝑘, \cdot})}^{𝖳} \\ = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} {(𝐵^{𝖳})}_{\cdot, 𝑘}, \end{aligned}

since the transpose of row $𝑘$ of $𝐵$ is column $𝑘$ of $𝐵^{𝖳}$ . On the other side, column $𝑖$ of $𝐴^{𝖳}$ is the transpose of row $𝑖$ of $𝐴$ , with entries $𝑎_{𝑖 1}, \dots, 𝑎_{𝑖 𝑚}$ . By the column view (Proposition 2.4.8(b)), column $𝑖$ of $𝐵^{𝖳} 𝐴^{𝖳}$ is

𝐵^{𝖳} {(𝐴^{𝖳})}_{\cdot, 𝑖} = 𝑎_{𝑖 1} {(𝐵^{𝖳})}_{\cdot, 1} + \dots + 𝑎_{𝑖 𝑚} {(𝐵^{𝖳})}_{\cdot, 𝑚} .

So ${(𝐴 𝐵)}^{𝖳}$ and $𝐵^{𝖳} 𝐴^{𝖳}$ have the same columns. □

By induction, ${(𝐴_{1} 𝐴_{2} \dots 𝐴_{𝑘})}^{𝖳} =$ $𝐴_{𝑘}^{𝖳} \dots 𝐴_{2}^{𝖳} 𝐴_{1}^{𝖳}$ , and in particular ${(𝐴^{𝑘})}^{𝖳} = {(𝐴^{𝖳})}^{𝑘}$ . Proposition 2.4.23 is the engine of Technique 3.2.27, which turns facts about rows and left multiplication into facts about columns and right multiplication. The transpose also has a meaning in terms of linear maps, which needs more structure than a matrix: with an inner product it is the adjoint (Section 6.6), and in general it is the dual map (Section 13.1).

The column–row products $𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ of standard basis vectors are the simplest matrices of all, and we will use them repeatedly.

Lemma 2.4.24 (Matrix units). For

1 \leq 𝑖 \leq 𝑚

and

1 \leq 𝑗 \leq 𝑛

, the matrix

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳} \in

𝐹^{𝑚 \times 𝑛}

has a

1

in position

(𝑖, 𝑗)

and

0

everywhere else.

(a)Every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ is $𝐴 =$ $\sum_{𝑖 = 1}^{𝑚} \sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑖 𝑗} 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ , and these are the only coefficients that work. So the $𝑚 𝑛$ matrices $𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ form a basis of $𝐹^{𝑚 \times 𝑛}$ .
(b)For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ : $𝐴 𝐞_{𝑗} = 𝐴_{\cdot, 𝑗}$ , $𝐞_{𝑖}^{𝖳} 𝐴 = 𝐴_{𝑖, \cdot}$ , and $𝐞_{𝑖}^{𝖳} 𝐴 𝐞_{𝑗} =$ $𝑎_{𝑖 𝑗}$ .
(c) $(𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) (𝐞_{𝑘} 𝐞_{𝑙}^{𝖳}) =$ $𝛿_{𝑗 𝑘} 𝐞_{𝑖} 𝐞_{𝑙}^{𝖳}$ , for matrices of compatible sizes.

Proof.routine

Uses. Proposition 2.4.8 (Four views of the product), Proposition 2.4.14 (Algebra of matrices), Proposition 2.3.13 (Linearity of the product), Definition 1.6.1 (Basis), Notation 2.4.7 (Entries, rows, and columns)

Hint 1. The

(𝑘, 𝑙)

entry of the column–row product

𝐮 𝐯^{𝖳}

𝑢_{𝑘} 𝑣_{𝑙}

. For

𝐮 = 𝐞_{𝑖}

and

𝐯 = 𝐞_{𝑗}

that is

𝛿_{𝑘 𝑖} 𝛿_{𝑙 𝑗}

Hint 2. For (c), regroup with associativity:

𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐞_{𝑘}) 𝐞_{𝑙}^{𝖳}

, and the middle factor is a

1 \times 1

matrix.

Sketch. The

(𝑘, 𝑙)

entry of

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

𝛿_{𝑘 𝑖} 𝛿_{𝑙 𝑗}

. (a) The

(𝑘, 𝑙)

entry of

\sum 𝑐_{𝑖 𝑗} 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

𝑐_{𝑘 𝑙}

, so it equals

𝐴

exactly when

𝑐_{𝑘 𝑙} = 𝑎_{𝑘 𝑙}

. (b) Column and row views. (c) Associativity and

𝐞_{𝑗}^{𝖳} 𝐞_{𝑘} = 𝛿_{𝑗 𝑘}

By Proposition 2.4.8(a) with inner size $1$ , the $(𝑘, 𝑙)$ entry of $𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ is $𝛿_{𝑘 𝑖} 𝛿_{𝑙 𝑗}$ , which is $1$ if $(𝑘, 𝑙) = (𝑖, 𝑗)$ and $0$ otherwise.

(a) Since matrices are added and scaled entrywise, the $(𝑘, 𝑙)$ entry of $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ is $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝛿_{𝑘 𝑖} 𝛿_{𝑙 𝑗} =$ $𝑐_{𝑘 𝑙}$ . So this sum equals $𝐴$ if and only if $𝑐_{𝑘 𝑙} = 𝑎_{𝑘 𝑙}$ for all $𝑘, 𝑙$ . Every matrix is therefore a linear combination of the $𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ in exactly one way, which is what it means for them to form a basis (Definition 1.6.1), with the entries of $𝐴$ as its coordinates.

(b) $𝐴 𝐞_{𝑗} = 𝐴_{\cdot, 𝑗}$ is Proposition 2.3.13(c). By the row view (Proposition 2.4.8(c)), $𝐞_{𝑖}^{𝖳} 𝐴 =$ $\sum_{𝑘} 𝛿_{𝑖 𝑘} 𝐴_{𝑘, \cdot} =$ $𝐴_{𝑖, \cdot}$ . Then $𝐞_{𝑖}^{𝖳} 𝐴 𝐞_{𝑗} =$ $𝐴_{𝑖, \cdot} 𝐞_{𝑗}$ is the $𝑗$ -th entry of row $𝑖$ , which is $𝑎_{𝑖 𝑗}$ .

(c) By associativity (Proposition 2.4.14) and (b), $𝐞_{𝑗}^{𝖳} 𝐞_{𝑘}$ is the $(𝑗, 𝑘)$ entry of $𝐼$ , which is $𝛿_{𝑗 𝑘}$ . So

(𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) (𝐞_{𝑘} 𝐞_{𝑙}^{𝖳}) = 𝐞_{𝑖} (𝐞_{𝑗}^{𝖳} 𝐞_{𝑘}) 𝐞_{𝑙}^{𝖳} = 𝛿_{𝑗 𝑘} 𝐞_{𝑖} 𝐞_{𝑙}^{𝖳} .

□

Part (c) gives the noncommutativity of Example 2.4.18 in its purest form: for $𝑖 \neq 𝑗$ , $(𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) (𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) =$ $𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}$ , while $(𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) =$ $𝐞_{𝑗} 𝐞_{𝑗}^{𝖳}$ . The matrices $𝐴$ and $𝐵$ of that example are $𝐞_{1} 𝐞_{2}^{𝖳}$ and $𝐞_{2} 𝐞_{1}^{𝖳}$ .

Exercise 2.4.25.routine

(a)Show that $𝐴^{𝖳} 𝐴$ and $𝐴 𝐴^{𝖳}$ are symmetric for every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .
(b)Let $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ be symmetric. Show that $𝐴 𝐵 + 𝐵 𝐴$ is symmetric, that $𝐴 𝐵 - 𝐵 𝐴$ is skew-symmetric, and that $𝐴 𝐵$ is symmetric if and only if $𝐴 𝐵 = 𝐵 𝐴$ .

Solution.

Uses. Proposition 2.4.23 (Transpose of a product), Proposition 2.4.22 (Transpose is a linear involution)

Hint 1. Take the transpose of each expression with Proposition 2.4.23, and use

{(𝐴^{𝖳})}^{𝖳} = 𝐴

Hint 2. For symmetric

𝐴

and

𝐵

{(𝐴 𝐵)}^{𝖳} =

𝐵^{𝖳} 𝐴^{𝖳} =

𝐵 𝐴

Sketch. (a)

{(𝐴^{𝖳} 𝐴)}^{𝖳} =

𝐴^{𝖳} {(𝐴^{𝖳})}^{𝖳} =

𝐴^{𝖳} 𝐴

, and likewise for

𝐴 𝐴^{𝖳}

. (b)

{(𝐴 𝐵)}^{𝖳} = 𝐵 𝐴

, so transposing swaps

𝐴 𝐵

and

𝐵 𝐴

𝐴 𝐵 + 𝐵 𝐴

is fixed,

𝐴 𝐵 - 𝐵 𝐴

changes sign, and

𝐴 𝐵

is fixed exactly when

𝐴 𝐵 = 𝐵 𝐴

(a) By Proposition 2.4.23 and Proposition 2.4.22, ${(𝐴^{𝖳} 𝐴)}^{𝖳} =$ $𝐴^{𝖳} {(𝐴^{𝖳})}^{𝖳} =$ $𝐴^{𝖳} 𝐴$ and ${(𝐴 𝐴^{𝖳})}^{𝖳} =$ ${(𝐴^{𝖳})}^{𝖳} 𝐴^{𝖳} =$ $𝐴 𝐴^{𝖳}$ .

(b) Since $𝐴^{𝖳} = 𝐴$ and $𝐵^{𝖳} = 𝐵$ , Proposition 2.4.23 gives ${(𝐴 𝐵)}^{𝖳} =$ $𝐵^{𝖳} 𝐴^{𝖳} =$ $𝐵 𝐴$ , and likewise ${(𝐵 𝐴)}^{𝖳} = 𝐴 𝐵$ . By linearity of transposition (Proposition 2.4.22),

\begin{matrix} {(𝐴 𝐵 + 𝐵 𝐴)}^{𝖳} = 𝐵 𝐴 + 𝐴 𝐵, \\ {(𝐴 𝐵 - 𝐵 𝐴)}^{𝖳} = 𝐵 𝐴 - 𝐴 𝐵 = - (𝐴 𝐵 - 𝐵 𝐴) . \end{matrix}

Finally $𝐴 𝐵$ is symmetric if and only if $𝐴 𝐵 =$ ${(𝐴 𝐵)}^{𝖳} =$ $𝐵 𝐴$ .

2.4.7The trace

Matrix multiplication is not commutative, but there is a number attached to a square matrix that cannot tell $𝐴 𝐵$ from $𝐵 𝐴$ .

Definition 2.4.26 (Trace). The trace of $𝐴 =$ $(𝑎_{𝑖 𝑗}) \in$ $𝐹^{𝑛 \times 𝑛}$ is the sum of its diagonal entries,

tr 𝐴 = 𝑎_{11} + 𝑎_{22} + \dots + 𝑎_{𝑛 𝑛} = \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑖} .

For example, $tr (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) = 5$ and $tr 𝐼_{𝑛} = 𝑛 * 1$ , which is $𝑛$ over $ℚ$ , $ℝ$ , or $ℂ$ and is $0$ over $𝔽_{𝑝}$ when $𝑝 ∣ 𝑛$ . In this notation, the trace-zero matrices of Example 1.4.11 are those with $tr 𝐴 = 0$ .

Proposition 2.4.27 (The trace is linear). For

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

and

𝑎 \in 𝐹

tr (𝑎 𝐴 + 𝐵) =

𝑎 tr 𝐴 +

tr 𝐵

and

tr 𝐴^{𝖳} = tr 𝐴

Proof.routine

Uses. Definition 2.4.26 (Trace), Definition 1.2.7 (Matrices), Definition 2.4.21 (Transpose)

Hint 1. The diagonal entries of

𝑎 𝐴 + 𝐵

are

𝑎 𝑎_{𝑖 𝑖} + 𝑏_{𝑖 𝑖}

Hint 2. Transposing does not move the diagonal entries:

{(𝐴^{𝖳})}_{𝑖 𝑖} = 𝑎_{𝑖 𝑖}

Sketch. The diagonal entries of

𝑎 𝐴 + 𝐵

are

𝑎 𝑎_{𝑖 𝑖} + 𝑏_{𝑖 𝑖}

; add them up. Transposing fixes the diagonal:

{(𝐴^{𝖳})}_{𝑖 𝑖} = 𝑎_{𝑖 𝑖}

Matrices are added and scaled entrywise, so

\begin{aligned} tr (𝑎 𝐴 + 𝐵) & = \sum_{𝑖} (𝑎 𝑎_{𝑖 𝑖} + 𝑏_{𝑖 𝑖}) \\ = 𝑎 \sum_{𝑖} 𝑎_{𝑖 𝑖} + \sum_{𝑖} 𝑏_{𝑖 𝑖} = 𝑎 tr 𝐴 + tr 𝐵 . \end{aligned}

By Definition 2.4.21, ${(𝐴^{𝖳})}_{𝑖 𝑖} = 𝑎_{𝑖 𝑖}$ , so $tr 𝐴^{𝖳} = tr 𝐴$ . □

The trace is not multiplicative: for $𝐴 = diag (1, 0)$ and $𝐵 = diag (0, 1)$ we have $𝐴 𝐵 = 0$ , so $tr (𝐴 𝐵) = 0$ , but $tr 𝐴 tr 𝐵 = 1$ . What it does satisfy is the following.

Proposition 2.4.28 (Cyclicity of the trace). For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ ,

tr (𝐴 𝐵) = tr (𝐵 𝐴) .

Intuition. Here

𝐴 𝐵

𝑚 \times 𝑚

and

𝐵 𝐴

𝑛 \times 𝑛

, so the two products may not even have the same size, let alone be equal. But the diagonal entries of

𝐴 𝐵

are

{(𝐴 𝐵)}_{𝑖 𝑖} =

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑖}

, so

tr (𝐴 𝐵)

is the sum of

𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑖}

over all pairs

(𝑖, 𝑘)

: every entry of

𝐴

multiplied by the entry of

𝐵

in the mirror position. That description is symmetric in

𝐴

and

𝐵

. There is also an approach that avoids indices. For fixed

𝐴

, both sides are linear in

𝐵

, so by Technique 2.2.7 it is enough to check the identity for the matrix units of Lemma 2.4.24.

Proof (entry by entry).routine

Uses. Definition 2.4.26 (Trace), Proposition 2.4.8 (Four views of the product), Definition 1.1.1 (Field)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Write

tr (𝐴 𝐵) =

\sum_{𝑖} {(𝐴 𝐵)}_{𝑖 𝑖}

and expand each diagonal entry with the entry formula.

Hint 2. You get a double sum

\sum_{𝑖} \sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑖}

. Exchange the order of summation and recognize the diagonal entries of

𝐵 𝐴

Sketch. Both

tr (𝐴 𝐵)

and

tr (𝐵 𝐴)

expand to the double sum of

𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑖}

over all

𝑖 \leq 𝑚

and

𝑘 \leq 𝑛

; the two expansions differ only in the order of summation.

By Definition 2.4.26 and Proposition 2.4.8(a),

\begin{aligned} tr (𝐴 𝐵) & = \sum_{𝑖 = 1}^{𝑚} {(𝐴 𝐵)}_{𝑖 𝑖} = \sum_{𝑖 = 1}^{𝑚} \sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑖} \\ = \sum_{𝑘 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑚} 𝑏_{𝑘 𝑖} 𝑎_{𝑖 𝑘} \\ = \sum_{𝑘 = 1}^{𝑛} {(𝐵 𝐴)}_{𝑘 𝑘} = tr (𝐵 𝐴), \end{aligned}

where we exchanged the two finite sums and used commutativity of multiplication in $𝐹$ . □

Proof (check on matrix units).standard

Uses. Lemma 2.4.24 (Matrix units), Proposition 2.4.27 (The trace is linear), Proposition 2.4.14 (Algebra of matrices), Corollary 2.2.6 (Agreeing on a spanning list), Definition 2.4.26 (Trace)

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. Fix

𝐴

and define

𝜑, 𝜓 : 𝐹^{𝑛 \times 𝑚} \to 𝐹

𝜑 (𝑋) = tr (𝐴 𝑋)

and

𝜓 (𝑋) = tr (𝑋 𝐴)

. Why are these linear?

Hint 2. By Corollary 2.2.6, it is enough that

𝜑

and

𝜓

agree on the matrix units

𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}

(

1 \leq 𝑘 \leq 𝑛

1 \leq 𝑖 \leq 𝑚

Hint 3.

𝐴 𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}

is zero except for column

𝑖

, which is

𝐴_{\cdot, 𝑘}

. Which diagonal entry survives? Do the same for

𝐞_{𝑘} 𝐞_{𝑖}^{𝖳} 𝐴

with rows.

Sketch.

𝜑 (𝑋) = tr (𝐴 𝑋)

and

𝜓 (𝑋) = tr (𝑋 𝐴)

are linear in

𝑋

by distributivity and Proposition 2.4.27.

𝐴 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) =

𝐴_{\cdot, 𝑘} 𝐞_{𝑖}^{𝖳}

has only column

𝑖

nonzero, so its trace is its

(𝑖, 𝑖)

entry

𝑎_{𝑖 𝑘}

;

(𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) 𝐴 =

𝐞_{𝑘} 𝐴_{𝑖, \cdot}

has only row

𝑘

nonzero, with

(𝑘, 𝑘)

entry

𝑎_{𝑖 𝑘}

. They agree on a spanning list, so

𝜑 = 𝜓

; take

𝑋 = 𝐵

Fix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and define $𝜑, 𝜓 : 𝐹^{𝑛 \times 𝑚} \to 𝐹$ by $𝜑 (𝑋) = tr (𝐴 𝑋)$ and $𝜓 (𝑋) = tr (𝑋 𝐴)$ . Both are linear: for instance $𝜑 (𝑐 𝑋 + 𝑌) =$ $tr (𝑐 𝐴 𝑋 + 𝐴 𝑌) =$ $𝑐 𝜑 (𝑋) +$ $𝜑 (𝑌)$ by Proposition 2.4.14 and Proposition 2.4.27. By Lemma 2.4.24(a), the matrices $𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}$ with $1 \leq 𝑘 \leq 𝑛$ and $1 \leq 𝑖 \leq 𝑚$ span $𝐹^{𝑛 \times 𝑚}$ , so by Corollary 2.2.6 it suffices to show $𝜑 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) =$ $𝜓 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳})$ .

By associativity and Lemma 2.4.24(b), $𝐴 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) =$ $(𝐴 𝐞_{𝑘}) 𝐞_{𝑖}^{𝖳} =$ $𝐴_{\cdot, 𝑘} 𝐞_{𝑖}^{𝖳}$ . This $𝑚 \times 𝑚$ matrix has $(𝑟, 𝑠)$ entry $𝑎_{𝑟 𝑘} 𝛿_{𝑠 𝑖}$ , so its only nonzero column is column $𝑖$ , and its only diagonal entry that can be nonzero is the $(𝑖, 𝑖)$ entry $𝑎_{𝑖 𝑘}$ . Hence $𝜑 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) =$ $𝑎_{𝑖 𝑘}$ . Similarly, $(𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) 𝐴 =$ $𝐞_{𝑘} (𝐞_{𝑖}^{𝖳} 𝐴) =$ $𝐞_{𝑘} 𝐴_{𝑖, \cdot}$ is the $𝑛 \times 𝑛$ matrix with $(𝑟, 𝑠)$ entry $𝛿_{𝑟 𝑘} 𝑎_{𝑖 𝑠}$ , whose only possibly nonzero diagonal entry is the $(𝑘, 𝑘)$ entry $𝑎_{𝑖 𝑘}$ . So $𝜓 (𝐞_{𝑘} 𝐞_{𝑖}^{𝖳}) =$ $𝑎_{𝑖 𝑘}$ as well. Hence $𝜑 = 𝜓$ , and $𝜑 (𝐵) = 𝜓 (𝐵)$ is the claim. □

The first proof is shorter. The second shows what linearity in $𝐵$ buys: only $𝑚 𝑛$ very simple products need to be computed, and each is a picture (one nonzero column, one nonzero row) rather than a sum.

Cyclicity extends to longer products by grouping: $tr (𝐴 𝐵 𝐶) =$ $tr (𝐴 (𝐵 𝐶)) =$ $tr ((𝐵 𝐶) 𝐴) =$ $tr (𝐵 𝐶 𝐴)$ , and likewise $tr (𝐵 𝐶 𝐴) =$ $tr (𝐶 𝐴 𝐵)$ . A product inside a trace can be rotated, but not rearranged arbitrarily (Exercise 2.4.32). This makes the trace a test for identities in which the order of factors matters.

Technique 2.4.29 (Cyclicity of trace). The trace is linear, and it does not see the order of two factors: $tr (𝐴 𝐵) = tr (𝐵 𝐴)$ , so $tr (𝐴_{1} 𝐴_{2} \dots 𝐴_{𝑘})$ is unchanged by rotating the factors cyclically. Take the trace of both sides of a claimed identity. If the traces differ, the identity is false; and quantities such as $𝐴 𝐵 - 𝐵 𝐴$ , which are invisible to the trace, can be eliminated.

Reach for it when commutators $𝐴 𝐵 - 𝐵 𝐴$ appear (they always have trace $0$ ), when a product is conjugated as in $𝑆^{- 1} 𝐴 𝑆$ (once inverses are available, $tr (𝑆^{- 1} 𝐴 𝑆) =$ $tr (𝐴 𝑆 𝑆^{- 1}) =$ $tr 𝐴$ , which makes the trace a similarity invariant, Section 4.5), and when an inner product of matrices is written as $tr (𝐵^{𝖳} 𝐴)$ (Section 6.1). Only cyclic rotations are allowed: $tr (𝐴 𝐵 𝐶)$ and $tr (𝐵 𝐴 𝐶)$ differ in general. And the trace detects nothing about a matrix of trace $0$ ; it is a single number, so it can rule things out but rarely proves them. The canonical example is Proposition 2.4.30.

Used in 28 places and 5 practice exercises

Proposition 2.4.30, Exercise 2.4.50, Exercise 2.4.52, Exercise 2.4.53, Exercise 2.4.54, Exercise 2.5.44, Exercise 2.8.12, Problem 2.9, Problem 2.16, Problem 2.17, Exercise 4.3.38, Exercise 4.3.43, Proposition 4.5.27, Exercise 4.5.47, Exercise 6.3.48, Exercise 6.4.51, Exercise 6.5.38, Problem 6.11, Problem 6.18, Proposition 7.5.25, Corollary 7.5.26, Exercise 7.5.41, Exercise 7.5.44, Exercise 7.6.56, Exercise 8.1.33, Exercise 8.1.37, Exercise 8.1.38, Exercise 8.3.34; 5 practice exercises.

Proposition 2.4.30 (

𝐴 𝐵 - 𝐵 𝐴 \neq 𝐼

). Let

𝑛 \geq 1

, and suppose that

𝑛 * 1 \neq 0

𝐹

; for instance,

𝐹

has characteristic

0

(Definition 1.1.28). Then

𝐴 𝐵 - 𝐵 𝐴 \neq 𝐼_{𝑛}

for all

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

Proof.routine

Uses. Proposition 2.4.27 (The trace is linear), Proposition 2.4.28 (Cyclicity of the trace), Definition 2.4.26 (Trace)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. Take the trace of both sides of

𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑛}

Hint 2. By linearity and cyclicity,

tr (𝐴 𝐵 - 𝐵 𝐴) =

tr (𝐴 𝐵) -

tr (𝐵 𝐴) =

0

. What is

tr 𝐼_{𝑛}

Sketch.

tr (𝐴 𝐵 - 𝐵 𝐴) =

tr (𝐴 𝐵) -

tr (𝐵 𝐴) =

0

, but

tr 𝐼_{𝑛} = 𝑛 * 1 \neq 0

By Proposition 2.4.27 and Proposition 2.4.28,

tr (𝐴 𝐵 - 𝐵 𝐴) =

tr (𝐴 𝐵) -

tr (𝐵 𝐴) =

0

. But

tr 𝐼_{𝑛} = 1 + \dots + 1 = 𝑛 * 1

, which is nonzero by hypothesis. So

𝐴 𝐵 - 𝐵 𝐴

and

𝐼_{𝑛}

have different traces and cannot be equal. □

In terms of maps: on the infinite-dimensional space $𝐹 [𝑥]$ , differentiation $𝐷$ and multiplication by $𝑥$ satisfy $𝐷 𝑀 - 𝑀 𝐷 = id$ , by the product rule (Exercise 2.4.51). Proposition 2.4.30 says that this identity has no solution by $𝑛 \times 𝑛$ matrices, that is, by operators on $𝐹^{𝑛}$ , when $𝑛 * 1 \neq 0$ . In quantum mechanics the same relation holds between the position and momentum operators, and this is why they cannot act on a finite-dimensional space.

Remark 2.4.31 (The hypothesis $𝑛 * 1 \neq 0$ is needed). The matrices of Example 2.4.18 satisfy

\begin{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}) . \end{matrix}

Over $𝔽_{2}$ , where $- 1 = 1$ , this is $𝐼_{2}$ . There is no contradiction with Proposition 2.4.30, because $2 * 1 = 0$ in $𝔽_{2}$ , and indeed $tr 𝐼_{2} = 0$ there. In general, over $𝔽_{𝑝}$ there are $𝑝 \times 𝑝$ matrices with $𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑝}$ (Exercise 2.4.52).

Exercise 2.4.32.standard Find the error in the following argument, and show that its conclusion is false.

Claim. For all $𝐴, 𝐵, 𝐶 \in 𝐹^{𝑛 \times 𝑛}$ , $tr (𝐴 𝐵 𝐶) =$ $tr (𝐵 𝐴 𝐶)$ .

Proof. By associativity and Proposition 2.4.28,

\begin{aligned} tr (𝐴 𝐵 𝐶) & = tr ((𝐴 𝐵) 𝐶) \\ = tr ((𝐵 𝐴) 𝐶) = tr (𝐵 𝐴 𝐶) . \end{aligned}

Solution.

Uses. Proposition 2.4.28 (Cyclicity of the trace), Lemma 2.4.24 (Matrix units)

Hint 1. Proposition 2.4.28 says

tr (𝑋 𝑌) = tr (𝑌 𝑋)

, an equality of two numbers. Does it say

𝑋 𝑌 = 𝑌 𝑋

Hint 2. For a counterexample, try

𝐴 = 𝐞_{1} 𝐞_{2}^{𝖳}

𝐵 = 𝐞_{2} 𝐞_{1}^{𝖳}

, and

𝐶 = 𝐞_{1} 𝐞_{1}^{𝖳}

𝐹^{2 \times 2}

Sketch. The step

tr ((𝐴 𝐵) 𝐶) =

tr ((𝐵 𝐴) 𝐶)

replaces

𝐴 𝐵

𝐵 𝐴

inside a product, which needs

𝐴 𝐵 = 𝐵 𝐴

; cyclicity only gives

tr (𝑋 𝑌) = tr (𝑌 𝑋)

. With the matrix units above,

𝐴 𝐵 𝐶 = 𝐞_{1} 𝐞_{1}^{𝖳}

has trace

1

and

𝐵 𝐴 𝐶 = 0

The error is in the step $tr ((𝐴 𝐵) 𝐶) =$ $tr ((𝐵 𝐴) 𝐶)$ . Proposition 2.4.28 says that $tr (𝑋 𝑌) = tr (𝑌 𝑋)$ for two matrices $𝑋$ and $𝑌$ . With $𝑋 = 𝐴 𝐵$ and $𝑌 = 𝐶$ it gives $tr (𝐴 𝐵 𝐶) =$ $tr (𝐶 𝐴 𝐵)$ , a rotation. It does not say that $𝐴 𝐵$ and $𝐵 𝐴$ are equal, or that they can be exchanged inside a longer product; the argument used $tr (𝐴 𝐵) = tr (𝐵 𝐴)$ as if it were $𝐴 𝐵 = 𝐵 𝐴$ .

The conclusion is false. In $𝐹^{2 \times 2}$ , let $𝐴 = 𝐞_{1} 𝐞_{2}^{𝖳}$ , $𝐵 = 𝐞_{2} 𝐞_{1}^{𝖳}$ , and $𝐶 = 𝐞_{1} 𝐞_{1}^{𝖳}$ . By Lemma 2.4.24(c), $𝐴 𝐵 = 𝐞_{1} 𝐞_{1}^{𝖳}$ and $𝐵 𝐴 = 𝐞_{2} 𝐞_{2}^{𝖳}$ , so

\begin{matrix} 𝐴 𝐵 𝐶 = 𝐞_{1} 𝐞_{1}^{𝖳} 𝐞_{1} 𝐞_{1}^{𝖳} = 𝐞_{1} 𝐞_{1}^{𝖳}, \\ 𝐵 𝐴 𝐶 = 𝐞_{2} 𝐞_{2}^{𝖳} 𝐞_{1} 𝐞_{1}^{𝖳} = 0 . \end{matrix}

Hence $tr (𝐴 𝐵 𝐶) =$ $1 \neq$ $0 =$ $tr (𝐵 𝐴 𝐶)$ . In matrices: $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ , $𝐶 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .

2.4.8Block matrices

Large matrices often have structure that is visible only when we group their entries into rectangular pieces, such as a block of zeros or a copy of the identity. Multiplication respects this grouping.

Definition 2.4.33 (Block matrix). Let $𝐴 \in 𝐹^{ℓ \times 𝑚}$ . Split the row indices $1, \dots, ℓ$ into $𝑟$ consecutive groups of sizes $ℓ_{1}, \dots, ℓ_{𝑟}$ , so $ℓ_{1} + \dots + ℓ_{𝑟} = ℓ$ , and the column indices into $𝑠$ consecutive groups of sizes $𝑚_{1}, \dots, 𝑚_{𝑠}$ . The block $𝐴_{𝐼 𝐾} \in 𝐹^{ℓ_{𝐼} \times 𝑚_{𝐾}}$ is the submatrix of $𝐴$ formed by the entries in the $𝐼$ -th group of rows and the $𝐾$ -th group of columns. We then write $𝐴$ as an $𝑟 \times 𝑠$ array of blocks,

𝐴 = (\begin{matrix} 𝐴_{11} & \dots & 𝐴_{1 𝑠} \\ ⋮ & ⋮ \\ 𝐴_{𝑟 1} & \dots & 𝐴_{𝑟 𝑠} \end{matrix}),

and call this a block matrix, partitioned with row sizes $ℓ_{1}, \dots, ℓ_{𝑟}$ and column sizes $𝑚_{1}, \dots, 𝑚_{𝑠}$ . A block of zeros is written $0$ .

For example, with row sizes $1, 2$ and column sizes $2, 2$ ,

(\begin{matrix} 1 & 2 & 0 & 3 \\ 0 & 1 & 4 & 5 \\ 2 & 0 & 6 & 7 \end{matrix}) = (\begin{matrix} 𝐴_{11} & 𝐴_{12} \\ 𝐴_{21} & 𝐴_{22} \end{matrix}),

where, for instance, $𝐴_{11} = (\begin{matrix} 1 & 2 \end{matrix})$ and $𝐴_{22} = (\begin{matrix} 4 & 5 \\ 6 & 7 \end{matrix})$ . A square block matrix with square diagonal blocks $𝐴_{11}, \dots, 𝐴_{𝑟 𝑟}$ is block diagonal if all other blocks are zero, and block upper triangular if $𝐴_{𝐼 𝐾} = 0$ whenever $𝐼 > 𝐾$ .

Theorem 2.4.34 (Block multiplication). Let $𝐴 \in 𝐹^{ℓ \times 𝑚}$ be partitioned with row sizes $ℓ_{1}, \dots, ℓ_{𝑟}$ and column sizes $𝑚_{1}, \dots, 𝑚_{𝑠}$ , and let $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ be partitioned with row sizes $𝑚_{1}, \dots, 𝑚_{𝑠}$ (the column sizes of $𝐴$ ) and column sizes $𝑛_{1}, \dots, 𝑛_{𝑡}$ . Partition $𝐴 𝐵$ with row sizes $ℓ_{1}, \dots, ℓ_{𝑟}$ and column sizes $𝑛_{1}, \dots, 𝑛_{𝑡}$ . Then

{(𝐴 𝐵)}_{𝐼 𝐽} = \sum_{𝐾 = 1}^{𝑠} 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}

for $1 \leq 𝐼 \leq 𝑟$ and $1 \leq 𝐽 \leq 𝑡$ . That is, block matrices are multiplied by the entry formula, treating blocks as entries and keeping each product in its order.

Proof (entry by entry).standard

Uses. Definition 2.4.33 (Block matrix), Proposition 2.4.8 (Four views of the product)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Fix an entry of

𝐴 𝐵

in block

(𝐼, 𝐽)

, and write it with the entry formula as a sum over

𝑘 = 1, \dots, 𝑚

Hint 2. Split that sum according to the group of columns of

𝐴

(equivalently, rows of

𝐵

) that

𝑘

lies in. Each piece is an entry of some

𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}

Sketch. For row

𝑖

in group

𝐼

and column

𝑗

in group

𝐽

{(𝐴 𝐵)}_{𝑖 𝑗} =

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

. Grouping the indices

𝑘

by the

𝐾

-th group of columns of

𝐴

, the

𝐾

-th partial sum is exactly the corresponding entry of

𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}

, by the entry formula for that product. Adding over

𝐾

gives the entry of

\sum_{𝐾} 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}

Let $𝑖$ be the $𝑝$ -th row index in the $𝐼$ -th group of rows, and $𝑗$ the $𝑞$ -th column index in the $𝐽$ -th group of columns. Write $𝐺_{𝐾}$ for the $𝐾$ -th group of indices in ${1, \dots, 𝑚}$ , which has $𝑚_{𝐾}$ elements. For $𝑘$ the $𝑢$ -th element of $𝐺_{𝐾}$ , the entries $𝑎_{𝑖 𝑘}$ and $𝑏_{𝑘 𝑗}$ are the entries ${(𝐴_{𝐼 𝐾})}_{𝑝 𝑢}$ and ${(𝐵_{𝐾 𝐽})}_{𝑢 𝑞}$ of the blocks. Splitting the sum over $𝑘$ into the groups $𝐺_{1}, \dots, 𝐺_{𝑠}$ ,

\begin{aligned} {(𝐴 𝐵)}_{𝑖 𝑗} & = \sum_{𝑘 = 1}^{𝑚} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} = \sum_{𝐾 = 1}^{𝑠} \sum_{𝑘 \in 𝐺_{𝐾}} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} \\ = \sum_{𝐾 = 1}^{𝑠} \sum_{𝑢 = 1}^{𝑚_{𝐾}} {(𝐴_{𝐼 𝐾})}_{𝑝 𝑢} {(𝐵_{𝐾 𝐽})}_{𝑢 𝑞} \\ = \sum_{𝐾 = 1}^{𝑠} {(𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽})}_{𝑝 𝑞} . \end{aligned}

The left side is the $(𝑝, 𝑞)$ entry of ${(𝐴 𝐵)}_{𝐼 𝐽}$ and the right side is the $(𝑝, 𝑞)$ entry of $\sum_{𝐾} 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}$ . □

The second proof reduces the theorem to three special cases, each of which is one of the views of Proposition 2.4.8.

Proof (from the views).standard

Uses. Proposition 2.4.8 (Four views of the product), Definition 2.4.33 (Block matrix)

Hint 1. Handle three special cases first: only the columns of

𝐵

are split; only the rows of

𝐴

are split; only the inner index is split,

𝐴 = (\begin{matrix} 𝐴_{1} & \dots & 𝐴_{𝑠} \end{matrix})

and

𝐵

𝐵_{1}, \dots, 𝐵_{𝑠}

stacked.

Hint 2. The first two cases are the column and row views. For the third, group the terms of the column–row view.

Hint 3. For the general case, block

(𝐼, 𝐽)

𝐴 𝐵

is (rows of group

𝐼

𝐴

) times (columns of group

𝐽

𝐵

) by the first two cases; now apply the third.

Sketch. By the column view, the columns of

𝐴 𝐵

in group

𝐽

are

𝐴

times the columns of

𝐵

in group

𝐽

; by the row view, the rows of

𝐴 𝐵

in group

𝐼

are the rows of

𝐴

in group

𝐼

times

𝐵

. So

{(𝐴 𝐵)}_{𝐼 𝐽} =

𝐴_{𝐼} 𝐵^{𝐽}

, with

𝐴_{𝐼}

the

𝐼

-th block row of

𝐴

and

𝐵^{𝐽}

the

𝐽

-th block column of

𝐵

. By the column–row view,

𝐴_{𝐼} 𝐵^{𝐽} =

\sum_{𝑘} {(𝐴_{𝐼})}_{\cdot, 𝑘} {(𝐵^{𝐽})}_{𝑘, \cdot}

, and grouping the

𝑘

by blocks gives

\sum_{𝐾} 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}

Let $𝐴_{𝐼}$ be the $𝐼$ -th block row of $𝐴$ , that is, the $ℓ_{𝐼} \times 𝑚$ matrix formed by the rows of $𝐴$ in the $𝐼$ -th group, and let $𝐵^{𝐽}$ be the $𝐽$ -th block column of $𝐵$ , the $𝑚 \times 𝑛_{𝐽}$ matrix formed by its columns in the $𝐽$ -th group.

By the row view (Proposition 2.4.8(c)), each row of $𝐴 𝐵$ in the $𝐼$ -th group is the corresponding row of $𝐴$ times $𝐵$ , so these rows form the matrix $𝐴_{𝐼} 𝐵$ . By the column view (Proposition 2.4.8(b)), applied to $𝐴_{𝐼} 𝐵$ , its columns in the $𝐽$ -th group are $𝐴_{𝐼}$ times the corresponding columns of $𝐵$ , which form $𝐴_{𝐼} 𝐵^{𝐽}$ . Hence ${(𝐴 𝐵)}_{𝐼 𝐽} =$ $𝐴_{𝐼} 𝐵^{𝐽}$ .

By the column–row view (Proposition 2.4.8(d)), $𝐴_{𝐼} 𝐵^{𝐽} =$ $\sum_{𝑘 = 1}^{𝑚} {(𝐴_{𝐼})}_{\cdot, 𝑘} {(𝐵^{𝐽})}_{𝑘, \cdot}$ . Group the terms by the groups $𝐺_{1}, \dots, 𝐺_{𝑠}$ of the index $𝑘$ . The columns of $𝐴_{𝐼}$ with $𝑘 \in 𝐺_{𝐾}$ are the columns of $𝐴_{𝐼 𝐾}$ , and the rows of $𝐵^{𝐽}$ with $𝑘 \in 𝐺_{𝐾}$ are the rows of $𝐵_{𝐾 𝐽}$ , in the same order. So by the column–row view again, applied to $𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}$ ,

\sum_{𝑘 \in 𝐺_{𝐾}} {(𝐴_{𝐼})}_{\cdot, 𝑘} {(𝐵^{𝐽})}_{𝑘, \cdot} = 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽},

and summing over $𝐾$ gives ${(𝐴 𝐵)}_{𝐼 𝐽} =$ $\sum_{𝐾} 𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}$ . □

In the second proof the three special cases are what to remember: blocks of columns of $𝐵$ produce blocks of columns of $𝐴 𝐵$ , blocks of rows of $𝐴$ produce blocks of rows of $𝐴 𝐵$ , and splitting the inner index turns the product into a sum. The partitions must match: the column sizes of $𝐴$ must be the row sizes of $𝐵$ , or the products $𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}$ are not defined. And the factors cannot be swapped, since blocks are matrices: $𝐴_{𝐼 𝐾} 𝐵_{𝐾 𝐽}$ is not $𝐵_{𝐾 𝐽} 𝐴_{𝐼 𝐾}$ .

For $2 \times 2$ block matrices the theorem says that the $(𝐼, 𝐽)$ block of $𝐴 𝐵$ is $𝐴_{𝐼 1} 𝐵_{1 𝐽} +$ $𝐴_{𝐼 2} 𝐵_{2 𝐽}$ , exactly as for the entries of a product of $2 \times 2$ matrices. For block diagonal matrices it gives

\begin{matrix} (\begin{matrix} 𝐴_{1} & 0 \\ 0 & 𝐴_{2} \end{matrix}) (\begin{matrix} 𝐵_{1} & 0 \\ 0 & 𝐵_{2} \end{matrix}) \\ = (\begin{matrix} 𝐴_{1} 𝐵_{1} & 0 \\ 0 & 𝐴_{2} 𝐵_{2} \end{matrix}), \end{matrix}

and for block upper triangular matrices

\begin{matrix} (\begin{matrix} 𝐴_{1} & 𝑋 \\ 0 & 𝐴_{2} \end{matrix}) (\begin{matrix} 𝐵_{1} & 𝑌 \\ 0 & 𝐵_{2} \end{matrix}) \\ = (\begin{matrix} 𝐴_{1} 𝐵_{1} & 𝐴_{1} 𝑌 + 𝑋 𝐵_{2} \\ 0 & 𝐴_{2} 𝐵_{2} \end{matrix}) . \end{matrix}

So block diagonal matrices multiply block by block, and in particular ${diag (𝐴_{1}, 𝐴_{2})}^{𝑘} =$ $diag (𝐴_{1}^{𝑘}, 𝐴_{2}^{𝑘})$ , where $diag (𝐴_{1}, 𝐴_{2})$ denotes the block diagonal matrix.

Technique 2.4.35 (Block decomposition). Split matrices into blocks that match the structure of the problem, and compute with the blocks as if they were entries (Theorem 2.4.34). Typical splittings: off a single first row and column, to set up an induction on the size; along a basis that is split into two parts, for example a basis of a subspace extended to a basis of the whole space; or around a block of zeros or a copy of $𝐼$ .

Reach for it when a matrix has large zero or identity blocks, when an argument should reduce from size $𝑛$ to size $𝑛 - 1$ , or when a statement concerns a map that preserves a subspace. Two checks: the partitions must match, and products of blocks must keep their order. The canonical example is Proposition 2.4.36. Later it computes determinants of block triangular matrices (Section 5.4), compares $𝐴 𝐵$ with $𝐵 𝐴$ (Section 7.3), and organizes the generalized eigenspace decomposition and the Jordan form (Section 10.2, Section 10.3).

Used in 27 places and 6 practice exercises

Proposition 2.4.36, Exercise 2.4.37, Exercise 2.4.52, Exercise 2.4.55, Exercise 2.5.40, Exercise 2.8.9, Problem 2.13, Problem 2.16, Theorem 3.5.27, Exercise 3.5.46, Problem 3.4, Problem 3.14, Exercise 4.5.53, Theorem 4.7.42, Lemma 4.8.2, Exercise 4.8.13, Problem 4.12, Theorem 5.4.26, Corollary 5.4.27, Exercise 5.4.43, Exercise 5.5.47, Exercise 5.6.14, Exercise 6.3.63, Proposition 7.3.22, Problem 7.2, Problem 7.6, Theorem 8.3.23; 6 practice exercises.

Recall from Exercise 2.3.38 that $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is upper triangular if $𝑎_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ .

Proposition 2.4.36 (Products of upper triangular matrices). If

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

are upper triangular, then so is

𝐴 𝐵

, and its diagonal entries are

{(𝐴 𝐵)}_{𝑖 𝑖} =

𝑎_{𝑖 𝑖} 𝑏_{𝑖 𝑖}

Intuition. There are two natural strategies. The entry formula

{(𝐴 𝐵)}_{𝑖 𝑗} =

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

suggests looking at which terms can be nonzero. Alternatively, an upper triangular matrix of size

𝑛

is a

1 \times 1

corner, a row, a zero column, and an upper triangular matrix of size

𝑛 - 1

. That suggests block multiplication and induction on

𝑛

. The second strategy is longer here, but it is the template for every later induction on the size of a triangular matrix (Section 5.3, Section 7.5).

Proof (by blocks, induction on $𝑛$ ).standard

Uses. Theorem 2.4.34 (Block multiplication), Definition 2.4.33 (Block matrix)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Partition with row and column sizes

1, 𝑛 - 1

. What do the blocks of an upper triangular matrix look like?

Hint 2. Write

𝐴 =

(\begin{matrix} 𝑎_{11} & 𝐚^{𝖳} \\ 𝟎 & 𝐴^{'} \end{matrix})

and similarly for

𝐵

, with

𝐴^{'}

and

𝐵^{'}

upper triangular of size

𝑛 - 1

. Multiply by blocks and apply the induction hypothesis to

𝐴^{'} 𝐵^{'}

Sketch. Induct on

𝑛

;

𝑛 = 1

is clear. Split off the first row and column:

𝐴 =

(\begin{matrix} 𝑎_{11} & 𝐚^{𝖳} \\ 𝟎 & 𝐴^{'} \end{matrix})

and

𝐵 =

(\begin{matrix} 𝑏_{11} & 𝐛^{𝖳} \\ 𝟎 & 𝐵^{'} \end{matrix})

with

𝐴^{'}, 𝐵^{'}

upper triangular. By block multiplication,

𝐴 𝐵

has corner

𝑎_{11} 𝑏_{11}

, a zero column below it, and lower right block

𝐴^{'} 𝐵^{'}

, which is upper triangular with diagonal entries

𝑎_{𝑖 𝑖} 𝑏_{𝑖 𝑖}

(

𝑖 \geq 2

) by induction.

We induct on $𝑛$ . For $𝑛 = 1$ every matrix is upper triangular and ${(𝐴 𝐵)}_{11} = 𝑎_{11} 𝑏_{11}$ .

Let $𝑛 \geq 2$ and assume the claim for size $𝑛 - 1$ . Partition $𝐴$ and $𝐵$ with row sizes and column sizes $1, 𝑛 - 1$ . Since $𝐴$ is upper triangular, its lower left block is the zero column $𝟎 \in 𝐹^{𝑛 - 1}$ , and its lower right block $𝐴^{'}$ , which has entries $𝑎_{𝑖 𝑗}$ with $𝑖, 𝑗 \geq 2$ , is upper triangular. So

𝐴 = (\begin{matrix} 𝑎_{11} & 𝐚^{𝖳} \\ 𝟎 & 𝐴^{'} \end{matrix}), 𝐵 = (\begin{matrix} 𝑏_{11} & 𝐛^{𝖳} \\ 𝟎 & 𝐵^{'} \end{matrix}),

for some $𝐚, 𝐛 \in 𝐹^{𝑛 - 1}$ and upper triangular $𝐴^{'},$ $𝐵^{'} \in$ $𝐹^{(𝑛 - 1) \times (𝑛 - 1)}$ . By Theorem 2.4.34, the blocks of $𝐴 𝐵$ are

\begin{aligned} 𝑎_{11} 𝑏_{11} + 𝐚^{𝖳} 𝟎 & = 𝑎_{11} 𝑏_{11}, & 𝑎_{11} 𝐛^{𝖳} + 𝐚^{𝖳} 𝐵^{'}, \\ 𝟎 𝑏_{11} + 𝐴^{'} 𝟎 & = 𝟎, & 𝟎 𝐛^{𝖳} + 𝐴^{'} 𝐵^{'} = 𝐴^{'} 𝐵^{'}, \end{aligned}

that is,

𝐴 𝐵 = (\begin{matrix} 𝑎_{11} 𝑏_{11} & 𝑎_{11} 𝐛^{𝖳} + 𝐚^{𝖳} 𝐵^{'} \\ 𝟎 & 𝐴^{'} 𝐵^{'} \end{matrix}) .

By the induction hypothesis, $𝐴^{'} 𝐵^{'}$ is upper triangular with diagonal entries $𝑎_{𝑖 𝑖} 𝑏_{𝑖 𝑖}$ for $𝑖 = 2, \dots, 𝑛$ . So every entry of $𝐴 𝐵$ below the diagonal is either in the zero column or below the diagonal of $𝐴^{'} 𝐵^{'}$ , hence zero, and the diagonal entries of $𝐴 𝐵$ are $𝑎_{11} 𝑏_{11}$ and those of $𝐴^{'} 𝐵^{'}$ . □

Proof (entry by entry).routine

Uses. Proposition 2.4.8 (Four views of the product)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. In

{(𝐴 𝐵)}_{𝑖 𝑗} =

\sum_{𝑘} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

, when can the term

𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

be nonzero?

Hint 2. It needs

𝑖 \leq 𝑘

and

𝑘 \leq 𝑗

Sketch.

𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗} \neq 0

forces

𝑖 \leq 𝑘 \leq 𝑗

. If

𝑖 > 𝑗

there is no such

𝑘

, and if

𝑖 = 𝑗

only

𝑘 = 𝑖

remains.

{(𝐴 𝐵)}_{𝑖 𝑗} =

\sum_{𝑘 = 1}^{𝑛} 𝑎_{𝑖 𝑘} 𝑏_{𝑘 𝑗}

, the factor

𝑎_{𝑖 𝑘}

is zero unless

𝑖 \leq 𝑘

, and

𝑏_{𝑘 𝑗}

is zero unless

𝑘 \leq 𝑗

. So only terms with

𝑖 \leq 𝑘 \leq 𝑗

can be nonzero. If

𝑖 > 𝑗

there are none, and

{(𝐴 𝐵)}_{𝑖 𝑗} = 0

. If

𝑖 = 𝑗

, the only such term is

𝑘 = 𝑖

, so

{(𝐴 𝐵)}_{𝑖 𝑖} =

𝑎_{𝑖 𝑖} 𝑏_{𝑖 𝑖}

. □

A third proof translates to maps: by Exercise 2.3.38, ${[𝑇]}_{ℬ︀ ℬ︀}$ is upper triangular exactly when $𝑇$ maps each $span (𝐯_{1}, \dots, 𝐯_{𝑘})$ into itself, and a composite of two maps with this property has it too. That proof is the one that generalizes to triangularization in Section 7.5.

Exercise 2.4.37.routine Let

𝑋 \in 𝐹^{𝑝 \times 𝑞}

, and let

𝑀 = (\begin{matrix} 𝐼_{𝑝} & 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix})

. Show that

𝑀^{𝑘} =

(\begin{matrix} 𝐼_{𝑝} & 𝑘 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix})

for every

𝑘 \geq 1

, where

𝑘 𝑋 = 𝑋 + \dots + 𝑋

(

𝑘

terms), and that

(\begin{matrix} 𝐼_{𝑝} & 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix}) (\begin{matrix} 𝐼_{𝑝} & - 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix}) =

𝐼_{𝑝 + 𝑞}

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Proposition 2.4.14 (Algebra of matrices)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Multiply with Theorem 2.4.34, using sizes

𝑝, 𝑞

for rows and columns of both factors.

Hint 2. Induct on

𝑘

𝑀^{𝑘 + 1} = 𝑀^{𝑘} 𝑀

Sketch.

(\begin{matrix} 𝐼 & 𝑌 \\ 0 & 𝐼 \end{matrix}) (\begin{matrix} 𝐼 & 𝑍 \\ 0 & 𝐼 \end{matrix}) =

(\begin{matrix} 𝐼 & 𝑍 + 𝑌 \\ 0 & 𝐼 \end{matrix})

by block multiplication. Induction gives

𝑀^{𝑘} = (\begin{matrix} 𝐼 & 𝑘 𝑋 \\ 0 & 𝐼 \end{matrix})

, and

𝑌 = 𝑋

𝑍 = - 𝑋

gives

𝐼

Let $𝑌, 𝑍 \in 𝐹^{𝑝 \times 𝑞}$ , and partition both factors below with sizes $𝑝, 𝑞$ . By Theorem 2.4.34 and Proposition 2.4.14(b), the blocks of the product are $𝐼_{𝑝} 𝐼_{𝑝} + 𝑌 0 = 𝐼_{𝑝}$ , $𝐼_{𝑝} 𝑍 +$ $𝑌 𝐼_{𝑞} =$ $𝑍 +$ $𝑌$ , $0 𝐼_{𝑝} + 𝐼_{𝑞} 0 = 0$ , and $0 𝑍 + 𝐼_{𝑞} 𝐼_{𝑞} = 𝐼_{𝑞}$ :

(\begin{matrix} 𝐼_{𝑝} & 𝑌 \\ 0 & 𝐼_{𝑞} \end{matrix}) (\begin{matrix} 𝐼_{𝑝} & 𝑍 \\ 0 & 𝐼_{𝑞} \end{matrix}) = (\begin{matrix} 𝐼_{𝑝} & 𝑍 + 𝑌 \\ 0 & 𝐼_{𝑞} \end{matrix}) .

For $𝑘 = 1$ the claim is $𝑀 = 𝑀$ . If $𝑀^{𝑘} =$ $(\begin{matrix} 𝐼_{𝑝} & 𝑘 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix})$ , then by the formula $𝑀^{𝑘 + 1} =$ $𝑀^{𝑘} 𝑀 =$ $(\begin{matrix} 𝐼_{𝑝} & 𝑋 + 𝑘 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix}) =$ $(\begin{matrix} 𝐼_{𝑝} & (𝑘 + 1) 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix})$ . Taking $𝑌 = 𝑋$ and $𝑍 = - 𝑋$ gives $(\begin{matrix} 𝐼_{𝑝} & 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix}) (\begin{matrix} 𝐼_{𝑝} & - 𝑋 \\ 0 & 𝐼_{𝑞} \end{matrix}) =$ $(\begin{matrix} 𝐼_{𝑝} & 0 \\ 0 & 𝐼_{𝑞} \end{matrix}) =$ $𝐼_{𝑝 + 𝑞}$ . In the language of maps, $𝑀$ adds $𝑋$ times the last $𝑞$ coordinates to the first $𝑝$ coordinates, and the second factor subtracts it again.

2.4.9Counting walks Beyond 21-242

Applications to graphs are not part of 21-242.

Powers of a matrix count paths. This is the simplest instance of a theme that runs through Markov chains (Section 11.1) and spectral graph theory (Section 16.5). (Another application of the matrix product, homogeneous coordinates, which turn translations of $𝐹^{𝑛}$ into matrix products, is in Section 4.7.)

Definition 2.4.38 (Adjacency matrix). A directed graph

𝐺

on the vertices

1, \dots, 𝑛

is a set of ordered pairs

(𝑖, 𝑗)

of vertices, called edges. A walk of length $𝑘$ from

𝑖

𝑗

is a sequence of vertices

𝑖 =

𝑣_{0},

𝑣_{1},

\dots,

𝑣_{𝑘} =

𝑗

such that

(𝑣_{𝑡 - 1}, 𝑣_{𝑡})

is an edge for each

𝑡 = 1, \dots, 𝑘

. The adjacency matrix of

𝐺

is the

𝑛 \times 𝑛

matrix

𝐴

over

ℚ

with

𝑎_{𝑖 𝑗} = 1

(𝑖, 𝑗)

is an edge and

𝑎_{𝑖 𝑗} = 0

otherwise. An undirected graph is a directed graph in which

(𝑗, 𝑖)

is an edge whenever

(𝑖, 𝑗)

is; its adjacency matrix is symmetric.

Proposition 2.4.39 (Powers count walks). Let

𝐴

be the adjacency matrix of a directed graph

𝐺

1, \dots, 𝑛

. For every

𝑘 \geq 0

{(𝐴^{𝑘})}_{𝑖 𝑗}

is the number of walks of length

𝑘

from

𝑖

𝑗

. In particular,

tr (𝐴^{𝑘})

is the number of closed walks of length

𝑘

, counted with their starting vertex.

Proof.standard

Uses. Proposition 2.4.8 (Four views of the product), Definition 2.4.38 (Adjacency matrix), Notation 2.4.16 (Powers of a matrix)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Induct on

𝑘

. For

𝑘 = 0

𝐴^{0} = 𝐼_{𝑛}

, and a walk of length

0

from

𝑖

𝑗

exists only when

𝑖 = 𝑗

Hint 2. A walk of length

𝑘 + 1

from

𝑖

𝑗

is a walk of length

𝑘

from

𝑖

to some vertex

𝑙

, followed by the edge

(𝑙, 𝑗)

. Sort the walks by

𝑙

, and compare with

{(𝐴^{𝑘 + 1})}_{𝑖 𝑗} =

\sum_{𝑙} {(𝐴^{𝑘})}_{𝑖 𝑙} 𝑎_{𝑙 𝑗}

Sketch. Induct on

𝑘

. Grouping the walks of length

𝑘 + 1

from

𝑖

𝑗

by their next-to-last vertex

𝑙

, there are (walks of length

𝑘

from

𝑖

𝑙

)

\times 𝑎_{𝑙 𝑗}

of them for each

𝑙

, and the sum over

𝑙

\sum_{𝑙} {(𝐴^{𝑘})}_{𝑖 𝑙} 𝑎_{𝑙 𝑗} =

{(𝐴^{𝑘 + 1})}_{𝑖 𝑗}

We induct on $𝑘$ . For $𝑘 = 0$ , ${(𝐴^{0})}_{𝑖 𝑗} = 𝛿_{𝑖 𝑗}$ , and there is exactly one walk of length $0$ from $𝑖$ to $𝑖$ (the sequence $𝑣_{0} = 𝑖$ ) and none from $𝑖$ to $𝑗 \neq 𝑖$ .

Suppose the claim holds for $𝑘$ . A walk $𝑣_{0}, \dots, 𝑣_{𝑘 + 1}$ of length $𝑘 + 1$ from $𝑖$ to $𝑗$ consists of the walk $𝑣_{0}, \dots, 𝑣_{𝑘}$ of length $𝑘$ from $𝑖$ to $𝑙 = 𝑣_{𝑘}$ , followed by the edge $(𝑙, 𝑗)$ ; conversely, any walk of length $𝑘$ from $𝑖$ to $𝑙$ can be extended in this way exactly when $(𝑙, 𝑗)$ is an edge. So the number of walks of length $𝑘 + 1$ from $𝑖$ to $𝑗$ whose next-to-last vertex is $𝑙$ equals the number of walks of length $𝑘$ from $𝑖$ to $𝑙$ times $𝑎_{𝑙 𝑗}$ , which is ${(𝐴^{𝑘})}_{𝑖 𝑙} 𝑎_{𝑙 𝑗}$ by the induction hypothesis. Summing over $𝑙$ , the number of walks of length $𝑘 + 1$ from $𝑖$ to $𝑗$ is

\sum_{𝑙 = 1}^{𝑛} {(𝐴^{𝑘})}_{𝑖 𝑙} 𝑎_{𝑙 𝑗} = {(𝐴^{𝑘 + 1})}_{𝑖 𝑗} .

The last claim follows by adding the diagonal entries. □

Example 2.4.40 (Walks in a small graph).

Figure 2.4.2. The undirected graph with edges

{1, 2}

{2, 3}

{3, 4}

{4, 1}

, and

{1, 3}

The graph of Figure 2.4.2 has

\begin{matrix} 𝐴 = (\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix}), \\ 𝐴^{2} = (\begin{matrix} 3 & 1 & 2 & 1 \\ 1 & 2 & 1 & 2 \\ 2 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \end{matrix}) . \end{matrix}

For instance ${(𝐴^{2})}_{13} = 2$ counts the walks $1, 2, 3$ and $1, 4, 3$ . In an undirected graph, ${(𝐴^{2})}_{𝑖 𝑖}$ is the number of neighbours of $𝑖$ , and ${(𝐴^{2})}_{𝑖 𝑗}$ is the number of common neighbours of $𝑖$ and $𝑗$ . The diagonal entries of $𝐴^{3}$ are $4, 2, 4, 2$ , so $tr (𝐴^{3}) = 12$ . A closed walk of length $3$ in a graph without loops goes around a triangle, and each triangle gives $6$ closed walks ( $3$ starting vertices, $2$ directions). So the graph has $12 / 6 = 2$ triangles, namely ${1, 2, 3}$ and ${1, 3, 4}$ .

Exercises

Exercise 2.4.41.routine Let $𝐷 : {𝐹 [𝑥]}_{\leq 3} \to$ ${𝐹 [𝑥]}_{\leq 2}$ be differentiation and $𝑀 : {𝐹 [𝑥]}_{\leq 2} \to$ ${𝐹 [𝑥]}_{\leq 3}$ multiplication by $𝑥$ , with the bases ${ℬ︀}_{2} = 1, 𝑥, 𝑥^{2}$ and ${ℬ︀}_{3} = 1, 𝑥, 𝑥^{2}, 𝑥^{3}$ .

(a)Find ${[𝐷]}_{{ℬ︀}_{2} {ℬ︀}_{3}}$ and ${[𝑀]}_{{ℬ︀}_{3} {ℬ︀}_{2}}$ .
(b)Compute ${[𝐷 𝑀]}_{{ℬ︀}_{2} {ℬ︀}_{2}}$ and ${[𝑀 𝐷]}_{{ℬ︀}_{3} {ℬ︀}_{3}}$ as products of matrices, and check the answers against the formulas $𝐷 𝑀 (𝑝) = {(𝑥 𝑝)}^{'}$ and $𝑀 𝐷 (𝑝) = 𝑥 𝑝^{'}$ .
(c)Compare $tr (𝐷 𝑀)$ and $tr (𝑀 𝐷)$ , meaning the traces of these two matrices.

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.4.2 (The matrix of a composite), Proposition 2.4.28 (Cyclicity of the trace), Example 2.1.9 (Maps of polynomials)

Hint 1. The columns of

{[𝐷]}_{{ℬ︀}_{2} {ℬ︀}_{3}}

are the coordinates of

𝐷 (1),

𝐷 (𝑥),

𝐷 (𝑥^{2}),

𝐷 (𝑥^{3})

{ℬ︀}_{2}

; the columns of

{[𝑀]}_{{ℬ︀}_{3} {ℬ︀}_{2}}

are those of

𝑥, 𝑥^{2}, 𝑥^{3}

{ℬ︀}_{3}

Hint 2. By Theorem 2.4.2,

[𝐷 𝑀] = [𝐷] [𝑀]

and

[𝑀 𝐷] = [𝑀] [𝐷]

. Compute column by column. Then compute

{(𝑥 \cdot 𝑥^{𝑘})}^{'}

and

𝑥 {(𝑥^{𝑘})}^{'}

directly.

Sketch.

[𝐷] =

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

and

[𝑀]

has columns

𝐞_{2}, 𝐞_{3}, 𝐞_{4}

. Then

[𝐷 𝑀] =

diag (1, 2, 3)

and

[𝑀 𝐷] =

diag (0, 1, 2, 3)

, matching

{(𝑥^{𝑘 + 1})}^{'} =

(𝑘 + 1) 𝑥^{𝑘}

and

𝑥 {(𝑥^{𝑘})}^{'} = 𝑘 𝑥^{𝑘}

. Both traces are

6

, as Proposition 2.4.28 predicts for a

3 \times 4

and a

4 \times 3

matrix.

(a) $𝐷 (1) = 𝟎$ , $𝐷 (𝑥) = 1$ , $𝐷 (𝑥^{2}) = 2 𝑥$ , and $𝐷 (𝑥^{3}) = 3 𝑥^{2}$ , and $𝑀 (1) = 𝑥$ , $𝑀 (𝑥) = 𝑥^{2}$ , $𝑀 (𝑥^{2}) = 𝑥^{3}$ , so

\begin{matrix} {[𝐷]}_{{ℬ︀}_{2} {ℬ︀}_{3}} = (\begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{matrix}), \\ {[𝑀]}_{{ℬ︀}_{3} {ℬ︀}_{2}} = (\begin{matrix} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) . \end{matrix}

(b) By Theorem 2.4.2, ${[𝐷 𝑀]}_{{ℬ︀}_{2} {ℬ︀}_{2}} =$ ${[𝐷]}_{{ℬ︀}_{2} {ℬ︀}_{3}} {[𝑀]}_{{ℬ︀}_{3} {ℬ︀}_{2}}$ . Its columns are $[𝐷]$ times the columns $𝐞_{2}, 𝐞_{3}, 𝐞_{4}$ of $[𝑀]$ , which are columns $2, 3, 4$ of $[𝐷]$ :

{[𝐷 𝑀]}_{{ℬ︀}_{2} {ℬ︀}_{2}} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{matrix}) .

Similarly ${[𝑀 𝐷]}_{{ℬ︀}_{3} {ℬ︀}_{3}} =$ ${[𝑀]}_{{ℬ︀}_{3} {ℬ︀}_{2}} {[𝐷]}_{{ℬ︀}_{2} {ℬ︀}_{3}}$ has columns $[𝑀] 𝟎 = 𝟎$ , $[𝑀] (1, 0, 0) = 𝐞_{2}$ , $[𝑀] (0, 2, 0) = 2 𝐞_{3}$ , and $[𝑀] (0, 0, 3) = 3 𝐞_{4}$ :

{[𝑀 𝐷]}_{{ℬ︀}_{3} {ℬ︀}_{3}} = (\begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{matrix}) .

Directly, $𝐷 𝑀 (𝑥^{𝑘}) =$ ${(𝑥^{𝑘 + 1})}^{'} =$ $(𝑘 + 1) 𝑥^{𝑘}$ for $𝑘 = 0, 1, 2$ , and $𝑀 𝐷 (𝑥^{𝑘}) =$ $𝑥 \cdot$ $𝑘 𝑥^{𝑘 - 1} =$ $𝑘 𝑥^{𝑘}$ for $𝑘 = 0, 1, 2, 3$ , which are the diagonal entries found above.

(c) Both traces are $1 + 2 + 3 = 6 = 0 + 1 + 2 + 3$ , although the matrices have different sizes. This is Proposition 2.4.28 for the $3 \times 4$ matrix $[𝐷]$ and the $4 \times 3$ matrix $[𝑀]$ . Note also that $[𝐷 𝑀] - [𝑀 𝐷]$ is not defined, since the sizes differ; on all of $𝐹 [𝑥]$ , $𝐷 𝑀 - 𝑀 𝐷 = id$ (Exercise 2.4.51).

Exercise 2.4.42.standard Let $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛}) \in$ $𝐹^{𝑛 \times 𝑛}$ .

(a)Show that ${(𝐷 𝑋)}_{𝑖 𝑗} =$ $𝑑_{𝑖} 𝑥_{𝑖 𝑗}$ and ${(𝑋 𝐷)}_{𝑖 𝑗} =$ $𝑥_{𝑖 𝑗} 𝑑_{𝑗}$ for $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ .
(b)Suppose $𝑑_{1}, \dots, 𝑑_{𝑛}$ are distinct. Show that $𝑋$ commutes with $𝐷$ if and only if $𝑋$ is diagonal.
(c)Find all $𝑋 \in 𝐹^{3 \times 3}$ that commute with $diag (1, 1, 0)$ .

Solution.

Uses. Example 2.4.10 (Diagonal matrices), Proposition 2.4.8 (Four views of the product), Proposition 1.1.17 (No zero divisors)

Hint 1. (a) is the row view and the column view of Example 2.4.10, read entry by entry.

Hint 2.

𝐷 𝑋 = 𝑋 𝐷

means

(𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} =

0

for all

𝑖, 𝑗

. When does this force

𝑥_{𝑖 𝑗} = 0

Sketch. (a)

𝐷 𝑋

scales row

𝑖

𝑑_{𝑖}

;

𝑋 𝐷

scales column

𝑗

𝑑_{𝑗}

. (b)

𝑋 𝐷 = 𝐷 𝑋

iff

(𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} =

0

for all

𝑖, 𝑗

; with distinct

𝑑

’s this forces

𝑥_{𝑖 𝑗} = 0

for

𝑖 \neq 𝑗

. (c) The condition kills exactly the entries

𝑥_{𝑖 𝑗}

with

𝑑_{𝑖} \neq 𝑑_{𝑗}

, so

𝑋

is block diagonal with blocks of sizes

2, 1

(a) By Example 2.4.10, row $𝑖$ of $𝐷 𝑋$ is $𝑑_{𝑖} 𝑋_{𝑖, \cdot}$ and column $𝑗$ of $𝑋 𝐷$ is $𝑑_{𝑗} 𝑋_{\cdot, 𝑗}$ . Reading off the $(𝑖, 𝑗)$ entries gives ${(𝐷 𝑋)}_{𝑖 𝑗} =$ $𝑑_{𝑖} 𝑥_{𝑖 𝑗}$ and ${(𝑋 𝐷)}_{𝑖 𝑗} =$ $𝑥_{𝑖 𝑗} 𝑑_{𝑗}$ .

(b) By (a), $𝐷 𝑋 = 𝑋 𝐷$ if and only if $𝑑_{𝑖} 𝑥_{𝑖 𝑗} =$ $𝑥_{𝑖 𝑗} 𝑑_{𝑗}$ , that is, $(𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} =$ $0$ , for all $𝑖, 𝑗$ . For $𝑖 = 𝑗$ this always holds. For $𝑖 \neq 𝑗$ , $𝑑_{𝑖} - 𝑑_{𝑗} \neq 0$ , so it holds if and only if $𝑥_{𝑖 𝑗} = 0$ (Proposition 1.1.17). So $𝑋$ commutes with $𝐷$ exactly when all its off-diagonal entries vanish.

(c) Here $𝑑_{1} = 𝑑_{2} = 1$ and $𝑑_{3} = 0$ . The condition $(𝑑_{𝑖} - 𝑑_{𝑗}) 𝑥_{𝑖 𝑗} =$ $0$ is automatic when $𝑑_{𝑖} = 𝑑_{𝑗}$ , that is, for $𝑖, 𝑗 \in {1, 2}$ and for $𝑖 = 𝑗 = 3$ , and it forces $𝑥_{𝑖 𝑗} = 0$ when exactly one of $𝑖, 𝑗$ equals $3$ , since then $𝑑_{𝑖} - 𝑑_{𝑗} = \pm 1 \neq 0$ . So the matrices commuting with $diag (1, 1, 0)$ are

𝑋 = (\begin{matrix} 𝑥_{11} & 𝑥_{12} & 0 \\ 𝑥_{21} & 𝑥_{22} & 0 \\ 0 & 0 & 𝑥_{33} \end{matrix}),

with the five remaining entries arbitrary. These are the block diagonal matrices with blocks of sizes $2$ and $1$ , matching the blocks on which $diag (1, 1, 0)$ is a scalar matrix.

Exercise 2.4.43.standard Let

𝑛 \geq 2

. Show that

𝐴 \in 𝐹^{𝑛 \times 𝑛}

commutes with every upper triangular matrix in

𝐹^{𝑛 \times 𝑛}

if and only if

𝐴 = 𝑐 𝐼_{𝑛}

for some

𝑐 \in 𝐹

Solution.

Uses. Lemma 2.4.24 (Matrix units), Proposition 2.4.14 (Algebra of matrices)

Hint 1. Use only a few upper triangular matrices: the matrix units

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

with

𝑖 \leq 𝑗

Hint 2. Commuting with

𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}

says

𝐴_{\cdot, 𝑖} 𝐞_{𝑖}^{𝖳} =

𝐞_{𝑖} 𝐴_{𝑖, \cdot}

. The left side is zero outside column

𝑖

, the right side zero outside row

𝑖

. What does that force?

Hint 3. Once

𝐴

is diagonal, compare

𝐴 (𝐞_{1} 𝐞_{𝑗}^{𝖳})

with

(𝐞_{1} 𝐞_{𝑗}^{𝖳}) 𝐴

Sketch. Commuting with

𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}

gives

𝐴_{\cdot, 𝑖} 𝐞_{𝑖}^{𝖳} =

𝐞_{𝑖} 𝐴_{𝑖, \cdot}

; comparing entries outside position

(𝑖, 𝑖)

, column

𝑖

and row

𝑖

𝐴

vanish off the diagonal, so

𝐴

is diagonal. Then

𝐴 𝐞_{1} 𝐞_{𝑗}^{𝖳} =

𝑎_{11} 𝐞_{1} 𝐞_{𝑗}^{𝖳}

and

𝐞_{1} 𝐞_{𝑗}^{𝖳} 𝐴 =

𝑎_{𝑗 𝑗} 𝐞_{1} 𝐞_{𝑗}^{𝖳}

give

𝑎_{𝑗 𝑗} = 𝑎_{11}

If. $𝑐 𝐼_{𝑛}$ commutes with every matrix, since $(𝑐 𝐼_{𝑛}) 𝑋 =$ $𝑐 𝑋 =$ $𝑋 (𝑐 𝐼_{𝑛})$ by Proposition 2.4.14.

Only if. Suppose $𝐴$ commutes with every upper triangular matrix. Fix $𝑖$ . The matrix unit $𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}$ is upper triangular, and by associativity and Lemma 2.4.24(b),

𝐴 (𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) = 𝐴_{\cdot, 𝑖} 𝐞_{𝑖}^{𝖳}, (𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) 𝐴 = 𝐞_{𝑖} 𝐴_{𝑖, \cdot} .

The first matrix has $(𝑘, 𝑙)$ entry $𝑎_{𝑘 𝑖} 𝛿_{𝑙 𝑖}$ : it is zero outside column $𝑖$ , where it equals column $𝑖$ of $𝐴$ . The second has $(𝑘, 𝑙)$ entry $𝛿_{𝑘 𝑖} 𝑎_{𝑖 𝑙}$ : it is zero outside row $𝑖$ , where it equals row $𝑖$ of $𝐴$ . Comparing the entries in positions $(𝑘, 𝑖)$ with $𝑘 \neq 𝑖$ gives $𝑎_{𝑘 𝑖} = 0$ , and comparing those in positions $(𝑖, 𝑙)$ with $𝑙 \neq 𝑖$ gives $𝑎_{𝑖 𝑙} = 0$ . As $𝑖$ was arbitrary, $𝐴$ is diagonal, so $𝐴 𝐞_{𝑗} = 𝑎_{𝑗 𝑗} 𝐞_{𝑗}$ and $𝐞_{𝑗}^{𝖳} 𝐴 =$ $𝑎_{𝑗 𝑗} 𝐞_{𝑗}^{𝖳}$ for every $𝑗$ .

Now let $2 \leq 𝑗 \leq 𝑛$ . The matrix unit $𝐞_{1} 𝐞_{𝑗}^{𝖳}$ is upper triangular, and

\begin{aligned} 𝐴 (𝐞_{1} 𝐞_{𝑗}^{𝖳}) & = (𝐴 𝐞_{1}) 𝐞_{𝑗}^{𝖳} = 𝑎_{11} 𝐞_{1} 𝐞_{𝑗}^{𝖳}, \\ (𝐞_{1} 𝐞_{𝑗}^{𝖳}) 𝐴 & = 𝐞_{1} (𝐞_{𝑗}^{𝖳} 𝐴) = 𝑎_{𝑗 𝑗} 𝐞_{1} 𝐞_{𝑗}^{𝖳} . \end{aligned}

These are equal, and $𝐞_{1} 𝐞_{𝑗}^{𝖳} \neq 0$ , so $𝑎_{𝑗 𝑗} = 𝑎_{11}$ . Hence $𝐴 = 𝑎_{11} 𝐼_{𝑛}$ .

Exercise 2.4.44.standard Prove or disprove each statement about matrices in $𝐹^{𝑛 \times 𝑛}$ , $𝑛 \geq 2$ .

(a)If $𝐴^{2} = 𝐼_{𝑛}$ , then $𝐴 = 𝐼_{𝑛}$ or $𝐴 = - 𝐼_{𝑛}$ .
(b)If $𝐴$ and $𝐵$ are symmetric, then $𝐴 𝐵$ is symmetric.
(c) ${(𝐴 𝐵)}^{2} = 𝐴^{2} 𝐵^{2}$ .
(d)If $𝐹 = ℝ$ and $𝐴^{𝖳} 𝐴 = 0$ , then $𝐴 = 0$ . What if $𝐹 = ℂ$ or $𝐹 = 𝔽_{2}$ ?
(e)If $𝐴$ is upper triangular and $𝐴^{2} = 0$ , then every diagonal entry of $𝐴$ is $0$ .

Solution.

Uses. Proposition 2.4.8 (Four views of the product), Definition 2.4.21 (Transpose), Exercise 2.4.25, Proposition 2.4.36 (Products of upper triangular matrices), Example 2.4.18 ( $𝐴 𝐵 \neq 𝐵 𝐴$ ), Proposition 1.1.17 (No zero divisors)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. (a), (b), and (c) are false; look among

2 \times 2

matrices with entries

0

and

1

. For (a), think of a reflection.

Hint 2. (d) Compute the diagonal entries of

𝐴^{𝖳} 𝐴

. (e) Use Proposition 2.4.36.

Sketch. (a) False:

{(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})}^{2} = 𝐼_{2}

. (b) False:

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

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

. (c) False: with

𝐴 = 𝐞_{1} 𝐞_{2}^{𝖳}

𝐵 = 𝐞_{2} 𝐞_{1}^{𝖳}

{(𝐴 𝐵)}^{2} = 𝐞_{1} 𝐞_{1}^{𝖳}

but

𝐴^{2} = 0

. (d) True over

ℝ

{(𝐴^{𝖳} 𝐴)}_{𝑗 𝑗} =

\sum_{𝑖} 𝑎_{𝑖 𝑗}^{2}

. False over

ℂ

and

𝔽_{2}

𝐴 = (\begin{matrix} 1 & 0 \\ 𝑖 & 0 \end{matrix})

, resp.

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

. (e) True:

{(𝐴^{2})}_{𝑖 𝑖} = 𝑎_{𝑖 𝑖}^{2}

We give the counterexamples for $𝑛 = 2$ . For $𝑛 > 2$ , those in (b), (c), and (d) can be placed in the top left corner of an $𝑛 \times 𝑛$ zero matrix (Theorem 2.4.34), and the one in (a) in the top left corner of $𝐼_{𝑛}$ .

(a) False. $𝐴 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ swaps $𝐞_{1}$ and $𝐞_{2}$ , so $𝐴^{2} = 𝐼_{2}$ , but $𝐴 \neq \pm 𝐼_{2}$ (in $𝔽_{2}$ , where $- 𝐼_{2} = 𝐼_{2}$ , still $𝐴 \neq 𝐼_{2}$ ). Geometrically, $𝐴$ is the reflection across the line $𝑦 = 𝑥$ . For $𝑛 > 2$ , the matrix that swaps $𝐞_{1}$ and $𝐞_{2}$ and fixes the other $𝐞_{𝑗}$ works.

(b) False. $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ are symmetric, but $𝐴 𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ is not. By Exercise 2.4.25, $𝐴 𝐵$ is symmetric exactly when $𝐴 𝐵 = 𝐵 𝐴$ .

(c) False. With $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ (Example 2.4.18), $𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , so ${(𝐴 𝐵)}^{2} = 𝐴 𝐵 \neq 0$ , while $𝐴^{2} = 0$ gives $𝐴^{2} 𝐵^{2} = 0$ . In general ${(𝐴 𝐵)}^{2} = 𝐴 𝐵 𝐴 𝐵$ , and this equals $𝐴 𝐴 𝐵 𝐵$ when $𝐴 𝐵 = 𝐵 𝐴$ .

(d) True over $ℝ$ . By Proposition 2.4.8(a) and Definition 2.4.21, the $(𝑗, 𝑗)$ entry of $𝐴^{𝖳} 𝐴$ is $\sum_{𝑖} {(𝐴^{𝖳})}_{𝑗 𝑖} 𝑎_{𝑖 𝑗} =$ $\sum_{𝑖} 𝑎_{𝑖 𝑗}^{2}$ . If $𝐴^{𝖳} 𝐴 = 0$ , then for each $𝑗$ this sum of squares of real numbers is $0$ , so every $𝑎_{𝑖 𝑗} = 0$ .

Over $ℂ$ it is false: for $𝐴 = (\begin{matrix} 1 & 0 \\ 𝑖 & 0 \end{matrix})$ , $𝐴^{𝖳} 𝐴 =$ $(\begin{matrix} 1 & 𝑖 \\ 0 & 0 \end{matrix}) (\begin{matrix} 1 & 0 \\ 𝑖 & 0 \end{matrix}) =$ $(\begin{matrix} 1 + 𝑖^{2} & 0 \\ 0 & 0 \end{matrix}) =$ $0$ . Over $𝔽_{2}$ , $𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 0 \end{matrix})$ gives $𝐴^{𝖳} 𝐴 = (\begin{matrix} 1 + 1 & 0 \\ 0 & 0 \end{matrix}) = 0$ . The real proof used that a sum of squares vanishes only if each term does, which fails in both fields. Over $ℂ$ the cure is to conjugate, using $𝐴^{*} 𝐴$ (Section 6.1).

(e) True. By Proposition 2.4.36, $𝐴^{2}$ is upper triangular with diagonal entries $𝑎_{𝑖 𝑖}^{2}$ . If $𝐴^{2} = 0$ , then $𝑎_{𝑖 𝑖}^{2} = 0$ , so $𝑎_{𝑖 𝑖} = 0$ by Proposition 1.1.17.

Exercise 2.4.45.standard

(a)Show that $𝐴 =$ $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) \in$ $𝐹^{2 \times 2}$ satisfies $𝐴^{2} = 0$ if and only if $𝑎 + 𝑑 = 0$ and $𝑎^{2} + 𝑏 𝑐 = 0$ .
(b)Let $𝑝$ be prime. How many $𝐴 \in 𝔽_{𝑝}^{2 \times 2}$ satisfy $𝐴^{2} = 0$ ?

Solution.

Uses. Proposition 2.4.8 (Four views of the product), Proposition 1.1.17 (No zero divisors)

Hint 1. Compute

𝐴^{2}

. Its off-diagonal entries are

𝑏 (𝑎 + 𝑑)

and

𝑐 (𝑎 + 𝑑)

Hint 2. If

𝑎 + 𝑑 \neq 0

, then

𝑏 = 𝑐 = 0

; what do the diagonal entries then force? For (b), count the pairs

(𝑏, 𝑐)

with

𝑏 𝑐 = - 𝑎^{2}

, separately for

𝑎 = 0

and

𝑎 \neq 0

Sketch.

𝐴^{2} =

(\begin{matrix} 𝑎^{2} + 𝑏 𝑐 & 𝑏 (𝑎 + 𝑑) \\ 𝑐 (𝑎 + 𝑑) & 𝑑^{2} + 𝑏 𝑐 \end{matrix})

. If

𝑎 + 𝑑 \neq 0

then

𝑏 = 𝑐 = 0

and

𝑎^{2} = 𝑑^{2} = 0

, so

𝑎 = 𝑑 = 0

, a contradiction; so

𝑑 = - 𝑎

, and then all four conditions reduce to

𝑎^{2} + 𝑏 𝑐 = 0

. (b) For

𝑎 = 0

𝑏 𝑐 = 0

has

2 𝑝 - 1

solutions. For each of the

𝑝 - 1

nonzero

𝑎

𝑏 𝑐 = - 𝑎^{2} \neq 0

has

𝑝 - 1

solutions. Total

2 𝑝 - 1 + {(𝑝 - 1)}^{2} = 𝑝^{2}

(a) By the entry formula,

𝐴^{2} = (\begin{matrix} 𝑎^{2} + 𝑏 𝑐 & 𝑏 (𝑎 + 𝑑) \\ 𝑐 (𝑎 + 𝑑) & 𝑑^{2} + 𝑏 𝑐 \end{matrix}) .

Suppose $𝐴^{2} = 0$ . If $𝑎 + 𝑑 \neq 0$ , the off-diagonal entries give $𝑏 = 𝑐 = 0$ (Proposition 1.1.17), and then the diagonal entries give $𝑎^{2} = 𝑑^{2} = 0$ , so $𝑎 = 𝑑 = 0$ , contradicting $𝑎 + 𝑑 \neq 0$ . Hence $𝑎 + 𝑑 = 0$ , and then $𝑎^{2} + 𝑏 𝑐 = 0$ is the $(1, 1)$ entry. Conversely, if $𝑑 = - 𝑎$ and $𝑎^{2} + 𝑏 𝑐 = 0$ , then the off-diagonal entries are $0$ , the $(1, 1)$ entry is $0$ , and the $(2, 2)$ entry is $𝑑^{2} +$ $𝑏 𝑐 =$ $𝑎^{2} +$ $𝑏 𝑐 =$ $0$ .

(b) By (a), such $𝐴$ correspond to triples $(𝑎, 𝑏, 𝑐) \in 𝔽_{𝑝}^{3}$ with $𝑏 𝑐 = - 𝑎^{2}$ , with $𝑑 = - 𝑎$ . If $𝑎 = 0$ , we need $𝑏 𝑐 = 0$ , that is, $𝑏 = 0$ or $𝑐 = 0$ : there are $𝑝 + 𝑝 - 1 = 2 𝑝 - 1$ such pairs. If $𝑎 \neq 0$ , then $- 𝑎^{2} \neq 0$ , so $𝑏 \neq 0$ and $𝑐 = - 𝑎^{2} 𝑏^{- 1}$ is determined by $𝑏$ : there are $𝑝 - 1$ pairs. With $𝑝 - 1$ nonzero values of $𝑎$ , the total is

(2 𝑝 - 1) + {(𝑝 - 1)}^{2} = 𝑝^{2} .

For $𝑝 = 2$ the four matrices are $0$ , $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , $(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ , and $(\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ .

Exercise 2.4.46.standard

(a)For $𝜆 \in 𝐹$ , let $𝐽 = (\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix})$ . Show that $𝐽^{𝑘} =$ $(\begin{matrix} 𝜆^{𝑘} & 𝑘 𝜆^{𝑘 - 1} \\ 0 & 𝜆^{𝑘} \end{matrix})$ for every $𝑘 \geq 1$ , where $𝑘 𝜆^{𝑘 - 1}$ means $(𝑘 * 1) 𝜆^{𝑘 - 1}$ .
(b)Deduce that ${(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})}^{𝑝} = 𝐼_{2}$ over $𝔽_{𝑝}$ .
(c)Find $𝐴 \in 𝔽_{2}^{2 \times 2}$ and $𝐴^{'} \in ℝ^{2 \times 2}$ with $𝐴^{3} = 𝐼_{2}$ and $𝐴^{' 3} = 𝐼_{2}$ , neither equal to $𝐼_{2}$ .

Solution.

Uses. Notation 2.4.16 (Powers of a matrix), Proposition 2.4.8 (Four views of the product), Theorem 2.4.2 (The matrix of a composite), Example 2.4.5 (Composites through their matrices)

Hint 1. (a) Induct on

𝑘

, computing

𝐽^{𝑘 + 1} = 𝐽^{𝑘} 𝐽

with the entry formula.

Hint 2. (b) Take

𝜆 = 1

and

𝑘 = 𝑝

. (c) Over

ℝ

, think of a rotation. Over

𝔽_{2}

, try

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

Sketch. (a)

𝐽^{𝑘} 𝐽 =

(\begin{matrix} 𝜆^{𝑘 + 1} & 𝜆^{𝑘} + 𝑘 𝜆^{𝑘} \\ 0 & 𝜆^{𝑘 + 1} \end{matrix})

. (b)

𝑝 * 1 = 0

𝔽_{𝑝}

. (c) Over

𝔽_{2}

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

and

{(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})}^{3} = 𝐼_{2}

. Over

ℝ

, the rotation by

2 𝜋 / 3

[𝑅_{2 𝜋 / 3}] =

\frac{1}{2} (\begin{matrix} - 1 & - \sqrt{3} \\ \sqrt{3} & - 1 \end{matrix})

(a) For $𝑘 = 1$ the formula reads $𝐽 = 𝐽$ , since $1 * 1 = 1$ and $𝜆^{0} = 1$ . If it holds for $𝑘$ , then

𝐽^{𝑘 + 1} = 𝐽^{𝑘} 𝐽 = (\begin{matrix} 𝜆^{𝑘} & 𝑘 𝜆^{𝑘 - 1} \\ 0 & 𝜆^{𝑘} \end{matrix}) (\begin{matrix} 𝜆 & 1 \\ 0 & 𝜆 \end{matrix}) .

By the entry formula, this product has diagonal entries $𝜆^{𝑘 + 1}$ , lower left entry $0$ , and upper right entry $𝜆^{𝑘} \cdot$ $1 +$ $𝑘 𝜆^{𝑘 - 1} \cdot$ $𝜆 =$ $(𝑘 + 1) 𝜆^{𝑘}$ , which is the formula for $𝑘 + 1$ .

(b) With $𝜆 = 1$ and $𝑘 = 𝑝$ , (a) gives ${(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})}^{𝑝} =$ $(\begin{matrix} 1 & 𝑝 * 1 \\ 0 & 1 \end{matrix}) =$ $𝐼_{2}$ , since $𝑝 * 1 = 0$ in $𝔽_{𝑝}$ . The map $(𝑥, 𝑦) \mapsto$ $(𝑥 + 𝑦, 𝑦)$ of $𝔽_{𝑝}^{2}$ adds $𝑦$ to the first coordinate, and doing so $𝑝$ times adds $𝑝 * 𝑦 = 0$ .

(c) Over $𝔽_{2}$ , let $𝐴 = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ . Then, using $1 + 1 = 0$ ,

\begin{matrix} 𝐴^{2} = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}), \\ 𝐴^{3} = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) . \end{matrix}

Over $ℝ$ , let $𝐴^{'} =$ ${[𝑅_{2 𝜋 / 3}]}_{ℰ︀ ℰ︀} =$ $\frac{1}{2} (\begin{matrix} - 1 & - \sqrt{3} \\ \sqrt{3} & - 1 \end{matrix})$ . By Theorem 2.4.2 and Example 2.4.5(b), $𝐴^{' 3} =$ $[𝑅_{2 𝜋 / 3}^{3}] =$ $[𝑅_{2 𝜋}] =$ $𝐼_{2}$ , and $𝐴^{'} \neq 𝐼_{2}$ .

Exercise 2.4.47.standard Let $𝑓_{0} = 0$ , $𝑓_{1} = 1$ , and $𝑓_{𝑘 + 1} =$ $𝑓_{𝑘} +$ $𝑓_{𝑘 - 1}$ for $𝑘 \geq 1$ (the Fibonacci numbers), and let $𝑄 = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \in ℚ^{2 \times 2}$ .

(a)Show that $𝑄^{𝑘} =$ $(\begin{matrix} 𝑓_{𝑘 + 1} & 𝑓_{𝑘} \\ 𝑓_{𝑘} & 𝑓_{𝑘 - 1} \end{matrix})$ for every $𝑘 \geq 1$ .
(b)Deduce that $𝑓_{𝑚 + 𝑛} =$ $𝑓_{𝑚 + 1} 𝑓_{𝑛} +$ $𝑓_{𝑚} 𝑓_{𝑛 - 1}$ for all $𝑚, 𝑛 \geq 1$ , and in particular $𝑓_{2 𝑛} =$ $𝑓_{𝑛} (𝑓_{𝑛 + 1} + 𝑓_{𝑛 - 1})$ .

Solution.

Uses. Notation 2.4.16 (Powers of a matrix), Proposition 2.4.8 (Four views of the product), Proposition 2.4.14 (Algebra of matrices)

Hint 1. (a) Induct on

𝑘

, with

𝑄^{𝑘 + 1} = 𝑄^{𝑘} 𝑄

Hint 2. (b) Compare the

(1, 2)

entries of

𝑄^{𝑚 + 𝑛}

and

𝑄^{𝑚} 𝑄^{𝑛}

Sketch. (a)

𝑄^{𝑘} 𝑄 =

(\begin{matrix} 𝑓_{𝑘 + 1} + 𝑓_{𝑘} & 𝑓_{𝑘 + 1} \\ 𝑓_{𝑘} + 𝑓_{𝑘 - 1} & 𝑓_{𝑘} \end{matrix})

. (b)

{(𝑄^{𝑚 + 𝑛})}_{12} =

𝑓_{𝑚 + 𝑛}

and

{(𝑄^{𝑚} 𝑄^{𝑛})}_{12} =

𝑓_{𝑚 + 1} 𝑓_{𝑛} +

𝑓_{𝑚} 𝑓_{𝑛 - 1}

. Put

𝑚 = 𝑛

(a) For $𝑘 = 1$ , $(\begin{matrix} 𝑓_{2} & 𝑓_{1} \\ 𝑓_{1} & 𝑓_{0} \end{matrix}) =$ $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) =$ $𝑄$ . If the formula holds for $𝑘$ , then

\begin{aligned} 𝑄^{𝑘 + 1} = 𝑄^{𝑘} 𝑄 & = (\begin{matrix} 𝑓_{𝑘 + 1} & 𝑓_{𝑘} \\ 𝑓_{𝑘} & 𝑓_{𝑘 - 1} \end{matrix}) (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \\ = (\begin{matrix} 𝑓_{𝑘 + 1} + 𝑓_{𝑘} & 𝑓_{𝑘 + 1} \\ 𝑓_{𝑘} + 𝑓_{𝑘 - 1} & 𝑓_{𝑘} \end{matrix}) \\ = (\begin{matrix} 𝑓_{𝑘 + 2} & 𝑓_{𝑘 + 1} \\ 𝑓_{𝑘 + 1} & 𝑓_{𝑘} \end{matrix}) . \end{aligned}

(b) By Notation 2.4.16, $𝑄^{𝑚 + 𝑛} = 𝑄^{𝑚} 𝑄^{𝑛}$ . The $(1, 2)$ entry of the left side is $𝑓_{𝑚 + 𝑛}$ by (a), and by the entry formula the $(1, 2)$ entry of the right side is

\begin{matrix} {(𝑄^{𝑚})}_{11} {(𝑄^{𝑛})}_{12} + {(𝑄^{𝑚})}_{12} {(𝑄^{𝑛})}_{22} \\ = 𝑓_{𝑚 + 1} 𝑓_{𝑛} + 𝑓_{𝑚} 𝑓_{𝑛 - 1} . \end{matrix}

With $𝑚 = 𝑛$ this is $𝑓_{2 𝑛} =$ $𝑓_{𝑛 + 1} 𝑓_{𝑛} +$ $𝑓_{𝑛} 𝑓_{𝑛 - 1} =$ $𝑓_{𝑛} (𝑓_{𝑛 + 1} + 𝑓_{𝑛 - 1})$ . For example, $𝑓_{10} =$ $𝑓_{5} (𝑓_{6} + 𝑓_{4}) =$ $5 (8 + 3) =$ $55$ . Linear recurrences in general are treated with matrix powers in Section 15.2.

Exercise 2.4.48.routine Find the error in the following computation, which claims that ${(𝐴 𝐵)}^{𝖳} = 𝐴^{𝖳} 𝐵^{𝖳}$ for $𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}$ :

\begin{aligned} {({(𝐴 𝐵)}^{𝖳})}_{𝑖 𝑗} & = {(𝐴 𝐵)}_{𝑗 𝑖} = \sum_{𝑘} 𝑎_{𝑗 𝑘} 𝑏_{𝑘 𝑖} \\ = \sum_{𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} {(𝐵^{𝖳})}_{𝑖 𝑘} = {(𝐴^{𝖳} 𝐵^{𝖳})}_{𝑖 𝑗} . \end{aligned}

Solution.

Uses. Proposition 2.4.8 (Four views of the product), Proposition 2.4.23 (Transpose of a product)

Hint 1. The first three equalities are correct. In the entry formula

{(𝑋 𝑌)}_{𝑖 𝑗} =

\sum_{𝑘} 𝑥_{𝑖 𝑘} 𝑦_{𝑘 𝑗}

, which index of each factor is the summation index?

Hint 2. In

{(𝐴^{𝖳})}_{𝑘 𝑗} {(𝐵^{𝖳})}_{𝑖 𝑘}

, the summation index

𝑘

is the first index of the

𝐴^{𝖳}

factor. Reorder the two factors.

Sketch. The last step misreads the index pattern. After reordering the factors, the sum is

\sum_{𝑘} {(𝐵^{𝖳})}_{𝑖 𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗}

, which is the

(𝑖, 𝑗)

entry of

𝐵^{𝖳} 𝐴^{𝖳}

, not of

𝐴^{𝖳} 𝐵^{𝖳}

. The correct conclusion is

{(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳}

Everything up to the last equality is correct. In a product ${(𝑋 𝑌)}_{𝑖 𝑗} =$ $\sum_{𝑘} 𝑥_{𝑖 𝑘} 𝑦_{𝑘 𝑗}$ , the row index $𝑖$ belongs to the left factor, the column index $𝑗$ to the right factor, and the summation index is the column index of the left factor and the row index of the right one. In $\sum_{𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} {(𝐵^{𝖳})}_{𝑖 𝑘}$ , the factor carrying $𝑖$ is $𝐵^{𝖳}$ and the factor carrying $𝑗$ is $𝐴^{𝖳}$ . Since scalars commute,

\begin{aligned} \sum_{𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} {(𝐵^{𝖳})}_{𝑖 𝑘} & = \sum_{𝑘} {(𝐵^{𝖳})}_{𝑖 𝑘} {(𝐴^{𝖳})}_{𝑘 𝑗} \\ = {(𝐵^{𝖳} 𝐴^{𝖳})}_{𝑖 𝑗} . \end{aligned}

So the computation actually proves Proposition 2.4.23. The claimed identity is false: with $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ as in Example 2.4.19, we have ${(𝐴 𝐵)}^{𝖳} = 0^{𝖳} = 0$ , while $𝐴^{𝖳} 𝐵^{𝖳} =$ $(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) =$ $(\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ .

Exercise 2.4.49.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)Show that $tr (𝐴 𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) =$ $𝑎_{𝑖 𝑗}$ for $1 \leq 𝑖 \leq 𝑚$ and $1 \leq 𝑗 \leq 𝑛$ .
(b)Show that if $tr (𝐴 𝑋) = 0$ for every $𝑋 \in 𝐹^{𝑛 \times 𝑚}$ , then $𝐴 = 0$ .
(c)Show that every linear map $𝜑 : 𝐹^{𝑛 \times 𝑚} \to 𝐹$ has the form $𝜑 (𝑋) = tr (𝐵 𝑋)$ for exactly one $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ .

Solution.

Uses. Lemma 2.4.24 (Matrix units), Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.4.14 (Algebra of matrices)

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. (a) Rotate inside the trace:

tr (𝐴 𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) =

tr (𝐞_{𝑖}^{𝖳} 𝐴 𝐞_{𝑗})

, a

1 \times 1

matrix.

Hint 2. (c) Choose

𝐵

so that

tr (𝐵 𝑋)

and

𝜑 (𝑋)

agree on the matrix units

𝑋 = 𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}

. Uniqueness is (b) applied to a difference.

Sketch. (a) By cyclicity,

tr (𝐴 𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) =

tr (𝐞_{𝑖}^{𝖳} 𝐴 𝐞_{𝑗}) =

𝑎_{𝑖 𝑗}

. (b) Take

𝑋 = 𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}

. (c) Let

𝑏_{𝑖 𝑗} =

𝜑 (𝐞_{𝑗} 𝐞_{𝑖}^{𝖳})

; then

𝑋 \mapsto tr (𝐵 𝑋)

is linear and agrees with

𝜑

on the matrix units, which span. If

tr (𝐵 𝑋) =

tr (𝐵^{'} 𝑋)

for all

𝑋

, then

tr ((𝐵 - 𝐵^{'}) 𝑋) = 0

for all

𝑋

, so

𝐵 = 𝐵^{'}

by (b).

(a) By Proposition 2.4.28 with the factors $𝐴 𝐞_{𝑗} \in 𝐹^{𝑚 \times 1}$ and $𝐞_{𝑖}^{𝖳} \in 𝐹^{1 \times 𝑚}$ , and by Lemma 2.4.24(b),

tr ((𝐴 𝐞_{𝑗}) 𝐞_{𝑖}^{𝖳}) = tr (𝐞_{𝑖}^{𝖳} (𝐴 𝐞_{𝑗})) = 𝐞_{𝑖}^{𝖳} 𝐴 𝐞_{𝑗} = 𝑎_{𝑖 𝑗} .

(b) Taking $𝑋 =$ $𝐞_{𝑗} 𝐞_{𝑖}^{𝖳} \in$ $𝐹^{𝑛 \times 𝑚}$ in the hypothesis and using (a) gives $𝑎_{𝑖 𝑗} = 0$ for all $𝑖, 𝑗$ .

(c) Define $𝐵 \in 𝐹^{𝑚 \times 𝑛}$ by $𝑏_{𝑖 𝑗} =$ $𝜑 (𝐞_{𝑗} 𝐞_{𝑖}^{𝖳})$ . The map $𝜓 (𝑋) = tr (𝐵 𝑋)$ is linear, by Proposition 2.4.14 and Proposition 2.4.27, and by (a) applied to $𝐵$ , $𝜓 (𝐞_{𝑗} 𝐞_{𝑖}^{𝖳}) =$ $𝑏_{𝑖 𝑗} =$ $𝜑 (𝐞_{𝑗} 𝐞_{𝑖}^{𝖳})$ . The matrix units span $𝐹^{𝑛 \times 𝑚}$ (Lemma 2.4.24(a)), so $𝜓 = 𝜑$ by Corollary 2.2.6. If also $𝜑 (𝑋) = tr (𝐵^{'} 𝑋)$ for all $𝑋$ , then $tr ((𝐵 - 𝐵^{'}) 𝑋) = 0$ for all $𝑋$ , and $𝐵 = 𝐵^{'}$ by (b). So the linear maps $𝐹^{𝑛 \times 𝑚} \to 𝐹$ correspond exactly to the matrices of $𝐹^{𝑚 \times 𝑛}$ ; this is a first example of duality (Section 13.1).

Exercise 2.4.50.hard Let

𝜑 : 𝐹^{𝑛 \times 𝑛} \to 𝐹

be linear with

𝜑 (𝐴 𝐵) = 𝜑 (𝐵 𝐴)

for all

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

. Show that

𝜑 = 𝑐 tr

for some

𝑐 \in 𝐹

. (So the trace is, up to a scalar, the only linear functional with the property of Proposition 2.4.28.)

Solution.

Uses. Lemma 2.4.24 (Matrix units), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.4.27 (The trace is linear)

Techniques. Check it on a basis (Technique 2.2.7), Cyclicity of trace (Technique 2.4.29)

Hint 1. It is enough to compute

𝜑

on the matrix units

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

. Write each one as a product

𝑋 𝑌

for which

𝑌 𝑋

is simpler.

Hint 2. For

𝑖 \neq 𝑗

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳} =

(𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳})

, and the product in the other order is

0

. For the diagonal units, compare

(𝐞_{𝑖} 𝐞_{1}^{𝖳}) (𝐞_{1} 𝐞_{𝑖}^{𝖳})

with the product in the other order.

Sketch. For

𝑖 \neq 𝑗

, write

𝐞_{𝑖} 𝐞_{𝑗}^{𝖳} = 𝑋 𝑌

with

𝑋 = 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}

and

𝑌 = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}

; then

𝑌 𝑋 = 0

, so

𝜑 (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) =

𝜑 (𝑌 𝑋) =

0

. Writing

𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}

and

𝐞_{1} 𝐞_{1}^{𝖳}

as the two products of

𝐞_{𝑖} 𝐞_{1}^{𝖳}

and

𝐞_{1} 𝐞_{𝑖}^{𝖳}

shows that

𝜑

takes the same value

𝑐

on all diagonal units. So

𝜑

and

𝑐 tr

agree on the matrix units.

We compute $𝜑$ on the matrix units, using Lemma 2.4.24(c) throughout. For $𝑖 \neq 𝑗$ ,

\begin{matrix} 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳} = (𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}), \\ (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) (𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) = 𝛿_{𝑗 𝑖} 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳} = 0, \end{matrix}

so the hypothesis gives $𝜑 (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) =$ $𝜑 (0) =$ $0$ . For the diagonal units,

\begin{matrix} 𝐞_{𝑖} 𝐞_{𝑖}^{𝖳} = (𝐞_{𝑖} 𝐞_{1}^{𝖳}) (𝐞_{1} 𝐞_{𝑖}^{𝖳}), \\ 𝐞_{1} 𝐞_{1}^{𝖳} = (𝐞_{1} 𝐞_{𝑖}^{𝖳}) (𝐞_{𝑖} 𝐞_{1}^{𝖳}), \end{matrix}

so $𝜑 (𝐞_{𝑖} 𝐞_{𝑖}^{𝖳}) =$ $𝜑 (𝐞_{1} 𝐞_{1}^{𝖳})$ for every $𝑖$ ; call this value $𝑐$ . On the other hand $tr (𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}) =$ $𝛿_{𝑖 𝑗}$ . So the linear maps $𝜑$ and $𝑐 tr$ (Proposition 2.4.27) agree on every matrix unit. The matrix units span $𝐹^{𝑛 \times 𝑛}$ (Lemma 2.4.24(a)), so $𝜑 = 𝑐 tr$ by Corollary 2.2.6.

Exercise 2.4.51.standard Let $𝐷, 𝑀 \in L (𝐹 [𝑥])$ be differentiation and multiplication by $𝑥$ (Example 2.1.9).

(a)Show that $𝐷 𝑀 -$ $𝑀 𝐷 =$ ${id}_{𝐹 [𝑥]}$ .
(b)Explain why (a) does not contradict Proposition 2.4.30, even over $ℚ$ .
(c)Show that if $𝑈$ is a subspace of $𝐹 [𝑥]$ spanned by finitely many polynomials and $𝑀 (𝑈) \subseteq 𝑈$ , then $𝑈 = {𝟎}$ .

Solution.

Uses. Example 2.1.9 (Maps of polynomials), Proposition 2.1.23 ( $L (𝑉, 𝑊)$ is a vector space), Proposition 2.1.17 (Compositions of linear maps are linear), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.4.30 ( $𝐴 𝐵 - 𝐵 𝐴 \neq 𝐼$ ), Definition 1.2.16 (Degree)

Hint 1. (a) Both sides are linear, so check on the monomials

𝑥^{𝑘}

, which span

𝐹 [𝑥]

Hint 2. (b) Proposition 2.4.30 is about

𝑛 \times 𝑛

matrices. (c) If

𝑈 \neq {𝟎}

, take a nonzero

𝑝 \in 𝑈

of the largest degree among a finite spanning list, and apply

𝑀

Sketch. (a)

(𝐷 𝑀 - 𝑀 𝐷) (𝑥^{𝑘}) =

(𝑘 + 1) 𝑥^{𝑘} -

𝑘 𝑥^{𝑘} =

𝑥^{𝑘}

. (b)

𝐹 [𝑥]

has no finite basis, so

𝐷

and

𝑀

are not given by square matrices; the trace argument needs a finite size. (c) Every element of

𝑈

has degree at most the largest degree

𝑑

in a finite spanning list; if

𝑈 \neq {𝟎}

it contains an element of degree exactly

𝑑

, and

𝑀

of it has degree

𝑑 + 1

(a) Both $𝐷 𝑀 - 𝑀 𝐷$ and $id$ are linear (Proposition 2.1.23, Proposition 2.1.17). For $𝑘 \geq 0$ ,

\begin{aligned} (𝐷 𝑀 - 𝑀 𝐷) (𝑥^{𝑘}) & = 𝐷 (𝑥^{𝑘 + 1}) - 𝑥 𝐷 (𝑥^{𝑘}) \\ = (𝑘 + 1) 𝑥^{𝑘} - 𝑘 𝑥^{𝑘} = 𝑥^{𝑘}, \end{aligned}

where for $𝑘 = 0$ the second term is $𝑥 𝐷 (1) = 𝟎$ . The monomials span $𝐹 [𝑥]$ , so $𝐷 𝑀 - 𝑀 𝐷 = id$ by Corollary 2.2.6. (This is the product rule ${(𝑥 𝑝)}^{'} = 𝑝 + 𝑥 𝑝^{'}$ .)

(b) Proposition 2.4.30 is a statement about $𝑛 \times 𝑛$ matrices, that is, about operators on $𝐹^{𝑛}$ , and its proof takes the trace, a finite sum of diagonal entries. The maps $𝐷$ and $𝑀$ act on $𝐹 [𝑥]$ , which is spanned by no finite list (every finite list of polynomials has a largest degree). So they have no $𝑛 \times 𝑛$ matrices, and there is no trace to take. Part (c) shows that we also cannot cut $𝐹 [𝑥]$ down to a finite-dimensional piece on which $𝑀$ acts.

(c) Suppose $𝑈 =$ $span (𝑝_{1}, \dots, 𝑝_{𝑟})$ with $𝑀 (𝑈) \subseteq 𝑈$ and $𝑈 \neq {𝟎}$ . We may drop the $𝑝_{𝑖}$ that are $𝟎$ , so all are nonzero, and $𝑟 \geq 1$ . Let $𝑑$ be the largest of $deg 𝑝_{1}, \dots, deg 𝑝_{𝑟}$ . Every element of $𝑈$ is a combination of the $𝑝_{𝑖}$ , so every nonzero element of $𝑈$ has degree at most $𝑑$ , and $𝑝_{𝑖}$ has degree $𝑑$ for some $𝑖$ . But $𝑀 (𝑝_{𝑖}) =$ $𝑥 𝑝_{𝑖} \in$ $𝑈$ has degree $𝑑 + 1$ , a contradiction. So $𝑈 = {𝟎}$ . (The same argument shows that $𝐹 [𝑥]$ itself is not spanned by finitely many polynomials.)

Exercise 2.4.52.hard Let $𝑝$ be prime.

(a)Let $𝐴, 𝐵 \in 𝔽_{𝑝}^{𝑝 \times 𝑝}$ be the matrices with $𝐴 𝐞_{1} = 𝟎$ , $𝐴 𝐞_{𝑘 + 1} = 𝑘 𝐞_{𝑘}$ for $1 \leq 𝑘 \leq 𝑝 - 1$ , and $𝐵 𝐞_{𝑘} = 𝐞_{𝑘 + 1}$ for $𝑘 \leq 𝑝 - 1$ , $𝐵 𝐞_{𝑝} = 𝟎$ . Show that $𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑝}$ .
(b)Show that there are $𝑋, 𝑌 \in 𝔽_{𝑝}^{𝑛 \times 𝑛}$ with $𝑋 𝑌 - 𝑌 𝑋 = 𝐼_{𝑛}$ if and only if $𝑝$ divides $𝑛$ .

Solution.

Uses. Proposition 2.4.30 ( $𝐴 𝐵 - 𝐵 𝐴 \neq 𝐼$ ), Theorem 2.4.34 (Block multiplication), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.3.13 (Linearity of the product)

Techniques. Block decomposition (Technique 2.4.35), Cyclicity of trace (Technique 2.4.29)

Hint 1. (a)

𝐴

and

𝐵

are the matrices of differentiation and of multiplication by

𝑥

on polynomials of degree less than

𝑝

, in the basis

1, 𝑥, \dots, 𝑥^{𝑝 - 1}

, with

𝑥^{𝑝}

replaced by

0

. Compute

(𝐴 𝐵 - 𝐵 𝐴) 𝐞_{𝑘}

, treating

𝑘 = 𝑝

separately.

Hint 2. (b) One direction is Proposition 2.4.30: over

𝔽_{𝑝}

𝑛 * 1 = 0

exactly when

𝑝 ∣ 𝑛

. For the other, put

𝑛 / 𝑝

copies of the matrices from (a) on the diagonal of a block diagonal matrix.

Sketch. (a) For

𝑘 < 𝑝

𝐴 𝐵 𝐞_{𝑘} =

𝐴 𝐞_{𝑘 + 1} =

𝑘 𝐞_{𝑘}

and

𝐵 𝐴 𝐞_{𝑘} =

(𝑘 - 1) 𝐞_{𝑘}

, so the difference is

𝐞_{𝑘}

. For

𝑘 = 𝑝

𝐴 𝐵 𝐞_{𝑝} = 𝟎

and

𝐵 𝐴 𝐞_{𝑝} =

(𝑝 - 1) 𝐞_{𝑝}

, so the difference is

(1 - 𝑝) 𝐞_{𝑝} = 𝐞_{𝑝}

. (b) If

𝑝 ∤ 𝑛

then

𝑛 * 1 \neq 0

𝔽_{𝑝}

. If

𝑛 = 𝑝 𝑞

, let

𝑋 = diag (𝐴, \dots, 𝐴)

and

𝑌 = diag (𝐵, \dots, 𝐵)

(

𝑞

blocks); block multiplication gives

𝑋 𝑌 -

𝑌 𝑋 =

diag (𝐼_{𝑝}, \dots, 𝐼_{𝑝}) =

𝐼_{𝑛}

(a) We compare $(𝐴 𝐵 - 𝐵 𝐴) 𝐞_{𝑘}$ with $𝐞_{𝑘}$ for each $𝑘$ ; by Proposition 2.3.13(c) these are the columns of the two matrices. Note that $𝐵 𝐴 𝐞_{𝑘} =$ $𝐵 ((𝑘 - 1) 𝐞_{𝑘 - 1}) =$ $(𝑘 - 1) 𝐞_{𝑘}$ for $2 \leq 𝑘 \leq 𝑝$ , and $𝐵 𝐴 𝐞_{1} =$ $𝐵 𝟎 =$ $𝟎 =$ $(1 - 1) 𝐞_{1}$ , so $𝐵 𝐴 𝐞_{𝑘} =$ $(𝑘 - 1) 𝐞_{𝑘}$ for all $𝑘$ . For $1 \leq 𝑘 \leq 𝑝 - 1$ , $𝐴 𝐵 𝐞_{𝑘} =$ $𝐴 𝐞_{𝑘 + 1} =$ $𝑘 𝐞_{𝑘}$ , so

(𝐴 𝐵 - 𝐵 𝐴) 𝐞_{𝑘} = 𝑘 𝐞_{𝑘} - (𝑘 - 1) 𝐞_{𝑘} = 𝐞_{𝑘} .

For $𝑘 = 𝑝$ , $𝐴 𝐵 𝐞_{𝑝} = 𝐴 𝟎 = 𝟎$ , so $(𝐴 𝐵 - 𝐵 𝐴) 𝐞_{𝑝} =$ $- (𝑝 - 1) 𝐞_{𝑝}$ , which is $𝐞_{𝑝}$ because $- (𝑝 - 1) = 1 - 𝑝 = 1$ in $𝔽_{𝑝}$ . So $𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑝}$ . For $𝑝 = 2$ these are the matrices $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ of Remark 2.4.31.

(b) If $𝑝 ∤ 𝑛$ , then $𝑛 * 1 = 𝑛 mod 𝑝 \neq 0$ in $𝔽_{𝑝}$ , and Proposition 2.4.30 says that no such $𝑋, 𝑌$ exist. Conversely, suppose $𝑛 = 𝑝 𝑞$ . Let $𝑋$ and $𝑌$ be the block diagonal matrices with $𝑞$ diagonal blocks, all equal to $𝐴$ , respectively all equal to $𝐵$ , partitioned with sizes $𝑝, \dots, 𝑝$ . By Theorem 2.4.34, $𝑋 𝑌$ and $𝑌 𝑋$ are block diagonal with diagonal blocks $𝐴 𝐵$ , respectively $𝐵 𝐴$ , so $𝑋 𝑌 - 𝑌 𝑋$ is block diagonal with diagonal blocks $𝐴 𝐵 - 𝐵 𝐴 = 𝐼_{𝑝}$ . That is the matrix $𝐼_{𝑛}$ .

Exercise 2.4.53.hard Let

𝐴, 𝐵 \in 𝐹^{𝑛 \times 𝑛}

, and suppose that

𝐶 = 𝐴 𝐵 - 𝐵 𝐴

commutes with

𝐴

. Show that

tr (𝐶^{𝑘}) = 0

for every

𝑘 \geq 1

Solution.

Uses. Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear), Proposition 2.4.14 (Algebra of matrices)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. It suffices to write

𝐶^{𝑘}

as a commutator

𝐴 𝑋 - 𝑋 𝐴

for some

𝑋

, since commutators have trace

0

Hint 2.

𝐶^{𝑘} =

𝐶^{𝑘 - 1} (𝐴 𝐵 - 𝐵 𝐴) =

𝐶^{𝑘 - 1} 𝐴 𝐵 -

𝐶^{𝑘 - 1} 𝐵 𝐴

. Move

𝐴

past

𝐶^{𝑘 - 1}

in the first term.

Sketch. Since

𝐶

commutes with

𝐴

, so does

𝐶^{𝑘 - 1}

. Expanding

𝐶^{𝑘} =

𝐶^{𝑘 - 1} (𝐴 𝐵 - 𝐵 𝐴)

and moving

𝐴

to the front of the first term gives

𝐶^{𝑘} = 𝐴 𝑋 - 𝑋 𝐴

with

𝑋 = 𝐶^{𝑘 - 1} 𝐵

, so

tr (𝐶^{𝑘}) = 0

by cyclicity.

Since $𝐴 𝐶 = 𝐶 𝐴$ , induction gives $𝐴 𝐶^{𝑘 - 1} = 𝐶^{𝑘 - 1} 𝐴$ for every $𝑘 \geq 1$ (for $𝑘 = 1$ , $𝐶^{0} = 𝐼_{𝑛}$ ). By distributivity and associativity (Proposition 2.4.14),

\begin{aligned} 𝐶^{𝑘} & = 𝐶^{𝑘 - 1} (𝐴 𝐵 - 𝐵 𝐴) \\ = (𝐶^{𝑘 - 1} 𝐴) 𝐵 - 𝐶^{𝑘 - 1} 𝐵 𝐴 \\ = 𝐴 (𝐶^{𝑘 - 1} 𝐵) - (𝐶^{𝑘 - 1} 𝐵) 𝐴 . \end{aligned}

So with $𝑋 = 𝐶^{𝑘 - 1} 𝐵$ , Proposition 2.4.27 and Proposition 2.4.28 give $tr (𝐶^{𝑘}) =$ $tr (𝐴 𝑋) -$ $tr (𝑋 𝐴) =$ $0$ . Over $ℂ$ , the vanishing of every $tr (𝐶^{𝑘})$ forces $𝐶$ to be nilpotent, a result known as Jacobson’s lemma; that last step needs eigenvalues (Section 7.3).

Exercise 2.4.54.challenge Let

𝐴, 𝐵 \in ℝ^{𝑛 \times 𝑛}

be symmetric. Show that

tr (𝐴 𝐵 𝐴 𝐵) \leq

tr (𝐴^{2} 𝐵^{2})

, with equality if and only if

𝐴 𝐵 = 𝐵 𝐴

Solution.

Uses. Proposition 2.4.28 (Cyclicity of the trace), Proposition 2.4.27 (The trace is linear), Proposition 2.4.23 (Transpose of a product), Proposition 2.4.8 (Four views of the product), Exercise 2.4.25

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. The equality case suggests looking at

𝐶 = 𝐴 𝐵 - 𝐵 𝐴

. What is

𝐶^{𝖳}

Hint 2. Expand

tr (𝐶^{2})

and use cyclicity to bring each of the four terms to

tr (𝐴 𝐵 𝐴 𝐵)

tr (𝐴^{2} 𝐵^{2})

Hint 3. For a real skew-symmetric

𝐶

tr (𝐶^{2}) =

- tr (𝐶^{𝖳} 𝐶)

, and

tr (𝐶^{𝖳} 𝐶)

is a sum of squares of entries.

Sketch.

𝐶 = 𝐴 𝐵 - 𝐵 𝐴

is skew-symmetric. Cyclicity gives

tr (𝐶^{2}) =

2 tr (𝐴 𝐵 𝐴 𝐵) -

2 tr (𝐴^{2} 𝐵^{2})

. Also

tr (𝐶^{2}) =

- tr (𝐶^{𝖳} 𝐶) =

- \sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗}^{2} \leq

0

, with equality iff

𝐶 = 0

Let $𝐶 = 𝐴 𝐵 - 𝐵 𝐴$ . By Exercise 2.4.25, $𝐶$ is skew-symmetric: $𝐶^{𝖳} = - 𝐶$ . Expanding,

𝐶^{2} = 𝐴 𝐵 𝐴 𝐵 - 𝐴 𝐵 𝐵 𝐴 - 𝐵 𝐴 𝐴 𝐵 + 𝐵 𝐴 𝐵 𝐴 .

By Proposition 2.4.28, rotating the factors gives $tr (𝐴 𝐵 𝐵 𝐴) =$ $tr (𝐴 𝐴 𝐵 𝐵)$ , $tr (𝐵 𝐴 𝐴 𝐵) =$ $tr (𝐴 𝐴 𝐵 𝐵)$ , and $tr (𝐵 𝐴 𝐵 𝐴) =$ $tr (𝐴 𝐵 𝐴 𝐵)$ . So by Proposition 2.4.27,

tr (𝐶^{2}) = 2 tr (𝐴 𝐵 𝐴 𝐵) - 2 tr (𝐴^{2} 𝐵^{2}) .

On the other hand $𝐶^{2} = - 𝐶^{𝖳} 𝐶$ , and by the entry formula the $(𝑗, 𝑗)$ entry of $𝐶^{𝖳} 𝐶$ is $\sum_{𝑖} 𝑐_{𝑖 𝑗}^{2}$ . Hence

tr (𝐶^{2}) = - tr (𝐶^{𝖳} 𝐶) = - \sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗}^{2} \leq 0,

with equality if and only if every $𝑐_{𝑖 𝑗} = 0$ , that is, $𝐴 𝐵 = 𝐵 𝐴$ . Combining the two expressions for $tr (𝐶^{2})$ gives $tr (𝐴 𝐵 𝐴 𝐵) \leq$ $tr (𝐴^{2} 𝐵^{2})$ , with equality exactly when $𝐴 𝐵 = 𝐵 𝐴$ .

Exercise 2.4.55.standard Let $𝐴 \in 𝐹^{𝑝 \times 𝑝}$ , $𝑋 \in 𝐹^{𝑝 \times 𝑞}$ , and $𝐷 \in 𝐹^{𝑞 \times 𝑞}$ , and let $𝑁 = (\begin{matrix} 𝐴 & 𝑋 \\ 0 & 𝐷 \end{matrix})$ .

(a)Show that $𝑁^{𝑘} =$ $(\begin{matrix} 𝐴^{𝑘} & 𝑋_{𝑘} \\ 0 & 𝐷^{𝑘} \end{matrix})$ for every $𝑘 \geq 1$ , where $𝑋_{𝑘} =$ $\sum_{𝑖 = 0}^{𝑘 - 1} 𝐴^{𝑖} 𝑋 𝐷^{𝑘 - 1 - 𝑖}$ .
(b)Deduce that if $𝐴^{𝑘} = 0$ and $𝐷^{𝑘} = 0$ , then $𝑁^{2 𝑘} = 0$ .

Solution.

Uses. Theorem 2.4.34 (Block multiplication), Proposition 2.4.14 (Algebra of matrices), Notation 2.4.16 (Powers of a matrix)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. (a) Induct on

𝑘

. Compute

𝑁^{𝑘 + 1} = 𝑁^{𝑘} 𝑁

by blocks; the top right block is

𝐴^{𝑘} 𝑋 + 𝑋_{𝑘} 𝐷

Hint 2. (b)

𝑁^{2 𝑘} = 𝑁^{𝑘} 𝑁^{𝑘}

, and

𝑁^{𝑘}

has zero diagonal blocks.

Sketch. (a) By blocks,

𝑁^{𝑘} 𝑁

has diagonal blocks

𝐴^{𝑘 + 1}

𝐷^{𝑘 + 1}

and top right block

𝐴^{𝑘} 𝑋 + 𝑋_{𝑘} 𝐷

, and

𝑋_{𝑘} 𝐷 =

\sum_{𝑖 = 0}^{𝑘 - 1} 𝐴^{𝑖} 𝑋 𝐷^{𝑘 - 𝑖}

, so the top right block is

𝑋_{𝑘 + 1}

. (b)

𝑁^{𝑘} = (\begin{matrix} 0 & 𝑋_{𝑘} \\ 0 & 0 \end{matrix})

, and

{(\begin{matrix} 0 & 𝑌 \\ 0 & 0 \end{matrix})}^{2} = 0

(a) For $𝑘 = 1$ , $𝑋_{1} = 𝐴^{0} 𝑋 𝐷^{0} = 𝑋$ . Suppose the formula holds for $𝑘$ . By Theorem 2.4.34,

\begin{aligned} 𝑁^{𝑘 + 1} = 𝑁^{𝑘} 𝑁 & = (\begin{matrix} 𝐴^{𝑘} & 𝑋_{𝑘} \\ 0 & 𝐷^{𝑘} \end{matrix}) (\begin{matrix} 𝐴 & 𝑋 \\ 0 & 𝐷 \end{matrix}) \\ = (\begin{matrix} 𝐴^{𝑘 + 1} & 𝐴^{𝑘} 𝑋 + 𝑋_{𝑘} 𝐷 \\ 0 & 𝐷^{𝑘 + 1} \end{matrix}), \end{aligned}

and by distributivity

\begin{aligned} 𝐴^{𝑘} 𝑋 + 𝑋_{𝑘} 𝐷 & = 𝐴^{𝑘} 𝑋 𝐷^{0} + \sum_{𝑖 = 0}^{𝑘 - 1} 𝐴^{𝑖} 𝑋 𝐷^{𝑘 - 𝑖} \\ = \sum_{𝑖 = 0}^{𝑘} 𝐴^{𝑖} 𝑋 𝐷^{𝑘 - 𝑖} = 𝑋_{𝑘 + 1} . \end{aligned}

(b) If $𝐴^{𝑘} = 0$ and $𝐷^{𝑘} = 0$ , then $𝑁^{𝑘} = (\begin{matrix} 0 & 𝑋_{𝑘} \\ 0 & 0 \end{matrix})$ , and by block multiplication

𝑁^{2 𝑘} = 𝑁^{𝑘} 𝑁^{𝑘} = (\begin{matrix} 0 & 𝑋_{𝑘} \\ 0 & 0 \end{matrix}) (\begin{matrix} 0 & 𝑋_{𝑘} \\ 0 & 0 \end{matrix}) = 0,

since each block of the product is a sum of terms with a zero factor. So a block upper triangular matrix whose diagonal blocks are nilpotent is nilpotent. The bound $2 𝑘$ cannot be improved to $𝑘$ in general: for $𝑝 = 𝑞 = 1$ , $𝐴 = 𝐷 = 0$ , and $𝑋 = 1$ , $𝑁 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ has $𝐴^{1} = 𝐷^{1} = 0$ but $𝑁^{1} \neq 0$ .

Exercise 2.4.56.routineBeyond 21-242 Let $𝐺$ be the directed graph on $1, 2, 3$ with edges $(1, 2)$ , $(2, 3)$ , $(3, 1)$ , and $(1, 1)$ .

(a)Write down its adjacency matrix $𝐴$ and compute $𝐴^{2}$ and $𝐴^{3}$ .
(b)How many walks of length $3$ go from $1$ to $1$ ? List them. How many closed walks of length $3$ are there in all?

Solution.

Uses. Definition 2.4.38 (Adjacency matrix), Proposition 2.4.39 (Powers count walks)

Hint 1.

𝐴

has a

1

in positions

(1, 2)

(2, 3)

(3, 1)

, and

(1, 1)

Hint 2. By Proposition 2.4.39, the answers are

{(𝐴^{3})}_{11}

and

tr (𝐴^{3})

. Check them by listing walks.

Sketch.

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

and

𝐴^{3} = (\begin{matrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})

. The two walks of length

3

from

1

1

are

1, 1, 1, 1

and

1, 2, 3, 1

, and

tr (𝐴^{3}) = 4

(a)

\begin{matrix} 𝐴 = (\begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}), 𝐴^{2} = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix}), \\ 𝐴^{3} = 𝐴^{2} 𝐴 = (\begin{matrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}) . \end{matrix}

(b) By Proposition 2.4.39 there are ${(𝐴^{3})}_{11} = 2$ walks of length $3$ from $1$ to $1$ : they are $1, 1, 1, 1$ (the loop three times) and $1, 2, 3, 1$ (around the triangle). In all there are $tr (𝐴^{3}) = 2 + 1 + 1 = 4$ closed walks of length $3$ : the two above, and $2, 3, 1, 2$ and $3, 1, 2, 3$ .

Exercise 2.4.57.hardBeyond 21-242 Let $𝑛 \geq 2$ , let $𝐽 \in ℚ^{𝑛 \times 𝑛}$ be the matrix all of whose entries are $1$ , and let $𝐴 = 𝐽 - 𝐼_{𝑛}$ , the adjacency matrix of the complete graph on $𝑛$ vertices (every two distinct vertices are joined).

(a)Show that $𝐽^{2} = 𝑛 𝐽$ .
(b)Show that $𝐴^{𝑘} =$ $𝑎_{𝑘} 𝐽 +$ ${(- 1)}^{𝑘} 𝐼_{𝑛}$ for $𝑘 \geq 1$ , where $𝑎_{𝑘} =$ $({(𝑛 - 1)}^{𝑘} - {(- 1)}^{𝑘}) / 𝑛$ .
(c)How many walks of length $𝑘$ are there between two distinct vertices, and how many closed walks of length $𝑘$ are there in all?

Solution.

Uses. Proposition 2.4.39 (Powers count walks), Proposition 2.4.8 (Four views of the product), Proposition 2.4.14 (Algebra of matrices), Definition 2.4.26 (Trace)

Hint 1. (a) Every entry of

𝐽^{2}

is a sum of

𝑛

products

1 \cdot 1

Hint 2. (b) Induct on

𝑘

. Expand

(𝑎_{𝑘} 𝐽 + {(- 1)}^{𝑘} 𝐼) (𝐽 - 𝐼)

with (a), and check that the coefficient of

𝐽

satisfies

𝑎_{𝑘 + 1} =

(𝑛 - 1) 𝑎_{𝑘} +

{(- 1)}^{𝑘}

Sketch. (a) Each entry of

𝐽^{2}

is a sum of

𝑛

ones. (b) Multiplying

𝑎_{𝑘} 𝐽 + {(- 1)}^{𝑘} 𝐼

𝐽 - 𝐼

and using

𝐽^{2} = 𝑛 𝐽

gives coefficient

(𝑛 - 1) 𝑎_{𝑘} + {(- 1)}^{𝑘}

𝐽

and

{(- 1)}^{𝑘 + 1}

𝐼

; the formula for

𝑎_{𝑘}

satisfies this recursion. (c) Off the diagonal,

{(𝐴^{𝑘})}_{𝑖 𝑗} = 𝑎_{𝑘}

; the trace is

𝑛 𝑎_{𝑘} + 𝑛 {(- 1)}^{𝑘}

, which simplifies to

{(𝑛 - 1)}^{𝑘} +

(𝑛 - 1) {(- 1)}^{𝑘}

(a) By the entry formula, ${(𝐽^{2})}_{𝑖 𝑗} =$ $\sum_{𝑘 = 1}^{𝑛} 1 \cdot$ $1 =$ $𝑛$ , so $𝐽^{2} = 𝑛 𝐽$ .

(b) For $𝑘 = 1$ , $𝑎_{1} = (𝑛 - 1 + 1) / 𝑛 = 1$ , and $𝐴 =$ $𝐽 -$ $𝐼_{𝑛} =$ $𝑎_{1} 𝐽 +$ ${(- 1)}^{1} 𝐼_{𝑛}$ . If $𝐴^{𝑘} =$ $𝑎_{𝑘} 𝐽 +$ ${(- 1)}^{𝑘} 𝐼_{𝑛}$ , then by Proposition 2.4.14 and (a),

\begin{aligned} 𝐴^{𝑘 + 1} & = (𝑎_{𝑘} 𝐽 + {(- 1)}^{𝑘} 𝐼_{𝑛}) (𝐽 - 𝐼_{𝑛}) \\ = 𝑎_{𝑘} 𝑛 𝐽 - 𝑎_{𝑘} 𝐽 + {(- 1)}^{𝑘} 𝐽 - {(- 1)}^{𝑘} 𝐼_{𝑛} \\ = ((𝑛 - 1) 𝑎_{𝑘} + {(- 1)}^{𝑘}) 𝐽 + {(- 1)}^{𝑘 + 1} 𝐼_{𝑛} . \end{aligned}

It remains to show that the coefficient of $𝐽$ is $𝑎_{𝑘 + 1}$ . Write $𝑏_{𝑘} =$ $𝑛 𝑎_{𝑘} =$ ${(𝑛 - 1)}^{𝑘} -$ ${(- 1)}^{𝑘}$ . Then $𝑛 ((𝑛 - 1) 𝑎_{𝑘} + {(- 1)}^{𝑘}) =$ $(𝑛 - 1) 𝑏_{𝑘} +$ $𝑛 {(- 1)}^{𝑘}$ , and

\begin{matrix} (𝑛 - 1) 𝑏_{𝑘} + 𝑛 {(- 1)}^{𝑘} \\ = {(𝑛 - 1)}^{𝑘 + 1} - (𝑛 - 1) {(- 1)}^{𝑘} + 𝑛 {(- 1)}^{𝑘} \\ = {(𝑛 - 1)}^{𝑘 + 1} + {(- 1)}^{𝑘} = 𝑏_{𝑘 + 1} . \end{matrix}

Dividing by $𝑛$ gives $(𝑛 - 1) 𝑎_{𝑘} +$ ${(- 1)}^{𝑘} =$ $𝑎_{𝑘 + 1}$ .

(c) By Proposition 2.4.39 and (b), for $𝑖 \neq 𝑗$ there are ${(𝐴^{𝑘})}_{𝑖 𝑗} =$ $𝑎_{𝑘} =$ $({(𝑛 - 1)}^{𝑘} - {(- 1)}^{𝑘}) / 𝑛$ walks of length $𝑘$ from $𝑖$ to $𝑗$ , and the number of closed walks of length $𝑘$ is

\begin{aligned} tr (𝐴^{𝑘}) & = 𝑛 𝑎_{𝑘} + 𝑛 {(- 1)}^{𝑘} \\ = {(𝑛 - 1)}^{𝑘} - {(- 1)}^{𝑘} + 𝑛 {(- 1)}^{𝑘} \\ = {(𝑛 - 1)}^{𝑘} + (𝑛 - 1) {(- 1)}^{𝑘} . \end{aligned}

For instance, the triangle ( $𝑛 = 3$ ) has $2^{3} - 2 = 6$ closed walks of length $3$ , the two directions around it from each of the three vertices. As a check, $𝑎_{𝑘}$ is an integer, since $𝑛 - 1$ and $- 1$ leave the same remainder modulo $𝑛$ , so $𝑛$ divides ${(𝑛 - 1)}^{𝑘} - {(- 1)}^{𝑘}$ .

More practice

The practice bank has 112 exercises on this section’s topics.