2.3 Matrices of linear maps

By Theorem 2.2.1, a linear map $𝑇 : 𝑉 \to 𝑊$ is determined by its values $𝑇 (𝐯_{1}),$ $\dots,$ $𝑇 (𝐯_{𝑛})$ on a basis $𝐯_{1}, \dots, 𝐯_{𝑛}$ of $𝑉$ , and these values can be any list in $𝑊$ (Corollary 2.2.18). If $𝑊$ has a basis $𝐰_{1}, \dots, 𝐰_{𝑚}$ as well, each value $𝑇 (𝐯_{𝑗})$ is in turn determined by its coordinate vector in $𝐹^{𝑚}$ . So $𝑇$ is recorded by $𝑚 𝑛$ scalars, and writing the $𝑛$ coordinate vectors side by side gives an $𝑚 \times 𝑛$ matrix, the matrix of $𝑇$ . Two things then have to be worked out: how to recover the values of $𝑇$ from its matrix, which will force the definition of the matrix–vector product, and how much the matrix depends on the chosen bases, which turns out to be a great deal.

Throughout this section, $𝑉$ and $𝑊$ are vector spaces over $𝐹$ with bases $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ of $𝑉$ and $𝒞︀ = 𝐰_{1}, \dots, 𝐰_{𝑚}$ of $𝑊$ , where $𝑛, 𝑚 \geq 1$ , unless other bases are named. (We leave out the zero space, because matrices with no rows or no columns are not defined in Definition 1.2.7.)

2.3.1The matrix of a linear map

Definition 2.3.1 (Matrix of a linear map). Let $𝑇 \in L (𝑉, 𝑊)$ . The matrix of $𝑇$ with respect to $ℬ︀$ and $𝒞︀$ is the $𝑚 \times 𝑛$ matrix

{[𝑇]}_{𝒞︀ ℬ︀} = (\begin{matrix} {[𝑇 (𝐯_{1})]}_{𝒞︀} & {[𝑇 (𝐯_{2})]}_{𝒞︀} & \dots & {[𝑇 (𝐯_{𝑛})]}_{𝒞︀} \end{matrix})

whose $𝑗$ -th column is the coordinate vector of $𝑇 (𝐯_{𝑗})$ with respect to $𝒞︀$ . Equivalently, its entries $𝑎_{𝑖 𝑗}$ are the scalars with

𝑇 (𝐯_{𝑗}) = 𝑎_{1 𝑗} 𝐰_{1} + 𝑎_{2 𝑗} 𝐰_{2} + \dots + 𝑎_{𝑚 𝑗} 𝐰_{𝑚} (𝑗 = 1, \dots, 𝑛) .

For an operator $𝑇 \in L (𝑉)$ , the matrix of $𝑇$ with respect to $ℬ︀$ is ${[𝑇]}_{ℬ︀ ℬ︀}$ .

The matrix is well defined, since each $𝑇 (𝐯_{𝑗})$ has exactly one coordinate vector with respect to the basis $𝒞︀$ (Definition 1.6.14).

The matrix has one column for each vector of $ℬ︀$ and one row for each vector of $𝒞︀$ , so its size is (length of $𝒞︀$ ) $\times$ (length of $ℬ︀$ ). Column $𝑗$ records where $𝑇$ sends the $𝑗$ -th basis vector of the domain, written in the coordinates of the target, and the entry $𝑎_{𝑖 𝑗}$ is the coefficient of $𝐰_{𝑖}$ in $𝑇 (𝐯_{𝑗})$ . To keep the indices straight, imagine $𝐯_{1}, \dots, 𝐯_{𝑛}$ written above the columns and $𝐰_{1}, \dots, 𝐰_{𝑚}$ written to the left of the rows. The target basis comes first in ${[𝑇]}_{𝒞︀ ℬ︀}$ so that the two copies of $ℬ︀$ sit next to each other in the formula ${[𝑇]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀} =$ ${[𝑇 (𝐯)]}_{𝒞︀}$ of Theorem 2.3.9 below. We always write both subscripts, even when they are equal.

Notation 2.3.2 (The standard basis

ℰ︀

). We write

ℰ︀

for the standard basis

𝐞_{1}, \dots, 𝐞_{𝑘}

𝐹^{𝑘}

(Definition 1.6.8), with

𝑘

determined by the context. Since

𝐲 =

𝑦_{1} 𝐞_{1} +

\dots +

𝑦_{𝑘} 𝐞_{𝑘}

for

𝐲 =

(𝑦_{1}, \dots, 𝑦_{𝑘}) \in

𝐹^{𝑘}

, we have

{[𝐲]}_{ℰ︀} = 𝐲

. That is, in the standard basis a vector of

𝐹^{𝑘}

is its own coordinate vector.

In particular, for a linear map $𝑇 : 𝐹^{𝑛} \to 𝐹^{𝑚}$ , the matrix ${[𝑇]}_{ℰ︀ ℰ︀}$ with respect to the standard bases of $𝐹^{𝑛}$ and $𝐹^{𝑚}$ has the columns $𝑇 (𝐞_{1}),$ $\dots,$ $𝑇 (𝐞_{𝑛})$ .

Example 2.3.3 (Matrices with respect to standard bases).

(a)Let $𝑇 : ℝ^{3} \to ℝ^{2}$ , $𝑇 (𝑥, 𝑦, 𝑧) =$ $(2 𝑥 - 𝑦 + 3 𝑧, 𝑥 + 5 𝑧)$ , the map of Example 2.1.7. Then $𝑇 (𝐞_{1}) = (2, 1)$ , $𝑇 (𝐞_{2}) = (- 1, 0)$ , and $𝑇 (𝐞_{3}) = (3, 5)$ , so
${[𝑇]}_{ℰ︀ ℰ︀} = (\begin{matrix} 2 & - 1 & 3 \\ 1 & 0 & 5 \end{matrix}) .$
This is the matrix $𝐴$ of Example 2.1.7: the coefficient of the $𝑗$ -th variable in the $𝑖$ -th coordinate of $𝑇 (𝑥, 𝑦, 𝑧)$ is the entry in row $𝑖$ and column $𝑗$ . Proposition 2.3.17 shows that this always happens.
(b)The rotation $𝑅_{𝜃}$ of $ℝ^{2}$ by the angle $𝜃$ (Example 2.1.11) sends $𝐞_{1}$ to $(cos 𝜃, sin 𝜃)$ and $𝐞_{2}$ to $(- sin 𝜃, cos 𝜃)$ , so
${[𝑅_{𝜃}]}_{ℰ︀ ℰ︀} = (\begin{matrix} cos 𝜃 & - sin 𝜃 \\ sin 𝜃 & cos 𝜃 \end{matrix}), for example {[𝑅_{𝜋 / 2}]}_{ℰ︀ ℰ︀} = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) .$

Example 2.3.4 (Differentiation). Let $𝑉 = {𝐹 [𝑥]}_{\leq 2}$ . Every element of $𝑉$ is $𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ for exactly one triple $(𝑎, 𝑏, 𝑐) \in 𝐹^{3}$ (Definition 1.2.13, Definition 1.2.16), so $ℬ︀ = 1, 𝑥, 𝑥^{2}$ is a basis of $𝑉$ and ${[𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}]}_{ℬ︀} =$ $(𝑎, 𝑏, 𝑐)$ . Differentiation does not raise degrees, so $𝐷$ maps $𝑉$ into $𝑉$ , and we regard it as an operator $𝐷 \in L (𝑉)$ (Example 2.1.9). Since

𝐷 (1) = 𝟎, 𝐷 (𝑥) = 1, 𝐷 (𝑥^{2}) = 2 𝑥,

whose coordinate vectors are $(0, 0, 0)$ , $(1, 0, 0)$ , and $(0, 2, 0)$ ,

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

Over $𝔽_{2}$ the entry $2$ is $0$ . The domain and the target can also be different spaces. Regarded as a map ${𝐹 [𝑥]}_{\leq 3} \to {𝐹 [𝑥]}_{\leq 2}$ , with the bases ${ℬ︀}^{'} = 1, 𝑥, 𝑥^{2}, 𝑥^{3}$ and $ℬ︀$ , differentiation has the $3 \times 4$ matrix

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

Strictly speaking these are two different linear maps, since their domains differ.

Definition 2.3.5 (Identity matrix). The

𝑛 \times 𝑛

identity matrix

𝐼_{𝑛}

is the matrix with columns

𝐞_{1}, \dots, 𝐞_{𝑛}

. Its entry in row

𝑖

and column

𝑗

1

𝑖 = 𝑗

and

0

𝑖 \neq 𝑗

. We write

𝐼

when

𝑛

is clear from the context.

Example 2.3.6 (The zero map and the identity map). The zero map $0 \in L (𝑉, 𝑊)$ sends each $𝐯_{𝑗}$ to $𝟎$ , whose coordinate vector is $𝟎$ . So ${[0]}_{𝒞︀ ℬ︀}$ is the zero matrix, for all bases. The identity map sends $𝐯_{𝑗}$ to $𝐯_{𝑗} =$ $0 𝐯_{1} +$ $\dots +$ $1 𝐯_{𝑗} +$ $\dots +$ $0 𝐯_{𝑛}$ , whose $ℬ︀$ -coordinate vector is $𝐞_{𝑗}$ . So

{[{id}_{𝑉}]}_{ℬ︀ ℬ︀} = 𝐼_{𝑛} for every basis ℬ︀ of 𝑉 .

Here the same basis is used on both sides. Section 2.3.5 shows that ${[{id}_{𝑉}]}_{𝒞︀ ℬ︀}$ looks quite different when $𝒞︀ \neq ℬ︀$ .

Exercise 2.3.7.routine Let

𝑇 : {𝐹 [𝑥]}_{\leq 1} \to 𝐹^{2}

𝑇 (𝑝) =

(𝑝 (0), 𝑝 (1))

. Find

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

for the basis

ℬ︀ = 1, 𝑥

, and

{[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}}

for the basis

\overset{̊}{ℬ︀} = 1 - 𝑥, 𝑥

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Notation 2.3.2 (The standard basis $ℰ︀$ ), Example 2.1.9 (Maps of polynomials)

Hint 1. Each coordinate of

𝑇 (𝑝)

is an evaluation, so

𝑇

is linear. The columns of

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

are

𝑇 (1)

and

𝑇 (𝑥)

Hint 2. For

\overset{̊}{ℬ︀}

, compute

𝑇 (1 - 𝑥)

and

𝑇 (𝑥)

. You should also check that

\overset{̊}{ℬ︀}

is a basis.

Sketch.

𝑇 (1) = (1, 1)

and

𝑇 (𝑥) = (0, 1)

, so

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

𝑇 (1 - 𝑥) = (1, 0)

and

𝑇 (𝑥) = (0, 1)

, so

{[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}} = 𝐼_{2}

The coordinates of $𝑇 (𝑝)$ are ${ev}_{0} (𝑝)$ and ${ev}_{1} (𝑝)$ , which are linear in $𝑝$ (Example 2.1.9), so $𝑇 (𝑐 𝑝 + 𝑞) =$ $𝑐 𝑇 (𝑝) +$ $𝑇 (𝑞)$ coordinate by coordinate, and $𝑇$ is linear. By Notation 2.3.2, the columns of ${[𝑇]}_{ℰ︀ ℬ︀}$ are $𝑇 (1) = (1, 1)$ and $𝑇 (𝑥) = (0, 1)$ :

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

The list $\overset{̊}{ℬ︀}$ is a basis: $𝑐 (1 - 𝑥) +$ $𝑑 𝑥 =$ $𝑐 +$ $(𝑑 - 𝑐) 𝑥$ equals $𝑎 + 𝑏 𝑥$ exactly when $𝑐 = 𝑎$ and $𝑑 = 𝑎 + 𝑏$ . Since $𝑇 (1 - 𝑥) = (1, 0)$ and $𝑇 (𝑥) = (0, 1)$ ,

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

The same map has two different matrices. In the second basis the coordinates of $𝑝$ are exactly its values at $0$ and $1$ .

2.3.2The matrix–vector product

Suppose we know $𝐴 = {[𝑇]}_{𝒞︀ ℬ︀}$ and the coordinates ${[𝐯]}_{ℬ︀} =$ $(𝑥_{1}, \dots, 𝑥_{𝑛})$ of a vector $𝐯 \in 𝑉$ , and we want the coordinates of $𝑇 (𝐯)$ .

Intuition (Computing ${[𝑇 (𝐯)]}_{𝒞︀}$ ). Since $𝐯 =$ $𝑥_{1} 𝐯_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐯_{𝑛}$ , linearity of $𝑇$ gives $𝑇 (𝐯) =$ $𝑥_{1} 𝑇 (𝐯_{1}) +$ $\dots +$ $𝑥_{𝑛} 𝑇 (𝐯_{𝑛})$ . Taking $𝒞︀$ -coordinates is linear as well (Proposition 1.6.19), so

{[𝑇 (𝐯)]}_{𝒞︀} = 𝑥_{1} {[𝑇 (𝐯_{1})]}_{𝒞︀} + \dots + 𝑥_{𝑛} {[𝑇 (𝐯_{𝑛})]}_{𝒞︀} .

The right side is the linear combination of the columns of $𝐴$ whose coefficients are the entries of ${[𝐯]}_{ℬ︀}$ . Realize that it no longer mentions $𝑇$ , the spaces $𝑉$ and $𝑊$ , or the bases: it is computed from the matrix $𝐴$ and the column $(𝑥_{1}, \dots, 𝑥_{𝑛})$ alone. So it is an operation on a matrix and a column, and we give it a name.

Definition 2.3.8 (Matrix–vector product). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛} \in 𝐹^{𝑚}$ , and let $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ . The product of $𝐴$ and $𝐱$ is

𝐴 𝐱 = 𝑥_{1} 𝐚_{1} + 𝑥_{2} 𝐚_{2} + \dots + 𝑥_{𝑛} 𝐚_{𝑛} \in 𝐹^{𝑚} .

It is defined only when the number of columns of $𝐴$ equals the number of entries of $𝐱$ , and then $𝐴 𝐱$ has as many entries as $𝐴$ has rows.

In words, $𝐴 𝐱$ is the linear combination of the columns of $𝐴$ with coefficients $𝑥_{1}, \dots, 𝑥_{𝑛}$ . With this definition, the computation above becomes a theorem.

Theorem 2.3.9 (The matrix of a map computes the map). For every $𝑇 \in L (𝑉, 𝑊)$ and every $𝐯 \in 𝑉$ ,

{[𝑇]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀} = {[𝑇 (𝐯)]}_{𝒞︀} .

Proof.routine

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 2.3.8 (Matrix–vector product), Definition 1.6.14 (Coordinates), Proposition 1.6.19 (Coordinates respect linear combinations), Definition 2.1.1 (Linear map)

Hint 1. Write

𝐯

in terms of

ℬ︀

, using its coordinates

(𝑥_{1}, \dots, 𝑥_{𝑛}) =

{[𝐯]}_{ℬ︀}

Hint 2. Apply

𝑇

, then take

𝒞︀

-coordinates. Both steps respect linear combinations, and what comes out is a combination of the columns of

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

Sketch. With

{[𝐯]}_{ℬ︀} =

(𝑥_{1}, \dots, 𝑥_{𝑛})

, linearity of

𝑇

and of

{[\cdot]}_{𝒞︀}

gives

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

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

, a combination of the vectors

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

. These are the columns of

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

, so the combination is

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

by Definition 2.3.8.

Let ${[𝐯]}_{ℬ︀} =$ $(𝑥_{1}, \dots, 𝑥_{𝑛})$ , so that $𝐯 =$ $𝑥_{1} 𝐯_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐯_{𝑛}$ (Definition 1.6.14). Then

\begin{aligned} {[𝑇 (𝐯)]}_{𝒞︀} & = {[𝑥_{1} 𝑇 (𝐯_{1}) + \dots + 𝑥_{𝑛} 𝑇 (𝐯_{𝑛})]}_{𝒞︀} & (linearity of 𝑇) \\ = 𝑥_{1} {[𝑇 (𝐯_{1})]}_{𝒞︀} + \dots + 𝑥_{𝑛} {[𝑇 (𝐯_{𝑛})]}_{𝒞︀} & (linearity of {[\cdot]}_{𝒞︀}) \\ = {[𝑇]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀} & (definition of the product), \end{aligned}

since the $𝑗$ -th column of ${[𝑇]}_{𝒞︀ ℬ︀}$ is ${[𝑇 (𝐯_{𝑗})]}_{𝒞︀}$ (Definition 2.3.1). □

So to evaluate $𝑇$ in coordinates, take the $ℬ︀$ -coordinates of $𝐯$ , multiply by the matrix, and read the result as $𝒞︀$ -coordinates. Another way to say this: there are two routes from a vector $𝐯 \in 𝑉$ to a column in $𝐹^{𝑚}$ . One applies $𝑇$ and then takes $𝒞︀$ -coordinates; the other takes $ℬ︀$ -coordinates and then multiplies by $𝐴 = {[𝑇]}_{𝒞︀ ℬ︀}$ . Theorem 2.3.9 says that the two routes always arrive at the same column (Figure 2.3.1). In terms of maps, ${[\cdot]}_{𝒞︀} \circ$ $𝑇 =$ $𝑇_{𝐴} \circ$ ${[\cdot]}_{ℬ︀}$ , where $𝑇_{𝐴}$ is multiplication by $𝐴$ (Definition 2.3.15 below). The map $𝑇_{𝐴}$ does to coordinate vectors what $𝑇$ does to vectors.

Figure 2.3.1. Two routes from

𝑉

𝐹^{𝑚}

, where

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

. Left: the spaces and maps. Right: what happens to a single vector

𝐯

. Going right and then down gives

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

, and going down and then right gives

𝐴 {[𝐯]}_{ℬ︀}

; Theorem 2.3.9 says that these agree.

You have probably met the product $𝐴 𝐱$ before, defined by a formula for its entries. The point here is that its definition is not a convention. Once we record vectors by their coordinates and linear maps by the columns ${[𝑇 (𝐯_{𝑗})]}_{𝒞︀}$ , only one product makes Theorem 2.3.9 true. In fact, the special case of the standard bases already forces it.

Proposition 2.3.10 (The product is forced). Suppose that for all $𝑚, 𝑛 \geq 1$ we are given a rule that assigns to each $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐱 \in 𝐹^{𝑛}$ a vector $𝐴 ⋆ 𝐱 \in 𝐹^{𝑚}$ , such that

{[𝑇]}_{ℰ︀ ℰ︀} ⋆ 𝐱 = 𝑇 (𝐱) for every 𝑇 \in L (𝐹^{𝑛}, 𝐹^{𝑚}) and every 𝐱 \in 𝐹^{𝑛} .

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

Since ${[𝐱]}_{ℰ︀} = 𝐱$ and ${[𝑇 (𝐱)]}_{ℰ︀} = 𝑇 (𝐱)$ , the hypothesis is exactly Theorem 2.3.9 for $𝑉 = 𝐹^{𝑛}$ and $𝑊 = 𝐹^{𝑚}$ with their standard bases, with $⋆$ in place of the product.

Proof.routine

Uses. Corollary 2.2.17 (Linear maps out of $𝐹^{𝑛}$ ), Definition 2.3.1 (Matrix of a linear map), Notation 2.3.2 (The standard basis $ℰ︀$ ), Definition 2.3.8 (Matrix–vector product)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Given

𝐴

and

𝐱

, find a linear map

𝑇 : 𝐹^{𝑛} \to 𝐹^{𝑚}

whose matrix with respect to the standard bases is

𝐴

Hint 2. By Corollary 2.2.17 there is a linear

𝑇

with

𝑇 (𝐞_{𝑗}) = 𝐚_{𝑗}

, the

𝑗

-th column of

𝐴

. That corollary also tells you what

𝑇 (𝐱)

is.

Sketch. Let

𝑇

be the linear map with

𝑇 (𝐞_{𝑗}) = 𝐚_{𝑗}

. Then

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

and

𝑇 (𝐱) =

\sum_{𝑗} 𝑥_{𝑗} 𝐚_{𝑗}

(Corollary 2.2.17), so

𝐴 ⋆ 𝐱 = 𝑇 (𝐱) = 𝐴 𝐱

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and let $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ . By Corollary 2.2.17 there is a linear map $𝑇 : 𝐹^{𝑛} \to 𝐹^{𝑚}$ with $𝑇 (𝐞_{𝑗}) = 𝐚_{𝑗}$ for each $𝑗$ , and $𝑇 (𝐱) =$ $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛}$ . The $𝑗$ -th column of ${[𝑇]}_{ℰ︀ ℰ︀}$ is ${[𝑇 (𝐞_{𝑗})]}_{ℰ︀} = 𝐚_{𝑗}$ (Notation 2.3.2), so ${[𝑇]}_{ℰ︀ ℰ︀} = 𝐴$ . Hence

𝐴 ⋆ 𝐱 = {[𝑇]}_{ℰ︀ ℰ︀} ⋆ 𝐱 = 𝑇 (𝐱) = 𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛} = 𝐴 𝐱 .

□

Matrix multiplication arises the same way in Section 2.4: it is the only product of matrices for which the matrix of a composite is the product of the matrices (Theorem 2.4.2).

The definition describes $𝐴 𝐱$ one column at a time. The familiar formula for its entries is a consequence.

Proposition 2.3.11 (Entries of $𝐴 𝐱$ ). Let $𝐴 =$ $(𝑎_{𝑖 𝑗}) \in$ $𝐹^{𝑚 \times 𝑛}$ and $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑛}) \in$ $𝐹^{𝑛}$ . For $𝑖 = 1, \dots, 𝑚$ , the $𝑖$ -th entry of $𝐴 𝐱$ is

𝑎_{𝑖 1} 𝑥_{1} + 𝑎_{𝑖 2} 𝑥_{2} + \dots + 𝑎_{𝑖 𝑛} 𝑥_{𝑛} = \sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} .

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. What is the

𝑖

-th entry of the

𝑗

-th column

𝐚_{𝑗}

Hint 2. Vectors in

𝐹^{𝑚}

are added and scaled entry by entry.

Sketch. The

𝑖

-th entry of

𝐚_{𝑗}

𝑎_{𝑖 𝑗}

, so the

𝑖

-th entry of

𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛}

𝑥_{1} 𝑎_{𝑖 1} +

\dots +

𝑥_{𝑛} 𝑎_{𝑖 𝑛}

The

𝑗

-th column

𝐚_{𝑗}

has

𝑖

-th entry

𝑎_{𝑖 𝑗}

. Since the operations of

𝐹^{𝑚}

are entrywise (Definition 1.2.4), the

𝑖

-th entry of

𝐴 𝐱 =

𝑥_{1} 𝐚_{1} +

\dots +

𝑥_{𝑛} 𝐚_{𝑛}

𝑥_{1} 𝑎_{𝑖 1} +

\dots +

𝑥_{𝑛} 𝑎_{𝑖 𝑛} =

𝑎_{𝑖 1} 𝑥_{1} +

\dots +

𝑎_{𝑖 𝑛} 𝑥_{𝑛}

