3.5 Rank and the Fundamental Theorems

The two propositions of Section 3.4.4 located the answers to the two basic questions about $𝐴 𝐱 = 𝐲$ in the pivots of $𝐴_{𝑟} = rref (𝐴)$ . A pivot in every column means that solutions are unique (Proposition 3.4.15), and a pivot in every row means that there is a solution for every $𝐲$ (Proposition 3.4.16). Each row and each column holds at most one pivot, so both conditions are statements about a single number, the number of pivots. This number is the rank of $𝐴$ . With it we complete the Fundamental Theorems of Section 2.7: the rank supplies the sixth condition in each of them, and the inequality $rank 𝐴 \leq min (𝑚, 𝑛)$ supplies their constraints on the shape of $𝐴$ . In particular, invertible matrices are square. Along the way we construct one-sided inverses directly from the pivots, show that every invertible matrix is a product of elementary matrices, and show that a one-sided inverse of a square matrix is automatically two-sided. Finally, allowing column operations as well as row operations, we bring every matrix to a normal form that depends only on its rank.

3.5.1Rank

Definition 3.5.1 (Rank). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The rank of

𝐴

, written

rank 𝐴

rank (𝐴)

, is the number of pivots of

𝐴

, that is, the number of pivots of

rref (𝐴)

(Definition 3.3.9).

This is the number $𝑘$ of Section 3.4. Since $rref (𝐴)$ is determined by $𝐴$ , however the reduction is carried out (Corollary 3.3.18), so is the rank. Everything we know about pivots translates into statements about it.

Proposition 3.5.2 (First properties of rank). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ .

(a) $rank 𝐴 \leq min (𝑚, 𝑛)$ . Moreover, $rank 𝐴 = 𝑚$ if and only if $𝐴_{𝑟}$ has a pivot in every row, and $rank 𝐴 = 𝑛$ if and only if $𝐴_{𝑟}$ has a pivot in every column.
(b) $𝐴$ has exactly $𝑛 - rank 𝐴$ free columns, and $𝐴_{𝑟}$ has exactly $𝑚 - rank 𝐴$ zero rows.
(c) $rank (𝐺 𝐴) = rank 𝐴$ for every invertible $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ . In particular, row equivalent matrices have the same rank.
(d) $rank 𝐴$ is the number of indices $𝑗 \in {1, \dots, 𝑛}$ with $𝐚_{𝑗} \notin$ $span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})$ .

Proof.routine

Uses. Proposition 3.3.8 (Properties of the output), Definition 3.4.2 (Pivot and free variables), Corollary 3.3.18 (RREF and row equivalence), Definition 3.2.21 (Row equivalence), Corollary 3.2.11 (Products of elementary matrices), Corollary 3.3.19 (Pivot columns, intrinsically), Definition 1.3.10 (Span)

Hint 1. Where does Proposition 3.3.8 put the pivots? Count the rows and the columns they occupy.

Hint 2. For (c), compare

rref (𝐺 𝐴)

with

rref (𝐴)

. For (d), which result describes the pivot columns without running the algorithm?

Sketch. The

𝑟

pivots sit in positions

(1, 𝑝_{1}),

\dots,

(𝑟, 𝑝_{𝑟})

with

𝑝_{1} < \dots < 𝑝_{𝑟}

: one in each of the first

𝑟

rows and one in each of

𝑟

distinct columns. This gives (a) and (b). Part (c) is

rref (𝐺 𝐴) =

rref (𝐴)

, and (d) is Corollary 3.3.19(a), which says that the pivot columns are exactly the columns that are not combinations of earlier ones.

Let $𝑟 = rank 𝐴$ and let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be the pivot columns. By Proposition 3.3.8, the pivots are the entries in positions $(1, 𝑝_{1}),$ $\dots,$ $(𝑟, 𝑝_{𝑟})$ of $𝐴_{𝑟}$ , rows $1, \dots, 𝑟$ of $𝐴_{𝑟}$ are nonzero, and rows $𝑟 + 1, \dots, 𝑚$ are zero.

(a) The pivots lie in $𝑟$ distinct rows and $𝑟$ distinct columns, so $𝑟 \leq 𝑚$ and $𝑟 \leq 𝑛$ . Each row contains at most one pivot, so every one of the $𝑚$ rows contains a pivot if and only if $𝑟 = 𝑚$ . The same argument applies to the $𝑛$ columns.

(b) By Definition 3.4.2, the columns other than $𝑝_{1}, \dots, 𝑝_{𝑟}$ are the free columns, and there are $𝑛 - 𝑟$ of them. The zero rows of $𝐴_{𝑟}$ are rows $𝑟 + 1, \dots, 𝑚$ .

(c) By Corollary 3.3.18(a), $rref (𝐺 𝐴) =$ $rref (𝐴)$ , so $𝐺 𝐴$ and $𝐴$ have the same pivots. If $𝐴 \sim 𝐵$ , then $𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴$ for elementary matrices $𝐸_{𝑖}$ (Definition 3.2.21), and the product $𝐸_{𝑘} \dots 𝐸_{1}$ is invertible (Corollary 3.2.11).

(d) By Corollary 3.3.19(a), column $𝑗$ is a pivot column if and only if $𝐚_{𝑗}$ is not a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑗 - 1}$ , that is, if and only if $𝐚_{𝑗} \notin$ $span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})$ (Definition 1.3.10; for $𝑗 = 1$ the span of the empty list is ${𝟎}$ ). So the indices in (d) are exactly the pivot columns, and there are $𝑟$ of them. □

Part (d) describes the rank without reference to the algorithm. Scan the columns of $𝐴$ from left to right and count those that are not combinations of the columns before them; the count is $rank 𝐴$ . For instance, $(\begin{matrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{matrix})$ has rank $1$ : its first column is nonzero, and the other two are multiples of it.

Part (c) is about row operations. Column operations also preserve the rank, $rank (𝐴 𝐻) = rank 𝐴$ for invertible $𝐻$ , but row reduction gives no direct handle on this, because $rref (𝐴 𝐻)$ and $rref (𝐴)$ are in general different matrices. We prove it in Exercise 3.5.41, and Section 4.3 gives two more proofs.

Example 3.5.3 (A rank that depends on the field). Let

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

Over $ℚ$ , pass $1$ adds $- 2$ times row $1$ to rows $2$ and $3$ . Pass $2$ finds the pivot $(2, 3)$ and adds $- 2$ and $- 3$ times row $2$ to rows $3$ and $4$ . Pass $3$ scales row $3$ by $- 1 / 6$ and clears column $4$ :

\begin{aligned} 𝐴 & ⇝ (\begin{matrix} 1 & 2 & 0 & 0 & 1 \\ 0 & 0 & 1 & 3 & 5 \\ 0 & 0 & 2 & 0 & 4 \\ 0 & 0 & 3 & 0 & 6 \end{matrix}) \\ ⇝ (\begin{matrix} 1 & 2 & 0 & 0 & 1 \\ 0 & 0 & 1 & 3 & 5 \\ 0 & 0 & 0 & - 6 & - 6 \\ 0 & 0 & 0 & - 9 & - 9 \end{matrix}) \\ ⇝ (\begin{matrix} 1 & 2 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) = 𝐴_{𝑟} . \end{aligned}

So over $ℚ$ , $rank 𝐴 =$ $3 <$ $min (4, 5)$ , the pivot columns are $1, 3, 4$ , and the free columns are $2, 5$ . In terms of Proposition 3.5.2(d), $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{5} = 𝐚_{1} + 2 𝐚_{3} + 𝐚_{4}$ are the columns that bring nothing new (Corollary 3.3.19(b)).

Now read the same entries in $𝔽_{3}$ . The first two passes are the same computation with every entry reduced modulo $3$ , and the entries $- 6$ and $- 9$ of the second matrix are $0$ in $𝔽_{3}$ . So after pass $2$ the last two rows are zero, the algorithm halts, and $rank 𝐴 = 2$ over $𝔽_{3}$ . Over $𝔽_{𝑝}$ with $𝑝 \geq 5$ the computation over $ℚ$ goes through unchanged, since the only scalar we divided by is $- 6$ , which is nonzero in $𝔽_{𝑝}$ ; so the rank is $3$ there.

So the rank of a matrix with integer entries can depend on the field in which we read them. Enlarging the field never changes it: if $𝐹$ is a subfield of $𝐾$ and $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , then $rref (𝐴)$ is the same over $𝐹$ and over $𝐾$ (Exercise 3.3.54), so a rational matrix has the same rank over $ℚ$ , $ℝ$ , and $ℂ$ .

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

The matrix of Example 3.5.3 over

ℚ

. At the end the summary reports the rank, the pivot columns, and the free columns. Use “Edit” to switch the field to

𝔽_{3}

and watch the third pivot disappear, or to

𝔽_{2}

, where the rank is

3

again for different reasons.

Exercise 3.5.4.routine Find the rank of each matrix.

(a) $(\begin{matrix} 1 & - 1 & 2 \\ - 2 & 2 & - 4 \\ 3 & - 3 & 6 \end{matrix})$ over $ℚ$ .
(b)The Vandermonde matrix $𝑉 (1, 2, 3) =$ $(\begin{matrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{matrix})$ (Definition 3.4.22), over $ℚ$ and over $𝔽_{2}$ .
(c)The $𝑛 \times 𝑛$ matrix all of whose entries are $1$ , over any field.

Solution.

Uses. Definition 3.5.1 (Rank), Proposition 3.5.2 (First properties of rank), Theorem 3.4.24 (Polynomial interpolation), Theorem 3.3.23 (Invertibility and RREF)

Hint 1. For (a) and (c), use Proposition 3.5.2(d): count the columns that are not in the span of the earlier ones. Here every column is a multiple of the first.

Hint 2. For (b) over

ℚ

, the nodes

1, 2, 3

are distinct. What happens to them in

𝔽_{2}

Sketch. (a) Every column is a multiple of the first, which is nonzero: rank

1

. (b) Over

ℚ

𝑉

is invertible by Theorem 3.4.24, so its reduced form is

𝐼_{3}

and the rank is

3

. Over

𝔽_{2}

, rows

1

and

3

coincide and the rank is

2

. (c) Rank

1

(a) The first column $𝐚_{1} = (1, - 2, 3)$ is nonzero, and $𝐚_{2} = - 𝐚_{1}$ , $𝐚_{3} = 2 𝐚_{1}$ . By Proposition 3.5.2(d), only $𝑗 = 1$ counts, so the rank is $1$ .

(b) Over $ℚ$ the nodes $1, 2, 3$ are distinct, so $𝑉 (1, 2, 3)$ is invertible by Theorem 3.4.24. By Theorem 3.3.23 its reduced form is $𝐼_{3}$ , which has $3$ pivots. Over $𝔽_{2}$ we have $3 = 1$ , $4 = 0$ , and $9 = 1$ , so the matrix is $(\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})$ . Adding row $1$ to rows $2$ and $3$ gives the rows $(1, 1, 1)$ , $(0, 1, 1)$ , $(0, 0, 0)$ , and adding row $2$ to row $1$ gives

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

which is in RREF with $2$ pivots. So the rank is $2$ over $𝔽_{2}$ : the nodes $1$ and $3$ coincide in $𝔽_{2}$ , so two rows of $𝑉$ coincide.

(c) Every column equals the first, which is nonzero. By Proposition 3.5.2(d), the rank is $1$ .

Exercise 3.5.5.standard Let

𝑛 \geq 2

, and let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

be the matrix with entry

𝑖 + 𝑗

in position

(𝑖, 𝑗)

(that is, the element

(𝑖 + 𝑗) * 1

𝐹

). Show that

rank 𝐴 = 2

, whatever the field

𝐹

Solution.

Uses. Proposition 3.5.2 (First properties of rank), Definition 1.3.10 (Span)

Hint 1. Write each column as a combination of two fixed vectors:

𝐮 = (1, 2, \dots, 𝑛)

and the all-ones vector

𝟏

Hint 2. Column

𝑗

𝐮 + 𝑗 𝟏

. Express column

𝑗

through columns

1

and

2

, and use Proposition 3.5.2(d).

Hint 3. To see that column

2

is not a multiple of column

1

in every field, look at the first two entries of both columns.

Sketch. Column

𝑗

𝐜_{𝑗} = 𝐮 + 𝑗 𝟏

, and

𝐜_{𝑗} =

(2 - 𝑗) 𝐜_{1} +

(𝑗 - 1) 𝐜_{2}

. So only

𝑗 = 1, 2

can count in Proposition 3.5.2(d). Both do:

𝐜_{1} \neq 𝟎

because its first two entries

2, 3

differ by

1

, and

𝐜_{2} = 𝑡 𝐜_{1}

would give

3 = 2 𝑡

and

4 = 3 𝑡

, hence

1 = 𝑡

and then

3 = 2

, which is false in every field.

Let $𝐮 = (1, 2, \dots, 𝑛)$ and $𝟏 = (1, 1, \dots, 1)$ in $𝐹^{𝑛}$ . Column $𝑗$ of $𝐴$ is

𝐜_{𝑗} = (1 + 𝑗, 2 + 𝑗, \dots, 𝑛 + 𝑗) = 𝐮 + 𝑗 𝟏 .

For every $𝑗$ , in the combination $(2 - 𝑗) 𝐜_{1} +$ $(𝑗 - 1) 𝐜_{2} =$ $(2 - 𝑗) (𝐮 + 𝟏) +$ $(𝑗 - 1) (𝐮 + 2 𝟏)$ the coefficient of $𝐮$ is $(2 - 𝑗) + (𝑗 - 1) = 1$ and that of $𝟏$ is $(2 - 𝑗) + 2 (𝑗 - 1) = 𝑗$ . So

(2 - 𝑗) 𝐜_{1} + (𝑗 - 1) 𝐜_{2} = 𝐮 + 𝑗 𝟏 = 𝐜_{𝑗},

and for $𝑗 \geq 3$ the column $𝐜_{𝑗}$ lies in $span (𝐜_{1}, 𝐜_{2})$ , hence in $span (𝐜_{1}, \dots, 𝐜_{𝑗 - 1})$ . By Proposition 3.5.2(d), $rank 𝐴 \leq 2$ , and it remains to see that $𝑗 = 1$ and $𝑗 = 2$ both count.

The first two entries of $𝐜_{1}$ are $2$ and $3$ , and $3 - 2 = 1 \neq 0$ , so they are not both $0$ : $𝐜_{1} \neq 𝟎$ . Suppose $𝐜_{2} = 𝑡 𝐜_{1}$ for some $𝑡 \in 𝐹$ . Comparing the first two entries gives $3 = 2 𝑡$ and $4 = 3 𝑡$ . Subtracting, $1 = 𝑡$ , and then $3 = 2$ , that is, $1 = 0$ , which is false. So $𝐜_{2} \notin span (𝐜_{1})$ , and $rank 𝐴 = 2$ .

The rank also answers the consistency question for a single right-hand side. Adjoining $𝐲$ to $𝐴$ as an extra column can create at most one new pivot, and it does so exactly when the system has no solution.

Proposition 3.5.6 (Consistency and rank). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ . Then

rank 𝐴 \leq rank (𝐴 | 𝐲) \leq rank 𝐴 + 1,

and $𝐴 𝐱 = 𝐲$ is consistent if and only if $rank (𝐴 | 𝐲) =$ $rank 𝐴$ .

Proof.routine

Uses. Corollary 3.3.19 (Pivot columns, intrinsically), Corollary 3.4.5 (Consistency from the augmented matrix), Proposition 3.5.2 (First properties of rank)

Hint 1. Describe the pivot columns of

(𝐴 | 𝐲)

with Corollary 3.3.19(a). Does whether column

𝑗 \leq 𝑛

is a pivot column depend on the last column?

Hint 2. So the two matrices have the same pivot columns among

1, \dots, 𝑛

. When is column

𝑛 + 1

a pivot column?

Sketch. By Corollary 3.3.19(a), column

𝑗

of a matrix is a pivot column exactly when it is not a combination of the earlier columns, a condition involving only columns

1, \dots, 𝑗

. So for

𝑗 \leq 𝑛

, column

𝑗

is a pivot column of

(𝐴 | 𝐲)

if and only if it is one of

𝐴

. Hence

rank (𝐴 | 𝐲)

rank 𝐴 + 1

if the last column is a pivot column and

rank 𝐴

otherwise, and by Corollary 3.4.5 the last column is a pivot column exactly when the system is inconsistent.

The first

𝑛

columns of

(𝐴 | 𝐲)

are

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

. By Corollary 3.3.19(a), for

𝑗 \leq 𝑛

, column

𝑗

is a pivot column of

(𝐴 | 𝐲)

if and only if

𝐚_{𝑗}

is not a linear combination of

𝐚_{1}, \dots, 𝐚_{𝑗 - 1}

, which is also the condition for column

𝑗

to be a pivot column of

𝐴

. So the two matrices have the same pivot columns among

1, \dots, 𝑛

. Hence

rank (𝐴 | 𝐲) =

rank 𝐴

if column

𝑛 + 1

is not a pivot column of

(𝐴 | 𝐲)

, and

rank (𝐴 | 𝐲) =

rank 𝐴 +

1

if it is. By Corollary 3.4.5, column

𝑛 + 1

is a pivot column if and only if

𝐴 𝐱 = 𝐲

is inconsistent. □

In other words, $𝐴 𝐱 = 𝐲$ is consistent exactly when $𝐲$ brings nothing new beyond the columns of $𝐴$ . This criterion is often called the Rouché–Capelli theorem. It is convenient when ranks are already known, but in practice one row reduces $(𝐴 | 𝐲)$ and looks at the last column, which is what the proof does.

3.5.2The Fundamental Theorems, completed

In Section 2.7 we stated three Fundamental Theorems for $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ , each a list of equivalent conditions (I)–(V), and left open a sixth condition (the lecture marked it “secret”) and the constraint each theorem puts on the shape of $𝐴$ . We can now fill in both.

Intuition (What the rank counts). Think of

𝐴_{𝑟} 𝐱 = 𝐺 𝐲

as the system

𝐴 𝐱 = 𝐲

after elimination. Each of the

rank 𝐴

nonzero rows of

𝐴_{𝑟}

determines one pivot variable. The other

𝑛 - rank 𝐴

unknowns are free, and each free variable is an independent direction in which a solution can be moved without changing

𝐴 𝐱

; this is the failure of uniqueness. The remaining

𝑚 - rank 𝐴

rows of

𝐴_{𝑟}

are zero, and each produces a consistency condition

{(𝐺 𝐲)}_{𝑖} = 0

on the right-hand side; this is the failure of existence. So

𝑛 - rank 𝐴

measures how far

𝑇_{𝐴}

is from injective, and

𝑚 - rank 𝐴

how far it is from surjective. Since

rank 𝐴 \leq min (𝑚, 𝑛)

, a matrix with more columns than rows always has free variables, and a matrix with more rows than columns always has zero rows.

One-sided inverses from the pivots

Condition (V) of the first two theorems asks for a linear map: a left inverse of $𝑇_{𝐴}$ , or a right inverse. That (V) implies the other conditions is quick (Proposition 2.5.4, Proposition 2.5.5). The converse requires producing the inverse, and row reduction produces it explicitly. First, a remark that lets us work with matrices instead of maps.

Remark 3.5.7 (Inverses of

𝑇_{𝐴}

and inverses of

𝐴

). For

𝐶 \in 𝐹^{𝑛 \times 𝑚}

we have

𝑇_{𝐶} \circ 𝑇_{𝐴} = 𝑇_{𝐶 𝐴}

(Theorem 2.4.2(b)), and

𝑇_{𝐼_{𝑛}} = {id}_{𝐹^{𝑛}}

(Proposition 2.3.13). Every linear map

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

𝑇_{𝐶}

for exactly one

𝐶 \in 𝐹^{𝑛 \times 𝑚}

(Proposition 2.3.17). So

𝑆 = 𝑇_{𝐶}

is a left inverse of

𝑇_{𝐴}

if and only if

𝑇_{𝐶 𝐴} = 𝑇_{𝐼_{𝑛}}

, that is, if and only if

𝐶 𝐴 = 𝐼_{𝑛}

, by the uniqueness in Proposition 2.3.17. Likewise

𝑇_{𝐶}

is a right inverse of

𝑇_{𝐴}

if and only if

𝐴 𝐶 = 𝐼_{𝑚}

. Such a

𝐶

is a left inverse, respectively a right inverse, of the matrix

𝐴

(Definition 2.5.1, Definition 2.5.2), and we pass freely between the two readings.

Intuition (Choosing solutions linearly). A right inverse

𝑋

𝐴

is a rule that picks, for each

𝐲

, one solution

𝐱 = 𝑋 𝐲

𝐴 𝐱 = 𝐲

, and does so linearly. When there are free variables,

𝐴 𝐱 = 𝐲

has many solutions, and an arbitrary choice for each

𝐲

need not be linear. But one choice is visibly linear: the particular solution, which sets every free variable to

0

and reads the pivot variables off

𝐺 𝐲

(Definition 3.4.8). Writing this rule as a matrix gives the lecture’s construction.

Proposition 3.5.8 (Right inverses from the pivots). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ with $rank 𝐴 = 𝑚$ . Then $𝐴$ has a right inverse. Explicitly, let $𝑝_{1} < \dots < 𝑝_{𝑚}$ be the pivot columns of $𝐴$ , let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ , and let $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ be the matrix with entry $1$ in position $(𝑝_{𝑖}, 𝑖)$ for $𝑖 = 1, \dots, 𝑚$ and $0$ elsewhere. Then $𝐴_{𝑟} 𝐵 = 𝐼_{𝑚}$ and

𝐴 (𝐵 𝐺) = 𝐼_{𝑚} .

Moreover, for each $𝐲 \in 𝐹^{𝑚}$ , the vector $𝐵 𝐺 𝐲$ is the particular solution of $𝐴 𝐱 = 𝐲$ .

Proof.routine

Uses. Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.3.8 (Matrix–vector product), Definition 2.4.1 (Matrix product), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Definition 3.4.8 (Basic solutions)

Hint 1. Compute

𝐴_{𝑟} 𝐵

one column at a time. Column

𝑖

𝐵

is a standard basis vector of

𝐹^{𝑛}

. Which one?

Hint 2. Column

𝑖

𝐴_{𝑟} 𝐵

𝐴_{𝑟} 𝐞_{𝑝_{𝑖}}

, which is column

𝑝_{𝑖}

𝐴_{𝑟}

. What is that column?

Hint 3. Write

𝐴 = 𝐺^{- 1} 𝐴_{𝑟}

and compute

𝐴 𝐵 𝐺

Sketch. Column

𝑖

𝐵

𝐞_{𝑝_{𝑖}}

, so column

𝑖

𝐴_{𝑟} 𝐵

is column

𝑝_{𝑖}

𝐴_{𝑟}

, which is

𝐞_{𝑖}

; hence

𝐴_{𝑟} 𝐵 = 𝐼_{𝑚}

. Then

𝐴 𝐵 𝐺 =

𝐺^{- 1} 𝐴_{𝑟} 𝐵 𝐺 =

𝐺^{- 1} 𝐺 =

𝐼_{𝑚}

. Finally,

𝐵 𝐳

has

𝑧_{𝑖}

in position

𝑝_{𝑖}

and

0

in every free position, so

𝐵 𝐺 𝐲

is the particular solution.

By construction, column $𝑖$ of $𝐵$ is $𝐞_{𝑝_{𝑖}} \in 𝐹^{𝑛}$ . By Definition 2.4.1 and Definition 2.3.8, column $𝑖$ of $𝐴_{𝑟} 𝐵$ is $𝐴_{𝑟} 𝐞_{𝑝_{𝑖}}$ , which is column $𝑝_{𝑖}$ of $𝐴_{𝑟}$ . Since $𝐴_{𝑟}$ is in RREF with pivot columns $𝑝_{1}, \dots, 𝑝_{𝑚}$ , this column is $𝐞_{𝑖} \in 𝐹^{𝑚}$ (Lemma 3.3.16(b)). So $𝐴_{𝑟} 𝐵 = 𝐼_{𝑚}$ .

Since $𝐺 𝐴 = 𝐴_{𝑟}$ and $𝐺$ is invertible, $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ . Hence

𝐴 (𝐵 𝐺) = 𝐺^{- 1} 𝐴_{𝑟} 𝐵 𝐺 = 𝐺^{- 1} 𝐼_{𝑚} 𝐺 = 𝐼_{𝑚},

as desired.

For the last claim, let $𝐳 = 𝐺 𝐲$ . The vector $𝐵 𝐳 =$ $𝑧_{1} 𝐞_{𝑝_{1}} +$ $\dots +$ $𝑧_{𝑚} 𝐞_{𝑝_{𝑚}}$ has $𝑧_{𝑖}$ in position $𝑝_{𝑖}$ for each $𝑖$ , and $0$ in every other position, that is, in every free position. Since $rank 𝐴 = 𝑚$ , there are no consistency conditions, and by Definition 3.4.8(b) this is the particular solution of $𝐴 𝐱 = 𝐲$ . □

So the $𝑖$ th column of $𝐵 𝐺$ is the particular solution of $𝐴 𝐱 = 𝐞_{𝑖}$ . In other words, the right inverse is found by solving the $𝑚$ systems $𝐴 𝐱 =$ $𝐞_{1},$ $\dots,$ $𝐴 𝐱 =$ $𝐞_{𝑚}$ , just as the inverse of a square matrix is (compare the intuition after Algorithm 3.3.24). Any other choice of solutions would also give a right inverse; the particular solutions are simply the ones the reduced matrix hands us.

For left inverses the roles of rows and columns are exchanged. If $rank 𝐴 = 𝑛$ there are no free variables, and the reduced system $𝐴_{𝑟} 𝐱 = 𝐺 𝐲$ lists the unknowns $𝑥_{1}, \dots, 𝑥_{𝑛}$ themselves, so $𝐱$ can be read off from $𝐺 𝐲$ . We give this argument, and a second one that never row reduces and instead extends the columns of $𝐴$ to a basis.

Proposition 3.5.9 (Left inverses). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

with

rank 𝐴 = 𝑛

. Then

𝐴

has a left inverse.

Proof (from the pivots).routine

Uses. Proposition 3.5.2 (First properties of rank), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Definition 2.4.1 (Matrix product)

Hint 1. If every column of

𝐴_{𝑟}

is a pivot column, what are

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

, and what does

𝐴_{𝑟}

look like?

Hint 2.

𝐴_{𝑟} = (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix})

