2.5 Matrices as maps, multiplication, change of basis

A matrix is the list of where a linear map sends the basis vectors. Multiplying matrices is composing maps, and changing basis changes the matrix but not the map.

Chapter 2.3 showed that a linear map is decided by what it does to a basis, and 2.4 showed that you may choose those values freely. This chapter writes that information down as a rectangular table of numbers, a matrix, so it can be computed with. Then it asks three questions. How do you read what a matrix does? Why does multiplying two matrices use that strange row-times-column rule? And what happens to the table when you describe the same map using a different basis?

Before you start

2.3: linear maps. 2.4: composition, inverses, isomorphisms, and prescribing values on a basis. 2.2: basis and coordinates.

Quick checkA linear map

T

of the plane has

T(1, 0) = (2, 3)

and

T(0, 1) = (0, 1)

. What is

T(1, 1)

Quick check

S

and

T

are invertible maps. Which is the inverse of

ST

Quick checkWhat are the coordinates of

(3, 1)

in the basis

b_1 = (1, 1)

b_2 = (1, -1)

The picture

This is the visualizer from 2.3 with one new reading. The two arrows $\hat\imath$ and $\hat\jmath$ are the standard basis vectors. Drag their tips anywhere. The numbers in the corner, the matrix $A$ , are the coordinates of where the two arrows landed: first column where $\hat\imath$ went, second column where $\hat\jmath$ went. Look at the purple vector $v$ . It is $v_1\hat\imath + v_2\hat\jmath$ , so it lands at $v_1$ times the first column plus $v_2$ times the second column. That sentence is the whole of matrix-times-vector.

Try the following. Pick “Rotate 90°” and read off the matrix: $\hat\imath$ goes to $(0, 1)$ and $\hat\jmath$ goes to $(-1, 0)$ , so the columns are $(0,1)$ and $(-1,0)$ . Then pick “Reflect” and “Stretch” and do the same. In every case you can write the matrix down by looking at two arrows.

The idea, in words

A linear map $T$ from an $n$ -dimensional space to an $m$ -dimensional space is decided by the $n$ vectors $T(e_1), \dots, T(e_n)$ (2.3). Each is a vector in the target, so each is a list of $m$ coordinates. Stand those $n$ lists side by side as columns, and you have a table with $m$ rows and $n$ columns: the matrix of $T$ . Two things then happen.

Reading the table. The image of any vector is a combination of the columns, with the vector’s own coordinates as the weights. That is the 3Blue1Brown way to see a matrix, and Spagnolie’s ‘triple-starred’ picture in Lecture 10.

Chaining. If you chain two maps, the columns of the chain are the second matrix applied to the columns of the first. Writing that out gives the row-times-column rule. It looks arbitrary only if you forget that it came from composition.

Why· Why the table depends on the basis, and why that is fine

The columns are coordinates, and coordinates depend on the basis (2.2). The same map has different tables in different bases. That is no problem: the map is the real object, and a matrix is a description of it in a chosen language. The last section of the chapter shows how to translate between two descriptions, and why a good choice of basis can make a table far simpler.

Definitions and theorems

Matrices as arrays

Definition T

Matrix

An $m \times n$ matrix is a rectangular array of numbers with $m$ rows and $n$ columns, written $A = (a_{ij})$ where $a_{ij}$ is the entry in row $i$ and column $j$ . The first subscript is the row. A matrix with one column is a column vector. A matrix with $m = n$ is square. The set of all real $m \times n$ matrices is $\mathbb R^{m \times n}$ (Apostol: $M_{m,n}$ ).

In one lineA rectangular array of numbers with $m$ rows and $n$ columns; $a_{ij}$ is the entry in row $i$ and column $j$ .

Why it existsIt is the compact table that records a linear map once bases are chosen, and also an object you can add and multiply in its own right.

Matrices of the same size are added, and scaled, entry by entry. This is the vector space $\mathbb R^{m \times n}$ of 2.1.

Theorem A Apostol 2.13

Matrix space has dimension mn

Let $E_{ij}$ be the $m \times n$ matrix with a $1$ in row $i$ , column $j$ , and $0$ everywhere else. The $mn$ matrices $E_{ij}$ form a basis of $\mathbb R^{m \times n}$ , so $\dim \mathbb R^{m \times n} = mn$ .

In one lineThe space of $m \times n$ matrices has dimension $mn$ .

Why it is trueA matrix is $mn$ free numbers, and the matrices with a single $1$ record each number separately.

ProofApostol 2.13

The idea: Spanning: any matrix is the sum of its entries times the E's. Independence: a combination of the E's has the coefficients as its entries.

Spanning: for any

A = (a_{ij})

A = \sum_{i,j} a_{ij}E_{ij}

The

(i,j)

entry of

\sum_{p,q} a_{pq}E_{pq}

a_{ij}

, because only

E_{ij}

has a nonzero entry there.

Independence: suppose

\sum c_{ij}E_{ij}

is the zero matrix.

Same computation: the combination has entry

c_{ij}

at position

(i,j)

Then each

c_{ij} = 0

. So the

E_{ij}

are independent and span: they are a basis, and there are

mn

of them.

Every entry of the zero matrix is

0

The matrix of a linear map

Definition T

Matrix of a linear map

Let $T: V \to W$ be linear. Choose ordered bases $(e_1, \dots, e_n)$ of $V$ and $(w_1, \dots, w_m)$ of $W$ . Write each image in the basis of $W$ :

T(e_k) = \sum_{i=1}^m t_{ik}\, w_i, \qquad k = 1, \dots, n.

The matrix of $T$ relative to these bases is the $m \times n$ matrix $m(T) = (t_{ik})$ . Its $k$ th column is the coordinates of $T(e_k)$ . Call the two bases $\mathcal E = (e_1, \dots, e_n)$ and $\mathcal W = (w_1, \dots, w_m)$ . When the bases need naming we write $m_{\mathcal E \to \mathcal W}(T)$ (Spagnolie’s $A_{e \to w}$ ). For a vector $x$ we write $[x]_{\mathcal E}$ for the column of its coordinates in the basis $\mathcal E$ .

In one lineWith bases chosen, the matrix whose column $k$ is the coordinates of $T(e_k)$ .

Why it existsIt stores everything about $T$ in a table, because $T$ is decided by its values on a basis.

A warning about notation. The letter $m$ now has two jobs: it is the number of rows, and (following Apostol) it is the name of the function $T \mapsto m(T)$ that produces the matrix. When $m$ is followed by a map in brackets, as in $m(T)$ , it is the matrix of that map.

A tip on shape: the shape is (dimension of the target) by (dimension of the source). A map from $\mathbb R^3$ to $\mathbb R^2$ has a $2 \times 3$ matrix: it takes in columns of height 3, so it must have 3 columns, and it puts out columns of height 2.

Quick checkA linear map of the plane has

T(e_1) = (1, 2)

and

T(e_2) = (3, 4)

. What is its matrix in the standard basis?

Worked example Apostol 2.10 Ex. 2; Spagnolie Lecture 10

Find the matrix of differentiation

D

from

P_3

P_2

in the standard bases, and again in the bases

(x,\ \tfrac12 x^2,\ \tfrac13 x^3,\ 1)

and

(1,\ x,\ x^2)

Solution.

Fix the bases. For the source $P_3$ (cubics, dimension 4) take $e = (1, x, x^2, x^3)$ . For the target $P_2$ (dimension 3) take $w = (1, x, x^2)$ . The matrix needs an ordered basis on each side. The matrix will be $3 \times 4$ : target dimension by source dimension.
Differentiate each source basis vector and write the answer in $w$ . $D(1) = 0 = (0,0,0)$ , $D(x) = 1 = (1,0,0)$ , $D(x^2) = 2x = (0,2,0)$ , $D(x^3) = 3x^2 = (0,0,3)$ . Column $k$ is the coordinates of $T(e_k)$ in the target basis.
Place the four columns side by side.

m(D) = \begin{bmatrix}0&1&0&0\\0&0&2&0\\0&0&0&3\end{bmatrix}.

Columns, not rows: each image becomes a column. 4. Now change the bases. Take $e' = (x, \tfrac12 x^2, \tfrac13 x^3, 1)$ and keep $w$ . Then $D(x) = 1 = (1,0,0)$ , $D(\tfrac12x^2) = x = (0,1,0)$ , $D(\tfrac13x^3) = x^2 = (0,0,1)$ , $D(1) = 0$ . We chose source vectors that $D$ sends exactly onto the target basis vectors, and the last one from the null space. 5. Write the new matrix.

m(D) = \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\end{bmatrix}.

Same map, much simpler table. The ones form an identity block of size 3, the rank of

D

, and the zero column is the null space.

Answer. The two matrices above. Same map, different bases, different tables.

Step 4 is a special case of a general fact, stated later in the chapter as the ‘diagonal form’ theorem. First, the central result: how to compute with a matrix.

Theorem T Apostol Thm 2.13; Spagnolie Lecture 10

Matrix times vector

Let $m(T) = (t_{ik})$ be the matrix of $T$ relative to bases $\mathcal E = (e_k)$ and $\mathcal W = (w_i)$ . If $x = \sum_k x_k e_k$ then $T(x) = \sum_i y_i w_i$ with

y_i = \sum_{k=1}^n t_{ik}\,x_k \quad (i = 1, \dots, m), \qquad \text{that is,} \qquad [T(x)]_{\mathcal W} = m(T)\,[x]_{\mathcal E},

where the matrix-times-column on the right is defined by the displayed formula. Equivalently, $[T(x)]_{\mathcal W} = x_1 F_1 + \dots + x_n F_n$ , where $F_k$ is column $k$ of $m(T)$ .

In one lineIf $x$ has coordinates $x_k$ , then $T(x)$ has coordinates $y_i = \sum_k t_{ik}x_k$ , which is $x_1 \cdot (\text{column }1) + \dots + x_n \cdot (\text{column }n)$ .

Why it is trueExpand $x$ in the basis, push $T$ through, and read the coefficient of each $w_i$ .

ProofApostol 2.10; Spagnolie Lecture 10

The idea: Write x in the basis, apply T term by term, expand each T(e_k), and collect the coefficient of each w_i.