. □

This is the row-times-column rule: the $𝑖$ -th entry of $𝐴 𝐱$ pairs row $𝑖$ of $𝐴$ with $𝐱$ , multiplying entries in matching positions and adding. So there are two ways to read $𝐴 𝐱$ . By columns, it is a linear combination of the columns of $𝐴$ , and this is the view to remember for proofs. By rows, it is a list of $𝑚$ numbers, each computed from one row of $𝐴$ . This is usually quicker by hand, and it is how Section 3.1 reads a system of equations.

Example 2.3.12 (A product computed two ways). Let $𝐴 = (\begin{matrix} 1 & - 2 & 0 \\ 3 & 1 & 4 \end{matrix}) \in ℝ^{2 \times 3}$ and $𝐱 = (2, 1, - 1)$ . By columns,

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

By rows, the first entry is $1 \cdot$ $2 +$ $(- 2) \cdot$ $1 +$ $0 \cdot$ $(- 1) =$ $0$ and the second is $3 \cdot 2 + 1 \cdot 1 + 4 \cdot (- 1) = 3$ .

Proposition 2.3.13 (Linearity of the product). Let

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

𝐱, 𝐲 \in 𝐹^{𝑛}

, and

𝑐 \in 𝐹

, and let

𝐚_{𝑗}

be the

𝑗

-th column of

𝐴

