3.2 Elementary matrices · Matrix Theory

In Example 3.1.13 we solved the running system by adding multiples of one row of its augmented matrix to another, and the paragraph after it argued that such steps never change the solution set, because each can be undone. This section turns that argument into algebra. Every row operation is left multiplication by an invertible matrix, an elementary matrix, so a sequence of row operations is left multiplication by a single invertible matrix $𝐺$ . Then “row operations do not change the solutions” becomes the statement $𝐴 𝐱 =$ $𝐲 \Leftrightarrow$ $𝐺 𝐴 𝐱 =$ $𝐺 𝐲$ , and a run of Gauss–Jordan elimination (Section 3.3) is recorded in one equation, $𝐺 𝐴 = rref (𝐴)$ , which we can reason about with matrix algebra.

3.2.1Row operations as matrix multiplication

Definition 3.2.1 (Elementary row operations). Let $𝐴$ be a matrix with $𝑚$ rows, and let $1 \leq 𝑖, 𝑗 \leq 𝑚$ . An elementary row operation on $𝐴$ is one of the following.

Swap rows $𝑖$ and $𝑗$ , where $𝑖 \neq 𝑗$ .
Scale row $𝑖$ by a scalar $𝑐 \neq 0$ , that is, multiply every entry of row $𝑖$ by $𝑐$ .
Add $𝑐$ times row $𝑖$ to row $𝑗$ , where $𝑖 \neq 𝑗$ and $𝑐 \in 𝐹$ . That is, replace row $𝑗$ by row $𝑗$ plus $𝑐$ times row $𝑖$ , and leave every other row, row $𝑖$ included, unchanged.

These are the operations of type 1, type 2, and type 3. An operation of type 3 is also called a row replacement.

These are the moves on equations from Section 3.1.3, performed on rows, with two restrictions. Both restrictions are there to make each operation reversible. Scaling a row by $0$ turns it into a zero row, and nothing done afterwards can recover the old row. Adding $𝑐$ times row $𝑖$ to row $𝑖$ itself is scaling row $𝑖$ by $1 + 𝑐$ , which erases the row when $𝑐 = - 1$ . When $𝑖 \neq 𝑗$ , a replacement leaves row $𝑖$ in place, so subtracting $𝑐$ times row $𝑖$ from row $𝑗$ undoes it. (The error in Exercise 3.1.35 was to use a row that had already been replaced.)

Intuition (Why row operations should be matrix products). A row operation treats all columns of $𝐴$ alike: the new $𝑙$ th column depends only on the old $𝑙$ th column, and it is computed from it by the same rule for every $𝑙$ . Applied to a single column $𝐱 =$ $(𝑥_{1}, \dots, 𝑥_{𝑚}) \in$ $𝐹^{𝑚}$ , the three operations are the maps that

exchange the entries $𝑥_{𝑖}$ and $𝑥_{𝑗}$ ;
replace $𝑥_{𝑖}$ by $𝑐 𝑥_{𝑖}$ ;
replace $𝑥_{𝑗}$ by $𝑥_{𝑗} + 𝑐 𝑥_{𝑖}$ , that is, $𝐱 \mapsto 𝐱 + 𝑐 𝑥_{𝑖} 𝐞_{𝑗}$ .

Each is linear, since every entry of the output is a fixed linear combination of the entries of $𝐱$ . Every linear map $𝐹^{𝑚} \to 𝐹^{𝑚}$ is multiplication by the $𝑚 \times 𝑚$ matrix whose columns are the images of $𝐞_{1}, \dots, 𝐞_{𝑚}$ (Proposition 2.3.17). Since $𝐞_{1}, \dots, 𝐞_{𝑚}$ are the columns of the identity matrix $𝐼_{𝑚}$ , those images are the columns of the matrix we get by performing the operation on $𝐼_{𝑚}$ . So each row operation should be left multiplication by “the operation performed on $𝐼_{𝑚}$ ”.

Definition 3.2.2 (Elementary matrices). Let $𝑚 \geq 1$ , let $1 \leq 𝑖 \leq 𝑚$ , and let $𝑐 \in 𝐹$ . We define three kinds of $𝑚 \times 𝑚$ matrices.

For $1 \leq 𝑗 \leq 𝑚$ with $𝑗 \neq 𝑖$ , $𝐸_{𝑖 𝑗}$ is the result of swapping rows $𝑖$ and $𝑗$ of $𝐼_{𝑚}$ .
For $𝑐 \neq 0$ , $𝐸_{𝑖 𝑐}$ is the result of scaling row $𝑖$ of $𝐼_{𝑚}$ by $𝑐$ .
For $1 \leq 𝑗 \leq 𝑚$ with $𝑗 \neq 𝑖$ , $𝐸_{𝑖 𝑐 𝑗}$ is the result of adding $𝑐$ times row $𝑖$ of $𝐼_{𝑚}$ to row $𝑗$ .

A matrix of one of these forms is an elementary matrix, of type 1, 2, or 3 respectively. Equivalently, an $𝑚 \times 𝑚$ matrix is elementary if it is obtained from $𝐼_{𝑚}$ by a single elementary row operation.

Each elementary matrix differs from $𝐼_{𝑚}$ in very few entries. $𝐸_{𝑖 𝑐}$ is diagonal, with $𝑐$ in position $(𝑖, 𝑖)$ and $1$ elsewhere on the diagonal. $𝐸_{𝑖 𝑐 𝑗}$ is $𝐼_{𝑚}$ with one more nonzero entry, $𝑐$ in position $(𝑗, 𝑖)$ . That entry sits in row $𝑗$ , the row that changes, and in column $𝑖$ , the number of the row that is added. $𝐸_{𝑖 𝑗}$ agrees with $𝐼_{𝑚}$ outside rows $𝑖$ and $𝑗$ ; its row $𝑖$ has its $1$ in column $𝑗$ , and its row $𝑗$ has its $1$ in column $𝑖$ .

Example 3.2.3 (Elementary matrices of size $3$ ). With $𝑚 = 3$ ,

𝐸_{13} = (\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), 𝐸_{2, 5} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 1 \end{matrix}), 𝐸_{3, 2, 1} = (\begin{matrix} 1 & 0 & 2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), 𝐸_{1, - 2, 3} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 2 & 0 & 1 \end{matrix}) .

The first swaps rows $1$ and $3$ , the second scales row $2$ by $5$ , the third adds $2$ times row $3$ to row $1$ , and the fourth adds $- 2$ times row $1$ to row $3$ .

Remark 3.2.4 (Reading the subscripts). The size

𝑚

is not part of the notation. It is always clear from context, since

𝐸

multiplies a matrix with

𝑚

rows on the left (or, in Section 3.2.5, a matrix with

𝑚

columns on the right). The number of subscripts tells the types apart: two for types 1 and 2, three for type 3. When the scalar is a specific number, we separate the subscripts by commas:

𝐸_{2, 5}

scales row

2

5

, and

𝐸_{1, - 2, 3}

adds

- 2

times row

1

to row

3

. A swap carries no scalar, so its subscripts are never separated:

𝐸_{25}

swaps rows

2

and

5

. (We also use commas when an index is a longer expression, as in

𝐸_{𝑘, 𝑠, 𝑘 + 1}

.) A matrix can have several names. For instance

𝐸_{𝑖 𝑗} = 𝐸_{𝑗 𝑖}

, and

𝐼_{𝑚} = 𝐸_{1, 1}

is itself elementary (when

𝑚 \geq 2

, it is also

𝐸_{1, 0, 2}

). Some books write

𝐸_{𝑖 𝑗}

for the matrix with a single

1

in position

(𝑖, 𝑗)

and zeros elsewhere; we never do.

Non-example 3.2.5 (Two operations at once). The matrix

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

is not elementary. It differs from

𝐼_{2}

in all four entries, and the only elementary matrices that differ from

𝐼_{2}

in more than one entry are swaps, whose entries are all

0

1

. It is the result of two operations on

𝐼_{2}

: swapping the rows gives

𝐸_{12}

, and then scaling row

1

2

gives

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

. By Proposition 3.2.7 below, this makes it the product

𝐸_{1, 2} 𝐸_{12}

, in which the swap acts first.

The intuition above says that we only need to know what an operation does to a single column. The following lemma makes this precise. We write $𝜌 [𝐴]$ for the result of applying a map $𝜌$ to each column of $𝐴$ , to distinguish it from $𝜌$ applied to a vector.

Lemma 3.2.6 (Operations that act column by column). Let $𝜌 : 𝐹^{𝑚} \to 𝐹^{𝑚}$ be linear. For $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ with columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , let $𝜌 [𝐴]$ be the $𝑚 \times 𝑛$ matrix with columns $𝜌 (𝐚_{1}),$ $\dots,$ $𝜌 (𝐚_{𝑛})$ . Then

𝜌 [𝐴] = 𝜌 [𝐼_{𝑚}] 𝐴 .

Proof.routine

Uses. Definition 2.3.8 (Matrix–vector product), Definition 2.4.1 (Matrix product), Theorem 2.2.1 (Linear maps are determined by a basis), Definition 1.6.8 (Standard bases), Definition 2.3.15 (The linear map of a matrix)

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. Let

𝑅 = 𝜌 [𝐼_{𝑚}]

. What is the

𝑘

th column of

𝑅

, and what is

𝑅 𝐞_{𝑘}

Hint 2. The linear maps

𝐱 \mapsto 𝑅 𝐱

and

𝜌

agree on the standard basis. Then compare

𝑅 𝐴

and

𝜌 [𝐴]

column by column.

Sketch.

𝑅 = 𝜌 [𝐼_{𝑚}]

has columns

𝜌 (𝐞_{1}),

\dots,

𝜌 (𝐞_{𝑚})

, so

𝑅 𝐞_{𝑘} = 𝜌 (𝐞_{𝑘})

. Two linear maps that agree on a basis are equal, so

𝑅 𝐱 = 𝜌 (𝐱)

for all

𝐱

. The

𝑙

th column of

𝑅 𝐴

𝑅 𝐚_{𝑙} = 𝜌 (𝐚_{𝑙})

Let

𝑅 = 𝜌 [𝐼_{𝑚}]

. The columns of

𝐼_{𝑚}

are

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

, so the

𝑘

th column of

𝑅

𝜌 (𝐞_{𝑘})

. By Definition 2.3.8,

𝑅 𝐞_{𝑘}

is the

𝑘

th column of

𝑅

. So the linear maps

𝑇_{𝑅} : 𝐱 \mapsto 𝑅 𝐱

and

𝜌

agree on the standard basis

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

, and by the uniqueness part of Theorem 2.2.1 they are equal:

𝑅 𝐱 = 𝜌 (𝐱)

for every

𝐱 \in 𝐹^{𝑚}

. By Definition 2.4.1, the

𝑙

th column of

𝑅 𝐴

𝑅 𝐚_{𝑙} = 𝜌 (𝐚_{𝑙})

, which is the

𝑙

th column of

𝜌 [𝐴]

. Hence

𝑅 𝐴 = 𝜌 [𝐴]

. □

Proposition 3.2.7 (Row operations are left multiplications). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , let $1 \leq 𝑖, 𝑗 \leq 𝑚$ with $𝑖 \neq 𝑗$ , and let the elementary matrices below be $𝑚 \times 𝑚$ .

(a) $𝐸_{𝑖 𝑗} 𝐴$ is $𝐴$ with rows $𝑖$ and $𝑗$ swapped.
(b)If $𝑐 \neq 0$ , then $𝐸_{𝑖 𝑐} 𝐴$ is $𝐴$ with row $𝑖$ scaled by $𝑐$ .
(c) $𝐸_{𝑖 𝑐 𝑗} 𝐴$ is $𝐴$ with $𝑐$ times row $𝑖$ added to row $𝑗$ .

That is, performing an elementary row operation on $𝐴$ gives $𝐸 𝐴$ , where $𝐸$ is the result of performing the same operation on $𝐼_{𝑚}$ .

The two proofs below differ in kind. The first explains why the matrix is “the operation performed on $𝐼_{𝑚}$ ”, and it works for any operation that acts on each column by the same linear map. The second computes entries, and on the way it shows what left multiplication by an arbitrary matrix does to rows.

Proof (do it to the identity).routine

Uses. Lemma 3.2.6 (Operations that act column by column), Definition 3.2.2 (Elementary matrices), Definition 1.2.4 (The space $𝐹^{𝑛}$ )

Hint 1. Show that performing the operation on

𝐴

gives

𝜌 [𝐴]

for a linear map

𝜌 : 𝐹^{𝑚} \to 𝐹^{𝑚}

Hint 2. Write

𝜌 (𝐱)

𝐱

plus a multiple of

𝐞_{𝑖}

𝐞_{𝑗}

, and apply Lemma 3.2.6.

Sketch. Each operation changes every column by one map

𝜌 : 𝐹^{𝑚} \to 𝐹^{𝑚}

, for example

𝜌 (𝐱) =

𝐱 +

𝑐 𝑥_{𝑖} 𝐞_{𝑗}

for a replacement. Each

𝜌

is linear because

𝐱 \mapsto 𝑥_{𝑘}

is. By Lemma 3.2.6 the result is

𝜌 [𝐼_{𝑚}] 𝐴

, and

𝜌 [𝐼_{𝑚}]

is the elementary matrix by definition.

Fix one of the three operations, and let $𝜌 : 𝐹^{𝑚} \to 𝐹^{𝑚}$ be the result of performing it on a single column $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑚})$ . Explicitly,

\begin{aligned} swap: & 𝜌 (𝐱) = 𝐱 + (𝑥_{𝑗} - 𝑥_{𝑖}) 𝐞_{𝑖} + (𝑥_{𝑖} - 𝑥_{𝑗}) 𝐞_{𝑗}, \\ scaling: & 𝜌 (𝐱) = 𝐱 + (𝑐 - 1) 𝑥_{𝑖} 𝐞_{𝑖}, \\ replacement: & 𝜌 (𝐱) = 𝐱 + 𝑐 𝑥_{𝑖} 𝐞_{𝑗} . \end{aligned}

(In the first line, the $𝑖$ th entry of $𝜌 (𝐱)$ is $𝑥_{𝑖} +$ $(𝑥_{𝑗} - 𝑥_{𝑖}) =$ $𝑥_{𝑗}$ and the $𝑗$ th entry is $𝑥_{𝑖}$ .) Since vectors in $𝐹^{𝑚}$ are added and scaled entry by entry (Definition 1.2.4), each map $𝐱 \mapsto 𝑥_{𝑘}$ is linear, and so each $𝜌$ is linear. A row operation changes every column of $𝐴$ by the same rule, so performing it on $𝐴$ gives $𝜌 [𝐴]$ , and performing it on $𝐼_{𝑚}$ gives $𝜌 [𝐼_{𝑚}]$ , which is the elementary matrix $𝐸$ of Definition 3.2.2. By Lemma 3.2.6, the result of the operation on $𝐴$ is $𝜌 [𝐴] =$ $𝜌 [𝐼_{𝑚}] 𝐴 =$ $𝐸 𝐴$ . □

Proof (entry by entry).routine

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

Hint 1. Show that the

(𝑘, 𝑙)

entry of

𝐺 𝐴

𝑔_{𝑘 1} 𝑎_{1 𝑙} +

\dots +

𝑔_{𝑘 𝑚} 𝑎_{𝑚 𝑙}

for any

𝐺 \in 𝐹^{𝑚 \times 𝑚}

Hint 2. If row

𝑘

𝐸

equals row

𝑘

𝐼_{𝑚}

, then row

𝑘

𝐸 𝐴

is row

𝑘

𝐴

. Check the remaining rows of

𝐸

one type at a time.

Sketch. Row

𝑘

𝐺 𝐴

𝑔_{𝑘 1}

times row

1

𝐴

, plus

\dots

, plus

𝑔_{𝑘 𝑚}

times row

𝑚

. Rows of

𝐸

that agree with

𝐼_{𝑚}

copy the corresponding rows of

𝐴

. Row

𝑗

𝐸_{𝑖 𝑐 𝑗}

has

1

in column

𝑗

and

𝑐

in column

𝑖

, so row

𝑗

𝐸_{𝑖 𝑐 𝑗} 𝐴

is row

𝑗

plus

𝑐

times row

𝑖

. Swaps and scalings are similar.

Let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ have entries $𝑔_{𝑘 𝑝}$ and columns $𝐠_{1}, \dots, 𝐠_{𝑚}$ . By Definition 2.4.1 and Definition 2.3.8, the $𝑙$ th column of $𝐺 𝐴$ is $𝐺 𝐚_{𝑙} =$ $𝑎_{1 𝑙} 𝐠_{1} +$ $\dots +$ $𝑎_{𝑚 𝑙} 𝐠_{𝑚}$ , whose $𝑘$ th entry is

{(𝐺 𝐴)}_{𝑘 𝑙} = 𝑔_{𝑘 1} 𝑎_{1 𝑙} + 𝑔_{𝑘 2} 𝑎_{2 𝑙} + \dots + 𝑔_{𝑘 𝑚} 𝑎_{𝑚 𝑙} .

In words: row $𝑘$ of $𝐺 𝐴$ is $𝑔_{𝑘 1}$ times row $1$ of $𝐴$ , plus $𝑔_{𝑘 2}$ times row $2$ , and so on. In particular, if row $𝑘$ of $𝐺$ equals row $𝑘$ of $𝐼_{𝑚}$ , with a single $1$ in column $𝑘$ , then row $𝑘$ of $𝐺 𝐴$ is row $𝑘$ of $𝐴$ . So for $𝐺 = 𝐸$ elementary, we only have to look at the rows where $𝐸$ differs from $𝐼_{𝑚}$ .

(a) Row $𝑖$ of $𝐸_{𝑖 𝑗}$ has its $1$ in column $𝑗$ , so row $𝑖$ of $𝐸_{𝑖 𝑗} 𝐴$ is row $𝑗$ of $𝐴$ . Likewise, row $𝑗$ of $𝐸_{𝑖 𝑗} 𝐴$ is row $𝑖$ of $𝐴$ .

(b) Row $𝑖$ of $𝐸_{𝑖 𝑐}$ has $𝑐$ in column $𝑖$ and zeros elsewhere, so row $𝑖$ of $𝐸_{𝑖 𝑐} 𝐴$ is $𝑐$ times row $𝑖$ of $𝐴$ .

(c) Row $𝑗$ of $𝐸_{𝑖 𝑐 𝑗}$ has $1$ in column $𝑗$ , $𝑐$ in column $𝑖$ , and zeros elsewhere (here $𝑖 \neq 𝑗$ matters). By the formula above, ${(𝐸_{𝑖 𝑐 𝑗} 𝐴)}_{𝑗 𝑙} =$ $𝑎_{𝑗 𝑙} +$ $𝑐 𝑎_{𝑖 𝑙}$ , so row $𝑗$ of $𝐸_{𝑖 𝑐 𝑗} 𝐴$ is row $𝑗$ of $𝐴$ plus $𝑐$ times row $𝑖$ of $𝐴$ . □

The second proof shows more than we needed. For any $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ , writing $𝐫_{1}, \dots, 𝐫_{𝑚}$ for the rows of $𝐴$ ,

row 𝑘 of 𝐺 𝐴 = 𝑔_{𝑘 1} 𝐫_{1} + 𝑔_{𝑘 2} 𝐫_{2} + \dots + 𝑔_{𝑘 𝑚} 𝐫_{𝑚},

the linear combination of the rows of $𝐴$ whose coefficients are the entries of row $𝑘$ of $𝐺$ . Left multiplication recombines rows. The elementary matrices are the simplest recombinations: each changes one row, using at most one other row.

Example 3.2.8 (The running system, recorded). The elimination of Example 3.1.13 performed four row operations on the augmented matrix $(𝐴 | 𝐲)$ of the running system: add $- 2$ times row $1$ to row $2$ ; add $- 3$ times row $1$ to row $3$ ; add $- 1$ times row $2$ to row $3$ ; add $- 2$ times row $2$ to row $1$ . By Proposition 3.2.7 these are left multiplications by $𝐸_{1, - 2, 2}$ , $𝐸_{1, - 3, 3}$ , $𝐸_{2, - 1, 3}$ , $𝐸_{2, - 2, 1}$ , in that order. By associativity of matrix multiplication, the final matrix is

𝐸_{2, - 2, 1} (𝐸_{2, - 1, 3} (𝐸_{1, - 3, 3} (𝐸_{1, - 2, 2} (𝐴 | 𝐲)))) = 𝐺 (𝐴 | 𝐲),

where

𝐺 = 𝐸_{2, - 2, 1} 𝐸_{2, - 1, 3} 𝐸_{1, - 3, 3} 𝐸_{1, - 2, 2} .

Realize that the first operation is the rightmost factor of $𝐺$ . To compute $𝐺$ , perform the same four operations on $𝐼_{3}$ (each step is left multiplication by the next factor, by Proposition 3.2.7 again):