Let

x = \sum_{k=1}^n x_k e_k

Coordinates of

x

in the basis

(e_k)

T(x) = \sum_k x_k\, T(e_k)

Linearity:

T

passes through sums and multiples (2.3).

T(x) = \sum_k x_k \sum_i t_{ik}\, w_i

Definition of the matrix:

T(e_k) = \sum_i t_{ik}w_i

T(x) = \sum_i \Big(\sum_k t_{ik}x_k\Big) w_i

Swap the order of the two finite sums, and collect the coefficient of each

w_i

y_i = \sum_k t_{ik}x_k

Coordinates in a basis are unique (2.2), so the coefficient of

w_i

is the

i

th coordinate.

This is the column form

y = x_1F_1 + \dots + x_nF_n

Read the same formula column by column: the

i

th entry of

x_1F_1 + \dots + x_nF_n

\sum_k x_k t_{ik}

In the picture. In the visualizer above, the purple vector $v$ has coordinates $(v_1, v_2)$ . The caption says it lands at ‘column 1 times $v_1$ plus column 2 times $v_2$ ’. That is the last step of this proof, in two dimensions. Dragging $\hat\imath$ and $\hat\jmath$ changes the columns, and $Av$ moves with them.

Quick checkFor a

3 \times 2

matrix

A

, which statement is right?

Your answerLet

A = \begin{bmatrix}2&-1&0\\1&3&4\end{bmatrix}

and

x = (1, 2, -1)

. Compute

Ax

1\cdot(\text{column }1) + 2\cdot(\text{column }2) - 1\cdot(\text{column }3)

. What is the SECOND entry of

Ax

Worked example

Find the matrix of

T(x, y, z) = (x + 2y,\ 3z - y)

and of

S(u, v) = (u + v,\ u - v)

. Then find the matrix of

ST

and check it on

(2, 1, 4)

Solution.

Read off the shapes. $T$ takes 3 numbers in and gives 2 out, so its matrix is $2 \times 3$ . $S$ is $\mathbb R^2 \to \mathbb R^2$ , so its matrix is $2 \times 2$ . Shape is (target dimension) by (source dimension).
Find the columns of $T$ . $T(1,0,0) = (1, 0)$ , $T(0,1,0) = (2, -1)$ , $T(0,0,1) = (0, 3)$ . So $m(T) = \begin{bmatrix}1&2&0\\0&-1&3\end{bmatrix}$ . Column $k$ is $T(e_k)$ . Equivalently the coefficients of $x, y, z$ in each output formula, one output per row.
Find the columns of $S$ . $S(1,0) = (1, 1)$ and $S(0,1) = (1, -1)$ , so $m(S) = \begin{bmatrix}1&1\\1&-1\end{bmatrix}$ . Same rule.
Multiply, with $T$ acting first. $m(ST) = m(S)\,m(T) = \begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}1&2&0\\0&-1&3\end{bmatrix} = \begin{bmatrix}1&1&3\\1&3&-3\end{bmatrix}$ . The product of matrices is the matrix of the composition, with the first map on the right. Shapes: $(2\times2)(2\times3) = 2\times3$ .
Check on $(2, 1, 4)$ . Directly: $T(2,1,4) = (4,\ 11)$ and $S(4, 11) = (15, -7)$ . By the matrix: $(2 + 1 + 12,\ 2 + 3 - 12) = (15, -7)$ . Both routes must agree, since the matrix describes the composition.

Answer. $m(ST) = \begin{bmatrix}1&1&3\\1&3&-3\end{bmatrix}$ , and both routes give $(15, -7)$ .

Worked example Apostol 2.12 #5; MATH 375 HW6

A linear map

T

\mathbb R^3

has

T(k) = (2, 3, 5)

T(j + k) = (1, 0, 0)

and

T(i + j + k) = (0, 1, -1)

. Find its matrix in the standard bases, and compute

T(i + 2j + 3k)

Solution. Here $i = (1,0,0)$ , $j = (0,1,0)$ and $k = (0,0,1)$ are the standard basis vectors of $\mathbb R^3$ (Apostol’s names for $e_1, e_2, e_3$ ).

Find $T(j)$ . $T(j) = T(j + k) - T(k) = (1,0,0) - (2,3,5) = (-1,-3,-5)$ . Linearity lets us subtract values: $j = (j + k) - k$ .
Find $T(i)$ . $T(i) = T(i + j + k) - T(j) - T(k) = (0,1,-1) - (-1,-3,-5) - (2,3,5) = (-1, 1, -1)$ . Same idea: $i = (i + j + k) - j - k$ .
Write the images as columns. The columns are $T(i), T(j), T(k)$ :

m(T) = \begin{bmatrix}-1&-1&2\\1&-3&3\\-1&-5&5\end{bmatrix}.

The matrix in the standard bases has columns $T(e_k)$ , with coordinates read off as the entries themselves. 4. Check against the data. The matrix times $(0,0,1)$ is column 3, $(2,3,5)$ . Times $(0,1,1)$ it gives column 2 plus column 3, $(1, 0, 0)$ . Times $(1,1,1)$ it gives $(-1-1+2,\ 1-3+3,\ -1-5+5) = (0, 1, -1)$ . The matrix must reproduce all three given values. 5. Compute $T(i + 2j + 3k)$ . $1\cdot(-1,1,-1) + 2\cdot(-1,-3,-5) + 3\cdot(2,3,5) = (-1-2+6,\ 1-6+9,\ -1-10+15) = (3, 4, 4)$ . Matrix times vector is a combination of columns, with the coordinates $1, 2, 3$ as weights.

Answer. The matrix above, and $T(i + 2j + 3k) = (3, 4, 4)$ . (The posted answer key made an elimination slip when finding the null space of this map; the correct null space is $\{O\}$ , since the three columns are independent.)

Matrices are the maps

Fix the bases and write $m(T)$ for the matrix of each map $T \in L(V,W)$ . This gives a function $\Phi: L(V, W) \to \mathbb R^{m \times n}$ , $\Phi(T) = m(T)$ . It turns out to be an isomorphism, which is the idea behind Spagnolie’s remark in Lecture 11.

Theorem T Apostol Thm 2.15 (the isomorphism theorem); Spagnolie Lecture 11

Maps and matrices are the same thing

Let $\dim V = n$ and $\dim W = m$ , with fixed bases. Then the function $\Phi: L(V, W) \to \mathbb R^{m \times n}$ defined by $\Phi(T) = m(T)$ is linear, one-to-one and onto. In particular $\dim L(V, W) = mn$ .

In one lineFor fixed bases, the function $T \mapsto m(T)$ is an isomorphism from $L(V, W)$ onto $\mathbb R^{m \times n}$ .

Why it is trueAdding maps adds their columns, a map is decided by its columns, and any table of columns is the table of some map.

ProofApostol 2.14

The idea: Linear because images add and scale; one-to-one because a map is decided by its values on a basis; onto by prescribing the columns.

Linear: column

k

m(S + T)

is column

k

m(S)

plus column

k

m(T)

, so

m(S + T) = m(S) + m(T)

. In the same way

m(cT) = c\,m(T)

(S + T)(e_k) = S(e_k) + T(e_k)

, and coordinates of a sum are the sums of coordinates.

One-to-one: suppose

m(S) = m(T)

. Then

S(e_k) = T(e_k)

for every

k

m(S) = m(T)

, both maps send each

e_k

to the same vector.

S = T

. Hence

\Phi

is one-to-one.

Two linear maps that agree on a basis are equal (2.3).

Onto: given any matrix

(t_{ik})

, there is a linear map

T

with

T(e_k) = \sum_i t_{ik}w_i

'Prescribed values on a basis' from 2.4: you may choose the images of the

e_k

freely.

Then

m(T) = (t_{ik})

. So

m

is an isomorphism, and

\dim L(V,W) = \dim \mathbb R^{m \times n} = mn

By construction its columns are the given ones.

Your answerWhat is

\dim L(\mathbb R^3, \mathbb R^4)

, the dimension of the space of all linear maps from

\mathbb R^3

\mathbb R^4

Matrix multiplication is composition

Let $T: U \to V$ and $S: V \to W$ be linear, with $\dim U = n$ , $\dim V = p$ , $\dim W = m$ , and bases $(u_j)$ , $(v_k)$ , $(w_i)$ . Then $m(T)$ is $p \times n$ and $m(S)$ is $m \times p$ , and $ST: U \to W$ has an $m \times n$ matrix. What is it in terms of $m(S)$ and $m(T)$ ? Do not guess a rule. Compute it, one column at a time.

Theorem T Apostol Thm 2.16; Spagnolie Lecture 11

Matrix of a composition

With $m(S) = (s_{ik})$ and $m(T) = (t_{kj})$ as above, $m(ST)$ is the $m \times n$ matrix with

\big(m(ST)\big)_{ij} = \sum_{k=1}^p s_{ik}\,t_{kj}.

In words: column $j$ of $m(ST)$ is $m(S)$ applied to column $j$ of $m(T)$ .

In one lineThe $(i, j)$ entry of $m(ST)$ is $\sum_{k} s_{ik}t_{kj}$ : row $i$ of $m(S)$ times column $j$ of $m(T)$ .

Why it is trueColumn $j$ of $m(ST)$ is the coordinates of $S(T(u_j))$ . Those are $m(S)$ times the coordinates of $T(u_j)$ , which is column $j$ of $m(T)$ .

ProofApostol 2.15; Spagnolie Lecture 11 page 2

The idea: Take the j-th basis vector of U. Send it through T, then through S, and record coordinates at each stage. The first stage gives column j of m(T); the second stage is 'Matrix times vector'.

Column

j

m(ST)

is the coordinates, in

(w_i)

, of

ST(u_j) = S(T(u_j))

Column

j

of any matrix is the coordinates of the image of the

j

th basis vector.

T(u_j) = \sum_k t_{kj}v_k

. So the coordinate column of

T(u_j)

in the basis

(v_k)

is column

j

m(T)

Definition of

m(T)

: its

j

th column lists the coordinates of

T(u_j)

in the basis

(v_k)

The coordinate column of

S(T(u_j))

in the basis

(w_i)