(a) $𝐴 (𝑐 𝐱 + 𝐲) =$ $𝑐 𝐴 𝐱 +$ $𝐴 𝐲$ .
(b) $(𝑐 𝐴 + 𝐴^{'}) 𝐱 =$ $𝑐 𝐴 𝐱 +$ $𝐴^{'} 𝐱$ .
(c) $𝐴 𝐞_{𝑗} = 𝐚_{𝑗}$ for $𝑗 = 1, \dots, 𝑛$ , and $𝐼_{𝑛} 𝐱 = 𝐱$ .

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Definition 1.2.7 (Matrices), Definition 2.3.5 (Identity matrix), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. Write each side as a combination of columns using Definition 2.3.8, and regroup with the vector space axioms of

𝐹^{𝑚}

Hint 2. For (b), what are the columns of

𝑐 𝐴 + 𝐴^{'}

? For (c), what are the entries of

𝐞_{𝑗}

Sketch. (a) Expand

\sum_{𝑗} (𝑐 𝑥_{𝑗} + 𝑦_{𝑗}) 𝐚_{𝑗}

and regroup. (b) Matrices are added and scaled entrywise, so the

𝑗

-th column of

𝑐 𝐴 + 𝐴^{'}

𝑐 𝐚_{𝑗} + 𝐚_{𝑗}^{'}

; expand

\sum_{𝑗} 𝑥_{𝑗} (𝑐 𝐚_{𝑗} + 𝐚_{𝑗}^{'})

and regroup. (c)

𝐞_{𝑗}

has a single nonzero entry, a

1

in position

𝑗

, and

𝐼_{𝑛}

has columns

𝐞_{1}, \dots, 𝐞_{𝑛}

(a) The vector $𝑐 𝐱 + 𝐲$ has entries $𝑐 𝑥_{𝑗} + 𝑦_{𝑗}$ (Definition 1.2.4), so by Definition 2.3.8 and the vector space axioms of $𝐹^{𝑚}$ ,

𝐴 (𝑐 𝐱 + 𝐲) = \sum_{𝑗 = 1}^{𝑛} (𝑐 𝑥_{𝑗} + 𝑦_{𝑗}) 𝐚_{𝑗} = 𝑐 \sum_{𝑗 = 1}^{𝑛} 𝑥_{𝑗} 𝐚_{𝑗} + \sum_{𝑗 = 1}^{𝑛} 𝑦_{𝑗} 𝐚_{𝑗} = 𝑐 𝐴 𝐱 + 𝐴 𝐲 .

(b) Let $𝐚_{𝑗}^{'}$ be the $𝑗$ -th column of $𝐴^{'}$ . Matrices are added and scaled entrywise (Definition 1.2.7), so the $𝑗$ -th column of $𝑐 𝐴 + 𝐴^{'}$ is $𝑐 𝐚_{𝑗} + 𝐚_{𝑗}^{'}$ . Hence

(𝑐 𝐴 + 𝐴^{'}) 𝐱 = \sum_{𝑗 = 1}^{𝑛} 𝑥_{𝑗} (𝑐 𝐚_{𝑗} + 𝐚_{𝑗}^{'}) = 𝑐 \sum_{𝑗 = 1}^{𝑛} 𝑥_{𝑗} 𝐚_{𝑗} + \sum_{𝑗 = 1}^{𝑛} 𝑥_{𝑗} 𝐚_{𝑗}^{'} = 𝑐 𝐴 𝐱 + 𝐴^{'} 𝐱 .

(c) The entries of $𝐞_{𝑗}$ are $0$ except for a $1$ in position $𝑗$ , so $𝐴 𝐞_{𝑗} =$ $0 𝐚_{1} +$ $\dots +$ $1 𝐚_{𝑗} +$ $\dots +$ $0 𝐚_{𝑛} =$ $𝐚_{𝑗}$ . The columns of $𝐼_{𝑛}$ are $𝐞_{1}, \dots, 𝐞_{𝑛}$ (Definition 2.3.5), so $𝐼_{𝑛} 𝐱 =$ $𝑥_{1} 𝐞_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐞_{𝑛} =$ $𝐱$ . □

Part (c) says that multiplying by $𝐞_{𝑗}$ picks out the $𝑗$ -th column. It is the quickest way to get information about $𝐴$ out of the products $𝐴 𝐱$ .

Exercise 2.3.14.routine Compute each product by columns and by rows.

(a) $(\begin{matrix} 1 & 2 & 3 \\ 4 & 0 & 1 \end{matrix}) (\begin{matrix} 2 \\ 1 \\ 4 \end{matrix})$ over $𝔽_{5}$ .
(b) $(\begin{matrix} 1 & 𝑖 \\ - 𝑖 & 2 \end{matrix}) (\begin{matrix} 𝑖 \\ 1 \end{matrix})$ over $ℂ$ .

Solution.

Uses. Definition 2.3.8 (Matrix–vector product), Proposition 2.3.11 (Entries of $𝐴 𝐱$ )

Hint 1. By columns:

2

times the first column, plus

1

times the second, plus

4

times the third. Reduce modulo

5

at the end.

Hint 2. By rows: each entry pairs one row with the vector. In (b),

𝑖 \cdot 𝑖 = - 1

Sketch. (a) Both ways give

(16, 12)

, which is

(1, 2)

𝔽_{5}^{2}

. By rows,

2 + 2 + 12 = 16

and

8 + 0 + 4 = 12

. (b)

𝑖 (1, - 𝑖) +

(𝑖, 2) =

(2 𝑖, 3)

, and by rows

𝑖 + 𝑖 = 2 𝑖

and

- 𝑖^{2} + 2 = 3

(a) By columns, in $𝔽_{5}^{2}$ ,

2 (\begin{matrix} 1 \\ 4 \end{matrix}) + 1 (\begin{matrix} 2 \\ 0 \end{matrix}) + 4 (\begin{matrix} 3 \\ 1 \end{matrix}) = (\begin{matrix} 2 + 2 + 12 \\ 8 + 0 + 4 \end{matrix}) = (\begin{matrix} 16 \\ 12 \end{matrix}) = (\begin{matrix} 1 \\ 2 \end{matrix}) .

By rows, the first entry is $1 \cdot 2 + 2 \cdot 1 + 3 \cdot 4 = 16 = 1$ and the second is $4 \cdot 2 + 0 \cdot 1 + 1 \cdot 4 = 12 = 2$ .

(b) By columns,

𝑖 (\begin{matrix} 1 \\ - 𝑖 \end{matrix}) + 1 (\begin{matrix} 𝑖 \\ 2 \end{matrix}) = (\begin{matrix} 𝑖 \\ 1 \end{matrix}) + (\begin{matrix} 𝑖 \\ 2 \end{matrix}) = (\begin{matrix} 2 𝑖 \\ 3 \end{matrix}),

using $𝑖 (- 𝑖) = - 𝑖^{2} = 1$ . By rows, the entries are $1 \cdot 𝑖 + 𝑖 \cdot 1 = 2 𝑖$ and $(- 𝑖) \cdot$ $𝑖 +$ $2 \cdot$ $1 =$ $1 +$ $2 =$ $3$ .

2.3.3Matrices as linear maps

Fixing the matrix and letting the vector vary turns the product into a function.

Definition 2.3.15 (The linear map of a matrix). For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , the map $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ is

𝑇_{𝐴} (𝐱) = 𝐴 𝐱 .

The map $𝑇_{𝐴}$ is linear by Proposition 2.3.13(a). By Proposition 2.3.11, the $𝑖$ -th coordinate of $𝑇_{𝐴} (𝐱)$ is $𝑎_{𝑖 1} 𝑥_{1} +$ $\dots +$ $𝑎_{𝑖 𝑛} 𝑥_{𝑛}$ , so $𝑇_{𝐴}$ is the map given by a linear formula in Example 2.1.7, and the two definitions of $𝑇_{𝐴}$ agree. So a matrix can be regarded either as a table of scalars or as a linear map. The next two results show that the two views carry the same information.

Proposition 2.3.16 (The matrix of

𝑇_{𝐴}

). For every

𝐴 \in 𝐹^{𝑚 \times 𝑛}

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

Proof.routine

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 2.3.15 (The linear map of a matrix), Proposition 2.3.13 (Linearity of the product), Notation 2.3.2 (The standard basis $ℰ︀$ )

Hint 1. What is the

𝑗

-th column of

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

Hint 2. Compute

𝑇_{𝐴} (𝐞_{𝑗}) = 𝐴 𝐞_{𝑗}

with Proposition 2.3.13(c).

Sketch. The

𝑗

-th column of

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

{[𝐴 𝐞_{𝑗}]}_{ℰ︀} =

𝐴 𝐞_{𝑗} =

𝐚_{𝑗}

By Definition 2.3.1 and Notation 2.3.2, the

𝑗

-th column of

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

{[𝑇_{𝐴} (𝐞_{𝑗})]}_{ℰ︀} =

𝑇_{𝐴} (𝐞_{𝑗}) =

𝐴 𝐞_{𝑗}

, which is the

𝑗

-th column of

𝐴

by Proposition 2.3.13(c). So the two matrices have the same columns. □

Proposition 2.3.17 (Every linear map

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

is some

𝑇_{𝐴}

). For every

𝑇 \in L (𝐹^{𝑛}, 𝐹^{𝑚})

there is exactly one

𝐴 \in 𝐹^{𝑚 \times 𝑛}

with

𝑇 = 𝑇_{𝐴}

, namely

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

, the matrix whose columns are

𝑇 (𝐞_{1}),

\dots,

𝑇 (𝐞_{𝑛})

Proof.routine

Uses. Theorem 2.3.9 (The matrix of a map computes the map), Notation 2.3.2 (The standard basis $ℰ︀$ ), Proposition 2.3.13 (Linearity of the product)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For existence, apply Theorem 2.3.9 with the standard bases on both sides. What are

{[𝐱]}_{ℰ︀}

and

{[𝑇 (𝐱)]}_{ℰ︀}

Hint 2. For uniqueness, suppose that

𝑇_{𝐴} = 𝑇_{𝐴^{'}}

, and evaluate both maps at

𝐞_{𝑗}

Sketch. With

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

, Theorem 2.3.9 gives

𝑇 (𝐱) =

𝐴 {[𝐱]}_{ℰ︀} =

𝐴 𝐱

, since standard coordinates do nothing. If

𝑇_{𝐴} = 𝑇_{𝐴^{'}}

, then

𝐴 𝐞_{𝑗} = 𝐴^{'} 𝐞_{𝑗}

, so

𝐴

and

𝐴^{'}

have the same

𝑗

-th column for every

𝑗

Existence. Let $𝐴 = {[𝑇]}_{ℰ︀ ℰ︀}$ . Its columns are ${[𝑇 (𝐞_{𝑗})]}_{ℰ︀} =$ $𝑇 (𝐞_{𝑗})$ (Notation 2.3.2). For $𝐱 \in 𝐹^{𝑛}$ , Theorem 2.3.9 with the standard bases of $𝐹^{𝑛}$ and $𝐹^{𝑚}$ gives

𝑇 (𝐱) = {[𝑇 (𝐱)]}_{ℰ︀} = {[𝑇]}_{ℰ︀ ℰ︀} {[𝐱]}_{ℰ︀} = 𝐴 𝐱 = 𝑇_{𝐴} (𝐱) .

So $𝑇 = 𝑇_{𝐴}$ .

Uniqueness. Suppose $𝑇_{𝐴} = 𝑇_{𝐴^{'}}$ for some $𝐴, 𝐴^{'} \in 𝐹^{𝑚 \times 𝑛}$ . By Proposition 2.3.13(c), for each $𝑗$ the $𝑗$ -th columns of $𝐴$ and $𝐴^{'}$ are

𝐴 𝐞_{𝑗} = 𝑇_{𝐴} (𝐞_{𝑗}) = 𝑇_{𝐴^{'}} (𝐞_{𝑗}) = 𝐴^{'} 𝐞_{𝑗} .

So $𝐴$ and $𝐴^{'}$ have the same columns, and $𝐴 = 𝐴^{'}$ . □

Together with Proposition 2.3.16, this says that $𝐴 \mapsto 𝑇_{𝐴}$ and $𝑇 \mapsto {[𝑇]}_{ℰ︀ ℰ︀}$ are inverse bijections between $𝐹^{𝑚 \times 𝑛}$ and $L (𝐹^{𝑛}, 𝐹^{𝑚})$ . Two consequences are worth spelling out. First, the linear maps $𝐹^{𝑛} \to 𝐹^{𝑚}$ are exactly the maps given by linear formulas, which makes precise the rule of thumb at the end of Section 2.1.3. Second, finding the matrix of a linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ requires no formula at all: compute $𝑇 (𝐞_{1}),$ $\dots,$ $𝑇 (𝐞_{𝑛})$ and write them down as columns. From now on we often say “the matrix $𝐴$ ” for the map $𝑇_{𝐴}$ , and write $𝐴 𝐱$ rather than $𝑇_{𝐴} (𝐱)$ .

Exercise 2.3.18.routine For each linear map $𝑇$ , find the matrix $𝐴$ with $𝑇 = 𝑇_{𝐴}$ .

(a) $𝑇 : ℝ^{3} \to ℝ^{3}$ , $𝑇 (𝑥, 𝑦, 𝑧) =$ $(𝑧, 𝑥, 𝑦)$ .
(b) $𝑇 : ℝ^{3} \to ℝ^{3}$ , the projection $(𝑥, 𝑦, 𝑧) \mapsto$ $(𝑥, 𝑦, 0)$ onto the $𝑥 𝑦$ -plane.
(c) $𝑇 : ℝ^{3} \to ℝ$ , $𝑇 (𝑥, 𝑦, 𝑧) =$ $𝑥 +$ $𝑦 +$ $𝑧$ .
(d) $𝑇 : 𝔽_{2}^{2} \to 𝔽_{2}^{2}$ , the linear map with $𝑇 (1, 0) = (1, 1)$ and $𝑇 (0, 1) = (0, 1)$ . What is $𝑇 (1, 1)$ ?

Solution.

Uses. Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ ), Definition 2.3.8 (Matrix–vector product)

Hint 1. By Proposition 2.3.17, the columns of

𝐴

are

𝑇 (𝐞_{1}),

\dots,

𝑇 (𝐞_{𝑛})

. No formula for the entries is needed.

Hint 2. In (c) the target is

ℝ = ℝ^{1}

, so

𝐴

has one row. In (d),

𝑇 (1, 1) = 𝐴 (1, 1)

is the sum of the two columns.

Sketch. (a) Columns

𝐞_{2}, 𝐞_{3}, 𝐞_{1}

. (b) Columns

𝐞_{1}, 𝐞_{2}, 𝟎

. (c)

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

. (d)

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

, and

𝑇 (1, 1) =

(1, 1) +

(0, 1) =

(1, 0)

By Proposition 2.3.17, $𝐴$ is the matrix with columns $𝑇 (𝐞_{1}),$ $\dots,$ $𝑇 (𝐞_{𝑛})$ .

(a) $𝑇 (𝐞_{1}) = (0, 1, 0)$ , $𝑇 (𝐞_{2}) = (0, 0, 1)$ , and $𝑇 (𝐞_{3}) = (1, 0, 0)$ , so $𝐴 = (\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ .

(b) $𝑇 (𝐞_{1}) = 𝐞_{1}$ , $𝑇 (𝐞_{2}) = 𝐞_{2}$ , and $𝑇 (𝐞_{3}) = 𝟎$ , so $𝐴 = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix})$ .

(c) $𝑇 (𝐞_{1}) =$ $𝑇 (𝐞_{2}) =$ $𝑇 (𝐞_{3}) =$ $1$ , so $𝐴$ is the $1 \times 3$ matrix $(\begin{matrix} 1 & 1 & 1 \end{matrix})$ .

(d) $𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ . By Definition 2.3.8, $𝑇 (1, 1) =$ $𝐴 (1, 1) =$ $(1, 1) +$ $(0, 1) =$ $(1, 2) =$ $(1, 0)$ in $𝔽_{2}^{2}$ . So $𝑇$ swaps $(1, 0)$ and $(1, 1)$ and fixes $(0, 1)$ .

Example 2.3.19 (Projection and reflection). Let $ℓ$ be the line $𝑦 = 2 𝑥$ in $ℝ^{2}$ . It passes through $𝟎$ at the angle $𝜃$ with $cos 𝜃 = 1 / \sqrt{5}$ and $sin 𝜃 = 2 / \sqrt{5}$ , so ${cos}^{2} 𝜃 = 1 / 5$ , $sin 𝜃 cos 𝜃 = 2 / 5$ , ${sin}^{2} 𝜃 = 4 / 5$ , $cos 2 𝜃 = - 3 / 5$ , and $sin 2 𝜃 = 4 / 5$ . By the formulas of Example 2.1.11, the projection onto $ℓ$ and the reflection across $ℓ$ satisfy

\begin{aligned} {Pr}_{ℓ} (𝐞_{1}) & = (\frac{1}{5}, \frac{2}{5}), & {Pr}_{ℓ} (𝐞_{2}) & = (\frac{2}{5}, \frac{4}{5}), \\ 𝑆_{ℓ} (𝐞_{1}) & = (- \frac{3}{5}, \frac{4}{5}), & 𝑆_{ℓ} (𝐞_{2}) & = (\frac{4}{5}, \frac{3}{5}) . \end{aligned}

These are the columns of their matrices:

{[{Pr}_{ℓ}]}_{ℰ︀ ℰ︀} = \frac{1}{5} (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix}), {[𝑆_{ℓ}]}_{ℰ︀ ℰ︀} = \frac{1}{5} (\begin{matrix} - 3 & 4 \\ 4 & 3 \end{matrix}) .

The plane transformer below shows the reflection. Its panel displays the matrix $𝐴$ , and its two handles are the columns $𝐴 𝐞_{1}$ and $𝐴 𝐞_{2}$ , that is, the images of $𝐞_{1}$ and $𝐞_{2}$ . Dragging a handle changes one column of $𝐴$ and leaves the other alone, and the whole grid follows, because $𝐴 (𝑥, 𝑦) =$ $𝑥 𝐴 𝐞_{1} +$ $𝑦 𝐴 𝐞_{2}$ .

The reflection across the line

𝑦 = 2 𝑥

. Its matrix has columns

𝐴 𝐞_{1} = (- 0.6, 0.8)

and

𝐴 𝐞_{2} = (0.8, 0.6)

. Type the entries

0.2, 0.4, 0.4, 0.8

for the projection onto the same line, which flattens the grid onto it, or

0, - 1, 1, 0

for the rotation by a right angle. In each case the columns of the matrix are where

𝐞_{1}

and

𝐞_{2}

go.

For general $𝑉$ and $𝑊$ the same holds once the bases are fixed: a linear map is determined by its matrix, and every matrix of the right size is the matrix of some linear map.

Theorem 2.3.20 (Linear maps correspond to matrices). Let

ℬ︀

be a basis of

𝑉

of length

𝑛

and

𝒞︀

a basis of

𝑊

of length

𝑚

(a)If $𝑆, 𝑇 \in L (𝑉, 𝑊)$ and ${[𝑆]}_{𝒞︀ ℬ︀} =$ ${[𝑇]}_{𝒞︀ ℬ︀}$ , then $𝑆 = 𝑇$ .
(b)For every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ there is a $𝑇 \in L (𝑉, 𝑊)$ with ${[𝑇]}_{𝒞︀ ℬ︀} = 𝐴$ .

That is,

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

is a bijection from

L (𝑉, 𝑊)

onto

𝐹^{𝑚 \times 𝑛}

Intuition. For

𝑉 = 𝐹^{𝑛}

and

𝑊 = 𝐹^{𝑚}

with their standard bases, this is Proposition 2.3.17 together with Proposition 2.3.16. In general there are two natural strategies. One is to notice that the matrix is another way of writing the list

𝑇 (𝐯_{1}),

\dots,

𝑇 (𝐯_{𝑛})

, which determines

𝑇

by Section 2.2. The other is to move the problem into

𝐹^{𝑛}

and

𝐹^{𝑚}

with coordinates, where the special case applies, and move back. The first proof is shorter. The second exhibits every

𝑇

as some

𝑇_{𝐴}

in disguise, which is the picture of Figure 2.3.1.

Proof (via lists).routine

Uses. Theorem 2.2.1 (Linear maps are determined by a basis), Definition 1.6.14 (Coordinates), Definition 2.3.1 (Matrix of a linear map)

Hint 1. Two matrices are equal when their columns are equal. What does equality of the

𝑗

-th columns of

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

and

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

say about

𝑆 (𝐯_{𝑗})

and

𝑇 (𝐯_{𝑗})

Hint 2. For (b), the

𝑗

-th column of

𝐴

is the

𝒞︀

-coordinate vector of exactly one vector

𝐲_{𝑗} \in 𝑊

. Send

𝐯_{𝑗}

there.

Sketch. (a) Equal columns mean

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

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

, so

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

for all

𝑗

, and

𝑆 = 𝑇

by uniqueness in Theorem 2.2.1. (b) Let

𝐲_{𝑗} =

\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝐰_{𝑖}

; the linear map with

𝑇 (𝐯_{𝑗}) = 𝐲_{𝑗}

has

𝑗

-th column

{[𝐲_{𝑗}]}_{𝒞︀} = 𝐚_{𝑗}

(a) Suppose ${[𝑆]}_{𝒞︀ ℬ︀} =$ ${[𝑇]}_{𝒞︀ ℬ︀}$ . Comparing $𝑗$ -th columns, ${[𝑆 (𝐯_{𝑗})]}_{𝒞︀} =$ ${[𝑇 (𝐯_{𝑗})]}_{𝒞︀}$ for each $𝑗$ . A vector of $𝑊$ is determined by its coordinates: if ${[𝐰]}_{𝒞︀} =$ $(𝑐_{1}, \dots, 𝑐_{𝑚})$ , then $𝐰 =$ $𝑐_{1} 𝐰_{1} +$ $\dots +$ $𝑐_{𝑚} 𝐰_{𝑚}$ (Definition 1.6.14). So $𝑆 (𝐯_{𝑗}) = 𝑇 (𝐯_{𝑗})$ for every $𝑗$ , and $𝑆 = 𝑇$ by the uniqueness part of Theorem 2.2.1.

(b) Let $𝐚_{1}, \dots, 𝐚_{𝑛}$ be the columns of $𝐴$ , and let $𝐲_{𝑗} =$ $𝑎_{1 𝑗} 𝐰_{1} +$ $\dots +$ $𝑎_{𝑚 𝑗} 𝐰_{𝑚} \in$ $𝑊$ , so that ${[𝐲_{𝑗}]}_{𝒞︀} = 𝐚_{𝑗}$ . By Theorem 2.2.1 there is a linear map $𝑇 : 𝑉 \to 𝑊$ with $𝑇 (𝐯_{𝑗}) = 𝐲_{𝑗}$ for each $𝑗$ . The $𝑗$ -th column of ${[𝑇]}_{𝒞︀ ℬ︀}$ is ${[𝐲_{𝑗}]}_{𝒞︀} = 𝐚_{𝑗}$ , so ${[𝑇]}_{𝒞︀ ℬ︀} = 𝐴$ . □

Proof (via coordinates).routine

Uses. Theorem 2.3.9 (The matrix of a map computes the map), Example 2.1.8 (Coordinates), Proposition 1.6.19 (Coordinates respect linear combinations), Definition 2.3.15 (The linear map of a matrix), Proposition 2.1.17 (Compositions of linear maps are linear)

Techniques. Assemble linear maps from linear pieces (Technique 2.1.26)

Hint 1. Let

Φ : 𝐹^{𝑚} \to 𝑊

be the map

(𝑦_{1}, \dots, 𝑦_{𝑚}) \mapsto

𝑦_{1} 𝐰_{1} +

\dots +

𝑦_{𝑚} 𝐰_{𝑚}

. How are

Φ

and

{[\cdot]}_{𝒞︀}

related?

Hint 2. For (a), use Theorem 2.3.9 to compare

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

and

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

. For (b), try

𝑇 = Φ \circ 𝑇_{𝐴} \circ {[\cdot]}_{ℬ︀}

Sketch.

Φ

and

{[\cdot]}_{𝒞︀}

undo each other. (a) Both

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

and

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

equal

𝐴 {[𝐯]}_{ℬ︀}

; apply

Φ

. (b)

𝑇 = Φ \circ 𝑇_{𝐴} \circ {[\cdot]}_{ℬ︀}

is a composite of linear maps, and

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

𝐴 𝐞_{𝑗} =

𝐚_{𝑗}

Let $Φ : 𝐹^{𝑚} \to 𝑊$ be the linear map $(𝑦_{1}, \dots, 𝑦_{𝑚}) \mapsto$ $𝑦_{1} 𝐰_{1} +$ $\dots +$ $𝑦_{𝑚} 𝐰_{𝑚}$ of Example 2.1.8. It undoes $𝒞︀$ -coordinates in both orders: $Φ ({[𝐰]}_{𝒞︀}) = 𝐰$ for $𝐰 \in 𝑊$ , and ${[Φ (𝐲)]}_{𝒞︀} = 𝐲$ for $𝐲 \in 𝐹^{𝑚}$ .

(a) Let $𝐴 =$ ${[𝑆]}_{𝒞︀ ℬ︀} =$ ${[𝑇]}_{𝒞︀ ℬ︀}$ . For $𝐯 \in 𝑉$ , Theorem 2.3.9 gives

{[𝑆 (𝐯)]}_{𝒞︀} = 𝐴 {[𝐯]}_{ℬ︀} = {[𝑇 (𝐯)]}_{𝒞︀},

and applying $Φ$ gives $𝑆 (𝐯) = 𝑇 (𝐯)$ .

(b) Define $𝑇 = Φ \circ 𝑇_{𝐴} \circ {[\cdot]}_{ℬ︀}$ , that is, $𝑇 (𝐯) =$ $Φ (𝐴 {[𝐯]}_{ℬ︀})$ . It is a composite of linear maps (Proposition 1.6.19, Definition 2.3.15, Example 2.1.8), so it is linear by Proposition 2.1.17. Since ${[𝐯_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}$ ,

{[𝑇 (𝐯_{𝑗})]}_{𝒞︀} = {[Φ (𝐴 𝐞_{𝑗})]}_{𝒞︀} = 𝐴 𝐞_{𝑗} = 𝐚_{𝑗},

so the $𝑗$ -th column of ${[𝑇]}_{𝒞︀ ℬ︀}$ is the $𝑗$ -th column of $𝐴$ . □

The second proof shows what an arbitrary linear map looks like through coordinates. By (a), every $𝑇 \in L (𝑉, 𝑊)$ is the map built in (b) from its own matrix: $𝑇 = Φ \circ 𝑇_{𝐴} \circ {[\cdot]}_{ℬ︀}$ with $𝐴 = {[𝑇]}_{𝒞︀ ℬ︀}$ . Read from right to left, this says: take coordinates, multiply by the matrix, and turn the resulting coordinates back into a vector. In Section 2.4 we will see that the bijection $𝑇 \mapsto {[𝑇]}_{𝒞︀ ℬ︀}$ also respects addition and scalar multiplication and turns composition into matrix multiplication. So $L (𝑉, 𝑊)$ and $𝐹^{𝑚 \times 𝑛}$ are isomorphic vector spaces (Section 4.5).

Exercise 2.3.21.routine Let $ℬ︀ = 1, 𝑥$ and $𝒞︀ = 1, 1 + 𝑥$ , both bases of ${𝐹 [𝑥]}_{\leq 1}$ , and let $𝑇 \in L ({𝐹 [𝑥]}_{\leq 1})$ be the operator with

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

Find $𝑇 (𝑎 + 𝑏 𝑥)$ , and find ${[𝑇]}_{ℬ︀ ℬ︀}$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.3.20 (Linear maps correspond to matrices), Theorem 2.2.1 (Linear maps are determined by a basis)

Hint 1. The columns say what

𝑇 (1)

and

𝑇 (𝑥)

are, in

𝒞︀

-coordinates. Turn them back into polynomials.

Hint 2. Then

𝑇 (𝑎 + 𝑏 𝑥) =

𝑎 𝑇 (1) +

𝑏 𝑇 (𝑥)

. For

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

, write

𝑇 (1)

and

𝑇 (𝑥)

in the basis

1, 𝑥

Sketch.

𝑇 (1) =

1 \cdot

1 +

0 \cdot

(1 + 𝑥) =

1

and

𝑇 (𝑥) =

2 \cdot

1 +

1 \cdot

(1 + 𝑥) =

3 +

𝑥

. So

𝑇 (𝑎 + 𝑏 𝑥) =

(𝑎 + 3 𝑏) +

𝑏 𝑥

and

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

$𝒞︀$ is a basis, since $𝑎 +$ $𝑏 𝑥 =$ $(𝑎 - 𝑏) \cdot$ $1 +$ $𝑏 (1 + 𝑥)$ , and these are the only possible coefficients. By Definition 2.3.1, the first column says $𝑇 (1) =$ $1 \cdot$ $1 +$ $0 \cdot$ $(1 + 𝑥) =$ $1$ , and the second says $𝑇 (𝑥) =$ $2 \cdot$ $1 +$ $1 \cdot$ $(1 + 𝑥) =$ $3 +$ $𝑥$ . By linearity,

𝑇 (𝑎 + 𝑏 𝑥) = 𝑎 𝑇 (1) + 𝑏 𝑇 (𝑥) = (𝑎 + 3 𝑏) + 𝑏 𝑥 .

(By Theorem 2.3.20, this is the only operator with the given matrix.) In the basis $ℬ︀$ , $𝑇 (1) = 1$ has coordinates $(1, 0)$ and $𝑇 (𝑥) = 3 + 𝑥$ has coordinates $(3, 1)$ , so

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

2.3.4Different bases, different matrices

The matrix ${[𝑇]}_{𝒞︀ ℬ︀}$ depends on three things: the map $𝑇$ , the basis $ℬ︀$ , and the basis $𝒞︀$ . Changing either basis, even by reordering it, can change the matrix, and one map can have matrices that look nothing alike.

Example 2.3.22 (Differentiation in four bases). Let $𝑉 = {𝐹 [𝑥]}_{\leq 2}$ , and let $𝐷 \in L (𝑉)$ be differentiation, as in Example 2.3.4.

(a)For $ℬ︀ = 1, 𝑥, 𝑥^{2}$ , we found
${[𝐷]}_{ℬ︀ ℬ︀} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{matrix}) .$
(b)Reverse the order: $ℛ︀ = 𝑥^{2}, 𝑥, 1$ . Now $𝐷 (𝑥^{2}) = 2 𝑥$ , $𝐷 (𝑥) = 1$ , and $𝐷 (1) = 𝟎$ have the $ℛ︀$ -coordinates $(0, 2, 0)$ , $(0, 0, 1)$ , and $(0, 0, 0)$ , so
${[𝐷]}_{ℛ︀ ℛ︀} = (\begin{matrix} 0 & 0 & 0 \\ 2 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) .$
The vectors are the same as in (a), but a basis is a list, and its order matters.
(c)Suppose that $2 \neq 0$ in $𝐹$ , and let $\overset{̊}{ℬ︀} = 1, 𝑥, \frac{1}{2} 𝑥^{2}$ . This is a basis, since $𝑎 +$ $𝑏 𝑥 +$ $𝑐 𝑥^{2} =$ $𝑎 \cdot$ $1 +$ $𝑏 𝑥 +$ $2 𝑐 \cdot$ $\frac{1}{2} 𝑥^{2}$ , with only these coefficients possible. Now $𝐷 (\frac{1}{2} 𝑥^{2}) = 𝑥$ , so
${[𝐷]}_{\overset{̊}{ℬ︀} \overset{̊}{ℬ︀}} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) .$
Each basis vector goes to the one before it, and the first goes to $𝟎$ .
(d)Keep the assumption $2 \neq 0$ , and use different bases on the two sides: ${ℬ︀}^{'} = 𝑥, \frac{1}{2} 𝑥^{2}, 1$ in the domain and $ℬ︀ = 1, 𝑥, 𝑥^{2}$ in the target. Then $𝐷 (𝑥) = 1$ , $𝐷 (\frac{1}{2} 𝑥^{2}) = 𝑥$ , and $𝐷 (1) = 𝟎$ have the $ℬ︀$ -coordinates $𝐞_{1}$ , $𝐞_{2}$ , and $𝟎$ , so
${[𝐷]}_{ℬ︀ {ℬ︀}^{'}} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}) .$

Intuition (One basis or two). The matrix in (d) is the matrix of the projection $(𝑥_{1}, 𝑥_{2}, 𝑥_{3}) \mapsto$ $(𝑥_{1}, 𝑥_{2}, 0)$ of $𝐹^{3}$ , a map $𝑃$ with $𝑃 \circ 𝑃 = 𝑃$ . But $𝐷$ is nothing like that: $𝐷 (𝐷 (𝐷 (𝑝))) = 𝟎$ for every $𝑝 \in 𝑉$ , since each application of $𝐷$ lowers the degree. Using different bases on the two sides gives so much freedom that the matrix forgets almost everything about $𝐷$ . What survives is how many independent values $𝐷$ takes, its rank (Section 4.2, and Theorem 3.5.27 for matrices).

For an operator $𝑇 \in L (𝑉)$ , comparing $𝑇 (𝐯)$ with $𝐯$ only makes sense in a single coordinate system, so we use the same basis on both sides, and then more survives. Let $𝑁$ be any of the three matrices in (a)–(c), with its basis $𝒜︀$ . Applying Theorem 2.3.9 three times,

𝑁 (𝑁 (𝑁 {[𝑝]}_{𝒜︀})) = 𝑁 (𝑁 {[𝐷 (𝑝)]}_{𝒜︀}) = 𝑁 {[𝐷 (𝐷 (𝑝))]}_{𝒜︀} = {[𝐷 (𝐷 (𝐷 (𝑝)))]}_{𝒜︀} = 𝟎

for every $𝑝$ , and since every $𝐱 \in 𝐹^{3}$ is ${[𝑝]}_{𝒜︀}$ for some $𝑝$ , multiplying by $𝑁$ three times kills every vector. You can check this directly for each $𝑁$ . The matrix in (d) does not have this property: it fixes $𝐞_{1}$ . Properties of an operator that are visible in its matrix in every basis are studied in Section 4.5, under the name of similarity.

Example 2.3.23 (Maps of the plane in adapted bases). Let $ℓ$ be the line $𝑦 = 2 𝑥$ , as in Example 2.3.19, and let $𝒰︀ = 𝐮_{1}, 𝐮_{2}$ with $𝐮_{1} = (1, 2)$ on $ℓ$ and $𝐮_{2} = (- 2, 1)$ perpendicular to $ℓ$ (since $1 \cdot (- 2) + 2 \cdot 1 = 0$ ). This is a basis of $ℝ^{2}$ : the equations $𝑎 - 2 𝑏 = 𝑥$ and $2 𝑎 + 𝑏 = 𝑦$ have exactly one solution, $𝑎 = (𝑥 + 2 𝑦) / 5$ and $𝑏 = (𝑦 - 2 𝑥) / 5$ .

The projection $𝑃 = {Pr}_{ℓ}$ fixes $𝐮_{1}$ and sends $𝐮_{2}$ to $𝟎$ , and the reflection $𝑆 = 𝑆_{ℓ}$ fixes $𝐮_{1}$ and sends $𝐮_{2}$ to $- 𝐮_{2}$ . (With the matrices of Example 2.3.19: $\frac{1}{5} (1 + 4, 2 + 8) = (1, 2)$ and $\frac{1}{5} (- 2 + 2, - 4 + 4) =$ $(0, 0)$ .) So

{[𝑃]}_{𝒰︀ 𝒰︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}), {[𝑆]}_{𝒰︀ 𝒰︀} = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}),

compared with $\frac{1}{5} (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})$ and $\frac{1}{5} (\begin{matrix} - 3 & 4 \\ 4 & 3 \end{matrix})$ in the standard basis. In the adapted basis, the matrices show what the maps do.

The rotation $𝑅 = 𝑅_{𝜋 / 2}$ has ${[𝑅]}_{ℰ︀ ℰ︀} = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ . In the reversed standard basis $𝐞_{2}, 𝐞_{1}$ , the vector $𝑅 (𝐞_{2}) = - 𝐞_{1}$ has coordinates $(0, - 1)$ and $𝑅 (𝐞_{1}) = 𝐞_{2}$ has coordinates $(1, 0)$ , so the matrix becomes $(\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix})$ . That is the standard matrix of the clockwise rotation $𝑅_{- 𝜋 / 2}$ : reordering the basis reverses the orientation of the coordinate system. In the basis $𝒰︀$ , on the other hand, $𝑅 (𝐮_{1}) =$ $(- 2, 1) =$ $𝐮_{2}$ and $𝑅 (𝐮_{2}) =$ $(- 1, - 2) =$ $- 𝐮_{1}$ , so ${[𝑅]}_{𝒰︀ 𝒰︀} =$ $(\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ , the same as in the standard basis.

Two lessons. First, a matrix alone does not determine a map; only the matrix together with the bases does (Theorem 2.3.20). For instance $(\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ is ${[𝑆_{ℓ}]}_{𝒰︀ 𝒰︀}$ , and it is also the standard matrix of the reflection across the $𝑥$ -axis. Second, choosing a basis adapted to the map is how one understands it. If some basis consists of vectors that $𝑇$ sends to multiples of themselves, the matrix of $𝑇$ in that basis is diagonal. This is how Example 2.2.3 built $𝑃$ and $𝑆$ in the first place (Technique 2.2.4), and finding such bases is the subject of Section 7.4.

2.3.5The identity map in two bases

By Example 2.3.6, ${[{id}_{𝑉}]}_{ℬ︀ ℬ︀} = 𝐼_{𝑛}$ for every basis $ℬ︀$ . With two different bases, the matrix of the identity map is a different matrix, and it can look like almost anything. What it does is given by Theorem 2.3.9: for any two bases $ℬ︀$ and $𝒞︀$ of $𝑉$ ,

{[{id}_{𝑉}]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀} = {[{id}_{𝑉} (𝐯)]}_{𝒞︀} = {[𝐯]}_{𝒞︀} for every 𝐯 \in 𝑉 .

That is, the matrix of the identity converts $ℬ︀$ -coordinates into $𝒞︀$ -coordinates.

Example 2.3.24 (The identity in two bases). Let $𝐹$ be a field with $1 + 1 \neq 0$ , and let $ℬ︀ = (1, 1), (1, - 1)$ , a basis of $𝐹^{2}$ (Example 2.2.3). The columns of ${[id]}_{ℰ︀ ℬ︀}$ are the standard coordinates of $(1, 1)$ and $(1, - 1)$ , which are these vectors themselves. The columns of ${[id]}_{ℬ︀ ℰ︀}$ are the $ℬ︀$ -coordinates of $𝐞_{1} =$ $\frac{1}{2} (1, 1) +$ $\frac{1}{2} (1, - 1)$ and $𝐞_{2} =$ $\frac{1}{2} (1, 1) -$ $\frac{1}{2} (1, - 1)$ . So

{[id]}_{ℰ︀ ℬ︀} = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}), {[id]}_{ℬ︀ ℰ︀} = \frac{1}{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) .

For $𝐯 =$ $(3, 1) =$ $2 (1, 1) +$ $(1, - 1)$ we have ${[𝐯]}_{ℬ︀} = (2, 1)$ , and indeed the two matrices convert between the two coordinate vectors of $𝐯$ :

(\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} 2 \\ 1 \end{matrix}) = (\begin{matrix} 3 \\ 1 \end{matrix}) = {[𝐯]}_{ℰ︀}, \frac{1}{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} 3 \\ 1 \end{matrix}) = (\begin{matrix} 2 \\ 1 \end{matrix}) = {[𝐯]}_{ℬ︀} .

The example generalizes in one direction. For any basis $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ of $𝐹^{𝑛}$ , ${[id]}_{ℰ︀ ℬ︀}$ is the matrix whose columns are $𝐛_{1}, \dots, 𝐛_{𝑛}$ , because ${[𝐛_{𝑗}]}_{ℰ︀} = 𝐛_{𝑗}$ . The other direction, ${[id]}_{ℬ︀ ℰ︀}$ , requires solving for coordinates.

Remark 2.3.25 (A warning about the identity). The phrase “the matrix of the identity map” means nothing until both bases are specified:

{[{id}_{𝑉}]}_{𝒞︀ ℬ︀} = 𝐼_{𝑛}

exactly when

ℬ︀ = 𝒞︀

(Exercise 2.3.26). In general,

{[{id}_{𝑉}]}_{𝒞︀ ℬ︀}

is the matrix that changes

ℬ︀

-coordinates into

𝒞︀

-coordinates. These matrices are the subject of Section 4.5 (Definition 4.5.10). There, once matrix multiplication is available (Section 2.4), they compute

{[𝑇]}_{\overset{̊}{𝒞︀} \overset{̊}{ℬ︀}}

from

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

for any other bases

\overset{̊}{ℬ︀}

and

\overset{̊}{𝒞︀}

, and explain the different matrices of

𝐷

and of the plane maps found above.

Exercise 2.3.26.routine Let

ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}

and

𝒞︀ = 𝐰_{1}, \dots, 𝐰_{𝑛}

be bases of

𝑉

of the same length. Show that

{[{id}_{𝑉}]}_{𝒞︀ ℬ︀} = 𝐼_{𝑛}

if and only if

ℬ︀ = 𝒞︀

, that is,

𝐯_{𝑗} = 𝐰_{𝑗}

for every

𝑗

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 2.3.5 (Identity matrix), Definition 1.6.14 (Coordinates)

Hint 1. The

𝑗

-th column of

{[{id}_{𝑉}]}_{𝒞︀ ℬ︀}

{[𝐯_{𝑗}]}_{𝒞︀}

. When is it

𝐞_{𝑗}

Hint 2. A vector with

𝒞︀

-coordinates

𝐞_{𝑗}

0 𝐰_{1} +

\dots +

1 𝐰_{𝑗} +

\dots +

0 𝐰_{𝑛}

Sketch. The

𝑗

-th column is

{[𝐯_{𝑗}]}_{𝒞︀}

, and

{[𝐯_{𝑗}]}_{𝒞︀} = 𝐞_{𝑗}

if and only if

𝐯_{𝑗} = 𝐰_{𝑗}

. So all columns agree with those of

𝐼_{𝑛}

if and only if

𝐯_{𝑗} = 𝐰_{𝑗}

for all

𝑗

By Definition 2.3.1, the $𝑗$ -th column of ${[{id}_{𝑉}]}_{𝒞︀ ℬ︀}$ is ${[𝐯_{𝑗}]}_{𝒞︀}$ , and the $𝑗$ -th column of $𝐼_{𝑛}$ is $𝐞_{𝑗}$ . Since a vector is determined by its coordinates (Definition 1.6.14), ${[𝐯_{𝑗}]}_{𝒞︀} = 𝐞_{𝑗}$ holds if and only if

𝐯_{𝑗} = 0 𝐰_{1} + \dots + 1 𝐰_{𝑗} + \dots + 0 𝐰_{𝑛} = 𝐰_{𝑗} .

So ${[{id}_{𝑉}]}_{𝒞︀ ℬ︀} = 𝐼_{𝑛}$ if and only if $𝐯_{𝑗} = 𝐰_{𝑗}$ for every $𝑗$ .

2.3.6Translating between maps and matrices

The results of this section give a dictionary between linear maps of spaces with chosen bases and matrices.

A vector $𝐯 \in 𝑉$ corresponds to its coordinate vector ${[𝐯]}_{ℬ︀} \in 𝐹^{𝑛}$ , and a map $𝑇 \in L (𝑉, 𝑊)$ to its matrix ${[𝑇]}_{𝒞︀ ℬ︀} \in 𝐹^{𝑚 \times 𝑛}$ .
The value $𝑇 (𝐯)$ corresponds to the product ${[𝑇]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀}$ (Theorem 2.3.9), and the value $𝑇 (𝐯_{𝑗})$ on a basis vector to the $𝑗$ -th column.
Two maps are equal if and only if their matrices are (Theorem 2.3.20).
For $𝑉 = 𝐹^{𝑛}$ and $𝑊 = 𝐹^{𝑚}$ with the standard bases, $𝑇$ corresponds to the unique $𝐴$ with $𝑇 = 𝑇_{𝐴}$ (Proposition 2.3.17), and $id$ corresponds to $𝐼_{𝑛}$ .

Technique 2.3.27 (Translate between maps and matrices). A linear map between spaces with chosen bases and its matrix carry the same information, so a question about one can be translated into a question about the other, using the dictionary above.

In one direction, to compute with a linear map, replace vectors by their coordinate vectors and the map by its matrix. Evaluating $𝑇$ becomes a matrix–vector product, and an equation $𝑇 (𝐯) = 𝐰$ becomes the linear system ${[𝑇]}_{𝒞︀ ℬ︀} 𝐱 =$ ${[𝐰]}_{𝒞︀}$ in the unknown coordinates $𝐱$ of $𝐯$ (Section 3.1). In the other direction, to prove a statement about a matrix $𝐴$ , read it as a statement about the linear map $𝑇_{𝐴}$ , prove it with the theory of linear maps, which needs no indices, and translate back with the uniqueness in Proposition 2.3.17.

Reach for the first direction when you need numbers, and for the second when a matrix identity would otherwise need a computation with indices. A rule of thumb: compute with matrices, prove with maps. Before translating, fix the bases and keep track of which basis each coordinate vector refers to; most errors come from mixing them up. The canonical example is Example 2.3.28. Later instances: matrix multiplication is defined by translating composition (Section 2.4), the rank of a matrix is the rank of its map (Section 4.2), and the determinant and the eigenvalues of an operator are read off from its matrix in any basis (Section 5.4, Section 7.3).

Used in 36 places and 4 practice exercises

Exercise 2.3.32, Exercise 2.3.35, Exercise 2.3.42, Theorem 2.4.2, Proposition 2.4.14, Proposition 2.5.20, Exercise 2.5.22, Proposition 2.6.20, Corollary 2.7.16, Exercise 2.8.8, Exercise 2.8.13, Problem 2.2, Problem 2.13, Problem 3.12, Theorem 4.1.1, Proposition 4.1.31, Theorem 4.2.11, Proposition 4.2.15, Proposition 4.5.12, Proposition 4.5.16, Theorem 4.5.17, Theorem 4.5.25, Proposition 4.5.27, Proposition 5.4.20, Theorem 6.6.15, Proposition 6.6.18, Exercise 6.6.46, Corollary 7.3.13, Theorem 7.4.2, Proposition 7.5.25, Proposition 8.1.7, Corollary 8.1.11, Theorem 8.4.4, Proposition B.1.18, Exercise B.1.41, Exercise B.1.42; 4 practice exercises.

Example 2.3.28 (Translating in both directions).

(a)From maps to matrices. We find all $𝑝 \in {ℚ [𝑥]}_{\leq 2}$ with $𝑝 (𝑥 + 1) -$ $𝑝 (𝑥) =$ $𝑥$ . The map $Δ : {ℚ [𝑥]}_{\leq 2} \to {ℚ [𝑥]}_{\leq 2}$ , $Δ (𝑝) =$ $𝑝 (𝑥 + 1) -$ $𝑝 (𝑥)$ , is linear, being the difference of the substitution map of Exercise 2.1.32 and the identity (Technique 2.1.26). With $ℬ︀ = 1, 𝑥, 𝑥^{2}$ ,
$Δ (1) = 𝟎, Δ (𝑥) = (𝑥 + 1) - 𝑥 = 1, Δ (𝑥^{2}) = {(𝑥 + 1)}^{2} - 𝑥^{2} = 1 + 2 𝑥,$
so
${[Δ]}_{ℬ︀ ℬ︀} = (\begin{matrix} 0 & 1 & 1 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{matrix}) .$
By Theorem 2.3.9, $𝑝 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ satisfies $Δ (𝑝) = 𝑥$ if and only if ${[Δ]}_{ℬ︀ ℬ︀} (𝑎, 𝑏, 𝑐) =$ ${[𝑥]}_{ℬ︀} =$ $(0, 1, 0)$ . By Proposition 2.3.11 this is the system $𝑏 + 𝑐 = 0$ , $2 𝑐 = 1$ , $0 = 0$ , whose solutions are $𝑐 = 1 / 2$ , $𝑏 = - 1 / 2$ , and $𝑎$ arbitrary. So the solutions are
$𝑝 = 𝑎 + \frac{𝑥^{2} - 𝑥}{2} (𝑎 \in ℚ) .$
This gives a formula for sums. For $𝑞 (𝑡) = 𝑡 (𝑡 - 1) / 2$ and every number $𝑡$ ,
$𝑞 (𝑡 + 1) - 𝑞 (𝑡) = \frac{(𝑡 + 1) 𝑡 - 𝑡 (𝑡 - 1)}{2} = 𝑡,$
so the sum $0 + 1 + \dots + (𝑛 - 1)$ telescopes:
$\sum_{𝑘 = 0}^{𝑛 - 1} 𝑘 = \sum_{𝑘 = 0}^{𝑛 - 1} (𝑞 (𝑘 + 1) - 𝑞 (𝑘)) = 𝑞 (𝑛) - 𝑞 (0) = \frac{𝑛 (𝑛 - 1)}{2} .$
(b)From matrices to maps. Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , and suppose that for every $𝐱 \in 𝐹^{𝑛}$ the vector $𝐴 𝐱$ is a scalar multiple of $𝐱$ . We show that $𝐴 = 𝜆 𝐼_{𝑛}$ for some $𝜆 \in 𝐹$ . The hypothesis says that $𝑇_{𝐴} (𝐱) \in span (𝐱)$ for every $𝐱$ . By Exercise 2.1.48, $𝑇_{𝐴} = 𝜆 id$ for some $𝜆 \in 𝐹$ . Now $(𝜆 𝐼_{𝑛}) 𝐱 =$ $𝜆 (𝐼_{𝑛} 𝐱) =$ $𝜆 𝐱$ by Proposition 2.3.13, so $𝜆 id = 𝑇_{𝜆 𝐼_{𝑛}}$ . Hence $𝑇_{𝐴} = 𝑇_{𝜆 𝐼_{𝑛}}$ , and $𝐴 = 𝜆 𝐼_{𝑛}$ by the uniqueness in Proposition 2.3.17. A direct proof with entries is possible, but it would repeat the argument of Exercise 2.1.48 in coordinates.

Exercises

Exercise 2.3.29.routine Let $𝑇 : ℝ^{2} \to ℝ^{3}$ , $𝑇 (𝑥, 𝑦) =$ $(𝑥 + 𝑦, 𝑥 - 𝑦, 2 𝑥)$ , and consider the bases $ℬ︀ = (1, 1), (1, - 1)$ of $ℝ^{2}$ and $𝒞︀ =$ $(1, 0, 0),$ $(1, 1, 0),$ $(1, 1, 1)$ of $ℝ^{3}$ .

(a)Find ${[𝑇]}_{𝒞︀ ℬ︀}$ .
(b)Check Theorem 2.3.9 for $𝐯 = (3, 1)$ by computing both sides.

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.3.9 (The matrix of a map computes the map), Definition 2.3.8 (Matrix–vector product)

Hint 1. First find a formula for the

𝒞︀

-coordinates

(𝑎, 𝑏, 𝑐)

of a vector

(𝑥, 𝑦, 𝑧)

by solving for

𝑎, 𝑏, 𝑐

Hint 2. The columns of

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

are the

𝒞︀

-coordinates of

𝑇 (1, 1)

and

𝑇 (1, - 1)

. For (b),

(3, 1) =

2 (1, 1) +

(1, - 1)

Sketch.

{[(𝑥, 𝑦, 𝑧)]}_{𝒞︀} =

(𝑥 - 𝑦, 𝑦 - 𝑧, 𝑧)

𝑇 (1, 1) = (2, 0, 2)

and

𝑇 (1, - 1) = (0, 2, 2)

give

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

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

. For

𝐯 = (3, 1)

{[𝐯]}_{ℬ︀} = (2, 1)

, and both sides equal

(2, - 4, 6)

Since

𝑎 (1, 0, 0) + 𝑏 (1, 1, 0) + 𝑐 (1, 1, 1) = (𝑎 + 𝑏 + 𝑐, 𝑏 + 𝑐, 𝑐),

the $𝒞︀$ -coordinates of $(𝑥, 𝑦, 𝑧)$ are $𝑐 = 𝑧$ , $𝑏 = 𝑦 - 𝑧$ , and $𝑎 = 𝑥 - 𝑦$ :

{[(𝑥, 𝑦, 𝑧)]}_{𝒞︀} = (𝑥 - 𝑦, 𝑦 - 𝑧, 𝑧) .

(a) $𝑇 (1, 1) = (2, 0, 2)$ has $𝒞︀$ -coordinates $(2, - 2, 2)$ , and $𝑇 (1, - 1) = (0, 2, 2)$ has $𝒞︀$ -coordinates $(- 2, 0, 2)$ . So

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

(b) Since $(3, 1) =$ $2 (1, 1) +$ $1 (1, - 1)$ , ${[𝐯]}_{ℬ︀} = (2, 1)$ , and

{[𝑇]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀} = 2 (\begin{matrix} 2 \\ - 2 \\ 2 \end{matrix}) + 1 (\begin{matrix} - 2 \\ 0 \\ 2 \end{matrix}) = (\begin{matrix} 2 \\ - 4 \\ 6 \end{matrix}) .

On the other side, $𝑇 (3, 1) = (4, 2, 6)$ , whose $𝒞︀$ -coordinates are $(4 - 2, 2 - 6, 6) =$ $(2, - 4, 6)$ . The two sides agree.

Exercise 2.3.30.routine Find the error in the following computation, and correct it.

Let $ℬ︀ = (1, 1), (1, - 1)$ , a basis of $ℝ^{2}$ , and let $𝐯 = (3, 1)$ . The matrix ${[id]}_{ℰ︀ ℬ︀} = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ relates the two bases, so the $ℬ︀$ -coordinates of $𝐯$ are

{[𝐯]}_{ℬ︀} = {[id]}_{ℰ︀ ℬ︀} 𝐯 = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} 3 \\ 1 \end{matrix}) = (\begin{matrix} 4 \\ 2 \end{matrix}) .

Solution.

Uses. Theorem 2.3.9 (The matrix of a map computes the map), Example 2.3.24 (The identity in two bases)

Hint 1. Check the answer: is

4 (1, 1) + 2 (1, - 1)

equal to

(3, 1)

Hint 2. By Theorem 2.3.9,

{[id]}_{ℰ︀ ℬ︀}

multiplies

ℬ︀

-coordinates and produces

ℰ︀

-coordinates. Which matrix goes the other way?

Sketch.

{[id]}_{ℰ︀ ℬ︀} {[𝐯]}_{ℬ︀} =

{[𝐯]}_{ℰ︀}

, so this matrix turns

ℬ︀

-coordinates into standard coordinates, not the reverse. The correct matrix is

{[id]}_{ℬ︀ ℰ︀} =

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

, which gives

{[𝐯]}_{ℬ︀} = (2, 1)

The answer is wrong: $4 (1, 1) +$ $2 (1, - 1) =$ $(6, 2) \neq$ $(3, 1)$ . By Theorem 2.3.9, ${[id]}_{ℰ︀ ℬ︀} {[𝐰]}_{ℬ︀} =$ ${[𝐰]}_{ℰ︀}$ for every $𝐰$ , so ${[id]}_{ℰ︀ ℬ︀}$ takes $ℬ︀$ -coordinates as input and produces standard coordinates. The computation feeds it standard coordinates. What it actually produced is the vector whose $ℬ︀$ -coordinates are $(3, 1)$ , namely $3 (1, 1) +$ $(1, - 1) =$ $(4, 2)$ .

To go from standard coordinates to $ℬ︀$ -coordinates, use ${[id]}_{ℬ︀ ℰ︀} =$ $\frac{1}{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ (Example 2.3.24):

{[𝐯]}_{ℬ︀} = {[id]}_{ℬ︀ ℰ︀} {[𝐯]}_{ℰ︀} = \frac{1}{2} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) (\begin{matrix} 3 \\ 1 \end{matrix}) = (\begin{matrix} 2 \\ 1 \end{matrix}) .

Check: $2 (1, 1) +$ $(1, - 1) =$ $(3, 1)$ . The subscripts are a guide: in ${[id]}_{𝒞︀ ℬ︀} {[𝐯]}_{ℬ︀}$ the inner two must match.

Exercise 2.3.31.routine Find the error in the following argument.

Claim. Let $𝐹$ be any field. If $𝐴 \in 𝐹^{2 \times 2}$ satisfies $𝐴 (1, 1) = (1, 1)$ and $𝐴 (1, - 1) = (1, - 1)$ , then $𝐴 = 𝐼_{2}$ .

Proof. The maps $𝑇_{𝐴}$ and $id = 𝑇_{𝐼_{2}}$ agree on the vectors $(1, 1)$ and $(1, - 1)$ , which form a basis of $𝐹^{2}$ . Two linear maps that agree on a basis are equal, so $𝑇_{𝐴} = 𝑇_{𝐼_{2}}$ , and $𝐴 = 𝐼_{2}$ by Proposition 2.3.17.

Solution.

Uses. Example 2.2.3 (Building maps from a convenient basis), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 2.3.17 (Every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ is some $𝑇_{𝐴}$ )

Hint 1. When is

(1, 1), (1, - 1)

a basis of

𝐹^{2}

? Look at Example 2.2.3.

Hint 2. Over

𝔽_{2}

- 1 = 1

. Try

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

Sketch.

(1, 1), (1, - 1)

is a basis only when

1 + 1 \neq 0

. Over

𝔽_{2}

the two vectors coincide, and

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

satisfies both hypotheses without being

𝐼_{2}

. When

1 + 1 \neq 0

the argument is correct.

The error is the claim that $(1, 1), (1, - 1)$ is a basis of $𝐹^{2}$ for every field. It is a basis when $1 + 1 \neq 0$ (Example 2.2.3), but over $𝔽_{2}$ we have $- 1 = 1$ , so the two vectors are equal and the list is linearly dependent. Then the hypothesis says only that $𝐴 (1, 1) = (1, 1)$ , and the claim fails: over $𝔽_{2}$ ,

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

so $𝐴 = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ satisfies both hypotheses and $𝐴 \neq 𝐼_{2}$ . In general $(1, - 1) = (1, 1)$ exactly when $1 + 1 = 0$ . When $1 + 1 \neq 0$ the argument is correct as written, by Corollary 2.2.6 and Proposition 2.3.17.

Exercise 2.3.32.standard Let $𝑇 : {𝐹 [𝑥]}_{\leq 3} \to$ ${𝐹 [𝑥]}_{\leq 3}$ , $𝑇 (𝑝) = 𝑝 (𝑥 + 1)$ , which is linear by Exercise 2.1.32, and let $ℬ︀ = 1, 𝑥, 𝑥^{2}, 𝑥^{3}$ .

(a)Find ${[𝑇]}_{ℬ︀ ℬ︀}$ for $𝐹 = ℚ$ and for $𝐹 = 𝔽_{2}$ .
(b)Over $𝔽_{2}$ , use the matrix to find all $𝑝 \in 𝔽_{2} {[𝑥]}_{\leq 3}$ with $𝑝 (𝑥 + 1) = 𝑝 (𝑥)$ .
(c)Do the same over $ℚ$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.3.9 (The matrix of a map computes the map), Proposition 2.3.11 (Entries of $𝐴 𝐱$ ), Theorem 2.3.20 (Linear maps correspond to matrices)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. Expand

{(𝑥 + 1)}^{𝑘}

for

𝑘 = 0, 1, 2, 3

. Over

𝔽_{2}

, reduce the binomial coefficients modulo

2

Hint 2.

𝑝 (𝑥 + 1) = 𝑝 (𝑥)

means

𝑇 (𝑝) = 𝑝

, that is,

𝐴 {[𝑝]}_{ℬ︀} = {[𝑝]}_{ℬ︀}

with

𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}

. Write out the four entries of

𝐴 (𝑎, 𝑏, 𝑐, 𝑑)

and compare.

Sketch. The columns are the coefficients of

1

1 + 𝑥

1 + 2 𝑥 + 𝑥^{2}

1 + 3 𝑥 + 3 𝑥^{2} + 𝑥^{3}

. Over

𝔽_{2}

the condition

𝐴 (𝑎, 𝑏, 𝑐, 𝑑) =

(𝑎, 𝑏, 𝑐, 𝑑)

reads

𝑏 + 𝑐 + 𝑑 = 0

and

𝑑 = 0

, so

𝑝 = 𝑎 + 𝑏 (𝑥 + 𝑥^{2})

. Over

ℚ

it reads

𝑏 + 𝑐 + 𝑑 = 0

2 𝑐 + 3 𝑑 = 0

3 𝑑 = 0

, so

𝑝

is constant.

(a) $𝑇 (1) = 1$ , $𝑇 (𝑥) = 1 + 𝑥$ , $𝑇 (𝑥^{2}) = 1 + 2 𝑥 + 𝑥^{2}$ , and $𝑇 (𝑥^{3}) =$ $1 +$ $3 𝑥 +$ $3 𝑥^{2} +$ $𝑥^{3}$ . Their coordinate vectors are the columns, so over $ℚ$ and over $𝔽_{2}$ (where $2 = 0$ and $3 = 1$ ) respectively

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

The entries are the binomial coefficients of Pascal’s triangle, reduced modulo $2$ in the second case.

(b) Let $𝐴$ be the matrix over $𝔽_{2}$ , and ${[𝑝]}_{ℬ︀} =$ $(𝑎, 𝑏, 𝑐, 𝑑)$ . By Theorem 2.3.9 and since coordinates determine vectors, $𝑇 (𝑝) = 𝑝$ if and only if $𝐴 (𝑎, 𝑏, 𝑐, 𝑑) =$ $(𝑎, 𝑏, 𝑐, 𝑑)$ . By Proposition 2.3.11,

𝐴 (\begin{matrix} 𝑎 \\ 𝑏 \\ 𝑐 \\ 𝑑 \end{matrix}) = (\begin{matrix} 𝑎 + 𝑏 + 𝑐 + 𝑑 \\ 𝑏 + 𝑑 \\ 𝑐 + 𝑑 \\ 𝑑 \end{matrix}),

so the condition is $𝑏 + 𝑐 + 𝑑 = 0$ and $𝑑 = 0$ , that is, $𝑑 = 0$ and $𝑐 = 𝑏$ (in $𝔽_{2}$ , $𝑏 + 𝑐 = 0$ means $𝑐 = 𝑏$ ). So the solutions are the four polynomials $𝑝 = 𝑎 + 𝑏 (𝑥 + 𝑥^{2})$ with $𝑎, 𝑏 \in 𝔽_{2}$ . Check: $(𝑥 + 1) +$ ${(𝑥 + 1)}^{2} =$ $𝑥 +$ $1 +$ $𝑥^{2} +$ $1 =$ $𝑥 +$ $𝑥^{2}$ over $𝔽_{2}$ .

(c) Over $ℚ$ the condition $𝐴 (𝑎, 𝑏, 𝑐, 𝑑) =$ $(𝑎, 𝑏, 𝑐, 𝑑)$ reads

𝑎 + 𝑏 + 𝑐 + 𝑑 = 𝑎, 𝑏 + 2 𝑐 + 3 𝑑 = 𝑏, 𝑐 + 3 𝑑 = 𝑐, 𝑑 = 𝑑,

so $3 𝑑 = 0$ , then $2 𝑐 = 0$ , then $𝑏 = 0$ : only the constant polynomials satisfy $𝑝 (𝑥 + 1) = 𝑝 (𝑥)$ . The difference between the two fields is the entry $2$ in row $2$ , column $3$ : over $ℚ$ it forces $𝑐 = 0$ , and over $𝔽_{2}$ it vanishes, which lets $𝑥 + 𝑥^{2}$ through.

Exercise 2.3.33.standard Let $𝑇 : {𝐹 [𝑥]}_{\leq 2} \to 𝐹^{3}$ , $𝑇 (𝑝) =$ $(𝑝 (0), 𝑝 (1), 𝑝 (2))$ , where $2 = 1 + 1$ .

(a)Find ${[𝑇]}_{ℰ︀ ℬ︀}$ for $ℬ︀ = 1, 𝑥, 𝑥^{2}$ .
(b)Suppose $2 \neq 0$ in $𝐹$ . Find a basis $\overset{̊}{ℬ︀} = 𝑝_{0}, 𝑝_{1}, 𝑝_{2}$ of ${𝐹 [𝑥]}_{\leq 2}$ with ${[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}} = 𝐼_{3}$ , and prove that it is a basis.
(c)With $\overset{̊}{ℬ︀}$ as in (b), show that ${[𝑞]}_{\overset{̊}{ℬ︀}} =$ $(𝑞 (0), 𝑞 (1), 𝑞 (2))$ for every $𝑞 \in {𝐹 [𝑥]}_{\leq 2}$ .
(d)Show that over $𝔽_{2}$ no basis $\overset{̊}{ℬ︀}$ with ${[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}} = 𝐼_{3}$ exists.

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Theorem 2.3.9 (The matrix of a map computes the map), Definition 1.6.1 (Basis), Definition 1.2.17 (Evaluation)

Hint 1. (a) The columns are

𝑇 (1)

𝑇 (𝑥)

𝑇 (𝑥^{2})

. (b) The condition says

𝑇 (𝑝_{𝑗}) = 𝐞_{𝑗 + 1}

: each

𝑝_{𝑗}

1

𝑗

and

0

at the other two points. Build it from the factors

𝑥

𝑥 - 1

𝑥 - 2

Hint 2. To prove that

𝑝_{0}, 𝑝_{1}, 𝑝_{2}

is a basis, show that

𝑞 -

(𝑞 (0) 𝑝_{0} + 𝑞 (1) 𝑝_{1} + 𝑞 (2) 𝑝_{2})

vanishes at

0, 1, 2

, and that the only

𝑟 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}

vanishing at

0, 1, 2

𝑟 = 𝟎

Hint 3. (d) Over

𝔽_{2}

2 = 0

. Compare the first and third coordinates of

𝑇 (𝑝)

Sketch. (a)

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

. (b)

𝑝_{0} =

(𝑥 - 1) (𝑥 - 2) / 2

𝑝_{1} = - 𝑥 (𝑥 - 2)

𝑝_{2} = 𝑥 (𝑥 - 1) / 2

. Every

𝑞

equals

\sum_{𝑗} 𝑞 (𝑗) 𝑝_{𝑗}

, because the difference vanishes at

0, 1, 2

and

𝑟 (0) =

𝑟 (1) =

𝑟 (2) =

0

forces

𝑟 = 𝟎

when

2 \neq 0

; the coefficients are unique because evaluating

\sum 𝑐_{𝑗} 𝑝_{𝑗}

𝑘

gives

𝑐_{𝑘}

. (c)

{[𝑇 (𝑞)]}_{ℰ︀} =

𝐼_{3} {[𝑞]}_{\overset{̊}{ℬ︀}}

. (d) Every value

𝑇 (𝑝) =

(𝑝 (0), 𝑝 (1), 𝑝 (0))

has equal first and third coordinates, but

𝐞_{1}

does not.

(a) $𝑇 (1) = (1, 1, 1)$ , $𝑇 (𝑥) = (0, 1, 2)$ , and $𝑇 (𝑥^{2}) = (0, 1, 4)$ , so

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

(b) We need $𝑇 (𝑝_{𝑗}) = 𝐞_{𝑗 + 1}$ , that is, $𝑝_{𝑗} (𝑘) = 1$ if $𝑘 = 𝑗$ and $0$ otherwise, for $𝑗, 𝑘 \in {0, 1, 2}$ . Let

\begin{aligned} 𝑝_{0} & = \frac{1}{2} (𝑥 - 1) (𝑥 - 2) = \frac{1}{2} (𝑥^{2} - 3 𝑥 + 2), \\ 𝑝_{1} & = - 𝑥 (𝑥 - 2) = - 𝑥^{2} + 2 𝑥, \\ 𝑝_{2} & = \frac{1}{2} 𝑥 (𝑥 - 1) = \frac{1}{2} (𝑥^{2} - 𝑥) . \end{aligned}

Evaluating the expanded forms: $𝑝_{0}$ takes the values $1, 0, 0$ at $0, 1, 2$ (at $2$ : $(4 - 6 + 2) / 2 = 0$ ), $𝑝_{1}$ takes $0, 1, 0$ , and $𝑝_{2}$ takes $0, 0, 1$ .

Spanning. Let $𝑞 \in {𝐹 [𝑥]}_{\leq 2}$ and $𝑟 =$ $𝑞 -$ $(𝑞 (0) 𝑝_{0} + 𝑞 (1) 𝑝_{1} + 𝑞 (2) 𝑝_{2})$ . Evaluation is linear, so $𝑟 (𝑘) =$ $𝑞 (𝑘) -$ $𝑞 (𝑘) =$ $0$ for $𝑘 = 0, 1, 2$ . Write $𝑟 = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}$ . Then $𝑟 (0) = 𝑎 = 0$ , $𝑟 (1) = 𝑏 + 𝑐 = 0$ , and $𝑟 (2) = 2 𝑏 + 4 𝑐 = 0$ . Substituting $𝑏 = - 𝑐$ into the last equation gives $2 𝑐 = 0$ , so $𝑐 = 0$ because $2 \neq 0$ , and then $𝑏 = 0$ . Hence $𝑟 = 𝟎$ and $𝑞 =$ $𝑞 (0) 𝑝_{0} +$ $𝑞 (1) 𝑝_{1} +$ $𝑞 (2) 𝑝_{2}$ .

Uniqueness. If $𝑞 =$ $𝑐_{0} 𝑝_{0} +$ $𝑐_{1} 𝑝_{1} +$ $𝑐_{2} 𝑝_{2}$ , evaluating at $𝑘$ gives $𝑞 (𝑘) = 𝑐_{𝑘}$ . So the coefficients are determined by $𝑞$ , and $\overset{̊}{ℬ︀}$ is a basis (Definition 1.6.1). By construction, ${[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}} = 𝐼_{3}$ .

(c) By Theorem 2.3.9 and Proposition 2.3.13(c),

(𝑞 (0), 𝑞 (1), 𝑞 (2)) = {[𝑇 (𝑞)]}_{ℰ︀} = 𝐼_{3} {[𝑞]}_{\overset{̊}{ℬ︀}} = {[𝑞]}_{\overset{̊}{ℬ︀}} .

(This is also visible in the uniqueness argument.) In this basis, the coordinates of a polynomial are its values.

(d) Over $𝔽_{2}$ , $2 = 0$ , so $𝑇 (𝑝) =$ $(𝑝 (0), 𝑝 (1), 𝑝 (0))$ for every $𝑝$ : the first and third coordinates of every value of $𝑇$ agree. If ${[𝑇]}_{ℰ︀ \overset{̊}{ℬ︀}} = 𝐼_{3}$ , then $𝑇 (𝑝_{0}) =$ $𝐞_{1} =$ $(1, 0, 0)$ , whose first and third coordinates differ. So no such basis exists. Correspondingly, the first and third rows of ${[𝑇]}_{ℰ︀ ℬ︀} =$ $(\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})$ are equal over $𝔽_{2}$ .