𝐼_{3} \to (\begin{matrix} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \to (\begin{matrix} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ - 3 & 0 & 1 \end{matrix}) \to (\begin{matrix} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ - 1 & - 1 & 1 \end{matrix}) \to (\begin{matrix} 5 & - 2 & 0 \\ - 2 & 1 & 0 \\ - 1 & - 1 & 1 \end{matrix}) = 𝐺 .

Multiplying out confirms that $𝐺$ does the whole elimination at once:

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

In Section 3.3 the same bookkeeping, applied to a complete run of Gauss–Jordan elimination, produces the equation $𝐺 𝐴 = rref (𝐴)$ (Theorem 3.3.10).

Exercise 3.2.9.routine Let $𝐴 = (\begin{matrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{matrix})$ . Find elementary matrices $𝐸$ and $𝐸^{'}$ with

𝐸 𝐴 = (\begin{matrix} 1 & 2 \\ 3 & 4 \\ 3 & 2 \end{matrix}), 𝐸^{'} 𝐴 = (\begin{matrix} 5 & 6 \\ 3 & 4 \\ 1 & 2 \end{matrix}),

and write each of them out as a $3 \times 3$ array.

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Definition 3.2.2 (Elementary matrices)

Hint 1. Which rows of

𝐴

changed, and how is each new row built from the old rows?

Hint 2. Row

3

𝐸 𝐴

(5, 6) - 2 (1, 2)

. Once you know the operation, perform it on

𝐼_{3}

Sketch.

𝐸 𝐴

𝐴

with

- 2

times row

1

added to row

3

, so

𝐸 = 𝐸_{1, - 2, 3}

𝐸^{'} 𝐴

𝐴

with rows

1

and

3

swapped, so

𝐸^{'} = 𝐸_{13}

Only row $3$ changed in $𝐸 𝐴$ , and $(3, 2) =$ $(5, 6) -$ $2 (1, 2)$ . So $𝐸 𝐴$ is $𝐴$ with $- 2$ times row $1$ added to row $3$ , and by Proposition 3.2.7 we can take $𝐸 = 𝐸_{1, - 2, 3}$ . In $𝐸^{'} 𝐴$ rows $1$ and $3$ are swapped, so $𝐸^{'} = 𝐸_{13}$ . Performing these operations on $𝐼_{3}$ ,

𝐸 = 𝐸_{1, - 2, 3} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 2 & 0 & 1 \end{matrix}), 𝐸^{'} = 𝐸_{13} = (\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) .

3.2.2Inverses

Each elementary row operation is undone by an operation of the same type: swap the same two rows again, scale row $𝑖$ by $𝑐^{- 1}$ , or add $- 𝑐$ times row $𝑖$ to row $𝑗$ . In the language of matrices:

Proposition 3.2.10 (Inverses of elementary matrices). Every elementary matrix is invertible, and its inverse is an elementary matrix of the same type:

𝐸_{𝑖 𝑗}^{- 1} = 𝐸_{𝑖 𝑗}, 𝐸_{𝑖 𝑐}^{- 1} = 𝐸_{𝑖 𝑐^{- 1}}, 𝐸_{𝑖 𝑐 𝑗}^{- 1} = 𝐸_{𝑖 (- 𝑐) 𝑗} .

Proof.routine

Uses. Proposition 3.2.7 (Row operations are left multiplications), Definition 3.2.2 (Elementary matrices), Definition 2.5.12 (Invertible)

Hint 1. Guess the inverse

𝐸^{'}

from the operation that undoes

𝐸

. To verify

𝐸 𝐸^{'} = 𝐼_{𝑚}

, apply Proposition 3.2.7 with

𝐴 = 𝐸^{'}

: the product

𝐸 𝐸^{'}

𝐸^{'}

with the operation of

𝐸

performed on it.

Hint 2. For type 3, you need row

𝑖

𝐸_{𝑖 (- 𝑐) 𝑗}

. Why is it row

𝑖

𝐼_{𝑚}

Sketch. By Proposition 3.2.7,

𝐸 𝐸^{'}

𝐸^{'}

with the operation of

𝐸

performed on it. Swapping rows

𝑖, 𝑗

𝐸_{𝑖 𝑗}

gives

𝐼_{𝑚}

; scaling row

𝑖

𝐸_{𝑖 𝑐^{- 1}}

𝑐

gives

𝐼_{𝑚}

; adding

𝑐

times row

𝑖

𝐸_{𝑖 (- 𝑐) 𝑗}

, which is row

𝑖

𝐼_{𝑚}

because

𝑖 \neq 𝑗

, to its row

𝑗

gives

𝐼_{𝑚}

. The same holds with the factors exchanged.

We check that each proposed inverse $𝐸^{'}$ satisfies $𝐸 𝐸^{'} = 𝐼_{𝑚}$ and $𝐸^{'} 𝐸 = 𝐼_{𝑚}$ (Definition 2.5.12). By Proposition 3.2.7, $𝐸 𝐸^{'}$ is $𝐸^{'}$ with the operation of $𝐸$ performed on it.

Type 1. $𝐸_{𝑖 𝑗} 𝐸_{𝑖 𝑗}$ is $𝐸_{𝑖 𝑗}$ with rows $𝑖$ and $𝑗$ swapped. Since $𝐸_{𝑖 𝑗}$ is $𝐼_{𝑚}$ with those rows swapped, swapping them back gives $𝐼_{𝑚}$ .

Type 2. Let $𝑐 \neq 0$ . Row $𝑖$ of $𝐸_{𝑖 𝑐^{- 1}}$ has $𝑐^{- 1}$ in column $𝑖$ and zeros elsewhere, and all other rows are rows of $𝐼_{𝑚}$ . Scaling row $𝑖$ by $𝑐$ gives $𝑐 𝑐^{- 1} = 1$ in column $𝑖$ , so $𝐸_{𝑖 𝑐} 𝐸_{𝑖 𝑐^{- 1}} =$ $𝐼_{𝑚}$ . Exchanging the roles of $𝑐$ and $𝑐^{- 1}$ gives $𝐸_{𝑖 𝑐^{- 1}} 𝐸_{𝑖 𝑐} =$ $𝐼_{𝑚}$ .

Type 3. The matrix $𝐸_{𝑖 (- 𝑐) 𝑗}$ differs from $𝐼_{𝑚}$ only in row $𝑗$ , so, as $𝑖 \neq 𝑗$ , its row $𝑖$ is row $𝑖$ of $𝐼_{𝑚}$ : a $1$ in column $𝑖$ and zeros elsewhere. Its row $𝑗$ has $1$ in column $𝑗$ and $- 𝑐$ in column $𝑖$ . Adding $𝑐$ times row $𝑖$ to row $𝑗$ turns the entry $- 𝑐$ into $- 𝑐 + 𝑐 = 0$ and changes nothing else, so $𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 (- 𝑐) 𝑗} =$ $𝐼_{𝑚}$ . Exchanging the roles of $𝑐$ and $- 𝑐$ gives $𝐸_{𝑖 (- 𝑐) 𝑗} 𝐸_{𝑖 𝑐 𝑗} =$ $𝐼_{𝑚}$ . □

The hypothesis $𝑖 \neq 𝑗$ was used exactly once, to know that the operation leaves row $𝑖$ alone. Without it, “adding $- 1$ times row $𝑖$ to row $𝑖$ ” would produce $𝐼_{𝑚}$ with row $𝑖$ replaced by zeros, a matrix that sends $𝐞_{𝑖}$ to $𝟎$ and so is not invertible.

Corollary 3.2.11 (Products of elementary matrices). Let $𝐸_{1},$ $\dots,$ $𝐸_{𝑘} \in$ $𝐹^{𝑚 \times 𝑚}$ be elementary. Then $𝐺 = 𝐸_{𝑘} \dots 𝐸_{2} 𝐸_{1}$ is invertible, and

𝐺^{- 1} = 𝐸_{1}^{- 1} 𝐸_{2}^{- 1} \dots 𝐸_{𝑘}^{- 1}

is again a product of elementary matrices. (For $𝑘 = 0$ , the empty product is $𝐼_{𝑚}$ .)

Proof.routine

Uses. Proposition 3.2.10 (Inverses of elementary matrices), Definition 2.5.12 (Invertible), induction on $𝑘$

Hint 1. Induct on

𝑘

. Write

𝐺 = 𝐸_{𝑘} 𝐺^{'}

, where

𝐺^{'}

is a product of

𝑘 - 1

elementary matrices.

Hint 2. Check that

𝐻^{'} 𝐸_{𝑘}^{- 1}

is a two-sided inverse of

𝐸_{𝑘} 𝐺^{'}

when

𝐻^{'}

is a two-sided inverse of

𝐺^{'}

Sketch. If

𝐺^{'} 𝐻^{'} =

𝐻^{'} 𝐺^{'} =

𝐼_{𝑚}

, then

(𝐸_{𝑘} 𝐺^{'}) (𝐻^{'} 𝐸_{𝑘}^{- 1}) =

𝐸_{𝑘} 𝐸_{𝑘}^{- 1} =

𝐼_{𝑚}

and

(𝐻^{'} 𝐸_{𝑘}^{- 1}) (𝐸_{𝑘} 𝐺^{'}) =

𝐻^{'} 𝐺^{'} =

𝐼_{𝑚}

. Induction on

𝑘

gives

𝐺^{- 1} = 𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}

, and each

𝐸_{𝑙}^{- 1}

is elementary by Proposition 3.2.10.

We induct on $𝑘$ . For $𝑘 = 0$ , $𝐺 = 𝐼_{𝑚}$ is its own inverse. Let $𝑘 \geq 1$ , and suppose $𝐺^{'} = 𝐸_{𝑘 - 1} \dots 𝐸_{1}$ is invertible with inverse $𝐻^{'} =$ $𝐸_{1}^{- 1} \dots 𝐸_{𝑘 - 1}^{- 1}$ . Then $𝐺 = 𝐸_{𝑘} 𝐺^{'}$ , and with $𝐻 = 𝐻^{'} 𝐸_{𝑘}^{- 1}$ , associativity gives

𝐺 𝐻 = 𝐸_{𝑘} (𝐺^{'} 𝐻^{'}) 𝐸_{𝑘}^{- 1} = 𝐸_{𝑘} 𝐸_{𝑘}^{- 1} = 𝐼_{𝑚}, 𝐻 𝐺 = 𝐻^{'} (𝐸_{𝑘}^{- 1} 𝐸_{𝑘}) 𝐺^{'} = 𝐻^{'} 𝐺^{'} = 𝐼_{𝑚} .

So $𝐺$ is invertible with $𝐺^{- 1} =$ $𝐻 =$ $𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}$ , as desired. By Proposition 3.2.10 each $𝐸_{𝑙}^{- 1}$ is elementary. □

Example 3.2.12 (Undoing the running elimination). For the matrix $𝐺 =$ $𝐸_{2, - 2, 1} 𝐸_{2, - 1, 3} 𝐸_{1, - 3, 3} 𝐸_{1, - 2, 2}$ of Example 3.2.8, Corollary 3.2.11 and Proposition 3.2.10 give

𝐺^{- 1} = 𝐸_{1, 2, 2} 𝐸_{1, 3, 3} 𝐸_{2, 1, 3} 𝐸_{2, 2, 1} .

To compute it, perform on $𝐼_{3}$ first the operation of the rightmost factor (add $2$ times row $2$ to row $1$ ), then the others from right to left. The result is

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

Its first two columns are the first two columns $𝐚_{1}, 𝐚_{2}$ of $𝐴$ . This is no accident: $𝐺 𝐴$ has first two columns $𝐞_{1}$ and $𝐞_{2}$ , so $𝐺 𝐚_{1} = 𝐞_{1}$ and $𝐺 𝐚_{2} = 𝐞_{2}$ , that is, $𝐚_{1} = 𝐺^{- 1} 𝐞_{1}$ and $𝐚_{2} = 𝐺^{- 1} 𝐞_{2}$ .

Exercise 3.2.13.routine Over

𝔽_{5}

, write

{(𝐸_{12} 𝐸_{1, 3} 𝐸_{2, 4, 1})}^{- 1}

as a product of

2 \times 2

elementary matrices, and compute it as a matrix.

Solution.

Uses. Corollary 3.2.11 (Products of elementary matrices), Proposition 3.2.10 (Inverses of elementary matrices)

Hint 1. Invert each factor and reverse the order.

Hint 2. In

𝔽_{5}

3^{- 1} = 2

and

- 4 = 1

Sketch. The inverse is

𝐸_{2, - 4, 1} 𝐸_{1, 3^{- 1}} 𝐸_{12} =

𝐸_{2, 1, 1} 𝐸_{1, 2} 𝐸_{12} =

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

By Corollary 3.2.11 and Proposition 3.2.10,

{(𝐸_{12} 𝐸_{1, 3} 𝐸_{2, 4, 1})}^{- 1} = 𝐸_{2, 4, 1}^{- 1} 𝐸_{1, 3}^{- 1} 𝐸_{12}^{- 1} = 𝐸_{2, - 4, 1} 𝐸_{1, 3^{- 1}} 𝐸_{12} = 𝐸_{2, 1, 1} 𝐸_{1, 2} 𝐸_{12},

since $- 4 = 1$ and $3 \cdot 2 = 6 = 1$ in $𝔽_{5}$ . Performing the operations of the factors on $𝐼_{2}$ from right to left: swapping the rows gives $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ , scaling row $1$ by $2$ gives $(\begin{matrix} 0 & 2 \\ 1 & 0 \end{matrix})$ , and adding row $2$ to row $1$ gives $(\begin{matrix} 1 & 2 \\ 1 & 0 \end{matrix})$ . As a check, $𝐸_{12} 𝐸_{1, 3} 𝐸_{2, 4, 1} =$ $(\begin{matrix} 0 & 1 \\ 3 & 2 \end{matrix})$ , and

(\begin{matrix} 0 & 1 \\ 3 & 2 \end{matrix}) (\begin{matrix} 1 & 2 \\ 1 & 0 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 5 & 6 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) in 𝔽_{5} .

3.2.3Row operations preserve solution sets

We can now prove what Section 3.1.3 argued informally. Replacing the equations of a system by combinations of them never loses a solution, and when the replacement can be undone, it gains none either.

Proposition 3.2.14 (Invertible matrices preserve solution sets). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ , and let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible. Then for every $𝐱 \in 𝐹^{𝑛}$ ,

𝐴 𝐱 = 𝐲 \Leftrightarrow (𝐺 𝐴) 𝐱 = 𝐺 𝐲 .

So the systems $𝐴 𝐱 = 𝐲$ and $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ are equivalent. Their augmented matrices are related by $𝐺 (𝐴 | 𝐲) =$ $(𝐺 𝐴 | 𝐺 𝐲)$ .

Proof.routine

Uses. Theorem 2.4.2 (The matrix of a composite), Definition 2.5.12 (Invertible), Definition 2.4.1 (Matrix product), Definition 3.1.12 (Augmented matrix), Definition 3.1.1 (Linear system)

Hint 1. The direction

\Rightarrow

holds for every

𝐺

. Which property of

𝐺

does

\Leftarrow

need?

Hint 2. Multiply

𝐺 (𝐴 𝐱) = 𝐺 𝐲

on the left by

𝐺^{- 1}

, using

(𝐺 𝐴) 𝐱 = 𝐺 (𝐴 𝐱)

Sketch. Since

(𝐺 𝐴) 𝐱 = 𝐺 (𝐴 𝐱)

, applying

𝐺

𝐴 𝐱 = 𝐲

gives

(𝐺 𝐴) 𝐱 = 𝐺 𝐲

; applying

𝐺^{- 1}

𝐺 (𝐴 𝐱) = 𝐺 𝐲

gives back

𝐴 𝐱 = 𝐲

. The columns of

𝐺 (𝐴 | 𝐲)

are

𝐺 𝐚_{1},

\dots,

𝐺 𝐚_{𝑛},

𝐺 𝐲

By Theorem 2.4.2, $𝑇_{𝐺 𝐴} = 𝑇_{𝐺} \circ 𝑇_{𝐴}$ , that is, $(𝐺 𝐴) 𝐱 = 𝐺 (𝐴 𝐱)$ for every $𝐱 \in 𝐹^{𝑛}$ ; likewise $(𝐻 𝐺) 𝐳 = 𝐻 (𝐺 𝐳)$ for all $𝐻 \in 𝐹^{𝑚 \times 𝑚}$ and $𝐳 \in 𝐹^{𝑚}$ .

( $\Rightarrow$ ) If $𝐴 𝐱 = 𝐲$ , then $(𝐺 𝐴) 𝐱 =$ $𝐺 (𝐴 𝐱) =$ $𝐺 𝐲$ .

( $\Leftarrow$ ) Suppose $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ , that is, $𝐺 (𝐴 𝐱) = 𝐺 𝐲$ . Applying $𝐺^{- 1}$ to both sides,

𝐴 𝐱 = (𝐺^{- 1} 𝐺) (𝐴 𝐱) = 𝐺^{- 1} (𝐺 (𝐴 𝐱)) = 𝐺^{- 1} (𝐺 𝐲) = (𝐺^{- 1} 𝐺) 𝐲 = 𝐲 .

So the two systems have the same solutions, which is what it means for them to be equivalent (Definition 3.1.1). Finally, by Definition 2.4.1, the columns of $𝐺 (𝐴 | 𝐲)$ are $𝐺 𝐚_{1},$ $\dots,$ $𝐺 𝐚_{𝑛},$ $𝐺 𝐲$ , where $𝐚_{1}, \dots, 𝐚_{𝑛}$ are the columns of $𝐴$ . The first $𝑛$ of these are the columns of $𝐺 𝐴$ , so $𝐺 (𝐴 | 𝐲) =$ $(𝐺 𝐴 | 𝐺 𝐲)$ . □

Corollary 3.2.15 (Row operations preserve solution sets). If

(𝐴^{'} | 𝐲^{'})

is obtained from

(𝐴 | 𝐲)

by a finite sequence of elementary row operations, then the systems

𝐴 𝐱 = 𝐲

and

𝐴^{'} 𝐱 = 𝐲^{'}

are equivalent.

Proof.routine

Uses. Proposition 3.2.7 (Row operations are left multiplications), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.2.14 (Invertible matrices preserve solution sets)

Hint 1. Write the sequence of operations as left multiplication by one matrix

𝐺

Hint 2.

𝐺

is a product of elementary matrices. Now apply Proposition 3.2.14.

Sketch. If

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

perform the operations, then

(𝐴^{'} | 𝐲^{'}) =

𝐺 (𝐴 | 𝐲) =

(𝐺 𝐴 | 𝐺 𝐲)

with

𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}

invertible, so

𝐴^{'} = 𝐺 𝐴

and

𝐲^{'} = 𝐺 𝐲

, and Proposition 3.2.14 applies.

Let $𝐸_{1}, \dots, 𝐸_{𝑘}$ be the elementary matrices of the operations, in the order performed. By Proposition 3.2.7, applied $𝑘$ times, and associativity,

(𝐴^{'} | 𝐲^{'}) = 𝐸_{𝑘} (\dots (𝐸_{1} (𝐴 | 𝐲)) \dots) = 𝐺 (𝐴 | 𝐲), 𝐺 = 𝐸_{𝑘} \dots 𝐸_{1} .

By Proposition 3.2.14, $𝐺 (𝐴 | 𝐲) =$ $(𝐺 𝐴 | 𝐺 𝐲)$ , so $𝐴^{'} = 𝐺 𝐴$ and $𝐲^{'} = 𝐺 𝐲$ . Since $𝐺$ is invertible (Corollary 3.2.11), Proposition 3.2.14 says that $𝐴 𝐱 = 𝐲$ and $𝐴^{'} 𝐱 = 𝐲^{'}$ are equivalent. □

Remark 3.2.16 (Where invertibility is used). The direction $\Rightarrow$ of Proposition 3.2.14 holds for every matrix $𝐺$ , even a non-square one: replacing the equations of a system by combinations of them never loses a solution. Only $\Leftarrow$ needs $𝐺^{- 1}$ , and without it solutions can be gained. The failed elimination in Exercise 3.1.35 replaced the equations of $𝑥_{1} + 𝑥_{2} = 2$ , $𝑥_{1} - 𝑥_{2} = 0$ by “first minus second” and “second minus first” at the same time, which is left multiplication by

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

This $𝐺$ is not invertible: $𝐺 (1, 1) = 𝟎$ , whereas an invertible matrix sends only $𝟎$ to $𝟎$ (if $𝐺 𝐳 = 𝟎$ , then $𝐳 = 𝐺^{- 1} 𝐺 𝐳 = 𝟎$ ). Accordingly, the new system had solutions that the old one did not. Performed one after the other, the two replacements are $𝐸_{2, - 1, 1}$ followed by $𝐸_{1, - 1, 2}$ , and their product $𝐸_{1, - 1, 2} 𝐸_{2, - 1, 1} =$ $(\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix})$ is invertible. In fact a left inverse of $𝐺$ is all that $\Leftarrow$ needs; see Exercise 3.2.45.

Row operations change the columns of $𝐴$ , but they do not change the linear relations among them. This is the fact that will let us read off relations among the columns of $𝐴$ from a much simpler matrix.

Corollary 3.2.17 (Row operations preserve relations among columns). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible, so that $𝐺 𝐴$ has columns $𝐺 𝐚_{1}, \dots, 𝐺 𝐚_{𝑛}$ . For all $𝑥_{1}, \dots, 𝑥_{𝑛} \in 𝐹$ ,

𝑥_{1} 𝐚_{1} + \dots + 𝑥_{𝑛} 𝐚_{𝑛} = 𝟎 \Leftrightarrow 𝑥_{1} (𝐺 𝐚_{1}) + \dots + 𝑥_{𝑛} (𝐺 𝐚_{𝑛}) = 𝟎 .

In particular:

(a)for distinct indices $𝑙_{1}, \dots, 𝑙_{𝑟}$ , the list $𝐚_{𝑙_{1}}, \dots, 𝐚_{𝑙_{𝑟}}$ is linearly independent if and only if the list $𝐺 𝐚_{𝑙_{1}},$ $\dots,$ $𝐺 𝐚_{𝑙_{𝑟}}$ is;
(b)for scalars $𝑐_{𝑙}$ , $𝐚_{𝑘} =$ $\sum_{𝑙 \neq 𝑘} 𝑐_{𝑙} 𝐚_{𝑙}$ if and only if $𝐺 𝐚_{𝑘} =$ $\sum_{𝑙 \neq 𝑘} 𝑐_{𝑙} 𝐺 𝐚_{𝑙}$ .

Proof.routine

Uses. Proposition 3.2.14 (Invertible matrices preserve solution sets), Definition 2.3.8 (Matrix–vector product), Definition 2.4.1 (Matrix product), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. Write both sides as matrix–vector products:

𝑥_{1} 𝐚_{1} +

\dots +

𝑥_{𝑛} 𝐚_{𝑛} =

𝐴 𝐱

Hint 2. Apply Proposition 3.2.14 with

𝐲 = 𝟎

. For (a) and (b), view a relation among some of the columns as a relation among all of them.

Sketch. By Definition 2.3.8 the two sides are

𝐴 𝐱 = 𝟎

and

(𝐺 𝐴) 𝐱 = 𝟎 = 𝐺 𝟎

, which are equivalent by Proposition 3.2.14. A relation among

𝐚_{𝑙_{1}}, \dots, 𝐚_{𝑙_{𝑟}}

is a relation among all columns with the other coefficients

0

, so the two lists have the same relations, in particular the same nontrivial ones. For (b), use the relation with coefficient

- 1

𝐚_{𝑘}

The columns of $𝐺 𝐴$ are $𝐺 𝐚_{1}, \dots, 𝐺 𝐚_{𝑛}$ by Definition 2.4.1. Let $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑛})$ . By Definition 2.3.8, the left side of the displayed equivalence says $𝐴 𝐱 = 𝟎$ , and the right side says $(𝐺 𝐴) 𝐱 = 𝟎$ . Since $𝐺 𝟎 = 𝟎$ , these are equivalent by Proposition 3.2.14 with $𝐲 = 𝟎$ .

(a) Taking $𝑥_{𝑙} = 0$ for every $𝑙$ outside ${𝑙_{1}, \dots, 𝑙_{𝑟}}$ , the equivalence says that $\sum_{𝑞} 𝑥_{𝑙_{𝑞}} 𝐚_{𝑙_{𝑞}} =$ $𝟎$ if and only if $\sum_{𝑞} 𝑥_{𝑙_{𝑞}} 𝐺 𝐚_{𝑙_{𝑞}} =$ $𝟎$ . So the two lists satisfy the same linear relations. By Theorem 1.5.5, one of them is linearly independent exactly when it satisfies only the trivial relation, and then so does the other.

(b) $𝐚_{𝑘} =$ $\sum_{𝑙 \neq 𝑘} 𝑐_{𝑙} 𝐚_{𝑙}$ says that $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛} =$ $𝟎$ with $𝑥_{𝑘} = - 1$ and $𝑥_{𝑙} = 𝑐_{𝑙}$ for $𝑙 \neq 𝑘$ . By the equivalence, this holds if and only if the same relation holds among the $𝐺 𝐚_{𝑙}$ , which says $𝐺 𝐚_{𝑘} =$ $\sum_{𝑙 \neq 𝑘} 𝑐_{𝑙} 𝐺 𝐚_{𝑙}$ . □

Example 3.2.18 (Reading a relation off the reduced matrix). In Example 3.2.8, $𝐺 𝐴$ has columns $𝐞_{1}$ , $𝐞_{2}$ , and $(- 7, 3, 0) =$ $- 7 𝐞_{1} +$ $3 𝐞_{2}$ . So the third column of $𝐺 𝐴$ is $- 7$ times the first plus $3$ times the second, and by part (b) of Corollary 3.2.17 the same holds in $𝐴$ :

𝐚_{3} = - 7 𝐚_{1} + 3 𝐚_{2}, that is, (\begin{matrix} - 1 \\ 1 \\ 0 \end{matrix}) = - 7 (\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}) + 3 (\begin{matrix} 2 \\ 5 \\ 7 \end{matrix}) .

This is the relation $7 𝐚_{1} - 3 𝐚_{2} + 𝐚_{3} = 𝟎$ behind the homogeneous solution $(7, - 3, 1)$ of Example 3.1.15. By part (a), $𝐚_{1}, 𝐚_{2}$ is linearly independent, because $𝐞_{1}, 𝐞_{2}$ is.

Non-example 3.2.19 (Row operations move the column space). The relations among the columns survive, but the columns themselves move, and so does their span. The columns of the running matrix

𝐴

all lie in the plane

𝑦_{3} = 𝑦_{1} + 𝑦_{2}

, which is

im 𝑇_{𝐴}

(Section 3.1.5). The columns of

𝐺 𝐴

all have third entry

0

, so

im 𝑇_{𝐺 𝐴}

is the plane

𝑦_{3} = 0

. A smaller example: for

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

, the row operation

𝐸_{1, - 1, 2}

gives

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

, and

span ((1, 1)) \neq

span ((1, 0))

. So Proposition 3.2.14 does not say that

𝐴 𝐱 = 𝐲

and

(𝐺 𝐴) 𝐱 = 𝐲

are equivalent: the right-hand side must be replaced by

𝐺 𝐲

Exercise 3.2.20.routine Let

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

Find row operations that turn $𝐴$ into $𝐵$ . Then, using Corollary 3.2.17 and without further computation, write the third column of $𝐴$ as a combination of the first two, and decide whether the first two columns of $𝐴$ are linearly independent. Check your answers directly.

Solution.

Uses. Corollary 3.2.17 (Row operations preserve relations among columns), Proposition 3.2.7 (Row operations are left multiplications), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. Clear the first column below the top entry, then work on the second column.

Hint 2. In

𝐵

, the third column is

𝐞_{1} + 2 𝐞_{2}

and the first two columns are

𝐞_{1}, 𝐞_{2}

Sketch. Add

- 2

times row

1

to row

2

and

- 1

times row

1

to row

3

, add row

2

to row

3

, scale row

2

- 1 / 2

, and add

- 1

times row

2

to row

1

. Since

𝐛_{3} = 𝐛_{1} + 2 𝐛_{2}

and

𝐛_{1}, 𝐛_{2}

is independent,

𝐚_{3} = 𝐚_{1} + 2 𝐚_{2}

and

𝐚_{1}, 𝐚_{2}

is independent.

Adding $- 2$ times row $1$ to row $2$ and $- 1$ times row $1$ to row $3$ gives rows $(1, 1, 3)$ , $(0, - 2, - 4)$ , $(0, 2, 4)$ . Adding row $2$ to row $3$ makes row $3$ zero. Scaling row $2$ by $- 1 / 2$ gives $(0, 1, 2)$ , and adding $- 1$ times this row to row $1$ gives $(1, 0, 1)$ . The result is $𝐵$ . So $𝐵 = 𝐺 𝐴$ , where $𝐺$ is the product of the five elementary matrices, which is invertible by Corollary 3.2.11.

The columns of $𝐵$ are $𝐞_{1}$ , $𝐞_{2}$ , and $𝐞_{1} + 2 𝐞_{2}$ . By Corollary 3.2.17(b), the third column of $𝐴$ is $1$ times the first plus $2$ times the second; and by Corollary 3.2.17(a), the first two columns of $𝐴$ are linearly independent, since $𝐞_{1}, 𝐞_{2}$ is. Directly: $(1, 2, 1) +$ $2 (1, 0, 3) =$ $(3, 2, 7)$ , and if $𝑠 (1, 2, 1) +$ $𝑡 (1, 0, 3) =$ $𝟎$ , then the second entry gives $𝑠 = 0$ and then the first gives $𝑡 = 0$ .

3.2.4Row equivalence

Because row operations can be undone, the relation “ $𝐵$ can be reached from $𝐴$ by row operations” is symmetric, and it partitions matrices of a given size into classes.

Definition 3.2.21 (Row equivalence). Matrices

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

are row equivalent, written

𝐴 \sim 𝐵

, if

𝐵

can be obtained from

𝐴

by a finite sequence of elementary row operations. By Proposition 3.2.7, this means that

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

for some elementary matrices

𝐸_{1},

\dots,

𝐸_{𝑘} \in

𝐹^{𝑚 \times 𝑚}

, where

𝑘 \geq 0

(for

𝑘 = 0

𝐵 = 𝐴

Proposition 3.2.22 (Row equivalence is an equivalence relation). For all $𝐴, 𝐵, 𝐶 \in 𝐹^{𝑚 \times 𝑛}$ :

(reflexivity) $𝐴 \sim 𝐴$ ;
(symmetry) if $𝐴 \sim 𝐵$ , then $𝐵 \sim 𝐴$ ;
(transitivity) if $𝐴 \sim 𝐵$ and $𝐵 \sim 𝐶$ , then $𝐴 \sim 𝐶$ .

Proof.routine

Uses. Definition 3.2.21 (Row equivalence), Proposition 3.2.10 (Inverses of elementary matrices)

Hint 1. For symmetry, undo the operations in the reverse order.

Hint 2. Write

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

and multiply on the left by

𝐸_{𝑘}^{- 1}

, then by

𝐸_{𝑘 - 1}^{- 1}

, and so on. Why is each

𝐸_{𝑙}^{- 1}

allowed?

Sketch. The empty sequence gives

𝐴 \sim 𝐴

. If

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

, then

𝐴 = 𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1} 𝐵

, and each

𝐸_{𝑙}^{- 1}

is elementary by Proposition 3.2.10. If

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

and

𝐶 = 𝐸_{𝑟}^{'} \dots 𝐸_{1}^{'} 𝐵

, then

𝐶 =

𝐸_{𝑟}^{'} \dots 𝐸_{1}^{'} 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

Reflexivity. Take $𝑘 = 0$ .

Symmetry. Let $𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴$ . Multiplying on the left by $𝐸_{𝑘}^{- 1}$ , then by $𝐸_{𝑘 - 1}^{- 1}$ , and so on, gives $𝐴 =$ $𝐸_{1}^{- 1} 𝐸_{2}^{- 1} \dots 𝐸_{𝑘}^{- 1} 𝐵$ . By Proposition 3.2.10 each $𝐸_{𝑙}^{- 1}$ is elementary, so $𝐵 \sim 𝐴$ : the operations of $𝐸_{𝑘}^{- 1}, \dots, 𝐸_{1}^{- 1}$ , performed in that order, turn $𝐵$ into $𝐴$ .

Transitivity. If $𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴$ and $𝐶 = 𝐸_{𝑟}^{'} \dots 𝐸_{1}^{'} 𝐵$ , then $𝐶 =$ $𝐸_{𝑟}^{'} \dots 𝐸_{1}^{'} 𝐸_{𝑘} \dots 𝐸_{1} 𝐴$ , so $𝐴 \sim 𝐶$ . □

In this language, Corollary 3.2.15 says that row equivalent augmented matrices describe equivalent systems. Taking $𝐲 = 𝟎$ gives an invariant that is easy to compute.

Corollary 3.2.23 (Row equivalent matrices have the same kernel). If

𝐴 \in 𝐹^{𝑚 \times 𝑛}

and

𝐺 \in 𝐹^{𝑚 \times 𝑚}

is invertible, then

ker 𝑇_{𝐺 𝐴} = ker 𝑇_{𝐴}

. In particular, if

𝐴 \sim 𝐵

, then

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

Proof.routine

Uses. Proposition 3.2.14 (Invertible matrices preserve solution sets), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ ), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. The kernel is the solution set of a homogeneous system.

Hint 2. Apply Proposition 3.2.14 with

𝐲 = 𝟎

Sketch.

𝐱 \in ker 𝑇_{𝐺 𝐴}

means

(𝐺 𝐴) 𝐱 = 𝟎 = 𝐺 𝟎

, which by Proposition 3.2.14 is equivalent to

𝐴 𝐱 = 𝟎

. If

𝐴 \sim 𝐵

, then

𝐵 = 𝐺 𝐴

with

𝐺

a product of elementary matrices, which is invertible.

By Proposition 3.1.8,

ker 𝑇_{𝐴}

and

ker 𝑇_{𝐺 𝐴}

are the solution sets of

𝐴 𝐱 = 𝟎

and

(𝐺 𝐴) 𝐱 = 𝟎

. Since

𝐺 𝟎 = 𝟎

, these systems are equivalent by Proposition 3.2.14, so the kernels are equal. If

𝐴 \sim 𝐵

, then

𝐵 = 𝐺 𝐴

with

𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}

, which is invertible by Corollary 3.2.11. □

Example 3.2.24 (Telling matrices apart by their kernels). The matrices $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $(\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ are not row equivalent: the first sends $(𝑥_{1}, 𝑥_{2})$ to $(𝑥_{1}, 0)$ and the second to $(𝑥_{2}, 0)$ , so their kernels are $span (𝐞_{2})$ and $span (𝐞_{1})$ . On the other hand, $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) \sim (\begin{matrix} 0 & 0 \\ 3 & 0 \end{matrix})$ : swap the rows, then scale row $2$ by $3$ .

Similarly, a matrix $𝐴 \in 𝐹^{𝑚 \times 𝑚}$ with $𝐴 \sim 𝐼_{𝑚}$ is invertible: by symmetry (Proposition 3.2.22) $𝐼_{𝑚} \sim 𝐴$ , so $𝐴 = 𝐺 𝐼_{𝑚} = 𝐺$ for a product $𝐺$ of elementary matrices. The converse, that every invertible matrix is row equivalent to $𝐼_{𝑚}$ , is proved in Section 3.3 (Theorem 3.3.23); it gives Theorem 3.5.19 in Section 3.5.

Remark 3.2.25. The converse of Corollary 3.2.23 is also true: two

𝑚 \times 𝑛

matrices with the same kernel are row equivalent. The proof needs the reduced row echelon form of Section 3.3. Each matrix is row equivalent to its reduced row echelon form, and a matrix in reduced row echelon form turns out to be determined by its kernel together with its size. So the kernel is a complete invariant of row equivalence.

Exercise 3.2.26.routine Which of the following matrices are row equivalent to $𝐴 = (\begin{matrix} 1 & 2 \\ 2 & 4 \end{matrix})$ ?

(i) (\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix}), (ii) (\begin{matrix} 2 & 1 \\ 4 & 2 \end{matrix}), (iii) (\begin{matrix} 0 & 0 \\ 3 & 6 \end{matrix}) .

Solution.

Uses. Definition 3.2.21 (Row equivalence), Corollary 3.2.23 (Row equivalent matrices have the same kernel), Proposition 3.2.22 (Row equivalence is an equivalence relation)

Hint 1. Try to reach each matrix from

𝐴

by row operations. When that seems impossible, compare kernels.

Hint 2.

ker 𝑇_{𝐴} =

span ((2, - 1))

. What is the kernel of (ii)?

Sketch. (i) Add

- 2

times row

1

to row

2

. (iii) From (i), swap the rows and scale row

2

3

. (ii) is not: its kernel is

span ((1, - 2))

, while

ker 𝑇_{𝐴} =

span ((2, - 1))

(i) Yes: adding $- 2$ times row $1$ to row $2$ of $𝐴$ gives $(\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})$ .

(iii) Yes: from $(\begin{matrix} 1 & 2 \\ 0 & 0 \end{matrix})$ , swapping the rows gives $(\begin{matrix} 0 & 0 \\ 1 & 2 \end{matrix})$ , and scaling row $2$ by $3$ gives $(\begin{matrix} 0 & 0 \\ 3 & 6 \end{matrix})$ . By transitivity (Proposition 3.2.22), (iii) is row equivalent to $𝐴$ .

(ii) No. $𝐴 (𝑥_{1}, 𝑥_{2}) =$ $(𝑥_{1} + 2 𝑥_{2}, 2 (𝑥_{1} + 2 𝑥_{2}))$ , so $ker 𝑇_{𝐴} =$ ${𝐱 | 𝑥_{1} + 2 𝑥_{2} = 0} =$ $span ((2, - 1))$ . For the matrix in (ii), $𝐱 \mapsto$ $(2 𝑥_{1} + 𝑥_{2}, 2 (2 𝑥_{1} + 𝑥_{2}))$ , so its kernel is $span ((1, - 2))$ . These are different, since $(2, - 1)$ is not a multiple of $(1, - 2)$ , so the matrices are not row equivalent by Corollary 3.2.23.

3.2.5Column operations

The elementary column operations on a matrix with $𝑛$ columns are defined like the row operations: swap columns $𝑖$ and $𝑗$ ( $𝑖 \neq 𝑗$ ), scale column $𝑖$ by $𝑐 \neq 0$ , and add $𝑐$ times column $𝑗$ to column $𝑖$ ( $𝑖 \neq 𝑗$ ). Right multiplication recombines columns: by Definition 2.4.1 and Definition 2.3.8, column $𝑙$ of $𝐴 𝐻$ is

𝐴 𝐡_{𝑙} = ℎ_{1 𝑙} 𝐚_{1} + ℎ_{2 𝑙} 𝐚_{2} + \dots + ℎ_{𝑛 𝑙} 𝐚_{𝑛},

the combination of the columns of $𝐴$ with coefficients from column $𝑙$ of $𝐻$ . So we expect column operations to be right multiplications. They are, by the same elementary matrices, with the roles of the indices exchanged.

Rows and columns are exchanged by the transpose, so we can obtain this from Proposition 3.2.7 instead of proving it from scratch. The move is worth naming.

Technique 3.2.27 (Transpose to trade rows for columns). The transpose turns the rows of a matrix into the columns of $𝐴^{𝖳}$ , and it reverses products: ${(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳}$ (Proposition 2.4.23). So a statement about the rows of $𝐴$ , or about left multiplication, becomes a statement about the columns of $𝐴^{𝖳}$ , or about right multiplication, once everything is transposed. Prove whichever version is easier, and transpose to get the other.

Reach for it whenever you have a result about rows and need its mirror image about columns, or the other way around. The canonical example is Proposition 3.2.28, where column operations come from row operations. Later instances are the equality of row rank and column rank (Section 4.3) and $det 𝐴^{𝖳} = det 𝐴$ , which makes every column property of the determinant a row property too (Section 5.4).

Used in 15 places and 7 practice exercises

Exercise 2.5.45, Proposition 3.2.28, Exercise 3.2.46, Theorem 3.5.27, Exercise 3.6.8, Problem 3.2, Theorem 4.3.8, Corollary 4.3.10, Proposition 4.3.23, Exercise 4.3.29, Problem 4.2, Theorem 5.4.14, Corollary 5.4.15, Theorem 5.5.3, Problem 7.7; 7 practice exercises.

Proposition 3.2.28 (Column operations are right multiplications). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , let $1 \leq 𝑖, 𝑗 \leq 𝑛$ with $𝑖 \neq 𝑗$ , and let the elementary matrices below be $𝑛 \times 𝑛$ .

(a) $𝐴 𝐸_{𝑖 𝑗}$ is $𝐴$ with columns $𝑖$ and $𝑗$ swapped.
(b)If $𝑐 \neq 0$ , then $𝐴 𝐸_{𝑖 𝑐}$ is $𝐴$ with column $𝑖$ scaled by $𝑐$ .
(c) $𝐴 𝐸_{𝑖 𝑐 𝑗}$ is $𝐴$ with $𝑐$ times column $𝑗$ added to column $𝑖$ .

Proof (transpose).routine

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 2.4.23 (Transpose of a product), Definition 2.4.21 (Transpose)

Techniques. Transpose to trade rows for columns (Technique 3.2.27)

Hint 1. Compute

{(𝐴 𝐸)}^{𝖳}

with Proposition 2.4.23. What is

𝐸^{𝖳}

for each type?

Hint 2.

𝐸_{𝑖 𝑐 𝑗}

has its extra entry

𝑐

in position

(𝑗, 𝑖)

. Which elementary matrix has

𝑐

in position

(𝑖, 𝑗)

Sketch.

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

. Swaps and scalings are symmetric, and

𝐸_{𝑖 𝑐 𝑗}^{𝖳} =

𝐸_{𝑗 𝑐 𝑖}

. So

𝐸^{𝖳} 𝐴^{𝖳}

𝐴^{𝖳}

with a row operation performed, by Proposition 3.2.7; the rows of

𝐴^{𝖳}

are the columns of

𝐴

, and

𝐸_{𝑗 𝑐 𝑖}

adds

𝑐

times row

𝑗

to row

𝑖

. Transposing back gives the column statement.

By Proposition 2.4.23, ${(𝐴 𝐸)}^{𝖳} = 𝐸^{𝖳} 𝐴^{𝖳}$ , so $𝐴 𝐸 = {(𝐸^{𝖳} 𝐴^{𝖳})}^{𝖳}$ . Row $𝑘$ of $𝐴^{𝖳}$ is column $𝑘$ of $𝐴$ , written as a row (Definition 2.4.21).

(c) $𝐸_{𝑖 𝑐 𝑗}$ is $𝐼_{𝑛}$ with an extra entry $𝑐$ in position $(𝑗, 𝑖)$ , so $𝐸_{𝑖 𝑐 𝑗}^{𝖳}$ is $𝐼_{𝑛}$ with $𝑐$ in position $(𝑖, 𝑗)$ , which is $𝐸_{𝑗 𝑐 𝑖}$ . By Proposition 3.2.7, $𝐸_{𝑗 𝑐 𝑖} 𝐴^{𝖳}$ is $𝐴^{𝖳}$ with $𝑐$ times row $𝑗$ added to row $𝑖$ . Transposing turns rows into columns, so $𝐴 𝐸_{𝑖 𝑐 𝑗} =$ ${(𝐸_{𝑗 𝑐 𝑖} 𝐴^{𝖳})}^{𝖳}$ is $𝐴$ with $𝑐$ times column $𝑗$ added to column $𝑖$ .

(a), (b) $𝐸_{𝑖 𝑗}$ and $𝐸_{𝑖 𝑐}$ are symmetric: $𝐸_{𝑖 𝑗}^{𝖳} = 𝐸_{𝑖 𝑗}$ and $𝐸_{𝑖 𝑐}^{𝖳} = 𝐸_{𝑖 𝑐}$ . By Proposition 3.2.7, $𝐸_{𝑖 𝑗} 𝐴^{𝖳}$ and $𝐸_{𝑖 𝑐} 𝐴^{𝖳}$ are $𝐴^{𝖳}$ with rows $𝑖$ and $𝑗$ swapped, respectively with row $𝑖$ scaled by $𝑐$ , and transposing gives the claims. □

Proof (directly).routine

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

Hint 1. By Definition 2.4.1, column

𝑙

𝐴 𝐸

𝐴

times column

𝑙

𝐸

Hint 2. Find the columns of

𝐸_{𝑖 𝑐 𝑗}

. Which of them differs from a standard basis vector?

Sketch. Column

𝑙

𝐴 𝐸

𝐴

times column

𝑙

𝐸

. Column

𝑖

𝐸_{𝑖 𝑐 𝑗}

𝐞_{𝑖} + 𝑐 𝐞_{𝑗}

and the others are

𝐞_{𝑙}

, so column

𝑖

𝐴 𝐸_{𝑖 𝑐 𝑗}

𝐚_{𝑖} + 𝑐 𝐚_{𝑗}

and the others are unchanged. Columns

𝑖

and

𝑗

𝐸_{𝑖 𝑗}

are

𝐞_{𝑗}

and

𝐞_{𝑖}

, and column

𝑖

𝐸_{𝑖 𝑐}

𝑐 𝐞_{𝑖}

By Definition 2.4.1, column $𝑙$ of $𝐴 𝐸$ is $𝐴 𝐮_{𝑙}$ , where $𝐮_{𝑙}$ is column $𝑙$ of $𝐸$ , and $𝐴 𝐞_{𝑙} = 𝐚_{𝑙}$ by Definition 2.3.8.

(c) Column $𝑙$ of $𝐸_{𝑖 𝑐 𝑗}$ is $𝐞_{𝑙}$ for $𝑙 \neq 𝑖$ , and column $𝑖$ is $𝐞_{𝑖} + 𝑐 𝐞_{𝑗}$ , since the extra entry $𝑐$ is in row $𝑗$ of column $𝑖$ . So column $𝑙$ of $𝐴 𝐸_{𝑖 𝑐 𝑗}$ is $𝐚_{𝑙}$ for $𝑙 \neq 𝑖$ , and column $𝑖$ is $𝐴 (𝐞_{𝑖} + 𝑐 𝐞_{𝑗}) =$ $𝐚_{𝑖} +$ $𝑐 𝐚_{𝑗}$ .

(a), (b) Columns $𝑖$ and $𝑗$ of $𝐸_{𝑖 𝑗}$ are $𝐞_{𝑗}$ and $𝐞_{𝑖}$ , and column $𝑖$ of $𝐸_{𝑖 𝑐}$ is $𝑐 𝐞_{𝑖}$ ; all other columns are those of $𝐼_{𝑛}$ . So $𝐴 𝐸_{𝑖 𝑗}$ has columns $𝑖$ and $𝑗$ equal to $𝐚_{𝑗}$ and $𝐚_{𝑖}$ , and $𝐴 𝐸_{𝑖 𝑐}$ has column $𝑖$ equal to $𝑐 𝐚_{𝑖}$ , with the other columns unchanged. □

The direct proof is shorter here. The transposed proof shows that the column statement carries no new information: it is the row statement seen in a mirror.

Remark 3.2.29 (One matrix, two operations). The matrix $𝐸_{𝑖 𝑐 𝑗}$ , which has $𝑐$ in position $(𝑗, 𝑖)$ , is at once the result of adding $𝑐$ times row $𝑖$ to row $𝑗$ of the identity and the result of adding $𝑐$ times column $𝑗$ to column $𝑖$ of the identity. So the subscript $𝑖 𝑐 𝑗$ reads left to right for rows (“from row $𝑖$ into row $𝑗$ ”) and right to left for columns (“from column $𝑗$ into column $𝑖$ ”). For example, with $𝐴 = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix})$ ,

𝐴 𝐸_{1, - 2, 2} = (\begin{matrix} 1 - 4 & 2 & 3 \\ 4 - 10 & 5 & 6 \end{matrix}) = (\begin{matrix} - 3 & 2 & 3 \\ - 6 & 5 & 6 \end{matrix}),

where $𝐸_{1, - 2, 2}$ is $3 \times 3$ and adds $- 2$ times column $2$ to column $1$ . The $2 \times 2$ matrix with the same name acts on the left and adds $- 2$ times row $1$ to row $2$ : $𝐸_{1, - 2, 2} 𝐴 =$ $(\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 0 \end{matrix})$ . Also note the order of factors: if column operations with matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ are performed on $𝐴$ in that order, the result is $𝐴 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑘}$ , so the first operation is now the leftmost factor.

Row operations do not change the kernel (Corollary 3.2.23) but can change the image (Non-example 3.2.19). Column operations behave the other way around.

Proposition 3.2.30 (Column operations preserve the image). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, and let

𝐻 \in 𝐹^{𝑛 \times 𝑛}

be invertible. Then

im 𝑇_{𝐴 𝐻} = im 𝑇_{𝐴}

. In particular, column operations do not change the span of the columns of a matrix.

Proof.routine

Uses. Definition 2.6.6 (Image), Theorem 2.4.2 (The matrix of a composite), Definition 2.5.12 (Invertible), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.1.8 (Systems and the map $𝑇_{𝐴}$ )

Techniques. Double containment (Technique 1.3.14)

Hint 1. Prove the two containments separately.

Hint 2.

𝐴 𝐻 𝐱 = 𝐴 (𝐻 𝐱)

, and

𝐴 𝐱 =

(𝐴 𝐻) (𝐻^{- 1} 𝐱)

Sketch. Every

(𝐴 𝐻) 𝐱 = 𝐴 (𝐻 𝐱)

lies in

im 𝑇_{𝐴}

. Conversely

𝐴 𝐱 =

(𝐴 𝐻) (𝐻^{- 1} 𝐱) \in

im 𝑇_{𝐴 𝐻}

. Column operations multiply on the right by a product of elementary matrices, which is invertible.

We prove both containments, using $(𝐴 𝐻) 𝐱 = 𝐴 (𝐻 𝐱)$ (Theorem 2.4.2) throughout.

$im 𝑇_{𝐴 𝐻} \subseteq im 𝑇_{𝐴}$ . For $𝐱 \in 𝐹^{𝑛}$ , $(𝐴 𝐻) 𝐱 =$ $𝐴 (𝐻 𝐱) \in$ $im 𝑇_{𝐴}$ .

$im 𝑇_{𝐴} \subseteq im 𝑇_{𝐴 𝐻}$ . For $𝐱 \in 𝐹^{𝑛}$ , $𝐴 𝐱 =$ $𝐴 ((𝐻 𝐻^{- 1}) 𝐱) =$ $(𝐴 𝐻) (𝐻^{- 1} 𝐱) \in$ $im 𝑇_{𝐴 𝐻}$ .

A sequence of column operations multiplies $𝐴$ on the right by a product of elementary matrices (Proposition 3.2.28), which is invertible by Corollary 3.2.11, and $im 𝑇_{𝐴}$ is the span of the columns of $𝐴$ (Proposition 3.1.8). □

Non-example 3.2.31 (Column operations change the kernel). For

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

ker 𝑇_{𝐴} =

span ((1, - 1))

. Adding

- 1

times column

2

to column

1

gives

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

, whose kernel is

span ((1, 0))

. In general

ker 𝑇_{𝐴 𝐻} =

{𝐻^{- 1} 𝐱 | 𝐱 \in ker 𝑇_{𝐴}}

: the kernel is moved by

𝐻^{- 1}

This is why we solve systems with row operations. The solution set of a consistent system $𝐴 𝐱 = 𝐲$ is a translate of $ker 𝑇_{𝐴}$ (Proposition 3.1.19), and row operations keep the kernel and the solution set. Column operations keep the image, so they suit questions about the span of the columns, and both kinds together reduce every matrix to a very simple form, the rank normal form of Theorem 3.5.27.

Exercise 3.2.32.routine Let

𝐴 = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix})

. Find a

3 \times 3

elementary matrix

𝐸

with

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

. What does the same matrix

𝐸

do to a

3 \times 3

matrix

𝐵

when it multiplies on the left?

Solution.

Uses. Proposition 3.2.28 (Column operations are right multiplications), Proposition 3.2.7 (Row operations are left multiplications)

Hint 1. Which column changed, and by a multiple of which other column?

Hint 2. Adding

𝑐

times column

𝑗

to column

𝑖

is right multiplication by

𝐸_{𝑖 𝑐 𝑗}

Sketch. Column

2

became

(2, 5) - 2 (1, 4)

, so

𝐸 =

𝐸_{2, - 2, 1} =

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

. On the left,

𝐸_{2, - 2, 1} 𝐵

𝐵

with

- 2

times row

2

added to row

1

Only column $2$ changed, and $(0, - 3) =$ $(2, 5) -$ $2 (1, 4)$ . So $𝐴 𝐸$ is $𝐴$ with $- 2$ times column $1$ added to column $2$ , which by Proposition 3.2.28(c) (with $𝑖 = 2$ , $𝑗 = 1$ ) is $𝐴 𝐸_{2, - 2, 1}$ , where

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

By Proposition 3.2.7, $𝐸_{2, - 2, 1} 𝐵$ is $𝐵$ with $- 2$ times row $2$ added to row $1$ : the indices play the opposite roles.

3.2.6Elementary matrices in the plane

Over $ℝ$ , a $2 \times 2$ matrix $𝐸$ is a linear map $𝑇_{𝐸}$ of the plane, and we can watch what it does. Realize that a vector $𝐱 \in ℝ^{2}$ is itself a $2 \times 1$ matrix, so by Proposition 3.2.7, $𝐸 𝐱$ is $𝐱$ with the row operation of $𝐸$ performed on its two entries. The elementary $2 \times 2$ matrices are

𝐸_{12} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), 𝐸_{1 𝑐} = (\begin{matrix} 𝑐 & 0 \\ 0 & 1 \end{matrix}), 𝐸_{2 𝑐} = (\begin{matrix} 1 & 0 \\ 0 & 𝑐 \end{matrix}), 𝐸_{1 𝑐 2} = (\begin{matrix} 1 & 0 \\ 𝑐 & 1 \end{matrix}), 𝐸_{2 𝑐 1} = (\begin{matrix} 1 & 𝑐 \\ 0 & 1 \end{matrix}),

with $𝑐 \neq 0$ for the two scalings, and they act as follows.

Example 3.2.33 (The elementary maps of the plane).

Swap. $𝑇_{𝐸_{12}} (𝑥_{1}, 𝑥_{2}) =$ $(𝑥_{2}, 𝑥_{1})$ is the reflection across the line $𝑥_{1} = 𝑥_{2}$ . It fixes that line pointwise and reverses orientation: in Figure 3.2.1 the letter F is mirrored.
Scaling. $𝑇_{𝐸_{1 𝑐}} (𝑥_{1}, 𝑥_{2}) =$ $(𝑐 𝑥_{1}, 𝑥_{2})$ . For $𝑐 > 0$ it stretches the plane horizontally by the factor $𝑐$ (a compression if $𝑐 < 1$ ) and fixes the $𝑥_{2}$ -axis pointwise. For $𝑐 < 0$ it stretches by $| 𝑐 |$ and also reflects across the $𝑥_{2}$ -axis. $𝐸_{2 𝑐}$ does the same vertically.
Replacement. $𝑇_{𝐸_{2 𝑐 1}} (𝑥_{1}, 𝑥_{2}) =$ $(𝑥_{1} + 𝑐 𝑥_{2}, 𝑥_{2})$ is a horizontal shear. It slides each horizontal line $𝑥_{2} = 𝑡$ along itself by $𝑐 𝑡$ , so the $𝑥_{1}$ -axis is fixed pointwise, and the higher a point is, the farther it moves. The unit square becomes a parallelogram with the same base and the same height. $𝐸_{1 𝑐 2}$ is a vertical shear.

Figure 3.2.1. The three types of

2 \times 2

elementary matrices acting on the plane. Each panel shows the images of the grid, of the unit square, and of

𝐞_{1}

(blue) and

𝐞_{2}

(ochre). The reflection reverses orientation, so its image of the letter F is mirrored and its square is drawn in red.

The inverses of Proposition 3.2.10 are visible here: the shear by $𝑐$ is undone by the shear by $- 𝑐$ , the stretch by $𝑐$ by the stretch by $𝑐^{- 1}$ , and the reflection by itself.

The plane transformer, starting at the shear

𝐸_{2, 1, 1}

. Move

𝐴 𝐞_{2}

along the horizontal grid line

𝑥_{2} = 1

(focus it and use the left and right arrow keys): every position gives a shear

𝐸_{2 𝑐 1} = (\begin{matrix} 1 & 𝑐 \\ 0 & 1 \end{matrix})

. Move

𝐴 𝐞_{1}

along the

𝑥_{1}

-axis back and forth through

0

to see the scalings

𝐸_{1 𝑐}

, and how the square flattens at

𝑐 = 0

, which is why

𝑐 = 0

is excluded. For the swap, type the entries

0, 1, 1, 0

Example 3.2.34 (A rotation built from shears). The rotation of the plane by $90 °$ counterclockwise sends $𝐞_{1} \mapsto 𝐞_{2}$ and $𝐞_{2} \mapsto - 𝐞_{1}$ , so its matrix is $𝑅 = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ . It is not elementary, but it is a product of three shears. With $𝑆 =$ $𝐸_{2, - 1, 1} =$ $(\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix})$ and $𝐿 = 𝐸_{1, 1, 2} = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ ,

𝑆 𝐿 𝑆 = (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 0 & - 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix}) = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}) = 𝑅 .