m(S)

times the coordinate column of

T(u_j)

in the basis

(v_k)

. This is the second claim: column

j

m(ST)

m(S)

times column

j

m(T)

'Matrix times vector', applied to the map

S

and the vector

x = T(u_j)

V

The

i

th entry of that column is

\sum_{k=1}^p s_{ik}t_{kj}

. That is the

(i, j)

entry of

m(ST)

The formula for matrix times vector: the

i

th entry of

m(S)\,y

\sum_k s_{ik}y_k

, with

y_k = t_{kj}

Proof workshopRebuild the proof that the matrix of a composition is the product

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

So the row-times-column rule is not a definition somebody invented. It is forced: it is the only table that describes ‘do $T$ , then $S$ ’. We therefore use the formula to define the product of two matrices.

Definition T

Matrix multiplication

Let $A = (a_{ik})$ be $m \times p$ and $B = (b_{kj})$ be $p \times n$ . The product $AB$ is the $m \times n$ matrix whose $(i, j)$ entry is

(AB)_{ij} = \sum_{k=1}^p a_{ik}\,b_{kj} = (\text{row } i \text{ of } A)\cdot(\text{column } j \text{ of } B).

It is defined only when the number of columns of $A$ equals the number of rows of $B$ . Equivalently, column $j$ of $AB$ is $A$ times column $j$ of $B$ . With this definition, the theorem reads $m(ST) = m(S)\,m(T)$ .

In one lineFor $A$ of size $m \times p$ and $B$ of size $p \times n$ , $AB$ is the $m \times n$ matrix with $(AB)_{ij} = \sum_k a_{ik}b_{kj}$ .

Why it existsIt makes the matrix of a composition equal to the product of the matrices: $m(ST) = m(S)\,m(T)$ .

Shapes: (m by p) times (p by n) is (m by n). The two inside numbers must match and then vanish. Read the product right to left as maps, exactly like $ST$ : $AB$ means ‘apply $B$ , then $A$ ’.

Where this came from· Cayley and the matrix

In 1850 James Joseph Sylvester introduced the word ‘matrix’ (Latin for womb) for a rectangular array from which determinants can be taken. People had long written coefficients of linear substitutions in arrays, and by the 1840s Gauss and Eisenstein had noticed that substitutions can be multiplied like numbers, except that the order matters. Arthur Cayley’s 1858 ‘Memoir on the Theory of Matrices’ gave the array itself an abstract definition and an algebra: sum, product and inverse. Both men worked on invariant theory, where one constantly performs a linear substitution of variables and then another, which is exactly the situation of the rule derived above. In the same memoir Cayley stated that a matrix satisfies its own characteristic equation. He proved it for $2 \times 2$ matrices and said he had checked $3 \times 3$ ; Frobenius gave the first proof for every size in 1878. Spagnolie’s Lecture 17 proves a special case of this Cayley–Hamilton theorem.

Worked example Spagnolie Lecture 11 page 2

Compute

AB

for

A = \begin{bmatrix}1&1&1\\0&1&2\end{bmatrix}

and

B = \begin{bmatrix}0&1&0\\1&1&0\\0&1&1\end{bmatrix}

, column by column, and check it on a vector

Solution.

Answer. $AB = \begin{bmatrix}1&3&1\\1&3&2\end{bmatrix}$ .

Quick check

A

2 \times 3

and

B

3 \times 4

. Which products exist?

Your answerLet

A = \begin{bmatrix}1&2\\3&4\end{bmatrix}

and

B = \begin{bmatrix}5&6\\7&8\end{bmatrix}

. What is the entry in row 2, column 1 of

AB

Matrix multiplication does not commute

Spagnolie’s 2D example (Lecture 11). Let $A = \begin{bmatrix}0&-1\\1&0\end{bmatrix}$ , which sends $(x, y)$ to $(-y, x)$ , a quarter turn counterclockwise, and $B = \begin{bmatrix}-1&0\\0&1\end{bmatrix}$ , which sends $(x, y)$ to $(-x, y)$ , a mirror in the $y$ -axis. Then

AB = \begin{bmatrix}0&-1\\-1&0\end{bmatrix}, \qquad BA = \begin{bmatrix}0&1\\1&0\end{bmatrix}.

$AB$ means ‘mirror, then turn’: $(1, 0)$ goes to $(-1, 0)$ , then to $(0, -1)$ , which is column 1 of $AB$ . $BA$ means ‘turn, then mirror’: $(1, 0)$ goes to $(0, 1)$ and stays, which is column 1 of $BA$ . The matrix $BA = \begin{bmatrix}0&1\\1&0\end{bmatrix}$ is exactly the “Reflect” preset of the visualizer: turning then mirroring in the $y$ -axis is the same as mirroring in the line $y = x$ . Spagnolie’s note labelled $A$ as ‘clockwise’. It is counterclockwise, since $\hat\imath = (1,0)$ goes to $(0, 1)$ ; the formula is right and the label is not.

Two more ways products fail to commute. The sizes can differ: for $A$ of size $2 \times 3$ and $B$ of size $3 \times 2$ , $AB$ is $2 \times 2$ and $BA$ is $3 \times 3$ . And a product can be zero while neither factor is.

Worked example Apostol 2.16 #1; MATH 375 HW7

For

A = \begin{bmatrix}1&-4&2\\-1&4&-2\end{bmatrix}

B = \begin{bmatrix}1&2\\-1&3\\5&-2\end{bmatrix}

and

C = \begin{bmatrix}2&2\\1&-1\\1&-3\end{bmatrix}

, compute

AB

BA

AC

and

CA

Solution.

Check the shapes first. $A$ is $2 \times 3$ , $B$ and $C$ are $3 \times 2$ . So $AB$ , $AC$ are $2 \times 2$ , while $BA$ , $CA$ are $3 \times 3$ . The inside numbers must match; here they do in both orders, and the results differ in size, so $AB \ne BA$ before we compute anything.
Compute $AB$ entry by entry. $(AB)_{11} = 1\cdot1 + (-4)(-1) + 2\cdot5 = 15$ . $(AB)_{12} = 1\cdot2 + (-4)\cdot3 + 2\cdot(-2) = -14$ . Row 2 of $A$ is the negative of row 1, so row 2 of $AB$ is $(-15, 14)$ . Row $i$ of $A$ against column $j$ of $B$ . The shortcut for row 2 saves two dot products.
Compute $BA$ row by row. Row $i$ of $BA$ is $b_{i1}(\text{row 1 of }A) + b_{i2}(\text{row 2 of }A)$ . Row 1: $1(1,-4,2) + 2(-1,4,-2) = (-1, 4, -2)$ . Row 2: $-1(1,-4,2) + 3(-1,4,-2) = (-4, 16, -8)$ . Row 3: $5(1,-4,2) - 2(-1,4,-2) = (7, -28, 14)$ . A row of a product is a combination of the rows of the right factor, with the left factor’s row as weights. This is the mirror image of ‘combination of columns’.
Compute $AC$ . $(AC)_{11} = 2 - 4 + 2 = 0$ , $(AC)_{12} = 2 + 4 - 6 = 0$ , and row 2 is the negative of row 1. So $AC = O$ ( $2 \times 2$ zero matrix). Every column of $C$ is sent to $O$ by $A$ : the columns of $C$ lie in the null space of $A$ .
Compute $CA$ . Row 1: $2(1,-4,2) + 2(-1,4,-2) = (0,0,0)$ . Row 2: $1(1,-4,2) - 1(-1,4,-2) = (2,-8,4)$ . Row 3: $1(1,-4,2) - 3(-1,4,-2) = (4,-16,8)$ . Same row rule as step 3.

Answer.

AB = \begin{bmatrix}15&-14\\-15&14\end{bmatrix},\ \ BA = \begin{bmatrix}-1&4&-2\\-4&16&-8\\7&-28&14\end{bmatrix},\ \ AC = O,\ \ CA = \begin{bmatrix}0&0&0\\2&-8&4\\4&-16&8\end{bmatrix}.

Here $AC = O$ but $CA \ne O$ , and neither $A$ nor $C$ is zero.

What does hold is the pair of laws that matter for algebra.

Theorem T Apostol Thm 2.17

Matrix multiplication is associative and distributive

For matrices of compatible sizes: $A(BC) = (AB)C$ , $(A + B)C = AC + BC$ , and $C(A + B) = CA + CB$ .

In one line $A(BC) = (AB)C$ , $(A + B)C = AC + BC$ and $C(A + B) = CA + CB$ whenever the products are defined.

Why it is trueMatrices are maps, and composition of maps is associative and distributive. Nobody needs to expand a sum.