. Find an

𝑛 \times 𝑚

matrix

𝐶

with

𝐶 𝐴_{𝑟} = 𝐼_{𝑛}

, and then use

𝐺 𝐴 = 𝐴_{𝑟}

Sketch. Every column is a pivot column, so

𝑝_{𝑠} = 𝑠

and column

𝑠

𝐴_{𝑟}

𝐞_{𝑠}

𝐴_{𝑟} = (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix})

. With

𝐶 =

(\begin{matrix} 𝐼_{𝑛} & 0 \end{matrix}) \in

𝐹^{𝑛 \times 𝑚}

𝐶 𝐴_{𝑟} = 𝐼_{𝑛}

, so

(𝐶 𝐺) 𝐴 =

𝐶 𝐴_{𝑟} =

𝐼_{𝑛}

. The matrix

𝐶 𝐺

consists of the first

𝑛

rows of

𝐺

Let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10). By Proposition 3.5.2(a), every column of $𝐴_{𝑟}$ is a pivot column. So $𝑝_{1} < \dots < 𝑝_{𝑛}$ are $𝑛$ increasing numbers in ${1, \dots, 𝑛}$ , which forces $𝑝_{𝑠} = 𝑠$ , and by Lemma 3.3.16(b) column $𝑠$ of $𝐴_{𝑟}$ is $𝐞_{𝑠} \in 𝐹^{𝑚}$ . In block form,

𝐴_{𝑟} = (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix}),

where the zero block has $𝑚 - 𝑛$ rows (and is absent if $𝑚 = 𝑛$ ). Let $𝐶 =$ $(\begin{matrix} 𝐼_{𝑛} & 0 \end{matrix}) \in$ $𝐹^{𝑛 \times 𝑚}$ . For $𝑠 \leq 𝑛$ , column $𝑠$ of $𝐶 𝐴_{𝑟}$ is $𝐶 𝐞_{𝑠}$ , which is column $𝑠$ of $𝐶$ , namely $𝐞_{𝑠} \in 𝐹^{𝑛}$ . So $𝐶 𝐴_{𝑟} = 𝐼_{𝑛}$ , and

(𝐶 𝐺) 𝐴 = 𝐶 (𝐺 𝐴) = 𝐶 𝐴_{𝑟} = 𝐼_{𝑛} .

Thus $𝐶 𝐺$ is a left inverse of $𝐴$ . By Definition 2.4.1, row $𝑖$ of $𝐶 𝐺$ is row $𝑖$ of $𝐶$ times $𝐺$ , which is row $𝑖$ of $𝐺$ ; so $𝐶 𝐺$ consists of the first $𝑛$ rows of $𝐺$ . □

Proof (by extending the columns to a basis).standard

Uses. Proposition 3.4.15 (A pivot in every column), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.5.14 (Appending a vector), Proposition 1.4.14 (The span is the smallest subspace containing a list), Definition 1.6.1 (Basis), Theorem 2.2.1 (Linear maps are determined by a basis), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ )

Techniques. Construct a map by choosing it on a basis (Technique 2.2.4), Check it on a basis (Technique 2.2.7)

Hint 1. The columns

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

𝐴

are linearly independent. A left inverse

𝑆

must send

𝐚_{𝑗} = 𝐴 𝐞_{𝑗}

𝐞_{𝑗}

. On what kind of list can we prescribe the values of a linear map freely?

Hint 2. Extend

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

to a basis of

𝐹^{𝑚}

by going through

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

and appending each one that is not yet in the span (Proposition 1.5.14).

Hint 3. Define

𝑆

on that basis by

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

and

𝑆 = 𝟎

on the appended vectors, and check

𝑆 \circ 𝑇_{𝐴} = id

on the standard basis of

𝐹^{𝑛}

Sketch. The columns are independent (a pivot in every column). Appending each

𝐞_{𝑖}

that is not in the span so far keeps the list independent and eventually puts every

𝐞_{𝑖}

in its span, so it becomes a basis

𝐚_{1},

\dots,

𝐚_{𝑛},

𝐞_{𝑖_{1}},

\dots,

𝐞_{𝑖_{𝑡}}

𝐹^{𝑚}

. Let

𝑆

be the linear map with

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

and

𝑆 (𝐞_{𝑖_{𝑠}}) = 𝟎

. Then

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

𝑆 (𝐚_{𝑗}) =

𝐞_{𝑗}

, so

𝑆 \circ 𝑇_{𝐴}

and

id

agree on a basis and are equal.

Since $rank 𝐴 = 𝑛$ , $𝐴_{𝑟}$ has a pivot in every column (Proposition 3.5.2(a)), so $𝐴 𝐱 = 𝟎$ only for $𝐱 = 𝟎$ (Proposition 3.4.15). As $𝐴 𝐱 =$ $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛}$ , this says that the columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ are linearly independent (Theorem 1.5.5).

Extending to a basis. Let ${ℒ︀}_{0}$ be the list $𝐚_{1}, \dots, 𝐚_{𝑛}$ . For $𝑖 = 1, \dots, 𝑚$ , let ${ℒ︀}_{𝑖} = {ℒ︀}_{𝑖 - 1}$ if $𝐞_{𝑖} \in span ({ℒ︀}_{𝑖 - 1})$ , and let ${ℒ︀}_{𝑖}$ be ${ℒ︀}_{𝑖 - 1}$ with $𝐞_{𝑖}$ appended otherwise. By Proposition 1.5.14 and induction on $𝑖$ , each ${ℒ︀}_{𝑖}$ is linearly independent. Each $𝐞_{𝑖}$ lies in $span ({ℒ︀}_{𝑖})$ , either because it was already in $span ({ℒ︀}_{𝑖 - 1}) \subseteq$ $span ({ℒ︀}_{𝑖})$ or because it was appended, and $span ({ℒ︀}_{𝑖}) \subseteq$ $span ({ℒ︀}_{𝑚})$ since ${ℒ︀}_{𝑖}$ is a sublist of ${ℒ︀}_{𝑚}$ . So $span ({ℒ︀}_{𝑚})$ is a subspace of $𝐹^{𝑚}$ containing $𝐞_{1}, \dots, 𝐞_{𝑚}$ , hence containing every linear combination of them (Proposition 1.4.14), that is, all of $𝐹^{𝑚}$ . Thus

{ℒ︀}_{𝑚} = 𝐚_{1}, \dots, 𝐚_{𝑛}, 𝐞_{𝑖_{1}}, \dots, 𝐞_{𝑖_{𝑡}}

is linearly independent and spans $𝐹^{𝑚}$ : it is a basis of $𝐹^{𝑚}$ (Definition 1.6.1).

Defining $𝑆$ . By Theorem 2.2.1 there is a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑆 (𝐚_{𝑗}) = 𝐞_{𝑗}$ for $𝑗 = 1, \dots, 𝑛$ and $𝑆 (𝐞_{𝑖_{𝑠}}) = 𝟎$ for $𝑠 = 1, \dots, 𝑡$ . For each $𝑗$ , $(𝑆 \circ 𝑇_{𝐴}) (𝐞_{𝑗}) =$ $𝑆 (𝐴 𝐞_{𝑗}) =$ $𝑆 (𝐚_{𝑗}) =$ $𝐞_{𝑗}$ . So the linear maps $𝑆 \circ 𝑇_{𝐴}$ and ${id}_{𝐹^{𝑛}}$ agree on the basis $𝐞_{1}, \dots, 𝐞_{𝑛}$ , and by the uniqueness in Theorem 2.2.1 they are equal. By Remark 3.5.7, $𝑆 = 𝑇_{𝐶}$ for a left inverse $𝐶$ of $𝐴$ . □

The first approach gives a formula: the first $𝑛$ rows of any invertible $𝐺$ with $𝐺 𝐴 = 𝐴_{𝑟}$ form a left inverse of $𝐴$ . The second shows where the freedom lies. A left inverse is forced on the columns of $𝐴$ , which it must send to $𝐞_{1}, \dots, 𝐞_{𝑛}$ , but on the appended vectors $𝐞_{𝑖_{𝑠}}$ we could have prescribed any values at all. It also uses nothing about $𝐹^{𝑚}$ beyond a finite spanning list, which is why it survives in abstract vector spaces (Exercise 3.5.40).

Example 3.5.10 (One-sided inverses, computed). A right inverse. Let $𝐴 = (\begin{matrix} 1 & 2 & 3 \\ 2 & 4 & 7 \end{matrix}) \in ℚ^{2 \times 3}$ . Gauss–Jordan elimination performs $𝐸_{1, - 2, 2}$ and then $𝐸_{2, - 3, 1}$ , and carrying $𝐼_{2}$ along (Proposition 3.3.11) gives

\begin{aligned} (\begin{matrix} 1 & 2 & 3 & 1 & 0 \\ 2 & 4 & 7 & 0 & 1 \end{matrix}) & ⇝ (\begin{matrix} 1 & 2 & 3 & 1 & 0 \\ 0 & 0 & 1 & - 2 & 1 \end{matrix}) \\ ⇝ (\begin{matrix} 1 & 2 & 0 & 7 & - 3 \\ 0 & 0 & 1 & - 2 & 1 \end{matrix}) . \end{aligned}

So $rank 𝐴 = 2$ , the pivot columns are $𝑝_{1} = 1$ and $𝑝_{2} = 3$ , and $𝐺 = (\begin{matrix} 7 & - 3 \\ - 2 & 1 \end{matrix})$ . The matrix $𝐵$ has $1$ s in positions $(1, 1)$ and $(3, 2)$ , so

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

Check: the rows of $𝐴$ times the columns of $𝐵 𝐺$ give $7 - 6 = 1$ , $- 3 + 3 = 0$ , $14 - 14 = 0$ , and $- 6 + 7 = 1$ , so $𝐴 (𝐵 𝐺) = 𝐼_{2}$ . The middle row of $𝐵 𝐺$ is zero because $𝑥_{2}$ is a free variable, set to $0$ in every particular solution. Another right inverse is $𝐵 𝐺 + (\begin{matrix} - 2 \\ 1 \\ 0 \end{matrix}) (\begin{matrix} 1 & 1 \end{matrix})$ , since $(- 2, 1, 0)$ lies in $ker 𝑇_{𝐴}$ ; right inverses are far from unique.

A left inverse. Let $𝐴^{'} = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 2 & 1 \end{matrix}) \in ℚ^{3 \times 2}$ . Elimination performs $𝐸_{1, - 1, 2}$ , $𝐸_{1, - 2, 3}$ , and $𝐸_{2, - 1, 3}$ , ending at $𝐴_{𝑟}^{'} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix})$ , and the same operations turn $𝐼_{3}$ into

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

So $rank 𝐴^{'} = 2$ , and by the first approach the first two rows of $𝐺$ form a left inverse $𝐶 = (\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \end{matrix})$ ; indeed $𝐶 𝐴^{'} = 𝐼_{2}$ . The second approach extends the columns $(1, 1, 2)$ and $(0, 1, 1)$ to a basis. The vector $𝐞_{1}$ is not in their span (a combination $𝑥 (1, 1, 2) +$ $𝑦 (0, 1, 1) =$ $(𝑥, 𝑥 + 𝑦, 2 𝑥 + 𝑦)$ equal to $𝐞_{1}$ needs $𝑥 = 1$ , $𝑦 = - 1$ , and then $2 𝑥 + 𝑦 = 1 \neq 0$ ), so the basis is $(1, 1, 2),$ $(0, 1, 1),$ $𝐞_{1}$ . Solving for the coordinates of $𝐞_{2}$ and $𝐞_{3}$ in this basis,

\begin{aligned} 𝐞_{2} & = - (1, 1, 2) + 2 (0, 1, 1) + 𝐞_{1}, \\ 𝐞_{3} & = (1, 1, 2) - (0, 1, 1) - 𝐞_{1}, \end{aligned}

so $𝑆 (𝐞_{1}) = 𝟎$ , $𝑆 (𝐞_{2}) = (- 1, 2)$ , and $𝑆 (𝐞_{3}) = (1, - 1)$ :

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

Check: $𝑆$ sends the columns $(1, 1, 2)$ and $(0, 1, 1)$ of $𝐴^{'}$ to $(0 - 1 + 2, 0 + 2 - 2) =$ $(1, 0)$ and $(0 - 1 + 1, 0 + 2 - 1) =$ $(0, 1)$ , so $𝑆 𝐴^{'} = 𝐼_{2}$ . The two left inverses differ: $𝑆 - 𝐶 = (\begin{matrix} - 1 & - 1 & 1 \\ 1 & 1 & - 1 \end{matrix})$ . Each row of the difference is a multiple of $(- 1, - 1, 1)$ , the last row of $𝐺$ , which kills the columns of $𝐴^{'}$ ; Exercise 3.5.33 shows that this is the general pattern.

The row reducer below carries out the first computation. With $𝐼_{2}$ carried along, the right block at the end is $𝐺$ .

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

Reducing

(𝐴 | 𝐼_{2})

for the matrix

𝐴

of Example 3.5.10. The left block becomes

𝐴_{𝑟}

, with pivots in columns

1

and

3

, and the right block becomes

𝐺

. Placing the rows of

𝐺

in rows

𝑝_{1} = 1

and

𝑝_{2} = 3

of a

3 \times 2

matrix, with zeros in row

2

, gives the right inverse

𝐵 𝐺

Exercise 3.5.11.routine Let

𝐴 =

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

ℚ^{2 \times 4}

. Find its rank and pivot columns, and use Proposition 3.5.8 to find a right inverse. Check your answer.

Solution.

Uses. Proposition 3.5.8 (Right inverses from the pivots), Proposition 3.3.11 (Carrying extra columns along)

Hint 1. Reduce

(𝐴 | 𝐼_{2})

. Only one row operation is needed.

Hint 2. The pivot columns are

1

and

2

, so

𝐵

has its

1

s in positions

(1, 1)

and

(2, 2)

𝐵 𝐺

𝐺

on top of two zero rows.

Sketch. Adding

- 1

times row

2

to row

1

gives

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

and

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

. So

rank 𝐴 = 2

𝑝_{1} = 1

𝑝_{2} = 2

, and

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

Row $1$ already has a leading $1$ in column $1$ , and column $1$ is clear below it. In pass $2$ , the entry in position $(2, 2)$ is $1$ , and we add $- 1$ times row $2$ to row $1$ :

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

So $rank 𝐴 = 2$ , the pivot columns are $1$ and $2$ , and $𝐺 = (\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix})$ . The matrix $𝐵 \in ℚ^{4 \times 2}$ has $1$ s in positions $(1, 1)$ and $(2, 2)$ , so

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

Check: $𝐴 (𝐵 𝐺)$ is $𝐴$ times the columns $(1, 0, 0, 0)$ and $(- 1, 1, 0, 0)$ , that is, $𝐚_{1} = (1, 0)$ and $- 𝐚_{1} +$ $𝐚_{2} =$ $(- 1, 0) +$ $(1, 1) =$ $(0, 1)$ . So $𝐴 (𝐵 𝐺) = 𝐼_{2}$ .

The completed theorems

We restate each Fundamental Theorem in full. Conditions (I)–(V) are those of Section 2.7, and (VI) is new.

Theorem 3.5.12 (First Fundamental Theorem, completed). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is injective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has at most one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ are linearly independent.
(IV) $ker 𝑇_{𝐴} = {𝟎}$ .
(V) $𝑇_{𝐴}$ has a left inverse: a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}$ .
(VI) $rank 𝐴 = 𝑛$ .

Moreover, if these hold, then

𝑛 \leq 𝑚

Proof.routine

Uses. Theorem 2.7.2 (First Fundamental Theorem), Proposition 2.5.4 (Left inverses give uniqueness), Proposition 3.5.2 (First properties of rank), Proposition 3.4.15 (A pivot in every column), Definition 2.6.5 (Kernel), Proposition 3.5.9 (Left inverses), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ )

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Theorem 2.7.2 already ties (I)–(IV) together and shows (V)

\Rightarrow

(I). Which of (I)–(IV) is closest to a statement about pivots?

Hint 2. (IV) says that

𝐴 𝐱 = 𝟎

has only the trivial solution. Combine Proposition 3.4.15 with Proposition 3.5.2(a).

Hint 3. For (VI)

\Rightarrow

(V), use Proposition 3.5.9. For the last claim, recall

rank 𝐴 \leq 𝑚

Sketch. (I)–(IV) are equivalent and (V) implies (I) by Theorem 2.7.2. (IV) says

𝐴 𝐱 = 𝟎

only for

𝐱 = 𝟎

, which by Proposition 3.4.15 means a pivot in every column, that is,

rank 𝐴 = 𝑛

. (VI) gives a left inverse matrix by Proposition 3.5.9, hence a left inverse map. So (V)

\Rightarrow

(I)

\Rightarrow

(IV)

\Rightarrow

(VI)

\Rightarrow

(V). Finally

𝑛 = rank 𝐴 \leq 𝑚

By Theorem 2.7.2, conditions (I)–(IV) are equivalent, and (V) implies (I) (this is Proposition 2.5.4). We show (IV) $\Rightarrow$ (VI) $\Rightarrow$ (V), which closes the cycle (V) $\Rightarrow$ (I) $\Rightarrow$ (IV) $\Rightarrow$ (VI) $\Rightarrow$ (V). In fact we show (IV) $\Leftrightarrow$ (VI).

(IV) $\Leftrightarrow$ (VI). By Definition 2.6.5, $ker 𝑇_{𝐴} = {𝟎}$ says that $𝐴 𝐱 = 𝟎$ has only the trivial solution. By Proposition 3.4.15 this holds if and only if $𝐴_{𝑟}$ has a pivot in every column, which by Proposition 3.5.2(a) means $rank 𝐴 = 𝑛$ .

(VI) $\Rightarrow$ (V). By Proposition 3.5.9 there is $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ with $𝐶 𝐴 = 𝐼_{𝑛}$ , and by Remark 3.5.7 the linear map $𝑆 = 𝑇_{𝐶}$ satisfies $𝑆 \circ 𝑇_{𝐴} = {id}_{𝐹^{𝑛}}$ .

Finally, if the conditions hold, then $𝑛 = rank 𝐴 \leq 𝑚$ by Proposition 3.5.2(a). □

Theorem 3.5.13 (Second Fundamental Theorem, completed). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is surjective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has at least one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ span $𝐹^{𝑚}$ .
(IV) $im 𝑇_{𝐴} = 𝐹^{𝑚}$ .
(V) $𝑇_{𝐴}$ has a right inverse: a linear map $𝑆 : 𝐹^{𝑚} \to 𝐹^{𝑛}$ with $𝑇_{𝐴} \circ 𝑆 = {id}_{𝐹^{𝑚}}$ .
(VI) $rank 𝐴 = 𝑚$ .

Moreover, if these hold, then

𝑛 \geq 𝑚

Proof.routine