Figure 3.2.2 shows the three steps: a horizontal shear, a vertical shear, and the first shear again. The same $𝑅$ is also a product of two reflections, $𝑅 = 𝐸_{1, - 1} 𝐸_{12}$ : first reflect across the line $𝑥_{1} = 𝑥_{2}$ , then across the $𝑥_{2}$ -axis. So a matrix can be written as a product of elementary matrices in several ways, and the number and types of the factors are not determined by the matrix.

Figure 3.2.2. The rotation by

90 °

as three shears,

𝑅 = 𝑆 𝐿 𝑆

. From left to right: the unit square and the letter F, then their images under

𝑆

, under

𝐿 𝑆

, and under

𝑆 𝐿 𝑆 = 𝑅

Intuition (Elementary maps as building blocks). Section 3.5 proves that every invertible matrix is a product of elementary matrices (Theorem 3.5.19). For the plane this says that every invertible linear map of

ℝ^{2}

is a composition of shears, stretches along the axes (possibly with a reflection), and the reflection across

𝑥_{1} = 𝑥_{2}

. The figures also show how each building block changes area. A shear keeps the area of the unit square. The stretch

𝐸_{1 𝑐}

multiplies it by

| 𝑐 |

. The swap keeps it but reverses orientation. Recorded with signs, these are the numbers