Exercise 2.3.34.standard Let $𝑇 : ℝ^{2} \to ℝ^{2}$ , $𝑇 (𝑥, 𝑦) =$ $(𝑥 + 𝑦, 2 𝑥 + 2 𝑦)$ .

(a)Find bases $ℬ︀$ and $𝒞︀$ of $ℝ^{2}$ with ${[𝑇]}_{𝒞︀ ℬ︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .
(b)Show that there is no basis $ℬ︀$ of $ℝ^{2}$ with ${[𝑇]}_{ℬ︀ ℬ︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .
(c)Find a basis $ℬ︀$ of $ℝ^{2}$ for which ${[𝑇]}_{ℬ︀ ℬ︀}$ is diagonal.

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.1 (Basis), Proposition 1.2.35 (Zero products)

Hint 1. Every value of

𝑇

is a multiple of

(1, 2)

𝑇 (𝑥, 𝑦) =

(𝑥 + 𝑦) (1, 2)

. For (a) you need

𝑇 (𝐯_{1}) = 𝐰_{1}

and

𝑇 (𝐯_{2}) = 𝟎

Hint 2. For (b), the matrix would force

𝑇 (𝐯_{1}) = 𝐯_{1}

. Then

𝐯_{1}

is a value of

𝑇

. Compute

𝑇

on a multiple of

(1, 2)

Sketch. (a)

ℬ︀ = (1, 0), (1, - 1)

and

𝒞︀ = (1, 2), (0, 1)

𝑇 (1, 0) = (1, 2)

and

𝑇 (1, - 1) = 𝟎

. (b)

𝑇 (𝐯_{1}) = 𝐯_{1}

forces

𝐯_{1} = 𝑐 (1, 2)

, but

𝑇 (𝑐 (1, 2)) =

3 𝑐 (1, 2)

, so

2 𝐯_{1} = 𝟎

. (c)

ℬ︀ = (1, 2), (1, - 1)

gives

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

Note that $𝑇 (𝑥, 𝑦) =$ $(𝑥 + 𝑦) (1, 2)$ , so every value of $𝑇$ is a multiple of $(1, 2)$ , and $𝑇 (1, 2) = 3 (1, 2)$ .

(a) We need $𝑇 (𝐯_{1}) = 𝐰_{1}$ and $𝑇 (𝐯_{2}) = 𝟎$ . Take $ℬ︀ = (1, 0), (1, - 1)$ , a basis since $(𝑥, 𝑦) =$ $(𝑥 + 𝑦) (1, 0) -$ $𝑦 (1, - 1)$ with no other coefficients possible. Then $𝑇 (1, 0) = (1, 2)$ and $𝑇 (1, - 1) = (0, 0)$ . Take $𝒞︀ = (1, 2), (0, 1)$ , a basis since $(𝑥, 𝑦) =$ $𝑥 (1, 2) +$ $(𝑦 - 2 𝑥) (0, 1)$ with no other coefficients possible. Then ${[𝑇 (1, 0)]}_{𝒞︀} =$ $(1, 0)$ and ${[𝑇 (1, - 1)]}_{𝒞︀} =$ $(0, 0)$ , so ${[𝑇]}_{𝒞︀ ℬ︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .

(b) Suppose $ℬ︀ = 𝐯_{1}, 𝐯_{2}$ is a basis with ${[𝑇]}_{ℬ︀ ℬ︀} = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ . The first column says $𝑇 (𝐯_{1}) = 𝐯_{1}$ . So $𝐯_{1}$ is a value of $𝑇$ , hence $𝐯_{1} = 𝑐 (1, 2)$ for some $𝑐 \in ℝ$ , and then $𝑇 (𝐯_{1}) =$ $𝑐 𝑇 (1, 2) =$ $3 𝑐 (1, 2) =$ $3 𝐯_{1}$ . So $3 𝐯_{1} = 𝐯_{1}$ , that is, $2 𝐯_{1} = 𝟎$ , and $𝐯_{1} = 𝟎$ by Proposition 1.2.35. But a basis does not contain $𝟎$ , a contradiction.

(c) Let $ℬ︀ = (1, 2), (1, - 1)$ . It is a basis: $𝑎 (1, 2) +$ $𝑏 (1, - 1) =$ $(𝑥, 𝑦)$ exactly when $𝑎 = (𝑥 + 𝑦) / 3$ and $𝑏 = (2 𝑥 - 𝑦) / 3$ . Since $𝑇 (1, 2) = 3 (1, 2)$ and $𝑇 (1, - 1) = 𝟎$ ,

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

With two bases the nonzero entry can be scaled to $1$ , as in (a); with one basis the factor $3$ by which $𝑇$ stretches the line through $(1, 2)$ cannot be changed. Such factors are the eigenvalues of Section 7.2.

Exercise 2.3.35.standard Regard $ℂ$ as a vector space over $ℝ$ with the basis $ℬ︀ = 1, 𝑖$ .

(a)For $𝑧 = 𝑎 + 𝑏 𝑖$ with $𝑎, 𝑏 \in ℝ$ , let $𝑀_{𝑧} : ℂ \to ℂ$ , $𝑀_{𝑧} (𝑤) = 𝑧 𝑤$ . Find ${[𝑀_{𝑧}]}_{ℬ︀ ℬ︀}$ .
(b)Find the matrix of complex conjugation $𝑤 \mapsto 𝑤$ with respect to $ℬ︀$ .
(c)Show that a matrix $𝐴 \in ℝ^{2 \times 2}$ is ${[𝑇]}_{ℬ︀ ℬ︀}$ for some $ℂ$ -linear $𝑇 : ℂ \to ℂ$ if and only if $𝐴 = (\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ for some $𝑎, 𝑏 \in ℝ$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Exercise 2.1.5, Non-example 2.1.14 (Complex conjugation), Theorem 2.3.20 (Linear maps correspond to matrices)

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1. The columns are the

ℬ︀

-coordinates of

𝑀_{𝑧} (1) = 𝑧

and

𝑀_{𝑧} (𝑖) = 𝑧 𝑖

Hint 2. For (c), a

ℂ

-linear map

ℂ \to ℂ

is multiplication by some complex number (Exercise 2.1.5), and it is in particular

ℝ

-linear, so it has a matrix with respect to

ℬ︀

Sketch. (a)

𝑧 = 𝑎 + 𝑏 𝑖

and

𝑧 𝑖 = - 𝑏 + 𝑎 𝑖

give

(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})

. (b)

1 = 1

and

𝑖 = - 𝑖

give

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

. (c) A

ℂ

-linear

𝑇

𝑀_{𝑧}

for

𝑧 = 𝑇 (1)

, so its matrix has the form in (a); conversely

(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix}) =

{[𝑀_{𝑎 + 𝑏 𝑖}]}_{ℬ︀ ℬ︀}

(a) $𝑀_{𝑧}$ is $ℝ$ -linear (it is even $ℂ$ -linear, Exercise 2.1.5), so it has a matrix with respect to $ℬ︀$ . Since $𝑀_{𝑧} (1) = 𝑎 + 𝑏 𝑖$ and $𝑀_{𝑧} (𝑖) =$ $(𝑎 + 𝑏 𝑖) 𝑖 =$ $- 𝑏 +$ $𝑎 𝑖$ ,

{[𝑀_{𝑧}]}_{ℬ︀ ℬ︀} = (\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix}) .

For $𝑧 = cos 𝜃 + 𝑖 sin 𝜃$ this is the rotation matrix of Example 2.3.3: multiplying by a complex number of modulus $1$ rotates the plane.

(b) Conjugation is $ℝ$ -linear (Non-example 2.1.14), with $1 = 1$ and $𝑖 = - 𝑖$ , so its matrix is $(\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ .

(c) Let $𝑇 : ℂ \to ℂ$ be $ℂ$ -linear. By Exercise 2.1.5, $𝑇 = 𝑀_{𝑧}$ with $𝑧 = 𝑇 (1)$ , and $𝑇$ is in particular $ℝ$ -linear. Writing $𝑧 = 𝑎 + 𝑏 𝑖$ , part (a) gives ${[𝑇]}_{ℬ︀ ℬ︀} =$ $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ . Conversely, $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix}) =$ ${[𝑀_{𝑎 + 𝑏 𝑖}]}_{ℬ︀ ℬ︀}$ by (a), and $𝑀_{𝑎 + 𝑏 𝑖}$ is $ℂ$ -linear. By Theorem 2.3.20, each such matrix is the matrix of exactly one $ℝ$ -linear map, so the matrices of the form $(\begin{matrix} 𝑎 & - 𝑏 \\ 𝑏 & 𝑎 \end{matrix})$ are exactly the matrices of the $ℂ$ -linear maps. The matrix of conjugation in (b) is not of this form, consistent with Non-example 2.1.14.