Uses. Theorem 2.7.4 (Second Fundamental Theorem), Proposition 2.5.5 (Right inverses give existence), Proposition 3.5.2 (First properties of rank), Proposition 3.4.16 (A pivot in every row), Proposition 3.5.8 (Right inverses from the pivots), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ )

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Mirror the proof of Theorem 3.5.12. Which of (I)–(IV) is a statement about pivots in rows?

Hint 2. (II) is the second condition of Proposition 3.4.16. For (VI)

\Rightarrow

(V), use Proposition 3.5.8.

Sketch. (I)–(IV) are equivalent and (V) implies (I) by Theorem 2.7.4. (II) holds iff

𝐴_{𝑟}

has a pivot in every row (Proposition 3.4.16), iff

rank 𝐴 = 𝑚

. (VI) gives the right inverse

𝐵 𝐺

of Proposition 3.5.8. So (V)

\Rightarrow

(I)

\Rightarrow

(II)

\Rightarrow

(VI)

\Rightarrow

(V), and

𝑚 = rank 𝐴 \leq 𝑛

By Theorem 2.7.4, conditions (I)–(IV) are equivalent, and (V) implies (I) (this is Proposition 2.5.5). We show (II) $\Leftrightarrow$ (VI) and (VI) $\Rightarrow$ (V), which closes the cycle (V) $\Rightarrow$ (I) $\Rightarrow$ (II) $\Rightarrow$ (VI) $\Rightarrow$ (V).

(II) $\Leftrightarrow$ (VI). By Proposition 3.4.16, (II) holds if and only if $𝐴_{𝑟}$ has a pivot in every row, which by Proposition 3.5.2(a) means $rank 𝐴 = 𝑚$ .

(VI) $\Rightarrow$ (V). By Proposition 3.5.8 there is $𝑋 = 𝐵 𝐺 \in 𝐹^{𝑛 \times 𝑚}$ with $𝐴 𝑋 = 𝐼_{𝑚}$ , and by Remark 3.5.7 the linear map $𝑆 = 𝑇_{𝑋}$ satisfies $𝑇_{𝐴} \circ 𝑆 = {id}_{𝐹^{𝑚}}$ .

Finally, if the conditions hold, then $𝑚 = rank 𝐴 \leq 𝑛$ by Proposition 3.5.2(a). □

Theorem 3.5.14 (Third Fundamental Theorem, completed). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The following are equivalent.

(I) $𝑇_{𝐴}$ is bijective.
(II)For every $𝐲 \in 𝐹^{𝑚}$ , the equation $𝐴 𝐱 = 𝐲$ has exactly one solution $𝐱 \in 𝐹^{𝑛}$ .
(III)The columns of $𝐴$ form a basis of $𝐹^{𝑚}$ .
(IV) $ker 𝑇_{𝐴} = {𝟎}$ and $im 𝑇_{𝐴} = 𝐹^{𝑚}$ .
(V) $𝑇_{𝐴}$ is invertible.
(VI) $rank 𝐴 = 𝑚 = 𝑛$ .

Moreover, if these hold, then

𝑚 = 𝑛

Proof.routine

Uses. Theorem 2.7.8 (Third Fundamental Theorem), Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed), Proposition 2.7.7 (Bijective linear maps are invertible)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. A bijection is a map that is both injective and surjective.

Hint 2. Apply the two previous theorems.

Sketch. (I)–(V) are equivalent by Theorem 2.7.8.

𝑇_{𝐴}

is bijective iff it is injective and surjective, iff

rank 𝐴 = 𝑛

and

rank 𝐴 = 𝑚

by Theorem 3.5.12 and Theorem 3.5.13.

By Theorem 2.7.8, conditions (I)–(V) are equivalent; the step from (I) to (V) is that the inverse of a bijective linear map is linear (Proposition 2.7.7). For (I)

\Leftrightarrow

(VI):

𝑇_{𝐴}

is bijective if and only if it is injective and surjective, which by Theorem 3.5.12 and Theorem 3.5.13 holds if and only if

rank 𝐴 = 𝑛

and

rank 𝐴 = 𝑚

. In that case

𝑚 = rank 𝐴 = 𝑛

. □

So the sixth conditions are $rank 𝐴 = 𝑛$ , $rank 𝐴 = 𝑚$ , and $rank 𝐴 = 𝑚 = 𝑛$ , and the “moreover” parts follow from $rank 𝐴 \leq min (𝑚, 𝑛)$ . By Remark 3.5.7, condition (V) can be read for matrices: $𝐴$ has a left inverse, a right inverse, or an inverse, respectively. With this reading, the “moreover” parts give the fact that the lecture singles out: invertible matrices are square.

Corollary 3.5.15 (Invertible matrices are square). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)If $𝐴$ has a left inverse, then $𝑛 \leq 𝑚$ .
(b)If $𝐴$ has a right inverse, then $𝑛 \geq 𝑚$ .
(c)If $𝐴$ is invertible, that is, $𝐴 𝐵 = 𝐼_{𝑚}$ and $𝐵 𝐴 = 𝐼_{𝑛}$ for some $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ , then $𝑚 = 𝑛$ .

Proof.routine

Uses. Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed)

Hint 1. Translate “

𝐴

has a left inverse” into condition (V) of one of the theorems.

Hint 2. Apply the “moreover” parts.

Sketch. A left inverse

𝐶

𝐴

gives the left inverse

𝑇_{𝐶}

𝑇_{𝐴}

, so (V) of Theorem 3.5.12 holds and

𝑛 \leq 𝑚

. Right inverses give

𝑛 \geq 𝑚

by Theorem 3.5.13, and an inverse is both.

(a) If $𝐶 𝐴 = 𝐼_{𝑛}$ , then $𝑇_{𝐶}$ is a left inverse of $𝑇_{𝐴}$ (Remark 3.5.7), so condition (V) of Theorem 3.5.12 holds, and $𝑛 \leq 𝑚$ .

(b) If $𝐴 𝐶 = 𝐼_{𝑚}$ , then $𝑇_{𝐶}$ is a right inverse of $𝑇_{𝐴}$ , so condition (V) of Theorem 3.5.13 holds, and $𝑛 \geq 𝑚$ .

(c) An inverse $𝐵$ is both a left and a right inverse, so $𝑛 \leq 𝑚$ and $𝑛 \geq 𝑚$ by (a) and (b). □

Here is what the theorems say about a list of vectors in $𝐹^{𝑚}$ , read through the matrix that has them as columns.

Corollary 3.5.16 (Lists of vectors in $𝐹^{𝑚}$ ). Let $𝐯_{1}, \dots, 𝐯_{𝑛} \in 𝐹^{𝑚}$ , and let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be the matrix with columns $𝐯_{1}, \dots, 𝐯_{𝑛}$ .

(a)The list is linearly independent if and only if $rank 𝐴 = 𝑛$ . In that case $𝑛 \leq 𝑚$ .
(b)The list spans $𝐹^{𝑚}$ if and only if $rank 𝐴 = 𝑚$ . In that case $𝑛 \geq 𝑚$ .
(c)If $𝑛 = 𝑚$ , the list is linearly independent if and only if it spans $𝐹^{𝑚}$ , if and only if it is a basis of $𝐹^{𝑚}$ .

Proof.routine

Uses. Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed), Definition 1.6.1 (Basis)

Hint 1. Which conditions of the completed theorems are about the columns of

𝐴

Hint 2. For (c), when

𝑛 = 𝑚

, the conditions

rank 𝐴 = 𝑛

and

rank 𝐴 = 𝑚

coincide.

Sketch. (a) is (III)

\Leftrightarrow

(VI) of Theorem 3.5.12 with its “moreover”, and (b) is the same for Theorem 3.5.13. If

𝑛 = 𝑚

, both say

rank 𝐴 = 𝑚

; a basis is a list that is both independent and spanning.

(a) By (III) $\Leftrightarrow$ (VI) of Theorem 3.5.12, the columns of $𝐴$ are linearly independent if and only if $rank 𝐴 = 𝑛$ , and then $𝑛 \leq 𝑚$ .

(b) By (III) $\Leftrightarrow$ (VI) of Theorem 3.5.13, the columns of $𝐴$ span $𝐹^{𝑚}$ if and only if $rank 𝐴 = 𝑚$ , and then $𝑛 \geq 𝑚$ .

(c) If $𝑛 = 𝑚$ , the conditions in (a) and (b) are the same condition $rank 𝐴 = 𝑚$ . So the list is independent if and only if it spans $𝐹^{𝑚}$ , and in that case it is both, which is the definition of a basis (Definition 1.6.1). □

In particular a basis of $𝐹^{𝑚}$ , being independent and spanning, has $𝑛 \leq 𝑚$ and $𝑛 \geq 𝑚$ vectors: every basis of $𝐹^{𝑚}$ has exactly $𝑚$ vectors. This is how Section 4.1 begins (Theorem 4.1.1), on the way to defining the dimension of a vector space. Part (c) is a first instance of a principle that Section 4.2 makes general: for a list whose length is right, independence and spanning are the same condition. Part (a) also explains Corollary 3.4.19(a) from the side of the columns: more than $𝑚$ vectors in $𝐹^{𝑚}$ are always dependent.

Remark 3.5.17 (Rank of a linear map). For a linear map

𝑇 : 𝑉 \to 𝑊

and bases

ℬ︀

𝑉

and

𝒞︀

𝑊

, it is tempting to define

rank 𝑇

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

. This is a good definition, but only because the rank of

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

does not depend on the choice of bases, and that needs ideas we do not have yet. Section 4.2 defines the rank of

𝑇

intrinsically, as the dimension of

im 𝑇

(Definition 4.2.14), and shows that it equals

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

for every choice of bases.

Exercise 3.5.18.routine For each item, either give an example or explain why none exists.

(a) $𝐴 \in ℝ^{3 \times 5}$ with $𝑇_{𝐴}$ injective.
(b) $𝐴 \in ℝ^{3 \times 5}$ with $𝑇_{𝐴}$ surjective.
(c) $𝐴 \in ℝ^{5 \times 3}$ with $rank 𝐴 = 3$ and a right inverse.
(d) $𝐴 \in ℝ^{4 \times 4}$ with $rank 𝐴 = 4$ that is not invertible.

Solution.

Hint 1. Each “moreover” clause is a constraint on the shape. Check it first.

Hint 2. For (d), compare with condition (VI) of Theorem 3.5.14.

Sketch. (a) None: injective needs

𝑛 \leq 𝑚

, but

5 > 3

. (b)

𝐴 = (\begin{matrix} 𝐼_{3} & 0 \end{matrix})

, rank

3 = 𝑚

. (c) None: a right inverse needs

𝑛 \geq 𝑚

, but

3 < 5

. (d) None:

rank 𝐴 = 4 = 𝑚 = 𝑛

makes

𝑇_{𝐴}

invertible.

(a) None. By Theorem 3.5.12, $𝑇_{𝐴}$ injective forces $𝑛 \leq 𝑚$ , and here $𝑛 = 5 > 3 = 𝑚$ . (Concretely, $rank 𝐴 \leq 3 < 5$ .)

(b) $𝐴 =$ $(\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix})$ is in RREF with $3$ pivots, so $rank 𝐴 = 3 = 𝑚$ and $𝑇_{𝐴}$ is surjective by Theorem 3.5.13.

(c) None. By Corollary 3.5.15(b), a matrix with a right inverse has $𝑛 \geq 𝑚$ , and here $𝑛 = 3 < 5 = 𝑚$ . The condition $rank 𝐴 = 3$ is possible, and it gives a left inverse instead.

(d) None. If $rank 𝐴 = 4$ , then $rank 𝐴 = 𝑚 = 𝑛$ , so $𝑇_{𝐴}$ is invertible by Theorem 3.5.14, and so is $𝐴$ (Remark 3.5.7).

3.5.3Invertible matrices are products of elementary matrices

Elementary matrices are invertible, and so are their products (Corollary 3.2.11). The converse says that the elementary matrices generate all invertible matrices: there are no others.

Theorem 3.5.19 (Invertible matrices are products of elementary matrices). Every invertible matrix $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is a product of elementary matrices. Explicitly, if Gauss–Jordan elimination on $𝐴$ performs the row operations with elementary matrices $𝐸_{1}, \dots, 𝐸_{𝑡}$ , in this order, then

𝐴 = 𝐸_{1}^{- 1} 𝐸_{2}^{- 1} \dots 𝐸_{𝑡}^{- 1},

and each $𝐸_{𝑖}^{- 1}$ is elementary. Consequently, a square matrix is invertible if and only if it is a product of elementary matrices.

Proof.routine

Uses. Theorem 3.3.23 (Invertibility and RREF), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.2.10 (Inverses of elementary matrices)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. What is

rref (𝐴)

for an invertible

𝐴

Hint 2.

𝐺 𝐴 = 𝐼_{𝑛}

with

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

. Solve for

𝐴

Sketch. By Theorem 3.3.23,

rref (𝐴) = 𝐼_{𝑛}

, so

𝐸_{𝑡} \dots 𝐸_{1} 𝐴 = 𝐼_{𝑛}

and

𝐴 =

{(𝐸_{𝑡} \dots 𝐸_{1})}^{- 1} =

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

, a product of elementary matrices by Proposition 3.2.10. The converse is Corollary 3.2.11.

Let $𝐺 = 𝐸_{𝑡} \dots 𝐸_{1}$ , so that $𝐺 𝐴 = rref (𝐴)$ (Theorem 3.3.10). Since $𝐴$ is invertible, $rref (𝐴) = 𝐼_{𝑛}$ by Theorem 3.3.23, so $𝐺 𝐴 = 𝐼_{𝑛}$ . By Corollary 3.2.11, $𝐺$ is invertible with $𝐺^{- 1} = 𝐸_{1}^{- 1} \dots 𝐸_{𝑡}^{- 1}$ , and multiplying $𝐺 𝐴 = 𝐼_{𝑛}$ on the left by $𝐺^{- 1}$ gives

𝐴 = 𝐺^{- 1} = 𝐸_{1}^{- 1} 𝐸_{2}^{- 1} \dots 𝐸_{𝑡}^{- 1} .

Each $𝐸_{𝑖}^{- 1}$ is elementary by Proposition 3.2.10. (If $𝑡 = 0$ , then $𝐴 = 𝐼_{𝑛}$ , the empty product.) Conversely, every product of elementary matrices is invertible by Corollary 3.2.11. □

Example 3.5.20 (Factoring an invertible matrix). Let $𝐴 = (\begin{matrix} 3 & 6 \\ 1 & 3 \end{matrix}) \in ℚ^{2 \times 2}$ . Elimination scales row $1$ by $1 / 3$ , adds $- 1$ times row $1$ to row $2$ , and adds $- 2$ times row $2$ to row $1$ :

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

Inverting each operation and reversing the order (Proposition 3.2.10),

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

Read from the right, this builds $𝐴$ out of $𝐼_{2}$ : $𝐸_{2, 2, 1}$ turns $𝐼_{2}$ into $(\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix})$ , then adding row $1$ to row $2$ gives $(\begin{matrix} 1 & 2 \\ 1 & 3 \end{matrix})$ , and scaling row $1$ by $3$ gives $𝐴$ . In the plane, $𝑇_{𝐴}$ is a horizontal shear, followed by a vertical shear, followed by a stretch along the $𝑥_{1}$ -axis (Example 3.2.33).

Combined with Section 3.3, the theorem gives several descriptions of the same class of matrices.

Corollary 3.5.21 (Invertibility and row equivalence).

(a)For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , the following are equivalent: $𝐴$ is invertible; $𝐴$ is a product of elementary matrices; $𝐴 \sim 𝐼_{𝑛}$ ; $rref (𝐴) = 𝐼_{𝑛}$ .
(b)For $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ , we have $𝐴 \sim 𝐵$ if and only if $𝐵 = 𝐺 𝐴$ for some invertible $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ .

Proof.routine

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Definition 3.2.21 (Row equivalence), Proposition 3.2.22 (Row equivalence is an equivalence relation), Theorem 3.3.23 (Invertibility and RREF), Corollary 3.2.11 (Products of elementary matrices)

Hint 1. By Definition 3.2.21,

𝐴 \sim 𝐵

means

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

. Compare this with “

𝐵 = 𝐺 𝐴

for a product

𝐺

of elementary matrices”.

Hint 2. For (a),

𝐴 \sim 𝐼_{𝑛}

means

𝐼_{𝑛} = 𝐺 𝐴

for a product

𝐺

of elementary matrices; equivalently (by symmetry)