1

𝑐

, and

- 1

, which will be the determinants of the three types, and the determinant of any invertible matrix is then pinned down by its factorization into elementary matrices.

Remark 3.2.35 (Where elementary matrices reappear). Elementary matrices are bookkeeping for elimination, and they come back several times.

In Section 3.3, a run of Gauss–Jordan elimination on $𝐴$ is recorded by a product $𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}$ with $𝐺 𝐴 = rref (𝐴)$ (Theorem 3.3.10). By Proposition 3.2.14, the system $𝐴 𝐱 = 𝐲$ can then be solved in the form $rref (𝐴) 𝐱 = 𝐺 𝐲$ (Section 3.4).
In Section 3.5, every invertible matrix turns out to be a product of elementary matrices (Theorem 3.5.19). This yields a proof technique, reducing to elementary matrices (Technique 5.4.6): to prove a statement about all invertible matrices that is preserved under products, prove it for each of the three types.
In Section 5.4, that technique computes $det (𝐴 𝐸) =$ $det 𝐴 \cdot$ $det 𝐸$ type by type, and from it $det (𝐴 𝐵) =$ $det 𝐴 \cdot$ $det 𝐵$ (Theorem 5.4.10) and $det 𝐴^{𝖳} = det 𝐴$ (Theorem 5.4.14).

Exercises

Exercise 3.2.36.routine Which of the following matrices are elementary? For each one that is, name the row operation it performs and write down its inverse. All matrices are over $ℝ$ , except (h), which is over $𝔽_{3}$ .

\begin{matrix} (a) (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}), (b) (\begin{matrix} 1 & 0 \\ - 3 & 1 \end{matrix}), (c) (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (d) (\begin{matrix} 0 & 2 \\ 1 & 0 \end{matrix}), (e) (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}), \\ (f) (\begin{matrix} 1 & 0 & 4 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), (g) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}), (h) (\begin{matrix} 2 & 0 \\ 0 & 1 \end{matrix}), (i) (\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) . \end{matrix}

Solution.

Uses. Definition 3.2.2 (Elementary matrices), Proposition 3.2.10 (Inverses of elementary matrices)

Hint 1. Compare each matrix with the identity. In how many entries can an elementary matrix differ from

𝐼_{𝑚}

, and what do those entries look like?

Hint 2. A scaling differs from

𝐼_{𝑚}

in one diagonal entry, which is nonzero; a replacement in one off-diagonal entry; a swap in exactly four entries, which form the pattern

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

in rows and columns

𝑖, 𝑗

Sketch. Elementary: (a)

𝐼_{2}

; (b)

𝐸_{1, - 3, 2}

, inverse

𝐸_{1, 3, 2}

; (c)

𝐸_{12}

, its own inverse; (f)

𝐸_{3, 4, 1}

, inverse

𝐸_{3, - 4, 1}

; (h)

𝐸_{1, 2}

, its own inverse since

2 \cdot 2 = 1

𝔽_{3}

; (i)

𝐸_{23}

, its own inverse. Not elementary: (d), (e), (g).

From Definition 3.2.2: $𝐸_{𝑖 𝑐}$ differs from $𝐼_{𝑚}$ only in entry $(𝑖, 𝑖)$ , where it has $𝑐 \neq 0$ ; $𝐸_{𝑖 𝑐 𝑗}$ differs only in entry $(𝑗, 𝑖)$ , where it has $𝑐$ ; and $𝐸_{𝑖 𝑗}$ differs in exactly the entries $(𝑖, 𝑖),$ $(𝑗, 𝑗),$ $(𝑖, 𝑗),$ $(𝑗, 𝑖)$ , which are $0, 0, 1, 1$ . So a matrix is elementary exactly when it equals $𝐼_{𝑚}$ , or differs from $𝐼_{𝑚}$ in a single entry that is either off the diagonal or a nonzero diagonal entry, or differs from $𝐼_{𝑚}$ in exactly four entries forming a swap pattern. Inverses come from Proposition 3.2.10.

(a) Elementary: $𝐼_{2} = 𝐸_{1, 1}$ (scaling row $1$ by $1$ , or adding $0$ times row $1$ to row $2$ ). Its inverse is $𝐼_{2}$ .

(b) Elementary: the single extra entry $- 3$ is in position $(2, 1)$ , so this is $𝐸_{1, - 3, 2}$ , which adds $- 3$ times row $1$ to row $2$ . Its inverse is $𝐸_{1, 3, 2} = (\begin{matrix} 1 & 0 \\ 3 & 1 \end{matrix})$ .

(c) Elementary: $𝐸_{12}$ swaps the two rows, and it is its own inverse.

(d) Not elementary. It differs from $𝐼_{2}$ in all four entries, but it has the entry $2$ , which a swap does not. (It is $𝐸_{1, 2} 𝐸_{12}$ ; see Non-example 3.2.5.)

(e) Not elementary. It differs from $𝐼_{3}$ only in the diagonal entry $(3, 3)$ , which is $0$ , and scaling by $0$ is not allowed. (This matrix is not invertible: it sends $𝐞_{3}$ to $𝟎$ .)

(f) Elementary: the extra entry $4$ is in position $(1, 3)$ , that is, row $𝑗 = 1$ and column $𝑖 = 3$ . So this is $𝐸_{3, 4, 1}$ , which adds $4$ times row $3$ to row $1$ . Its inverse is $𝐸_{3, - 4, 1}$ .

(g) Not elementary: it differs from $𝐼_{2}$ in exactly two entries.

(h) Elementary: $𝐸_{1, 2}$ scales row $1$ by $2$ . In $𝔽_{3}$ , $2 \cdot 2 = 4 = 1$ , so $2^{- 1} = 2$ and $𝐸_{1, 2}$ is its own inverse.

(i) Elementary: $𝐸_{23}$ swaps rows $2$ and $3$ , and it is its own inverse.

Exercise 3.2.37.routine For each matrix $𝐴$ below, find elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ with $𝐸_{𝑘} \dots 𝐸_{1} 𝐴 = 𝐼_{2}$ , compute $𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}$ , and check that $𝐴 𝐺 = 𝐼_{2}$ as well.

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

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. Make the

(1, 1)

entry

1

, clear the entry below it, make the

(2, 2)

entry

1

, and clear the entry above it.

Hint 2. In

𝔽_{5}

2^{- 1} = 3

and

4^{- 1} = 4

. To compute

𝐺

, perform the same operations on

𝐼_{2}

Sketch. (a) Scale row

1

3

, add

- 1

times row

1