Exercise 2.3.36.standard Let $𝑉$ and $𝑊$ be vector spaces over $ℝ$ with bases. Prove or disprove each statement.

(a)If $𝑆, 𝑇 \in L (𝑉, 𝑊)$ and ${[𝑆]}_{𝒞︀ ℬ︀} =$ ${[𝑇]}_{\overset{̊}{𝒞︀} \overset{̊}{ℬ︀}}$ for some bases $ℬ︀, \overset{̊}{ℬ︀}$ of $𝑉$ and $𝒞︀, \overset{̊}{𝒞︀}$ of $𝑊$ , then $𝑆 = 𝑇$ .
(b)If $𝑇 \in L (𝑉)$ and ${[𝑇]}_{ℬ︀ ℬ︀}$ is the zero matrix for some basis $ℬ︀$ , then $𝑇 = 0$ .
(c)If $𝑇 \in L (𝑉)$ and ${[𝑇]}_{𝒞︀ ℬ︀} = 𝐼_{𝑛}$ for some bases $ℬ︀, 𝒞︀$ of $𝑉$ , then $𝑇 = {id}_{𝑉}$ .
(d)If $𝑇 \in L (𝑉)$ and ${[𝑇]}_{ℬ︀ ℬ︀}$ is diagonal for some basis $ℬ︀$ , then ${[𝑇]}_{𝒞︀ 𝒞︀}$ is diagonal for every basis $𝒞︀$ of $𝑉$ .
(e)There are bases $ℬ︀, 𝒞︀$ of $ℝ^{2}$ with ${[id]}_{𝒞︀ ℬ︀} = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ .

Solution.

Uses. Theorem 2.3.20 (Linear maps correspond to matrices), Example 2.3.6 (The zero map and the identity map), Example 2.3.23 (Maps of the plane in adapted bases), Definition 2.3.1 (Matrix of a linear map)

Hint 1. Only (b) is true. For (a), (c), and (d), look at Example 2.3.23 and at maps that send one basis to another.

Hint 2. For (e), what would the two columns say about the vectors of

ℬ︀

Sketch. (a) False:

{[𝑆_{ℓ}]}_{𝒰︀ 𝒰︀} =

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

is also the standard matrix of the reflection across the

𝑥

-axis. (b) True:

{[𝑇]}_{ℬ︀ ℬ︀} = {[0]}_{ℬ︀ ℬ︀}

, so

𝑇 = 0

by Theorem 2.3.20. (c) False:

𝑇 = 2 id

with

𝒞︀ = 2 𝐯_{1}, \dots, 2 𝐯_{𝑛}

. (d) False:

𝑆_{ℓ}

𝒰︀

and in

ℰ︀

. (e) False: both columns equal means

𝐯_{1} = 𝐯_{2}