𝐴 = 𝐺^{'} 𝐼_{𝑛}

Sketch. By Definition 3.2.21,

𝐴 \sim 𝐵

iff

𝐵 = 𝐺 𝐴

with

𝐺

a product of elementary matrices, and by Theorem 3.5.19 these

𝐺

are exactly the invertible matrices; this is (b). For (a),

𝐴 \sim 𝐼_{𝑛}

iff

𝐼_{𝑛} \sim 𝐴

iff

𝐴 = 𝐺 𝐼_{𝑛} = 𝐺

for an invertible

𝐺

, and

rref (𝐴) = 𝐼_{𝑛}

is Theorem 3.3.23.

(b) By Definition 3.2.21, $𝐴 \sim 𝐵$ if and only if $𝐵 = 𝐺 𝐴$ for some product $𝐺$ of elementary matrices. By Theorem 3.5.19 and Corollary 3.2.11, the products of elementary matrices in $𝐹^{𝑚 \times 𝑚}$ are exactly the invertible matrices.

(a) By Theorem 3.5.19, $𝐴$ is invertible if and only if it is a product of elementary matrices. By (b) and the symmetry of $\sim$ (Proposition 3.2.22), $𝐴 \sim 𝐼_{𝑛}$ if and only if $𝐴 = 𝐺 𝐼_{𝑛} = 𝐺$ for some invertible $𝐺$ , that is, if and only if $𝐴$ is invertible. Finally, $𝐴$ is invertible if and only if $rref (𝐴) = 𝐼_{𝑛}$ by Theorem 3.3.23. □

The theorem is what makes the method of Technique 5.4.6 work: a statement about all invertible matrices that is easy to check for swaps, scalings, and replacements, and that survives products, holds for every invertible matrix. Its main use is in Section 5.4, where it proves $det (𝐴 𝐵) =$ $det 𝐴 det 𝐵$ . Here is a first, simple instance, which turns statements about $𝐺 𝐴 𝐻$ into statements about row and column operations.

Corollary 3.5.22 (Row and column operations). Let

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

. Then

𝐵 = 𝐺 𝐴 𝐻

for some invertible

𝐺 \in 𝐹^{𝑚 \times 𝑚}

and

𝐻 \in 𝐹^{𝑛 \times 𝑛}

if and only if

𝐵

can be obtained from

𝐴

by a finite sequence of elementary row operations and elementary column operations.

Proof.routine

Uses. Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.2.7 (Row operations are left multiplications), Proposition 3.2.28 (Column operations are right multiplications)

Techniques. Reduce to elementary matrices (Technique 5.4.6)

Hint 1. A row operation is left multiplication by an elementary matrix, and a column operation is right multiplication by one.

Hint 2. For

\Rightarrow

, factor

𝐺

and

𝐻

into elementary matrices.

Hint 3. Row operations and column operations commute:

(𝐸 𝑋) 𝐸^{'} =

𝐸 (𝑋 𝐸^{'})

. So the operations may be performed in any interleaving.

Sketch. A row operation is

𝑋 \mapsto 𝐸 𝑋

and a column operation is

𝑋 \mapsto 𝑋 𝐸^{'}

(Proposition 3.2.7, Proposition 3.2.28); since

(𝐸 𝑋) 𝐸^{'} =

𝐸 (𝑋 𝐸^{'})

, any sequence of them turns

𝐴

into

(𝐸_{𝑠} \dots 𝐸_{1}) 𝐴 (𝐸_{1}^{'} \dots 𝐸_{𝑡}^{'})

, and both products are invertible. Conversely, factor

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

and

𝐻 = 𝐸_{1}^{'} \dots 𝐸_{𝑡}^{'}

by Theorem 3.5.19 and perform the corresponding operations.

By Proposition 3.2.7, performing a row operation on a matrix $𝑋$ replaces it by $𝐸 𝑋$ for an elementary $𝐸 \in 𝐹^{𝑚 \times 𝑚}$ , and by Proposition 3.2.28, performing a column operation replaces it by $𝑋 𝐸^{'}$ for an elementary $𝐸^{'} \in 𝐹^{𝑛 \times 𝑛}$ . By associativity, $(𝐸 𝑋) 𝐸^{'} =$ $𝐸 (𝑋 𝐸^{'})$ , so in any sequence of such operations the row operations and column operations can be collected separately. A sequence with row operations $𝐸_{1}, \dots, 𝐸_{𝑠}$ and column operations $𝐸_{1}^{'}, \dots, 𝐸_{𝑡}^{'}$ (each list in the order performed) therefore turns $𝐴$ into

(𝐸_{𝑠} \dots 𝐸_{1}) 𝐴 (𝐸_{1}^{'} \dots 𝐸_{𝑡}^{'}),

and both products are invertible by Corollary 3.2.11.

Conversely, suppose $𝐵 = 𝐺 𝐴 𝐻$ with $𝐺$ , $𝐻$ invertible. By Theorem 3.5.19, $𝐺 = 𝐸_{𝑠} \dots 𝐸_{1}$ and $𝐻 = 𝐸_{1}^{'} \dots 𝐸_{𝑡}^{'}$ for elementary matrices $𝐸_{𝑖}$ and $𝐸_{𝑗}^{'}$ . Performing on $𝐴$ the row operations of $𝐸_{1}, \dots, 𝐸_{𝑠}$ and then the column operations of $𝐸_{1}^{'}, \dots, 𝐸_{𝑡}^{'}$ produces $(𝐸_{𝑠} \dots 𝐸_{1}) 𝐴 (𝐸_{1}^{'} \dots 𝐸_{𝑡}^{'}) =$ $𝐺 𝐴 𝐻 =$ $𝐵$ . □

So the theorem lets us pass between “multiply by an invertible matrix” and “perform elementary operations” in both directions. The first is convenient in algebra, the second in computation and in proofs by induction on the number of operations.

3.5.4Square matrices

For a square matrix, $𝑚 = 𝑛$ , so the sixth conditions of the three Fundamental Theorems all read $rank 𝐴 = 𝑛$ . Injectivity, surjectivity, and bijectivity of $𝑇_{𝐴}$ are then the same condition. The most useful consequence is that a square matrix needs only a one-sided inverse to be invertible.

Theorem 3.5.23 (One-sided inverses of square matrices). Let

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

. If

𝐵 𝐴 = 𝐼_{𝑛}

, then

𝐴 𝐵 = 𝐼_{𝑛}

. Consequently, if a square matrix

𝐴

has a left inverse or a right inverse

𝐵

, then

𝐴

is invertible and

𝐵 = 𝐴^{- 1}

Proof.standard

Uses. Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.14 (Third Fundamental Theorem, completed), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Definition 2.5.12 (Invertible)

Hint 1.

𝐵 𝐴 = 𝐼_{𝑛}

says that

𝐴

has a left inverse. What does Theorem 3.5.12 then say about

rank 𝐴

, and what does that mean when

𝑚 = 𝑛

Hint 2.

𝐴

is invertible by Theorem 3.5.14. Compute

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

Hint 3. For a right inverse, swap the roles:

𝐴 𝐵 = 𝐼_{𝑛}

says that

𝐴

is a left inverse of

𝐵

Sketch. If

𝐵 𝐴 = 𝐼_{𝑛}

, then

𝑇_{𝐴}

has a left inverse, so

rank 𝐴 = 𝑛

by Theorem 3.5.12. As

𝐴

is square,

rank 𝐴 = 𝑛 = 𝑚

, so

𝐴

is invertible by Theorem 3.5.14. Then

𝐵 =

𝐵 (𝐴 𝐴^{- 1}) =

(𝐵 𝐴) 𝐴^{- 1} =

𝐴^{- 1}

, so

𝐴 𝐵 = 𝐴 𝐴^{- 1} = 𝐼_{𝑛}

. If instead

𝐴 𝐵 = 𝐼_{𝑛}

, apply this to the pair

(𝐵, 𝐴)

to get

𝐵 𝐴 = 𝐼_{𝑛}

Suppose $𝐵 𝐴 = 𝐼_{𝑛}$ . By Remark 3.5.7, $𝑇_{𝐵}$ is a left inverse of $𝑇_{𝐴}$ , so condition (V) of Theorem 3.5.12 holds and $rank 𝐴 = 𝑛$ . Since $𝐴$ is $𝑛 \times 𝑛$ , this says $rank 𝐴 = 𝑛 = 𝑚$ , so by Theorem 3.5.14 and Remark 3.5.7, $𝐴$ has an inverse $𝐴^{- 1}$ , with $𝐴 𝐴^{- 1} =$ $𝐴^{- 1} 𝐴 =$ $𝐼_{𝑛}$ . Then

𝐵 = 𝐵 𝐼_{𝑛} = 𝐵 (𝐴 𝐴^{- 1}) = (𝐵 𝐴) 𝐴^{- 1} = 𝐼_{𝑛} 𝐴^{- 1} = 𝐴^{- 1},

and therefore $𝐴 𝐵 = 𝐴 𝐴^{- 1} = 𝐼_{𝑛}$ .

For the second sentence: if $𝐵 𝐴 = 𝐼_{𝑛}$ , we have just shown that $𝐴$ is invertible with $𝐴^{- 1} = 𝐵$ . If $𝐴 𝐵 = 𝐼_{𝑛}$ , then the first sentence, applied with the roles of $𝐴$ and $𝐵$ exchanged, gives $𝐵 𝐴 = 𝐼_{𝑛}$ , so again $𝐵 = 𝐴^{- 1}$ . □

Intuition (Why squareness matters). The proof turned a statement about uniqueness into a statement about existence.

𝐵 𝐴 = 𝐼_{𝑛}

gives

𝐴 𝐱 =

𝟎 \Rightarrow

𝐱 =

𝐵 𝐴 𝐱 =

𝟎

, so there are no free variables; a square matrix without free variables has as many pivots as rows, so there are no zero rows either, and every equation

𝐴 𝐱 = 𝐲

is solvable. This is Technique 3.4.21 again. Both hypotheses are needed. For

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

and

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

we have

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

, but

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

. And the analogue for linear maps of an infinite-dimensional space fails: on

𝐹 [𝑥]

, let

𝑆

and

𝐿

be the linear maps with

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

for all

𝑘 \geq 0

, and

𝐿 (𝑥^{𝑘}) = 𝑥^{𝑘 - 1}

for

𝑘 \geq 1

and

𝐿 (1) = 𝟎

(Proposition 2.2.20). Then

𝐿 \circ 𝑆 = id

, but

(𝑆 \circ 𝐿) (1) = 𝟎

, so

𝑆 \circ 𝐿 \neq id

The theorem halves the work of checking that a matrix is an inverse. It also gives the converse of the familiar fact that products of invertible matrices are invertible.

Corollary 3.5.24 (Products of square matrices). Let

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

. Then

𝐴 𝐵

is invertible if and only if both

𝐴

and

𝐵

are invertible.

Proof.routine

Uses. Theorem 3.5.23 (One-sided inverses of square matrices), Definition 2.5.12 (Invertible)

Hint 1. If

𝐴 𝐵

has inverse

𝐶

, then

𝐴 (𝐵 𝐶) = 𝐼_{𝑛}

. What does that say about

𝐴

Hint 2. For

𝐵

, regroup

𝐶 (𝐴 𝐵) = 𝐼_{𝑛}

Sketch. If

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

, then

𝐴 (𝐵 𝐶) = 𝐼_{𝑛}

and

(𝐶 𝐴) 𝐵 = 𝐼_{𝑛}

, so

𝐴

has a right inverse and

𝐵

a left inverse; both are invertible by Theorem 3.5.23. Conversely,

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

𝐼_{𝑛}

Suppose $𝐴 𝐵$ is invertible, with inverse $𝐶$ . Then $𝐴 (𝐵 𝐶) =$ $(𝐴 𝐵) 𝐶 =$ $𝐼_{𝑛}$ , so $𝐴$ has a right inverse, and $(𝐶 𝐴) 𝐵 =$ $𝐶 (𝐴 𝐵) =$ $𝐼_{𝑛}$ , so $𝐵$ has a left inverse. By Theorem 3.5.23, $𝐴$ and $𝐵$ are invertible.

Conversely, if $𝐴$ and $𝐵$ are invertible, then $(𝐴 𝐵) (𝐵^{- 1} 𝐴^{- 1}) =$ $𝐴 (𝐵 𝐵^{- 1}) 𝐴^{- 1} =$ $𝐴 𝐴^{- 1} =$ $𝐼_{𝑛}$ , so $𝐴 𝐵$ has a right inverse and is invertible by Theorem 3.5.23. □

Again squareness is essential: with $𝐴 = (\begin{matrix} 1 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 \\ 0 \end{matrix})$ , the product $𝐴 𝐵 = 𝐼_{1}$ is invertible, but neither factor is, since neither is square. What survives without squareness is that $𝐴$ has a right inverse and $𝐵$ a left inverse, as the first two lines of the proof show (compare Section 2.5).

We collect what we know about square matrices. Every item below has appeared already; the point is that they are all one condition.

Corollary 3.5.25 (The invertible matrix theorem). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. The following are equivalent.

(a) $𝐴$ is invertible.
(b) $𝐴$ has a left inverse.
(c) $𝐴$ has a right inverse.
(d) $rank 𝐴 = 𝑛$ .
(e) $rref (𝐴) = 𝐼_{𝑛}$ .
(f) $𝐴$ is a product of elementary matrices.
(g)Any one of the conditions (I)–(VI) of Theorem 3.5.12, Theorem 3.5.13, or Theorem 3.5.14 holds.

In particular,

𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑛}

is injective if and only if it is surjective.

Proof.routine

Uses. Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed), Theorem 3.5.14 (Third Fundamental Theorem, completed), Theorem 3.5.23 (One-sided inverses of square matrices), Theorem 3.3.23 (Invertibility and RREF), Theorem 3.5.19 (Invertible matrices are products of elementary matrices), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ )

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. Show that each condition is equivalent to (d).

Hint 2. When

𝑚 = 𝑛

, what do the sixth conditions of the three theorems say?

Sketch. With

𝑚 = 𝑛

, condition (VI) of each of the three theorems reads

rank 𝐴 = 𝑛

, so every condition (I)–(VI) of each theorem is equivalent to (d). (a), (b), (c) are (V) of the three theorems, read for matrices; (e) and (f) are equivalent to (a) by Theorem 3.3.23 and Theorem 3.5.19.

Since

𝑚 = 𝑛

, condition (VI) of each of Theorem 3.5.12, Theorem 3.5.13, and Theorem 3.5.14 says

rank 𝐴 = 𝑛

. So, by those theorems, every one of their conditions is equivalent to (d), which gives (d)

\Leftrightarrow

(g). By Remark 3.5.7, (b), (c), and (a) are condition (V) of the three theorems, read for matrices, so they are equivalent to (d) as well. (Alternatively, (b)

\Leftrightarrow

(a)

\Leftrightarrow

\Leftrightarrow

(e) is Theorem 3.3.23, and (a)

\Leftrightarrow

(f) is Theorem 3.5.19. The last sentence is the equivalence of (I) in Theorem 3.5.12 with (I) in Theorem 3.5.13. □

This contains Corollary 3.4.20, which was proved by counting pivots directly. The equivalence of injectivity and surjectivity for $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑛}$ extends to every linear map $𝑇 : 𝑉 \to 𝑉$ of a finite-dimensional space, once dimension is available (Section 4.2).

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

Claim. If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ satisfy $𝐴 𝐵 = 𝐼_{𝑚}$ , then $𝐵 𝐴 = 𝐼_{𝑛}$ .

Proof. Since $𝐴 𝐵 = 𝐼_{𝑚}$ , we have $𝐴 𝐵 𝐴 =$ $𝐼_{𝑚} 𝐴 =$ $𝐴 =$ $𝐴 𝐼_{𝑛}$ . Cancelling $𝐴$ on the left gives $𝐵 𝐴 = 𝐼_{𝑛}$ .

Solution.

Uses. Corollary 3.5.15 (Invertible matrices are square), Theorem 3.5.23 (One-sided inverses of square matrices)

Hint 1. Cancelling

𝐴

on the left from

𝐴 𝑋 = 𝐴 𝑌

means multiplying on the left by a left inverse of

𝐴

. Does

𝐴

have one?

Hint 2. Try

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

Sketch. Cancelling

𝐴

on the left needs a left inverse of

𝐴

, which a matrix with a right inverse has only when it is square. Counterexample:

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

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

𝐴 𝐵 = 𝐼_{1}

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

The step “cancelling $𝐴$ on the left” is the error. From $𝐴 𝑋 = 𝐴 𝑌$ we may conclude $𝑋 = 𝑌$ if $𝐴$ has a left inverse $𝐶$ , by multiplying by $𝐶$ ; in general we may not, since $𝑇_{𝐴}$ need not be injective. Here $𝐴$ has a right inverse $𝐵$ , so $𝑛 \geq 𝑚$ by Corollary 3.5.15(b), and if $𝑛 > 𝑚$ then $𝐴$ has no left inverse at all, by Corollary 3.5.15(a).

The conclusion is false: for $𝐴 = (\begin{matrix} 1 & 0 \end{matrix}) \in 𝐹^{1 \times 2}$ and $𝐵 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ , we have $𝐴 𝐵 = (1) = 𝐼_{1}$ , but

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

When $𝑚 = 𝑛$ , the conclusion is true, but its proof needs Theorem 3.5.23, not cancellation.

3.5.5Rank normal form

Row operations bring $𝐴$ to $𝐴_{𝑟}$ , and no further: $𝐴_{𝑟}$ is the simplest matrix row equivalent to $𝐴$ . If column operations are allowed too, more can be cleared. Each free column of $𝐴_{𝑟}$ is a combination of the pivot columns to its left (Lemma 3.3.16(d)), and the pivot columns are $𝐞_{1}, \dots, 𝐞_{𝑘}$ , so column operations can subtract those combinations and leave zero. After moving the pivot columns to the front, what remains is determined by the rank alone.

Theorem 3.5.27 (Rank normal form). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝑘 = rank 𝐴$ , and let $𝑁_{𝑘} \in 𝐹^{𝑚 \times 𝑛}$ be the matrix

𝑁_{𝑘} = (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 0 \end{matrix}),

with $1$ in positions $(1, 1), \dots, (𝑘, 𝑘)$ and $0$ elsewhere. There are invertible matrices $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ and $𝐻 \in 𝐹^{𝑛 \times 𝑛}$ such that

𝐺 𝐴 𝐻 = 𝑁_{𝑘} .

Here $𝐺$ can be any invertible matrix with $𝐺 𝐴 = 𝐴_{𝑟}$ .

Proof (column operations on the reduced form).standard

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Proposition 3.3.8 (Properties of the output), Definition 2.4.1 (Matrix product), Theorem 2.4.34 (Block multiplication), Theorem 3.5.14 (Third Fundamental Theorem, completed), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Definition 2.5.12 (Invertible)

Techniques. Reduce to RREF (Technique 3.3.22), Block decomposition (Technique 2.4.35)

Hint 1. Start from

𝐺 𝐴 = 𝐴_{𝑟}

. It remains to find an invertible

𝐻

with

𝐴_{𝑟} 𝐻 = 𝑁_{𝑘}

, that is, to clear

𝐴_{𝑟}

by column operations.

Hint 2. First reorder the columns so that the pivot columns come first. In block form, the result is

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

for some

𝑘 \times (𝑛 - 𝑘)

matrix

𝑋

Hint 3. Multiply on the right by

(\begin{matrix} 𝐼_{𝑘} & - 𝑋 \\ 0 & 𝐼_{𝑛 - 𝑘} \end{matrix})

. Why is that matrix invertible?

Sketch. Let

𝑃

have columns

𝐞_{𝑝_{1}},

\dots,

𝐞_{𝑝_{𝑘}},

𝐞_{𝑓_{1}},

\dots,

𝐞_{𝑓_{ℓ}}

, a reordering of the standard basis, so

𝑃

is invertible. Then

𝐴_{𝑟} 𝑃

lists the pivot columns

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

first, and all columns vanish below row

𝑘

, so

𝐴_{𝑟} 𝑃 = (\begin{matrix} 𝐼_{𝑘} & 𝑋 \\ 0 & 0 \end{matrix})

. With

𝑈 = (\begin{matrix} 𝐼_{𝑘} & - 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix})

, invertible with inverse

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

, block multiplication gives

𝐴_{𝑟} 𝑃 𝑈 = 𝑁_{𝑘}

. Take

𝐻 = 𝑃 𝑈

Let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ (Theorem 3.3.10), with pivot columns $𝑝_{1} < \dots < 𝑝_{𝑘}$ and free columns $𝑓_{1} < \dots < 𝑓_{ℓ}$ , where $ℓ = 𝑛 - 𝑘$ . It suffices to find an invertible $𝐻$ with $𝐴_{𝑟} 𝐻 = 𝑁_{𝑘}$ , since then $𝐺 𝐴 𝐻 =$ $𝐴_{𝑟} 𝐻 =$ $𝑁_{𝑘}$ .

Moving the pivot columns to the front. Let $𝑃 \in 𝐹^{𝑛 \times 𝑛}$ be the matrix with columns $𝐞_{𝑝_{1}},$ $\dots,$ $𝐞_{𝑝_{𝑘}},$ $𝐞_{𝑓_{1}},$ $\dots,$ $𝐞_{𝑓_{ℓ}}$ . These are $𝐞_{1}, \dots, 𝐞_{𝑛}$ in another order, so they form a basis of $𝐹^{𝑛}$ , and $𝑃$ is invertible by Theorem 3.5.14 ((III) $\Rightarrow$ (V)) and Remark 3.5.7. Column $𝑗$ of $𝐴_{𝑟} 𝑃$ is $𝐴_{𝑟}$ times column $𝑗$ of $𝑃$ (Definition 2.4.1). For $𝑗 \leq 𝑘$ this is $𝐴_{𝑟} 𝐞_{𝑝_{𝑗}}$ , column $𝑝_{𝑗}$ of $𝐴_{𝑟}$ , which is $𝐞_{𝑗}$ (Lemma 3.3.16(b)). For $𝑗 = 𝑘 + 𝑖$ it is column $𝑓_{𝑖}$ of $𝐴_{𝑟}$ . Rows $𝑘 + 1, \dots, 𝑚$ of $𝐴_{𝑟}$ are zero (Proposition 3.3.8(a)), so every column of $𝐴_{𝑟} 𝑃$ vanishes below row $𝑘$ . In block form, with row sizes $𝑘, 𝑚 - 𝑘$ and column sizes $𝑘, ℓ$ ,

𝐴_{𝑟} 𝑃 = (\begin{matrix} 𝐼_{𝑘} & 𝑋 \\ 0 & 0 \end{matrix}),

where column $𝑖$ of $𝑋 \in 𝐹^{𝑘 \times ℓ}$ consists of the first $𝑘$ entries of column $𝑓_{𝑖}$ of $𝐴_{𝑟}$ .

Clearing $𝑋$ . Let

𝑈 = (\begin{matrix} 𝐼_{𝑘} & - 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix}), 𝑈^{'} = (\begin{matrix} 𝐼_{𝑘} & 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix}) \in 𝐹^{𝑛 \times 𝑛} .

By block multiplication (Theorem 2.4.34),

\begin{aligned} 𝑈 𝑈^{'} & = (\begin{matrix} 𝐼_{𝑘} & 𝑋 - 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix}) = 𝐼_{𝑛}, \\ 𝑈^{'} 𝑈 & = (\begin{matrix} 𝐼_{𝑘} & - 𝑋 + 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix}) = 𝐼_{𝑛}, \end{aligned}

so $𝑈$ is invertible (Definition 2.5.12), and

\begin{aligned} 𝐴_{𝑟} 𝑃 𝑈 & = (\begin{matrix} 𝐼_{𝑘} & 𝑋 \\ 0 & 0 \end{matrix}) (\begin{matrix} 𝐼_{𝑘} & - 𝑋 \\ 0 & 𝐼_{ℓ} \end{matrix}) \\ = (\begin{matrix} 𝐼_{𝑘} & - 𝑋 + 𝑋 \\ 0 & 0 \end{matrix}) = 𝑁_{𝑘} . \end{aligned}

So $𝐻 = 𝑃 𝑈$ is invertible, as a product of invertible matrices, and $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ . (If $𝑘 = 0$ , then $𝐴_{𝑟} = 0 = 𝑁_{0}$ and $𝐻 = 𝐼_{𝑛}$ works; if $ℓ = 0$ , then $𝑃 = 𝐼_{𝑛}$ and $𝑋$ and $𝑈$ are not needed. Blocks of size zero are simply absent.) □

Proof (by row reducing the transpose).standard

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Proposition 3.3.8 (Properties of the output), Definition 2.4.21 (Transpose), Proposition 2.4.23 (Transpose of a product), Proposition 3.5.9 (Left inverses), Proposition 3.5.2 (First properties of rank), Corollary 3.5.16 (Lists of vectors in $𝐹^{𝑚}$ )

Techniques. Transpose to trade rows for columns (Technique 3.2.27), Reduce to RREF (Technique 3.3.22)

Hint 1. Column operations on

𝐴_{𝑟}

are row operations on

𝐴_{𝑟}^{𝖳}

. So row reduce

𝐴_{𝑟}^{𝖳} \in 𝐹^{𝑛 \times 𝑚}

Hint 2. The first

𝑘

columns of

𝐴_{𝑟}^{𝖳}

are the nonzero rows of

𝐴_{𝑟}

, transposed, and the others are zero. Why are those

𝑘

columns linearly independent?

Hint 3. Row

𝑠

𝐴_{𝑟}

has a

1

in column

𝑝_{𝑠}

, while every other row has a

0

there.

Sketch. The first

𝑘

columns of

𝐴_{𝑟}^{𝖳}

form an

𝑛 \times 𝑘

matrix

𝑀

whose column

𝑠

is row

𝑠

𝐴_{𝑟}

; its

𝑝_{𝑡}

-th entry is

1

𝑠 = 𝑡

and

0

otherwise, so the columns are independent and

rank 𝑀 = 𝑘

. As in the proof of Proposition 3.5.9, some invertible

𝐾

has

𝐾 𝑀 = (\begin{matrix} 𝐼_{𝑘} \\ 0 \end{matrix})

, so

𝐾 𝐴_{𝑟}^{𝖳} = 𝑁_{𝑘}^{𝖳}

(the remaining columns are zero). Transposing,

𝐴_{𝑟} 𝐾^{𝖳} = 𝑁_{𝑘}

, and

𝐾^{𝖳}

is invertible.

Let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ , and let $𝑝_{1} < \dots < 𝑝_{𝑘}$ be the pivot columns. By Proposition 3.3.8, rows $𝑘 + 1, \dots, 𝑚$ of $𝐴_{𝑟}$ are zero, so the transpose $𝐴_{𝑟}^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ (Definition 2.4.21) has the block form

𝐴_{𝑟}^{𝖳} = (\begin{matrix} 𝑀 & 0 \end{matrix}),

where $𝑀 \in 𝐹^{𝑛 \times 𝑘}$ has as its column $𝑠$ the transpose of row $𝑠$ of $𝐴_{𝑟}$ , and the zero block has $𝑚 - 𝑘$ columns.

The columns of $𝑀$ are independent. Column $𝑝_{𝑡}$ of $𝐴_{𝑟}$ is $𝐞_{𝑡}$ (Lemma 3.3.16(b)), so row $𝑠$ of $𝐴_{𝑟}$ has entry $1$ in column $𝑝_{𝑡}$ if $𝑠 = 𝑡$ , and $0$ if $𝑠 \neq 𝑡$ . Hence if $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐹$ and $𝑐_{1} 𝐦_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐦_{𝑘} =$ $𝟎$ , where $𝐦_{𝑠}$ is column $𝑠$ of $𝑀$ , then the entry in position $𝑝_{𝑡}$ gives $𝑐_{𝑡} = 0$ , for each $𝑡$ . So the columns of $𝑀$ are linearly independent, and $rank 𝑀 = 𝑘$ by Corollary 3.5.16(a).

Reducing $𝑀$ . By Theorem 3.3.10 there is an invertible $𝐾 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐾 𝑀 = rref (𝑀)$ , and since $rank 𝑀 = 𝑘$ is the number of columns of $𝑀$ , the proof of Proposition 3.5.9 (first approach) shows that $rref (𝑀) = (\begin{matrix} 𝐼_{𝑘} \\ 0 \end{matrix})$ . Therefore

𝐾 𝐴_{𝑟}^{𝖳} = (\begin{matrix} 𝐾 𝑀 & 𝐾 0 \end{matrix}) = (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 0 \end{matrix}) = 𝑁_{𝑘}^{𝖳} \in 𝐹^{𝑛 \times 𝑚} .

Transposing with Proposition 2.4.23, $𝐴_{𝑟} 𝐾^{𝖳} =$ ${(𝐾 𝐴_{𝑟}^{𝖳})}^{𝖳} =$ $𝑁_{𝑘}$ . The matrix $𝐻 = 𝐾^{𝖳}$ is invertible, with inverse ${(𝐾^{- 1})}^{𝖳}$ , since $𝐾^{𝖳} {(𝐾^{- 1})}^{𝖳} =$ ${(𝐾^{- 1} 𝐾)}^{𝖳} =$ $𝐼_{𝑛}$ and similarly in the other order. So $𝐺 𝐴 𝐻 =$ $𝐴_{𝑟} 𝐻 =$ $𝑁_{𝑘}$ . □

The first proof writes $𝐻$ down: a reordering of the columns followed by subtracting multiples of the first $𝑘$ columns from the others. The second explains why the transpose of $𝐴_{𝑟}$ is no harder to reduce than $𝐴_{𝑟}$ itself: its nonzero columns are independent, because the pivot structure of $𝐴_{𝑟}$ makes the nonzero rows of $𝐴_{𝑟}$ independent. By Corollary 3.5.22, the theorem says that every matrix of rank $𝑘$ can be brought to $𝑁_{𝑘}$ by elementary row and column operations.

Example 3.5.28 (A rank normal form). For the matrix $𝐴$ of Example 3.3.3 we found

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

with pivot columns $1, 3$ and free columns $2, 4$ , so $𝑘 = 2$ . Following the first proof, $𝑃$ has columns $𝐞_{1}, 𝐞_{3}, 𝐞_{2}, 𝐞_{4}$ , and

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

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

and $𝐻 = 𝑃 𝑈$ is $𝑈$ with rows $2$ and $3$ exchanged,

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

Then

𝐺 𝐴 𝐻 = 𝐴_{𝑟} 𝐻 = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}) = 𝑁_{2} .

The last two columns of $𝐻$ , $(- 2, 1, 0, 0)$ and $(2, 0, - 2, 1)$ , are the basic solutions $𝐬_{1}, 𝐬_{2}$ of Example 3.4.10. This is no accident: in general, column $𝑘 + 𝑖$ of $𝐻 = 𝑃 𝑈$ is $𝐞_{𝑓_{𝑖}} -$ $\sum_{𝑠} 𝑥_{𝑠 𝑖} 𝐞_{𝑝_{𝑠}}$ , which is the basic solution $𝐬_{𝑖}$ (Definition 3.4.8).

What does the normal form say about the map $𝑇_{𝐴}$ ? Read $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ as $𝐴 𝐻 = 𝐺^{- 1} 𝑁_{𝑘}$ . The columns of $𝐻$ and of $𝐺^{- 1}$ form bases of $𝐹^{𝑛}$ and of $𝐹^{𝑚}$ , and in these bases $𝑇_{𝐴}$ is as simple as a linear map can be.

Corollary 3.5.29 (Bases adapted to $𝑇_{𝐴}$ ). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have rank $𝑘$ . There are a basis $𝐛_{1}, \dots, 𝐛_{𝑛}$ of $𝐹^{𝑛}$ and a basis $𝐜_{1}, \dots, 𝐜_{𝑚}$ of $𝐹^{𝑚}$ such that

𝐴 𝐛_{𝑗} = 𝐜_{𝑗} (1 \leq 𝑗 \leq 𝑘), 𝐴 𝐛_{𝑗} = 𝟎 (𝑘 < 𝑗 \leq 𝑛) .

That is, with $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ and $𝒞︀ = 𝐜_{1}, \dots, 𝐜_{𝑚}$ , we have ${[𝑇_{𝐴}]}_{𝒞︀ ℬ︀} = 𝑁_{𝑘}$ . Moreover

\begin{aligned} ker 𝑇_{𝐴} & = span (𝐛_{𝑘 + 1}, \dots, 𝐛_{𝑛}), \\ im 𝑇_{𝐴} & = span (𝐜_{1}, \dots, 𝐜_{𝑘}) . \end{aligned}

Proof.standard

Uses. Theorem 3.5.27 (Rank normal form), Theorem 3.5.14 (Third Fundamental Theorem, completed), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Definition 2.4.1 (Matrix product), Definition 2.3.1 (Matrix of a linear map), Corollary 1.5.17 (Sublists), Definition 1.3.10 (Span)

Hint 1. Take

𝐛_{𝑗}

to be the columns of

𝐻

and

𝐜_{𝑖}

the columns of

𝐺^{- 1}

. Why are these bases?

Hint 2. Compare column

𝑗

𝐴 𝐻

with column

𝑗

𝐺^{- 1} 𝑁_{𝑘}

Hint 3. For the kernel, write

𝐱 = \sum_{𝑗} 𝑥_{𝑗} 𝐛_{𝑗}

and use that

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

are independent.

Sketch. With

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

, let

𝐛_{𝑗}

be the columns of

𝐻

and

𝐜_{𝑖}

those of

𝐺^{- 1}

; both lists are bases by Theorem 3.5.14, since

𝐻

and

𝐺^{- 1}

are invertible. Column

𝑗

𝐴 𝐻 = 𝐺^{- 1} 𝑁_{𝑘}

𝐴 𝐛_{𝑗}

on the left and

𝐺^{- 1} 𝐞_{𝑗} = 𝐜_{𝑗}

(for

𝑗 \leq 𝑘

) or

𝟎

(for

𝑗 > 𝑘

) on the right. Then

𝐴 \sum_{𝑗} 𝑥_{𝑗} 𝐛_{𝑗} =

\sum_{𝑗 \leq 𝑘} 𝑥_{𝑗} 𝐜_{𝑗}

, which is

𝟎

iff

𝑥_{1} = \dots = 𝑥_{𝑘} = 0

and ranges over

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

By Theorem 3.5.27 there are invertible $𝐺$ and $𝐻$ with $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ , so $𝐴 𝐻 = 𝐺^{- 1} 𝑁_{𝑘}$ . Let $𝐛_{1}, \dots, 𝐛_{𝑛}$ be the columns of $𝐻$ and $𝐜_{1}, \dots, 𝐜_{𝑚}$ the columns of $𝐺^{- 1}$ . Since $𝑇_{𝐻}$ and $𝑇_{𝐺^{- 1}}$ are invertible (Remark 3.5.7), the columns of $𝐻$ form a basis of $𝐹^{𝑛}$ and those of $𝐺^{- 1}$ a basis of $𝐹^{𝑚}$ , by Theorem 3.5.14 ((V) $\Rightarrow$ (III)).

By Definition 2.4.1, column $𝑗$ of $𝐴 𝐻$ is $𝐴 𝐛_{𝑗}$ , and column $𝑗$ of $𝐺^{- 1} 𝑁_{𝑘}$ is $𝐺^{- 1}$ times column $𝑗$ of $𝑁_{𝑘}$ . That column is $𝐞_{𝑗} \in 𝐹^{𝑚}$ if $𝑗 \leq 𝑘$ and $𝟎$ if $𝑗 > 𝑘$ , so column $𝑗$ of $𝐺^{- 1} 𝑁_{𝑘}$ is $𝐜_{𝑗}$ if $𝑗 \leq 𝑘$ and $𝟎$ if $𝑗 > 𝑘$ . This proves the displayed equations. By Definition 2.3.1, column $𝑗$ of ${[𝑇_{𝐴}]}_{𝒞︀ ℬ︀}$ is the coordinate vector of $𝐴 𝐛_{𝑗}$ in the basis $𝒞︀$ , which is $𝐞_{𝑗}$ for $𝑗 \leq 𝑘$ and $𝟎$ for $𝑗 > 𝑘$ ; so ${[𝑇_{𝐴}]}_{𝒞︀ ℬ︀} = 𝑁_{𝑘}$ .

Every $𝐱 \in 𝐹^{𝑛}$ is $𝐱 =$ $𝑥_{1} 𝐛_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐛_{𝑛}$ for unique scalars $𝑥_{𝑗}$ , and by linearity

𝐴 𝐱 = 𝑥_{1} 𝐜_{1} + \dots + 𝑥_{𝑘} 𝐜_{𝑘} .

Since $𝐜_{1}, \dots, 𝐜_{𝑘}$ is linearly independent (a sublist of a basis, Corollary 1.5.17), $𝐴 𝐱 = 𝟎$ if and only if $𝑥_{1} = \dots = 𝑥_{𝑘} = 0$ , that is, if and only if $𝐱 \in$ $span (𝐛_{𝑘 + 1}, \dots, 𝐛_{𝑛})$ . And as $𝐱$ ranges over $𝐹^{𝑛}$ , the scalars $𝑥_{1}, \dots, 𝑥_{𝑘}$ range over all of $𝐹$ , so $𝐴 𝐱$ ranges over $span (𝐜_{1}, \dots, 𝐜_{𝑘})$ . □

So every linear map $𝐹^{𝑛} \to 𝐹^{𝑚}$ of rank $𝑘$ is, in suitable coordinates, the map $(𝑥_{1}, \dots, 𝑥_{𝑛}) \mapsto$ $(𝑥_{1}, \dots, 𝑥_{𝑘}, 0, \dots, 0)$ : it keeps $𝑘$ coordinates and kills the rest. Choosing bases to make a map simple is a theme of the rest of the book (Section 4.5, and diagonalization in Section 7.4). The corollary also previews Section 4.2. In the first proof of Theorem 3.5.27, the last $𝑛 - 𝑘$ columns of $𝐻$ are the basic solutions, and the first $𝑘$ columns of $𝐺^{- 1}$ are $𝐴 𝐞_{𝑝_{1}},$ $\dots,$ $𝐴 𝐞_{𝑝_{𝑘}}$ , the pivot columns of $𝐴$ . So the kernel is spanned by $𝑛 - 𝑘$ vectors, one for each free variable, and the image by the $𝑘$ pivot columns of $𝐴$ . Once dimension is defined, this says $dim ker 𝑇_{𝐴} +$ $dim im 𝑇_{𝐴} =$ $𝑛$ .

Is $𝑘$ the only number for which $𝐴$ has a normal form $𝑁_{𝑘}$ ? It is: if $𝐺 𝐴 𝐻 = 𝑁_{𝑗}$ for some invertible $𝐺$ and $𝐻$ , then $𝑗 = rank 𝐴$ . This amounts to $rank (𝐴 𝐻) = rank 𝐴$ for invertible $𝐻$ , and is proved in Exercise 3.5.41. It follows that two matrices $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ satisfy $𝐵 = 𝐺 𝐴 𝐻$ for some invertible $𝐺$ , $𝐻$ if and only if they have the same rank: rank is the only invariant of a matrix under row and column operations together.

Exercise 3.5.30.routine Let

𝐴 =

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

ℂ^{2 \times 3}

. Find invertible

𝐺

and

𝐻

with

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

, where

𝑘 = rank 𝐴

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Proposition 3.2.7 (Row operations are left multiplications)

Hint 1. Compare row

2

with

𝑖

times row

1

Hint 2. One row operation reduces

𝐴

. Then follow the first proof of Theorem 3.5.27: the only pivot column is column

1

, so

𝑃 = 𝐼_{3}

Sketch. Row

2

𝑖

times row

1

, so

𝐸_{1, - 𝑖, 2}

gives

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

and

𝑘 = 1

, with

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

. Then

𝑋 = (\begin{matrix} 𝑖 & 1 + 𝑖 \end{matrix})

and

𝐻 =

𝑈 =

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

Since $𝑖 (1, 𝑖, 1 + 𝑖) =$ $(𝑖, - 1, 𝑖 - 1)$ , row $2$ is $𝑖$ times row $1$ . Adding $- 𝑖$ times row $1$ to row $2$ gives

𝐴_{𝑟} = (\begin{matrix} 1 & 𝑖 & 1 + 𝑖 \\ 0 & 0 & 0 \end{matrix}), 𝐺 = 𝐸_{1, - 𝑖, 2} = (\begin{matrix} 1 & 0 \\ - 𝑖 & 1 \end{matrix}) .

So $𝑘 = rank 𝐴 = 1$ , the pivot column is $1$ , and the free columns are $2, 3$ . As in the first proof of Theorem 3.5.27, $𝑃 = 𝐼_{3}$ , $𝑋 = (\begin{matrix} 𝑖 & 1 + 𝑖 \end{matrix})$ , and

𝐻 = 𝑈 = (\begin{matrix} 1 & - 𝑖 & - 1 - 𝑖 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) .

Check: $𝐴_{𝑟} 𝐻$ has first column $(1, 0)$ , second column $(- 𝑖 + 𝑖, 0) = 𝟎$ , and third column $(- 1 - 𝑖 + 1 + 𝑖, 0) = 𝟎$ . So $𝐺 𝐴 𝐻 =$ $𝐴_{𝑟} 𝐻 =$ $(\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) =$ $𝑁_{1}$ .

Exercises

Exercise 3.5.31.standard For a scalar $𝑡$ , let

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

(a)Find $rank 𝐴_{𝑡}$ for every $𝑡 \in ℝ$ .
(b)Find $rank 𝐴_{𝑡}$ for every $𝑡 \in 𝔽_{3}$ . Which rank that occurs over $ℝ$ never occurs over $𝔽_{3}$ , and why?

Solution.

Uses. Proposition 3.5.2 (First properties of rank), Definition 3.5.1 (Rank), Algorithm 3.3.1 (Gauss–Jordan elimination), Proposition 1.1.17 (No zero divisors)

Hint 1. Row operations do not change the rank (Proposition 3.5.2(c)), so you may reorder the rows first. Put the row

(1, 1, 𝑡)

on top.

Hint 2. After clearing the first column, add the new second row to the third. The last entry becomes

2 -

𝑡 -

𝑡^{2} =

- (𝑡 - 1) (𝑡 + 2)

Hint 3. Treat the cases

𝑡 = 1

𝑡 = - 2

, and the rest separately. In

𝔽_{3}

, which of these cases coincide?

Sketch. Swapping rows

1

and

3

and eliminating gives rows

(1, 1, 𝑡)

(0, 𝑡 - 1, 1 - 𝑡)

(0, 0, - (𝑡 - 1) (𝑡 + 2))

. (a) Rank

1

for

𝑡 = 1

, rank

2

for

𝑡 = - 2

, rank

3

otherwise. (b) In

𝔽_{3}

- 2 = 1

, so the two exceptional values merge: rank

1

for

𝑡 = 1

and rank

3

for

𝑡 = 0, 2

. Rank

2

never occurs.

By Proposition 3.5.2(c), row operations do not change the rank, so we may use any convenient sequence of them; at the end we reduce to RREF and count pivots. Swap rows $1$ and $3$ , add $- 1$ times the new row $1$ to row $2$ , and add $- 𝑡$ times it to row $3$ :

𝐴_{𝑡} ⇝ (\begin{matrix} 1 & 1 & 𝑡 \\ 1 & 𝑡 & 1 \\ 𝑡 & 1 & 1 \end{matrix}) ⇝ (\begin{matrix} 1 & 1 & 𝑡 \\ 0 & 𝑡 - 1 & 1 - 𝑡 \\ 0 & 1 - 𝑡 & 1 - 𝑡^{2} \end{matrix}) .

Adding row $2$ to row $3$ makes the last entry $(1 - 𝑡) +$ $(1 - 𝑡^{2}) =$ $2 -$ $𝑡 -$ $𝑡^{2} =$ $- (𝑡 - 1) (𝑡 + 2)$ :

⇝ (\begin{matrix} 1 & 1 & 𝑡 \\ 0 & 𝑡 - 1 & 1 - 𝑡 \\ 0 & 0 & - (𝑡 - 1) (𝑡 + 2) \end{matrix}) .

These operations make sense over every field. Call this matrix $𝑀_{𝑡}$ .

(a) $𝑡 = 1$ . Rows $2$ and $3$ of $𝑀_{1}$ are zero, and $𝑀_{1} = (\begin{matrix} 1 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix})$ is in RREF. So $rank 𝐴_{1} = 1$ .