to row

2

, scale row

2

4

, add

- 2

times row

2

to row

1

;

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

. (b) Add

- 𝑖

times row

1

to row

2

, scale row

2

1 / 3

, add

- 𝑖

times row

2

to row

1

;

𝐺 = \frac{1}{3} (\begin{matrix} 2 & - 𝑖 \\ - 𝑖 & 1 \end{matrix})

(a) In $𝔽_{5}$ : scaling row $1$ by $2^{- 1} = 3$ gives $(\begin{matrix} 1 & 12 \\ 1 & 1 \end{matrix}) = (\begin{matrix} 1 & 2 \\ 1 & 1 \end{matrix})$ . Adding $- 1$ times row $1$ to row $2$ gives $(\begin{matrix} 1 & 2 \\ 0 & - 1 \end{matrix}) = (\begin{matrix} 1 & 2 \\ 0 & 4 \end{matrix})$ . Scaling row $2$ by $4^{- 1} = 4$ gives $(\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix})$ , and adding $- 2$ times row $2$ to row $1$ gives $𝐼_{2}$ . So

𝐺 = 𝐸_{2, - 2, 1} 𝐸_{2, 4} 𝐸_{1, - 1, 2} 𝐸_{1, 3} .

Performing the same four operations on $𝐼_{2}$ : $(\begin{matrix} 3 & 0 \\ 0 & 1 \end{matrix})$ , then $(\begin{matrix} 3 & 0 \\ - 3 & 1 \end{matrix}) = (\begin{matrix} 3 & 0 \\ 2 & 1 \end{matrix})$ , then $(\begin{matrix} 3 & 0 \\ 8 & 4 \end{matrix}) = (\begin{matrix} 3 & 0 \\ 3 & 4 \end{matrix})$ , then $(\begin{matrix} 3 - 6 & - 8 \\ 3 & 4 \end{matrix}) = (\begin{matrix} 2 & 2 \\ 3 & 4 \end{matrix})$ . So $𝐺 = (\begin{matrix} 2 & 2 \\ 3 & 4 \end{matrix})$ . Check:

𝐴 𝐺 = (\begin{matrix} 2 & 4 \\ 1 & 1 \end{matrix}) (\begin{matrix} 2 & 2 \\ 3 & 4 \end{matrix}) = (\begin{matrix} 16 & 20 \\ 5 & 6 \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) in 𝔽_{5} .

(b) Adding $- 𝑖$ times row $1$ to row $2$ gives $(\begin{matrix} 1 & 𝑖 \\ 0 & 2 - 𝑖^{2} \end{matrix}) =$ $(\begin{matrix} 1 & 𝑖 \\ 0 & 3 \end{matrix})$ . Scaling row $2$ by $1 / 3$ gives $(\begin{matrix} 1 & 𝑖 \\ 0 & 1 \end{matrix})$ , and adding $- 𝑖$ times row $2$ to row $1$ gives $𝐼_{2}$ . So $𝐺 =$ $𝐸_{2, - 𝑖, 1} 𝐸_{2, 1 / 3} 𝐸_{1, - 𝑖, 2}$ . Performing these operations on $𝐼_{2}$ : $(\begin{matrix} 1 & 0 \\ - 𝑖 & 1 \end{matrix})$ , then $(\begin{matrix} 1 & 0 \\ - 𝑖 / 3 & 1 / 3 \end{matrix})$ , then

𝐺 = (\begin{matrix} 1 - 𝑖 (- 𝑖 / 3) & - 𝑖 / 3 \\ - 𝑖 / 3 & 1 / 3 \end{matrix}) = \frac{1}{3} (\begin{matrix} 2 & - 𝑖 \\ - 𝑖 & 1 \end{matrix}),

using $1 + 𝑖^{2} / 3 = 2 / 3$ . Check:

𝐴 𝐺 = \frac{1}{3} (\begin{matrix} 1 & 𝑖 \\ 𝑖 & 2 \end{matrix}) (\begin{matrix} 2 & - 𝑖 \\ - 𝑖 & 1 \end{matrix}) = \frac{1}{3} (\begin{matrix} 2 - 𝑖^{2} & - 𝑖 + 𝑖 \\ 2 𝑖 - 2 𝑖 & - 𝑖^{2} + 2 \end{matrix}) = \frac{1}{3} (\begin{matrix} 3 & 0 \\ 0 & 3 \end{matrix}) = 𝐼_{2} .

In both cases $𝐺 𝐴 = 𝐼_{2} = 𝐴 𝐺$ , so $𝐺 = 𝐴^{- 1}$ . Computing inverses this way is the subject of Algorithm 3.3.24.

Exercise 3.2.38.routine Let

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

. Compute

𝐸_{1, 2, 3} 𝐴

and

𝐴 𝐸_{1, 2, 3}

and describe each in words. Then find the elementary matrix

𝐸

for which

𝐴 𝐸

𝐴

with

2

times column

1

added to column

3

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.28 (Column operations are right multiplications)

Hint 1. On the left,

𝐸_{1, 2, 3}

adds

2

times row

1

to row

3

. On the right, it adds

2

times column

3

to column

1

Hint 2. For the last part, read the subscript right to left: adding

𝑐

times column

𝑗

to column

𝑖

is right multiplication by

𝐸_{𝑖 𝑐 𝑗}

Sketch.

𝐸_{1, 2, 3} 𝐴 =

(\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 12 & 15 \end{matrix})

and

𝐴 𝐸_{1, 2, 3} =

(\begin{matrix} 7 & 2 & 3 \\ 16 & 5 & 6 \\ 25 & 8 & 9 \end{matrix})

. The last part needs

𝐸 = 𝐸_{3, 2, 1}

By Proposition 3.2.7, $𝐸_{1, 2, 3} 𝐴$ is $𝐴$ with $2$ times row $1$ added to row $3$ :

𝐸_{1, 2, 3} 𝐴 = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 + 2 & 8 + 4 & 9 + 6 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 12 & 15 \end{matrix}) .

By Proposition 3.2.28(c) with $𝑖 = 1$ , $𝑗 = 3$ , $𝐴 𝐸_{1, 2, 3}$ is $𝐴$ with $2$ times column $3$ added to column $1$ :

𝐴 𝐸_{1, 2, 3} = (\begin{matrix} 1 + 6 & 2 & 3 \\ 4 + 12 & 5 & 6 \\ 7 + 18 & 8 & 9 \end{matrix}) = (\begin{matrix} 7 & 2 & 3 \\ 16 & 5 & 6 \\ 25 & 8 & 9 \end{matrix}) .

Adding $2$ times column $1$ to column $3$ is Proposition 3.2.28(c) with $𝑖 = 3$ , $𝑗 = 1$ , so $𝐸 = 𝐸_{3, 2, 1}$ . Indeed $𝐴 𝐸_{3, 2, 1} =$ $(\begin{matrix} 1 & 2 & 5 \\ 4 & 5 & 14 \\ 7 & 8 & 23 \end{matrix})$ .

Exercise 3.2.39.routine Let $𝑖 \neq 𝑗$ and $𝑐, 𝑑 \in 𝐹$ .

(a)Show that $𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 𝑑 𝑗} =$ $𝐸_{𝑖 (𝑐 + 𝑑) 𝑗}$ and, for $𝑐, 𝑑 \neq 0$ , that $𝐸_{𝑖 𝑐} 𝐸_{𝑖 𝑑} =$ $𝐸_{𝑖 (𝑐 𝑑)}$ .
(b)Deduce that $𝐸_{𝑖 𝑐 𝑗}^{𝑘} =$ $𝐸_{𝑖 (𝑘 𝑐) 𝑗}$ for every positive integer $𝑘$ , and that $𝐸_{𝑖 𝑐 𝑗}^{𝑝} = 𝐼_{𝑚}$ when $𝐹 = 𝔽_{𝑝}$ .

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Definition 3.2.2 (Elementary matrices), induction on $𝑘$

Hint 1. By Proposition 3.2.7,

𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 𝑑 𝑗}

𝐸_{𝑖 𝑑 𝑗}

with

𝑐

times row

𝑖

added to row

𝑗

. What are rows

𝑖

and

𝑗

𝐸_{𝑖 𝑑 𝑗}

Hint 2. For (b), induct on

𝑘

. In

𝔽_{𝑝}

𝑝 𝑐 = 0

Sketch. Row

𝑖

𝐸_{𝑖 𝑑 𝑗}

is row

𝑖

𝐼_{𝑚}

, and row

𝑗

has

𝑑

in column

𝑖

; adding

𝑐

times row

𝑖

to row

𝑗

turns

𝑑

into

𝑐 + 𝑑

. Row

𝑖

𝐸_{𝑖 𝑑}

𝑑

times row

𝑖

𝐼_{𝑚}

, and scaling it by

𝑐

gives

𝑐 𝑑

. Then induction gives

𝐸_{𝑖 𝑐 𝑗}^{𝑘} =

𝐸_{𝑖 (𝑘 𝑐) 𝑗}

, and

𝐸_{𝑖 (𝑝 𝑐) 𝑗} =

𝐸_{𝑖, 0, 𝑗} =

𝐼_{𝑚}

𝔽_{𝑝}

(a) By Proposition 3.2.7, $𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 𝑑 𝑗}$ is $𝐸_{𝑖 𝑑 𝑗}$ with $𝑐$ times row $𝑖$ added to row $𝑗$ . As $𝑖 \neq 𝑗$ , row $𝑖$ of $𝐸_{𝑖 𝑑 𝑗}$ is row $𝑖$ of $𝐼_{𝑚}$ , with a $1$ in column $𝑖$ , and row $𝑗$ has $1$ in column $𝑗$ and $𝑑$ in column $𝑖$ . After the operation, row $𝑗$ has $1$ in column $𝑗$ and $𝑑 + 𝑐$ in column $𝑖$ , and the other rows are unchanged. That is the matrix $𝐸_{𝑖 (𝑐 + 𝑑) 𝑗}$ .

Similarly, $𝐸_{𝑖 𝑐} 𝐸_{𝑖 𝑑}$ is $𝐸_{𝑖 𝑑}$ with row $𝑖$ scaled by $𝑐$ . Row $𝑖$ of $𝐸_{𝑖 𝑑}$ has $𝑑$ in column $𝑖$ and zeros elsewhere, so the result has $𝑐 𝑑$ there, and it is $𝐸_{𝑖 (𝑐 𝑑)}$ (note $𝑐 𝑑 \neq 0$ ).

(b) For $𝑘 = 1$ the claim is clear. If $𝐸_{𝑖 𝑐 𝑗}^{𝑘} =$ $𝐸_{𝑖 (𝑘 𝑐) 𝑗}$ , then by (a),

𝐸_{𝑖 𝑐 𝑗}^{𝑘 + 1} = 𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 𝑐 𝑗}^{𝑘} = 𝐸_{𝑖 𝑐 𝑗} 𝐸_{𝑖 (𝑘 𝑐) 𝑗} = 𝐸_{𝑖 (𝑐 + 𝑘 𝑐) 𝑗} = 𝐸_{𝑖 ((𝑘 + 1) 𝑐) 𝑗} .

In $𝔽_{𝑝}$ we have $𝑝 𝑐 = 0$ , so $𝐸_{𝑖 𝑐 𝑗}^{𝑝} =$ $𝐸_{𝑖, 0, 𝑗} =$ $𝐼_{𝑚}$ . For example, over $𝔽_{2}$ every type 3 elementary matrix is its own inverse.

Exercise 3.2.40.standard Let $𝑚 = 3$ and $𝑐, 𝑑 \in 𝐹$ .

(a)Compute $𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2}$ and $𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3}$ , and explain the difference in terms of row operations.
(b)Show that $𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2} =$ $𝐸_{1 (𝑐 𝑑) 3} 𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3}$ .
(c)Show that $𝐸_{1 𝑐 2}$ commutes with $𝐸_{1 𝑑 3}$ and with $𝐸_{3 𝑑 2}$ .

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Definition 3.2.2 (Elementary matrices)

Hint 1. Compute each product by performing the operations on

𝐼_{3}

, the right factor first.

Hint 2. In

𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2}

, row

2

is changed first, and the changed row

2

is then added to row

3

Hint 3. For (c), track what each product does to the rows

𝐫_{1}, 𝐫_{2}, 𝐫_{3}

of an arbitrary

𝐴

. Does either operation change a row that the other one adds?

Sketch.

𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2} =

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

and

𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3} =

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

: adding

𝑑

times the new row

2

also adds

𝑐 𝑑

times row

1

to row

3

. For (b) and (c), compare the effects on rows

𝐫_{1}, 𝐫_{2}, 𝐫_{3}

of any

𝐴

Write $𝐫_{1}, 𝐫_{2}, 𝐫_{3}$ for the rows of a $3 \times 𝑛$ matrix $𝐴$ . By Proposition 3.2.7, a product $𝐸^{'} 𝐸 𝐴$ performs the operation of $𝐸$ first and then that of $𝐸^{'}$ .

(a) $𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2} 𝐴$ : first row $2$ becomes $𝐫_{2} + 𝑐 𝐫_{1}$ , then $𝑑$ times this new row $2$ is added to row $3$ . The rows become

𝐫_{1}, 𝐫_{2} + 𝑐 𝐫_{1}, 𝐫_{3} + 𝑑 𝐫_{2} + 𝑐 𝑑 𝐫_{1} .

$𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3} 𝐴$ : first row $3$ becomes $𝐫_{3} + 𝑑 𝐫_{2}$ , then row $2$ becomes $𝐫_{2} + 𝑐 𝐫_{1}$ . The rows become $𝐫_{1}$ , $𝐫_{2} + 𝑐 𝐫_{1}$ , $𝐫_{3} + 𝑑 𝐫_{2}$ . Taking $𝐴 = 𝐼_{3}$ ,

𝐸_{2 𝑑 3} 𝐸_{1 𝑐 2} = (\begin{matrix} 1 & 0 & 0 \\ 𝑐 & 1 & 0 \\ 𝑐 𝑑 & 𝑑 & 1 \end{matrix}), 𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3} = (\begin{matrix} 1 & 0 & 0 \\ 𝑐 & 1 & 0 \\ 0 & 𝑑 & 1 \end{matrix}) .

The products differ when $𝑐 𝑑 \neq 0$ . The difference is the extra $𝑐 𝑑 𝐫_{1}$ in row $3$ : in the first order, the row that is added to row $3$ has already absorbed $𝑐 𝐫_{1}$ .

(b) $𝐸_{1 (𝑐 𝑑) 3} 𝐸_{1 𝑐 2} 𝐸_{2 𝑑 3} 𝐴$ performs, in order: $𝐫_{3} \to 𝐫_{3} + 𝑑 𝐫_{2}$ ; $𝐫_{2} \to 𝐫_{2} + 𝑐 𝐫_{1}$ ; then adds $𝑐 𝑑 𝐫_{1}$ to row $3$ . The rows become $𝐫_{1}$ , $𝐫_{2} + 𝑐 𝐫_{1}$ , $𝐫_{3} + 𝑑 𝐫_{2} + 𝑐 𝑑 𝐫_{1}$ , the same as in the first computation of (a). Taking $𝐴 = 𝐼_{3}$ gives the identity.

(c) $𝐸_{1 𝑐 2}$ and $𝐸_{1 𝑑 3}$ both read only row $1$ , which neither changes, and they change different rows. In either order the rows of $𝐴$ become $𝐫_{1}$ , $𝐫_{2} + 𝑐 𝐫_{1}$ , $𝐫_{3} + 𝑑 𝐫_{1}$ . Likewise $𝐸_{1 𝑐 2}$ and $𝐸_{3 𝑑 2}$ both change only row $2$ and read rows $1$ and $3$ , which neither changes; in either order row $2$ becomes $𝐫_{2} + 𝑐 𝐫_{1} + 𝑑 𝐫_{3}$ . Taking $𝐴 = 𝐼_{3}$ , the matrices commute.

Exercise 3.2.41.standard Let $𝑖 \neq 𝑗$ .

(a)Show that $𝐸_{𝑖 𝑗} =$ $𝐸_{𝑖, - 1} 𝐸_{𝑖, 1, 𝑗} 𝐸_{𝑗, - 1, 𝑖} 𝐸_{𝑖, 1, 𝑗}$ . So a swap can be performed with three replacements and one scaling.
(b)Show that over $𝔽_{2}$ , $𝐸_{𝑖 𝑗}$ is a product of three elementary matrices of type 3.
(c)Deduce that every product of elementary matrices is a product of elementary matrices of types 2 and 3 only.

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Definition 3.2.2 (Elementary matrices)

Hint 1. Follow only rows

𝑖

and

𝑗

; call them

𝐮

and

𝐯

. The rightmost factor acts first.

Hint 2. The sequence is

(𝐮, 𝐯) \to

(𝐮, 𝐮 + 𝐯) \to

(- 𝐯, 𝐮 + 𝐯) \to

\dots

. In

𝔽_{2}

, what is

𝐸_{𝑖, - 1}

Sketch. Rows

𝑖, 𝑗

(𝐮, 𝐯) \to

(𝐮, 𝐮 + 𝐯) \to

(- 𝐯, 𝐮 + 𝐯) \to

(- 𝐯, 𝐮) \to

(𝐯, 𝐮)

. Over

𝔽_{2}

- 1 = 1

, so

𝐸_{𝑖, - 1} = 𝐼_{𝑚}

and

𝐸_{𝑖 𝑗} =

𝐸_{𝑖, 1, 𝑗} 𝐸_{𝑗, 1, 𝑖} 𝐸_{𝑖, 1, 𝑗}

. For (c), replace every swap by the product in (a).

(a) Let $𝐴$ be any matrix with $𝑚$ rows, and let $𝐮$ and $𝐯$ be its rows $𝑖$ and $𝑗$ . By Proposition 3.2.7, the product on the right performs four operations on $𝐴$ , starting with the rightmost factor. Only rows $𝑖$ and $𝑗$ change, as follows:

\begin{aligned} (𝐮, 𝐯) & \overset{𝐸_{𝑖, 1, 𝑗}}{\to} (𝐮, 𝐮 + 𝐯) \overset{𝐸_{𝑗, - 1, 𝑖}}{\to} (𝐮 - (𝐮 + 𝐯), 𝐮 + 𝐯) = (- 𝐯, 𝐮 + 𝐯) \\ \overset{𝐸_{𝑖, 1, 𝑗}}{\to} (- 𝐯, - 𝐯 + 𝐮 + 𝐯) = (- 𝐯, 𝐮) \overset{𝐸_{𝑖, - 1}}{\to} (𝐯, 𝐮) . \end{aligned}

So the product performs the swap of rows $𝑖$ and $𝑗$ on every $𝐴$ ; taking $𝐴 = 𝐼_{𝑚}$ shows that it equals $𝐸_{𝑖 𝑗}$ .

(b) In $𝔽_{2}$ , $- 1 = 1$ , so $𝐸_{𝑖, - 1} =$ $𝐸_{𝑖, 1} =$ $𝐼_{𝑚}$ and $𝐸_{𝑗, - 1, 𝑖} =$ $𝐸_{𝑗, 1, 𝑖}$ . By (a), $𝐸_{𝑖 𝑗} =$ $𝐸_{𝑖, 1, 𝑗} 𝐸_{𝑗, 1, 𝑖} 𝐸_{𝑖, 1, 𝑗}$ .

(c) In a product of elementary matrices, replace each factor $𝐸_{𝑖 𝑗}$ by the product in (a). The result is the same matrix, written with factors of types 2 and 3 only.

Exercise 3.2.42.standard For $𝐴 =$ $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) \in$ $𝐹^{2 \times 2}$ , let $𝐷 (𝐴) = 𝑎 𝑑 - 𝑏 𝑐$ .

(a)Show that $𝐷 (𝐸 𝐴) = 𝐷 (𝐴)$ for every $2 \times 2$ elementary matrix $𝐸$ of type 3, that $𝐷 (𝐸_{12} 𝐴) =$ $- 𝐷 (𝐴)$ , and that $𝐷 (𝐸_{𝑖 𝑠} 𝐴) =$ $𝑠 𝐷 (𝐴)$ for $𝑖 = 1, 2$ and $𝑠 \neq 0$ .
(b)Suppose $1 + 1 \neq 0$ in $𝐹$ . Show that $𝐸_{12}$ is not a product of elementary matrices of type 3. Why does this not contradict Exercise 3.2.41(b)?
(c)Is $𝐸_{1, 2} \in ℝ^{2 \times 2}$ a product of elementary matrices of type 3?

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Exercise 3.2.41

Hint 1. For (a), write out

𝐸 𝐴

for each type and expand

𝐷

Hint 2. For (b), compute

𝐷

of a product

𝐸_{𝑘} \dots 𝐸_{1}

of type 3 matrices by writing it as

𝐸_{𝑘} \dots 𝐸_{1} 𝐼_{2}

Sketch. Adding

𝑡

times row

1

to row

2

gives

𝑎 (𝑑 + 𝑡 𝑏) -

𝑏 (𝑐 + 𝑡 𝑎) =

𝑎 𝑑 -

𝑏 𝑐

, and similarly for row

2

into row

1

; swapping gives

𝑐 𝑏 - 𝑑 𝑎

; scaling a row by

𝑠

multiplies

𝐷

𝑠

. So a product

𝑃

of type 3 matrices has

𝐷 (𝑃) = 𝐷 (𝐼_{2}) = 1

, while

𝐷 (𝐸_{12}) = - 1 \neq 1

when

1 + 1 \neq 0

, and

𝐷 (𝐸_{1, 2}) = 2