(a) False. Let $ℓ$ be the line $𝑦 = 2 𝑥$ and $𝒰︀$ as in Example 2.3.23. Then ${[𝑆_{ℓ}]}_{𝒰︀ 𝒰︀} =$ $(\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ , which is also ${[𝑆]}_{ℰ︀ ℰ︀}$ for the reflection $𝑆 (𝑥, 𝑦) =$ $(𝑥, - 𝑦)$ across the $𝑥$ -axis. But $𝑆_{ℓ} \neq 𝑆$ , since $𝑆_{ℓ} (1, 2) = (1, 2)$ and $𝑆 (1, 2) = (1, - 2)$ .

(b) True. The zero map also has the zero matrix (Example 2.3.6), so ${[𝑇]}_{ℬ︀ ℬ︀} = {[0]}_{ℬ︀ ℬ︀}$ , and $𝑇 = 0$ by Theorem 2.3.20(a).

(c) False. Take $𝑉 = ℝ$ with $ℬ︀ = 1$ and $𝒞︀ = 2$ , and $𝑇 = 2 {id}_{ℝ}$ . Then $𝑇 (1) = 2 = 1 \cdot 2$ , so ${[𝑇]}_{𝒞︀ ℬ︀} = (1) = 𝐼_{1}$ , but $𝑇 \neq id$ . In general, ${[𝑇]}_{𝒞︀ ℬ︀} = 𝐼_{𝑛}$ says exactly that $𝑇 (𝐯_{𝑗}) = 𝐰_{𝑗}$ for each $𝑗$ , which describes the map sending one basis to the other.

(d) False. With $𝒰︀$ as in (a), ${[𝑆_{ℓ}]}_{𝒰︀ 𝒰︀} =$ $(\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ is diagonal, but ${[𝑆_{ℓ}]}_{ℰ︀ ℰ︀} =$ $\frac{1}{5} (\begin{matrix} - 3 & 4 \\ 4 & 3 \end{matrix})$ is not (Example 2.3.19).

(e) False. The columns of ${[id]}_{𝒞︀ ℬ︀}$ are ${[𝐯_{1}]}_{𝒞︀}$ and ${[𝐯_{2}]}_{𝒞︀}$ . If both are $(1, 1)$ , then $𝐯_{1} = 𝐰_{1} + 𝐰_{2} = 𝐯_{2}$ , so $ℬ︀$ contains a vector twice and is linearly dependent, which is impossible for a basis.

Exercise 2.3.37.standard Let $𝑇 \in L (𝑉, 𝑊)$ and $𝐴 = {[𝑇]}_{𝒞︀ ℬ︀}$ . Describe how $𝐴$ changes when the bases are modified as follows, and prove your answer. (Each modified list is again a basis; check this too.)

(a)Two vectors $𝐯_{𝑗}$ and $𝐯_{𝑘}$ of $ℬ︀$ are swapped.
(b) $𝐯_{𝑗}$ is replaced by $𝑐 𝐯_{𝑗}$ , where $𝑐 \neq 0$ .
(c)Two vectors $𝐰_{𝑖}$ and $𝐰_{𝑘}$ of $𝒞︀$ are swapped.
(d) $𝐰_{𝑖}$ is replaced by $𝑐 𝐰_{𝑖}$ , where $𝑐 \neq 0$ .
(e) $𝐰_{𝑘}$ is replaced by $𝐰_{𝑘} + 𝑐 𝐰_{𝑖}$ , where $𝑖 \neq 𝑘$ and $𝑐 \in 𝐹$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.14 (Coordinates), Definition 1.6.1 (Basis)

Hint 1. Changing

ℬ︀

changes which vectors

𝑇

is applied to, so it acts on the columns. Changing

𝒞︀

changes the coordinates of every value, so it acts on the rows.

Hint 2. For (d) and (e), take

𝑇 (𝐯_{𝑗}) =

\sum_{𝑙} 𝑎_{𝑙 𝑗} 𝐰_{𝑙}

and rewrite the right side in the new basis. In (e),

𝐰_{𝑘} =

(𝐰_{𝑘} + 𝑐 𝐰_{𝑖}) -

𝑐 𝐰_{𝑖}

Sketch. (a) Columns

𝑗

and

𝑘

swap. (b) Column

𝑗

is multiplied by

𝑐

. (c) Rows

𝑖

and

𝑘

swap. (d) Row

𝑖

is multiplied by

𝑐^{- 1}

, since

𝑎 𝐰_{𝑖} =

(𝑎 𝑐^{- 1}) (𝑐 𝐰_{𝑖})

. (e) Row

𝑖

becomes row

𝑖

minus

𝑐

times row

𝑘

, since

𝑎 𝐰_{𝑘} =

𝑎 (𝐰_{𝑘} + 𝑐 𝐰_{𝑖}) -

𝑎 𝑐 𝐰_{𝑖}

The modified lists are bases. Reordering a list does not change which combinations represent a vector, only the order of the terms, so (a) and (c) give bases. For (b),

\sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙} = \sum_{𝑙 \neq 𝑗} 𝑎_{𝑙} 𝐯_{𝑙} + (𝑎_{𝑗} 𝑐^{- 1}) (𝑐 𝐯_{𝑗}),

so a vector has a representation in the new list exactly when it has one in the old, and the coefficients correspond one to one; the same goes for (d). For (e), write $𝐰_{𝑘}^{'} = 𝐰_{𝑘} + 𝑐 𝐰_{𝑖}$ and $𝐰_{𝑙}^{'} = 𝐰_{𝑙}$ for $𝑙 \neq 𝑘$ . Then

\sum_{𝑙} 𝑏_{𝑙} 𝐰_{𝑙}^{'} = \sum_{𝑙} 𝑏_{𝑙} 𝐰_{𝑙} + 𝑐 𝑏_{𝑘} 𝐰_{𝑖},

so the combination with coefficients $(𝑏_{𝑙})$ in the new list equals the combination with coefficients $(𝑎_{𝑙})$ in the old list, where $𝑎_{𝑙} = 𝑏_{𝑙}$ for $𝑙 \neq 𝑖$ and $𝑎_{𝑖} = 𝑏_{𝑖} + 𝑐 𝑏_{𝑘}$ . This correspondence between coefficient lists is a bijection (its inverse is $𝑏_{𝑙} = 𝑎_{𝑙}$ for $𝑙 \neq 𝑖$ and $𝑏_{𝑖} = 𝑎_{𝑖} - 𝑐 𝑎_{𝑘}$ ), so every vector has exactly one representation in the new list.

(a) The columns of the new matrix are ${[𝑇 (𝐯_{𝑙})]}_{𝒞︀}$ in the new order, so columns $𝑗$ and $𝑘$ of $𝐴$ are swapped.

(b) The new $𝑗$ -th column is ${[𝑇 (𝑐 𝐯_{𝑗})]}_{𝒞︀} =$ $𝑐 {[𝑇 (𝐯_{𝑗})]}_{𝒞︀}$ by linearity of $𝑇$ and of coordinates, so column $𝑗$ is multiplied by $𝑐$ ; the other columns are unchanged.

(c) The coordinates of a vector with respect to the reordered basis are its old coordinates reordered in the same way. So in every column, the entries in positions $𝑖$ and $𝑘$ are swapped: rows $𝑖$ and $𝑘$ of $𝐴$ are swapped.

(d) For each $𝑗$ ,

𝑇 (𝐯_{𝑗}) = \sum_{𝑙 \neq 𝑖} 𝑎_{𝑙 𝑗} 𝐰_{𝑙} + (𝑎_{𝑖 𝑗} 𝑐^{- 1}) (𝑐 𝐰_{𝑖}),

so in the new basis the coordinates of $𝑇 (𝐯_{𝑗})$ are the old ones with the $𝑖$ -th entry multiplied by $𝑐^{- 1}$ . Row $𝑖$ of $𝐴$ is multiplied by $𝑐^{- 1}$ , not by $𝑐$ .

(e) For each $𝑗$ , substituting $𝐰_{𝑘} = 𝐰_{𝑘}^{'} - 𝑐 𝐰_{𝑖}$ ,

𝑇 (𝐯_{𝑗}) = \sum_{𝑙 \neq 𝑘} 𝑎_{𝑙 𝑗} 𝐰_{𝑙} + 𝑎_{𝑘 𝑗} (𝐰_{𝑘}^{'} - 𝑐 𝐰_{𝑖}) = \sum_{𝑙 \neq 𝑖, 𝑘} 𝑎_{𝑙 𝑗} 𝐰_{𝑙}^{'} + (𝑎_{𝑖 𝑗} - 𝑐 𝑎_{𝑘 𝑗}) 𝐰_{𝑖}^{'} + 𝑎_{𝑘 𝑗} 𝐰_{𝑘}^{'} .

So row $𝑖$ of $𝐴$ is replaced by row $𝑖$ minus $𝑐$ times row $𝑘$ , and the other rows are unchanged.

In the language of Section 3.2: changing the basis of the target performs row operations on the matrix, and changing the basis of the domain performs column operations. Note that in (d) and (e) the row operation undoes the operation on the basis, with the roles of the indices exchanged in (e): adding $𝑐$ times $𝐰_{𝑖}$ to $𝐰_{𝑘}$ subtracts $𝑐$ times row $𝑘$ from row $𝑖$ .

Exercise 2.3.38.standard A matrix

𝐴 \in 𝐹^{𝑛 \times 𝑛}

is upper triangular if

𝑎_{𝑖 𝑗} = 0

whenever

𝑖 > 𝑗

. Let

𝑇 \in L (𝑉)

, and for

𝑘 = 1, \dots, 𝑛

let

𝑉_{𝑘} =

span (𝐯_{1}, \dots, 𝐯_{𝑘})

. Show that the following are equivalent.

(i) ${[𝑇]}_{ℬ︀ ℬ︀}$ is upper triangular.
(ii) $𝑇 (𝐯_{𝑘}) \in 𝑉_{𝑘}$ for $𝑘 = 1, \dots, 𝑛$ .
(iii) $𝑇 (𝑉_{𝑘}) \subseteq 𝑉_{𝑘}$ for $𝑘 = 1, \dots, 𝑛$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.14 (Coordinates), Proposition 2.1.16 (Linear maps preserve spans and linear relations), Proposition 1.4.14 (The span is the smallest subspace containing a list)

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. Column

𝑘

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

{[𝑇 (𝐯_{𝑘})]}_{ℬ︀}

. Upper triangular means that its entries below position

𝑘

vanish.

Hint 2. For (ii)

\Rightarrow

(iii),

𝑇 (𝑉_{𝑘})

is spanned by

𝑇 (𝐯_{1}),

\dots,

𝑇 (𝐯_{𝑘})

, and each of these lies in

𝑉_{𝑗} \subseteq 𝑉_{𝑘}

for some

𝑗 \leq 𝑘

Sketch. (i)

\Leftrightarrow

(ii):

𝑎_{𝑖 𝑘} = 0

for all

𝑖 > 𝑘

says that

𝑇 (𝐯_{𝑘}) =

\sum_{𝑖 \leq 𝑘} 𝑎_{𝑖 𝑘} 𝐯_{𝑖} \in

𝑉_{𝑘}

, and conversely, by uniqueness of coordinates. (ii)

\Rightarrow

(iii):

𝑇 (𝑉_{𝑘}) =

span (𝑇 (𝐯_{1}), \dots, 𝑇 (𝐯_{𝑘})) \subseteq

𝑉_{𝑘}

. (iii)

\Rightarrow

(ii):

𝐯_{𝑘} \in 𝑉_{𝑘}

(i) $\Leftrightarrow$ (ii). Fix $𝑘$ . The $𝑘$ -th column of ${[𝑇]}_{ℬ︀ ℬ︀}$ is ${[𝑇 (𝐯_{𝑘})]}_{ℬ︀} =$ $(𝑎_{1 𝑘}, \dots, 𝑎_{𝑛 𝑘})$ , so $𝑇 (𝐯_{𝑘}) =$ $\sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖 𝑘} 𝐯_{𝑖}$ . If $𝑎_{𝑖 𝑘} = 0$ for all $𝑖 > 𝑘$ , then $𝑇 (𝐯_{𝑘}) =$ $\sum_{𝑖 \leq 𝑘} 𝑎_{𝑖 𝑘} 𝐯_{𝑖} \in$ $𝑉_{𝑘}$ . Conversely, if $𝑇 (𝐯_{𝑘}) \in 𝑉_{𝑘}$ , then $𝑇 (𝐯_{𝑘}) =$ $\sum_{𝑖 \leq 𝑘} 𝑐_{𝑖} 𝐯_{𝑖}$ for some scalars, which is a representation in terms of $ℬ︀$ with coefficients $0$ for $𝑖 > 𝑘$ . By uniqueness of coordinates (Definition 1.6.14), $𝑎_{𝑖 𝑘} = 0$ for $𝑖 > 𝑘$ . Applying this for every $𝑘$ gives the equivalence.

(ii) $\Rightarrow$ (iii). For $𝑗 \leq 𝑘$ , $𝑇 (𝐯_{𝑗}) \in$ $𝑉_{𝑗} \subseteq$ $𝑉_{𝑘}$ . By Proposition 2.1.16, $𝑇 (𝑉_{𝑘}) =$ $span (𝑇 (𝐯_{1}), \dots, 𝑇 (𝐯_{𝑘}))$ , and this is contained in the subspace $𝑉_{𝑘}$ by Proposition 1.4.14.

(iii) $\Rightarrow$ (ii). $𝐯_{𝑘} \in 𝑉_{𝑘}$ , so $𝑇 (𝐯_{𝑘}) \in$ $𝑇 (𝑉_{𝑘}) \subseteq$ $𝑉_{𝑘}$ .

For example, ${[𝐷]}_{ℬ︀ ℬ︀}$ in Example 2.3.4 is upper triangular, because $𝐷$ maps polynomials of degree at most $𝑘$ to polynomials of degree at most $𝑘$ . Upper-triangular matrices of operators return in Section 7.5.

Exercise 2.3.39.hard Let

𝑁 \in 𝐹^{4 \times 4}

be the matrix with

1

in positions

(1, 2)

(2, 3)

(3, 4)

and

0

elsewhere, and let

𝐷

be differentiation on

{𝐹 [𝑥]}_{\leq 3}

. For each of

𝐹 = ℚ

𝔽_{2}

𝔽_{3}

𝔽_{5}

, decide whether there is a basis

ℬ︀

{𝐹 [𝑥]}_{\leq 3}

with

{[𝐷]}_{ℬ︀ ℬ︀} = 𝑁

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Example 2.1.9 (Maps of polynomials), Corollary 2.2.6 (Agreeing on a spanning list), Proposition 1.1.24 ( $ℤ / 𝑛 ℤ$ is a field if and only if $𝑛$ is prime)

Hint 1. Read off what

{[𝐷]}_{ℬ︀ ℬ︀} = 𝑁

says about

𝐷 (𝐯_{1}), \dots, 𝐷 (𝐯_{4})

. What is

𝐷 (𝐷 (𝐷 (𝐯_{4})))

Hint 2. Over

𝔽_{2}

, compute

𝐷 (𝐷 (𝑥^{𝑘}))

; over

𝔽_{3}

, compute

𝐷 (𝐷 (𝐷 (𝑥^{𝑘})))

. Products of two, or of three, consecutive integers are divisible by

2

, or by

3

Hint 3. Over

ℚ

and

𝔽_{5}

, try to scale the monomials so that each one differentiates to the previous one.

Sketch.

{[𝐷]}_{ℬ︀ ℬ︀} = 𝑁

means

𝐷 (𝐯_{1}) = 𝟎

and

𝐷 (𝐯_{𝑘}) = 𝐯_{𝑘 - 1}

, so

𝐷^{3} (𝐯_{4}) = 𝐯_{1} \neq 𝟎

and

𝐷^{2} (𝐯_{3}) = 𝐯_{1} \neq 𝟎

. Over

𝔽_{2}

𝐷^{2} = 0

since

𝑘 (𝑘 - 1)

is even; over

𝔽_{3}

𝐷^{3} = 0

since

𝑘 (𝑘 - 1) (𝑘 - 2)

is divisible by

3

. So no basis exists there. Over

ℚ

and

𝔽_{5}

6 \neq 0

and

1, 𝑥, 𝑥^{2} / 2, 𝑥^{3} / 6

works.

The $𝑘$ -th column of $𝑁$ is $𝟎$ for $𝑘 = 1$ and $𝐞_{𝑘 - 1}$ for $𝑘 = 2, 3, 4$ . So ${[𝐷]}_{ℬ︀ ℬ︀} = 𝑁$ for $ℬ︀ =$ $𝐯_{1},$ $𝐯_{2},$ $𝐯_{3},$ $𝐯_{4}$ means exactly that

𝐷 (𝐯_{1}) = 𝟎, 𝐷 (𝐯_{2}) = 𝐯_{1}, 𝐷 (𝐯_{3}) = 𝐯_{2}, 𝐷 (𝐯_{4}) = 𝐯_{3} .

In that case $𝐷 (𝐷 (𝐯_{3})) = 𝐯_{1}$ and $𝐷 (𝐷 (𝐷 (𝐯_{4}))) =$ $𝐯_{1}$ , and $𝐯_{1} \neq 𝟎$ because it belongs to a basis.

$𝔽_{2}$ : no. For $𝑘 \geq 2$ , $𝐷 (𝐷 (𝑥^{𝑘})) =$ $𝑘 (𝑘 - 1) 𝑥^{𝑘 - 2}$ , and $𝑘 (𝑘 - 1)$ is even, so it is $0$ in $𝔽_{2}$ . Also $𝐷 (𝐷 (1)) =$ $𝐷 (𝐷 (𝑥)) =$ $𝟎$ . So the linear maps $𝐷 \circ 𝐷$ and $0$ agree on the basis $1, 𝑥, 𝑥^{2}, 𝑥^{3}$ , and $𝐷 \circ 𝐷 = 0$ (Corollary 2.2.6). This contradicts $𝐷 (𝐷 (𝐯_{3})) =$ $𝐯_{1} \neq$ $𝟎$ .

$𝔽_{3}$ : no. For $𝑘 \geq 3$ , $𝐷 (𝐷 (𝐷 (𝑥^{𝑘}))) =$ $𝑘 (𝑘 - 1) (𝑘 - 2) 𝑥^{𝑘 - 3}$ , and one of three consecutive integers is divisible by $3$ , so the coefficient is $0$ in $𝔽_{3}$ . For $𝑘 \leq 2$ , $𝐷 (𝐷 (𝐷 (𝑥^{𝑘}))) =$ $𝟎$ as well. As before, $𝐷 \circ 𝐷 \circ 𝐷 = 0$ , contradicting $𝐷 (𝐷 (𝐷 (𝐯_{4}))) =$ $𝐯_{1} \neq$ $𝟎$ .

$ℚ$ and $𝔽_{5}$ : yes. In both fields $2 \neq 0$ and $6 \neq 0$ (in $𝔽_{5}$ , $6 = 1$ ). Let

ℬ︀ = 1, 𝑥, \frac{1}{2} 𝑥^{2}, \frac{1}{6} 𝑥^{3} .

It is a basis of ${𝐹 [𝑥]}_{\leq 3}$ , since

𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2} + 𝑑 𝑥^{3} = 𝑎 \cdot 1 + 𝑏 𝑥 + 2 𝑐 \cdot \frac{1}{2} 𝑥^{2} + 6 𝑑 \cdot \frac{1}{6} 𝑥^{3},

and these coefficients are the only possible ones. Also $𝐷 (1) = 𝟎$ , $𝐷 (𝑥) = 1$ , $𝐷 (\frac{1}{2} 𝑥^{2}) = 𝑥$ , and $𝐷 (\frac{1}{6} 𝑥^{3}) = \frac{1}{2} 𝑥^{2}$ , so ${[𝐷]}_{ℬ︀ ℬ︀} = 𝑁$ . Over $𝔽_{5}$ , $\frac{1}{2} = 3$ and $\frac{1}{6} = 1$ , so the basis is $1, 𝑥, 3 𝑥^{2}, 𝑥^{3}$ ; for instance $𝐷 (𝑥^{3}) = 3 𝑥^{2}$ .

So the answer depends on the field: the property $𝐷 \circ 𝐷 \circ 𝐷 \neq 0$ , which every operator with matrix $𝑁$ has, holds over $ℚ$ and $𝔽_{5}$ and fails over $𝔽_{2}$ and $𝔽_{3}$ .

Exercise 2.3.40.hard Let

𝑇 \in L (𝑉)

, where

𝑉

has a basis of length

𝑛 \geq 1

. Show that

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

is the same matrix for every basis

ℬ︀

𝑉

of length

𝑛

if and only if

𝑇 = 𝜆 {id}_{𝑉}

for some

𝜆 \in 𝐹

. (In Section 4.1 we will see that every basis of

𝑉

has length

𝑛

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Example 2.3.6 (The zero map and the identity map), Theorem 2.3.20 (Linear maps correspond to matrices), Exercise 2.3.37

Hint 1. One direction is quick: what is

{[𝜆 {id}_{𝑉}]}_{ℬ︀ ℬ︀}

? For the other, fix one basis

ℬ︀

with matrix

𝐴

, and compare

𝐴

with the matrix in a cleverly modified basis.

Hint 2. For

𝑖 \neq 𝑗

, replace

𝐯_{𝑗}

𝐯_{𝑗} + 𝐯_{𝑖}

. How do the coordinates of a vector change? (See Exercise 2.3.37.)

Hint 3. In the new basis, a vector’s coordinates are the old ones except that the

𝑖

-th becomes (old

𝑖

-th) minus (old

𝑗

-th). Compare the entries in row

𝑖

of the two matrices, first in a column

𝑘 \neq 𝑗

, then in column

𝑗

Sketch.

{[𝜆 id]}_{ℬ︀ ℬ︀} = 𝜆 𝐼_{𝑛}

for every

ℬ︀

. Conversely, let

𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}

and let

{ℬ︀}^{'}

ℬ︀

with

𝐯_{𝑗}

replaced by

𝐯_{𝑗} + 𝐯_{𝑖}

. The

{ℬ︀}^{'}

-coordinates of a vector are its

ℬ︀

-coordinates with the

𝑖

-th entry replaced by (entry

𝑖

)

-

(entry

𝑗

). Entry

(𝑖, 𝑘)

{[𝑇]}_{{ℬ︀}^{'} {ℬ︀}^{'}}

for

𝑘 \neq 𝑗

𝑎_{𝑖 𝑘} - 𝑎_{𝑗 𝑘}

, so

𝑎_{𝑗 𝑘} = 0

. Entry

(𝑖, 𝑗)

𝑎_{𝑖 𝑗} +

𝑎_{𝑖 𝑖} -

𝑎_{𝑗 𝑗} -

𝑎_{𝑗 𝑖}

, so

𝑎_{𝑖 𝑖} = 𝑎_{𝑗 𝑗}

. Hence

𝐴 = 𝜆 𝐼_{𝑛}

and

𝑇 = 𝜆 id

If $𝑇 = 𝜆 {id}_{𝑉}$ . Then $𝑇 (𝐯_{𝑗}) = 𝜆 𝐯_{𝑗}$ , whose coordinate vector is $𝜆 𝐞_{𝑗}$ , so ${[𝑇]}_{ℬ︀ ℬ︀} = 𝜆 𝐼_{𝑛}$ for every basis $ℬ︀$ of length $𝑛$ .

Conversely, suppose all the matrices ${[𝑇]}_{ℬ︀ ℬ︀}$ with $ℬ︀$ of length $𝑛$ are equal. Fix a basis $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ and let $𝐴 = {[𝑇]}_{ℬ︀ ℬ︀}$ . If $𝑛 = 1$ , then $𝐴 = (𝜆)$ for some $𝜆$ , so $𝑇 (𝐯_{1}) = 𝜆 𝐯_{1}$ , and $𝑇 = 𝜆 {id}_{𝑉}$ because both are linear and agree on the basis.

Let $𝑛 \geq 2$ , and fix $𝑖 \neq 𝑗$ . Let ${ℬ︀}^{'}$ be $ℬ︀$ with $𝐯_{𝑗}$ replaced by $𝐯_{𝑗} + 𝐯_{𝑖}$ ; it is a basis of length $𝑛$ by Exercise 2.3.37(e) (with $𝑐 = 1$ ). Since $𝐯_{𝑗} =$ $(𝐯_{𝑗} + 𝐯_{𝑖}) -$ $𝐯_{𝑖}$ , a vector $𝐲 = \sum_{𝑙} 𝑐_{𝑙} 𝐯_{𝑙}$ equals

𝐲 = \sum_{𝑙 \neq 𝑖, 𝑗} 𝑐_{𝑙} 𝐯_{𝑙} + (𝑐_{𝑖} - 𝑐_{𝑗}) 𝐯_{𝑖} + 𝑐_{𝑗} (𝐯_{𝑗} + 𝐯_{𝑖}) .

So ${[𝐲]}_{{ℬ︀}^{'}}$ is ${[𝐲]}_{ℬ︀}$ with the $𝑖$ -th entry replaced by $𝑐_{𝑖} - 𝑐_{𝑗}$ .

Column $𝑘 \neq 𝑗$ . The $𝑘$ -th vector of ${ℬ︀}^{'}$ is $𝐯_{𝑘}$ , and $𝑇 (𝐯_{𝑘}) =$ $\sum_{𝑙} 𝑎_{𝑙 𝑘} 𝐯_{𝑙}$ . So the $(𝑖, 𝑘)$ entry of ${[𝑇]}_{{ℬ︀}^{'} {ℬ︀}^{'}}$ is $𝑎_{𝑖 𝑘} - 𝑎_{𝑗 𝑘}$ . Since this matrix equals $𝐴$ , $𝑎_{𝑖 𝑘} -$ $𝑎_{𝑗 𝑘} =$ $𝑎_{𝑖 𝑘}$ , that is, $𝑎_{𝑗 𝑘} = 0$ . Since $𝑛 \geq 2$ , for every $𝑗$ there is some $𝑖 \neq 𝑗$ , so $𝑎_{𝑗 𝑘} = 0$ whenever $𝑗 \neq 𝑘$ : $𝐴$ is diagonal.

Column $𝑗$ . The $𝑗$ -th vector of ${ℬ︀}^{'}$ is $𝐯_{𝑗} + 𝐯_{𝑖}$ , and $𝑇 (𝐯_{𝑗} + 𝐯_{𝑖}) =$ $\sum_{𝑙} (𝑎_{𝑙 𝑗} + 𝑎_{𝑙 𝑖}) 𝐯_{𝑙}$ . So the $(𝑖, 𝑗)$ entry of ${[𝑇]}_{{ℬ︀}^{'} {ℬ︀}^{'}}$ is $(𝑎_{𝑖 𝑗} + 𝑎_{𝑖 𝑖}) -$ $(𝑎_{𝑗 𝑗} + 𝑎_{𝑗 𝑖}) =$ $𝑎_{𝑖 𝑖} -$ $𝑎_{𝑗 𝑗}$ , using that $𝐴$ is diagonal. It must equal $𝑎_{𝑖 𝑗} = 0$ , so $𝑎_{𝑖 𝑖} = 𝑎_{𝑗 𝑗}$ .

So $𝐴 = 𝜆 𝐼_{𝑛}$ with $𝜆 = 𝑎_{11}$ . Since ${[𝜆 {id}_{𝑉}]}_{ℬ︀ ℬ︀} =$ $𝜆 𝐼_{𝑛}$ as well, $𝑇 = 𝜆 {id}_{𝑉}$ by Theorem 2.3.20.

Exercise 2.3.41.hard Lights out on a line. A row of $𝑛 \geq 2$ lamps is controlled by $𝑛$ buttons. Pressing button $𝑖$ switches lamp $𝑖$ and its neighbours (lamps $𝑖 - 1$ and $𝑖 + 1$ , when they exist) from on to off or from off to on. Record a configuration of the lamps as $𝐬 \in 𝔽_{2}^{𝑛}$ , with $𝑠_{𝑖} = 1$ when lamp $𝑖$ is on.

(a)Let $𝐴 \in 𝔽_{2}^{𝑛 \times 𝑛}$ have $𝑎_{𝑖 𝑗} = 1$ when $| 𝑖 - 𝑗 | \leq 1$ and $𝑎_{𝑖 𝑗} = 0$ otherwise. Show that pressing buttons in any order changes the configuration $𝐬$ to $𝐬 + 𝐴 𝐱$ , where $𝑥_{𝑗} \in 𝔽_{2}$ is the number of times button $𝑗$ was pressed, modulo $2$ .
(b)Show that every configuration can be switched off completely if and only if $𝑛$ is not of the form $3 𝑘 + 2$ .

Solution.

Uses. Definition 2.3.8 (Matrix–vector product), Proposition 2.3.11 (Entries of $𝐴 𝐱$ )

Hint 1. Pressing button

𝑗

adds the

𝑗

-th column of

𝐴

𝐬

. Over

𝔽_{2}

, adding a vector twice adds nothing.

Hint 2. Switching everything off means solving

𝐴 𝐱 = 𝐬

. Set

𝑥_{0} = 𝑥_{𝑛 + 1} = 0

, so that every equation reads

𝑥_{𝑖 - 1} +

𝑥_{𝑖} +

𝑥_{𝑖 + 1} =

𝑠_{𝑖}

. Once

𝑥_{1}

is chosen, the equations for

𝑖 = 1, \dots, 𝑛 - 1

determine

𝑥_{2}, \dots, 𝑥_{𝑛}

one at a time.

Hint 3. Compare the two sequences obtained from

𝑥_{1} = 0

and

𝑥_{1} = 1

. Their sum satisfies

𝑑_{𝑖 + 1} =

𝑑_{𝑖} +

𝑑_{𝑖 - 1}

with

𝑑_{0} = 0

𝑑_{1} = 1

, which is periodic:

0, 1, 1, 0, 1, 1, \dots

Sketch. (a) Each press of button

𝑗

adds column

𝐚_{𝑗}

; addition in

𝔽_{2}^{𝑛}

is commutative and

𝐚_{𝑗} + 𝐚_{𝑗} = 𝟎

, so the total change is

\sum_{𝑗} 𝑥_{𝑗} 𝐚_{𝑗} = 𝐴 𝐱

. (b) Solving

𝐴 𝐱 = 𝐬

by choosing

𝑥_{1}

and propagating, the last equation becomes

𝑥_{𝑛 + 1} = 0

. The two choices of

𝑥_{1}

give values of

𝑥_{𝑛 + 1}

differing by

𝑑_{𝑛 + 1}

, where

𝑑

0, 1, 1

repeated. If

3 ∤ 𝑛 + 1

, exactly one choice works for each

𝐬

. If

3 ∣ 𝑛 + 1

, either both or neither work, so each solvable

𝐬

has two solutions

𝐱

, only

2^{𝑛 - 1}

of the

2^{𝑛}

configurations are solvable, and some configuration cannot be switched off.

(a) Pressing button $𝑗$ switches exactly the lamps $𝑖$ with $| 𝑖 - 𝑗 | \leq 1$ , that is, it adds to $𝐬$ the vector $𝐚_{𝑗}$ with $1$ in these positions, which is the $𝑗$ -th column of $𝐴$ . A sequence of presses adds the corresponding columns, and since addition in $𝔽_{2}^{𝑛}$ is commutative, the order does not matter. Since $𝐚_{𝑗} + 𝐚_{𝑗} = 𝟎$ in $𝔽_{2}^{𝑛}$ , pressing button $𝑗$ a total of $𝑚_{𝑗}$ times adds $𝐚_{𝑗}$ if $𝑚_{𝑗}$ is odd and nothing if it is even. So the configuration becomes $𝐬 +$ $\sum_{𝑗} 𝑥_{𝑗} 𝐚_{𝑗} =$ $𝐬 +$ $𝐴 𝐱$ (Definition 2.3.8).

(b) By (a), $𝐬$ can be switched off exactly when $𝐬 + 𝐴 𝐱 = 𝟎$ for some $𝐱 \in 𝔽_{2}^{𝑛}$ , that is, when $𝐴 𝐱 = 𝐬$ (in $𝔽_{2}$ , $- 𝐬 = 𝐬$ ). By Proposition 2.3.11, with the convention $𝑥_{0} = 𝑥_{𝑛 + 1} = 0$ , this system reads

𝑥_{𝑖 - 1} + 𝑥_{𝑖} + 𝑥_{𝑖 + 1} = 𝑠_{𝑖} (𝑖 = 1, \dots, 𝑛) .

Propagation. Given $𝐬$ and a choice of $𝑥_{1} \in 𝔽_{2}$ , set $𝑥_{0} = 0$ and define $𝑥_{2}, 𝑥_{3}, \dots, 𝑥_{𝑛 + 1}$ by $𝑥_{𝑖 + 1} =$ $𝑠_{𝑖} +$ $𝑥_{𝑖 - 1} +$ $𝑥_{𝑖}$ for $𝑖 = 1, \dots, 𝑛$ . For $𝑖 \leq 𝑛 - 1$ this is forced by the $𝑖$ -th equation, and the last step defines a number $𝑥_{𝑛 + 1}$ . The sequence $𝑥_{1}, \dots, 𝑥_{𝑛}$ is a solution if and only if the $𝑛$ -th equation also holds with $𝑥_{𝑛 + 1} = 0$ , that is, if and only if the propagated value $𝑥_{𝑛 + 1}$ is $0$ . Every solution arises this way from its own $𝑥_{1}$ . So for each $𝐬$ , the solutions correspond to those $𝑥_{1} \in {0, 1}$ whose propagated $𝑥_{𝑛 + 1}$ is $0$ .

Comparing the two choices. Let $𝑥$ and $𝑥^{'}$ be the sequences propagated from $𝑥_{1} = 0$ and $𝑥_{1}^{'} = 1$ , and let $𝑑_{𝑖} = 𝑥_{𝑖} + 𝑥_{𝑖}^{'}$ . Then $𝑑_{0} = 0$ , $𝑑_{1} = 1$ , and $𝑑_{𝑖 + 1} =$ $𝑑_{𝑖 - 1} +$ $𝑑_{𝑖}$ , since the $𝑠_{𝑖}$ cancel. So $𝑑 =$ $0,$ $1,$ $1,$ $0,$ $1,$ $1,$ $0,$ $\dots$ , and $𝑑_{𝑖} = 0$ exactly when $3$ divides $𝑖$ .

If $3 ∤ 𝑛 + 1$ , then $𝑥_{𝑛 + 1} +$ $𝑥_{𝑛 + 1}^{'} =$ $𝑑_{𝑛 + 1} =$ $1$ , so exactly one of $𝑥_{𝑛 + 1}, 𝑥_{𝑛 + 1}^{'}$ is $0$ , and $𝐴 𝐱 = 𝐬$ has exactly one solution. Every configuration can be switched off.

If $3 ∣ 𝑛 + 1$ , then $𝑥_{𝑛 + 1} = 𝑥_{𝑛 + 1}^{'}$ , so for each $𝐬$ the system has either two solutions or none. Each of the $2^{𝑛}$ vectors $𝐱$ solves the system for exactly one $𝐬$ , namely $𝐬 = 𝐴 𝐱$ . So the solvable configurations number $2^{𝑛} / 2 =$ $2^{𝑛 - 1} <$ $2^{𝑛}$ , and some configuration cannot be switched off. Finally, $3$ divides $𝑛 + 1$ exactly when $𝑛 = 3 𝑘 + 2$ for some integer $𝑘 \geq 0$ .

For example, for $𝑛 = 2$ the matrix is $(\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ , both buttons switch both lamps, and the configuration $(1, 0)$ cannot be switched off.

Exercise 2.3.42.standard Using the matrix of

Δ (𝑝) =

𝑝 (𝑥 + 1) -

𝑝 (𝑥)

{ℚ [𝑥]}_{\leq 3}

with respect to

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

, find all

𝑝 \in {ℚ [𝑥]}_{\leq 3}

with

𝑝 (𝑥 + 1) -

𝑝 (𝑥) =

𝑥^{2}

. Deduce a formula for

0^{2} + 1^{2} + \dots + {(𝑛 - 1)}^{2}

, as in Example 2.3.28.

Solution.

Uses. Example 2.3.28 (Translating in both directions), Theorem 2.3.9 (The matrix of a map computes the map), Proposition 2.3.11 (Entries of $𝐴 𝐱$ )

Techniques. Translate between maps and matrices (Technique 2.3.27)

Hint 1.

Δ (𝑥^{3}) =

{(𝑥 + 1)}^{3} -

𝑥^{3} =

1 +

3 𝑥 +

3 𝑥^{2}

. The other columns are as in Example 2.3.28, with an extra zero row.

Hint 2. Solve

[Δ] (𝑎, 𝑏, 𝑐, 𝑑) =

(0, 0, 1, 0)

from the bottom up.

Sketch. The new column is

(1, 3, 3, 0)

. The system

𝑏 + 𝑐 + 𝑑 = 0

2 𝑐 + 3 𝑑 = 0

3 𝑑 = 1

gives

𝑑 = 1 / 3

𝑐 = - 1 / 2

𝑏 = 1 / 6

𝑎

free, so

𝑝 =

𝑎 +

𝑥 (𝑥 - 1) (2 𝑥 - 1) / 6

. Telescoping gives

\sum_{𝑘 = 0}^{𝑛 - 1} 𝑘^{2} =

𝑛 (𝑛 - 1) (2 𝑛 - 1) / 6

With $ℬ︀ = 1, 𝑥, 𝑥^{2}, 𝑥^{3}$ , we have $Δ (1) = 𝟎$ , $Δ (𝑥) = 1$ , $Δ (𝑥^{2}) = 1 + 2 𝑥$ , and $Δ (𝑥^{3}) = 1 + 3 𝑥 + 3 𝑥^{2}$ , so

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

For $𝑝 =$ $𝑎 +$ $𝑏 𝑥 +$ $𝑐 𝑥^{2} +$ $𝑑 𝑥^{3}$ , the equation $Δ (𝑝) = 𝑥^{2}$ becomes ${[Δ]}_{ℬ︀ ℬ︀} (𝑎, 𝑏, 𝑐, 𝑑) =$ $(0, 0, 1, 0)$ (Theorem 2.3.9), that is,

𝑏 + 𝑐 + 𝑑 = 0, 2 𝑐 + 3 𝑑 = 0, 3 𝑑 = 1 .

So $𝑑 = 1 / 3$ , $𝑐 = - 1 / 2$ , $𝑏 = 1 / 2 - 1 / 3 = 1 / 6$ , and $𝑎$ is arbitrary:

𝑝 = 𝑎 + \frac{𝑥}{6} - \frac{𝑥^{2}}{2} + \frac{𝑥^{3}}{3} = 𝑎 + \frac{𝑥 (𝑥 - 1) (2 𝑥 - 1)}{6} .

(Indeed $𝑥 (𝑥 - 1) (2 𝑥 - 1) =$ $2 𝑥^{3} -$ $3 𝑥^{2} +$ $𝑥$ .)

For $𝑞 (𝑡) =$ $𝑡 (𝑡 - 1) (2 𝑡 - 1) / 6$ and every number $𝑡$ ,

𝑞 (𝑡 + 1) - 𝑞 (𝑡) = \frac{𝑡 ((𝑡 + 1) (2 𝑡 + 1) - (𝑡 - 1) (2 𝑡 - 1))}{6} = \frac{𝑡 \cdot 6 𝑡}{6} = 𝑡^{2} .

Summing over $𝑡 = 0, 1, \dots, 𝑛 - 1$ , the right side telescopes:

\sum_{𝑘 = 0}^{𝑛 - 1} 𝑘^{2} = 𝑞 (𝑛) - 𝑞 (0) = \frac{𝑛 (𝑛 - 1) (2 𝑛 - 1)}{6} .

For $𝑛 = 3$ : $0 + 1 + 4 = 5 = (3 \cdot 2 \cdot 5) / 6$ .

Exercise 2.3.43.standard For $𝐲 \in 𝐹^{𝑘}$ let $𝑠 (𝐲) = 𝑦_{1} + \dots + 𝑦_{𝑘}$ be the sum of its entries, and let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)Show that $𝑠 (𝐴 𝐱) = 𝑠 (𝐱)$ for every $𝐱 \in 𝐹^{𝑛}$ if and only if the entries of each column of $𝐴$ add up to $1$ .
(b)Show that $𝐴 (1, \dots, 1) =$ $𝑐 (1, \dots, 1)$ if and only if the entries of each row of $𝐴$ add up to $𝑐$ .
(c)Let $𝐹 = ℝ$ , and suppose that all entries of $𝐴$ are nonnegative and each column adds up to $1$ . Show that if the entries of $𝐱$ are nonnegative and add up to $1$ , then the entries of $𝐴 𝐱$ are also nonnegative and add up to $1$ .

Solution.

Uses. Definition 2.3.8 (Matrix–vector product), Proposition 2.3.11 (Entries of $𝐴 𝐱$ ), Proposition 2.3.13 (Linearity of the product)

Hint 1. The map

𝑠

is linear. Apply it to

𝐴 𝐱 = \sum_{𝑗} 𝑥_{𝑗} 𝐚_{𝑗}

Hint 2. For the converse in (a), take

𝐱 = 𝐞_{𝑗}

. For (b), use the row-times-column rule.

Sketch. (a)

𝑠 (𝐴 𝐱) =

\sum_{𝑗} 𝑥_{𝑗} 𝑠 (𝐚_{𝑗})

, which is

𝑠 (𝐱)

when every

𝑠 (𝐚_{𝑗}) = 1

; conversely

𝑠 (𝐚_{𝑗}) =

𝑠 (𝐴 𝐞_{𝑗}) =

𝑠 (𝐞_{𝑗}) =

1

. (b) The

𝑖

-th entry of

𝐴 (1, \dots, 1)

is the

𝑖

-th row sum. (c) The entries

\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}

are sums of products of nonnegative numbers, and they add up to

1

by (a).

The map $𝑠 : 𝐹^{𝑘} \to 𝐹$ is linear, since

𝑠 (𝑐 𝐲 + 𝐳) = \sum_{𝑖} (𝑐 𝑦_{𝑖} + 𝑧_{𝑖}) = 𝑐 𝑠 (𝐲) + 𝑠 (𝐳) .

(a) Let $𝐚_{1}, \dots, 𝐚_{𝑛}$ be the columns of $𝐴$ . By Definition 2.3.8 and linearity of $𝑠$ ,

𝑠 (𝐴 𝐱) = 𝑠 (𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛}) = 𝑥_{1} 𝑠 (𝐚_{1}) + \dots + 𝑥_{𝑛} 𝑠 (𝐚_{𝑛}) .

If $𝑠 (𝐚_{𝑗}) = 1$ for every $𝑗$ , this is $𝑥_{1} + \dots + 𝑥_{𝑛} = 𝑠 (𝐱)$ . Conversely, if $𝑠 (𝐴 𝐱) = 𝑠 (𝐱)$ for all $𝐱$ , take $𝐱 = 𝐞_{𝑗}$ : by Proposition 2.3.13(c), $𝑠 (𝐚_{𝑗}) =$ $𝑠 (𝐴 𝐞_{𝑗}) =$ $𝑠 (𝐞_{𝑗}) =$ $1$ .

(b) By Proposition 2.3.11, the $𝑖$ -th entry of $𝐴 (1, \dots, 1)$ is $𝑎_{𝑖 1} + \dots + 𝑎_{𝑖 𝑛}$ , the sum of the entries of row $𝑖$ . So $𝐴 (1, \dots, 1) =$ $𝑐 (1, \dots, 1)$ if and only if every row sum is $𝑐$ .

(c) By Proposition 2.3.11, the $𝑖$ -th entry of $𝐴 𝐱$ is $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}$ , a sum of products of nonnegative numbers, hence nonnegative. By (a), the entries of $𝐴 𝐱$ add up to $𝑠 (𝐱) = 1$ . Vectors with nonnegative entries adding up to $1$ are probability distributions, and matrices as in (c) describe how they evolve in a Markov chain (Section 11.1).

Exercise 2.3.44.standardBeyond 21-242 The matrix of an operator on $𝐹 [𝑥]$ , which has no finite basis, can still be defined. For $𝑇 \in L (𝐹 [𝑥])$ , let $𝑎_{𝑖 𝑗} \in 𝐹$ ( $𝑖, 𝑗 \geq 0$ ) be the coefficients with $𝑇 (𝑥^{𝑗}) =$ $\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝑥^{𝑖}$ . Call the array ${(𝑎_{𝑖 𝑗})}_{𝑖, 𝑗 \geq 0}$ the matrix of $𝑇$ .

(a)Show that each column of the matrix has only finitely many nonzero entries, and that every array ${(𝑎_{𝑖 𝑗})}_{𝑖, 𝑗 \geq 0}$ with this property is the matrix of exactly one $𝑇 \in L (𝐹 [𝑥])$ .
(b)Find the matrices of differentiation $𝐷$ and of multiplication by $𝑥$ .
(c)Show that if $𝑝$ has coefficients $(𝑐_{0}, 𝑐_{1}, \dots)$ , then $𝑇 (𝑝)$ has coefficients ${(\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑐_{𝑗})}_{𝑖 \geq 0}$ , where each sum has only finitely many nonzero terms.
(d)Give an operator whose matrix has a row with infinitely many nonzero entries.

Solution.

Uses. Proposition 2.2.20 (Linear maps out of $𝐹 [𝑥]$ ), Definition 1.2.13 (Polynomials), Example 2.1.9 (Maps of polynomials)

Hint 1. Column

𝑗

lists the coefficients of the polynomial

𝑇 (𝑥^{𝑗})

. For the converse, use Proposition 2.2.20.

Hint 2. For (c), write

𝑝 = \sum_{𝑗} 𝑐_{𝑗} 𝑥^{𝑗}

and apply

𝑇

term by term. For (d), try an evaluation, viewed as a map into constants.

Sketch. (a)

𝑇 (𝑥^{𝑗})

is a polynomial, so its coefficients are eventually

0

. Given a column-finite array,

𝐰_{𝑗} =

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

is a polynomial, and Proposition 2.2.20 gives exactly one

𝑇

with

𝑇 (𝑥^{𝑗}) = 𝐰_{𝑗}

. (b)

𝐷

𝑎_{𝑗 - 1, 𝑗} = 𝑗

;

𝑀

𝑎_{𝑗 + 1, 𝑗} = 1

; all else

0

. (c) Expand

𝑇 (𝑝) =

\sum_{𝑗} 𝑐_{𝑗} 𝑇 (𝑥^{𝑗})

and collect the coefficient of each

𝑥^{𝑖}

. (d)

𝑝 \mapsto 𝑝 (1)

, regarded as a constant polynomial, has row

0

equal to

1, 1, 1, \dots

(a) Column $𝑗$ consists of the coefficients of the polynomial $𝑇 (𝑥^{𝑗})$ , and only finitely many coefficients of a polynomial are nonzero (Definition 1.2.13). Conversely, let $(𝑎_{𝑖 𝑗})$ be an array whose columns have finitely many nonzero entries. Then $𝐰_{𝑗} =$ $\sum_{𝑖} 𝑎_{𝑖 𝑗} 𝑥^{𝑖}$ is a polynomial for each $𝑗$ , and by Proposition 2.2.20 there is exactly one $𝑇 \in L (𝐹 [𝑥])$ with $𝑇 (𝑥^{𝑗}) = 𝐰_{𝑗}$ for every $𝑗$ . Its matrix is the given array, and any operator with this matrix sends each $𝑥^{𝑗}$ to $𝐰_{𝑗}$ , so it is this $𝑇$ .

(b) $𝐷 (𝑥^{𝑗}) = 𝑗 𝑥^{𝑗 - 1}$ for $𝑗 \geq 1$ and $𝐷 (1) = 𝟎$ , so the matrix of $𝐷$ has the entries $𝑎_{𝑗 - 1, 𝑗} = 𝑗$ for $𝑗 \geq 1$ , just above the diagonal, and zeros elsewhere. Multiplication by $𝑥$ sends $𝑥^{𝑗}$ to $𝑥^{𝑗 + 1}$ , so its matrix has $𝑎_{𝑗 + 1, 𝑗} = 1$ just below the diagonal, and zeros elsewhere.

(c) Let $𝑝 =$ $\sum_{𝑗 = 0}^{𝑑} 𝑐_{𝑗} 𝑥^{𝑗}$ , with $𝑐_{𝑗} = 0$ for $𝑗 > 𝑑$ . By linearity,

𝑇 (𝑝) = \sum_{𝑗 = 0}^{𝑑} 𝑐_{𝑗} 𝑇 (𝑥^{𝑗}) = \sum_{𝑗 = 0}^{𝑑} 𝑐_{𝑗} \sum_{𝑖} 𝑎_{𝑖 𝑗} 𝑥^{𝑖} = \sum_{𝑖} (\sum_{𝑗 = 0}^{𝑑} 𝑎_{𝑖 𝑗} 𝑐_{𝑗}) 𝑥^{𝑖} .

So the $𝑖$ -th coefficient of $𝑇 (𝑝)$ is $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑐_{𝑗}$ , in which the terms with $𝑗 > 𝑑$ are $0$ . This is the row-times-column rule of Proposition 2.3.11 for infinite matrices whose columns are finite.

(d) Let $𝑇 (𝑝) = 𝑝 (1)$ , regarded as a constant polynomial. It is linear (Example 2.1.9), and $𝑇 (𝑥^{𝑗}) = 1$ for every $𝑗$ , so row $0$ of its matrix is $1, 1, 1, \dots$ . Rows can be infinite; only the columns must be finite.

Exercise 2.3.45.routine Let $𝑇 : ℂ^{2} \to ℂ^{2}$ , $𝑇 (𝑧, 𝑤) =$ $(𝑧 + 𝑖 𝑤, 𝑖 𝑧 - 𝑤)$ .

(a)Find ${[𝑇]}_{ℰ︀ ℰ︀}$ .
(b)Show that $ℬ︀ = (1, 𝑖), (1, - 𝑖)$ is a basis of $ℂ^{2}$ , and find ${[𝑇]}_{ℬ︀ ℬ︀}$ . What does it tell you about $𝑇 \circ 𝑇$ ?

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.1 (Basis), Theorem 2.3.9 (The matrix of a map computes the map), Corollary 2.2.6 (Agreeing on a spanning list)

Hint 1. (a) The columns are

𝑇 (1, 0)

and

𝑇 (0, 1)

Hint 2. (b) Compute

𝑇 (1, 𝑖)

and

𝑇 (1, - 𝑖)

and express them in terms of

(1, 𝑖)

and

(1, - 𝑖)

Sketch. (a)

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

. (b)

(𝑧, 𝑤) =

𝑎 (1, 𝑖) +

𝑏 (1, - 𝑖)

has the unique solution

𝑎 = (𝑧 - 𝑖 𝑤) / 2

𝑏 = (𝑧 + 𝑖 𝑤) / 2

𝑇 (1, 𝑖) = 𝟎

and

𝑇 (1, - 𝑖) =

(2, 2 𝑖) =

2 (1, 𝑖)

, so

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

. So

𝑇

sends

(1, - 𝑖)

to a multiple of

(1, 𝑖)

and

(1, 𝑖)

𝟎

, hence

𝑇 \circ 𝑇 = 0

(a) $𝑇 (1, 0) = (1, 𝑖)$ and $𝑇 (0, 1) = (𝑖, - 1)$ , so ${[𝑇]}_{ℰ︀ ℰ︀} =$ $(\begin{matrix} 1 & 𝑖 \\ 𝑖 & - 1 \end{matrix})$ .

(b) The equation $(𝑧, 𝑤) =$ $𝑎 (1, 𝑖) +$ $𝑏 (1, - 𝑖)$ means $𝑎 + 𝑏 = 𝑧$ and $𝑖 (𝑎 - 𝑏) = 𝑤$ , that is, $𝑎 - 𝑏 = - 𝑖 𝑤$ . Adding and subtracting, $𝑎 = (𝑧 - 𝑖 𝑤) / 2$ and $𝑏 = (𝑧 + 𝑖 𝑤) / 2$ , and these values do satisfy both equations. So every vector has exactly one representation, and $ℬ︀$ is a basis. Now

𝑇 (1, 𝑖) = (1 + 𝑖^{2}, 𝑖 - 𝑖) = (0, 0), 𝑇 (1, - 𝑖) = (1 - 𝑖^{2}, 𝑖 + 𝑖) = (2, 2 𝑖) = 2 (1, 𝑖),

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

So $𝑇$ kills $(1, 𝑖)$ and sends $(1, - 𝑖)$ into $span ((1, 𝑖))$ . Hence $𝑇 (𝑇 (𝐯_{𝑗})) = 𝟎$ for both basis vectors, and $𝑇 \circ 𝑇 = 0$ by Corollary 2.2.6. Directly,

𝑇 (𝑇 (𝑧, 𝑤)) = (𝑧 + 𝑖 𝑤 + 𝑖 (𝑖 𝑧 - 𝑤), 𝑖 (𝑧 + 𝑖 𝑤) - (𝑖 𝑧 - 𝑤)) = (0, 0) .

The standard matrix hides this; the basis $ℬ︀$ shows it.

Exercise 2.3.46.standard For $𝜑 \in ℝ$ , let $𝐮_{1} = (cos 𝜑, sin 𝜑)$ and $𝐮_{2} =$ $(- sin 𝜑, cos 𝜑)$ , and let $𝒰︀ = 𝐮_{1}, 𝐮_{2}$ . Let $𝑅_{𝜃}$ be the rotation by $𝜃$ and $𝑆_{𝛼}$ the reflection across the line through $𝟎$ at angle $𝛼$ (Example 2.1.11).

(a)Show that $𝑎 𝐮_{1} +$ $𝑏 𝐮_{2} =$ $𝑅_{𝜑} (𝑎, 𝑏)$ , that $𝒰︀$ is a basis of $ℝ^{2}$ , and that the vector $(𝑟 cos 𝛽, 𝑟 sin 𝛽)$ has $𝒰︀$ -coordinates $(𝑟 cos (𝛽 - 𝜑), 𝑟 sin (𝛽 - 𝜑))$ .
(b)Show that ${[𝑅_{𝜃}]}_{𝒰︀ 𝒰︀} =$ ${[𝑅_{𝜃}]}_{ℰ︀ ℰ︀}$ .
(c)Show that ${[𝑆_{𝛼}]}_{𝒰︀ 𝒰︀} =$ ${[𝑆_{𝛼 - 𝜑}]}_{ℰ︀ ℰ︀}$ , and interpret this.

Solution.

Uses. Example 2.1.11 (Rotations, projections, and reflections), Exercise 2.1.43, Definition 2.3.1 (Matrix of a linear map), Example 2.3.3 (Matrices with respect to standard bases)

Hint 1. (a) Compare

𝑎 𝐮_{1} + 𝑏 𝐮_{2}

with the formula for

𝑅_{𝜑} (𝑎, 𝑏)

. For the basis property,

𝑅_{𝜑}

is undone by

𝑅_{- 𝜑}

(Exercise 2.1.43).

Hint 2. The formula for

𝑆_{𝛼}

shows that

𝑆_{𝛼}

sends the unit vector at angle

𝛽

to the unit vector at angle

2 𝛼 - 𝛽

, and

𝑅_{𝜃}

adds

𝜃

to the angle. Write down the angles of the images of

𝐮_{1}

(angle

𝜑

) and

𝐮_{2}

(angle

𝜑 + 𝜋 / 2

), and use (a).

Sketch. (a) Expanding gives

𝑎 𝐮_{1} +

𝑏 𝐮_{2} =

𝑅_{𝜑} (𝑎, 𝑏)

, and since

𝑅_{- 𝜑} 𝑅_{𝜑} =

id =

𝑅_{𝜑} 𝑅_{- 𝜑}

(𝑎, 𝑏) = 𝑅_{- 𝜑} (𝐲)

is the unique coefficient vector for

𝐲

;

𝑅_{- 𝜑}

subtracts

𝜑

from the angle. (b)

𝑅_{𝜃} (𝐮_{1})

and

𝑅_{𝜃} (𝐮_{2})

have angles

𝜑 + 𝜃

and

𝜑 + 𝜋 / 2 + 𝜃

, hence coordinates

(cos 𝜃, sin 𝜃)

and

(- sin 𝜃, cos 𝜃)

. (c)

𝑆_{𝛼} (𝐮_{1})

and

𝑆_{𝛼} (𝐮_{2})

have angles

2 𝛼 - 𝜑

and

2 𝛼 - 𝜑 - 𝜋 / 2

, hence coordinates

(cos 2 𝛾, sin 2 𝛾)

and

(sin 2 𝛾, - cos 2 𝛾)

with

𝛾 = 𝛼 - 𝜑

(a) By the formula for $𝑅_{𝜑}$ in Example 2.1.11,

𝑎 𝐮_{1} + 𝑏 𝐮_{2} = (𝑎 cos 𝜑 - 𝑏 sin 𝜑, 𝑎 sin 𝜑 + 𝑏 cos 𝜑) = 𝑅_{𝜑} (𝑎, 𝑏) .

By Exercise 2.1.43, $𝑅_{𝜑} 𝑅_{- 𝜑} =$ $𝑅_{- 𝜑} 𝑅_{𝜑} =$ $𝑅_{0} =$ $id$ . So for $𝐲 \in ℝ^{2}$ , the coefficients $(𝑎, 𝑏) = 𝑅_{- 𝜑} (𝐲)$ work, since $𝑅_{𝜑}$ undoes $𝑅_{- 𝜑}$ . They are the only ones: if $𝑅_{𝜑} (𝑎, 𝑏) = 𝐲$ , then applying $𝑅_{- 𝜑}$ gives $(𝑎, 𝑏) = 𝑅_{- 𝜑} (𝐲)$ . Hence $𝒰︀$ is a basis and ${[𝐲]}_{𝒰︀} = 𝑅_{- 𝜑} (𝐲)$ . Rotation by $- 𝜑$ subtracts $𝜑$ from the polar angle (Example 2.1.11), so

{[(𝑟 cos 𝛽, 𝑟 sin 𝛽)]}_{𝒰︀} = (𝑟 cos (𝛽 - 𝜑), 𝑟 sin (𝛽 - 𝜑)) .

(b) The vector $𝐮_{1}$ has angle $𝜑$ and $𝐮_{2} =$ $(cos (𝜑 + 𝜋 / 2), sin (𝜑 + 𝜋 / 2))$ has angle $𝜑 + 𝜋 / 2$ , both of length $1$ . Rotation adds $𝜃$ to the angle, so by (a),

{[𝑅_{𝜃} (𝐮_{1})]}_{𝒰︀} = (cos 𝜃, sin 𝜃), {[𝑅_{𝜃} (𝐮_{2})]}_{𝒰︀} = (cos (𝜃 + 𝜋 / 2), sin (𝜃 + 𝜋 / 2)) = (- sin 𝜃, cos 𝜃) .

These are the columns of ${[𝑅_{𝜃}]}_{ℰ︀ ℰ︀}$ (Example 2.3.3).

(c) From the formula in Example 2.1.11 and the angle subtraction formulas,

𝑆_{𝛼} (cos 𝛽, sin 𝛽) = (cos 𝛽 cos 2 𝛼 + sin 𝛽 sin 2 𝛼, cos 𝛽 sin 2 𝛼 - sin 𝛽 cos 2 𝛼) = (cos (2 𝛼 - 𝛽), sin (2 𝛼 - 𝛽)) .

So $𝑆_{𝛼} (𝐮_{1})$ has angle $2 𝛼 - 𝜑$ and $𝑆_{𝛼} (𝐮_{2})$ has angle $2 𝛼 - 𝜑 - 𝜋 / 2$ . With $𝛾 = 𝛼 - 𝜑$ , part (a) gives the coordinates

{[𝑆_{𝛼} (𝐮_{1})]}_{𝒰︀} = (cos 2 𝛾, sin 2 𝛾), {[𝑆_{𝛼} (𝐮_{2})]}_{𝒰︀} = (cos (2 𝛾 - 𝜋 / 2), sin (2 𝛾 - 𝜋 / 2)) = (sin 2 𝛾, - cos 2 𝛾) .

By the formula for $𝑆_{𝛾}$ , these are $𝑆_{𝛾} (𝐞_{1})$ and $𝑆_{𝛾} (𝐞_{2})$ , the columns of ${[𝑆_{𝛾}]}_{ℰ︀ ℰ︀}$ .

In words: in coordinates rotated by $𝜑$ , a rotation looks the same, and the reflection across the line at angle $𝛼$ looks like the reflection across the line at angle $𝛼 - 𝜑$ , the angle of the mirror measured from $𝐮_{1}$ instead of from $𝐞_{1}$ . Taking $𝜑 = 𝛼$ puts $𝐮_{1}$ on the mirror, and then ${[𝑆_{𝛼}]}_{𝒰︀ 𝒰︀} =$ ${[𝑆_{0}]}_{ℰ︀ ℰ︀} =$ $(\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix})$ , as in Example 2.3.23.

Exercise 2.3.47.hard Let $𝐴 \in ℂ^{𝑛 \times 𝑛}$ satisfy

| 𝑎_{𝑖 𝑖} | > \sum_{𝑗 \neq 𝑖} | 𝑎_{𝑖 𝑗} | for every 𝑖 = 1, \dots, 𝑛 .

Show that if $𝐴 𝐱 = 𝟎$ , then $𝐱 = 𝟎$ .

Solution.

Uses. Proposition 2.3.11 (Entries of $𝐴 𝐱$ ), the triangle inequality $| 𝑧 + 𝑤 | \leq | 𝑧 | + | 𝑤 |$ in $ℂ$ , Section B.1

Hint 1. Suppose

𝐴 𝐱 = 𝟎

with

𝐱 \neq 𝟎

. Look at the equation coming from a cleverly chosen row.

Hint 2. Choose

𝑖

with

| 𝑥_{𝑖} |

as large as possible. The

𝑖

-th entry of

𝐴 𝐱

gives

𝑎_{𝑖 𝑖} 𝑥_{𝑖} =

- \sum_{𝑗 \neq 𝑖} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}

. Estimate both sides.

Sketch. If

𝐱 \neq 𝟎

, pick

𝑖

with

| 𝑥_{𝑖} |

maximal, so

| 𝑥_{𝑖} | > 0

. Row

𝑖

𝐴 𝐱 = 𝟎

and the triangle inequality give

| 𝑎_{𝑖 𝑖} | | 𝑥_{𝑖} | \leq

\sum_{𝑗 \neq 𝑖} | 𝑎_{𝑖 𝑗} | | 𝑥_{𝑗} |

. Bounding each

| 𝑥_{𝑗} |

| 𝑥_{𝑖} |

makes the right side smaller than

| 𝑎_{𝑖 𝑖} | | 𝑥_{𝑖} |

, a contradiction.

Suppose $𝐴 𝐱 = 𝟎$ and $𝐱 \neq 𝟎$ . Choose $𝑖$ with $| 𝑥_{𝑖} | \geq | 𝑥_{𝑗} |$ for all $𝑗$ ; then $| 𝑥_{𝑖} | > 0$ . By Proposition 2.3.11, the $𝑖$ -th entry of $𝐴 𝐱$ is $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} = 0$ , so $𝑎_{𝑖 𝑖} 𝑥_{𝑖} =$ $- \sum_{𝑗 \neq 𝑖} 𝑎_{𝑖 𝑗} 𝑥_{𝑗}$ . Taking absolute values and using the triangle inequality,

| 𝑎_{𝑖 𝑖} | | 𝑥_{𝑖} | = | \sum_{𝑗 \neq 𝑖} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} | \leq \sum_{𝑗 \neq 𝑖} | 𝑎_{𝑖 𝑗} | | 𝑥_{𝑗} | \leq (\sum_{𝑗 \neq 𝑖} | 𝑎_{𝑖 𝑗} |) | 𝑥_{𝑖} | < | 𝑎_{𝑖 𝑖} | | 𝑥_{𝑖} |,

where the last step uses the hypothesis and $| 𝑥_{𝑖} | > 0$ . This is a contradiction, so $𝐱 = 𝟎$ .

The proof chose an extremal coordinate, the largest one in absolute value, so that a single row of $𝐴$ could be played against all the others. In the language of Section 2.6 the conclusion says that $𝑇_{𝐴}$ is injective, and since $𝐴$ is square it is then invertible (Corollary 3.5.25).

Exercise 2.3.48.challenge Let $𝑛 \geq 1$ and let $𝑇 : {𝐹 [𝑥]}_{\leq 𝑛} \to$ ${𝐹 [𝑥]}_{\leq 𝑛}$ , $𝑇 (𝑓) = 𝑓 (𝑥 + 1)$ . Let $𝐽 \in$ $𝐹^{(𝑛 + 1) \times (𝑛 + 1)}$ have $1$ in each diagonal position $(𝑘, 𝑘)$ and in each position $(𝑘, 𝑘 + 1)$ just above the diagonal, and $0$ elsewhere. (Use the usual algebra of polynomials freely, including that substituting $𝑥 + 1$ respects products and that substituting twice in a row gives $𝑓 (𝑥 + 2)$ ; these facts are proved in Section 7.1.)

(a)Over $ℚ$ , let $𝑏_{0} = 1$ and $𝑏_{𝑘} =$ $𝑥 (𝑥 - 1) \dots (𝑥 - 𝑘 + 1) / 𝑘!$ for $𝑘 \geq 1$ . Show that $ℬ︀ = 𝑏_{0}, 𝑏_{1}, \dots, 𝑏_{𝑛}$ is a basis of ${ℚ [𝑥]}_{\leq 𝑛}$ with ${[𝑇]}_{ℬ︀ ℬ︀} = 𝐽$ .
(b)Let $𝑝$ be a prime. Show that over $𝔽_{𝑝}$ there is a basis $ℬ︀$ of $𝔽_{𝑝} {[𝑥]}_{\leq 𝑛}$ with ${[𝑇]}_{ℬ︀ ℬ︀} = 𝐽$ if and only if $𝑛 < 𝑝$ .

Solution.

Uses. Definition 2.3.1 (Matrix of a linear map), Definition 1.6.1 (Basis), Definition 1.2.16 (Degree), Proposition 1.1.24 ( $ℤ / 𝑛 ℤ$ is a field if and only if $𝑛$ is prime), Corollary 2.2.6 (Agreeing on a spanning list), binomial coefficients: $(\binom{𝑝}{𝑘})$ is divisible by $𝑝$ for $0 < 𝑘 < 𝑝$

Hint 1. (a)

deg 𝑏_{𝑘} = 𝑘

, which gives the basis property. For the matrix, prove the polynomial identity

𝑏_{𝑘} (𝑥 + 1) =

𝑏_{𝑘} +

𝑏_{𝑘 - 1}

by pulling out the common factor

𝑥 (𝑥 - 1) \dots (𝑥 - 𝑘 + 2)

Hint 2. (b), “if”: for

𝑘 \leq 𝑛 < 𝑝

, the integer

𝑘!

is not divisible by

𝑝

, so it is invertible in

𝔽_{𝑝}

and (a) goes through. “Only if”: what does

{[𝑇]}_{ℬ︀ ℬ︀} = 𝐽

say about

𝑇 (𝐯_{𝑘})

? Compute

𝑇^{𝑟} (𝐯_{𝑠})

by induction on

𝑟

Hint 3. You should find

𝑇^{𝑟} (𝐯_{𝑠}) =

\sum_{𝑘} (\binom{𝑟}{𝑘}) 𝐯_{𝑠 - 𝑘}

. Take

𝑟 = 𝑠 = 𝑝

, and compare with

𝑇^{𝑝} (𝑓) =

𝑓 (𝑥 + 𝑝)

Sketch. (a) The

𝑏_{𝑘}

have degrees

0, 1, \dots, 𝑛

, so they form a basis. Pulling out the common factor

𝑥 (𝑥 - 1) \dots (𝑥 - 𝑘 + 2)

shows

𝑏_{𝑘} (𝑥 + 1) -

𝑏_{𝑘} =

𝑏_{𝑘 - 1}

, so

𝑇 (𝑏_{𝑘}) =

𝑏_{𝑘} +

𝑏_{𝑘 - 1}

and

𝑇 (𝑏_{0}) = 𝑏_{0}

: the matrix is

𝐽

. (b) If

𝑛 < 𝑝

, the same construction works in

𝔽_{𝑝}

. If

𝑛 \geq 𝑝

and

{[𝑇]}_{ℬ︀ ℬ︀} = 𝐽

with

ℬ︀ = 𝐯_{0}, \dots, 𝐯_{𝑛}

, then

𝑇 (𝐯_{𝑘}) =

𝐯_{𝑘} +

𝐯_{𝑘 - 1}

, and by induction

𝑇^{𝑝} (𝐯_{𝑝}) =

\sum_{𝑘} (\binom{𝑝}{𝑘}) 𝐯_{𝑝 - 𝑘} =

𝐯_{𝑝} +

𝐯_{0}

in characteristic

𝑝

. But

𝑇^{𝑝} (𝑓) =

𝑓 (𝑥 + 𝑝) =

𝑓

, so

𝐯_{0} = 𝟎

, a contradiction.

Throughout, index the basis vectors from $0$ , so that column $𝑘$ of $𝐽$ (for $𝑘 = 0, \dots, 𝑛$ ) is $𝐞_{𝑘}$ for $𝑘 = 0$ and $𝐞_{𝑘 - 1} + 𝐞_{𝑘}$ for $𝑘 \geq 1$ , where $𝐞_{0}, \dots, 𝐞_{𝑛}$ is the standard basis of $𝐹^{𝑛 + 1}$ . So ${[𝑇]}_{ℬ︀ ℬ︀} = 𝐽$ for $ℬ︀ = 𝐯_{0}, \dots, 𝐯_{𝑛}$ means

𝑇 (𝐯_{0}) = 𝐯_{0}, 𝑇 (𝐯_{𝑘}) = 𝐯_{𝑘} + 𝐯_{𝑘 - 1} (1 \leq 𝑘 \leq 𝑛) .

(2.3.1)

Polynomials of degrees $0, 1, \dots, 𝑛$ . Let $𝑞_{0},$ $\dots,$ $𝑞_{𝑛} \in$ ${𝐹 [𝑥]}_{\leq 𝑛}$ with $deg 𝑞_{𝑘} = 𝑘$ . They span ${𝐹 [𝑥]}_{\leq 𝑛}$ : by induction on $𝑘$ , every $𝑥^{𝑘}$ is in their span, since $𝑥^{𝑘}$ minus a suitable multiple of $𝑞_{𝑘}$ has degree less than $𝑘$ . They are linearly independent: in a relation $\sum_{𝑘} 𝑐_{𝑘} 𝑞_{𝑘} = 𝟎$ with some $𝑐_{𝑘} \neq 0$ , let $𝑘$ be the largest index with $𝑐_{𝑘} \neq 0$ ; then the coefficient of $𝑥^{𝑘}$ on the left is $𝑐_{𝑘}$ times the leading coefficient of $𝑞_{𝑘}$ , which is nonzero. So $𝑞_{0}, \dots, 𝑞_{𝑛}$ is a basis (Definition 1.6.1).

(a) Over $ℚ$ , $𝑏_{𝑘}$ is a product of $𝑘$ factors of degree $1$ divided by $𝑘!$ , so $deg 𝑏_{𝑘} = 𝑘$ , and $ℬ︀$ is a basis by the paragraph above. For $𝑘 \geq 1$ , write $𝑃 =$ $𝑥 (𝑥 - 1) \dots (𝑥 - 𝑘 + 2)$ (with $𝑃 = 1$ when $𝑘 = 1$ ), so that $𝑏_{𝑘} =$ $𝑃 (𝑥 - 𝑘 + 1) / 𝑘!$ and $𝑏_{𝑘 - 1} = 𝑃 / (𝑘 - 1)!$ . Substituting $𝑥 + 1$ for $𝑥$ in $𝑏_{𝑘}$ gives $(𝑥 + 1) 𝑃 / 𝑘!$ . Hence

𝑏_{𝑘} (𝑥 + 1) - 𝑏_{𝑘} = \frac{𝑃 ((𝑥 + 1) - (𝑥 - 𝑘 + 1))}{𝑘!} = \frac{𝑘 𝑃}{𝑘!} = \frac{𝑃}{(𝑘 - 1)!} = 𝑏_{𝑘 - 1} .

So $𝑇 (𝑏_{𝑘}) =$ $𝑏_{𝑘} +$ $𝑏_{𝑘 - 1}$ for $𝑘 \geq 1$ , and $𝑇 (𝑏_{0}) = 𝑏_{0}$ . This is (2.3.1), so ${[𝑇]}_{ℬ︀ ℬ︀} = 𝐽$ .

(b) If $𝑛 < 𝑝$ . For $𝑘 \leq 𝑛 < 𝑝$ , the integer $𝑘!$ is a product of integers between $1$ and $𝑝 - 1$ , none divisible by the prime $𝑝$ , so $𝑘! \neq 0$ in $𝔽_{𝑝}$ and it is invertible (Proposition 1.1.24). So $𝑏_{0}, \dots, 𝑏_{𝑛}$ are defined in $𝔽_{𝑝} [𝑥]$ , and the computation in (a) uses only the field operations and division by $𝑘!$ . It goes through unchanged, and gives a basis with ${[𝑇]}_{ℬ︀ ℬ︀} = 𝐽$ .

If $𝑛 \geq 𝑝$ . Suppose $ℬ︀ = 𝐯_{0}, \dots, 𝐯_{𝑛}$ is a basis satisfying (2.3.1). Set $𝐯_{𝑘} = 𝟎$ for $𝑘 < 0$ , so that $𝑇 (𝐯_{𝑘}) =$ $𝐯_{𝑘} +$ $𝐯_{𝑘 - 1}$ for all $𝑘 \leq 𝑛$ (for $𝑘 < 0$ both sides are $𝟎$ ). We claim that for all $𝑟 \geq 0$ and $0 \leq 𝑠 \leq 𝑛$ ,

𝑇^{𝑟} (𝐯_{𝑠}) = \sum_{𝑘 = 0}^{𝑟} (\binom{𝑟}{𝑘}) 𝐯_{𝑠 - 𝑘} .

For $𝑟 = 0$ both sides are $𝐯_{𝑠}$ . If it holds for $𝑟$ , then by linearity

𝑇^{𝑟 + 1} (𝐯_{𝑠}) = \sum_{𝑘 = 0}^{𝑟} (\binom{𝑟}{𝑘}) (𝐯_{𝑠 - 𝑘} + 𝐯_{𝑠 - 𝑘 - 1}) = \sum_{𝑘 = 0}^{𝑟 + 1} ((\binom{𝑟}{𝑘}) + (\binom{𝑟}{𝑘 - 1})) 𝐯_{𝑠 - 𝑘} = \sum_{𝑘 = 0}^{𝑟 + 1} (\binom{𝑟 + 1}{𝑘}) 𝐯_{𝑠 - 𝑘},

with the conventions $(\binom{𝑟}{- 1}) = (\binom{𝑟}{𝑟 + 1}) = 0$ and Pascal’s rule. Now take $𝑟 = 𝑠 = 𝑝$ , which is allowed since $𝑝 \leq 𝑛$ . For $0 < 𝑘 < 𝑝$ , $(\binom{𝑝}{𝑘})$ is divisible by $𝑝$ , so it is $0$ in $𝔽_{𝑝}$ , and

𝑇^{𝑝} (𝐯_{𝑝}) = 𝐯_{𝑝} + 𝐯_{0} .

On the other hand, substituting $𝑥 + 1$ a total of $𝑝$ times gives $𝑇^{𝑝} (𝑓) =$ $𝑓 (𝑥 + 𝑝 \cdot 1) =$ $𝑓 (𝑥)$ , since $𝑝 \cdot 1 = 0$ in $𝔽_{𝑝}$ . So $𝑇^{𝑝} (𝐯_{𝑝}) = 𝐯_{𝑝}$ , and $𝐯_{0} = 𝟎$ , which is impossible for a vector of a basis. Hence no such basis exists.

For example, over $𝔽_{2}$ with $𝑛 = 2$ : $𝑇^{2} = id$ , while a basis as above would give $𝑇^{2} (𝐯_{2}) =$ $𝐯_{2} +$ $2 𝐯_{1} +$ $𝐯_{0} =$ $𝐯_{2} +$ $𝐯_{0}$ .

More practice

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