ProofApostol 2.15 (Apostol's own proof)

The idea: Turn the matrices into maps using the isomorphism theorem, use the matching law for maps, and turn back.

Let

A, B, C

m \times p

p \times q

q \times n

. Choose linear maps

R, S, T

with

m(R) = A

m(S) = B

m(T) = C

in the standard bases.

'Maps and matrices are the same thing' is onto: with standard bases, every matrix is

m

of some linear map.

(AB)C = m(RS)\,m(T) = m\big((RS)T\big)

'Matrix of a composition', used twice:

m(RS) = AB

, and then

m((RS)T) = m(RS)\,m(T)

(RS)T = R(ST)

, so

m\big((RS)T\big) = m\big(R(ST)\big)

Composition is associative (2.4).

m\big(R(ST)\big) = m(R)\,m(ST) = A\,(BC)

. So

(AB)C = A(BC)

'Matrix of a composition' once more, in the other grouping.

The distributive laws follow in the same way.

The same argument with the distributive laws of 2.4:

m((R + S)T) = m(RT + ST) = m(RT) + m(ST)

, and

m

is linear.

(An alternative proof expands $\sum_k a_{ik}\big(\sum_l b_{kl}c_{lj}\big)$ and swaps the finite sums. It checks the same thing with more index bookkeeping.) Associativity is why $A^n$ makes sense: $A^0 = I$ and $A^n = A\,A^{n-1}$ .

Definition T

Identity matrix

The identity matrix $I_n$ is the matrix of the identity map $I: V \to V$ with the same basis on both sides. Since $I(e_k) = e_k$ , column $k$ is $(0, \dots, 1, \dots, 0)$ with the $1$ in place $k$ , so $I_n$ has $1$ s on the diagonal and $0$ s elsewhere. For $A$ of size $m \times n$ : $I_mA = A = AI_n$ .

In one lineThe square matrix $I_n$ with $1$ on the diagonal and $0$ elsewhere; it is the matrix of the identity map and satisfies $IA = A$ and $AI = A$ .

Why it existsIt is the matrix that does nothing, the unit for matrix multiplication.

The last equation holds because $IT = T = TI$ for maps and $m$ turns products into products.

Inverse matrices

A square matrix $A$ is invertible when the map $x \mapsto Ax$ is one-to-one and onto (2.4; for a map from a space to itself, one-to-one already forces onto, by 2.3). Its inverse is written $A^{-1}$ .

Theorem T Apostol 2.15 and 2.16; Spagnolie Lecture 11

The matrix of an inverse is the inverse of the matrix

Let $T: V \to V$ be one-to-one and onto, with the same basis on both sides, and $A = m(T)$ . Then $m(T^{-1})$ is the unique matrix $A^{-1}$ with $AA^{-1} = I = A^{-1}A$ . Also $(AB)^{-1} = B^{-1}A^{-1}$ when both are invertible.

In one lineIf $T: V \to V$ is invertible and $A = m(T)$ in one basis, then $A^{-1} = m(T^{-1})$ in the same basis, and $AA^{-1} = A^{-1}A = I$ .

Why it is true $m$ turns products into products and the identity map into $I$ .

ProofApostol 2.15 and 2.16

The idea: Apply m to TT⁻¹ = I and T⁻¹T = I. Uniqueness and the product rule come from the same facts about maps.

m(T)\,m(T^{-1}) = m(TT^{-1}) = m(I) = I

'Matrix of a composition':

m(ST) = m(S)\,m(T)

m(T^{-1})\,m(T) = m(T^{-1}T) = m(I) = I

The same, in the other order.

m(T^{-1})

is a two-sided inverse of

A

, and any other two-sided inverse equals it.

AB' = I

and

B'A = I

and also

AB'' = I

, then

B'' = (B'A)B'' = B'(AB'') = B'

by associativity.

For

(AB)^{-1}

(ST)^{-1} = T^{-1}S^{-1}

for maps, so

(AB)^{-1} = B^{-1}A^{-1}

'Inverse of a composition reverses the order' from 2.4, then apply

m

There is a formula for the $2 \times 2$ case that is worth knowing (it will reappear as a determinant in chapter 2.7).

Proposition A Apostol 2.20 #11

Inverse of a 2 by 2 matrix

Let $A = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ and $\Delta = ad - bc$ . If $\Delta \ne 0$ , then $A$ is invertible with $A^{-1} = \frac1\Delta\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ . If $\Delta = 0$ , then $A$ is not invertible.

In one line $\begin{bmatrix}a&b\\c&d\end{bmatrix}$ is invertible exactly when $ad - bc \ne 0$ , and then its inverse is $\frac{1}{ad - bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ .

Why it is trueMultiplying the matrix by the swapped-and-negated matrix gives $(ad - bc)I$ . If $ad - bc = 0$ , a nonzero vector is sent to $O$ .

ProofApostol 2.20 #11; MATH 375 HW7

The idea: If Δ is not zero, multiply and see I. If Δ is zero, exhibit a nonzero vector that A sends to O, so A is not one-to-one.

\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}d&-b\\-c&a\end{bmatrix} = \begin{bmatrix}ad - bc&-ab + ba\\cd - dc&-cb + da\end{bmatrix} = \Delta\, I

Row times column, entry by entry.

\Delta \ne 0

, then

A^{-1} = \frac1\Delta\begin{bmatrix}d&-b\\-c&a\end{bmatrix}

works on both sides.

Divide by

\Delta

, which is allowed when

\Delta \ne 0

. The same multiplication in the other order gives

\Delta I

too, so the result is a two-sided inverse.

\Delta = 0

A\begin{bmatrix}d\\-c\end{bmatrix} = \begin{bmatrix}ad - bc\\cd - dc\end{bmatrix} = O

and

A\begin{bmatrix}-b\\a\end{bmatrix} = \begin{bmatrix}-ab + ba\\-cb + da\end{bmatrix} = O

Compute

A

times the column

(d, -c)

and times

(-b, a)

A

is not one-to-one, hence not invertible (2.4).

A

is not the zero matrix, one of

a, b, c, d

is nonzero, so one of the two columns above is not

O

. The zero matrix is not invertible either. A nonzero vector in

N(A)

means

A

is not one-to-one.

Quick checkWhich of these matrices is NOT invertible?

Worked example

Find the inverse of

A = \begin{bmatrix}5&2\\7&3\end{bmatrix}

and use it to solve

Ax = \begin{bmatrix}4\\-1\end{bmatrix}

Solution.

Compute $\Delta$ . $\Delta = 5\cdot3 - 2\cdot7 = 15 - 14 = 1$ . The inverse exists exactly when $\Delta \ne 0$ .
Swap the diagonal and negate the off-diagonal. $\begin{bmatrix}3&-2\\-7&5\end{bmatrix}$ , then divide by $\Delta = 1$ . So $A^{-1} = \begin{bmatrix}3&-2\\-7&5\end{bmatrix}$ . The formula $\frac1\Delta\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ .
Check. $AA^{-1} = \begin{bmatrix}15 - 14&-10 + 10\\21 - 21&-14 + 15\end{bmatrix} = I$ . A claimed inverse must multiply back to $I$ .
Solve by multiplying by the inverse. $x = A^{-1}\begin{bmatrix}4\\-1\end{bmatrix} = \begin{bmatrix}12 + 2\\-28 - 5\end{bmatrix} = \begin{bmatrix}14\\-33\end{bmatrix}$ . From $Ax = b$ , multiply both sides on the left by $A^{-1}$ : $A^{-1}Ax = x$ .
Check the solution. $A\begin{bmatrix}14\\-33\end{bmatrix} = \begin{bmatrix}70 - 66\\98 - 99\end{bmatrix} = \begin{bmatrix}4\\-1\end{bmatrix}$ . Plug back into the original equation.

Answer. $A^{-1} = \begin{bmatrix}3&-2\\-7&5\end{bmatrix}$ and $x = (14, -33)$ .

Your answerFind the inverse of

\begin{bmatrix}3&1\\4&2\end{bmatrix}

. What is the entry in row 1, column 2 of the inverse?

Worked example used in graphics

Find the

3 \times 3

homogeneous matrix that scales the plane by 2 about the origin and then shifts it by

(1, 3)

; apply it to

(1, 1)

and find its inverse

Solution.

Explain homogeneous coordinates. Shifting is not a linear map, so a matrix cannot do it directly. The trick is to write the point $(x, y)$ as the column $(x, y, 1)$ . A shift adds a constant, and the constant can be produced as the third coordinate times a column.
Write the matrix. Scaling by 2 is $\begin{bmatrix}2&0\\0&2\end{bmatrix}$ on $(x,y)$ . The shift adds $1$ to $x$ and $3$ to $y$ . Together: $H = \begin{bmatrix}2&0&1\\0&2&3\\0&0&1\end{bmatrix}$ . The last row $(0, 0, 1)$ keeps the third coordinate equal to $1$ . The last column carries the shift.
Apply it. $H\begin{bmatrix}1\\1\\1\end{bmatrix} = \begin{bmatrix}2 + 0 + 1\\0 + 2 + 3\\1\end{bmatrix} = \begin{bmatrix}3\\5\\1\end{bmatrix}$ , the point $(3, 5)$ . Check by hand: scale $(1,1)$ to $(2,2)$ , then shift to $(3,5)$ .
Invert in two stages. Undo the shift first (subtract $(1, 3)$ ), then undo the scaling (halve): $H^{-1} = \begin{bmatrix}\tfrac12&0&0\\0&\tfrac12&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&-1\\0&1&-3\\0&0&1\end{bmatrix} = \begin{bmatrix}\tfrac12&0&-\tfrac12\\0&\tfrac12&-\tfrac32\\0&0&1\end{bmatrix}$ . $H = (\text{shift})(\text{scale})$ , so $H^{-1} = (\text{scale})^{-1}(\text{shift})^{-1}$ , socks and shoes.
Check. $H^{-1}(3, 5, 1) = (\tfrac32 - \tfrac12,\ \tfrac52 - \tfrac32,\ 1) = (1, 1, 1)$ . It must return the starting point.

Answer. $H = \begin{bmatrix}2&0&1\\0&2&3\\0&0&1\end{bmatrix}$ , $H(1,1,1) = (3,5,1)$ , and $H^{-1}$ as above.

Powers of a matrix

Worked example Apostol 2.16 #6; MATH 375 HW7

For

A = \begin{bmatrix}1&1\\0&1\end{bmatrix}

, find

A^2

and

A^n

, and prove the formula by induction

Solution.

Compute small powers. $A^2 = \begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix} = \begin{bmatrix}1&2\\0&1\end{bmatrix}$ and $A^3 = A\,A^2 = \begin{bmatrix}1&3\\0&1\end{bmatrix}$ . Compute until a pattern appears; here the top-right entry counts the powers.
State the guess. $A^n = \begin{bmatrix}1&n\\0&1\end{bmatrix}$ for every $n \ge 1$ . It fits $n = 1, 2, 3$ . A guess is not a proof, so we prove it by induction.
Base case. For $n = 1$ the formula says $A^1 = \begin{bmatrix}1&1\\0&1\end{bmatrix}$ , which is $A$ . Induction starts from one true case.
Inductive step. Assume $A^{n-1} = \begin{bmatrix}1&n-1\\0&1\end{bmatrix}$ . Then $A^n = A\,A^{n-1} = \begin{bmatrix}1&1\\0&1\end{bmatrix}\begin{bmatrix}1&n-1\\0&1\end{bmatrix} = \begin{bmatrix}1&(n-1) + 1\\0&1\end{bmatrix} = \begin{bmatrix}1&n\\0&1\end{bmatrix}$ . The definition $A^n = A\,A^{n-1}$ , the hypothesis, then one row-times-column multiplication.

Answer. $A^n = \begin{bmatrix}1&n\\0&1\end{bmatrix}$ . Geometrically, $n$ shears in a row slide the point $(0,1)$ to $(n, 1)$ .

The transpose

Definition T

Transpose

The transpose of an $m \times n$ matrix $A = (a_{ij})$ is the $n \times m$ matrix $A^{\mathsf T}$ with $(A^{\mathsf T})_{ij} = a_{ji}$ : rows become columns. For example, $\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}^{\mathsf T} = \begin{bmatrix}1&4\\2&5\\3&6\end{bmatrix}$ .