$𝑡 \neq 1$ . Scale row $2$ by $1 / (𝑡 - 1)$ , making it $(0, 1, - 1)$ , and add $- 1$ times it to row $1$ , which becomes $(1, 0, 𝑡 + 1)$ . If $𝑡 = - 2$ , row $3$ is zero, and the result $(\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & - 1 \\ 0 & 0 & 0 \end{matrix})$ is in RREF with $2$ pivots, so $rank 𝐴_{- 2} = 2$ . If $𝑡 \neq 1, - 2$ , the entry $- (𝑡 - 1) (𝑡 + 2)$ is nonzero, so scaling row $3$ and clearing column $3$ gives $𝐼_{3}$ , and $rank 𝐴_{𝑡} = 3$ .

(b) In $𝔽_{3}$ we have $- 2 = 1$ , so $𝑡 + 2 = 𝑡 - 1$ , and the last entry of $𝑀_{𝑡}$ is $- {(𝑡 - 1)}^{2}$ . For $𝑡 = 1$ the computation in (a) gives rank $1$ . For $𝑡 = 0$ and $𝑡 = 2$ , the entry $𝑡 - 1$ is nonzero and so is $- {(𝑡 - 1)}^{2}$ , by Proposition 1.1.17, so the computation in (a) gives rank $3$ . Rank $2$ never occurs: over $ℝ$ it requires $𝑡 = - 2$ with $𝑡 \neq 1$ , but in $𝔽_{3}$ the values $- 2$ and $1$ are the same. (Over an arbitrary field, $rank 𝐴_{𝑡} = 2$ exactly when $𝑡 = - 2 \neq 1$ , that is, when $𝑡 = - 2$ and $3 \neq 0$ in $𝐹$ .)

Exercise 3.5.32.routine Over

𝔽_{5}

, let

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

. Show that

rank 𝐴 = 2

, find a left inverse of

𝐴

with the first approach to Proposition 3.5.9, and find a second left inverse. How many left inverses does

𝐴

have? (Use Exercise 3.5.33 for the count.)

Solution.

Uses. Proposition 3.5.9 (Left inverses), Proposition 3.3.11 (Carrying extra columns along), Exercise 3.5.33

Hint 1. Reduce

(𝐴 | 𝐼_{3})

over

𝔽_{5}

, scanning only the first two columns. You will need

3^{- 1} = 2

Hint 2. The first two rows of the right block form a left inverse. The third row

𝐳

of the right block satisfies

𝐳 𝐴 = 𝟎

; add it to a row of the left inverse.

Sketch. Reducing

(𝐴 | 𝐼_{3})

gives

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

and

𝐺

with rows

(3, 1, 0)

(4, 2, 0)

(1, 3, 1)

. So

rank 𝐴 = 2

and

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

is a left inverse. Adding the third row of

𝐺

to the first row of

𝐶

gives another,

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

. There are

5^{2 \cdot 1} = 25

left inverses.

We reduce $(𝐴 | 𝐼_{3})$ over $𝔽_{5}$ , scanning the first two columns. Pass $1$ : the pivot is $(1, 1)$ , and we add $- 3 = 2$ times row $1$ to row $2$ . Pass $2$ : the entry in position $(2, 2)$ is now $4 + 4 = 8 = 3$ ; we scale row $2$ by $3^{- 1} = 2$ , then add $- 2 = 3$ times row $2$ to row $1$ and $- 1 = 4$ times row $2$ to row $3$ :

\begin{aligned} (\begin{matrix} 1 & 2 & 1 & 0 & 0 \\ 3 & 4 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{matrix}) & ⇝ (\begin{matrix} 1 & 2 & 1 & 0 & 0 \\ 0 & 3 & 2 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{matrix}) \\ ⇝ (\begin{matrix} 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 4 & 2 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{matrix}) \\ ⇝ (\begin{matrix} 1 & 0 & 3 & 1 & 0 \\ 0 & 1 & 4 & 2 & 0 \\ 0 & 0 & 1 & 3 & 1 \end{matrix}) . \end{aligned}

So $𝐴_{𝑟} = (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix})$ , $rank 𝐴 = 2$ , and by Proposition 3.3.11 the right block is $𝐺$ with $𝐺 𝐴 = 𝐴_{𝑟}$ . By the first approach to Proposition 3.5.9, the first two rows of $𝐺$ form a left inverse

𝐶 = (\begin{matrix} 3 & 1 & 0 \\ 4 & 2 & 0 \end{matrix}) .

Check: $3 (1, 2) +$ $1 (3, 4) =$ $(6, 10) =$ $(1, 0)$ and $4 (1, 2) +$ $2 (3, 4) =$ $(10, 16) =$ $(0, 1)$ in $𝔽_{5}$ , so $𝐶 𝐴 = 𝐼_{2}$ .

The third row $𝐳 = (1, 3, 1)$ of $𝐺$ satisfies $𝐳 𝐴 = 𝟎$ , since $𝐳 𝐴$ is row $3$ of $𝐺 𝐴 = 𝐴_{𝑟}$ . So adding $𝐳$ to the first row of $𝐶$ gives another left inverse,

𝐶^{'} = (\begin{matrix} 4 & 4 & 1 \\ 4 & 2 & 0 \end{matrix}),

and indeed $4 (1, 2) +$ $4 (3, 4) +$ $(0, 1) =$ $(16, 25) =$ $(1, 0)$ . By Exercise 3.5.33(c), with $𝑞 = 5$ , $𝑚 = 3$ , $𝑛 = 2$ , there are $5^{2 \cdot 1} = 25$ left inverses: each row of $𝐶$ may be changed by any of the $5$ multiples of $𝐳$ .

Exercise 3.5.33.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and let $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ .

(a)Suppose $rank 𝐴 = 𝑚$ , and let $𝑋_{0}$ be a right inverse of $𝐴$ . Show that the right inverses of $𝐴$ are exactly the matrices $𝑋_{0} + 𝐾$ with $𝐴 𝐾 = 0$ , that is, with every column of $𝐾$ in $ker 𝑇_{𝐴}$ .
(b)Suppose $rank 𝐴 = 𝑛$ , and let $𝐶_{0}$ consist of the first $𝑛$ rows of $𝐺$ . Show that $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ is a left inverse of $𝐴$ if and only if every row of $𝐶 - 𝐶_{0}$ is a linear combination of the last $𝑚 - 𝑛$ rows of $𝐺$ .
(c)Let $𝐹$ be finite with $𝑞$ elements. Show that a matrix of rank $𝑚$ has exactly $𝑞^{𝑚 (𝑛 - 𝑚)}$ right inverses, and a matrix of rank $𝑛$ has exactly $𝑞^{𝑛 (𝑚 - 𝑛)}$ left inverses.
(d)Over an arbitrary field, show that a matrix with a one-sided inverse has exactly one such inverse if and only if it is square.

Solution.

Uses. Proposition 3.5.9 (Left inverses), Proposition 3.5.8 (Right inverses from the pivots), Corollary 3.4.14 (Counting solutions), Definition 2.4.1 (Matrix product), Corollary 3.5.15 (Invertible matrices are square), Theorem 3.5.23 (One-sided inverses of square matrices), Proposition 3.5.2 (First properties of rank)

Hint 1. For (a) and (b), subtract:

𝐴 𝑋 = 𝐼_{𝑚} = 𝐴 𝑋_{0}

if and only if

𝐴 (𝑋 - 𝑋_{0}) = 0

, and similarly on the left.

Hint 2. For (b), a row vector

𝐳

satisfies

𝐳 𝐴 = 𝟎

if and only if

𝐰 𝐴_{𝑟} = 𝟎

, where

𝐰 = 𝐳 𝐺^{- 1}

. What is

𝐰 𝐴_{𝑟}

when

𝐴_{𝑟} = (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix})