(a) By Proposition 3.2.7, the type 3 matrices act as follows. Adding $𝑡$ times row $1$ to row $2$ gives $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 + 𝑡 𝑎 & 𝑑 + 𝑡 𝑏 \end{matrix})$ , and

𝑎 (𝑑 + 𝑡 𝑏) - 𝑏 (𝑐 + 𝑡 𝑎) = 𝑎 𝑑 - 𝑏 𝑐 .

Adding $𝑡$ times row $2$ to row $1$ gives $(\begin{matrix} 𝑎 + 𝑡 𝑐 & 𝑏 + 𝑡 𝑑 \\ 𝑐 & 𝑑 \end{matrix})$ , and $(𝑎 + 𝑡 𝑐) 𝑑 -$ $(𝑏 + 𝑡 𝑑) 𝑐 =$ $𝑎 𝑑 -$ $𝑏 𝑐$ . Swapping the rows gives $(\begin{matrix} 𝑐 & 𝑑 \\ 𝑎 & 𝑏 \end{matrix})$ , with $𝐷 =$ $𝑐 𝑏 -$ $𝑑 𝑎 =$ $- 𝐷 (𝐴)$ . Scaling row $1$ by $𝑠$ gives $𝐷 ((\begin{matrix} 𝑠 𝑎 & 𝑠 𝑏 \\ 𝑐 & 𝑑 \end{matrix})) =$ $𝑠 𝑎 𝑑 -$ $𝑠 𝑏 𝑐 =$ $𝑠 𝐷 (𝐴)$ , and scaling row $2$ by $𝑠$ gives $𝑎 (𝑠 𝑑) -$ $𝑏 (𝑠 𝑐) =$ $𝑠 𝐷 (𝐴)$ .

(b) Let $𝑃 = 𝐸_{𝑘} \dots 𝐸_{1}$ with each $𝐸_{𝑙}$ of type 3. Then $𝑃 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐼_{2}$ , and applying (a) $𝑘$ times, $𝐷 (𝑃) = 𝐷 (𝐼_{2}) = 1$ . But $𝐷 (𝐸_{12}) =$ $0 \cdot$ $0 -$ $1 \cdot$ $1 =$ $- 1$ , and $- 1 \neq 1$ because $1 + 1 \neq 0$ . So $𝐸_{12}$ is not such a product. Over $𝔽_{2}$ , $- 1 = 1$ and the invariant $𝐷$ gives no obstruction, in line with Exercise 3.2.41(b), where $𝐸_{12}$ was written as a product of three type 3 matrices.

(c) No: $𝐷 (𝐸_{1, 2}) = 2 \neq 1$ .

The number $𝐷 (𝐴)$ is the determinant of $𝐴$ (Theorem 5.1.13), and (a) is the $2 \times 2$ case of the rules computed in Section 5.4.

Exercise 3.2.43.routine Find the error in the following argument, and give a counterexample to its conclusion.

Claim. If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ is invertible, then $im 𝑇_{𝐺 𝐴} = im 𝑇_{𝐴}$ .

Proof. Let $𝐲 \in 𝐹^{𝑚}$ . By Proposition 3.2.14, the system $(𝐺 𝐴) 𝐱 = 𝐲$ has a solution if and only if $𝐴 𝐱 = 𝐲$ has one. So $𝐲 \in im 𝑇_{𝐺 𝐴}$ if and only if $𝐲 \in im 𝑇_{𝐴}$ .

Solution.

Uses. Proposition 3.2.14 (Invertible matrices preserve solution sets), Non-example 3.2.19 (Row operations move the column space)

Hint 1. Reread Proposition 3.2.14. Which right-hand side goes with

𝐺 𝐴

Hint 2. Try

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

and a single row operation.

Sketch. The proposition pairs

𝐴 𝐱 = 𝐲

with

(𝐺 𝐴) 𝐱 = 𝐺 𝐲

, not with

(𝐺 𝐴) 𝐱 = 𝐲

. What it shows is

𝐲 \in

im 𝑇_{𝐴} \Leftrightarrow

𝐺 𝐲 \in

im 𝑇_{𝐺 𝐴}

. Counterexample:

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

𝐺 = 𝐸_{1, - 1, 2}

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

Proposition 3.2.14 compares $𝐴 𝐱 = 𝐲$ with $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ : the right-hand side is multiplied by $𝐺$ too. The argument silently replaces $𝐺 𝐲$ by $𝐲$ . What the proposition does give is $𝐲 \in$ $im 𝑇_{𝐴} \Leftrightarrow$ $𝐺 𝐲 \in$ $im 𝑇_{𝐺 𝐴}$ , so $im 𝑇_{𝐺 𝐴} =$ ${𝐺 𝐲 | 𝐲 \in im 𝑇_{𝐴}}$ , which is usually a different subspace.

Counterexample: let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix}) \in ℝ^{2 \times 1}$ and $𝐺 = 𝐸_{1, - 1, 2}$ , so $𝐺 𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix})$ . Then $im 𝑇_{𝐴} =$ $span ((1, 1))$ and $im 𝑇_{𝐺 𝐴} =$ $span ((1, 0))$ , and $(1, 1)$ is not a multiple of $(1, 0)$ .

Exercise 3.2.44.standard Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ with $𝐴 \sim 𝐵$ . Prove or disprove each statement.

(a) $𝐴^{𝖳} \sim 𝐵^{𝖳}$ .
(b) $𝐴 𝐶 \sim 𝐵 𝐶$ for every $𝐶 \in 𝐹^{𝑛 \times 𝑝}$ .
(c) $𝐶 𝐴 \sim 𝐶 𝐵$ for every $𝐶 \in 𝐹^{𝑞 \times 𝑚}$ .
(d)If also $𝐶 \sim 𝐷$ in $𝐹^{𝑚 \times 𝑛}$ , then $𝐴 + 𝐶 \sim 𝐵 + 𝐷$ .
(e)If $𝑚 = 𝑛$ and $𝐴$ is invertible, then $𝐵$ is invertible.

Solution.

Uses. Definition 3.2.21 (Row equivalence), Corollary 3.2.23 (Row equivalent matrices have the same kernel), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. Write

𝐵 = 𝐺 𝐴

with

𝐺

a product of elementary matrices. Which statements follow from associativity alone?

Hint 2. To disprove, use kernels (Corollary 3.2.23). For (a) and (c), try

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

𝐴 = 𝐼_{2}

with

𝐵

obtained by a swap.

Sketch. (b) and (e) are true:

𝐵 𝐶 = 𝐺 (𝐴 𝐶)

, and

𝐵 = 𝐺 𝐴

is a product of invertible matrices. (a), (c), (d) are false:

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

but the transposes have kernels

span (𝐞_{2}) \neq

span (𝐞_{1})

; with

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

𝐶 𝐼_{2}

and

𝐶 𝐸_{12}

have different kernels;

𝐼_{2} + 𝐼_{2}

and

𝐸_{12} + 𝐼_{2}

have different kernels.

Throughout, $𝐵 = 𝐺 𝐴$ where $𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}$ is a product of elementary matrices.

(a) False. Let $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = 𝐸_{12} 𝐴 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ , so $𝐴 \sim 𝐵$ . Then $𝐴^{𝖳} = 𝐴$ has kernel $span (𝐞_{2})$ , while $𝐵^{𝖳} = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ sends $(𝑥_{1}, 𝑥_{2}) \mapsto (𝑥_{2}, 0)$ and has kernel $span (𝐞_{1})$ . By Corollary 3.2.23, $𝐴^{𝖳}$ and $𝐵^{𝖳}$ are not row equivalent.

(b) True. $𝐵 𝐶 =$ $(𝐺 𝐴) 𝐶 =$ $𝐺 (𝐴 𝐶) =$ $𝐸_{𝑘} \dots 𝐸_{1} (𝐴 𝐶)$ , so $𝐴 𝐶 \sim 𝐵 𝐶$ .

(c) False. Let $𝐴 = 𝐼_{2}$ , $𝐵 = 𝐸_{12}$ (so $𝐴 \sim 𝐵$ ), and $𝐶 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ . Then $𝐶 𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐶 𝐵 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , whose kernels are $span (𝐞_{2})$ and $span (𝐞_{1})$ , so $𝐶 𝐴$ and $𝐶 𝐵$ are not row equivalent.

(d) False. Let $𝐴 = 𝐶 = 𝐷 = 𝐼_{2}$ and $𝐵 = 𝐸_{12}$ . Then $𝐴 + 𝐶 = (\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix})$ and $𝐵 + 𝐷 = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ . The kernel of $𝐵 + 𝐷$ is $span ((1, - 1))$ . The kernel of $𝐴 + 𝐶$ is ${𝟎}$ if $1 + 1 \neq 0$ and all of $𝐹^{2}$ if $1 + 1 = 0$ ; either way it is not $span ((1, - 1))$ . So $𝐴 + 𝐶$ and $𝐵 + 𝐷$ are not row equivalent.

(e) True. $𝐺$ is invertible by Corollary 3.2.11, so $𝐵 = 𝐺 𝐴$ is a product of invertible matrices, which is invertible with inverse $𝐴^{- 1} 𝐺^{- 1}$ .

Exercise 3.2.45.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ , and let $𝐺 \in 𝐹^{𝑝 \times 𝑚}$ , where $𝑝$ need not equal $𝑚$ .

(a)Suppose $𝐺$ has a left inverse, that is, $𝐻 𝐺 = 𝐼_{𝑚}$ for some $𝐻 \in 𝐹^{𝑚 \times 𝑝}$ . Show that $𝐴 𝐱 = 𝐲$ and $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ have the same solutions.
(b)Give an example with $𝑚 = 2$ and $𝑝 = 3$ , and interpret it as an operation on the equations of a system.
(c)Conversely, suppose that for every $𝐴 \in 𝐹^{𝑚 \times 1}$ and every $𝐲 \in 𝐹^{𝑚}$ the systems $𝐴 𝐱 = 𝐲$ and $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ have the same solutions. Show that $𝑇_{𝐺}$ is injective.

Solution.

Uses. Proposition 3.2.14 (Invertible matrices preserve solution sets), Definition 2.5.1 (Left inverse), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Theorem 2.7.2 (First Fundamental Theorem)

Hint 1. Rerun the proof of Proposition 3.2.14. Where exactly was

𝐺^{- 1}

used?

Hint 2. For (b), let the third row of

𝐺

produce the sum of the two equations.

Hint 3. For (c), suppose

𝐺 𝐳 = 𝟎

. Choose

𝐴 = 0

and

𝐲 = 𝐳

and compare the two solution sets.

Sketch. (a)

\Rightarrow

is multiplication by

𝐺

;

\Leftarrow

multiplies by

𝐻

𝐴 𝐱 =

𝐻 𝐺 𝐴 𝐱 =

𝐻 𝐺 𝐲 =

𝐲

. (b)

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

appends the sum of the two equations;

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

. (c) If

𝐺 𝐳 = 𝟎

, then with

𝐴 = 0

𝐲 = 𝐳

, every

𝑥

solves the second system, hence the first, so

𝐳 = 𝟎

(a) If $𝐴 𝐱 = 𝐲$ , then $(𝐺 𝐴) 𝐱 =$ $𝐺 (𝐴 𝐱) =$ $𝐺 𝐲$ . Conversely, if $(𝐺 𝐴) 𝐱 = 𝐺 𝐲$ , multiplying on the left by $𝐻$ gives

𝐴 𝐱 = (𝐻 𝐺) 𝐴 𝐱 = 𝐻 ((𝐺 𝐴) 𝐱) = 𝐻 (𝐺 𝐲) = (𝐻 𝐺) 𝐲 = 𝐲 .

Only the left inverse was used.

(b) Let $𝐺 = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{matrix})$ and $𝐻 = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ . Then $𝐻 𝐺 = 𝐼_{2}$ . For a system of two equations with augmented matrix $(𝐴 | 𝐲)$ , the matrix $𝐺 (𝐴 | 𝐲) =$ $(𝐺 𝐴 | 𝐺 𝐲)$ consists of the two original equations followed by their sum. By (a), appending this redundant equation does not change the solution set. ( $𝐺$ is not square, so it is not invertible.)

(c) By Theorem 2.6.11 it suffices to show $ker 𝑇_{𝐺} = {𝟎}$ . Let $𝐳 \in 𝐹^{𝑚}$ with $𝐺 𝐳 = 𝟎$ . Take $𝐴 = 0 \in 𝐹^{𝑚 \times 1}$ and $𝐲 = 𝐳$ . For every $𝑥 \in 𝐹 = 𝐹^{1}$ , $(𝐺 𝐴) 𝑥 =$ $𝟎 =$ $𝐺 𝐳 =$ $𝐺 𝐲$ , so every $𝑥$ solves the second system. By hypothesis every $𝑥$ then solves the first system, so $𝟎 = 𝐴 𝑥 = 𝐲 = 𝐳$ . Hence $ker 𝑇_{𝐺} = {𝟎}$ , and $𝑇_{𝐺}$ is injective.

By Theorem 2.7.2, an injective $𝑇_{𝐺}$ has a left inverse. So (a) and (c) together say: multiplying systems by $𝐺$ always preserves solution sets exactly when $𝐺$ has a left inverse.

Exercise 3.2.46.standard The row space of

𝐴 \in 𝐹^{𝑚 \times 𝑛}

is the span of its rows, viewed as vectors in

𝐹^{𝑛}

; equivalently, it is

im 𝑇_{𝐴^{𝖳}}

. Show that row equivalent matrices have the same row space.

Solution (transpose).

Uses. Proposition 3.2.30 (Column operations preserve the image), Proposition 2.4.23 (Transpose of a product), Corollary 3.2.11 (Products of elementary matrices), Definition 2.5.12 (Invertible)

Techniques. Transpose to trade rows for columns (Technique 3.2.27), Double containment (Technique 1.3.14)

Hint 1. If

𝐵 = 𝐺 𝐴

, then

𝐵^{𝖳} = 𝐴^{𝖳} 𝐺^{𝖳}

. Which result about right multiplication applies?

Hint 2. You need

𝐺^{𝖳}

to be invertible. Transpose the equations

𝐺 𝐺^{- 1} =

𝐺^{- 1} 𝐺 =

𝐼_{𝑚}

Sketch.

𝐵^{𝖳} = 𝐴^{𝖳} 𝐺^{𝖳}

, and

𝐺^{𝖳}

is invertible with inverse

{(𝐺^{- 1})}^{𝖳}

. By Proposition 3.2.30,

im 𝑇_{𝐵^{𝖳}} = im 𝑇_{𝐴^{𝖳}}

Let

𝐴 \sim 𝐵

, so

𝐵 = 𝐺 𝐴

with

𝐺

a product of elementary matrices, invertible by Corollary 3.2.11. By Proposition 2.4.23,

𝐵^{𝖳} = 𝐴^{𝖳} 𝐺^{𝖳}

. Transposing

𝐺 𝐺^{- 1} = 𝐼_{𝑚}

and

𝐺^{- 1} 𝐺 = 𝐼_{𝑚}

gives

{(𝐺^{- 1})}^{𝖳} 𝐺^{𝖳} = 𝐼_{𝑚}

and

𝐺^{𝖳} {(𝐺^{- 1})}^{𝖳} = 𝐼_{𝑚}

(as

𝐼_{𝑚}^{𝖳} = 𝐼_{𝑚}

), so

𝐺^{𝖳}

is invertible. By Proposition 3.2.30,

im 𝑇_{𝐵^{𝖳}} =

im 𝑇_{𝐴^{𝖳} 𝐺^{𝖳}} =

im 𝑇_{𝐴^{𝖳}}

Solution (rows directly).

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.22 (Row equivalence is an equivalence relation), Proposition 1.4.14 (The span is the smallest subspace containing a list)

Techniques. Transpose to trade rows for columns (Technique 3.2.27), Double containment (Technique 1.3.14)

Hint 1. It suffices to treat a single row operation, then use symmetry.

Hint 2. Each row of

𝐸 𝐴

is a combination of rows of

𝐴

, so it lies in the row space of

𝐴

Sketch. Every row of

𝐸 𝐴

is a row of

𝐴

or a combination of two rows of

𝐴

, so the row space of

𝐸 𝐴

is contained in that of

𝐴

. Since

𝐴

is obtained back from

𝐸 𝐴

by an elementary operation, the reverse containment holds as well; then induct on the number of operations.

Write

𝑅 (𝐴)

for the row space. First let

𝐸

be elementary. By Proposition 3.2.7, every row of

𝐸 𝐴

is a row of

𝐴

, a nonzero multiple of a row of

𝐴

, or a row of

𝐴

plus a multiple of another row of

𝐴

. So every row of

𝐸 𝐴

lies in

𝑅 (𝐴)

, and since

𝑅 (𝐴)

is a subspace,

𝑅 (𝐸 𝐴) \subseteq 𝑅 (𝐴)

(Proposition 1.4.14). Also

𝐴 = 𝐸^{- 1} (𝐸 𝐴)

with

𝐸^{- 1}

elementary, so the same argument gives

𝑅 (𝐴) \subseteq 𝑅 (𝐸 𝐴)

. Hence

𝑅 (𝐸 𝐴) = 𝑅 (𝐴)

. If

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

, applying this

𝑘

times gives

𝑅 (𝐵) = 𝑅 (𝐴)

Exercise 3.2.47.standard

(a)Show that two $1 \times 𝑛$ matrices are row equivalent if and only if one is a nonzero scalar multiple of the other.
(b)Find all $𝐵 \in ℝ^{2 \times 2}$ with $𝐵 \sim (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$ .

Solution.

Uses. Definition 3.2.21 (Row equivalence), Definition 3.2.1 (Elementary row operations), Definition 2.4.1 (Matrix product), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. With only one row, which elementary row operations are available?

Hint 2. For (b), if

𝐵 = 𝐺 𝐴

, then the columns of

𝐵

are

𝐺

times the columns of

𝐴

. What do you learn about the two columns of

𝐵

Sketch. (a) A matrix with one row admits only scalings, and a sequence of them multiplies by a nonzero scalar. (b)

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

has both columns equal to

𝐺 𝐞_{1} \neq 𝟎

, so

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

with

(𝑎, 𝑏) \neq (0, 0)

; conversely each such

𝐵

is reached by a scaling and a replacement, or a swap and a scaling.

(a) Swaps and replacements need two different rows, so the only elementary row operations on a $1 \times 𝑛$ matrix are scalings by nonzero scalars. A sequence of them multiplies the matrix by the product of the scalars, which is nonzero. So $𝐴 \sim 𝐵$ implies $𝐵 = 𝑠 𝐴$ with $𝑠 \neq 0$ ; conversely, if $𝐵 = 𝑠 𝐴$ with $𝑠 \neq 0$ , scaling the row by $𝑠$ turns $𝐴$ into $𝐵$ .

(b) Let $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix})$ . We claim that $𝐵 \sim 𝐴$ if and only if $𝐵 = (\begin{matrix} 𝑎 & 𝑎 \\ 𝑏 & 𝑏 \end{matrix})$ with $(𝑎, 𝑏) \neq (0, 0)$ .

Suppose $𝐵 \sim 𝐴$ , and write $𝐵 = 𝐺 𝐴$ with $𝐺$ a product of elementary matrices. By Definition 2.4.1, both columns of $𝐵$ equal $𝐺 𝐞_{1}$ . This vector is nonzero, because $𝐺$ is invertible (Corollary 3.2.11) and so $𝐺 𝐞_{1} = 𝟎$ would give $𝐞_{1} = 𝐺^{- 1} 𝟎 = 𝟎$ . So $𝐵 = (\begin{matrix} 𝑎 & 𝑎 \\ 𝑏 & 𝑏 \end{matrix})$ with $(𝑎, 𝑏) =$ $𝐺 𝐞_{1} \neq$ $(0, 0)$ .

Conversely, let $(𝑎, 𝑏) \neq (0, 0)$ . If $𝑎 \neq 0$ , scale row $1$ of $𝐴$ by $𝑎$ to get $(\begin{matrix} 𝑎 & 𝑎 \\ 0 & 0 \end{matrix})$ , then add $𝑏 / 𝑎$ times row $1$ to row $2$ to get $(\begin{matrix} 𝑎 & 𝑎 \\ 𝑏 & 𝑏 \end{matrix})$ . If $𝑎 = 0$ , then $𝑏 \neq 0$ ; swap the rows of $𝐴$ to get $(\begin{matrix} 0 & 0 \\ 1 & 1 \end{matrix})$ , then scale row $2$ by $𝑏$ .

Exercise 3.2.48.standard Let

𝑝

be a prime and

𝑚 \geq 1

. How many different matrices in

𝔽_{𝑝}^{𝑚 \times 𝑚}

are elementary? List them for

𝑝 = 2

and

𝑚 = 2

Solution.

Uses. Definition 3.2.2 (Elementary matrices)

Hint 1. Count each type, but watch for coincidences. Which choices of

𝑐

give

𝐼_{𝑚}

? Can a matrix of one type equal a matrix of another type?

Hint 2. Compare the diagonal entries: a swap has two diagonal entries

0

, a scaling other than

𝐼_{𝑚}

is diagonal, and a replacement other than

𝐼_{𝑚}

has a nonzero off-diagonal entry and all diagonal entries

1

Sketch. Apart from

𝐼_{𝑚}

, the types are disjoint. There are

(\binom{𝑚}{2})