In one lineThe matrix $A^{\mathsf T}$ whose rows are the columns of $A$ : $(A^{\mathsf T})_{ij} = a_{ji}$ .

Why it existsIt swaps the roles of input and output. Later it is the matrix that moves across an inner product.

Directly from the definition, $(A^{\mathsf T})^{\mathsf T} = A$ , $(A + B)^{\mathsf T} = A^{\mathsf T} + B^{\mathsf T}$ and $(cA)^{\mathsf T} = cA^{\mathsf T}$ . The one that needs a proof reverses the order, like inverses.

Theorem T Apostol 3.6 #7(d); MATH 375 HW7 (2.21 #7)

Transpose of a product

For $A$ of size $m \times p$ and $B$ of size $p \times n$ , $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ .

In one line $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ .

Why it is trueEntries of $AB$ come from a row of $A$ and a column of $B$ , and the transposes swap which is which.

ProofApostol 3.6 #7

The idea: Compare the (i, j) entries of both sides, one definition at a time.

\big((AB)^{\mathsf T}\big)_{ij} = (AB)_{ji}

Definition of transpose: swap the indices of

AB

= \sum_k a_{jk}b_{ki}

Definition of the product, entry

(j, i)

= \sum_k (B^{\mathsf T})_{ik}\,(A^{\mathsf T})_{kj}

Definition of transpose, backwards:

a_{jk} = (A^{\mathsf T})_{kj}

and

b_{ki} = (B^{\mathsf T})_{ik}

. The numbers commute, so we can write

b

first.

= (B^{\mathsf T}A^{\mathsf T})_{ij}

. All entries agree.

Definition of the product of

B^{\mathsf T}

(

n \times p

) and

A^{\mathsf T}

(

p \times m

), entry

(i, j)

Your answerLet

A = \begin{bmatrix}1&2\\3&4\end{bmatrix}

and

B = \begin{bmatrix}0&1\\1&0\end{bmatrix}

. Compute

(AB)^{\mathsf T}

. What is its entry in row 1, column 2?

(Chapter 2.9 gives the transpose its geometric meaning, once we have inner products.)

Changing the basis

Now fix one space $V$ of dimension $n$ and one map $T: V \to V$ . Take two ordered bases: the old basis $\mathcal E = (e_1, \dots, e_n)$ and the new basis $\mathcal F = (f_1, \dots, f_n)$ . Let $A = m_{\mathcal E \to \mathcal E}(T)$ be the matrix of $T$ in the old basis and $B = m_{\mathcal F \to \mathcal F}(T)$ the matrix in the new basis. How are $A$ and $B$ related?

Definition T

Change of basis

Write each new basis vector in the old basis, $f_j = \sum_k c_{kj}e_k$ . The change-of-basis matrix is $C = (c_{kj})$ . Its $j$ th column is the old coordinates of $f_j$ . In the language of the previous sections, $C = m_{\mathcal F \to \mathcal E}(I)$ , the matrix of the identity map with the new basis on the input side and the old basis on the output side.

In one lineThe matrix $C$ whose column $j$ is the new basis vector $f_j$ written in old coordinates; it converts new coordinates into old ones.

Why it existsIt is the dictionary between two descriptions of the same space.

Theorem T Apostol 4.9; Spagnolie Lecture 17

Coordinates change by C

For every $x \in V$ : $[x]_{\mathcal E} = C\,[x]_{\mathcal F}$ . The matrix $C$ is invertible, and its inverse $C^{-1} = m_{\mathcal E \to \mathcal F}(I)$ turns old coordinates into new: $[x]_{\mathcal F} = C^{-1}[x]_{\mathcal E}$ .

In one line $[x]_{\mathcal E} = C\,[x]_{\mathcal F}$ , and $C$ is invertible with $C^{-1} = m_{\mathcal E \to \mathcal F}(I)$ .

Why it is true $C$ is the matrix of the identity map, so it turns new coordinates into old coordinates, and the matrix of the reverse trip is its inverse.

ProofApostol 4.9; Spagnolie Lecture 17

The idea: x is the identity map applied to x. 'Matrix times vector' for the identity map says exactly this. For the inverse, compose the two identity matrices.

By ‘Matrix times vector’,

[I(x)]_{\mathcal E} = m_{\mathcal F \to \mathcal E}(I)\,[x]_{\mathcal F}

. Since

I(x) = x

[x]_{\mathcal E} = C[x]_{\mathcal F}

I(x) = x

, and

C = m_{\mathcal F \to \mathcal E}(I)

takes

\mathcal F

-coordinates of the input to

\mathcal E

-coordinates of the output.

m_{\mathcal E \to \mathcal F}(I)\; m_{\mathcal F \to \mathcal E}(I) = m_{\mathcal F \to \mathcal F}(I) = I_n

'Matrix of a composition' for

II = I

with three bases: first

\mathcal F \to \mathcal E

, then

\mathcal E \to \mathcal F

m_{\mathcal F \to \mathcal E}(I)\; m_{\mathcal E \to \mathcal F}(I) = I_n

The same in the other order:

\mathcal E \to \mathcal F \to \mathcal E

C

is invertible and

C^{-1} = m_{\mathcal E \to \mathcal F}(I)

Definition of an inverse matrix.

Remember the direction. $C$ takes NEW coordinates to OLD coordinates. It is the matrix whose columns are the new basis written in old language.

Theorem T Apostol Thm 4.6 and 4.7; Spagnolie Lecture 17

Change of basis rewrites the matrix of a map

Let $T: V \to V$ be linear, $A = m_{\mathcal E \to \mathcal E}(T)$ , $B = m_{\mathcal F \to \mathcal F}(T)$ , and $C$ the change-of-basis matrix. Then $B = C^{-1}AC$ . Conversely, if $A$ is the matrix of $T$ in the basis $\mathcal E$ and $C$ is any invertible matrix, then $C^{-1}AC$ is the matrix of $T$ in the basis $\mathcal F$ whose columns, in $\mathcal E$ -coordinates, are the columns of $C$ .

In one lineIf $A$ and $B$ are the matrices of $T$ in the old and new bases, then $B = C^{-1}AC$ . Conversely every $C^{-1}AC$ is the matrix of the same map in some basis.

Why it is trueTo describe $T$ in new coordinates: convert new to old, apply the old matrix, convert back. The three conversions are $C$ , $A$ , $C^{-1}$ , read right to left.

ProofApostol 4.9 proves this with matrices of vectors; this is the same idea phrased with maps

The idea: T does not care about bases: T = I∘T∘I. Give each factor a matrix with the right bases, and multiply (matrix of a composition).

Write

T = I \circ T \circ I

as a chain of maps

(V, \mathcal F) \xrightarrow{\,I\,} (V, \mathcal E) \xrightarrow{\,T\,} (V, \mathcal E) \xrightarrow{\,I\,} (V, \mathcal F)

The identity map changes nothing, so

T = I\,T\,I

. We give the three factors different bases so that each has a matrix we know.

The first map has matrix

C

, the middle map has matrix

A

, and the last map has matrix

m_{\mathcal E \to \mathcal F}(I) = C^{-1}

Matrices of the three pieces:

C

, then

A

, then

C^{-1}

from the previous theorem.

B = m_{\mathcal F \to \mathcal F}(T) = C^{-1}\,A\,C

'Matrix of a composition': the matrix of a chain is the product, with the first map on the right.

The vectors

f_1, \dots, f_n

form a basis

\mathcal F

, and

C

is its change-of-basis matrix.

Converse. Let

C

be invertible and define

f_j = \sum_k c_{kj}e_k

. Let

U

be the linear map with

U(e_j) = f_j

('Prescribed values on a basis'), so

m(U) = C

. Let

U'

be the linear map whose matrix is

C^{-1}

. Then