Hint 3. For (c), count the possible columns of

𝐾

with Corollary 3.4.14(b), and the possible rows of

𝐶 - 𝐶_{0}

using that the rows of

𝐺

are linearly independent.

Sketch. (a)

𝐴 𝑋 = 𝐼_{𝑚}

iff

𝐴 (𝑋 - 𝑋_{0}) = 0

. (b)

𝐶 𝐴 = 𝐼_{𝑛}

iff

𝑍 𝐴 = 0

for

𝑍 = 𝐶 - 𝐶_{0}

. A row

𝐳

has

𝐳 𝐴 = 𝟎

iff

𝐰 = 𝐳 𝐺^{- 1}

has

𝐰 𝐴_{𝑟} =

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

𝟎

, iff

𝐳 = 𝐰 𝐺

is a combination of rows

𝑛 + 1, \dots, 𝑚

𝐺

. (c)

ker 𝑇_{𝐴}

has

𝑞^{𝑛 - 𝑚}

elements, and there are

𝑚

columns; the span of

𝑚 - 𝑛

independent rows has

𝑞^{𝑚 - 𝑛}

elements, and there are

𝑛

rows. (d) If

𝑛 > 𝑚

, a nonzero kernel vector perturbs a right inverse; if

𝑚 > 𝑛

, row

𝑚

𝐺

perturbs a left inverse; if

𝑚 = 𝑛

, the inverse is unique.

(a) If $𝐴 𝑋_{0} = 𝐼_{𝑚}$ , then $𝐴 𝑋 = 𝐼_{𝑚}$ if and only if $𝐴 (𝑋 - 𝑋_{0}) =$ $𝐴 𝑋 -$ $𝐴 𝑋_{0} =$ $0$ . By Definition 2.4.1, column $𝑗$ of $𝐴 𝐾$ is $𝐴 𝐤_{𝑗}$ , so $𝐴 𝐾 = 0$ says exactly that each column $𝐤_{𝑗}$ of $𝐾$ lies in $ker 𝑇_{𝐴}$ .

(b) By the first approach to Proposition 3.5.9, $𝐶_{0} 𝐴 = 𝐼_{𝑛}$ , and $𝐴_{𝑟} = (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix})$ . So $𝐶 𝐴 = 𝐼_{𝑛}$ if and only if $𝑍 𝐴 = 0$ , where $𝑍 = 𝐶 - 𝐶_{0}$ , that is, if and only if every row $𝐳$ of $𝑍$ satisfies $𝐳 𝐴 = 𝟎$ . Let $𝐳 \in 𝐹^{1 \times 𝑚}$ and $𝐰 = 𝐳 𝐺^{- 1}$ , so that $𝐳 = 𝐰 𝐺$ . Since $𝐴 = 𝐺^{- 1} 𝐴_{𝑟}$ ,

𝐳 𝐴 = 𝐳 𝐺^{- 1} 𝐴_{𝑟} = 𝐰 𝐴_{𝑟} = 𝐰 (\begin{matrix} 𝐼_{𝑛} \\ 0 \end{matrix}) = (𝑤_{1}, \dots, 𝑤_{𝑛}) .

So $𝐳 𝐴 = 𝟎$ if and only if $𝑤_{1} = \dots = 𝑤_{𝑛} = 0$ , if and only if $𝐳 =$ $𝐰 𝐺 =$ $𝑤_{𝑛 + 1} 𝐠_{𝑛 + 1} +$ $\dots +$ $𝑤_{𝑚} 𝐠_{𝑚}$ , where $𝐠_{𝑖}$ is row $𝑖$ of $𝐺$ (Definition 2.4.1). This is the claim.

(c) Right inverses. Fix a right inverse $𝑋_{0}$ (one exists, Proposition 3.5.8). By (a), the right inverses correspond bijectively to the matrices $𝐾$ whose $𝑚$ columns lie in $ker 𝑇_{𝐴}$ . The system $𝐴 𝐱 = 𝟎$ is consistent with $𝑛 - 𝑚$ free variables (Proposition 3.5.2(b)), so $ker 𝑇_{𝐴}$ has $𝑞^{𝑛 - 𝑚}$ elements by Corollary 3.4.14(b). Choosing the $𝑚$ columns independently gives ${(𝑞^{𝑛 - 𝑚})}^{𝑚} =$ $𝑞^{𝑚 (𝑛 - 𝑚)}$ matrices $𝐾$ .

Left inverses. The rows $𝐠_{𝑛 + 1}, \dots, 𝐠_{𝑚}$ of $𝐺$ are linearly independent: if $𝐜 𝐺 = 𝟎$ for a row vector $𝐜$ , then $𝐜 = 𝐜 𝐺 𝐺^{- 1} = 𝟎$ . So distinct coefficient lists $(𝑤_{𝑛 + 1}, \dots, 𝑤_{𝑚})$ give distinct combinations, and their span has exactly $𝑞^{𝑚 - 𝑛}$ elements. By (b), a left inverse is determined by choosing each of the $𝑛$ rows of $𝐶 - 𝐶_{0}$ in this span, which gives ${(𝑞^{𝑚 - 𝑛})}^{𝑛} =$ $𝑞^{𝑛 (𝑚 - 𝑛)}$ left inverses.

(d) If $𝐴$ is square and has a one-sided inverse, it is invertible and every one-sided inverse equals $𝐴^{- 1}$ (Theorem 3.5.23). Suppose $𝐴$ is not square. If $𝐴$ has a right inverse $𝑋_{0}$ , then $𝑛 > 𝑚$ (Corollary 3.5.15(b)), so $rank 𝐴 = 𝑚 < 𝑛$ and $𝐴$ has a free column; the corresponding basic solution $𝐬 \neq 𝟎$ lies in $ker 𝑇_{𝐴}$ , and by (a) the matrix $𝑋_{0} + 𝐬 𝐞_{1}^{𝖳}$ , whose first column is changed by $𝐬$ , is a second right inverse. If $𝐴$ has a left inverse, then $𝑚 > 𝑛$ , so $𝐺$ has a row $𝐠_{𝑚}$ beyond the first $𝑛$ , and $𝐠_{𝑚} \neq 𝟎$ as $𝐺$ is invertible. By (b), adding $𝐠_{𝑚}$ to the first row of $𝐶_{0}$ gives a second left inverse.

Exercise 3.5.34.standard Prove or disprove each statement. Matrices are over a field $𝐹$ and have the indicated sizes.

(a)If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has rank $𝑛$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ has rank $𝑝$ , then $𝐴 𝐵$ has rank $𝑝$ .
(b)If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has rank $𝑚$ and $𝐵 \in 𝐹^{𝑛 \times 𝑝}$ has rank $𝑛$ , then $𝐴 𝐵$ has rank $𝑚$ .
(c)For every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ , $rank (𝐴^{2}) = rank 𝐴$ .
(d)If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ has rank $𝑛$ , then $𝐴^{𝖳}$ has rank $𝑛$ .
(e)The matrices $𝐺$ and $𝐻$ in Theorem 3.5.27 are determined by $𝐴$ .
(f)If $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ with $𝑚 > 𝑛$ , then $𝐴 𝐵$ is not invertible.

Solution.

Uses. Theorem 3.5.12 (First Fundamental Theorem, completed), Theorem 3.5.13 (Second Fundamental Theorem, completed), Theorem 2.4.2 (The matrix of a composite), Proposition 2.4.23 (Transpose of a product), Remark 3.5.7 (Inverses of $𝑇_{𝐴}$ and inverses of $𝐴$ ), Theorem 3.5.14 (Third Fundamental Theorem, completed)

Hint 1. Translate rank conditions into injectivity or surjectivity of

𝑇_{𝐴}

𝑇_{𝐵}

, and

𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}

Hint 2. For (c), think of a matrix that kills its own image. For (d), transpose a left inverse. For (e), try

𝐴 = 0

Hint 3. For (f), which of

𝑇_{𝐴}

and

𝑇_{𝐵}

fails to be injective?

Sketch. (a) True: a composition of injective maps is injective. (b) True: a composition of surjective maps is surjective. (c) False:

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

has rank

1

and

𝐴^{2} = 0

. (d) True: if

𝐶 𝐴 = 𝐼_{𝑛}

, then

𝐴^{𝖳} 𝐶^{𝖳} = 𝐼_{𝑛}

, so

𝑇_{𝐴^{𝖳}}

is surjective onto

𝐹^{𝑛}

. (e) False: for

𝐴 = 0 \in 𝐹^{2 \times 2}

, every pair of invertible matrices works. (f) True:

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

is not injective, hence neither is

𝑇_{𝐴} \circ 𝑇_{𝐵}

(a) True. By Theorem 3.5.12, $𝑇_{𝐴}$ and $𝑇_{𝐵}$ are injective. If $(𝑇_{𝐴} \circ 𝑇_{𝐵}) (𝐱) =$ $(𝑇_{𝐴} \circ 𝑇_{𝐵}) (𝐱^{'})$ , then $𝑇_{𝐵} 𝐱 = 𝑇_{𝐵} 𝐱^{'}$ by injectivity of $𝑇_{𝐴}$ , and then $𝐱 = 𝐱^{'}$ . So $𝑇_{𝐴 𝐵} = 𝑇_{𝐴} \circ 𝑇_{𝐵}$ (Theorem 2.4.2(b)) is injective, and since $𝐴 𝐵 \in 𝐹^{𝑚 \times 𝑝}$ , Theorem 3.5.12 gives $rank (𝐴 𝐵) = 𝑝$ .

(b) True. By Theorem 3.5.13, $𝑇_{𝐴} : 𝐹^{𝑛} \to 𝐹^{𝑚}$ and $𝑇_{𝐵} : 𝐹^{𝑝} \to 𝐹^{𝑛}$ are surjective. Given $𝐲 \in 𝐹^{𝑚}$ , choose $𝐮 \in 𝐹^{𝑛}$ with $𝐴 𝐮 = 𝐲$ and then $𝐱 \in 𝐹^{𝑝}$ with $𝐵 𝐱 = 𝐮$ ; then $𝐴 𝐵 𝐱 = 𝐲$ . So $𝑇_{𝐴 𝐵}$ is surjective, and $rank (𝐴 𝐵) = 𝑚$ by Theorem 3.5.13.

(c) False. For $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ , which is in RREF with one pivot, $rank 𝐴 = 1$ , but $𝐴^{2} = 0$ has rank $0$ .

(d) True. By Theorem 3.5.12 and Remark 3.5.7, $𝐴$ has a left inverse $𝐶 \in 𝐹^{𝑛 \times 𝑚}$ , $𝐶 𝐴 = 𝐼_{𝑛}$ . By Proposition 2.4.23, $𝐴^{𝖳} 𝐶^{𝖳} =$ ${(𝐶 𝐴)}^{𝖳} =$ $𝐼_{𝑛}^{𝖳} =$ $𝐼_{𝑛}$ . So $𝐴^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ has a right inverse, and by Theorem 3.5.13 (applied to $𝐴^{𝖳}$ , which has $𝑛$ rows), $rank 𝐴^{𝖳} = 𝑛$ .

(e) False. Let $𝐴 = 0 \in 𝐹^{2 \times 2}$ , so $𝑘 = 0$ and $𝑁_{0} = 0$ . Then $𝐺 𝐴 𝐻 = 0 = 𝑁_{0}$ for every pair of invertible $𝐺$ , $𝐻$ , for instance $𝐺 = 𝐻 = 𝐼_{2}$ and $𝐺 = 𝐻 = 𝐸_{12}$ .

(f) True. Since $𝑚 > 𝑛$ , the map $𝑇_{𝐵} : 𝐹^{𝑚} \to 𝐹^{𝑛}$ is not injective, by the “moreover” part of Theorem 3.5.12: there is $𝐱 \neq 𝟎$ with $𝐵 𝐱 = 𝟎$ . Then $𝐴 𝐵 𝐱 = 𝟎$ , so $𝑇_{𝐴 𝐵}$ is not injective, and the $𝑚 \times 𝑚$ matrix $𝐴 𝐵$ is not invertible (Theorem 3.5.14).

Exercise 3.5.35.standard Claim. Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑛 \times 𝑚}$ with $𝐵 𝐴 = 𝐼_{𝑛}$ . Then $𝐴 𝐵 = 𝐼_{𝑚}$ .

Proof. Let $𝑃 = 𝐴 𝐵$ . Then $𝑃^{2} =$ $𝐴 (𝐵 𝐴) 𝐵 =$ $𝐴 𝐼_{𝑛} 𝐵 =$ $𝐴 𝐵 =$ $𝑃$ . Multiplying $𝑃^{2} = 𝑃$ on the left by $𝑃^{- 1}$ gives $𝑃 = 𝐼_{𝑚}$ .

(a)Find the error.
(b)Give a counterexample to the claim.
(c)Show that whenever $𝐵 𝐴 = 𝐼_{𝑛}$ , the matrix $𝑃 = 𝐴 𝐵$ satisfies $𝑃^{2} = 𝑃$ , and that $𝑃 = 𝐼_{𝑚}$ if and only if $𝑚 = 𝑛$ .

Solution.

Uses. Corollary 3.5.15 (Invertible matrices are square), Theorem 3.5.23 (One-sided inverses of square matrices), Definition 2.5.12 (Invertible)

Hint 1. Which step assumes something that has not been shown?

Hint 2. For (b), take

𝑛 = 1

and

𝑚 = 2

Hint 3. For (c), if

𝑃 = 𝐼_{𝑚}

, then

𝐵

is both a left and a right inverse of

𝐴

. What does Corollary 3.5.15 say?

Sketch. (a)

𝑃^{- 1}

need not exist; the argument assumes the conclusion that

𝑃

is invertible. (b)

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

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

𝐵 𝐴 = 𝐼_{1}

but

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

. (c)

𝑃^{2} = 𝑃

as computed. If

𝑚 = 𝑛

, then

𝐴 𝐵 = 𝐼_{𝑛}

by Theorem 3.5.23; if

𝐴 𝐵 = 𝐼_{𝑚}

, then

𝐴

is invertible, so

𝑚 = 𝑛

by Corollary 3.5.15.

(a) The computation $𝑃^{2} = 𝑃$ is correct. The error is the last step: it multiplies by $𝑃^{- 1}$ , but nothing shows that $𝑃$ is invertible. In fact, an invertible $𝑃$ with $𝑃^{2} = 𝑃$ is $𝐼_{𝑚}$ , so assuming that $𝑃$ is invertible is assuming the conclusion.

(b) Let $𝐴 = (\begin{matrix} 1 \\ 0 \end{matrix}) \in 𝐹^{2 \times 1}$ and $𝐵 = (\begin{matrix} 1 & 0 \end{matrix}) \in 𝐹^{1 \times 2}$ . Then $𝐵 𝐴 = (1) = 𝐼_{1}$ , but $𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) \neq 𝐼_{2}$ .

(c) $𝑃^{2} = 𝑃$ holds whenever $𝐵 𝐴 = 𝐼_{𝑛}$ , by the computation in the “proof”. If $𝑚 = 𝑛$ , then $𝐵 𝐴 = 𝐼_{𝑛}$ gives $𝐴 𝐵 = 𝐼_{𝑛}$ by Theorem 3.5.23. Conversely, if $𝑃 = 𝐴 𝐵 = 𝐼_{𝑚}$ , then $𝐴 𝐵 = 𝐼_{𝑚}$ and $𝐵 𝐴 = 𝐼_{𝑛}$ , so $𝐴$ is invertible (Definition 2.5.12) and $𝑚 = 𝑛$ by Corollary 3.5.15(c). So for $𝑚 > 𝑛$ (the only other possibility, by Corollary 3.5.15(a)), $𝑃$ is an idempotent different from $𝐼_{𝑚}$ ; in (b) it is the projection $(𝑥_{1}, 𝑥_{2}) \mapsto (𝑥_{1}, 0)$ .

Exercise 3.5.36.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , $𝐵 \in 𝐹^{𝑝 \times 𝑞}$ , and $𝐶 \in 𝐹^{𝑚 \times 𝑞}$ .

(a)Show that $rank (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐵 \end{matrix}) =$ $rank 𝐴 +$ $rank 𝐵$ .
(b)Show that $rank (\begin{matrix} 𝐴 & 𝐶 \\ 0 & 𝐵 \end{matrix}) \geq$ $rank 𝐴 +$ $rank 𝐵$ , and give an example where the inequality is strict.

Solution.

Uses. Proposition 3.5.2 (First properties of rank), Definition 2.4.33 (Block matrix), Definition 1.3.10 (Span)

Hint 1. Use Proposition 3.5.2(d): the rank counts the columns that are not combinations of earlier columns.

Hint 2. A combination of earlier columns of

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

has top block a combination of columns of

𝐴

and bottom block a combination of columns of

𝐵

. Treat the first

𝑛

columns and the last

𝑞

columns separately.

Hint 3. For (b), only the bottom block of a column

(𝐜_{𝑙}; 𝐛_{𝑙})

is needed to show it is new. For strictness, try

1 \times 1

blocks.

Sketch. (a) For

𝑗 \leq 𝑛

(𝐚_{𝑗}; 𝟎)

is a combination of earlier columns iff

𝐚_{𝑗}

is one of

𝐚_{1}, \dots, 𝐚_{𝑗 - 1}

. For

(𝟎; 𝐛_{𝑙})

, a combination

\sum 𝑐_{𝑖} (𝐚_{𝑖}; 𝟎) +

\sum_{𝑖 < 𝑙} 𝑑_{𝑖} (𝟎; 𝐛_{𝑖})

equals it iff

\sum 𝑐_{𝑖} 𝐚_{𝑖} = 𝟎

and

\sum 𝑑_{𝑖} 𝐛_{𝑖} = 𝐛_{𝑙}

, which is possible iff

𝐛_{𝑙} \in

span (𝐛_{1}, \dots, 𝐛_{𝑙 - 1})

. Count with Proposition 3.5.2(d). (b) The same count works for the first

𝑛

columns, and a column

(𝐜_{𝑙}; 𝐛_{𝑙})

with

𝐛_{𝑙}

new is new, by looking at bottom blocks. Strict:

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

Write $𝐚_{1}, \dots, 𝐚_{𝑛}$ for the columns of $𝐴$ , $𝐛_{1}, \dots, 𝐛_{𝑞}$ for those of $𝐵$ , and $𝐜_{1}, \dots, 𝐜_{𝑞}$ for those of $𝐶$ . For column vectors $𝐮 \in 𝐹^{𝑚}$ and $𝐯 \in 𝐹^{𝑝}$ , write $(𝐮; 𝐯) \in 𝐹^{𝑚 + 𝑝}$ for the column with $𝐮$ on top of $𝐯$ . By Proposition 3.5.2(d), the rank of a matrix is the number of its new columns, those not in the span of the columns before them.

(a) The columns of $𝑀 = (\begin{matrix} 𝐴 & 0 \\ 0 & 𝐵 \end{matrix})$ are $(𝐚_{1}; 𝟎),$ $\dots,$ $(𝐚_{𝑛}; 𝟎),$ $(𝟎; 𝐛_{1}),$ $\dots,$ $(𝟎; 𝐛_{𝑞})$ . For $𝑗 \leq 𝑛$ , the combinations of the earlier columns are the vectors $(\sum_{𝑖 < 𝑗} 𝑐_{𝑖} 𝐚_{𝑖}; 𝟎)$ , so $(𝐚_{𝑗}; 𝟎)$ is new in $𝑀$ if and only if $𝐚_{𝑗}$ is new in $𝐴$ . For $1 \leq 𝑙 \leq 𝑞$ , the combinations of the columns before $(𝟎; 𝐛_{𝑙})$ are the vectors

(\sum_{𝑖 = 1}^{𝑛} 𝑐_{𝑖} 𝐚_{𝑖}; \sum_{𝑖 < 𝑙} 𝑑_{𝑖} 𝐛_{𝑖}) .

Such a vector equals $(𝟎; 𝐛_{𝑙})$ for some choice of scalars if and only if $𝐛_{𝑙} \in$ $span (𝐛_{1}, \dots, 𝐛_{𝑙 - 1})$ : if $𝐛_{𝑙} =$ $\sum_{𝑖 < 𝑙} 𝑑_{𝑖} 𝐛_{𝑖}$ , take all $𝑐_{𝑖} = 0$ , and conversely the bottom block gives such an expression. So $(𝟎; 𝐛_{𝑙})$ is new in $𝑀$ if and only if $𝐛_{𝑙}$ is new in $𝐵$ . Counting, $rank 𝑀 =$ $rank 𝐴 +$ $rank 𝐵$ .

(b) For $𝑀^{'} = (\begin{matrix} 𝐴 & 𝐶 \\ 0 & 𝐵 \end{matrix})$ , the first $𝑛$ columns are as in (a), so exactly $rank 𝐴$ of them are new. Let $1 \leq 𝑙 \leq 𝑞$ with $𝐛_{𝑙}$ new in $𝐵$ . Every combination of the columns of $𝑀^{'}$ before $(𝐜_{𝑙}; 𝐛_{𝑙})$ has bottom block $\sum_{𝑖 < 𝑙} 𝑑_{𝑖} 𝐛_{𝑖}$ , which is not $𝐛_{𝑙}$ . So $(𝐜_{𝑙}; 𝐛_{𝑙})$ is new in $𝑀^{'}$ . Hence $𝑀^{'}$ has at least $rank 𝐴 + rank 𝐵$ new columns. For strict inequality, take $1 \times 1$ blocks $𝐴 = 𝐵 = (0)$ and $𝐶 = (1)$ : then $𝑀^{'} = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ has rank $1 > 0 + 0$ .

Exercise 3.5.37.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐲 \in 𝐹^{𝑚}$ . Show that exactly one of the following holds:

(i) $𝐴 𝐱 = 𝐲$ has a solution $𝐱 \in 𝐹^{𝑛}$ ;
(ii)there is $𝐳 \in 𝐹^{𝑚}$ with $𝐳^{𝖳} 𝐴 = 𝟎$ and $𝐳^{𝖳} 𝐲 \neq 0$ .

Then find such a $𝐳$ for the inconsistent system of Example 3.4.6, with $𝐲 = (4, 2, 6)$ .

Solution.

Uses. Corollary 3.4.4 (Consistency), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.3.8 (Properties of the output), Definition 2.4.1 (Matrix product)

Hint 1. If both held, compute

𝐳^{𝖳} 𝐴 𝐱

in two ways.

Hint 2. If (i) fails, Corollary 3.4.4 gives an

𝑖 > rank 𝐴

with

{(𝐺 𝐲)}_{𝑖} \neq 0

. Take

𝐳^{𝖳}

to be row

𝑖

𝐺

Sketch. Both cannot hold:

0 =

(𝐳^{𝖳} 𝐴) 𝐱 =

𝐳^{𝖳} 𝐲 \neq

0

. If (i) fails, some

𝑖 > rank 𝐴

has

{(𝐺 𝐲)}_{𝑖} \neq 0

; with

𝐳^{𝖳}

the

𝑖

th row of

𝐺

𝐳^{𝖳} 𝐴

is row

𝑖

𝐴_{𝑟}

, which is zero, and

𝐳^{𝖳} 𝐲 = {(𝐺 𝐲)}_{𝑖}

. For Example 3.4.6,

𝐳 = (- 1, - 1 / 2, 1)

and

𝐳^{𝖳} 𝐲 = 1

Not both. If $𝐴 𝐱 = 𝐲$ and $𝐳^{𝖳} 𝐴 = 𝟎$ , then $𝐳^{𝖳} 𝐲 =$ $𝐳^{𝖳} (𝐴 𝐱) =$ $(𝐳^{𝖳} 𝐴) 𝐱 =$ $0$ , so (ii) fails.

At least one. Suppose (i) fails. Let $𝐺$ be invertible with $𝐺 𝐴 = 𝐴_{𝑟}$ , and $𝑘 = rank 𝐴$ . By Corollary 3.4.4 there is an $𝑖$ with $𝑘 < 𝑖 \leq 𝑚$ and ${(𝐺 𝐲)}_{𝑖} \neq 0$ . Let $𝐳^{𝖳}$ be row $𝑖$ of $𝐺$ . By Definition 2.4.1, $𝐳^{𝖳} 𝐴$ is row $𝑖$ of $𝐺 𝐴 = 𝐴_{𝑟}$ , which is zero since $𝑖 > 𝑘$ (Proposition 3.3.8(a)), and $𝐳^{𝖳} 𝐲$ is the $𝑖$ th entry of $𝐺 𝐲$ , which is nonzero. So (ii) holds.

The example. In Example 3.4.6, $𝑘 = 2$ and the last row of $𝐺$ is $(- 1, - 1 / 2, 1)$ . So $𝐳 = (- 1, - 1 / 2, 1)$ , and indeed $𝐳^{𝖳} 𝐴 =$ $- (0, 0, 2, 4) -$ $\frac{1}{2} (2, 4, 2, 0) +$ $(1, 2, 3, 4) =$ $𝟎$ while $𝐳^{𝖳} 𝐲 = - 4 - 1 + 6 = 1$ . In words: minus the first equation, minus half the second, plus the third, reads $0 = 1$ . Such a $𝐳$ is a certificate of inconsistency that anyone can check without redoing the elimination.

Exercise 3.5.38.standard Let $𝐴, 𝐵, 𝐶 \in 𝐹^{𝑛 \times 𝑛}$ with $𝐴 𝐵 𝐶 = 𝐼_{𝑛}$ . Prove or disprove:

(a) $𝐵 𝐶 𝐴 = 𝐼_{𝑛}$ ;
(b) $𝐶 𝐴 𝐵 = 𝐼_{𝑛}$ ;
(c) $𝐵 𝐴 𝐶 = 𝐼_{𝑛}$ .

Solution.

Uses. Theorem 3.5.23 (One-sided inverses of square matrices)

Hint 1. Group

𝐴 𝐵 𝐶

𝐴 (𝐵 𝐶)

, or as

(𝐴 𝐵) 𝐶

, and apply Theorem 3.5.23.

Hint 2. For (c), take

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

with

𝐴

and

𝐵

invertible and

𝐴 𝐵 \neq 𝐵 𝐴

Sketch. (a)

𝐴 (𝐵 𝐶) = 𝐼_{𝑛}

gives

(𝐵 𝐶) 𝐴 = 𝐼_{𝑛}

. (b)

(𝐴 𝐵) 𝐶 = 𝐼_{𝑛}

gives

𝐶 (𝐴 𝐵) = 𝐼_{𝑛}

. (c) False: with

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

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

, and

𝐶 =

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

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

, we get

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

(a) True. $𝐴 (𝐵 𝐶) = 𝐼_{𝑛}$ , so by Theorem 3.5.23, $(𝐵 𝐶) 𝐴 = 𝐼_{𝑛}$ .

(b) True. $(𝐴 𝐵) 𝐶 = 𝐼_{𝑛}$ , so by Theorem 3.5.23, $𝐶 (𝐴 𝐵) = 𝐼_{𝑛}$ .

(c) False. Let $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix})$ . Then $𝐴 𝐵 = (\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix})$ , whose inverse is $𝐶 = (\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix})$ (check: $(\begin{matrix} 2 & 1 \\ 1 & 1 \end{matrix}) (\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}) =$ $(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$ ). So $𝐴 𝐵 𝐶 = 𝐼_{2}$ . But $𝐵 𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix})$ , and

𝐵 𝐴 𝐶 = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}) (\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}) = (\begin{matrix} 0 & 1 \\ - 1 & 3 \end{matrix}) \neq 𝐼_{2} .

This works over every field, since the $(1, 1)$ entry is $0 \neq 1$ . In general $𝐵 𝐴 𝐶 =$ $𝐵 𝐴 {(𝐴 𝐵)}^{- 1}$ , which is $𝐼_{𝑛}$ only if $𝐵 𝐴 = 𝐴 𝐵$ . Cyclic shifts of a product equal to $𝐼_{𝑛}$ are again $𝐼_{𝑛}$ , but other rearrangements need not be.

Exercise 3.5.39.hard Let

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

satisfy

𝐴 𝐵 = 𝐴 + 𝐵

. Show that

𝐴 𝐵 = 𝐵 𝐴

Solution.

Uses. Theorem 3.5.23 (One-sided inverses of square matrices), Proposition 2.4.14 (Algebra of matrices)

Techniques. Uniqueness gives existence (Technique 3.4.21)

Hint 1. Rewrite

𝐴 𝐵 - 𝐴 - 𝐵 = 0

so that it becomes a product equal to

𝐼_{𝑛}

. Add

𝐼_{𝑛}

to both sides.

Hint 2.

(𝐴 - 𝐼_{𝑛}) (𝐵 - 𝐼_{𝑛}) =

𝐼_{𝑛}

. Now use that a one-sided inverse of a square matrix is two-sided.

Sketch.

(𝐴 - 𝐼_{𝑛}) (𝐵 - 𝐼_{𝑛}) =

𝐴 𝐵 -

𝐴 -

𝐵 +

𝐼_{𝑛} =

𝐼_{𝑛}

. By Theorem 3.5.23,

(𝐵 - 𝐼_{𝑛}) (𝐴 - 𝐼_{𝑛}) =

𝐼_{𝑛}

as well, that is,

𝐵 𝐴 -

𝐴 -

𝐵 +

𝐼_{𝑛} =

𝐼_{𝑛}

. So

𝐵 𝐴 = 𝐴 + 𝐵 = 𝐴 𝐵

Expanding with the distributive laws (Proposition 2.4.14),

\begin{aligned} (𝐴 - 𝐼_{𝑛}) (𝐵 - 𝐼_{𝑛}) & = 𝐴 𝐵 - 𝐴 - 𝐵 + 𝐼_{𝑛} \\ = (𝐴 + 𝐵) - 𝐴 - 𝐵 + 𝐼_{𝑛} = 𝐼_{𝑛} . \end{aligned}

So $𝐵 - 𝐼_{𝑛}$ is a right inverse of the square matrix $𝐴 - 𝐼_{𝑛}$ . By Theorem 3.5.23 it is also a left inverse:

𝐼_{𝑛} = (𝐵 - 𝐼_{𝑛}) (𝐴 - 𝐼_{𝑛}) = 𝐵 𝐴 - 𝐵 - 𝐴 + 𝐼_{𝑛} .

Hence $𝐵 𝐴 = 𝐴 + 𝐵 = 𝐴 𝐵$ , as desired.

The proof computes nothing: the commutation comes entirely from Theorem 3.5.23, applied to the square matrix $𝐴 - 𝐼_{𝑛}$ .

Exercise 3.5.40.standard Let $𝑉$ and $𝑊$ be vector spaces over $𝐹$ , and let $𝑇 : 𝑉 \to 𝑊$ be linear.

(a)Suppose $𝑉$ has a basis $𝐯_{1}, \dots, 𝐯_{𝑛}$ and $𝑊$ is spanned by a finite list $𝐰_{1}, \dots, 𝐰_{𝑝}$ . Show that if $𝑇$ is injective, then $𝑇$ has a left inverse.
(b)Suppose $𝑊$ has a basis $𝐜_{1}, \dots, 𝐜_{𝑚}$ . Show that if $𝑇$ is surjective, then $𝑇$ has a right inverse. (No assumption on $𝑉$ is needed.)

Solution.

Uses. Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Proposition 1.5.14 (Appending a vector), Proposition 1.4.14 (The span is the smallest subspace containing a list), Definition 1.6.1 (Basis), Theorem 2.2.1 (Linear maps are determined by a basis)

Techniques. Check it on a basis (Technique 2.2.7), Construct a map by choosing it on a basis (Technique 2.2.4)

Hint 1. For (a), imitate the second approach to Proposition 3.5.9. First show that

𝑇 𝐯_{1}, \dots, 𝑇 𝐯_{𝑛}

is linearly independent.

Hint 2. Append to

𝑇 𝐯_{1}, \dots, 𝑇 𝐯_{𝑛}

each

𝐰_{𝑖}

that is not yet in the span. Then define

𝑆

on the resulting basis of

𝑊

Hint 3. For (b), choose a preimage of each

𝐜_{𝑖}

and define

𝑅

on the basis

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

Sketch. (a)

𝑇 𝐯_{1}, \dots, 𝑇 𝐯_{𝑛}

is independent since

ker 𝑇 = {𝟎}

. Appending each

𝐰_{𝑖}

not yet in the span keeps independence (Proposition 1.5.14) and ends with a list spanning

𝑊

, hence a basis. Define

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

and

𝑆 = 𝟎

on the appended vectors;

𝑆 \circ 𝑇

fixes each

𝐯_{𝑗}

, so it is

{id}_{𝑉}

. (b) Pick

𝐮_{𝑖}

with

𝑇 𝐮_{𝑖} = 𝐜_{𝑖}

and let

𝑅 (𝐜_{𝑖}) = 𝐮_{𝑖}

;

𝑇 \circ 𝑅

fixes each

𝐜_{𝑖}

, so it is

{id}_{𝑊}

(a) The images are independent. If $𝑐_{1} 𝑇 𝐯_{1} +$ $\dots +$ $𝑐_{𝑛} 𝑇 𝐯_{𝑛} =$ $𝟎$ , then $𝑇 (𝑐_{1} 𝐯_{1} + \dots + 𝑐_{𝑛} 𝐯_{𝑛}) =$ $𝟎$ by linearity, so $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑛} 𝐯_{𝑛} =$ $𝟎$ , because $ker 𝑇 = {𝟎}$ (Theorem 2.6.11), and all $𝑐_{𝑗} = 0$ because $𝐯_{1}, \dots, 𝐯_{𝑛}$ is independent.

Extending to a basis of $𝑊$ . Let ${ℒ︀}_{0} =$ $𝑇 𝐯_{1},$ $\dots,$ $𝑇 𝐯_{𝑛}$ , and for $𝑖 = 1, \dots, 𝑝$ let ${ℒ︀}_{𝑖} = {ℒ︀}_{𝑖 - 1}$ if $𝐰_{𝑖} \in span ({ℒ︀}_{𝑖 - 1})$ , and ${ℒ︀}_{𝑖} = {ℒ︀}_{𝑖 - 1}, 𝐰_{𝑖}$ otherwise. Each ${ℒ︀}_{𝑖}$ is independent by Proposition 1.5.14, and every $𝐰_{𝑖}$ lies in $span ({ℒ︀}_{𝑝})$ . So $span ({ℒ︀}_{𝑝})$ is a subspace containing a spanning list of $𝑊$ , hence equals $𝑊$ (Proposition 1.4.14), and ${ℒ︀}_{𝑝} =$ $𝑇 𝐯_{1},$ $\dots,$ $𝑇 𝐯_{𝑛},$ $𝐰_{𝑖_{1}},$ $\dots,$ $𝐰_{𝑖_{𝑡}}$ is a basis of $𝑊$ (Definition 1.6.1).

Defining $𝑆$ . By Theorem 2.2.1 there is a linear $𝑆 : 𝑊 \to 𝑉$ with $𝑆 (𝑇 𝐯_{𝑗}) = 𝐯_{𝑗}$ for each $𝑗$ and $𝑆 (𝐰_{𝑖_{𝑠}}) = 𝟎$ for each $𝑠$ . Then $(𝑆 \circ 𝑇) (𝐯_{𝑗}) =$ $𝐯_{𝑗}$ for every $𝑗$ , so the linear maps $𝑆 \circ 𝑇$ and ${id}_{𝑉}$ agree on a basis of $𝑉$ and are equal by the uniqueness in Theorem 2.2.1.

(b) Since $𝑇$ is surjective, for each $𝑖$ there is $𝐮_{𝑖} \in 𝑉$ with $𝑇 𝐮_{𝑖} = 𝐜_{𝑖}$ ; fix one. By Theorem 2.2.1 there is a linear $𝑅 : 𝑊 \to 𝑉$ with $𝑅 (𝐜_{𝑖}) = 𝐮_{𝑖}$ for each $𝑖$ . Then $(𝑇 \circ 𝑅) (𝐜_{𝑖}) =$ $𝐜_{𝑖}$ for every $𝑖$ , so $𝑇 \circ 𝑅 = {id}_{𝑊}$ , again by uniqueness in Theorem 2.2.1.

In (a), some finiteness assumption on $𝑊$ is what lets the extension stop; Section 4.1 develops this. In (b) the choice of the $𝐮_{𝑖}$ is where right inverses get their freedom, as in Exercise 3.5.33(a).

Exercise 3.5.41.hard This exercise shows that the number $𝑘$ in Theorem 3.5.27 is determined by $𝐴$ , and draws the consequences. Throughout, $𝑁_{𝑗} \in 𝐹^{𝑚 \times 𝑛}$ is as in Theorem 3.5.27.

(a)Let $𝑄 \in 𝐹^{𝑛 \times 𝑛}$ be invertible and $𝑘 \leq min (𝑚, 𝑛)$ . Show that $rank (𝑁_{𝑘} 𝑄) = 𝑘$ .
(b)Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . Show that if $𝐺 𝐴 𝐻 = 𝑁_{𝑗}$ for some invertible $𝐺$ and $𝐻$ , then $𝑗 = rank 𝐴$ .
(c)Show that $rank (𝐴 𝐻) = rank 𝐴$ for every invertible $𝐻 \in 𝐹^{𝑛 \times 𝑛}$ .
(d)Show that $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ satisfy $𝐵 = 𝐺 𝐴 𝐻$ for some invertible $𝐺$ , $𝐻$ if and only if $rank 𝐴 = rank 𝐵$ .

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Proposition 3.5.2 (First properties of rank), Theorem 2.4.34 (Block multiplication), Theorem 3.5.13 (Second Fundamental Theorem, completed), Theorem 2.4.2 (The matrix of a composite), Theorem 3.3.12 (Matrices in RREF)

Hint 1. For (a),

𝑁_{𝑘} 𝑄 = (\begin{matrix} 𝑄_{1} \\ 0 \end{matrix})

, where

𝑄_{1}

consists of the first

𝑘

rows of

𝑄

. Zero rows do not affect relations among the columns, so

rank (𝑁_{𝑘} 𝑄) =

rank 𝑄_{1}

by Proposition 3.5.2(d).

Hint 2.

𝑄_{1} = (\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix}) 𝑄

, and both

𝑇_{(\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix})}

and

𝑇_{𝑄}

are surjective. Apply Theorem 3.5.13 to

𝑄_{1}

Hint 3. For (b), compare a given normal form with the one from Theorem 3.5.27:

𝑁_{𝑗} =

(𝐺 𝐺_{0}^{- 1}) 𝑁_{𝑘} (𝐻_{0}^{- 1} 𝐻)

. For (c), find a normal form of

𝐴 𝐻

Sketch. (a) By block multiplication

𝑁_{𝑘} 𝑄 = (\begin{matrix} 𝑄_{1} \\ 0 \end{matrix})

, and its columns satisfy the same relations as those of

𝑄_{1}

, so

rank (𝑁_{𝑘} 𝑄) =

rank 𝑄_{1}

. As

𝑇_{𝑄_{1}} =

𝑇_{(\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix})} \circ

𝑇_{𝑄}

is surjective onto

𝐹^{𝑘}

rank 𝑄_{1} = 𝑘

. (b) With

𝐺_{0} 𝐴 𝐻_{0} = 𝑁_{𝑘}

𝑘 = rank 𝐴

𝑁_{𝑗} =

(𝐺 𝐺_{0}^{- 1}) 𝑁_{𝑘} (𝐻_{0}^{- 1} 𝐻)

, so

𝑗 =

rank 𝑁_{𝑗} =

rank (𝑁_{𝑘} 𝐻_{0}^{- 1} 𝐻) =

𝑘

by row invariance and (a). (c)

𝐺_{0} (𝐴 𝐻) (𝐻^{- 1} 𝐻_{0}) =

𝑁_{𝑘}

, so

rank (𝐴 𝐻) = 𝑘

by (b). (d) Use (c) and row invariance for

\Rightarrow

; both are equivalent to

𝑁_{𝑘}

for

\Leftarrow

(a) Partition $𝑄$ into its first $𝑘$ rows $𝑄_{1} \in 𝐹^{𝑘 \times 𝑛}$ and the remaining rows $𝑄_{2}$ , and $𝑁_{𝑘}$ into blocks with row sizes $𝑘, 𝑚 - 𝑘$ and column sizes $𝑘, 𝑛 - 𝑘$ . By Theorem 2.4.34,

𝑁_{𝑘} 𝑄 = (\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 0 \end{matrix}) (\begin{matrix} 𝑄_{1} \\ 𝑄_{2} \end{matrix}) = (\begin{matrix} 𝑄_{1} \\ 0 \end{matrix}) .

A list of scalars $𝑥_{1}, \dots, 𝑥_{𝑛}$ satisfies $\sum_{𝑙} 𝑥_{𝑙} 𝐪_{𝑙}^{'} = 𝟎$ for the columns $𝐪_{𝑙}^{'}$ of $(\begin{matrix} 𝑄_{1} \\ 0 \end{matrix})$ if and only if it satisfies $\sum_{𝑙} 𝑥_{𝑙} 𝐪_{𝑙} = 𝟎$ for the columns $𝐪_{𝑙}$ of $𝑄_{1}$ , since the extra entries are all $0$ . In particular, a column of $(\begin{matrix} 𝑄_{1} \\ 0 \end{matrix})$ is a combination of the earlier ones exactly when the same holds in $𝑄_{1}$ , so $rank (𝑁_{𝑘} 𝑄) =$ $rank 𝑄_{1}$ by Proposition 3.5.2(d).

Now $𝑄_{1} = (\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix}) 𝑄$ , where $(\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix}) \in 𝐹^{𝑘 \times 𝑛}$ (again by block multiplication). The map $𝑇_{(\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix})}$ sends $(𝑥_{1}, \dots, 𝑥_{𝑛})$ to $(𝑥_{1}, \dots, 𝑥_{𝑘})$ , so it is surjective onto $𝐹^{𝑘}$ , and $𝑇_{𝑄}$ is surjective because $𝑄$ is invertible. So $𝑇_{𝑄_{1}} =$ $𝑇_{(\begin{matrix} 𝐼_{𝑘} & 0 \end{matrix})} \circ$ $𝑇_{𝑄}$ (Theorem 2.4.2(b)) is surjective, and $rank 𝑄_{1} = 𝑘$ by Theorem 3.5.13. Hence $rank (𝑁_{𝑘} 𝑄) = 𝑘$ .

(b) By Theorem 3.5.27 there are invertible $𝐺_{0}$ , $𝐻_{0}$ with $𝐺_{0} 𝐴 𝐻_{0} = 𝑁_{𝑘}$ , where $𝑘 = rank 𝐴$ . So $𝐴 = 𝐺_{0}^{- 1} 𝑁_{𝑘} 𝐻_{0}^{- 1}$ , and if $𝐺 𝐴 𝐻 = 𝑁_{𝑗}$ , then

𝑁_{𝑗} = (𝐺 𝐺_{0}^{- 1}) 𝑁_{𝑘} (𝐻_{0}^{- 1} 𝐻) .

The matrix $𝑁_{𝑗}$ satisfies (R1)–(R4), so it is in RREF with $𝑗$ pivots (Theorem 3.3.12), and $rank 𝑁_{𝑗} = 𝑗$ . On the other hand, $𝐺 𝐺_{0}^{- 1}$ is invertible, so by Proposition 3.5.2(c) and (a) with $𝑄 = 𝐻_{0}^{- 1} 𝐻$ ,

rank 𝑁_{𝑗} = rank (𝑁_{𝑘} 𝐻_{0}^{- 1} 𝐻) = 𝑘 .

So $𝑗 = 𝑘 = rank 𝐴$ .

(c) With $𝐺_{0}$ , $𝐻_{0}$ , $𝑘$ as in (b), $𝐺_{0} (𝐴 𝐻) (𝐻^{- 1} 𝐻_{0}) =$ $𝐺_{0} 𝐴 𝐻_{0} =$ $𝑁_{𝑘}$ , and $𝐻^{- 1} 𝐻_{0}$ is invertible. By (b), applied to the matrix $𝐴 𝐻$ , $rank (𝐴 𝐻) =$ $𝑘 =$ $rank 𝐴$ .

(d) If $𝐵 = 𝐺 𝐴 𝐻$ , then $rank 𝐵 =$ $rank (𝐺 (𝐴 𝐻)) =$ $rank (𝐴 𝐻) =$ $rank 𝐴$ by Proposition 3.5.2(c) and (c). Conversely, if both have rank $𝑘$ , then $𝐺_{1} 𝐴 𝐻_{1} =$ $𝑁_{𝑘} =$ $𝐺_{2} 𝐵 𝐻_{2}$ for invertible $𝐺_{1}, 𝐻_{1}, 𝐺_{2}, 𝐻_{2}$ , so

𝐵 = (𝐺_{2}^{- 1} 𝐺_{1}) 𝐴 (𝐻_{1} 𝐻_{2}^{- 1}),

with both brackets invertible.

Exercise 3.5.42.standard A matrix

𝑃 \in 𝐹^{𝑛 \times 𝑛}

is idempotent if

𝑃^{2} = 𝑃

. Show that every

𝐴 \in 𝐹^{𝑛 \times 𝑛}

can be written as

𝐴 = 𝑆 𝑃

with

𝑆

invertible and

𝑃

idempotent, and also as

𝐴 = 𝑃^{'} 𝑆^{'}

with

𝑃^{'}

idempotent and

𝑆^{'}

invertible.

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Theorem 2.4.34 (Block multiplication), Proposition 2.4.14 (Algebra of matrices)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Start from

𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}

. Which square matrices are obviously idempotent?

Hint 2.

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

. Conjugates of idempotents are idempotent:

{(𝑋 𝑁_{𝑘} 𝑋^{- 1})}^{2} =

𝑋 𝑁_{𝑘}^{2} 𝑋^{- 1}

. Insert

𝐻^{- 1} 𝐻

𝐺 𝐺^{- 1}

in the right place.

Sketch.

𝐴 =

𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1} =

(𝐺^{- 1} 𝐻^{- 1}) (𝐻 𝑁_{𝑘} 𝐻^{- 1})

, and

{(𝐻 𝑁_{𝑘} 𝐻^{- 1})}^{2} =

𝐻 𝑁_{𝑘}^{2} 𝐻^{- 1} =

𝐻 𝑁_{𝑘} 𝐻^{- 1}

since

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

. Similarly

𝐴 =

(𝐺^{- 1} 𝑁_{𝑘} 𝐺) (𝐺^{- 1} 𝐻^{- 1})

By Theorem 3.5.27, $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ for invertible $𝐺$ , $𝐻$ and $𝑘 = rank 𝐴$ , so $𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}$ . Here $𝑁_{𝑘} \in 𝐹^{𝑛 \times 𝑛}$ , and by block multiplication $𝑁_{𝑘}^{2} =$ $(\begin{matrix} 𝐼_{𝑘}^{2} & 0 \\ 0 & 0 \end{matrix}) =$ $𝑁_{𝑘}$ . Now

𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1} = (𝐺^{- 1} 𝐻^{- 1}) (𝐻 𝑁_{𝑘} 𝐻^{- 1}) .

The first factor $𝑆 = 𝐺^{- 1} 𝐻^{- 1}$ is invertible, with inverse $𝐻 𝐺$ . The second, $𝑃 = 𝐻 𝑁_{𝑘} 𝐻^{- 1}$ , satisfies

𝑃^{2} = 𝐻 𝑁_{𝑘} (𝐻^{- 1} 𝐻) 𝑁_{𝑘} 𝐻^{- 1} = 𝐻 𝑁_{𝑘}^{2} 𝐻^{- 1} = 𝐻 𝑁_{𝑘} 𝐻^{- 1} = 𝑃 .

Similarly $𝐴 =$ $(𝐺^{- 1} 𝑁_{𝑘} 𝐺) (𝐺^{- 1} 𝐻^{- 1})$ , and $𝑃^{'} = 𝐺^{- 1} 𝑁_{𝑘} 𝐺$ is idempotent by the same computation, while $𝑆^{'} = 𝐺^{- 1} 𝐻^{- 1}$ is invertible.

So up to an invertible factor, every square matrix is an idempotent. The idempotent $𝑃 = 𝐻 𝑁_{𝑘} 𝐻^{- 1}$ fixes the first $𝑘$ columns of $𝐻$ and kills the others; in the language of Corollary 3.5.29, it is the projection onto the span of $𝐛_{1}, \dots, 𝐛_{𝑘}$ along the kernel of $𝐴$ .

Exercise 3.5.43.hard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ . A matrix $𝑋 \in 𝐹^{𝑛 \times 𝑚}$ is a generalized inverse of $𝐴$ if $𝐴 𝑋 𝐴 = 𝐴$ and $𝑋 𝐴 𝑋 = 𝑋$ .

(a)Show that every $𝐴$ has a generalized inverse.
(b)Show that if $𝐴$ has a left inverse or a right inverse, then every left inverse or right inverse of $𝐴$ is a generalized inverse.
(c)Let $𝑋$ satisfy $𝐴 𝑋 𝐴 = 𝐴$ . Show that whenever $𝐴 𝐱 = 𝐲$ is consistent, $𝐱 = 𝑋 𝐲$ is a solution.

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Theorem 2.4.34 (Block multiplication), Definition 2.4.21 (Transpose)

Hint 1. Solve the problem for

𝑁_{𝑘}

first: which

𝑛 \times 𝑚

matrix

𝑌

satisfies

𝑁_{𝑘} 𝑌 𝑁_{𝑘} = 𝑁_{𝑘}

and

𝑌 𝑁_{𝑘} 𝑌 = 𝑌

Hint 2.

𝑌 = 𝑁_{𝑘}^{𝖳}

works. Transport it with

𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}

: try

𝑋 = 𝐻 𝑁_{𝑘}^{𝖳} 𝐺

Hint 3. For (c), write

𝐲 = 𝐴 𝐱_{0}

and compute

𝐴 𝑋 𝐲

Sketch. (a) By block multiplication

𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} 𝑁_{𝑘} =

𝑁_{𝑘}

and

𝑁_{𝑘}^{𝖳} 𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} =

𝑁_{𝑘}^{𝖳}

. With

𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}

and

𝑋 = 𝐻 𝑁_{𝑘}^{𝖳} 𝐺

, the factors

𝐻^{- 1} 𝐻

and

𝐺 𝐺^{- 1}

cancel in

𝐴 𝑋 𝐴

and

𝑋 𝐴 𝑋

. (b) If

𝐶 𝐴 = 𝐼_{𝑛}

, then

𝐴 𝐶 𝐴 = 𝐴

and

𝐶 𝐴 𝐶 = 𝐶

; similarly for right inverses. (c) If

𝐲 = 𝐴 𝐱_{0}

, then

𝐴 𝑋 𝐲 =

𝐴 𝑋 𝐴 𝐱_{0} =

𝐴 𝐱_{0} =

𝐲

(a) First take $𝐴 = 𝑁_{𝑘}$ , and let $𝑌 = 𝑁_{𝑘}^{𝖳} \in 𝐹^{𝑛 \times 𝑚}$ , which has $1$ in positions $(1, 1), \dots, (𝑘, 𝑘)$ and $0$ elsewhere. By block multiplication, $𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} \in$ $𝐹^{𝑚 \times 𝑚}$ has the block form $(\begin{matrix} 𝐼_{𝑘} & 0 \\ 0 & 0 \end{matrix})$ , and then

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

where the second factor is $𝑁_{𝑘} \in 𝐹^{𝑚 \times 𝑛}$ . In the same way $𝑁_{𝑘}^{𝖳} 𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} =$ $𝑁_{𝑘}^{𝖳}$ .

For general $𝐴$ , take $𝐺$ , $𝐻$ invertible with $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ (Theorem 3.5.27), so $𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}$ , and let $𝑋 = 𝐻 𝑁_{𝑘}^{𝖳} 𝐺$ . Then

\begin{aligned} 𝐴 𝑋 𝐴 & = 𝐺^{- 1} 𝑁_{𝑘} (𝐻^{- 1} 𝐻) 𝑁_{𝑘}^{𝖳} (𝐺 𝐺^{- 1}) 𝑁_{𝑘} 𝐻^{- 1} \\ = 𝐺^{- 1} 𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} 𝑁_{𝑘} 𝐻^{- 1} = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1} = 𝐴, \\ 𝑋 𝐴 𝑋 & = 𝐻 𝑁_{𝑘}^{𝖳} (𝐺 𝐺^{- 1}) 𝑁_{𝑘} (𝐻^{- 1} 𝐻) 𝑁_{𝑘}^{𝖳} 𝐺 \\ = 𝐻 𝑁_{𝑘}^{𝖳} 𝑁_{𝑘} 𝑁_{𝑘}^{𝖳} 𝐺 = 𝐻 𝑁_{𝑘}^{𝖳} 𝐺 = 𝑋 . \end{aligned}

(b) If $𝐶 𝐴 = 𝐼_{𝑛}$ , then $𝐴 𝐶 𝐴 =$ $𝐴 (𝐶 𝐴) =$ $𝐴$ and $𝐶 𝐴 𝐶 =$ $(𝐶 𝐴) 𝐶 =$ $𝐶$ . If $𝐴 𝐶 = 𝐼_{𝑚}$ , then $𝐴 𝐶 𝐴 =$ $(𝐴 𝐶) 𝐴 =$ $𝐴$ and $𝐶 𝐴 𝐶 =$ $𝐶 (𝐴 𝐶) =$ $𝐶$ .

(c) If $𝐴 𝐱 = 𝐲$ is consistent, say $𝐲 = 𝐴 𝐱_{0}$ , then $𝐴 (𝑋 𝐲) =$ $𝐴 𝑋 𝐴 𝐱_{0} =$ $𝐴 𝐱_{0} =$ $𝐲$ .

So a generalized inverse solves every consistent system $𝐴 𝐱 = 𝐲$ by a single matrix multiplication, even when $𝐴$ has neither kind of one-sided inverse. Generalized inverses are not unique: by (b) and Exercise 3.5.33(d), a non-square matrix with a one-sided inverse has more than one.

Exercise 3.5.44.hard Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

. Show that

𝐴

is not invertible if and only if there is a nonzero

𝐵 \in 𝐹^{𝑛 \times 𝑛}

with

𝐴 𝐵 = 𝐵 𝐴 = 0

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Corollary 3.5.25 (The invertible matrix theorem), Definition 2.4.1 (Matrix product)

Hint 1. One direction is quick: if

𝐴

is invertible and

𝐴 𝐵 = 0

, multiply by

𝐴^{- 1}

Hint 2. For the other, solve the problem for

𝑁_{𝑘}

with

𝑘 < 𝑛

first. Which nonzero matrix

𝑈

has

𝑁_{𝑘} 𝑈 = 𝑈 𝑁_{𝑘} = 0

Hint 3. Take

𝑈

with a single

1

in position

(𝑛, 𝑛)

, and transport it:

𝐵 = 𝐻 𝑈 𝐺

Sketch. If

𝐴

is invertible and

𝐴 𝐵 = 0

, then

𝐵 = 𝐴^{- 1} 𝐴 𝐵 = 0

. If not,

𝑘 = rank 𝐴 < 𝑛

and

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

. The matrix

𝑈

with a single

1

in position

(𝑛, 𝑛)

has

𝑁_{𝑘} 𝑈 = 0

and

𝑈 𝑁_{𝑘} = 0

, because column

𝑛

and row

𝑛

𝑁_{𝑘}

are zero. Then

𝐵 = 𝐻 𝑈 𝐺 \neq 0

satisfies

𝐴 𝐵 =

𝐺^{- 1} 𝑁_{𝑘} 𝑈 𝐺 =

0

and

𝐵 𝐴 =

𝐻 𝑈 𝑁_{𝑘} 𝐻^{- 1} =

0

If $𝐴$ is invertible and $𝐴 𝐵 = 0$ , then $𝐵 = 𝐴^{- 1} (𝐴 𝐵) = 0$ . So an invertible $𝐴$ has no such $𝐵$ .

Conversely, suppose $𝐴$ is not invertible, so $𝑘 = rank 𝐴 < 𝑛$ (Corollary 3.5.25). By Theorem 3.5.27, $𝐺 𝐴 𝐻 = 𝑁_{𝑘}$ for invertible $𝐺$ , $𝐻$ , so $𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}$ . Let $𝑈 \in 𝐹^{𝑛 \times 𝑛}$ have entry $1$ in position $(𝑛, 𝑛)$ and $0$ elsewhere. Since $𝑘 < 𝑛$ , column $𝑛$ and row $𝑛$ of $𝑁_{𝑘}$ are zero. By Definition 2.4.1, $𝑁_{𝑘} 𝑈$ has as its only possibly nonzero column $𝑁_{𝑘} 𝐞_{𝑛}$ , which is column $𝑛$ of $𝑁_{𝑘}$ , so $𝑁_{𝑘} 𝑈 = 0$ ; and $𝑈 𝑁_{𝑘}$ has as its only possibly nonzero row $𝐞_{𝑛}^{𝖳} 𝑁_{𝑘}$ , which is row $𝑛$ of $𝑁_{𝑘}$ , so $𝑈 𝑁_{𝑘} = 0$ . Let $𝐵 = 𝐻 𝑈 𝐺$ . Then $𝐵 \neq 0$ , since otherwise $𝑈 = 𝐻^{- 1} 𝐵 𝐺^{- 1} = 0$ , and

\begin{aligned} 𝐴 𝐵 & = 𝐺^{- 1} 𝑁_{𝑘} (𝐻^{- 1} 𝐻) 𝑈 𝐺 = 𝐺^{- 1} (𝑁_{𝑘} 𝑈) 𝐺 = 0, \\ 𝐵 𝐴 & = 𝐻 𝑈 (𝐺 𝐺^{- 1}) 𝑁_{𝑘} 𝐻^{- 1} = 𝐻 (𝑈 𝑁_{𝑘}) 𝐻^{- 1} = 0, \end{aligned}

as desired. (In fact $𝐵 = 𝐻 𝑈 𝐺$ has rank $1$ , the rank of $𝑈$ , by Exercise 3.5.41(c) and Proposition 3.5.2(c).)

Exercise 3.5.45.hard

(a)Let $𝐹$ be a field with at least three elements. Show that every $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is the sum of two invertible matrices.
(b)Show that (a) fails for $𝐹 = 𝔽_{2}$ and $𝑛 = 1$ .

Solution.

Uses. Theorem 3.5.27 (Rank normal form), Corollary 3.5.24 (Products of square matrices)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. If

𝐺 𝐴 𝐻 = 𝑁_{𝑘}

and

𝑁_{𝑘} = 𝐷_{1} + 𝐷_{2}

with

𝐷_{1}

𝐷_{2}

invertible, what can you say about

𝐴

Hint 2. Choose

𝑐 \in 𝐹

with

𝑐 \neq 0, 1

. Split each diagonal entry of

𝑁_{𝑘}

, which is

1

0

, as a sum of two nonzero scalars.

Sketch. (a)

𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}

, so it suffices to split

𝑁_{𝑘}

. With

𝑐 \neq 0, 1

, let

𝐷_{1}

be diagonal with entries

𝑐

(

𝑘

times) and then

1

, and

𝐷_{2}

diagonal with entries

1 - 𝑐

(

𝑘

times) and then

- 1

. Both are invertible and

𝐷_{1} + 𝐷_{2} = 𝑁_{𝑘}

; then

𝐴 =

𝐺^{- 1} 𝐷_{1} 𝐻^{- 1} +

𝐺^{- 1} 𝐷_{2} 𝐻^{- 1}

. (b) The only invertible

1 \times 1

matrix over

𝔽_{2}

(1)

, and

(1) + (1) = (0)

(a) By Theorem 3.5.27, $𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}$ with $𝐺$ , $𝐻$ invertible. Suppose $𝑁_{𝑘} = 𝐷_{1} + 𝐷_{2}$ with $𝐷_{1}$ , $𝐷_{2}$ invertible. Then

𝐴 = 𝐺^{- 1} 𝐷_{1} 𝐻^{- 1} + 𝐺^{- 1} 𝐷_{2} 𝐻^{- 1},

and each term is a product of invertible matrices, hence invertible (Corollary 3.5.24). So it suffices to split $𝑁_{𝑘}$ .

Since $𝐹$ has at least three elements, there is $𝑐 \in 𝐹$ with $𝑐 \neq 0$ and $𝑐 \neq 1$ . Let $𝐷_{1}$ be the diagonal matrix with diagonal entries $𝑐, \dots, 𝑐$ ( $𝑘$ times) followed by $1, \dots, 1$ ( $𝑛 - 𝑘$ times), and $𝐷_{2}$ the diagonal matrix with entries $1 - 𝑐, \dots, 1 - 𝑐$ ( $𝑘$ times) followed by $- 1, \dots, - 1$ . Their sum is diagonal with entries $𝑐 + (1 - 𝑐) = 1$ ( $𝑘$ times) and $1 + (- 1) = 0$ , that is, $𝑁_{𝑘}$ . A diagonal matrix whose diagonal entries $𝑑_{𝑖}$ are all nonzero is invertible, with inverse the diagonal matrix with entries $𝑑_{𝑖}^{- 1}$ ; and $𝑐$ , $1$ , $1 - 𝑐$ , $- 1$ are all nonzero. So $𝐷_{1}$ and $𝐷_{2}$ are invertible.

(b) Over $𝔽_{2}$ , a $1 \times 1$ matrix $(𝑎)$ is invertible if and only if $𝑎 \neq 0$ , that is, $𝑎 = 1$ . The only sum of two invertible $1 \times 1$ matrices is $(1) + (1) = (0)$ , so $(1)$ is not such a sum.

Exercise 3.5.46.challenge Show that for

𝑛 \geq 2

, every

𝐴 \in 𝔽_{2}^{𝑛 \times 𝑛}

is the sum of two invertible matrices. (Compare Exercise 3.5.45.)

Solution.

Uses. Exercise 3.5.45, Theorem 3.5.27 (Rank normal form), Theorem 2.4.34 (Block multiplication), Theorem 3.3.23 (Invertibility and RREF), Theorem 3.5.23 (One-sided inverses of square matrices), Corollary 3.5.24 (Products of square matrices)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. As in Exercise 3.5.45, it suffices to write each

𝑁_{𝑘} \in 𝔽_{2}^{𝑛 \times 𝑛}

as a sum of two invertible matrices. Diagonal splittings are impossible now, since the only nonzero scalar is

1

Hint 2. Work with small diagonal blocks. Split

(0) = (1) + (1)

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

, and

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

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

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

. A block diagonal matrix with invertible blocks is invertible.

Hint 3. The blocks above handle every

𝑁_{𝑘}

except

𝑁_{𝑛} = 𝐼_{𝑛}

for odd

𝑛

. For that you need a

3 \times 3

block: find an invertible

𝑋

such that

𝐼_{3} + 𝑋

is also invertible.

Sketch. Reduce to

𝑁_{𝑘}

as in Exercise 3.5.45. Write

𝑁_{𝑘}

as block diagonal with blocks

𝐼_{2}

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

(0)

, and

𝐼_{3}

, each split into two invertible blocks:

(0) = (1) + (1)

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

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

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

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

𝐼_{3} = 𝑋 + (𝐼_{3} + 𝑋)

with

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

. For

𝑘

even use

𝑘 / 2

blocks

𝐼_{2}

; for

𝑘

odd and

𝑘 < 𝑛

use one

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

; for

𝑘 = 𝑛

odd use one

𝐼_{3}

. The remaining diagonal positions are

(0)

blocks.

As in the proof of Exercise 3.5.45(a), $𝐴 = 𝐺^{- 1} 𝑁_{𝑘} 𝐻^{- 1}$ , and it suffices to write $𝑁_{𝑘} = 𝑋 + 𝑌$ with $𝑋$ , $𝑌$ invertible. We use block diagonal matrices (Theorem 2.4.34): if $𝑋 =$ $diag (𝑋_{1}, \dots, 𝑋_{𝑟})$ and $𝑌 =$ $diag (𝑌_{1}, \dots, 𝑌_{𝑟})$ are block diagonal with the same block sizes, then $𝑋 +$ $𝑌 =$ $diag (𝑋_{1} + 𝑌_{1}, \dots, 𝑋_{𝑟} + 𝑌_{𝑟})$ , and if each $𝑋_{𝑖}$ is invertible, then $𝑋$ is invertible, with inverse $diag (𝑋_{1}^{- 1}, \dots, 𝑋_{𝑟}^{- 1})$ , by block multiplication.

Building blocks. Over $𝔽_{2}$ :

$(0) = (1) + (1)$ .
$𝐼_{2} = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) + (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ , and $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}) =$ $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) +$ $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ . Here $(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ reduces to $𝐼_{2}$ by adding row $1$ to row $2$ and then row $2$ to row $1$ ; $(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ reduces to $𝐼_{2}$ by a swap and then adding row $2$ to row $1$ ; and $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ is a swap. So all three are invertible (Theorem 3.3.23).
$𝐼_{3} = 𝑋 + (𝐼_{3} + 𝑋)$ with
$𝑋 = (\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}), 𝐼_{3} + 𝑋 = (\begin{matrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix}) .$
Both are invertible: one checks that $𝑋 (\begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) = 𝐼_{3}$ and $(𝐼_{3} + 𝑋) (\begin{matrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix}) =$ $𝐼_{3}$ , and a one-sided inverse of a square matrix is an inverse (Theorem 3.5.23).

Assembling $𝑁_{𝑘}$ . The diagonal of $𝑁_{𝑘}$ is $𝑘$ ones followed by $𝑛 - 𝑘$ zeros. Partition it into consecutive diagonal blocks as follows, putting $(0)$ blocks on all remaining zero positions.

If $𝑘$ is even, use $𝑘 / 2$ blocks $𝐼_{2}$ .
If $𝑘$ is odd and $𝑘 < 𝑛$ , use $(𝑘 - 1) / 2$ blocks $𝐼_{2}$ and then one block $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , which covers the last one and the first zero.
If $𝑘 = 𝑛$ is odd, then $𝑛 \geq 3$ ; use one block $𝐼_{3}$ and $(𝑛 - 3) / 2$ blocks $𝐼_{2}$ .

In each case $𝑁_{𝑘}$ is block diagonal with blocks from the list above, so splitting each block as shown writes $𝑁_{𝑘}$ as a sum of two block diagonal matrices with invertible blocks, which are invertible.

Finally $𝐴 =$ $𝐺^{- 1} 𝑋 𝐻^{- 1} +$ $𝐺^{- 1} 𝑌 𝐻^{- 1}$ , a sum of two invertible matrices (Corollary 3.5.24). The case $𝑘 = 𝑛 = 1$ is exactly the one excluded by $𝑛 \geq 2$ .

More practice

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