swaps (as

𝐸_{𝑖 𝑗} = 𝐸_{𝑗 𝑖}

𝑚 (𝑝 - 2)

scalings with

𝑐 \notin {0, 1}

, and

𝑚 (𝑚 - 1) (𝑝 - 1)

replacements with

𝑐 \neq 0

. Total

1 +

(\binom{𝑚}{2}) +

𝑚 (𝑝 - 2) +

𝑚 (𝑚 - 1) (𝑝 - 1)

; for

𝑝 = 𝑚 = 2

this is

4

𝐼_{2}

𝐸_{12}

𝐸_{1, 1, 2}

𝐸_{2, 1, 1}

The identity is elementary ( $𝐼_{𝑚} = 𝐸_{1, 1}$ ). We count the elementary matrices other than $𝐼_{𝑚}$ .

Swaps. $𝐸_{𝑖 𝑗}$ has diagonal entries $0$ in positions $𝑖$ and $𝑗$ . Since $𝐸_{𝑖 𝑗} = 𝐸_{𝑗 𝑖}$ and different pairs ${𝑖, 𝑗}$ give different matrices, there are $(\binom{𝑚}{2}) = 𝑚 (𝑚 - 1) / 2$ of them.

Scalings other than $𝐼_{𝑚}$ . $𝐸_{𝑖 𝑐}$ with $𝑐 \notin {0, 1}$ is diagonal and differs from $𝐼_{𝑚}$ exactly in position $(𝑖, 𝑖)$ , where it has $𝑐$ . Different pairs $(𝑖, 𝑐)$ give different matrices, so there are $𝑚 (𝑝 - 2)$ of them.

Replacements other than $𝐼_{𝑚}$ . $𝐸_{𝑖 𝑐 𝑗}$ with $𝑐 \neq 0$ has all diagonal entries $1$ and a single nonzero off-diagonal entry $𝑐$ in position $(𝑗, 𝑖)$ . Different triples $(𝑖, 𝑐, 𝑗)$ give different matrices, so there are $𝑚 (𝑚 - 1) (𝑝 - 1)$ of them.

No matrix lies in two of these groups: swaps have zero diagonal entries, scalings other than $𝐼_{𝑚}$ are diagonal with a diagonal entry different from $1$ , and replacements other than $𝐼_{𝑚}$ are not diagonal but have all diagonal entries $1$ . So the number of elementary matrices in $𝔽_{𝑝}^{𝑚 \times 𝑚}$ is

1 + 𝑚 \frac{𝑚 - 1}{2} + 𝑚 (𝑝 - 2) + 𝑚 (𝑚 - 1) (𝑝 - 1) .

For $𝑝 = 2$ , $𝑚 = 2$ this is $1 + 1 + 0 + 2 = 4$ :

𝐼_{2}, 𝐸_{12} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), 𝐸_{1, 1, 2} = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}), 𝐸_{2, 1, 1} = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}) .

Exercise 3.2.49.standard Let $𝑅_{𝜃} =$ $(\begin{matrix} cos 𝜃 & - sin 𝜃 \\ sin 𝜃 & cos 𝜃 \end{matrix})$ be the rotation of $ℝ^{2}$ by $𝜃$ , and for $𝑡 \in ℝ$ let $𝑆 (𝑡) =$ $𝐸_{2 𝑡 1} =$ $(\begin{matrix} 1 & 𝑡 \\ 0 & 1 \end{matrix})$ and $𝐿 (𝑡) =$ $𝐸_{1 𝑡 2} =$ $(\begin{matrix} 1 & 0 \\ 𝑡 & 1 \end{matrix})$ .

(a)Show that if $𝜃$ is not an odd multiple of $𝜋$ , then $𝑅_{𝜃} =$ $𝑆 (- tan (𝜃 / 2)) 𝐿 (sin 𝜃) 𝑆 (- tan (𝜃 / 2))$ .
(b)Write $𝑅_{𝜋} = - 𝐼_{2}$ as a product of five shears.

Solution.

Uses. Example 3.2.34 (A rotation built from shears)

Hint 1. Multiply out with

𝑡 = tan (𝜃 / 2)

and

𝑠 = sin 𝜃

, and simplify

𝑡 𝑠

with the double-angle formulas.

Hint 2.

𝑡 𝑠 =

2 {sin}^{2} (𝜃 / 2) =

1 -

cos 𝜃

. For (b), use

𝑅_{𝜋} = 𝑅_{𝜋 / 2}^{2}

and Example 3.2.34.

Sketch. With

𝑡 = tan (𝜃 / 2)

𝑠 = sin 𝜃

, the product is

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

. Since

𝑡 𝑠 = 1 - cos 𝜃

, the diagonal entries are

cos 𝜃

and the top right entry is

- 𝑡 (1 + cos 𝜃) =

- sin 𝜃

. For (b),

{(𝑆 (- 1) 𝐿 (1) 𝑆 (- 1))}^{2} =

𝑆 (- 1) 𝐿 (1) 𝑆 (- 2) 𝐿 (1) 𝑆 (- 1)

(a) Let $𝑡 = tan (𝜃 / 2)$ , which is defined because $𝜃 / 2$ is not an odd multiple of $𝜋 / 2$ , and $𝑠 = sin 𝜃$ . Then

𝑆 (- 𝑡) 𝐿 (𝑠) = (\begin{matrix} 1 & - 𝑡 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & 0 \\ 𝑠 & 1 \end{matrix}) = (\begin{matrix} 1 - 𝑡 𝑠 & - 𝑡 \\ 𝑠 & 1 \end{matrix}), 𝑆 (- 𝑡) 𝐿 (𝑠) 𝑆 (- 𝑡) = (\begin{matrix} 1 - 𝑡 𝑠 & - 𝑡 (1 - 𝑡 𝑠) - 𝑡 \\ 𝑠 & 1 - 𝑡 𝑠 \end{matrix}) .

By the double-angle formulas, $𝑡 𝑠 =$ $(sin (𝜃 / 2) / cos (𝜃 / 2)) \cdot$ $2 sin (𝜃 / 2) cos (𝜃 / 2) =$ $2 {sin}^{2} (𝜃 / 2) =$ $1 -$ $cos 𝜃$ . So $1 - 𝑡 𝑠 = cos 𝜃$ , and the top right entry is

- 𝑡 (cos 𝜃 + 1) = - \frac{sin (𝜃 / 2)}{cos (𝜃 / 2)} \cdot 2 {cos}^{2} (𝜃 / 2) = - 2 sin (𝜃 / 2) cos (𝜃 / 2) = - sin 𝜃 .

Hence the product is $𝑅_{𝜃}$ , as desired. For $𝜃 = 𝜋 / 2$ this is the factorization $𝑅 = 𝑆 𝐿 𝑆$ of Example 3.2.34.

(b) $𝑅_{𝜋} = 𝑅_{𝜋 / 2} 𝑅_{𝜋 / 2}$ , and by Example 3.2.34 $𝑅_{𝜋 / 2} =$ $𝑆 (- 1) 𝐿 (1) 𝑆 (- 1)$ . So

- 𝐼_{2} = 𝑆 (- 1) 𝐿 (1) 𝑆 (- 1) 𝑆 (- 1) 𝐿 (1) 𝑆 (- 1) = 𝑆 (- 1) 𝐿 (1) 𝑆 (- 2) 𝐿 (1) 𝑆 (- 1),

using $𝑆 (- 1) 𝑆 (- 1) =$ $𝑆 (- 2)$ (Exercise 3.2.39). (The formula in (a) is how images are rotated in software that can only shift pixels along rows and columns: each shear moves every row, or every column, by a fixed amount.)

Exercise 3.2.50.standard

(a)Let $𝐴 =$ $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) \in$ $𝐹^{2 \times 2}$ with $𝑎 𝑑 - 𝑏 𝑐 \neq 0$ . Find elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ with $𝐸_{𝑘} \dots 𝐸_{1} 𝐴 = 𝐼_{2}$ , and conclude that $𝐴$ is a product of elementary matrices.
(b)Carry this out for $𝐴 = (\begin{matrix} 0 & 1 \\ - 2 & 3 \end{matrix}) \in ℝ^{2 \times 2}$ , and describe $𝑇_{𝐴}$ as a composition of shears, stretches, and reflections.

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.10 (Inverses of elementary matrices), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. If

𝑎 \neq 0

: scale row

1

𝑎^{- 1}

, clear the

(2, 1)

entry, and check that the new

(2, 2)

entry is

(𝑎 𝑑 - 𝑏 𝑐) / 𝑎

. If

𝑎 = 0

, swap first.

Hint 2. From

𝐸_{𝑘} \dots 𝐸_{1} 𝐴 = 𝐼_{2}

, multiply on the left by

𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}

Sketch. If

𝑎 \neq 0

𝐸_{1 𝑎^{- 1}}

, then

𝐸_{1 (- 𝑐) 2}

, giving

(\begin{matrix} 1 & 𝑏 / 𝑎 \\ 0 & (𝑎 𝑑 - 𝑏 𝑐) / 𝑎 \end{matrix})

; then scale row

2

𝑎 / (𝑎 𝑑 - 𝑏 𝑐)

and add

- 𝑏 / 𝑎

times row

2

to row

1

. If

𝑎 = 0

then

𝑐 \neq 0

; swap first. Then

𝐴 = 𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}

. For

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

𝐴 =

𝐸_{12} 𝐸_{1, - 2} 𝐸_{2, - 3 / 2, 1}

(a) Case $𝑎 \neq 0$ . Scaling row $1$ by $𝑎^{- 1}$ gives $(\begin{matrix} 1 & 𝑏 / 𝑎 \\ 𝑐 & 𝑑 \end{matrix})$ . Adding $- 𝑐$ times row $1$ to row $2$ gives

(\begin{matrix} 1 & 𝑏 / 𝑎 \\ 0 & 𝑑 - 𝑐 𝑏 / 𝑎 \end{matrix}) = (\begin{matrix} 1 & 𝑏 / 𝑎 \\ 0 & (𝑎 𝑑 - 𝑏 𝑐) / 𝑎 \end{matrix}) .

The $(2, 2)$ entry $𝛿 = (𝑎 𝑑 - 𝑏 𝑐) / 𝑎$ is nonzero. Scaling row $2$ by $𝛿^{- 1}$ gives $(\begin{matrix} 1 & 𝑏 / 𝑎 \\ 0 & 1 \end{matrix})$ , and adding $- 𝑏 / 𝑎$ times row $2$ to row $1$ gives $𝐼_{2}$ . With

𝐸_{1} = 𝐸_{1 𝑎^{- 1}}, 𝐸_{2} = 𝐸_{1 (- 𝑐) 2}, 𝐸_{3} = 𝐸_{2 𝛿^{- 1}}, 𝐸_{4} = 𝐸_{2 (- 𝑏 / 𝑎) 1},

Proposition 3.2.7 gives $𝐸_{4} 𝐸_{3} 𝐸_{2} 𝐸_{1} 𝐴 =$ $𝐼_{2}$ .

Case $𝑎 = 0$ . Then $- 𝑏 𝑐 = 𝑎 𝑑 - 𝑏 𝑐 \neq 0$ , so $𝑐 \neq 0$ . Swapping the rows gives $(\begin{matrix} 𝑐 & 𝑑 \\ 0 & 𝑏 \end{matrix})$ , whose $(1, 1)$ entry is nonzero and whose value of “ $𝑎 𝑑 - 𝑏 𝑐$ ” is $𝑐 𝑏 - 𝑑 \cdot 0 = 𝑐 𝑏 \neq 0$ . Apply the first case to it.

In either case $𝐸_{𝑘} \dots 𝐸_{1} 𝐴 = 𝐼_{2}$ . Multiplying on the left by $𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}$ , which is the inverse of $𝐸_{𝑘} \dots 𝐸_{1}$ (Corollary 3.2.11), gives $𝐴 = 𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}$ , and each $𝐸_{𝑙}^{- 1}$ is elementary by Proposition 3.2.10.

(b) Here $𝑎 = 0$ . Swapping the rows gives $(\begin{matrix} - 2 & 3 \\ 0 & 1 \end{matrix})$ . Scaling row $1$ by $- 1 / 2$ gives $(\begin{matrix} 1 & - 3 / 2 \\ 0 & 1 \end{matrix})$ , and adding $3 / 2$ times row $2$ to row $1$ gives $𝐼_{2}$ . So $𝐸_{2, 3 / 2, 1} 𝐸_{1, - 1 / 2} 𝐸_{12} 𝐴 =$ $𝐼_{2}$ , and

𝐴 = 𝐸_{12} 𝐸_{1, - 2} 𝐸_{2, - 3 / 2, 1} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} - 2 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & - 3 / 2 \\ 0 & 1 \end{matrix}) .

Indeed, $(\begin{matrix} - 2 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} 1 & - 3 / 2 \\ 0 & 1 \end{matrix}) =$ $(\begin{matrix} - 2 & 3 \\ 0 & 1 \end{matrix})$ , and swapping its rows gives $𝐴$ . So $𝑇_{𝐴}$ is: a horizontal shear by $- 3 / 2$ , then a horizontal stretch by $2$ combined with the reflection across the $𝑥_{2}$ -axis, then the reflection across the line $𝑥_{1} = 𝑥_{2}$ .

Exercise 3.2.51.standard Let $𝐴 = (\begin{matrix} 1 & 2 & 3 \\ 2 & 4 & 7 \end{matrix}) \in ℝ^{2 \times 3}$ .

(a)Find elementary column operations that turn $𝐴$ into $(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , and compute the product $𝐻$ of the corresponding elementary matrices, so that $𝐴 𝐻 = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ .
(b)Let $𝐡_{3}$ be the third column of $𝐻$ . Show that $ker 𝑇_{𝐴} = span (𝐡_{3})$ .

Solution.

Uses. Proposition 3.2.28 (Column operations are right multiplications), Corollary 3.2.11 (Products of elementary matrices), Theorem 2.4.2 (The matrix of a composite), Remark 3.2.29 (One matrix, two operations)

Hint 1. Use column

1

to clear the rest of row

1

, then fix row

2

. Compute

𝐻

by performing the same column operations on

𝐼_{3}

Hint 2. For (b), write

𝐱 = 𝐻 𝐳

. Then

𝐴 𝐱 =

(𝐴 𝐻) 𝐳 =

(𝑧_{1}, 𝑧_{2})

Sketch. Add

- 2

times column

1

to column

2

and

- 3

times column

1

to column

3

, swap columns

2

and

3

, add

- 2

times column

2

to column

1

. On

𝐼_{3}

this gives

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

. Since

𝐻

is invertible, every

𝐱

𝐻 𝐳

, and

𝐴 𝐱 = (𝑧_{1}, 𝑧_{2})

vanishes exactly when

𝐳 = 𝑡 𝐞_{3}

, that is,

𝐱 =

𝑡 𝐡_{3} =

𝑡 (- 2, 1, 0)

(a) Adding $- 2$ times column $1$ to column $2$ gives $(\begin{matrix} 1 & 0 & 3 \\ 2 & 0 & 7 \end{matrix})$ ; adding $- 3$ times column $1$ to column $3$ gives $(\begin{matrix} 1 & 0 & 0 \\ 2 & 0 & 1 \end{matrix})$ ; swapping columns $2$ and $3$ gives $(\begin{matrix} 1 & 0 & 0 \\ 2 & 1 & 0 \end{matrix})$ ; and adding $- 2$ times column $2$ to column $1$ gives $(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ . By Proposition 3.2.28, and since the first column operation is the leftmost factor (Remark 3.2.29),

𝐻 = 𝐸_{2, - 2, 1} 𝐸_{3, - 3, 1} 𝐸_{23} 𝐸_{1, - 2, 2} .

Performing the four column operations on $𝐼_{3}$ (because $𝐼_{3} 𝐻 = 𝐻$ ):

𝐼_{3} \to (\begin{matrix} 1 & - 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \to (\begin{matrix} 1 & - 2 & - 3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \to (\begin{matrix} 1 & - 3 & - 2 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) \to (\begin{matrix} 7 & - 3 & - 2 \\ 0 & 0 & 1 \\ - 2 & 1 & 0 \end{matrix}) = 𝐻 .

(b) $𝐻$ is invertible (Corollary 3.2.11), so every $𝐱 \in ℝ^{3}$ can be written as $𝐱 = 𝐻 𝐳$ with $𝐳 = 𝐻^{- 1} 𝐱$ . Then

𝐴 𝐱 = (𝐴 𝐻) 𝐳 = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} 𝑧_{1} \\ 𝑧_{2} \\ 𝑧_{3} \end{matrix}) = (\begin{matrix} 𝑧_{1} \\ 𝑧_{2} \end{matrix}) .

So $𝐱 \in ker 𝑇_{𝐴}$ if and only if $𝑧_{1} = 𝑧_{2} = 0$ , that is, $𝐳 = 𝑡 𝐞_{3}$ for some $𝑡 \in ℝ$ , that is, $𝐱 = 𝑡 𝐻 𝐞_{3} = 𝑡 𝐡_{3}$ . Hence $ker 𝑇_{𝐴} =$ $span (𝐡_{3}) =$ $span ((- 2, 1, 0))$ . Check: $𝐴 (- 2, 1, 0) =$ $(- 2 + 2, - 4 + 4) =$ $𝟎$ .

Exercise 3.2.52.standard Let

𝑚 \geq 2

and

𝑀 \in 𝐹^{𝑚 \times 𝑚}

. Show that

𝑀

commutes with every elementary matrix of type 3 if and only if

𝑀 = 𝜆 𝐼_{𝑚}

for some

𝜆 \in 𝐹

Solution.

Uses. Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.28 (Column operations are right multiplications)

Hint 1. It suffices to use the matrices

𝐸_{𝑖, 1, 𝑗}

. Describe

𝑀 𝐸_{𝑖, 1, 𝑗}

and

𝐸_{𝑖, 1, 𝑗} 𝑀

as column and row operations on

𝑀

Hint 2.

𝑀 𝐸_{𝑖, 1, 𝑗}

𝑀

with column

𝑗

added to column

𝑖

, and

𝐸_{𝑖, 1, 𝑗} 𝑀

𝑀

with row

𝑖

added to row

𝑗

. Compare the entries in column

𝑖

Sketch.

𝑀 𝐸_{𝑖, 1, 𝑗}

differs from

𝑀

only in column

𝑖

, by

𝑚_{𝑘 𝑗}

in row

𝑘

;

𝐸_{𝑖, 1, 𝑗} 𝑀

differs from

𝑀

only in row

𝑗

, by

𝑚_{𝑖 𝑙}

in column

𝑙

. Comparing entry

(𝑘, 𝑖)

for

𝑘 \neq 𝑗

gives

𝑚_{𝑘 𝑗} = 0

; comparing entry

(𝑗, 𝑖)

gives

𝑚_{𝑗 𝑗} = 𝑚_{𝑖 𝑖}

. So

𝑀

is diagonal with equal diagonal entries.

If $𝑀 = 𝜆 𝐼_{𝑚}$ , then $𝑀 𝐸 = 𝜆 𝐸 = 𝐸 𝑀$ for every $𝐸$ .

Conversely, suppose $𝑀$ commutes with every type 3 elementary matrix, and let $𝑖 \neq 𝑗$ . By Proposition 3.2.28, $𝑀 𝐸_{𝑖, 1, 𝑗}$ is $𝑀$ with column $𝑗$ added to column $𝑖$ : it agrees with $𝑀$ outside column $𝑖$ , and its $(𝑘, 𝑖)$ entry is $𝑚_{𝑘 𝑖} + 𝑚_{𝑘 𝑗}$ . By Proposition 3.2.7, $𝐸_{𝑖, 1, 𝑗} 𝑀$ is $𝑀$ with row $𝑖$ added to row $𝑗$ : it agrees with $𝑀$ outside row $𝑗$ , and its $(𝑗, 𝑙)$ entry is $𝑚_{𝑗 𝑙} + 𝑚_{𝑖 𝑙}$ .

Compare the $(𝑘, 𝑖)$ entries for $𝑘 \neq 𝑗$ : on the left $𝑚_{𝑘 𝑖} + 𝑚_{𝑘 𝑗}$ , on the right $𝑚_{𝑘 𝑖}$ (row $𝑘$ is unchanged). So $𝑚_{𝑘 𝑗} = 0$ for all $𝑘 \neq 𝑗$ . Compare the $(𝑗, 𝑖)$ entries: $𝑚_{𝑗 𝑖} +$ $𝑚_{𝑗 𝑗} =$ $𝑚_{𝑗 𝑖} +$ $𝑚_{𝑖 𝑖}$ , so $𝑚_{𝑗 𝑗} = 𝑚_{𝑖 𝑖}$ .

Since $𝑚 \geq 2$ , every $𝑗$ has some $𝑖 \neq 𝑗$ . So every off-diagonal entry of $𝑀$ is $0$ and all diagonal entries are equal: $𝑀 = 𝜆 𝐼_{𝑚}$ with $𝜆 = 𝑚_{11}$ .

Exercise 3.2.53.hard Let

𝐹

be any field and

𝐴 =

(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) \in

𝐹^{2 \times 2}

with

𝑎 𝑑 - 𝑏 𝑐 = 1

. Show that

𝐴

is a product of at most four elementary matrices of type 3, that is, of shears.

Solution.

Uses. Exercise 3.2.42, Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.10 (Inverses of elementary matrices)

Hint 1. It suffices to reduce

𝐴

𝐼_{2}

with at most four row replacements, because inverses of type 3 matrices are of type 3. Type 3 operations do not change

𝑎 𝑑 - 𝑏 𝑐

(Exercise 3.2.42).

Hint 2. First make sure the

(2, 1)

entry is nonzero. Then one replacement makes the

(1, 1)

entry equal to

1

Hint 3. With

(1, 1)

entry

1

, clear the

(2, 1)

entry. What does

𝑎 𝑑 - 𝑏 𝑐 = 1

say about the new

(2, 2)

entry?

Sketch. If

𝑐 = 0

, then

𝑎 \neq 0

; add row

1

to row

2

to make

𝑐 \neq 0

. Add

(1 - 𝑎) / 𝑐

times row

2

to row

1

, making

𝑎 = 1

; add

- 𝑐

times row

1

to row

2

, making

𝑐 = 0

, and then

𝑑 = 1

since

𝑎 𝑑 - 𝑏 𝑐

is still

1

; add

- 𝑏

times row

2

to row

1

. That is at most four replacements, and

𝐴

is the product of their inverses in reverse order.

By Exercise 3.2.42(a), type 3 row operations do not change $𝐷 (𝐴) = 𝑎 𝑑 - 𝑏 𝑐$ , so every matrix below has $𝐷 = 1$ . We find type 3 matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ , with $𝑘 \leq 4$ , such that $𝐸_{𝑘} \dots 𝐸_{1} 𝐴 = 𝐼_{2}$ . Then $𝐴 = 𝐸_{1}^{- 1} \dots 𝐸_{𝑘}^{- 1}$ , and each $𝐸_{𝑙}^{- 1}$ is of type 3 by Proposition 3.2.10.

Step 1. If $𝑐 = 0$ , then $𝑎 𝑑 = 1$ , so $𝑎 \neq 0$ . Adding row $1$ to row $2$ changes the $(2, 1)$ entry to $𝑎 \neq 0$ . So after at most one operation the $(2, 1)$ entry, which we still call $𝑐$ , is nonzero.

Step 2. Add $(1 - 𝑎) / 𝑐$ times row $2$ to row $1$ . The new $(1, 1)$ entry is $𝑎 +$ $((1 - 𝑎) / 𝑐) 𝑐 =$ $1$ .

Step 3. Add $- 𝑐$ times row $1$ to row $2$ . The new $(2, 1)$ entry is $𝑐 - 𝑐 \cdot 1 = 0$ , so the matrix is $(\begin{matrix} 1 & 𝑏^{'} \\ 0 & 𝑑^{'} \end{matrix})$ for some $𝑏^{'}, 𝑑^{'}$ . Its value of $𝐷$ is $𝑑^{'}$ , and it is still $1$ , so $𝑑^{'} = 1$ .

Step 4. Add $- 𝑏^{'}$ times row $2$ to row $1$ . This gives $𝐼_{2}$ .

We used three operations if $𝑐 \neq 0$ at the start and four if $𝑐 = 0$ . So $𝐴$ is a product of at most four shears. For example, over $𝔽_{2}$ the swap $𝐸_{12}$ has $𝐷 = - 1 = 1$ , and Exercise 3.2.41(b) wrote it as three shears.

Exercise 3.2.54.hard Let $𝑎, 𝑏$ be integers, not both $0$ , and let $𝑔 = gcd (𝑎, 𝑏)$ . Call a $2 \times 2$ matrix an integer elementary matrix if it is $𝐸_{12}$ , $𝐸_{1, - 1}$ , $𝐸_{2, - 1}$ , or $𝐸_{𝑖 𝑐 𝑗}$ with $𝑐 \in ℤ$ .

(a)Show that integer elementary matrices have integer entries, and that their inverses are integer elementary matrices.
(b)Show that there are integer elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑘}$ with $𝐸_{𝑘} \dots 𝐸_{1} (\begin{matrix} 𝑎 \\ 𝑏 \end{matrix}) =$ $(\begin{matrix} 𝑔 \\ 0 \end{matrix})$ .
(c)Deduce Bézout’s identity: there are integers $𝑢, 𝑣$ with $𝑢 𝑎 + 𝑣 𝑏 = 𝑔$ .
(d)Carry out (b) and (c) for $(𝑎, 𝑏) = (42, 30)$ .

Solution.

Uses. Proposition 3.2.10 (Inverses of elementary matrices), Proposition 3.2.7 (Row operations are left multiplications), the division algorithm, strong induction on $| 𝑏 |$

Hint 1. Operations by integer elementary matrices are invertible over

ℤ

. What does that say about the common divisors of the two entries?

Hint 2. Imitate the Euclidean algorithm. If

𝑏 \neq 0

, write

𝑎 = 𝑞 𝑏 + 𝑟

with

0 \leq 𝑟 < | 𝑏 |

. Which operation turns

(𝑎, 𝑏)

into

(𝑟, 𝑏)

Hint 3. For (c), look at the first row of

𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}

Sketch. The operations preserve the common divisors of the two entries, so they preserve the gcd. If

𝑏 = 0

, scale by

\pm 1

. Otherwise add

- 𝑞

times row

2

to row

1

and swap, which replaces

(𝑎, 𝑏)

(𝑏, 𝑟)

with

| 𝑟 | < | 𝑏 |

; induct on

| 𝑏 |

. Then

𝐺 (\begin{matrix} 𝑎 \\ 𝑏 \end{matrix}) = (\begin{matrix} 𝑔 \\ 0 \end{matrix})

with

𝐺

an integer matrix, whose first row

(𝑢, 𝑣)

satisfies

𝑢 𝑎 + 𝑣 𝑏 = 𝑔

. For

(42, 30)

𝐺 = (\begin{matrix} - 2 & 3 \\ 5 & - 7 \end{matrix})

, and

- 2 \cdot 42 + 3 \cdot 30 = 6

(a) The matrices $𝐸_{12}$ , $𝐸_{𝑖, - 1}$ , and $𝐸_{𝑖 𝑐 𝑗}$ with $𝑐 \in ℤ$ have entries in ${0, 1, - 1, 𝑐}$ , so they are integer matrices. By Proposition 3.2.10 their inverses are $𝐸_{12}$ , $𝐸_{𝑖, - 1}$ , and $𝐸_{𝑖 (- 𝑐) 𝑗}$ , which are again integer elementary matrices.

(b) Common divisors are preserved. Let $𝐸$ be an integer elementary matrix and $𝐰 \in ℤ^{2}$ . Each entry of $𝐸 𝐰$ is an integer combination of the entries of $𝐰$ , so every common divisor of the entries of $𝐰$ divides both entries of $𝐸 𝐰$ . Since $𝐰 = 𝐸^{- 1} (𝐸 𝐰)$ and $𝐸^{- 1}$ is also an integer elementary matrix by (a), the converse holds too. So $𝐰$ and $𝐸 𝐰$ have the same common divisors, and in particular the same gcd.

The algorithm. We prove the claim by strong induction on $| 𝑏 |$ . If $𝑏 = 0$ , then $𝑔 = | 𝑎 |$ , and we are done after applying $𝐸_{1, - 1}$ if $𝑎 < 0$ . If $𝑏 \neq 0$ , divide with remainder: $𝑎 = 𝑞 𝑏 + 𝑟$ with $𝑞, 𝑟 \in ℤ$ and $0 \leq 𝑟 < | 𝑏 |$ . Adding $- 𝑞$ times row $2$ to row $1$ (the matrix $𝐸_{2, - 𝑞, 1}$ ) turns $(\begin{matrix} 𝑎 \\ 𝑏 \end{matrix})$ into $(\begin{matrix} 𝑟 \\ 𝑏 \end{matrix})$ , and swapping turns it into $(\begin{matrix} 𝑏 \\ 𝑟 \end{matrix})$ . These have the same gcd $𝑔$ , and $| 𝑟 | < | 𝑏 |$ , so by induction some product of integer elementary matrices turns $(\begin{matrix} 𝑏 \\ 𝑟 \end{matrix})$ into $(\begin{matrix} 𝑔 \\ 0 \end{matrix})$ . Composing gives the claim.

(c) Let $𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}$ . It has integer entries, being a product of integer matrices. If its first row is $(𝑢, 𝑣)$ , then the first entry of $𝐺 (\begin{matrix} 𝑎 \\ 𝑏 \end{matrix}) = (\begin{matrix} 𝑔 \\ 0 \end{matrix})$ says $𝑢 𝑎 + 𝑣 𝑏 = 𝑔$ .

(d) Adding $- 1$ times row $2$ to row $1$ gives $(\begin{matrix} 12 \\ 30 \end{matrix})$ ; adding $- 2$ times row $1$ to row $2$ gives $(\begin{matrix} 12 \\ 6 \end{matrix})$ ; adding $- 2$ times row $2$ to row $1$ gives $(\begin{matrix} 0 \\ 6 \end{matrix})$ ; swapping gives $(\begin{matrix} 6 \\ 0 \end{matrix})$ . So $𝐺 =$ $𝐸_{12} 𝐸_{2, - 2, 1} 𝐸_{1, - 2, 2} 𝐸_{2, - 1, 1}$ , with the first operation as the rightmost factor. Performing the four operations on $𝐼_{2}$ : $(\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix})$ , then $(\begin{matrix} 1 & - 1 \\ - 2 & 3 \end{matrix})$ , then $(\begin{matrix} 5 & - 7 \\ - 2 & 3 \end{matrix})$ , then

𝐺 = (\begin{matrix} - 2 & 3 \\ 5 & - 7 \end{matrix}) .

(This takes a shortcut through the algorithm of (b): instead of swapping after every division, it reduces whichever entry is larger.) So $𝑢 = - 2$ , $𝑣 = 3$ : indeed $- 2 \cdot$ $42 +$ $3 \cdot$ $30 =$ $- 84 +$ $90 =$ $6 =$ $gcd (42, 30)$ . The second row says $5 \cdot 42 - 7 \cdot 30 = 0$ .

Exercise 3.2.55.hard Start with the integer matrix $𝑀 = (\begin{matrix} 2 & 4 \\ 6 & 8 \end{matrix})$ . A move adds an integer multiple of one row to the other row, or an integer multiple of one column to the other column.

(a)Show that a move changes neither $𝑎 𝑑 - 𝑏 𝑐$ nor the greatest common divisor of the four entries of a matrix $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})$ .
(b)Which of $(\begin{matrix} 1 & 0 \\ 0 & - 8 \end{matrix})$ , $(\begin{matrix} 2 & 0 \\ 0 & 4 \end{matrix})$ , and $(\begin{matrix} 2 & 0 \\ 0 & - 4 \end{matrix})$ can be reached from $𝑀$ by a sequence of moves?

Solution.

Uses. Exercise 3.2.42, Proposition 3.2.28 (Column operations are right multiplications)

Hint 1. For

𝑎 𝑑 - 𝑏 𝑐

, the row moves were handled in Exercise 3.2.42. Do the same computation for columns, or transpose.

Hint 2. For the gcd, every new entry is an integer combination of old entries, and every move can be undone by a move.

Hint 3. Compute both invariants for

𝑀

and for each target. For a target that passes both tests, find the moves.

Sketch. Row moves keep

𝑎 𝑑 - 𝑏 𝑐

by Exercise 3.2.42; a column move adding

𝑡

times column

1

to column

2

gives

𝑎 (𝑑 + 𝑡 𝑐) -

(𝑏 + 𝑡 𝑎) 𝑐 =

𝑎 𝑑 -

𝑏 𝑐

, and similarly for the other column move. Moves preserve the set of common divisors of the entries because they are integer combinations and reversible.

𝑀

has

𝑎 𝑑 - 𝑏 𝑐 = - 8

and gcd

2

. The first target has gcd

1

, the second has

𝑎 𝑑 - 𝑏 𝑐 = 8

, and the third is reached by adding

- 3

times row

1

to row

2

and then

- 2

times column

1

to column

2

(a) The quantity $𝑎 𝑑 - 𝑏 𝑐$ . Row moves do not change it, by Exercise 3.2.42(a). Adding $𝑡$ times column $1$ to column $2$ gives $(\begin{matrix} 𝑎 & 𝑏 + 𝑡 𝑎 \\ 𝑐 & 𝑑 + 𝑡 𝑐 \end{matrix})$ , and $𝑎 (𝑑 + 𝑡 𝑐) -$ $(𝑏 + 𝑡 𝑎) 𝑐 =$ $𝑎 𝑑 -$ $𝑏 𝑐$ . Adding $𝑡$ times column $2$ to column $1$ gives $(\begin{matrix} 𝑎 + 𝑡 𝑏 & 𝑏 \\ 𝑐 + 𝑡 𝑑 & 𝑑 \end{matrix})$ , and $(𝑎 + 𝑡 𝑏) 𝑑 -$ $𝑏 (𝑐 + 𝑡 𝑑) =$ $𝑎 𝑑 -$ $𝑏 𝑐$ .

The gcd. After a move, each entry is an old entry plus an integer multiple of another old entry. So every integer dividing all four old entries divides all four new ones. The move is undone by the move with $- 𝑡$ in place of $𝑡$ , so conversely every common divisor of the new entries divides the old ones. The sets of common divisors agree, and so do the gcds.

(b) For $𝑀$ , $𝑎 𝑑 -$ $𝑏 𝑐 =$ $16 -$ $24 =$ $- 8$ and the gcd of $2, 4, 6, 8$ is $2$ .

$(\begin{matrix} 1 & 0 \\ 0 & - 8 \end{matrix})$ has $𝑎 𝑑 - 𝑏 𝑐 = - 8$ but gcd $1$ , so it cannot be reached.

$(\begin{matrix} 2 & 0 \\ 0 & 4 \end{matrix})$ has gcd $2$ but $𝑎 𝑑 - 𝑏 𝑐 = 8 \neq - 8$ , so it cannot be reached.

$(\begin{matrix} 2 & 0 \\ 0 & - 4 \end{matrix})$ can be reached. Adding $- 3$ times row $1$ to row $2$ gives $(\begin{matrix} 2 & 4 \\ 0 & - 4 \end{matrix})$ , and adding $- 2$ times column $1$ to column $2$ gives $(\begin{matrix} 2 & 0 \\ 0 & - 4 \end{matrix})$ .

In matrix terms, a move multiplies on the left or on the right by an integer elementary matrix $𝐸_{𝑖 𝑡 𝑗}$ (Proposition 3.2.7, Proposition 3.2.28). The two invariants here are the start of the theory of the Smith normal form, which classifies integer matrices up to such operations.

Exercise 3.2.56.challengeBeyond 21-242 Let $𝑛 \geq 2$ and let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be invertible. Using Theorem 3.5.19, show that

𝐴 = 𝑃 𝐸_{𝑛 𝑑}

for some product $𝑃$ of elementary matrices of type 3 and some $𝑑 \neq 0$ . (In Chapter 5, $𝑑$ turns out to be $det 𝐴$ .)

Solution.

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Exercise 3.2.41, Exercise 3.2.53, Proposition 3.2.7 (Row operations are left multiplications)

Hint 1. By Exercise 3.2.41(c),

𝐴

is a product of matrices of types 2 and 3. Try to move all the scalings to the right end.

Hint 2. Compute

𝐷 𝐸_{𝑖 𝑐 𝑗} 𝐷^{- 1}

for a diagonal

𝐷

with nonzero diagonal entries, by tracking rows. It is again of type 3.

Hint 3. A diagonal matrix with entries

𝑡

and

𝑡^{- 1}

in positions

𝑘, 𝑘 + 1

and

1

elsewhere is a product of type 3 matrices, by Exercise 3.2.53 applied in rows

𝑘, 𝑘 + 1

. Use such matrices to push all of a diagonal matrix’s entries into the last position.

Sketch. Write

𝐴

as a product of type 2 and type 3 matrices. For diagonal invertible

𝐷

𝐷 𝐸_{𝑖 𝑐 𝑗} 𝐷^{- 1} =

𝐸_{𝑖 (𝑐 𝑑_{𝑗} / 𝑑_{𝑖}) 𝑗}

, so the scalings can be moved to the right:

𝐴 = 𝑃_{1} 𝐷

with

𝑃_{1}

a product of type 3 matrices and

𝐷 =

diag (𝑑_{1}, \dots, 𝑑_{𝑛})

. With

𝑝_{𝑘} = 𝑑_{1} \dots 𝑑_{𝑘}

𝐷 =

𝐷_{1} \dots 𝐷_{𝑛 - 1} 𝐸_{𝑛 𝑝_{𝑛}}

, where

𝐷_{𝑘}

has

𝑝_{𝑘}, 𝑝_{𝑘}^{- 1}

in positions

𝑘, 𝑘 + 1

; each

𝐷_{𝑘}

is a product of shears by the

2 \times 2

result.

Write $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ for the diagonal matrix with diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ . A product of type 2 matrices is diagonal with nonzero diagonal entries, and conversely $diag (𝑑_{1}, \dots, 𝑑_{𝑛}) =$ $𝐸_{1 𝑑_{1}} \dots 𝐸_{𝑛 𝑑_{𝑛}}$ when all $𝑑_{𝑘} \neq 0$ (each factor scales one row of $𝐼_{𝑛}$ ).

Step 1: only types 2 and 3. By Theorem 3.5.19, $𝐴$ is a product of elementary matrices, and by Exercise 3.2.41(c) we may assume that every factor has type 2 or 3.

Step 2: moving scalings to the right. Let $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ with all $𝑑_{𝑘} \neq 0$ , and let $𝑖 \neq 𝑗$ . We claim

𝐷 𝐸_{𝑖 𝑐 𝑗} = 𝐸_{𝑖 𝑐^{'} 𝑗} 𝐷, 𝑐^{'} = 𝑐 𝑑_{𝑗} / 𝑑_{𝑖} .

Indeed, apply $𝐷 𝐸_{𝑖 𝑐 𝑗} 𝐷^{- 1}$ to a matrix with rows $𝐫_{1}, \dots, 𝐫_{𝑛}$ , using Proposition 3.2.7 three times. $𝐷^{- 1} =$ $diag (𝑑_{1}^{- 1}, \dots, 𝑑_{𝑛}^{- 1})$ gives rows $𝐫_{𝑘} / 𝑑_{𝑘}$ ; then $𝐸_{𝑖 𝑐 𝑗}$ changes row $𝑗$ to $𝐫_{𝑗} / 𝑑_{𝑗} +$ $𝑐 𝐫_{𝑖} / 𝑑_{𝑖}$ ; then $𝐷$ multiplies row $𝑘$ by $𝑑_{𝑘}$ . The result has rows $𝐫_{𝑘}$ for $𝑘 \neq 𝑗$ and $𝐫_{𝑗} +$ $𝑐 (𝑑_{𝑗} / 𝑑_{𝑖}) 𝐫_{𝑖}$ in row $𝑗$ , which is what $𝐸_{𝑖 𝑐^{'} 𝑗}$ does. So $𝐷 𝐸_{𝑖 𝑐 𝑗} 𝐷^{- 1} =$ $𝐸_{𝑖 𝑐^{'} 𝑗}$ , which gives the claim. Using it repeatedly, and merging adjacent diagonal factors (a product of diagonal matrices is diagonal), we can move every type 2 factor in the product of Step 1 to the right end. So $𝐴 = 𝑃_{1} 𝐷$ with $𝑃_{1}$ a product of type 3 matrices and $𝐷 =$ $diag (𝑑_{1}, \dots, 𝑑_{𝑛})$ , all $𝑑_{𝑘} \neq 0$ .

Step 3: the diagonal part. For $1 \leq 𝑘 < 𝑛$ and $𝑡 \neq 0$ , let $𝐷_{𝑘} (𝑡)$ be the diagonal matrix with $𝑡$ in position $𝑘$ , $𝑡^{- 1}$ in position $𝑘 + 1$ , and $1$ elsewhere. The $2 \times 2$ matrix $diag (𝑡, 𝑡^{- 1})$ has $𝑎 𝑑 - 𝑏 𝑐 = 1$ , so by Exercise 3.2.53 it is a product of $2 \times 2$ shears $𝐸_{1 𝑠 2}$ and $𝐸_{2 𝑠 1}$ . Replace each of these by the $𝑛 \times 𝑛$ matrix $𝐸_{𝑘, 𝑠, 𝑘 + 1}$ , respectively $𝐸_{𝑘 + 1, 𝑠, 𝑘}$ . By Proposition 3.2.7, these $𝑛 \times 𝑛$ matrices perform on rows $𝑘, 𝑘 + 1$ of $𝐼_{𝑛}$ exactly the operations that the $2 \times 2$ ones perform on rows $1, 2$ of $𝐼_{2}$ , and they leave the other rows alone. So their product is $𝐷_{𝑘} (𝑡)$ , which is therefore a product of type 3 matrices.

Now let $𝑝_{𝑘} = 𝑑_{1} 𝑑_{2} \dots 𝑑_{𝑘}$ , and consider $𝐷_{1} (𝑝_{1}) 𝐷_{2} (𝑝_{2}) \dots 𝐷_{𝑛 - 1} (𝑝_{𝑛 - 1}) 𝐸_{𝑛 𝑝_{𝑛}}$ . All factors are diagonal. Its first diagonal entry is $𝑝_{1} = 𝑑_{1}$ ; for $2 \leq 𝑘 \leq 𝑛 - 1$ its $𝑘$ th entry is $𝑝_{𝑘 - 1}^{- 1} 𝑝_{𝑘} = 𝑑_{𝑘}$ ; and its $𝑛$ th entry is $𝑝_{𝑛 - 1}^{- 1} 𝑝_{𝑛} = 𝑑_{𝑛}$ . So it equals $𝐷$ .

Therefore $𝐴 =$ $𝑃_{1} 𝐷_{1} (𝑝_{1}) \dots 𝐷_{𝑛 - 1} (𝑝_{𝑛 - 1}) 𝐸_{𝑛 𝑑}$ with $𝑑 =$ $𝑝_{𝑛} =$ $𝑑_{1} \dots 𝑑_{𝑛} \neq$ $0$ , and $𝑃 =$ $𝑃_{1} 𝐷_{1} (𝑝_{1}) \dots 𝐷_{𝑛 - 1} (𝑝_{𝑛 - 1})$ is a product of type 3 matrices.

More practice

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