m(UU') = CC^{-1} = I = m(I)

and

m(U'U) = I

too. Since

m

is one-to-one ('Maps and matrices are the same thing'),

UU' = U'U = I

. So

U

is one-to-one and onto, and it sends the basis

\mathcal E

to a basis ('One-to-one in finite dimension' from 2.4).

So the matrix of

T

\mathcal F

C^{-1}AC

Apply the first half of this theorem to this

\mathcal F

Proof workshopGive the reason for each line: $B = C^{-1}AC$

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

Write $T = I \circ T \circ I$ as the chain $(V, \mathcal F) \to (V, \mathcal E) \to (V, \mathcal E) \to (V, \mathcal F)$ .
The first map has matrix $C$ .
The middle map has matrix $A$ .
The last map has matrix $C^{-1}$ .
$B = C^{-1}AC$ .

Definition T

Similar matrices

Two $n \times n$ matrices $A$ and $B$ are similar if there is an invertible $C$ with $B = C^{-1}AC$ .

In one lineMatrices $A$ and $B$ with $B = C^{-1}AC$ for some invertible $C$ ; equivalently, two descriptions of the same map in different bases.

Why it existsIt is the right notion of 'the same linear map', since any quantity of the map itself must be the same for similar matrices.

By the theorem and its converse (Apostol Thm 4.8), $A$ and $B$ are similar exactly when they are matrices of the same linear map in two bases. Spagnolie’s slogan: similar matrices are the same transformation in different coordinates. Everything about the map that does not depend on the basis must come out the same for similar matrices. Chapters 2.7 and 2.8 show that the determinant, the trace and the eigenvalues are such quantities. A remark you will need: similarity is an equivalence relation (the prove problem on similarity below proves it).

In the picture. Pick “Eigen example” in the visualizer below and tick ‘eigenlines’. The matrix is $\begin{bmatrix}3&1\\0&2\end{bmatrix}$ . The two dashed lines are special directions that the map only stretches, by 3 and by 2. Use those two directions as the new basis and the matrix of the SAME picture becomes $\begin{bmatrix}3&0\\0&2\end{bmatrix}$ : a table with only a diagonal. That is a change of basis doing its job, and it is why $B = C^{-1}AC$ is worth the effort. Chapter 2.8 shows how to find such a basis.

Worked example Spagnolie Lecture 17; Apostol 4.9

Let

T(x) = Ax

with

A = \begin{bmatrix}4&1\\2&3\end{bmatrix}

. Find its matrix

B

in the basis

f_1 = (1,1)

f_2 = (1,-2)

, check it on

x = (2,5)

, and use it to compute

A^5

Solution.

Answer. $B = \begin{bmatrix}5&0\\0&2\end{bmatrix}$ and $A^5 = \begin{bmatrix}2094&1031\\2062&1063\end{bmatrix}$ .

Quick check

B = C^{-1}AC

where the columns of

C

are the new basis vectors in old coordinates. To find

B

's action on new coordinates

y

, which happens FIRST?

Your answerIn the example above the new basis is

f_1 = (1, 1)

f_2 = (1, -2)

. Write

x = (4, 1)

c_1 f_1 + c_2 f_2

. What is

c_1

, the first new coordinate?

Worked example Spagnolie Lecture 17 (powers); the general n is a prove problem below

Prove: if

B = C^{-1}AC

, then

B^2 = C^{-1}A^2C

Solution.

Write $B^2$ as a product. $B^2 = B\,B = (C^{-1}AC)(C^{-1}AC)$ . That is the definition of the square.
Regroup. $= C^{-1}A\,(C\,C^{-1})\,AC$ . Matrix multiplication is associative, so brackets can move.
Cancel. $C\,C^{-1} = I$ and $A\,I = A$ , so this is $C^{-1}A\,A\,C$ . The middle $C\,C^{-1}$ cancels because $C^{-1}$ is the inverse of $C$ .
Name the result. $= C^{-1}A^2C$ . Definition of $A^2$ .

Answer. $B^2 = C^{-1}A^2C$ . Every power cancels the middle pairs in the same way.

The simplest matrix a map can have

If you may choose different bases for the input and output, you can make the matrix almost empty.

Theorem T Apostol Thm 2.14; Spagnolie Lecture 10 (diagonal form)

Diagonal form of a linear map

Let $\dim V = n$ , $\dim W = m$ , and $r = \operatorname{rank} T$ . There are bases $(e_1, \dots, e_n)$ of $V$ and $(w_1, \dots, w_m)$ of $W$ with $T(e_i) = w_i$ for $i = 1, \dots, r$ and $T(e_i) = O$ for $i = r+1, \dots, n$ . The matrix of $T$ is then the $m \times n$ matrix with $1$ in positions $(1,1), \dots, (r,r)$ and $0$ elsewhere.

In one lineFor $T: V \to W$ of rank $r$ there are bases of $V$ and $W$ in which the matrix has $1$ s in the first $r$ diagonal places and $0$ everywhere else.

Why it is trueChoose a basis of the range and lift it to $V$ ; fill out with a basis of the null space.

ProofApostol 2.11; Spagnolie Lecture 10 page 5

The idea: Start in W: a basis of the range, extended to a basis of W. Lift the range basis back to V. Then add a basis of the null space. Rank–nullity says the count is right.

Let

w_1, \dots, w_r

be a basis of

T(V)

The range

T(V)

is a subspace of

W

of dimension

r

, so it has a basis (2.2).

Extend to a basis

w_1, \dots, w_r, w_{r+1}, \dots, w_m

W

'Extending to a basis' (2.2): an independent set extends to a basis of

W

For

i \le r

choose

e_i \in V

with

T(e_i) = w_i

Each

w_i

with

i \le r

is in the range, so it has a source.

Let

e_{r+1}, \dots, e_n

be a basis of

N(T)

, so

T(e_i) = O

for

i > r

The null space has dimension

k = n - r

by rank–nullity (2.3).

It remains to show

e_1, \dots, e_n

are independent. Applying

T

gives

\sum_{i=1}^r c_i w_i = O

Since there are

n = r + k

vectors, it is enough to show independence ('Extending to a basis' (b)). Suppose

\sum_{i=1}^n c_ie_i = O

and apply

T

c_1 = \dots = c_r = 0

The

w_i

with

i \le r

are independent.

Then

\sum_{i>r} c_ie_i = O

forces

c_{r+1} = \dots = c_n = 0

. So the

e_i

are a basis of

V

, and the matrix has the claimed form.

What remains is a combination of a basis of the null space equal to

O

(Spagnolie’s page has a typo in the index range. The second condition is for $i = r+1, \dots, n$ because there are $n$ basis vectors of $V$ .) This is what the differentiation example above did with $D$ : the basis $(x, \tfrac12 x^2, \tfrac13 x^3, 1)$ maps the first three vectors onto $1, x, x^2$ and the last one into the null space.

A preview· Preview: the case V = W with one shared basis

The theorem above allows different bases on the two sides. When the input and output spaces are the same space and the bases must agree, as in the change-of-basis section, you cannot always reach a diagonal matrix. When you can, the diagonal entries are the eigenvalues of chapter 2.8, and $A = CBC^{-1}$ is the factorisation that makes $A^{500}$ easy. The shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ is the standard example that cannot be diagonalised.

Where it is used

Used inside maths· Inside maths: the chain rule is a matrix product

In multivariable calculus the derivative of a map $g: \mathbb R^2 \to \mathbb R^2$ at a point is a linear map, and its matrix is the Jacobian $Dg$ of partial derivatives. The chain rule from Lectures 22 and 23 says $D(F \circ g) = DF(g)\;Dg$ , a product of matrices, because the derivative of a composition is the composition of derivatives. Take polar coordinates $g(r, \theta) = (r\cos\theta, r\sin\theta)$ and $F(x, y) = x^2 + y^2$ . Then $DF = \begin{bmatrix}2x&2y\end{bmatrix}$ and $Dg = \begin{bmatrix}\cos\theta&-r\sin\theta\\\sin\theta&r\cos\theta\end{bmatrix}$ , so

D(F\circ g) = \begin{bmatrix}2r\cos\theta&2r\sin\theta\end{bmatrix}\begin{bmatrix}\cos\theta&-r\sin\theta\\\sin\theta&r\cos\theta\end{bmatrix} = \begin{bmatrix}2r&0\end{bmatrix}.

Direct check: $F(g(r,\theta)) = r^2$ , whose partial derivative in $r$ is $2r$ and in $\theta$ is $0$ .

Used inside maths· Inside maths: angle-addition formulas from multiplying rotations

Let $R(\alpha) = \begin{bmatrix}\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha\end{bmatrix}$ be rotation by $\alpha$ . Turning by $\beta$ and then by $\alpha$ is turning by $\alpha + \beta$ , so $R(\alpha)R(\beta) = R(\alpha + \beta)$ . Multiply the left side out. Its first column is $\begin{bmatrix}\cos\alpha\cos\beta - \sin\alpha\sin\beta\\\sin\alpha\cos\beta + \cos\alpha\sin\beta\end{bmatrix}$ . The first column of $R(\alpha + \beta)$ is $(\cos(\alpha + \beta), \sin(\alpha + \beta))$ . Comparing entries gives $\cos(\alpha+\beta) = \cos\alpha\cos\beta - \sin\alpha\sin\beta$ and $\sin(\alpha + \beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta$ , the two formulas you memorised in JEE. They are matrix multiplication, and the memorising was never needed. Also $R(\alpha)R(\beta) = R(\beta)R(\alpha)$ : rotations of the plane about one point commute, unlike the 3D rotations of 2.4.

Used in the real world· Graphics: model, view and projection matrices, chained

To draw a 3D scene, a game engine takes each vertex $p$ (a point of a model) and applies three maps in a row: the model matrix $M_1$ places the object in the world, the view matrix $M_2$ moves the world so the camera sits at the origin looking down the $-z$ axis, and the projection matrix $P$ squeezes the 3D view into a flat image. Shifts are not linear, so the points are written in homogeneous coordinates $(x, y, z, 1)$ , which lets a shift be a $4 \times 4$ matrix. In 2D, rotating $90^\circ$ and shifting by $(5, 2)$ is $H = \begin{bmatrix}0&-1&5\\1&0&2\\0&0&1\end{bmatrix}$ , and $H(1, 0, 1) = (5, 3, 1)$ ; its inverse, the matrix a mouse-click needs, is $H^{-1} = \begin{bmatrix}0&1&-2\\-1&0&5\\0&0&1\end{bmatrix}$ .

The vertex shader on the GPU computes $P\,M_2\,M_1\,p$ . Read it right to left: model first, projection last. A perspective matrix with near plane $1$ and far plane $100$ (field of view $90^\circ$ , square image) is

P = \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-\tfrac{101}{99}&-\tfrac{200}{99}\\0&0&-1&0\end{bmatrix}.

A point $(2, 1, -4)$ in front of the camera is $(2, 1, -4, 1)$ , and $P$ sends it to $(2,\ 1,\ \tfrac{204}{99},\ 4)$ . The last coordinate $4$ is the distance in front of the camera. Dividing by it gives the screen position $(0.5,\ 0.25)$ and a depth of about $0.515$ . That final division is the only non-linear step. Everything before it is matrix multiplication, so the three matrices can be multiplied together once, into $PM_2M_1$ . For a model of 100,000 vertices, multiplying each vertex by three separate $4 \times 4$ matrices costs $3 \times 16 \times 100{,}000 = 4{,}800{,}000$ multiplications. Multiplying the matrices first costs $2 \times 64 = 128$ for the two matrix products, plus $16 \times 100{,}000$ for the vertices: about $1{,}600{,}000$ , three times fewer. Associativity is what makes this legal.

Used in the real world· Robotics: forward kinematics of a two-link arm

A planar robot arm has a first link of length $2$ at angle $\theta_1$ from the $x$ -axis and a second link of length $1$ at angle $\theta_2$ relative to the first. The end of the second link, measured from the elbow, is $R(\theta_2)\,(1, 0)$ in the first link’s frame. Add the first link and rotate everything by $\theta_1$ : the hand is at

p = R(\theta_1)\big[(2, 0) + R(\theta_2)(1, 0)\big].

For $\theta_1 = 90^\circ$ and $\theta_2 = -90^\circ$ : $R(-90^\circ)(1, 0) = (0, -1)$ , then $(2, 0) + (0, -1) = (2, -1)$ , then $R(90^\circ)(2, -1) = (1, 2)$ . Check by drawing: link 1 points straight up to $(0, 2)$ ; link 2 turns $90^\circ$ clockwise from it, so it points right and ends at $(1, 2)$ . Inverse kinematics, going from the hand position back to the angles, asks for the inverse of this chain of rotations, applied in reverse order.

Used in the real world· AI: why a neural network needs nonlinearities between layers

A dense layer is a matrix. For handwritten digits (MNIST, $28 \times 28 = 784$ pixels), a network with a $128 \times 784$ matrix $W_1$ and then a $10 \times 128$ matrix $W_2$ computes $W_2(W_1x)$ , which has $784 \times 128 + 128 \times 10 = 101{,}632$ weights. By associativity $W_2(W_1x) = (W_2W_1)x$ , and $W_2W_1$ is a single $10 \times 784$ matrix with only $7{,}840$ entries. Without a nonlinear function between the layers, the two layers collapse into one, and the second layer has added nothing. The matrix $W_2W_1$ also has rank at most $10$ (the second stretch problem), however large the middle layer is. That is why every deep network inserts a function such as ReLU between matrix products. CS 532 builds on exactly these shape-and-rank facts. A batch of 64 images is a $64 \times 784$ matrix $X$ , and the whole batch passes through the first layer in one product $XW_1^{\mathsf T}$ , a $64 \times 128$ matrix. That one product is what GPUs are built to do fast.

Traps

Watch out· Columns, not rows

The matrix of $T$ has the images $T(e_k)$ as its COLUMNS. Writing them as rows gives the transpose, which is a different map. On HW6 the answer key had a wrong first column in exactly this kind of problem (2.12 #6; the correct matrix is worked out in the Apostol 2.12 #6 problem below).

Watch out· AB is not BA

Even for square matrices of the same size. Spagnolie’s rotate-and-mirror example gives two different answers. And $AB = O$ does not force $A = O$ or $B = O$ (the HW7 example $AC = O$ above). So you cannot cancel a matrix from both sides of an equation the way you cancel a number, unless it is invertible.

Watch out· Shapes: the inside numbers must match

$(m \times p)(p \times n)$ gives $m \times n$ . If $AB$ exists, $BA$ may not exist, and if both exist they can have different sizes ( $2 \times 2$ and $3 \times 3$ in HW7 #1).

Watch out· Reversed order: inverses and transposes

$(AB)^{-1} = B^{-1}A^{-1}$ and $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ . Both reverse the order. And $B = C^{-1}AC$ is not the same as $B = CAC^{-1}$ : which one you need depends on whether $C$ ‘s columns are the NEW basis in OLD coordinates (then $C^{-1}AC$ ) or the other way round. Check which way the coordinates go.

Watch out· Same eigenvalues does not mean similar

Similar matrices share many numbers, but sharing them does not make two matrices similar. (Eigenvalues are defined in chapter 2.8; for now, they are the numbers by which a map stretches the directions it only stretches, like 3 and 2 in the picture above.) $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ and $I$ have the same characteristic polynomial $(\lambda - 1)^2$ , so the same eigenvalues, yet they are not similar (HW10 4.10 #1): $C^{-1}IC = I$ for every $C$ , so $I$ is similar only to itself (see the prove problem on $I$ below).

Problems

checkApostol 2.12 #11; MATH 375 HW6

Let $D$ be differentiation on the span of $\sin x$ and $\cos x$ , with basis $(\sin x, \cos x)$ . Find the matrix of $D$ and of $D^2$ .

Solution

$D(\sin x) = \cos x$ has coordinates $(0, 1)$ , and $D(\cos x) = -\sin x$ has coordinates $(-1, 0)$ . So $m(D) = \begin{bmatrix}0&-1\\1&0\end{bmatrix}$ . Then $m(D)^2 = \begin{bmatrix}0&-1\\1&0\end{bmatrix}\begin{bmatrix}0&-1\\1&0\end{bmatrix} = \begin{bmatrix}-1&0\\0&-1\end{bmatrix} = -I$ , which says $D^2 = -\mathrm{id}$ , i.e. $f'' = -f$ for these functions.

check

$A$ is $2 \times 3$ and $B$ is $3 \times 4$ . What are the sizes of $AB$ and of $BA$ ?

Solution

$AB$ is $2 \times 4$ . $BA$ does not exist: $B$ has 4 columns and $A$ has 2 rows.

check

Compute $\begin{bmatrix}1&2\\3&4\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}$ and $\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}1&2\\3&4\end{bmatrix}$ . What does each do to the first matrix?

Solution

The first product is $\begin{bmatrix}2&1\\4&3\end{bmatrix}$ : multiplying on the right by the swap matrix swaps the COLUMNS. The second is $\begin{bmatrix}3&4\\1&2\end{bmatrix}$ : multiplying on the left swaps the ROWS. (Right factor: columns of the product are combinations of columns of the left factor. Left factor: rows of the product are combinations of rows of the right factor.)

checkApostol 2.12 #2(b)

Find the matrix of the projection $T: \mathbb R^3 \to \mathbb R^2$ , $T(x_1, x_2, x_3) = (x_2, x_3)$ in the standard bases.

Solution

$T(e_1) = (0, 0)$ , $T(e_2) = (1, 0)$ , $T(e_3) = (0, 1)$ , so $m(T) = \begin{bmatrix}0&1&0\\0&0&1\end{bmatrix}$ ( $2 \times 3$ ). Check: it times $(x_1, x_2, x_3)$ gives $(x_2, x_3)$ .

useApostol 2.16 #1; MATH 375 HW7

For the matrices $A, B, C$ of the worked example above, compute $A(2B - 3C)$ in two ways.

Solution

First, $2B - 3C = \begin{bmatrix}2&4\\-2&6\\10&-4\end{bmatrix} - \begin{bmatrix}6&6\\3&-3\\3&-9\end{bmatrix} = \begin{bmatrix}-4&-2\\-5&9\\7&5\end{bmatrix}$ . Then $A(2B - 3C)$ has first row $(1,-4,2)\cdot$ columns: $1(-4) - 4(-5) + 2(7) = 30$ and $1(-2) - 4(9) + 2(5) = -28$ . Row 2 is the negative: $(-30, 28)$ . Second way, using distributivity: $A(2B - 3C) = 2AB - 3AC = 2\begin{bmatrix}15&-14\\-15&14\end{bmatrix} - 3O = \begin{bmatrix}30&-28\\-30&28\end{bmatrix}$ . Both agree.

use

Let $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ and let $T(x) = Ax$ . Find the matrix of $T$ in the basis $f_1 = (1,1)$ , $f_2 = (1,-1)$ .

Solution

$C = \begin{bmatrix}1&1\\1&-1\end{bmatrix}$ and $C^{-1} = \tfrac12\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ (check: $CC^{-1} = I$ ). $AC = \begin{bmatrix}3&1\\3&-1\end{bmatrix}$ . $B = C^{-1}AC = \tfrac12\begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}3&1\\3&-1\end{bmatrix} = \tfrac12\begin{bmatrix}6&0\\0&2\end{bmatrix} = \begin{bmatrix}3&0\\0&1\end{bmatrix}$ . Direct check: $A(1,1) = (3,3) = 3f_1$ and $A(1,-1) = (1,-1) = 1\cdot f_2$ .

useApostol 2.12 #6; MATH 375 HW6 (corrected)

For the map of the worked example with matrix $A = \begin{bmatrix}-1&-1&2\\1&-3&3\\-1&-5&5\end{bmatrix}$ , find its matrix in the basis $e_1 = (2,3,5)$ , $e_2 = (1,0,0)$ , $e_3 = (0,1,-1)$ (same basis on both sides).

Solution

Compute each $T(e_k)$ with $A$ , then write it in the basis. $T(e_1) = A(2,3,5) = (-2-3+10,\ 2-9+15,\ -2-15+25) = (5, 8, 8)$ . Solve $a e_1 + b e_2 + c e_3 = (5,8,8)$ : the second and third entries give $3a + c = 8$ and $5a - c = 8$ , so $a = 2$ , $c = 2$ , and the first gives $2a + b = 5$ , $b = 1$ . Column 1 is $(2, 1, 2)$ . $T(e_2) = A(1,0,0) = (-1, 1, -1)$ : $3a + c = 1$ , $5a - c = -1$ give $a = 0$ , $c = 1$ , then $b = -1$ . Column 2 is $(0, -1, 1)$ . $T(e_3) = A(0, 1, -1) = (-3, -6, -10)$ : $3a + c = -6$ , $5a - c = -10$ give $a = -2$ , $c = 0$ , then $2a + b = -3$ gives $b = 1$ . Column 3 is $(-2, 1, 0)$ . So

B = \begin{bmatrix}2&0&-2\\1&-1&1\\2&1&0\end{bmatrix}.

This agrees with $C^{-1}AC$ for $C = \begin{bmatrix}2&1&0\\3&0&1\\5&0&-1\end{bmatrix}$ (one can verify that $AC = CB$ ). The published key had $T(i)$ wrong in an intermediate step and a wrong first column.

use

A game draws a sprite by rotating it $90^\circ$ counterclockwise about the origin and then shifting it by $(2, -1)$ . Write the $3 \times 3$ homogeneous matrix, apply it to the corner $(3, 1)$ , and find the matrix that undoes it.

Solution

Rotation by $90^\circ$ is $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ , so $H = \begin{bmatrix}0&-1&2\\1&0&-1\\0&0&1\end{bmatrix}$ . Then $H(3, 1, 1) = (0 - 1 + 2,\ 3 + 0 - 1,\ 1) = (1, 2, 1)$ , the point $(1, 2)$ . To undo: subtract $(2, -1)$ , then rotate by $-90^\circ$ , which is $\begin{bmatrix}0&1\\-1&0\end{bmatrix}$ . As matrices, $H^{-1} = \begin{bmatrix}0&1&0\\-1&0&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&-2\\0&1&1\\0&0&1\end{bmatrix} = \begin{bmatrix}0&1&1\\-1&0&2\\0&0&1\end{bmatrix}$ . Check: $H^{-1}(1, 2, 1) = (2 + 1,\ -1 + 2,\ 1) = (3, 1, 1)$ , the corner we started with.

proveApostol 3.6 #7(e); MATH 375 HW7 (2.21 #7)

Prove that if $A$ is invertible then $A^{\mathsf T}$ is invertible and $(A^{\mathsf T})^{-1} = (A^{-1})^{\mathsf T}$ .

Solution

Let $B = A^{-1}$ , so $AB = I$ . Take transposes: $(AB)^{\mathsf T} = I^{\mathsf T} = I$ . By ‘Transpose of a product’, $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ , so $B^{\mathsf T}A^{\mathsf T} = I$ . Likewise $BA = I$ gives $A^{\mathsf T}B^{\mathsf T} = I$ . So $B^{\mathsf T}$ is a two-sided inverse of $A^{\mathsf T}$ , and by uniqueness of the inverse $(A^{\mathsf T})^{-1} = B^{\mathsf T} = (A^{-1})^{\mathsf T}$ .

proveApostol 4.9

Prove that similarity is an equivalence relation: (i) $A$ is similar to $A$ ; (ii) if $A$ is similar to $B$ then $B$ is similar to $A$ ; (iii) if $A$ is similar to $B$ and $B$ to $D$ then $A$ is similar to $D$ .

Solution

(i) $A = I^{-1}AI$ . (ii) If $B = C^{-1}AC$ , then multiplying by $C$ on the left and $C^{-1}$ on the right gives $CBC^{-1} = A$ . Write this as $A = (C^{-1})^{-1}B\,(C^{-1})$ , so $A$ is similar to $B$ via the invertible matrix $C^{-1}$ . (iii) If $B = C^{-1}AC$ and $D = E^{-1}BE$ , then $D = E^{-1}C^{-1}ACE = (CE)^{-1}A(CE)$ , using $(CE)^{-1} = E^{-1}C^{-1}$ . And $CE$ is invertible as a product of invertible matrices.

proveSpagnolie Lecture 17

Let $B = C^{-1}AC$ . Prove by induction that $B^n = C^{-1}A^nC$ for every $n \ge 1$ . Deduce $A^n = CB^nC^{-1}$ .

Solution

For $n = 1$ the claim is the hypothesis. Assume $B^{n-1} = C^{-1}A^{n-1}C$ . Then $B^n = B\,B^{n-1} = (C^{-1}AC)(C^{-1}A^{n-1}C) = C^{-1}A\,(CC^{-1})\,A^{n-1}C = C^{-1}A^nC$ , using associativity and $CC^{-1} = I$ . For the second claim, multiply $B^n = C^{-1}A^nC$ on the left by $C$ and on the right by $C^{-1}$ : $CB^nC^{-1} = (CC^{-1})A^n(CC^{-1}) = A^n$ .

proveApostol 2.16 #9; MATH 375 HW7

Let $A = \begin{bmatrix}1&0\\-1&1\end{bmatrix}$ . Prove $A^2 = 2A - I$ , then prove $A^n = nA - (n-1)I$ for all $n \ge 1$ , and compute $A^{100}$ .

Solution

$A^2 = \begin{bmatrix}1&0\\-2&1\end{bmatrix}$ and $2A - I = \begin{bmatrix}2&0\\-2&2\end{bmatrix} - \begin{bmatrix}1&0\\0&1\end{bmatrix} = \begin{bmatrix}1&0\\-2&1\end{bmatrix}$ . Equal. For the induction: $n = 1$ gives $A = 1A - 0I$ . Assume $A^{n-1} = (n-1)A - (n-2)I$ . Then $A^n = A\,A^{n-1} = (n-1)A^2 - (n-2)A = (n-1)(2A - I) - (n-2)A = nA - (n-1)I$ . For $n = 100$ : $A^{100} = 100A - 99I = \begin{bmatrix}100&0\\-100&100\end{bmatrix} - \begin{bmatrix}99&0\\0&99\end{bmatrix} = \begin{bmatrix}1&0\\-100&1\end{bmatrix}$ . (Matches the pattern $A^n = \begin{bmatrix}1&0\\-n&1\end{bmatrix}$ .)

proveStrang

Prove that similar matrices have the same trace, where the trace of a square matrix is the sum of its diagonal entries. (Hint: first prove $\operatorname{tr}(PQ) = \operatorname{tr}(QP)$ .)

Solution

$\operatorname{tr}(PQ) = \sum_i (PQ)_{ii} = \sum_i\sum_k p_{ik}q_{ki}$ , and $\operatorname{tr}(QP) = \sum_k\sum_i q_{ki}p_{ik}$ . These are the same finite double sum with the order of summation swapped and the numbers $p_{ik}q_{ki}$ multiplied in the other order, so they are equal. Now if $B = C^{-1}AC$ , put $P = C^{-1}$ and $Q = AC$ : $\operatorname{tr}(B) = \operatorname{tr}(C^{-1}\cdot AC) = \operatorname{tr}(AC\cdot C^{-1}) = \operatorname{tr}(A)$ .

proveMATH 375 HW10 4.10 #1

Prove that $I$ is similar only to itself. Deduce that $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ is not similar to $I$ .

Solution

If $B = C^{-1}IC$ , then $B = C^{-1}C = I$ . So the only matrix similar to $I$ is $I$ . The shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ is not $I$ , so it is not similar to $I$ , although both have the eigenvalue $1$ only.

stretchAxler 3.D

Let $A$ be an $n \times n$ matrix with $AB = BA$ for every $n \times n$ matrix $B$ . Prove $A = cI$ for some number $c$ .

Solution

Use $B = E_{ij}$ (the matrix with a single $1$ in row $i$ , column $j$ ). Computing entries, $(AE_{ij})_{kl} = \sum_m a_{km}(E_{ij})_{ml} = a_{ki}$ if $l = j$ and $0$ otherwise. Likewise $(E_{ij}A)_{kl} = a_{jl}$ if $k = i$ and $0$ otherwise. Since $AE_{ij} = E_{ij}A$ , compare entries. Take $l = j$ and $k \ne i$ : $a_{ki} = 0$ . So every off-diagonal entry of $A$ is $0$ (any off-diagonal pair $(k, i)$ with $k \ne i$ arises). Take $k = i$ , $l = j$ : $a_{ii} = a_{jj}$ . So all diagonal entries are equal, to some $c$ , and $A = cI$ .

stretch

Prove that $\operatorname{rank}(ST) \le \min(\operatorname{rank} S,\ \operatorname{rank} T)$ for linear maps $T: U \to V$ and $S: V \to W$ with finite-dimensional domains. Why does this bound the rank of $W_2W_1$ in the neural-network example?

Solution

The range of $ST$ is $S(T(U))$ , which lies inside $S(V)$ , the range of $S$ . A subspace of $S(V)$ has dimension at most $\dim S(V)$ (a problem in 2.2), so $\operatorname{rank}(ST) \le \operatorname{rank} S$ . For the other bound, restrict $S$ to the subspace $X = T(U)$ of $V$ . The restricted map $S|_X: X \to W$ is linear, and by rank–nullity its range has dimension $\dim X - \dim N(S|_X) \le \dim X$ . Its range is $S(T(U))$ , so $\operatorname{rank}(ST) \le \dim T(U) = \operatorname{rank} T$ . In the network, $W_1$ is $128 \times 784$ and $W_2$ is $10 \times 128$ , so $\operatorname{rank}(W_2W_1) \le \operatorname{rank} W_2 \le 10$ , because the range of $W_2$ sits inside $\mathbb R^{10}$ .

Summary

The matrix of a linear map relative to bases has $T(e_k)$ , written in the target basis, as its $k$ th column. Its shape is (target dimension) by (source dimension).
Matrix times vector is a combination of the columns, with the vector’s coordinates as the weights. The map $T \mapsto m(T)$ is an isomorphism from $L(V, W)$ to $\mathbb R^{m \times n}$ , so $\dim L(V, W) = mn$ .
Matrix multiplication is composition. Column $j$ of $AB$ is $A$ times column $j$ of $B$ , which gives the row-times-column rule. It is associative and distributive, and generally not commutative, and the inside sizes must match.
The identity matrix does nothing. $(AB)^{-1} = B^{-1}A^{-1}$ and $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ both reverse the order. A $2 \times 2$ matrix is invertible exactly when $ad - bc \ne 0$ .
The change-of-basis matrix $C$ has the new basis, in old coordinates, as its columns. It converts new coordinates to old ones: $[x]_{\mathcal E} = C[x]_{\mathcal F}$ .
The matrix of the same map in the new basis is $B = C^{-1}AC$ : similar matrices are one map in two languages. Powers become easy when $B$ is diagonal: $A^n = CB^nC^{-1}$ .
With separate bases on input and output, a map of rank $r$ has a matrix with $r$ ones on the diagonal and zeros elsewhere. With one shared basis you often cannot reach that, and finding the best basis is the subject of chapter 2.8.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

2.5 Matrices as maps, multiplication, change of basis

The picture

The idea, in words

Definitions and theorems

Matrices as arrays

Matrix

Matrix space has dimension mn

The matrix of a linear map

Matrix of a linear map

Matrix times vector

Matrices are the maps

Maps and matrices are the same thing

Matrix multiplication is composition

Matrix of a composition

Matrix multiplication

Matrix multiplication does not commute

Matrix multiplication is associative and distributive

Identity matrix

Inverse matrices

The matrix of an inverse is the inverse of the matrix

Inverse of a 2 by 2 matrix

Powers of a matrix

The transpose

Transpose

Transpose of a product

Changing the basis

Change of basis

Coordinates change by C

Change of basis rewrites the matrix of a map

Similar matrices

The simplest matrix a map can have

Diagonal form of a linear map

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere