3.3 Gauss–Jordan elimination

In Example 3.1.13 we solved the running system by eliminating unknowns, choosing each move by eye and stopping when the answer looked readable. To prove theorems with elimination we need a procedure with no judgment calls in it. This section states one, Gauss–Jordan elimination, proves that it terminates, and studies its output, the reduced row echelon form $rref (𝐴)$ . With the bookkeeping of Section 3.2, a whole run of the algorithm is recorded by one invertible matrix $𝐺$ with $𝐺 𝐴 = rref (𝐴)$ . The main theorem of the section says that $rref (𝐴)$ depends only on $𝐴$ : every way of row reducing $𝐴$ to a matrix of this shape ends at the same matrix. As a first application, we decide whether a square matrix is invertible, and compute its inverse, by row reduction.

3.3.1The algorithm

Intuition (How elimination is organized). Read the rows of $𝐴$ as equations and the columns as unknowns. Elimination uses one equation to remove one unknown from all the other equations, and the natural order is left to right. Find the first unknown $𝑥_{𝑗}$ that occurs in some equation, move such an equation to the top, divide it by its coefficient of $𝑥_{𝑗}$ , and subtract multiples of it from every other equation, so that $𝑥_{𝑗}$ occurs in no other equation. The top equation is now used up; we call its row pivoted. Then do the same with the equations that are left: find the leftmost unknown that still occurs in one of them, and so on.

Gauss–Jordan elimination clears the column of each new pivot above it as well as below it, so at the end each pivot is alone in its column. (Clearing only below gives Gaussian elimination, Section 3.3.6.) A column whose nonzero entries all lie in pivoted rows is skipped: it is already a combination of earlier pivot columns, and in Section 3.4 its unknown becomes a free variable.

In the algorithm below, $𝑀$ is the current matrix and $𝑘$ is the number of pivoted rows. The pivoted rows are always rows $1, \dots, 𝑘$ of $𝑀$ , and the other rows are unpivoted.

Algorithm 3.3.1 (Gauss–Jordan elimination)

Input: A matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .
Output: The matrix $rref (𝐴) \in 𝐹^{𝑚 \times 𝑛}$ , and its pivot columns $𝑝_{1} <$ $𝑝_{2} <$ $\dots <$ $𝑝_{𝑟}$ .

Start with $𝑀 = 𝐴$ and $𝑘 = 0$ .

Scan. Find the leftmost column

𝑗

𝑀

that has a nonzero entry in an unpivoted row, that is, in one of the rows

𝑘 + 1, \dots, 𝑚

. If there is no such column, halt and output

𝑀

Swap. If the entry of

𝑀

in position

(𝑘 + 1, 𝑗)

0

, swap row

𝑘 + 1

with the topmost row below it whose entry in column

𝑗

is nonzero.

Scale. Scale row

𝑘 + 1

by the inverse of its entry in column

𝑗

, so that this entry becomes

1

. (If it is

1

already, there is nothing to do.) Declare this entry a pivot, set

𝑝_{𝑘 + 1} = 𝑗

, and increase

𝑘

1

. Row

𝑘

is now pivoted.

Clear. For each row

𝑖 \neq 𝑘

whose entry

𝑐

in column

𝑗

is nonzero, add

- 𝑐

times row

𝑘

to row

𝑖

Repeat. Go back to step 1.

One execution of step 1 through step 4 that does not halt in step 1 is a pass. Each pass creates exactly one pivot, so after $𝑟$ passes the pivots sit in positions $(1, 𝑝_{1}),$ $(2, 𝑝_{2}),$ $\dots,$ $(𝑟, 𝑝_{𝑟})$ . (Later passes never move a pivoted row: swaps only involve unpivoted rows.) We call $𝑝_{1}, \dots, 𝑝_{𝑟}$ the pivot columns and rows $1, \dots, 𝑟$ the pivot rows. The leading entry of a nonzero row is its first nonzero entry, reading from the left.

Each step can be carried out. In step 2, column $𝑗$ has a nonzero entry in some unpivoted row, so if row $𝑘 + 1$ has a $0$ there, a row below it does not. In step 3 the entry is nonzero, so it has an inverse in $𝐹$ . In step 4 every operation adds a multiple of row $𝑘$ , which the step never changes, so the operations can be performed one at a time in any order with the same result. (Compare Exercise 3.1.35, where a row was used after it had been replaced.)

Remark 3.3.2 (The one free choice). Every step is determined by the current matrix except, in principle, step 2. The lecture’s version of that step says only “swap rows to make the topmost unpivoted entry of this column nonzero”, leaving open which row to bring up. We have fixed the choice (the topmost suitable row, and no swap when none is needed) so that the output is a function of

𝐴

. Other choices have their uses. By hand one might bring up a row whose entry is

1

, to avoid fractions; in floating-point arithmetic one brings up the entry of largest absolute value to limit rounding errors (partial pivoting). Whether a different choice can change the output is a real question. Corollary 3.3.18 answers it: it cannot.

Example 3.3.3 (A complete run). We run the algorithm on

𝐴 = (\begin{matrix} 0 & 0 & 2 & 4 \\ 2 & 4 & 2 & 0 \\ 1 & 2 & 3 & 4 \end{matrix}) \in ℚ^{3 \times 4} .

Pass 1. No row is pivoted, and column $1$ has nonzero entries, so $𝑗 = 1$ . The entry in position $(1, 1)$ is $0$ , and the topmost row below it with a nonzero entry in column $1$ is row $2$ , so we swap rows $1$ and $2$ . Then we scale row $1$ by $1 / 2$ and declare the pivot $(1, 1)$ , so $𝑝_{1} = 1$ . In column $1$ , row $2$ already has a $0$ and row $3$ has a $1$ , so we add $- 1$ times row $1$ to row $3$ :

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

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

Pass 2. Rows $2$ and $3$ are unpivoted. Column $2$ has entries $0, 0$ in these rows (the $2$ in row $1$ does not count, since row $1$ is pivoted), so the scan moves on and finds $𝑗 = 3$ . The entry in position $(2, 3)$ is $2 \neq 0$ , so there is no swap. We scale row $2$ by $1 / 2$ and declare the pivot $(2, 3)$ , so $𝑝_{2} = 3$ . Then we clear column $3$ above and below the pivot:

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

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

End. Only row $3$ is unpivoted, and it is zero, so the next scan finds no column and the algorithm halts after two passes. The output is

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

with pivot columns $𝑝_{1} = 1$ and $𝑝_{2} = 3$ . The run used six row operations, with elementary matrices (in the notation of Definition 3.2.2) $𝐸_{12}$ , $𝐸_{1, 1 / 2}$ , $𝐸_{1, - 1, 3}$ , $𝐸_{2, 1 / 2}$ , $𝐸_{2, - 1, 1}$ , $𝐸_{2, - 2, 3}$ .

The row reducer below performs the same run, one row operation at a time. Next to the current matrix $𝑀$ it shows the product $𝐺$ of the elementary matrices used so far, and $𝐺 𝐴 = 𝑀$ at every step (Theorem 3.3.10).

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

Gauss–Jordan elimination on the matrix of Example 3.3.3. Step forward and back to see each elementary matrix; pivots are boxed. Use “Edit” to row reduce your own matrix, over

ℚ

or over

𝔽_{𝑝}

The running system is also a good test. In Example 3.1.13 the four operations on its coefficient matrix were exactly the two passes of the algorithm (in pass $2$ we cleared row $3$ before row $1$ , which does not matter). So Example 3.2.8 already computed

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

together with the product $𝐺$ of the four elementary matrices.

Exercise 3.3.4.routine Run Gauss–Jordan elimination on

𝐵 = (\begin{matrix} 0 & 2 & 4 \\ 1 & 1 & 1 \\ 2 & 3 & 4 \end{matrix}) \in ℚ^{3 \times 3},

listing the elementary matrix of every row operation. What are the pivot columns?

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Proposition 3.2.7 (Row operations are left multiplications)

Hint 1. Pass 1 picks column

1

. The

(1, 1)

entry is

0

, so the first operation is a swap.

Hint 2. In pass 2 the pivot is in position

(2, 2)

and has to be scaled. Remember to clear above it as well as below it.

Sketch. The operations are

𝐸_{12}

𝐸_{1, - 2, 3}

𝐸_{2, 1 / 2}

𝐸_{2, - 1, 1}

𝐸_{2, - 1, 3}

, and

rref (𝐵)

has rows

(1, 0, - 1)

(0, 1, 2)

(0, 0, 0)

. The pivot columns are

1

and

2

Pass 1. Column $1$ has nonzero entries, so $𝑗 = 1$ . The $(1, 1)$ entry is $0$ and row $2$ is the topmost row with a nonzero entry in column $1$ , so we swap rows $1$ and $2$ ( $𝐸_{12}$ ). The new $(1, 1)$ entry is $1$ , so no scaling is needed; $𝑝_{1} = 1$ . Row $3$ has entry $2$ in column $1$ , so we add $- 2$ times row $1$ to row $3$ ( $𝐸_{1, - 2, 3}$ ):

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

Pass 2. Column $2$ has the nonzero entries $2, 1$ in the unpivoted rows $2, 3$ , so $𝑗 = 2$ , and the $(2, 2)$ entry is nonzero, so there is no swap. Scaling row $2$ by $1 / 2$ ( $𝐸_{2, 1 / 2}$ ) gives the row $(0, 1, 2)$ , and $𝑝_{2} = 2$ . Rows $1$ and $3$ have entry $1$ in column $2$ , so we add $- 1$ times row $2$ to each ( $𝐸_{2, - 1, 1}$ , $𝐸_{2, - 1, 3}$ ):

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

End. The only unpivoted row is zero, so the next scan finds no column and the algorithm halts. The pivot columns are $1$ and $2$ .

3.3.2Termination and the shape of the output

An algorithm is a construction, and a construction can be a proof: running Gauss–Jordan elimination on $𝐴$ will prove that $𝐴$ is row equivalent to a matrix of a very special shape. For that we have to show two things about every run, not just the one in Example 3.3.3. It stops, and what it stops with has the shape we want. The method is worth naming.

Technique 3.3.5 (Algorithms as proofs: invariants and termination). To prove that something exists, it is often enough to give a procedure that builds it. Two things then have to be proved about the procedure.

Termination. Find a quantity that moves in one direction at every step and cannot do so forever, such as a nonnegative integer that decreases, or an integer that increases and is bounded above. (Such a quantity is sometimes called a monovariant.)

Correctness. Find an invariant: a statement about the current state that is true at the start and that each step keeps true. When the procedure halts, the invariant together with the reason for halting gives the property of the output. Formally this is induction on the number of steps.

The art is in choosing the invariant. The property we want at the end is rarely preserved step by step on its own, and usually has to be strengthened, by adding facts about the intermediate states, until it is. Reach for this technique whenever a result says that some reduction is always possible (“every matrix can be brought to the form …”, “the process ends with …”). The canonical example is Gauss–Jordan elimination: termination is Proposition 3.3.6, and the invariant is Lemma 3.3.7. Later examples are Gram–Schmidt orthogonalization (Section 6.4) and the Euclidean algorithm for polynomials (Section 7.1); Exercise 3.2.54 is a small one.

Used in 15 places and 1 practice exercise

Proposition 3.3.6, Lemma 3.3.7, Proposition 3.3.8, Theorem 3.3.10, Theorem 3.3.12, Exercise 3.3.47, Exercise 3.3.53, Exercise 3.3.56, Exercise 3.6.11, Exercise 5.2.43, Algorithm 5.4.22, Exercise 5.4.48, Theorem 6.4.15, Theorem 7.1.45, Proposition 8.3.25; 1 practice exercise.

Proposition 3.3.6 (Termination). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. Gauss–Jordan elimination on

𝐴

halts after completing at most

𝑚

passes, and so performs at most

𝑚 (𝑚 + 1)

elementary row operations.

Proof.routine

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Find a quantity that changes in the same direction in every pass.

Hint 2. Track

𝑘

, the number of pivoted rows. What does each pass do to it, and how large can it get?

Sketch. Each pass increases

𝑘

1

in step 3, no step decreases it, and

𝑘 \leq 𝑚

, since once

𝑘 = 𝑚

there is no unpivoted row and step 1 halts. A pass performs at most one swap, one scaling, and

𝑚 - 1

replacements.

Every pass increases the number

𝑘

of pivoted rows by

1

, in step 3, and no step decreases

𝑘

. A pass can only begin if some row is unpivoted, that is, if

𝑘 < 𝑚

; when

𝑘 = 𝑚

, step 1 finds no column and halts. So at most

𝑚

passes are completed before the algorithm halts. Each pass performs at most one swap, at most one scaling, and at most

𝑚 - 1

replacements (one for each row other than row

𝑘

), so at most

𝑚 + 1

row operations. In total there are at most

𝑚 (𝑚 + 1)

. □

Now for the shape of the output. In Example 3.3.3 the pivots formed a staircase descending to the right, each pivot was alone in its column, and the leftover row was zero. The first two facts are what each pass sets up for its own pivot; the real issue is that later passes must not undo the work of earlier ones.

Intuition (Choosing the invariant). The obvious invariant is that the current matrix is

𝐺 𝐴

for a product

𝐺

of elementary matrices, but it says nothing about the shape. For the shape we want three facts about the pivots found so far: each pivot column is a standard basis vector, the pivots descend to the right, and each pivot row vanishes to the left of its pivot. The first one maintains itself. A later pass swaps and scales unpivoted rows and adds multiples of an unpivoted row to other rows, and every unpivoted row has a

0

in column

𝑝_{𝑠}

, because that column is

𝐞_{𝑠}

. The other two depend on where the next pivot is found. They are safe if the unpivoted rows vanish in every column up to the last pivot, so we add this to the invariant. It is exactly what choosing the leftmost column in step 1, followed by clearing, keeps true.

Lemma 3.3.7 (The loop invariant). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , and suppose Gauss–Jordan elimination on $𝐴$ has completed $𝑘$ passes, with pivot columns $𝑝_{1}, \dots, 𝑝_{𝑘}$ and current matrix $𝑀$ . Put $𝑝_{0} = 0$ . Then:

(a) $𝑀 = 𝐺 𝐴$ for some product $𝐺$ of elementary matrices;
(b) $𝑝_{1} <$ $𝑝_{2} <$ $\dots <$ $𝑝_{𝑘}$ ;
(c)for $1 \leq 𝑠 \leq 𝑘$ , column $𝑝_{𝑠}$ of $𝑀$ is $𝐞_{𝑠}$ ;
(d)for $1 \leq 𝑠 \leq 𝑘$ , row $𝑠$ of $𝑀$ has zeros in columns $1, \dots, 𝑝_{𝑠} - 1$ ;
(e)rows $𝑘 + 1, \dots, 𝑚$ of $𝑀$ have zeros in columns $1, \dots, 𝑝_{𝑘}$ .

Proof.standard

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Proposition 3.2.7 (Row operations are left multiplications), induction on $𝑘$

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Induct on

𝑘

. In pass

𝑘 + 1

, let

𝑗

be the column chosen by step 1. What does the choice of

𝑗

say about rows

𝑘 + 1, \dots, 𝑚

in columns

1, \dots, 𝑗 - 1

Hint 2. Let

𝐮

be row

𝑘 + 1

after step 3. Every operation of the pass either moves or scales unpivoted rows, or adds a multiple of

𝐮

to another row. Where is

𝐮

zero?

Hint 3. For (b), use (e) for the old

𝑘

: the unpivoted rows vanish in columns

1, \dots, 𝑝_{𝑘}

, so the scan cannot stop before column

𝑝_{𝑘} + 1

Sketch. By the choice of

𝑗

, rows

𝑘 + 1, \dots, 𝑚

vanish in columns

1, \dots, 𝑗 - 1

, and so does the new pivot row

𝐮

; by (e),

𝑗 > 𝑝_{𝑘}

. The pass only swaps and scales unpivoted rows and adds multiples of

𝐮

, so columns

𝑝_{𝑠}

with

𝑠 \leq 𝑘

and the zeros in (d) are untouched, while step 4 turns column

𝑗

into

𝐞_{𝑘 + 1}

. Rows

𝑘 + 2, \dots, 𝑚

are old unpivoted rows plus multiples of

𝐮

, so they vanish in columns

1, \dots, 𝑗

We induct on $𝑘$ . Before the first pass, $𝑘 = 0$ and $𝑀 = 𝐴 = 𝐼_{𝑚} 𝐴$ , and (b)–(e) say nothing.

Suppose that (a)–(e) hold after $𝑘$ passes, with current matrix $𝑀$ , and that pass $𝑘 + 1$ takes place, with column $𝑗$ chosen in step 1. Let $𝑀^{'}$ be the matrix after the pass. By the choice of $𝑗$ as the leftmost suitable column,

rows 𝑘 + 1, \dots, 𝑚 of 𝑀 have zeros in columns 1, \dots, 𝑗 - 1 .

(3.3.1)

The pass does three things. step 2 may exchange two rows among rows $𝑘 + 1, \dots, 𝑚$ . step 3 scales row $𝑘 + 1$ ; call the resulting row $𝐮$ . step 4 adds multiples of $𝐮$ to other rows and leaves row $𝑘 + 1$ equal to $𝐮$ . By (3.3.1), $𝐮$ has zeros in columns $1, \dots, 𝑗 - 1$ , and by step 3 it has entry $1$ in column $𝑗$ .

(a) Each operation of the pass is left multiplication by an elementary matrix (Proposition 3.2.7). So $𝑀^{'} = 𝐸 𝑀 = (𝐸 𝐺) 𝐴$ , where $𝐸$ is the product of the elementary matrices of the pass, and $𝐸 𝐺$ is again a product of elementary matrices.

(b) If $𝑘 \geq 1$ , then by (e), rows $𝑘 + 1, \dots, 𝑚$ of $𝑀$ vanish in columns $1, \dots, 𝑝_{𝑘}$ , so the column $𝑗$ found by the scan satisfies $𝑗 > 𝑝_{𝑘}$ . Hence $𝑝_{1} <$ $\dots <$ $𝑝_{𝑘} <$ $𝑝_{𝑘 + 1} =$ $𝑗$ .

(c) Let $𝑠 \leq 𝑘$ . Column $𝑝_{𝑠}$ of $𝑀$ is $𝐞_{𝑠}$ , so its entries in rows $𝑘 + 1, \dots, 𝑚$ are $0$ . Steps step 2 and step 3 only exchange or scale entries in these rows, and step 4 adds multiples of $𝐮$ , which is a multiple of one of these rows and so also has entry $0$ in column $𝑝_{𝑠}$ . So column $𝑝_{𝑠}$ of $𝑀^{'}$ is still $𝐞_{𝑠}$ . For the new pivot: after step 3 the entry of row $𝑘 + 1$ in column $𝑗$ is $1$ , and each operation of step 4 changes a single row $𝑖 \neq 𝑘 + 1$ , replacing its entry $𝑐$ in column $𝑗$ by $𝑐 - 𝑐 \cdot 1 = 0$ . So column $𝑗$ of $𝑀^{'}$ is $𝐞_{𝑘 + 1}$ .

(d) Let $𝑠 \leq 𝑘$ . Row $𝑠$ is not touched by steps step 2 and step 3, and in step 4 it changes by a multiple of $𝐮$ , which vanishes in columns $1, \dots, 𝑗 - 1$ , a range containing $1, \dots, 𝑝_{𝑠} - 1$ . So row $𝑠$ of $𝑀^{'}$ still vanishes in columns $1, \dots, 𝑝_{𝑠} - 1$ . Row $𝑘 + 1$ of $𝑀^{'}$ is $𝐮$ , which vanishes in columns $1, \dots, 𝑗 - 1 = 𝑝_{𝑘 + 1} - 1$ .

(e) Let $𝑖 \geq 𝑘 + 2$ . Row $𝑖$ of $𝑀^{'}$ is one of the rows $𝑘 + 1, \dots, 𝑚$ of $𝑀$ (possibly moved by the swap) plus a multiple of $𝐮$ . By (3.3.1) both vanish in columns $1, \dots, 𝑗 - 1$ , so row $𝑖$ of $𝑀^{'}$ does too, and its entry in column $𝑗$ is $0$ by (c). So rows $𝑘 + 2, \dots, 𝑚$ of $𝑀^{'}$ vanish in columns $1, \dots, 𝑝_{𝑘 + 1}$ .

This completes the induction. □

Proposition 3.3.8 (Properties of the output). Let $𝑅$ be the output of Gauss–Jordan elimination on $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , with pivot columns $𝑝_{1} < \dots < 𝑝_{𝑟}$ . Then $𝑟 \leq min (𝑚, 𝑛)$ , and:

(a)rows $𝑟 + 1, \dots, 𝑚$ of $𝑅$ are zero;
(b)for $1 \leq 𝑠 \leq 𝑟$ , the leading entry of row $𝑠$ is the pivot, a $1$ in column $𝑝_{𝑠}$ ;
(c)for $1 \leq 𝑠 \leq 𝑟$ , column $𝑝_{𝑠}$ of $𝑅$ is $𝐞_{𝑠}$ .

In particular, $𝑅$ satisfies the following conditions.

(R1)Every zero row lies below every nonzero row.
(R2)The leading entry of every nonzero row is $1$ .
(R3)The leading entry of each nonzero row lies strictly to the right of the leading entry of every row above it.
(R4)In a column that contains the leading entry of some row, every other entry is $0$ .

Proof.routine

Uses. Lemma 3.3.7 (The loop invariant), Proposition 3.3.6 (Termination)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Apply Lemma 3.3.7 after the last pass, and ask why the algorithm halted.

Hint 2. The scan found no column with a nonzero entry in rows

𝑟 + 1, \dots, 𝑚

. What does that say about those rows?

Sketch. There are at most

𝑚

passes and the

𝑝_{𝑠}

are distinct columns, so

𝑟 \leq min (𝑚, 𝑛)

. The algorithm halted because rows

𝑟 + 1, \dots, 𝑚

have no nonzero entry, which is (a). Parts (b) and (c) are (c) and (d) of Lemma 3.3.7. Then (R1)–(R4) follow, using

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

for (R3).

The algorithm completes $𝑟$ passes and then halts. By Proposition 3.3.6, $𝑟 \leq 𝑚$ , and by Lemma 3.3.7(b), $𝑝_{1} < \dots < 𝑝_{𝑟}$ are $𝑟$ distinct columns, so $𝑟 \leq 𝑛$ .

(a) The algorithm halted because step 1 found no column with a nonzero entry in one of the rows $𝑟 + 1, \dots, 𝑚$ . So these rows are zero.

(b), (c) By Lemma 3.3.7(d), row $𝑠$ of $𝑅$ vanishes in columns $1, \dots, 𝑝_{𝑠} - 1$ , and by Lemma 3.3.7(c), column $𝑝_{𝑠}$ of $𝑅$ is $𝐞_{𝑠}$ , so the entry of row $𝑠$ in column $𝑝_{𝑠}$ is $1$ .

By (a) and (b), the nonzero rows of $𝑅$ are exactly rows $1, \dots, 𝑟$ , which gives (R1). Their leading entries are the pivots, which are $1$ and lie in the columns $𝑝_{1} < \dots < 𝑝_{𝑟}$ ; this gives (R2) and (R3). The columns containing leading entries are $𝑝_{1}, \dots, 𝑝_{𝑟}$ , so (R4) is (c). □

3.3.3Reduced row echelon form

Definition 3.3.9 (Reduced row echelon form). Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

. The reduced row echelon form of

𝐴

, written

rref (𝐴)

𝐴_{𝑟}

, is the output of Gauss–Jordan elimination (Algorithm 3.3.1) on

𝐴

. The pivots and pivot columns of

𝐴

are those found by this run; by Proposition 3.3.8(b), the pivots are the leading entries of the nonzero rows of

rref (𝐴)

. A matrix

𝑅

is in reduced row echelon form (or in RREF) if

rref (𝑅) = 𝑅

This is the lecture’s definition: $rref (𝐴)$ is whatever the algorithm outputs. It has the advantage of being concrete, and the drawback that it is not yet clear which matrices are in RREF, or whether a different way of row reducing $𝐴$ could end somewhere else. We settle both questions in this section and the next. First, the bookkeeping of Section 3.2 turns the run into one matrix.

Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ). For every $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ there is a matrix $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ that is a product of elementary matrices, and hence invertible, with

𝐺 𝐴 = rref (𝐴) .

Explicitly, $𝐺 = 𝐸_{𝑡} \dots 𝐸_{2} 𝐸_{1}$ , where $𝐸_{1}, \dots, 𝐸_{𝑡}$ are the elementary matrices of the row operations of the run, in the order performed.

Proof.routine

Uses. Lemma 3.3.7 (The loop invariant), Proposition 3.2.7 (Row operations are left multiplications), Corollary 3.2.11 (Products of elementary matrices)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Which part of Lemma 3.3.7 is about

𝐺 𝐴

Hint 2. Apply it after the last pass, and recall that products of elementary matrices are invertible.

Sketch. By Lemma 3.3.7(a) after the last pass,

rref (𝐴) = 𝐺 𝐴

with

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

the product of the elementary matrices of the run (Proposition 3.2.7). Such a product is invertible by Corollary 3.2.11.

By Proposition 3.2.7, performing the operations of the run one after another gives

𝐸_{1} 𝐴

, then

𝐸_{2} 𝐸_{1} 𝐴

, and so on; this is the content of Lemma 3.3.7(a). After the last operation the matrix is

rref (𝐴) =

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

𝐺 𝐴

. By Corollary 3.2.11,

𝐺

is invertible. □

In other words, running the algorithm on $𝐴$ is the same as multiplying $𝐴$ on the left by one well-chosen invertible matrix. Two consequences are immediate. First, $𝐴 \sim rref (𝐴)$ (Definition 3.2.21). Second, by Corollary 3.2.23, $ker 𝑇_{𝐴} =$ $ker 𝑇_{rref (𝐴)}$ , and by Proposition 3.2.14, $𝐴 𝐱 = 𝐲$ if and only if $rref (𝐴) 𝐱 = 𝐺 𝐲$ . Section 3.4 reads the solutions off this second system.

The matrix $𝐺$ is found by performing the operations of the run on $𝐼_{𝑚}$ . It is convenient to do this alongside the run itself, by adjoining $𝐼_{𝑚}$ to $𝐴$ .

Proposition 3.3.11 (Carrying extra columns along). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑝}$ , and let $𝐺$ be as in Theorem 3.3.10.

(a) $𝐺 (𝐴 | 𝐵) =$ $(rref (𝐴) | 𝐺 𝐵)$ .
(b)Performing on the $𝑚 \times (𝑛 + 𝑝)$ matrix $(𝐴 | 𝐵)$ the run of Gauss–Jordan elimination with step 1 restricted to the first $𝑛$ columns ends at $(rref (𝐴) | 𝐺 𝐵)$ .

In particular, the restricted run on $(𝐴 | 𝐼_{𝑚})$ ends at $(rref (𝐴) | 𝐺)$ .

Proof.routine

Uses. Definition 2.4.1 (Matrix product), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.2.7 (Row operations are left multiplications)

Hint 1. Compute

𝐺 (𝐴 | 𝐵)

one column at a time.

Hint 2. For (b): the decisions in steps step 1 through step 4 depend only on entries in the scanned columns. How do row operations act on the individual columns of a matrix?

Sketch. Column

𝑙

𝐺 𝑀

𝐺

times column

𝑙

𝑀

, which gives (a). A row operation changes each column by itself, so during the restricted run the first

𝑛

columns evolve exactly as in the run on

𝐴

; since every decision depends only on them, the restricted run performs the same operations

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

and ends at

𝐺 (𝐴 | 𝐵)

(a) By Definition 2.4.1, column $𝑙$ of $𝐺 𝑀$ is $𝐺$ times column $𝑙$ of $𝑀$ , for any matrix $𝑀$ with $𝑚$ rows. The first $𝑛$ columns of $(𝐴 | 𝐵)$ are those of $𝐴$ and the last $𝑝$ are those of $𝐵$ , so the first $𝑛$ columns of $𝐺 (𝐴 | 𝐵)$ form $𝐺 𝐴 = rref (𝐴)$ and the last $𝑝$ form $𝐺 𝐵$ .

(b) For the same reason, if $𝐸$ is elementary, the first $𝑛$ columns of $𝐸 (𝐴 | 𝐵)$ form $𝐸 𝐴$ . So as long as the restricted run on $(𝐴 | 𝐵)$ and the run on $𝐴$ perform the same operations, the first $𝑛$ columns of the current matrix of the former are the current matrix of the latter. Every decision in steps step 1 through step 4 (which column, which rows, which scalars, whether to halt) depends only on the entries in the scanned columns. So, by induction on the number of operations, the two runs perform the same operations $𝐸_{1}, \dots, 𝐸_{𝑡}$ , and the restricted run ends at $𝐸_{𝑡} \dots 𝐸_{1} (𝐴 | 𝐵) =$ $𝐺 (𝐴 | 𝐵)$ , which is $(rref (𝐴) | 𝐺 𝐵)$ by (a). □

The row reducer does exactly this when it shows $𝐺$ : it carries $𝐼_{𝑚}$ along. For Example 3.3.3,

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

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

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

The last row of $𝐺$ is worth a look. Since the last row of $𝐺 𝐴$ is zero, $- 1$ times row $1$ of $𝐴$ , minus $1 / 2$ times row $2$ , plus row $3$ , is the zero row. So a zero row of $rref (𝐴)$ records a linear relation among the rows of $𝐴$ (see Exercise 3.3.57).

Which matrices are in RREF

We now characterize the matrices in RREF by their shape, without reference to the algorithm. One direction is Proposition 3.3.8. For the other, we run the algorithm on a matrix of the right shape and watch it do nothing.

Theorem 3.3.12 (Matrices in RREF). A matrix

𝑅 \in 𝐹^{𝑚 \times 𝑛}

is in reduced row echelon form if and only if it satisfies conditions (R1)–(R4) of Proposition 3.3.8. In that case the pivots of

𝑅

are its leading entries.

Proof.standard

Uses. Proposition 3.3.8 (Properties of the output), Algorithm 3.3.1 (Gauss–Jordan elimination), Definition 3.3.9 (Reduced row echelon form), induction on the number of passes

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. One direction is Proposition 3.3.8, applied to

𝑅 = rref (𝑅)

Hint 2. For the other, let rows

1, \dots, 𝑟

be the nonzero rows of

𝑅

, with leading entries in columns

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

. Run the algorithm on

𝑅

and show by induction that pass

𝑘

changes nothing.

Hint 3. In pass

𝑘

, which is the leftmost column with a nonzero entry in rows

𝑘, \dots, 𝑚

? What is the entry in row

𝑘

there, and what does (R4) say about the rest of that column?

Sketch. If

rref (𝑅) = 𝑅

, then

𝑅

is an output, so (R1)–(R4) hold by Proposition 3.3.8. Conversely, if (R1)–(R4) hold, then in pass

𝑘

the rows

𝑘, \dots, 𝑚

vanish to the left of

𝑐_{𝑘}

, the leading entry of row

𝑘

, which is

1

. So the scan picks

𝑐_{𝑘}

, there is no swap and no scaling, and by (R4) nothing needs clearing. After

𝑟

passes only zero rows are unpivoted, and the algorithm halts with output

𝑅

Suppose $𝑅$ is in RREF. Then $𝑅 = rref (𝑅)$ is an output of the algorithm, so it satisfies (R1)–(R4) by Proposition 3.3.8, and by Proposition 3.3.8(b) its pivots are its leading entries.

Conversely, suppose $𝑅$ satisfies (R1)–(R4). By (R1), its nonzero rows are rows $1, \dots, 𝑟$ for some $𝑟$ , and by (R3), their leading entries lie in columns $𝑐_{1} <$ $𝑐_{2} <$ $\dots <$ $𝑐_{𝑟}$ . We show by induction on $𝑘 = 0, 1, \dots, 𝑟$ that after $𝑘$ passes of Gauss–Jordan elimination on $𝑅$ , the current matrix is still $𝑅$ and the pivots are the leading entries of rows $1, \dots, 𝑘$ . For $𝑘 = 0$ there is nothing to show.

Suppose this holds for some $𝑘 < 𝑟$ , and consider pass $𝑘 + 1$ . Rows $𝑘 + 2, \dots, 𝑟$ have their leading entries in columns $𝑐_{𝑘 + 2}, \dots, 𝑐_{𝑟}$ , all to the right of $𝑐_{𝑘 + 1}$ , and rows $𝑟 + 1, \dots, 𝑚$ are zero. Together with the leading entry of row $𝑘 + 1$ , this shows that rows $𝑘 + 1, \dots, 𝑚$ vanish in columns $1, \dots, 𝑐_{𝑘 + 1} - 1$ , and that row $𝑘 + 1$ has a nonzero entry in column $𝑐_{𝑘 + 1}$ . So step 1 picks $𝑗 = 𝑐_{𝑘 + 1}$ , and step 2 does nothing. By (R2) the entry in position $(𝑘 + 1, 𝑐_{𝑘 + 1})$ is already $1$ , so step 3 changes nothing and declares this leading entry a pivot. By (R4) all other entries of column $𝑐_{𝑘 + 1}$ are $0$ , so step 4 changes nothing. This completes the induction.

After $𝑟$ passes the unpivoted rows are rows $𝑟 + 1, \dots, 𝑚$ , which are zero by (R1), so the algorithm halts and outputs $𝑅$ . Hence $rref (𝑅) = 𝑅$ , and the pivots are the leading entries. □

Since $rref (𝐴)$ satisfies (R1)–(R4) by Proposition 3.3.8, Theorem 3.3.12 gives $rref (rref (𝐴)) =$ $rref (𝐴)$ : running the algorithm a second time changes nothing. The shape described by (R1)–(R4) is a staircase. For instance, every $4 \times 6$ matrix in RREF with pivot columns $1, 3, 6$ looks like

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

where each $*$ is an arbitrary scalar. The pivot columns are $𝐞_{1}, 𝐞_{2}, 𝐞_{3}$ , everything below the staircase is $0$ , and the non-pivot columns are free above it.

Example 3.3.13 (Matrices in RREF). The identity $𝐼_{𝑛}$ and the zero matrix $0 \in 𝐹^{𝑚 \times 𝑛}$ are in RREF. (For $𝐼_{𝑛}$ the leading entries are the diagonal entries; the zero matrix has no nonzero rows, so (R2)–(R4) say nothing.) So are

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

In the second matrix, the entry $5$ sits in a non-pivot column, where (R4) imposes nothing.

Non-example 3.3.14 (Four ways to fail). Over $ℚ$ , each matrix below violates exactly one condition:

(R1) : (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}), (R2) : (\begin{matrix} 1 & 0 \\ 0 & 2 \end{matrix}), (R3) : (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), (R4) : (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}) .

In the first, a zero row lies above a nonzero row. In the second, a leading entry is $2$ . In the third, the leading entry of row $2$ lies to the left of that of row $1$ . In the fourth, the leading entry of row $2$ has a nonzero entry above it. The last three have reduced row echelon form $𝐼_{2}$ , and the first has $(\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .

Exercise 3.3.15.routine

(a)Which of the following matrices are in RREF? For each one that is not, name a condition among (R1)–(R4) that fails.
$(\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 4 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}), (\begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix}) .$
(b)Find all $2 \times 2$ matrices over a field $𝐹$ that are in RREF. How many are there over $𝔽_{𝑝}$ ?

Solution.

Uses. Theorem 3.3.12 (Matrices in RREF)

Hint 1. Locate the leading entry of each row, then check (R1)–(R4) one at a time.

Hint 2. For (b), sort by the number of nonzero rows, and then by the position of the leading entries.

Sketch. (a) In RREF: the second and fourth. The first fails (R3), the third fails (R1), the fifth fails (R4). (b)

0

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

for

𝑎 \in 𝐹

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

, and

𝐼_{2}

; over

𝔽_{𝑝}

there are

𝑝 + 3

(a) By Theorem 3.3.12 we check (R1)–(R4).

The first matrix fails (R3): the leading entry of row $3$ (column $2$ ) lies to the left of that of row $2$ (column $3$ ).
The second is in RREF: the leading entries are $1$ s in columns $1$ and $3$ , and those columns are $𝐞_{1}$ and $𝐞_{2}$ .
The third fails (R1): the zero row $2$ lies above the nonzero row $3$ .
The fourth is in RREF: leading $1$ s in columns $1$ and $2$ , which are $𝐞_{1}$ and $𝐞_{2}$ , and the zero row is last.
The fifth fails (R4): column $3$ contains the leading entry of row $2$ and also a nonzero entry in row $3$ . (It also fails (R3).)

(b) Let $𝑅 \in 𝐹^{2 \times 2}$ be in RREF. If $𝑅$ has no nonzero row, $𝑅 = 0$ . If it has one, it is row $1$ by (R1). Its leading $1$ is in column $1$ or column $2$ : in the first case $𝑅 = (\begin{matrix} 1 & 𝑎 \\ 0 & 0 \end{matrix})$ with $𝑎 \in 𝐹$ arbitrary (column $2$ contains no leading entry, so (R4) says nothing about it), and in the second case $𝑅 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ . If both rows are nonzero, their leading $1$ s are in columns $1$ and $2$ by (R3), and by (R4) $𝑅 = 𝐼_{2}$ . All these matrices satisfy (R1)–(R4). Over $𝔽_{𝑝}$ there are $1 + 𝑝 + 1 + 1 = 𝑝 + 3$ of them.

3.3.4Uniqueness

Two people row reducing the same matrix by hand will rarely perform the same operations. One may bring up a different row in step 2, or clear everything below the pivots first and the entries above them afterwards. If both end with a matrix satisfying (R1)–(R4), do they end with the same matrix? Equivalently, can one row equivalence class contain two different matrices in RREF? This matters beyond hand computation. Properties we read off $rref (𝐴)$ , such as the number of pivots (the rank, Section 3.5) or which columns are pivot columns, should belong to $𝐴$ , and we will constantly want to replace $𝐴$ by a row equivalent matrix $𝐺 𝐴$ without changing them.

The answer is that the reduced row echelon form is unique. We first record how to read the columns of a matrix in RREF.

Lemma 3.3.16 (Reading the columns of a matrix in RREF). Let $𝑅 \in 𝐹^{𝑚 \times 𝑛}$ be in RREF, with columns $𝐫_{1}, \dots, 𝐫_{𝑛}$ , entries $𝑟_{𝑖 𝑗}$ , and pivot columns $𝑝_{1} < \dots < 𝑝_{𝑟}$ . Put $𝑝_{𝑡} = 𝑛 + 1$ for $𝑡 > 𝑟$ .

(a)For $0 \leq 𝑠 \leq 𝑚$ , every column $𝐫_{𝑗}$ with $𝑗 < 𝑝_{𝑠 + 1}$ has zeros in rows $𝑠 + 1, \dots, 𝑚$ . That is, $𝐫_{𝑗} =$ $𝑟_{1 𝑗} 𝐞_{1} +$ $\dots +$ $𝑟_{𝑠 𝑗} 𝐞_{𝑠}$ .
(b) $𝐫_{𝑝_{𝑠}} = 𝐞_{𝑠}$ for $1 \leq 𝑠 \leq 𝑟$ .
(c)Column $𝑗$ is a pivot column if and only if $𝐫_{𝑗}$ is not a linear combination of $𝐫_{1}, \dots, 𝐫_{𝑗 - 1}$ .
(d)If column $𝑗$ is not a pivot column, and $𝑝_{1}, \dots, 𝑝_{𝑡}$ are the pivot columns to the left of it, then
$𝐫_{𝑗} = 𝑟_{1 𝑗} 𝐫_{𝑝_{1}} + 𝑟_{2 𝑗} 𝐫_{𝑝_{2}} + \dots + 𝑟_{𝑡 𝑗} 𝐫_{𝑝_{𝑡}} .$

Proof.standard

Uses. Theorem 3.3.12 (Matrices in RREF), Proposition 3.3.8 (Properties of the output), Definition 1.3.4 (Linear combination)

Hint 1. For (a), take a row

𝑖 \geq 𝑠 + 1

. Where is its leading entry, if it has one?

Hint 2. For (c), a pivot column

𝐫_{𝑝_{𝑠}} = 𝐞_{𝑠}

has a

1

in row

𝑠

. What is the entry in row

𝑠

of every earlier column, and of every combination of them?

Hint 3. For (d), apply (a) with

𝑠 = 𝑡

and substitute

𝐞_{𝑠} = 𝐫_{𝑝_{𝑠}}

Sketch. (a) A row

𝑖 > 𝑠

is zero or has its leading entry in column

𝑝_{𝑖} \geq 𝑝_{𝑠 + 1} > 𝑗

. (b) is (R2) with (R4). For (c), columns before

𝑝_{𝑠}

vanish in row

𝑠

by (a), and so do their combinations, while

𝐫_{𝑝_{𝑠}} = 𝐞_{𝑠}

does not. For a non-pivot column

𝑗

with

𝑡

pivot columns before it,

𝑗 < 𝑝_{𝑡 + 1}

, so (a) and (b) give (d), which exhibits

𝐫_{𝑗}

as a combination of earlier columns.

By Theorem 3.3.12, $𝑅$ satisfies (R1)–(R4) and its pivots are its leading entries: the leading entry of row $𝑠$ is a $1$ in column $𝑝_{𝑠}$ for $𝑠 \leq 𝑟$ , and rows $𝑟 + 1, \dots, 𝑚$ are zero.

(a) Let $𝑗 < 𝑝_{𝑠 + 1}$ and $𝑖 \geq 𝑠 + 1$ . If $𝑖 \leq 𝑟$ , the leading entry of row $𝑖$ is in column $𝑝_{𝑖} \geq 𝑝_{𝑠 + 1} > 𝑗$ , so $𝑟_{𝑖 𝑗} = 0$ . If $𝑖 > 𝑟$ , row $𝑖$ is zero. So $𝑟_{𝑖 𝑗} = 0$ for all $𝑖 \geq 𝑠 + 1$ .

(b) Column $𝑝_{𝑠}$ contains the leading entry of row $𝑠$ , which is $1$ by (R2), and its other entries are $0$ by (R4).

(c), (d) Suppose first that $𝑗 = 𝑝_{𝑠}$ is a pivot column. By (a), applied with $𝑠 - 1$ , every column $𝐫_{𝑙}$ with $𝑙 < 𝑗$ has entry $0$ in row $𝑠$ , and therefore so does every linear combination of $𝐫_{1}, \dots, 𝐫_{𝑗 - 1}$ . But $𝐫_{𝑗} = 𝐞_{𝑠}$ has entry $1$ in row $𝑠$ . So $𝐫_{𝑗}$ is not such a combination.

Now suppose $𝑗$ is not a pivot column, and let $𝑝_{1}, \dots, 𝑝_{𝑡}$ be the pivot columns to its left ( $𝑡 = 0$ if there are none). Then $𝑝_{𝑡 + 1} > 𝑗$ , so by (a) and (b),

𝐫_{𝑗} = 𝑟_{1 𝑗} 𝐞_{1} + \dots + 𝑟_{𝑡 𝑗} 𝐞_{𝑡} = 𝑟_{1 𝑗} 𝐫_{𝑝_{1}} + \dots + 𝑟_{𝑡 𝑗} 𝐫_{𝑝_{𝑡}} .

This is (d), and since $𝑝_{1}, \dots, 𝑝_{𝑡} < 𝑗$ , it shows that $𝐫_{𝑗}$ is a combination of earlier columns. (For $𝑡 = 0$ , it says $𝐫_{𝑗} = 𝟎$ , the empty combination.) Together with the first case, this proves (c). □

So a matrix in RREF records two kinds of information: which columns are new, in the sense of not being combinations of earlier columns (the pivot columns, which are $𝐞_{1}, 𝐞_{2}, \dots$ in order), and how each other column is built from the pivot columns before it (its entries).

Intuition (Two strategies for uniqueness). We want to show: if $𝑅$ and $𝑅^{'} = 𝐺 𝑅$ are both in RREF and $𝐺$ is invertible, then $𝑅 = 𝑅^{'}$ . There are two natural ways to think about this.

Track $𝐺$ . Left multiplication by $𝐺$ sends column $𝑝_{𝑠}$ of $𝑅$ , which is $𝐞_{𝑠}$ , to column $𝑝_{𝑠}$ of $𝑅^{'}$ . If we knew that $𝑅^{'}$ had its pivots in the same columns, that column would be $𝐞_{𝑠}$ too, so $𝐺 𝐞_{𝑠} = 𝐞_{𝑠}$ : the first $𝑟$ columns of $𝐺$ are $𝐞_{1}, \dots, 𝐞_{𝑟}$ . Then $𝐺$ fixes every vector in $span (𝐞_{1}, \dots, 𝐞_{𝑟})$ , which contains every column of $𝑅$ , so $𝐺 𝑅 = 𝑅$ . So everything comes down to showing that the pivot columns agree, and it is natural to do this one pivot at a time, from left to right, using invertibility of $𝐺$ to rule out a pivot that appears earlier in one matrix than in the other. This is an induction on the pivots.

Forget $𝐺$ . Row operations preserve the linear relations among the columns (Corollary 3.2.17). By Lemma 3.3.16, these relations determine which columns are pivot columns, and how the other columns are expressed through them. So two RREF matrices with the same relations among their columns are equal.

The first approach gives information about $𝐺$ that the second does not; the second is shorter and proves a stronger statement (Corollary 3.3.20).

Theorem 3.3.17 (Uniqueness of the reduced row echelon form). Let

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

be in RREF, and suppose

𝑅^{'} = 𝐺 𝑅

for some invertible

𝐺 \in 𝐹^{𝑚 \times 𝑚}

. Then

𝑅^{'} = 𝑅

Proof (pivot by pivot).hard

Uses. Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.3.8 (Matrix–vector product), Definition 2.5.12 (Invertible), induction on $𝑠$

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Let

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

be the columns of

𝐺

. Column

𝑗

𝑅^{'}

𝐺 𝐫_{𝑗} =

𝑟_{1 𝑗} 𝐠_{1} +

\dots +

𝑟_{𝑚 𝑗} 𝐠_{𝑚}

. Why are the

𝐠_{𝑖}

linearly independent?

Hint 2. Let

𝑝_{𝑠}

and

𝑞_{𝑠}

be the pivot columns of

𝑅

and

𝑅^{'}

(with value

𝑛 + 1

when there are fewer than

𝑠

pivots). Prove by induction on

𝑠

that

𝑝_{𝑠} = 𝑞_{𝑠}

, and that

𝐠_{𝑠} = 𝐞_{𝑠}

when

𝑝_{𝑠} \leq 𝑛

Hint 3. If

𝑝_{𝑠} < 𝑞_{𝑠}

, compute column

𝑝_{𝑠}

𝑅^{'}

in two ways: as

𝐺 𝐞_{𝑠} = 𝐠_{𝑠}

, and with Lemma 3.3.16(a) for

𝑅^{'}

. If

𝑞_{𝑠} < 𝑝_{𝑠}

, compute column

𝑞_{𝑠}

𝑅^{'}

in two ways and look at its

𝑠

th entry.

Sketch. The columns

𝐠_{𝑖}

𝐺

are independent since

𝐺 𝐜 = 𝟎

forces

𝐜 = 𝟎

. By induction on

𝑠

: if

𝑝_{𝑠} < 𝑞_{𝑠}

, then

𝐠_{𝑠} = 𝐺 𝐞_{𝑠}

is column

𝑝_{𝑠}

𝑅^{'}

, which lies in the span of

𝐞_{1}, \dots, 𝐞_{𝑠 - 1}

, that is, of

𝐠_{1}, \dots, 𝐠_{𝑠 - 1}

: a contradiction. If

𝑞_{𝑠} < 𝑝_{𝑠}

, column

𝑞_{𝑠}

𝑅

lies in

span (𝐞_{1}, \dots, 𝐞_{𝑠 - 1})

, and

𝐺

fixes that span, so column

𝑞_{𝑠}

𝑅^{'}

has

𝑠

th entry

0

, not

𝐞_{𝑠}

. So

𝑝_{𝑠} = 𝑞_{𝑠}

, and then

𝐠_{𝑠} = 𝐺 𝐞_{𝑠} = 𝐞_{𝑠}

. Finally every column of

𝑅

lies in

span (𝐞_{1}, \dots, 𝐞_{𝑟})

, which

𝐺

fixes.

Write $𝐫_{𝑗}$ , $𝐫_{𝑗}^{'}$ , and $𝐠_{𝑖}$ for the columns of $𝑅$ , $𝑅^{'}$ , and $𝐺$ , and $𝑝_{1} < \dots < 𝑝_{𝑟}$ and $𝑞_{1} < \dots < 𝑞_{𝑟^{'}}$ for the pivot columns of $𝑅$ and $𝑅^{'}$ . Put $𝑝_{𝑠} = 𝑛 + 1$ for $𝑠 > 𝑟$ and $𝑞_{𝑠} = 𝑛 + 1$ for $𝑠 > 𝑟^{'}$ . We use two facts.

By Definition 2.3.8, column $𝑗$ of $𝑅^{'}$ is
$𝐫_{𝑗}^{'} = 𝐺 𝐫_{𝑗} = 𝑟_{1 𝑗} 𝐠_{1} + \dots + 𝑟_{𝑚 𝑗} 𝐠_{𝑚} .$
In particular $𝐺 𝐞_{𝑖} = 𝐠_{𝑖}$ .
The columns of $𝐺$ are linearly independent: if $𝑐_{1} 𝐠_{1} +$ $\dots +$ $𝑐_{𝑚} 𝐠_{𝑚} =$ $𝟎$ , then $𝐺 𝐜 = 𝟎$ for $𝐜 = (𝑐_{1}, \dots, 𝑐_{𝑚})$ , so $𝐜 = 𝐺^{- 1} 𝐺 𝐜 = 𝟎$ .

We prove by induction on $𝑠 = 1, 2, \dots, 𝑚$ that

𝑝_{𝑠} = 𝑞_{𝑠}, and 𝐠_{𝑠} = 𝐞_{𝑠} if 𝑝_{𝑠} \leq 𝑛 .

Fix $𝑠$ , and assume this holds for every $𝑡 < 𝑠$ .

Suppose $𝑝_{𝑠} < 𝑞_{𝑠}$ . Then $𝑝_{𝑠} \leq 𝑛$ , so $𝑠 \leq 𝑟$ , and for $𝑡 < 𝑠$ we have $𝑝_{𝑡} < 𝑝_{𝑠} \leq 𝑛$ , hence $𝑞_{𝑡} = 𝑝_{𝑡} \leq 𝑛$ and $𝐠_{𝑡} = 𝐞_{𝑡}$ by the induction hypothesis. By Lemma 3.3.16(b), $𝐫_{𝑝_{𝑠}}^{'} =$ $𝐺 𝐫_{𝑝_{𝑠}} =$ $𝐺 𝐞_{𝑠} =$ $𝐠_{𝑠}$ . On the other hand $𝑝_{𝑠} < 𝑞_{𝑠}$ , so by Lemma 3.3.16(a) for $𝑅^{'}$ , the column $𝐫_{𝑝_{𝑠}}^{'}$ lies in $span (𝐞_{1}, \dots, 𝐞_{𝑠 - 1})$ , which is $span (𝐠_{1}, \dots, 𝐠_{𝑠 - 1})$ . So $𝐠_{𝑠}$ is a linear combination of $𝐠_{1}, \dots, 𝐠_{𝑠 - 1}$ , contradicting the independence of the columns of $𝐺$ .

Suppose $𝑞_{𝑠} < 𝑝_{𝑠}$ . Then $𝑞_{𝑠} \leq 𝑛$ , so $𝑠 \leq 𝑟^{'}$ , and for $𝑡 < 𝑠$ , $𝑞_{𝑡} < 𝑞_{𝑠} \leq 𝑛$ ; by the induction hypothesis $𝑝_{𝑡} = 𝑞_{𝑡} \leq 𝑛$ and $𝐠_{𝑡} = 𝐞_{𝑡}$ . By Lemma 3.3.16(a) for $𝑅$ , $𝐫_{𝑞_{𝑠}} =$ $\sum_{𝑡 < 𝑠} 𝑟_{𝑡 𝑞_{𝑠}} 𝐞_{𝑡}$ , so

𝐫_{𝑞_{𝑠}}^{'} = 𝐺 𝐫_{𝑞_{𝑠}} = \sum_{𝑡 < 𝑠} 𝑟_{𝑡 𝑞_{𝑠}} 𝐠_{𝑡} = \sum_{𝑡 < 𝑠} 𝑟_{𝑡 𝑞_{𝑠}} 𝐞_{𝑡},

whose $𝑠$ th entry is $0$ . But $𝐫_{𝑞_{𝑠}}^{'} = 𝐞_{𝑠}$ by Lemma 3.3.16(b) for $𝑅^{'}$ , a contradiction.

Hence $𝑝_{𝑠} = 𝑞_{𝑠}$ . If this number is at most $𝑛$ , then by Lemma 3.3.16(b) for both matrices, $𝐞_{𝑠} =$ $𝐫_{𝑝_{𝑠}}^{'} =$ $𝐺 𝐫_{𝑝_{𝑠}} =$ $𝐺 𝐞_{𝑠} =$ $𝐠_{𝑠}$ . This completes the induction.

In particular $𝑟 = 𝑟^{'}$ , since $𝑟$ is the number of $𝑠$ with $𝑝_{𝑠} \leq 𝑛$ , and $𝐠_{𝑠} = 𝐞_{𝑠}$ for $𝑠 \leq 𝑟$ . Finally, let $𝑗$ be any column. By Lemma 3.3.16(a) with $𝑠 = 𝑟$ , $𝐫_{𝑗} =$ $\sum_{𝑡 \leq 𝑟} 𝑟_{𝑡 𝑗} 𝐞_{𝑡}$ , so

𝐫_{𝑗}^{'} = 𝐺 𝐫_{𝑗} = \sum_{𝑡 \leq 𝑟} 𝑟_{𝑡 𝑗} 𝐠_{𝑡} = \sum_{𝑡 \leq 𝑟} 𝑟_{𝑡 𝑗} 𝐞_{𝑡} = 𝐫_{𝑗} .

So $𝑅^{'} = 𝑅$ , as desired. □

Proof (via relations among columns).hard

Uses. Corollary 3.2.17 (Row operations preserve relations among columns), Lemma 3.3.16 (Reading the columns of a matrix in RREF)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. By Corollary 3.2.17,

𝑅

and

𝑅^{'} = 𝐺 𝑅

satisfy the same linear relations among their columns. Use only this.

Hint 2. By Lemma 3.3.16(c), being a pivot column is a statement about relations among the columns. Conclude that

𝑅

and

𝑅^{'}

have the same pivot columns.

Hint 3. A non-pivot column of

𝑅

satisfies the relation of Lemma 3.3.16(d). Transfer that relation to

𝑅^{'}

Sketch. The columns satisfy

\sum_{𝑙} 𝑥_{𝑙} 𝐫_{𝑙} =

𝟎 \Leftrightarrow

\sum_{𝑙} 𝑥_{𝑙} 𝐫_{𝑙}^{'} =

𝟎

. “Column

𝑗

is a combination of earlier columns” is such a relation, so by Lemma 3.3.16(c) the pivot columns agree, and pivot columns are

𝐞_{𝑠}

in both. A non-pivot column satisfies

𝐫_{𝑗} =

\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐫_{𝑝_{𝑠}}

; the same relation in

𝑅^{'}

gives

𝐫_{𝑗}^{'} =

\sum_{𝑠} 𝑟_{𝑠 𝑗} 𝐞_{𝑠} =

𝐫_{𝑗}

Let $𝐫_{𝑗}$ and $𝐫_{𝑗}^{'} = 𝐺 𝐫_{𝑗}$ be the columns of $𝑅$ and $𝑅^{'}$ . By Corollary 3.2.17, for all $𝑥_{1}, \dots, 𝑥_{𝑛} \in 𝐹$ ,

𝑥_{1} 𝐫_{1} + \dots + 𝑥_{𝑛} 𝐫_{𝑛} = 𝟎 \Leftrightarrow 𝑥_{1} 𝐫_{1}^{'} + \dots + 𝑥_{𝑛} 𝐫_{𝑛}^{'} = 𝟎 .

(3.3.2)

We show that (3.3.2) alone forces $𝑅 = 𝑅^{'}$ .

The pivot columns agree. For scalars $𝑐_{1}, \dots, 𝑐_{𝑗 - 1}$ , the equation

𝐫_{𝑗} = 𝑐_{1} 𝐫_{1} + \dots + 𝑐_{𝑗 - 1} 𝐫_{𝑗 - 1}

is the relation in (3.3.2) with $𝑥_{𝑙} = 𝑐_{𝑙}$ for $𝑙 < 𝑗$ , $𝑥_{𝑗} = - 1$ , and $𝑥_{𝑙} = 0$ for $𝑙 > 𝑗$ . So it holds if and only if the same equation holds with $𝐫^{'}$ in place of $𝐫$ . Hence $𝐫_{𝑗}$ is a linear combination of the earlier columns of $𝑅$ if and only if $𝐫_{𝑗}^{'}$ is a linear combination of the earlier columns of $𝑅^{'}$ . By Lemma 3.3.16(c), applied to $𝑅$ and to $𝑅^{'}$ , column $𝑗$ is a pivot column of $𝑅$ if and only if it is a pivot column of $𝑅^{'}$ . Let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be the common pivot columns.

The columns agree. By Lemma 3.3.16(b), $𝐫_{𝑝_{𝑠}} =$ $𝐞_{𝑠} =$ $𝐫_{𝑝_{𝑠}}^{'}$ for each $𝑠$ . Let $𝑗$ be a non-pivot column, with pivot columns $𝑝_{1}, \dots, 𝑝_{𝑡}$ to its left. By Lemma 3.3.16(d) for $𝑅$ ,

𝐫_{𝑗} = 𝑟_{1 𝑗} 𝐫_{𝑝_{1}} + \dots + 𝑟_{𝑡 𝑗} 𝐫_{𝑝_{𝑡}} .

This is a relation among the columns of $𝑅$ , so by (3.3.2) the same relation holds in $𝑅^{'}$ :

𝐫_{𝑗}^{'} = 𝑟_{1 𝑗} 𝐫_{𝑝_{1}}^{'} + \dots + 𝑟_{𝑡 𝑗} 𝐫_{𝑝_{𝑡}}^{'} = 𝑟_{1 𝑗} 𝐞_{1} + \dots + 𝑟_{𝑡 𝑗} 𝐞_{𝑡} = 𝐫_{𝑗},

where the last equality is Lemma 3.3.16(d) and (b) for $𝑅$ again. So every column of $𝑅^{'}$ equals the corresponding column of $𝑅$ . □

The two proofs teach different things. The first shows how rigid $𝐺$ is: whenever $𝐺 𝑅$ is again in RREF, the first $𝑟$ columns of $𝐺$ are $𝐞_{1}, \dots, 𝐞_{𝑟}$ , although its other columns can be anything that keeps $𝐺$ invertible (Exercise 3.3.46). The second never looks at $𝐺$ . It used only that $𝑅$ and $𝑅^{'}$ satisfy the same linear relations among their columns, that is, that $ker 𝑇_{𝑅} = ker 𝑇_{𝑅^{'}}$ , and we will exploit this in Corollary 3.3.20.

Corollary 3.3.18 (RREF and row equivalence). Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ .

(a) $rref (𝐺 𝐴) =$ $rref (𝐴)$ for every invertible $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ .
(b) $𝐴 \sim 𝐵$ if and only if $rref (𝐴) = rref (𝐵)$ .
(c)If $𝑅$ is in RREF and $𝐴 \sim 𝑅$ , then $𝑅 = rref (𝐴)$ . In particular, any sequence of elementary row operations that turns $𝐴$ into a matrix satisfying (R1)–(R4), performed in any order and with any choices, ends at $rref (𝐴)$ .

Proof.standard

Uses. Theorem 3.3.17 (Uniqueness of the reduced row echelon form), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Theorem 3.3.12 (Matrices in RREF), Proposition 3.3.8 (Properties of the output), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.2.22 (Row equivalence is an equivalence relation), Definition 3.2.21 (Row equivalence)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For (a), write

rref (𝐴) = 𝑁 𝐴

and

rref (𝐺 𝐴) = 𝑀 𝐺 𝐴

with

𝑀

𝑁

invertible, and express

rref (𝐺 𝐴)

as an invertible matrix times

rref (𝐴)

Hint 2. For (b), use (a) in one direction, and

𝐴 \sim rref (𝐴)

with symmetry and transitivity of

\sim

in the other.

Sketch. (a)

rref (𝐺 𝐴) =

(𝑀 𝐺 𝑁^{- 1}) rref (𝐴)

, both sides are in RREF, and

𝑀 𝐺 𝑁^{- 1}

is invertible, so Theorem 3.3.17 applies. (b) If

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

, apply (a). If

rref (𝐴) = rref (𝐵)

, then

𝐴 \sim

rref (𝐴) =

rref (𝐵) \sim

𝐵

. (c) is (b) with

𝐵 = 𝑅

, since

rref (𝑅) = 𝑅

; matrices satisfying (R1)–(R4) are in RREF by Theorem 3.3.12.

(a) By Theorem 3.3.10 there are invertible $𝑁, 𝑀 \in 𝐹^{𝑚 \times 𝑚}$ with $rref (𝐴) = 𝑁 𝐴$ and $rref (𝐺 𝐴) =$ $𝑀 (𝐺 𝐴)$ . Then

rref (𝐺 𝐴) = 𝑀 𝐺 𝐴 = (𝑀 𝐺 𝑁^{- 1}) (𝑁 𝐴) = (𝑀 𝐺 𝑁^{- 1}) rref (𝐴),

and $𝑀 𝐺 𝑁^{- 1}$ is invertible, with inverse $𝑁 𝐺^{- 1} 𝑀^{- 1}$ . Both $rref (𝐺 𝐴)$ and $rref (𝐴)$ are in RREF (by Proposition 3.3.8 and Theorem 3.3.12), so Theorem 3.3.17 gives $rref (𝐺 𝐴) =$ $rref (𝐴)$ .

(b) If $𝐴 \sim 𝐵$ , then $𝐵 = 𝐺 𝐴$ with $𝐺 = 𝐸_{𝑘} \dots 𝐸_{1}$ a product of elementary matrices, which is invertible, so $rref (𝐵) = rref (𝐴)$ by (a). Conversely, suppose $rref (𝐴) = rref (𝐵)$ . By Theorem 3.3.10, $𝐴 \sim rref (𝐴)$ and $𝐵 \sim rref (𝐵)$ , so by symmetry and transitivity (Proposition 3.2.22), $𝐴 \sim$ $rref (𝐴) =$ $rref (𝐵) \sim$ $𝐵$ .

(c) If $𝑅$ is in RREF, then $rref (𝑅) = 𝑅$ , and $𝐴 \sim 𝑅$ gives $rref (𝐴) =$ $rref (𝑅) =$ $𝑅$ by (b). A sequence of row operations that turns $𝐴$ into a matrix $𝑅$ satisfying (R1)–(R4) shows $𝐴 \sim 𝑅$ , and $𝑅$ is in RREF by Theorem 3.3.12. □

Part (c) settles the question from Remark 3.3.2. A run of the algorithm that makes other choices in step 2 still ends at a matrix satisfying (R1)–(R4), since the proofs of Lemma 3.3.7 and Proposition 3.3.8 never used which row was brought up; so it ends at $rref (𝐴)$ . The same goes for Gaussian elimination followed by clearing upward (Section 3.3.6), and for any improvised hand computation. It also shows that the pivot columns, and their number, are determined by $𝐴$ . Here is a description of them that does not mention the algorithm at all.

Corollary 3.3.19 (Pivot columns, intrinsically). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and let $𝑟_{𝑖 𝑗}$ be the entries of $rref (𝐴)$ .

(a)Column $𝑗$ is a pivot column of $𝐴$ if and only if $𝐚_{𝑗}$ is not a linear combination of $𝐚_{1}, \dots, 𝐚_{𝑗 - 1}$ .
(b)If column $𝑗$ is not a pivot column and $𝑝_{1}, \dots, 𝑝_{𝑡}$ are the pivot columns to its left, then
$𝐚_{𝑗} = 𝑟_{1 𝑗} 𝐚_{𝑝_{1}} + \dots + 𝑟_{𝑡 𝑗} 𝐚_{𝑝_{𝑡}} .$

Proof.routine

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Corollary 3.2.17 (Row operations preserve relations among columns), Lemma 3.3.16 (Reading the columns of a matrix in RREF)

Hint 1. Write

rref (𝐴) = 𝐺 𝐴

. How are the columns of

rref (𝐴)

related to those of

𝐴

, and which relations do they share?

Hint 2. Combine Corollary 3.2.17(b) with Lemma 3.3.16(c) and (d).

Sketch. With

rref (𝐴) = 𝐺 𝐴

and

𝐺

invertible, the columns

𝐫_{𝑙} = 𝐺 𝐚_{𝑙}

satisfy the same relations as the

𝐚_{𝑙}

. So

𝐚_{𝑗}

is a combination of earlier columns, with given coefficients, exactly when

𝐫_{𝑗}

is; now apply Lemma 3.3.16(c) and (d).

By Theorem 3.3.10,

rref (𝐴) = 𝐺 𝐴

with

𝐺

invertible, so the columns of

rref (𝐴)

are

𝐫_{𝑙} = 𝐺 𝐚_{𝑙}

. By Corollary 3.2.17(b), applied with

𝑐_{𝑙} = 0

for

𝑙 > 𝑗

, we have

𝐚_{𝑗} =

\sum_{𝑙 < 𝑗} 𝑐_{𝑙} 𝐚_{𝑙}

if and only if

𝐫_{𝑗} =

\sum_{𝑙 < 𝑗} 𝑐_{𝑙} 𝐫_{𝑙}

. So

𝐚_{𝑗}

is a combination of

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

if and only if

𝐫_{𝑗}

is a combination of

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

, and (a) follows from Lemma 3.3.16(c). Similarly, (b) follows from the relation of Lemma 3.3.16(d). □

For the matrix of Example 3.3.3, the pivot columns are $1$ and $3$ , and Corollary 3.3.19(b) reads off $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{4} = - 2 𝐚_{1} + 2 𝐚_{3}$ from the entries of $rref (𝐴)$ . Indeed $- 2 (0, 2, 1) +$ $2 (2, 2, 3) =$ $(4, 0, 4)$ . Chapter 4 uses this description to extract bases from spanning lists.

Finally, we can prove the converse promised in Remark 3.2.25.

Corollary 3.3.20 (The kernel is a complete invariant). For

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

, the following are equivalent:

(i) $𝐴 \sim 𝐵$ ;
(ii) $rref (𝐴) = rref (𝐵)$ ;
(iii) $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ .

Proof.standard

Uses. Corollary 3.3.18 (RREF and row equivalence), Corollary 3.2.23 (Row equivalent matrices have the same kernel), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Definition 2.3.8 (Matrix–vector product), Theorem 3.3.17 (Uniqueness of the reduced row echelon form)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. (i)

\Leftrightarrow

(ii) is Corollary 3.3.18(b), and (i)

\Rightarrow

(iii) is Corollary 3.2.23. Only (iii)

\Rightarrow

(ii) is new.

Hint 2. Reduce to RREF:

ker 𝑇_{rref (𝐴)} =

ker 𝑇_{𝐴}

. What does

𝐱 \in ker 𝑇_{𝑅}

say about the columns of

𝑅

Hint 3. Reread the second proof of Theorem 3.3.17. Which hypothesis did it really use?

Sketch. If

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

, then

𝑅 = rref (𝐴)

and

𝑅^{'} = rref (𝐵)

have the same kernel by Corollary 3.2.23. By Definition 2.3.8,

𝐱 \in ker 𝑇_{𝑅}

says

𝑥_{1} 𝐫_{1} +

\dots +

𝑥_{𝑛} 𝐫_{𝑛} =

𝟎

, so

𝑅

and

𝑅^{'}

satisfy the same linear relations among their columns. The second proof of Theorem 3.3.17 used nothing else, so

𝑅 = 𝑅^{'}

(i) $\Leftrightarrow$ (ii) is Corollary 3.3.18(b), and (i) $\Rightarrow$ (iii) is Corollary 3.2.23. We prove (iii) $\Rightarrow$ (ii).

Suppose $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ , and let $𝑅 = rref (𝐴)$ and $𝑅^{'} = rref (𝐵)$ . By Theorem 3.3.10 and Corollary 3.2.23, $ker 𝑇_{𝑅} =$ $ker 𝑇_{𝐴} =$ $ker 𝑇_{𝐵} =$ $ker 𝑇_{𝑅^{'}}$ . By Definition 2.3.8, $𝑅 𝐱 =$ $𝑥_{1} 𝐫_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐫_{𝑛}$ , so $ker 𝑇_{𝑅} = ker 𝑇_{𝑅^{'}}$ says exactly that for all $𝑥_{1}, \dots, 𝑥_{𝑛} \in 𝐹$ ,

𝑥_{1} 𝐫_{1} + \dots + 𝑥_{𝑛} 𝐫_{𝑛} = 𝟎 \Leftrightarrow 𝑥_{1} 𝐫_{1}^{'} + \dots + 𝑥_{𝑛} 𝐫_{𝑛}^{'} = 𝟎,

where $𝐫_{𝑙}$ and $𝐫_{𝑙}^{'}$ are the columns of $𝑅$ and $𝑅^{'}$ . This is (3.3.2). The second proof of Theorem 3.3.17 deduced $𝑅 = 𝑅^{'}$ from (3.3.2) and Lemma 3.3.16 alone, so $𝑅 = 𝑅^{'}$ . □

So the kernel of $𝑇_{𝐴}$ , a subspace of $𝐹^{𝑛}$ , determines the row equivalence class of $𝐴$ among $𝑚 \times 𝑛$ matrices, and $rref (𝐴)$ is a canonical representative of that class. For example, a $2 \times 3$ matrix $𝐴$ has $ker 𝑇_{𝐴} =$ $span ((1, 1, 1))$ if and only if $rref (𝐴) =$ $(\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & - 1 \end{matrix})$ (Exercise 3.3.49).

Exercise 3.3.21.routine Decide which two of the following real matrices are row equivalent:

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

Solution.

Uses. Corollary 3.3.18 (RREF and row equivalence), Algorithm 3.3.1 (Gauss–Jordan elimination)

Hint 1. By Corollary 3.3.18(b), compare reduced row echelon forms.

Hint 2.

𝐶

has a row that is a multiple of the other, so it has one pivot.

Sketch.

rref (𝐴) =

rref (𝐵) =

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

and

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

, so

𝐴 \sim 𝐵

, and

𝐶

is row equivalent to neither.

For

𝐴

: adding

- 2

times row

1

to row

2

gives

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

, and adding

- 3

times row

2

to row

1

gives

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

. For

𝐵

: swapping the rows gives

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

, and adding

- 2

times row

2

to row

1

gives

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

. For

𝐶

: adding

- 3

times row

1

to row

2

gives

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

. Each result satisfies (R1)–(R4), so by Corollary 3.3.18(c) these are the reduced row echelon forms. By Corollary 3.3.18(b),

𝐴 \sim 𝐵

, while

𝐶

is row equivalent to neither.

3.3.5Inverses by row reduction

For a square matrix $𝐴$ , row reduction decides whether $𝐴$ is invertible and, if it is, computes $𝐴^{- 1}$ . The idea is one we will use again and again: invertibility does not change when $𝐴$ is multiplied on the left by an invertible matrix, and for a matrix in RREF it is visible at a glance.

Technique 3.3.22 (Reduce to RREF). Many properties of a matrix $𝐴$ do not change when $𝐴$ is replaced by $𝐺 𝐴$ with $𝐺$ invertible: for example, the kernel $ker 𝑇_{𝐴}$ (Corollary 3.2.23), the linear relations among the columns (Corollary 3.2.17), and, for square $𝐴$ , invertibility. To decide such a property, replace $𝐴$ by $rref (𝐴) = 𝐺 𝐴$ (Theorem 3.3.10), where the answer can be read off the pivots and the zero rows. Two things have to be checked: that the property really is unchanged by left multiplication by invertible matrices, and what the property says about a matrix in RREF.

Reach for it whenever a question about $𝐴$ is really about $ker 𝑇_{𝐴}$ , about relations among the columns of $𝐴$ , or about solutions of $𝐴 𝐱 = 𝐲$ (where $𝐲$ must be replaced by $𝐺 𝐲$ , Proposition 3.2.14). The canonical example is Theorem 3.3.23. It is the method of Section 3.4 and Section 3.5, and later of rank–nullity (Section 4.2) and of the equality of row rank and column rank (Section 4.3).

Used in 33 places

Corollary 3.3.20, Theorem 3.3.23, Exercise 3.3.49, Exercise 3.3.50, Proposition 3.4.1, Corollary 3.4.4, Theorem 3.4.9, Proposition 3.4.15, Proposition 3.4.16, Corollary 3.4.20, Exercise 3.4.45, Theorem 3.5.19, Theorem 3.5.27, Exercise 3.5.42, Exercise 3.5.45, Exercise 3.6.6, Exercise 3.6.7, Exercise 3.6.9, Exercise 3.6.10, Problem 3.3, Problem 3.4, Problem 3.5, Problem 3.6, Problem 3.8, Problem 3.10, Problem 3.11, Problem 3.12, Problem 3.14, Problem 3.17, Theorem 4.2.7, Theorem 4.2.11, Theorem 4.3.8, Problem 4.6.

Theorem 3.3.23 (Invertibility and RREF). Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

, and let

𝐺

be a product of elementary matrices with

𝐺 𝐴 = rref (𝐴)

(Theorem 3.3.10). Then

𝐴

is invertible if and only if

rref (𝐴) = 𝐼_{𝑛}

, and in that case

𝐴^{- 1} = 𝐺

Proof.standard

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Corollary 3.2.11 (Products of elementary matrices), Proposition 3.3.8 (Properties of the output), Definition 2.5.12 (Invertible)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. If

rref (𝐴) = 𝐼_{𝑛}

, then

𝐺 𝐴 = 𝐼_{𝑛}

with

𝐺

invertible. Why does this make

𝐺

a two-sided inverse of

𝐴

Hint 2. Conversely, a square matrix in RREF with

𝑛

pivots is

𝐼_{𝑛}

. If there are fewer pivots, what does the last row look like?

Hint 3. A matrix whose last row is zero has no right inverse. If

𝐴

were invertible, would

𝐺 𝐴

be?

Sketch. If

𝐺 𝐴 = 𝐼_{𝑛}

, then

𝐴 = 𝐺^{- 1}

, so

𝐴 𝐺 = 𝐼_{𝑛}

too and

𝐴^{- 1} = 𝐺

. If

𝑅 = rref (𝐴)

has

𝑛

pivots, its pivot columns are

1, \dots, 𝑛

and

𝑅 = 𝐼_{𝑛}

. Otherwise its last row is zero, so the last row of

𝑅 𝑋

is zero for every

𝑋

and

𝑅

is not invertible; but if

𝐴

were invertible,

𝑅 = 𝐺 𝐴

would be.

Suppose $rref (𝐴) = 𝐼_{𝑛}$ , so $𝐺 𝐴 = 𝐼_{𝑛}$ . Since $𝐺$ is invertible (Corollary 3.2.11), multiplying on the left by $𝐺^{- 1}$ gives $𝐴 = 𝐺^{- 1}$ . Hence $𝐴 𝐺 = 𝐺^{- 1} 𝐺 = 𝐼_{𝑛}$ as well, so $𝐴$ is invertible with $𝐴^{- 1} = 𝐺$ .

Conversely, suppose $𝑅 = rref (𝐴) \neq 𝐼_{𝑛}$ , and let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be its pivot columns. If $𝑟 = 𝑛$ , then $𝑝_{1}, \dots, 𝑝_{𝑛}$ are $𝑛$ increasing numbers among $1, \dots, 𝑛$ , so $𝑝_{𝑠} = 𝑠$ for every $𝑠$ , and by Proposition 3.3.8(c) column $𝑠$ of $𝑅$ is $𝐞_{𝑠}$ ; that is, $𝑅 = 𝐼_{𝑛}$ , which we have excluded. So $𝑟 < 𝑛$ , and row $𝑛$ of $𝑅$ is zero by Proposition 3.3.8(a). Then for every $𝑋 \in 𝐹^{𝑛 \times 𝑛}$ , the $(𝑛, 𝑙)$ entry of $𝑅 𝑋$ is $\sum_{𝑘} 𝑟_{𝑛 𝑘} 𝑥_{𝑘 𝑙} = 0$ , so $𝑅 𝑋 \neq 𝐼_{𝑛}$ ; thus $𝑅$ is not invertible. If $𝐴$ were invertible, then $𝑅 = 𝐺 𝐴$ would be invertible, with inverse $𝐴^{- 1} 𝐺^{- 1}$ . So $𝐴$ is not invertible. □

This gives an algorithm. To find the operations of the run and their product $𝐺$ at the same time, we carry $𝐼_{𝑛}$ along as in Proposition 3.3.11.

Algorithm 3.3.24 (Inverting a matrix by row reduction)

Input: A square matrix $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ .
Output: $𝐴^{- 1}$ , or the conclusion that $𝐴$ is not invertible.

Form the

𝑛 \times 2 𝑛

matrix

(𝐴 | 𝐼_{𝑛})

Row reduce it with Gauss–Jordan elimination, scanning only the first

𝑛

columns in step 1 of Algorithm 3.3.1. The result is

(rref (𝐴) | 𝐺)

If the left block is

𝐼_{𝑛}

, output

𝐴^{- 1} = 𝐺

. Otherwise

𝐴

is not invertible.

The algorithm is correct by Proposition 3.3.11 and Theorem 3.3.23. Two practical remarks. If $𝐴$ is invertible, all $𝑛$ pivots lie in the left block, so restricting the scan makes no difference; it only matters when $𝐴$ is not invertible. And one may stop as soon as the left block acquires a zero row: at that moment the left block is $𝐺^{'} 𝐴$ with $𝐺^{'}$ invertible, and a matrix with a zero row is not invertible (as in the proof above), so neither is $𝐴$ .

Intuition (Why carrying

𝐼_{𝑛}

along works). Column

𝑗

𝐴^{- 1}

is the solution of

𝐴 𝐱 = 𝐞_{𝑗}

, since

𝐴 (𝐴^{- 1} 𝐞_{𝑗}) = 𝐞_{𝑗}

. So inverting

𝐴

means solving the

𝑛

systems

𝐴 𝐱 =

𝐞_{1},

\dots,

𝐴 𝐱 =

𝐞_{𝑛}

, which share the coefficient matrix

𝐴

. Row reducing

(𝐴 | 𝐼_{𝑛})

solves all of them at once: when the left block becomes

𝐼_{𝑛}

, the system

𝐴 𝐱 = 𝐞_{𝑗}

has become

𝐼_{𝑛} 𝐱 = 𝐺 𝐞_{𝑗}

(Proposition 3.2.14), whose solution, column

𝑗

𝐺

, can be read off.

Example 3.3.25 (Inverting a $3 \times 3$ matrix). Let

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

Swapping rows $1$ and $2$ of $(𝐴 | 𝐼_{3})$ and then adding $- 2$ times row $1$ to row $3$ finishes pass $1$ :

(\begin{matrix} 0 & 2 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 & 0 & 1 \end{matrix}) \overset{𝐸_{12}}{⟶} (\begin{matrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 2 & 1 & 1 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 1 \end{matrix})

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

Pass $2$ scales row $2$ by $1 / 2$ and clears column $2$ with $𝐸_{2, - 1, 1}$ and $𝐸_{2, 1, 3}$ ; pass $3$ scales row $3$ by $2$ and clears column $3$ with $𝐸_{3, 1 / 2, 1}$ and $𝐸_{3, - 1 / 2, 2}$ :

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

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

The left block is $𝐼_{3}$ , so $𝐴$ is invertible and

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

As a check, the first row of $𝐴$ times the columns of $𝐴^{- 1}$ gives $(0 + 0 + 1, 0 + 4 - 4, 0 - 2 + 2) =$ $(1, 0, 0)$ , and similarly for the other rows. Fractions appeared along the way even though $𝐴$ and $𝐴^{- 1}$ have integer entries; Exercise 3.3.61 explains when integer arithmetic suffices.

(𝐴 | 𝐼_{3}) ⇝ (\begin{matrix} 1 & 0 & 0 & 0 & - 1 & 1 \\ 0 & 1 & 0 & 0 & 2 & - 1 \\ 0 & 0 & 1 & 1 & - 4 & 2 \end{matrix})

Inverting the matrix of Example 3.3.25:

(𝐴 | 𝐼_{3})

is row reduced, with pivots sought only in the left block. Edit the left block to try other matrices; when it does not reduce to

𝐼_{3}

, the summary says that

𝐴

is not invertible.

Example 3.3.26 (A matrix that is not invertible). Let $𝐴 \in ℚ^{3 \times 3}$ have rows $(1, 2, 3)$ , $(4, 5, 6)$ , $(7, 8, 9)$ . The algorithm gives

(𝐴 | 𝐼_{3}) ⇝ (\begin{matrix} 1 & 0 & - 1 & - 5 / 3 & 2 / 3 & 0 \\ 0 & 1 & 2 & 4 / 3 & - 1 / 3 & 0 \\ 0 & 0 & 0 & 1 & - 2 & 1 \end{matrix}) .

The left block is not $𝐼_{3}$ , so $𝐴$ is not invertible. The last row of $𝐺$ says more: since the last row of $𝐺 𝐴$ is zero, row $1$ of $𝐴$ minus twice row $2$ plus row $3$ is zero, which is easy to confirm.

For square matrices, Theorem 3.3.23 says in particular that an invertible matrix is row equivalent to $𝐼_{𝑛}$ . Section 3.5 turns this into the statement that every invertible matrix is a product of elementary matrices (Theorem 3.5.19), and fits it into the Fundamental Theorems. Also note that in the proof, $𝐺 𝐴 = 𝐼_{𝑛}$ was enough to conclude $𝐴 𝐺 = 𝐼_{𝑛}$ , because $𝐺$ was known to be invertible. That a one-sided inverse of a square matrix is always two-sided is Theorem 3.5.23.

Exercise 3.3.27.routine Let

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

Use Algorithm 3.3.24 to decide whether $𝐴$ is invertible over $ℚ$ , and over $𝔽_{3}$ , and find $𝐴^{- 1}$ when it exists.

Solution.

Uses. Algorithm 3.3.24 (Inverting a matrix by row reduction), Theorem 3.3.23 (Invertibility and RREF)

Hint 1. The two computations agree until some pivot has to be divided by. Which number is it?

Hint 2. Over

ℚ

, pass

3

divides row

3

3

. In

𝔽_{3}

3 = 0

Sketch. After two passes, valid over any field, the third row of

(𝐴 | 𝐼_{3})

(0, 0, 3 | - 1, 2, 1)

. Over

ℚ

3

is a pivot, and

3 𝐴^{- 1}

has rows

(1, - 2, 2)

(1, 1, - 1)

(- 1, 2, 1)

. Over

𝔽_{3}

the third row of the left block is zero, so

𝐴

is not invertible.

Pass $1$ adds $- 1$ times row $1$ to row $3$ ; pass $2$ adds $- 2$ times row $2$ to row $1$ and $2$ times row $2$ to row $3$ . This is the same over any field:

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

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

Over $ℚ$ . Pass $3$ scales row $3$ by $1 / 3$ and then adds $2$ times row $3$ to row $1$ and $- 1$ times row $3$ to row $2$ :

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

So $𝐴$ is invertible over $ℚ$ and

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

Check: the first row of $𝐴$ times the columns of $3 𝐴^{- 1}$ gives $(1 + 2, - 2 + 2, 2 - 2) =$ $(3, 0, 0)$ , and similarly for the others.

Over $𝔽_{3}$ . Here $3 = 0$ , so the last row of the left block above is zero, and the algorithm stops: $𝐴$ is not invertible over $𝔽_{3}$ . (Indeed, in the computation above, the last row of the right block gives $- 1$ times row $1$ of $𝐴$ plus $2$ times row $2$ plus row $3$ , which is $(- 1 + 0 + 1, - 2 + 2 + 0, 0 + 2 + 1) =$ $(0, 0, 3)$ , and $3 = 0$ in $𝔽_{3}$ .)

3.3.6Row echelon form Beyond 21-242

Echelon forms and triangular factorizations are standard in LADW and in numerical linear algebra, but not part of the course.

Clearing above the pivots is not needed to solve a system: once each pivot has zeros below it, the equations can be solved from the bottom up. This gives a cheaper algorithm and a weaker normal form.

Definition 3.3.28 (Row echelon form). A matrix

𝑈 \in 𝐹^{𝑚 \times 𝑛}

is in row echelon form if it satisfies (R1) and (R3): every zero row lies below every nonzero row, and the leading entry of each nonzero row lies strictly to the right of the leading entry of every row above it. The leading entries of the nonzero rows are the pivots of

𝑈

. A row echelon form of

𝐴

is a matrix in row echelon form that is row equivalent to

𝐴

Gaussian elimination is Algorithm 3.3.1 with two changes: step 3 of Algorithm 3.3.1 only declares the pivot, without scaling, and step 4 of Algorithm 3.3.1 clears only the rows below row $𝑘$ . If the pivot is $𝑎$ and row $𝑖 > 𝑘$ has entry $𝑐$ in the pivot column, the pass adds $- ℓ_{𝑖 𝑘}$ times row $𝑘$ to row $𝑖$ , where $ℓ_{𝑖 𝑘} = 𝑐 / 𝑎$ is the multiplier. The proof of Lemma 3.3.7 goes through with (c) weakened to “column $𝑝_{𝑠}$ of $𝑀$ has a nonzero entry in row $𝑠$ and zeros below it” (a pivot row is never changed after its own pass), and as in Proposition 3.3.8 the output is a row echelon form of $𝐴$ .

Example 3.3.29 (Row echelon forms are not unique). Let

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

over

ℚ

. Gaussian elimination gives

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

. Swapping the rows first and then clearing gives

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

, and

rref (𝐴) = 𝐼_{2}

is also a row echelon form of

𝐴

. All three have their pivots in columns

1

and

2

The pivot positions, unlike the entries, are always the same.

Proposition 3.3.30 (Pivots of row echelon forms). If

𝑈

is a row echelon form of

𝐴

, then the columns containing the pivots of

𝑈

are the pivot columns of

𝐴

Proof.standard

Uses. Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.12 (Matrices in RREF)

Hint 1. Turn

𝑈

into a matrix in RREF by row operations that do not move any leading entry.

Hint 2. Scale each nonzero row by the inverse of its leading entry. Then clear above the pivots, one pivot at a time. Check that clearing column

𝑐_{𝑠}

never disturbs a leading entry or a column cleared earlier.

Sketch. Scaling makes the leading entries

1

. Clearing above the pivots (say from the last one up) only adds multiples of a pivot row to rows above it, which changes those rows only to the right of their own leading entries, and never refills a column already cleared, since a pivot row is zero in the columns of later pivots once those are cleared. The result satisfies (R1)–(R4), has the same leading positions as

𝑈

, and is row equivalent to

𝐴

, so it is

rref (𝐴)

Let rows

1, \dots, 𝑟

be the nonzero rows of

𝑈

, with leading entries in columns

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

. First scale each row

𝑠 \leq 𝑟

by the inverse of its leading entry. Then, for

𝑠 = 𝑟, 𝑟 - 1, \dots, 1

in this order, add suitable multiples of row

𝑠

to rows

1, \dots, 𝑠 - 1

so that column

𝑐_{𝑠}

has zeros above row

𝑠

. Row

𝑠

vanishes in the columns before

𝑐_{𝑠}

, so adding a multiple of it to a row

𝑖 < 𝑠

changes row

𝑖

only in columns

𝑐_{𝑠}, \dots, 𝑛

, all to the right of

𝑐_{𝑖}

. Moreover, when we process

𝑠

, row

𝑠

has already been cleared in the columns

𝑐_{𝑠 + 1}, \dots, 𝑐_{𝑟}

(it lies above those pivots), so the columns cleared earlier are not disturbed. The final matrix

𝑅

therefore satisfies (R1)–(R4) with leading entries in columns

𝑐_{1}, \dots, 𝑐_{𝑟}

, and it is row equivalent to

𝑈

, hence to

𝐴

. By Corollary 3.3.18(c),

𝑅 = rref (𝐴)

, so

𝑐_{1}, \dots, 𝑐_{𝑟}

are the pivot columns of

𝐴

(Theorem 3.3.12). □

The second phase of this proof, scaling and clearing upward from the last pivot, is called back substitution. Gaussian elimination followed by back substitution is the usual way of computing $rref (𝐴)$ by hand, and by Corollary 3.3.18 it gives the same answer as Gauss–Jordan elimination.

3.3.7LU and PLU factorizations Beyond 21-242

Suppose we must solve $𝐴 𝐱 = 𝐲$ for one $𝐴$ and many right-hand sides $𝐲$ , as happens constantly in applications. The work of elimination is almost all spent on $𝐴$ and does not depend on $𝐲$ , so it is worth recording once and for all. Gaussian elimination without swaps only adds multiples of a row to rows below it, and the elementary matrices of such operations are lower triangular. This suggests factoring $𝐴$ into triangular pieces.

Definition 3.3.31 (Triangular matrices). A matrix

𝐿 \in 𝐹^{𝑛 \times 𝑛}

is lower triangular if

𝑙_{𝑖 𝑗} = 0

whenever

𝑖 < 𝑗

, and unit lower triangular if moreover

𝑙_{𝑖 𝑖} = 1

for every

𝑖

. Upper triangular and unit upper triangular matrices are defined in the same way with

𝑖 > 𝑗

. A diagonal matrix is one that is both.

Lemma 3.3.32 (Products and inverses of triangular matrices).

(a)If $𝐿, 𝐿^{'} \in 𝐹^{𝑛 \times 𝑛}$ are lower triangular, then so is $𝐿 𝐿^{'}$ , and ${(𝐿 𝐿^{'})}_{𝑖 𝑖} =$ $𝑙_{𝑖 𝑖} 𝑙_{𝑖 𝑖}^{'}$ .
(b)A unit lower triangular matrix is invertible, and its inverse is unit lower triangular.
(c)The same statements hold for upper triangular matrices.

Proof.standard

Uses. Definition 2.4.1 (Matrix product), Proposition 3.2.7 (Row operations are left multiplications), Corollary 3.2.11 (Products of elementary matrices), Proposition 2.4.23 (Transpose of a product)

Hint 1. For (a), in

{(𝐿 𝐿^{'})}_{𝑖 𝑗} =

\sum_{𝑘} 𝑙_{𝑖 𝑘} 𝑙_{𝑘 𝑗}^{'}

, which

𝑘

can give a nonzero term?

Hint 2. For (b), reduce

𝐿

𝐼_{𝑛}

by clearing below the diagonal one column at a time, from left to right, and check that every elementary matrix used is unit lower triangular.

Sketch. (a) A term

𝑙_{𝑖 𝑘} 𝑙_{𝑘 𝑗}^{'}

can be nonzero only if

𝑗 \leq 𝑘 \leq 𝑖

. (b) When column

𝑠

is processed, row

𝑠

𝐞_{𝑠}^{𝖳}

, so adding multiples of it to the rows below only kills the entries below the diagonal in column

𝑠

. This gives

𝐺 𝐿 = 𝐼_{𝑛}

with

𝐺

a product of matrices

𝐸_{𝑠 𝑐 𝑖}

𝑠 < 𝑖

, which are unit lower triangular; so

𝐿^{- 1} = 𝐺

is unit lower triangular by (a). (c) Transpose.

(a) We have ${(𝐿 𝐿^{'})}_{𝑖 𝑗} =$ $\sum_{𝑘} 𝑙_{𝑖 𝑘} 𝑙_{𝑘 𝑗}^{'}$ , and $𝑙_{𝑖 𝑘} 𝑙_{𝑘 𝑗}^{'}$ can be nonzero only if $𝑘 \leq 𝑖$ and $𝑘 \geq 𝑗$ . If $𝑖 < 𝑗$ there is no such $𝑘$ , so ${(𝐿 𝐿^{'})}_{𝑖 𝑗} = 0$ . If $𝑖 = 𝑗$ , only $𝑘 = 𝑖$ contributes, giving $𝑙_{𝑖 𝑖} 𝑙_{𝑖 𝑖}^{'}$ .

(b) Let $𝐿$ be unit lower triangular. For $𝑠 = 1, \dots, 𝑛 - 1$ in turn, and for each $𝑖 > 𝑠$ , add $- 𝑐$ times row $𝑠$ to row $𝑖$ , where $𝑐$ is the current $(𝑖, 𝑠)$ entry. We claim that just before column $𝑠$ is processed, the current matrix is unit lower triangular with columns $1, \dots, 𝑠 - 1$ equal to $𝐞_{1}, \dots, 𝐞_{𝑠 - 1}$ . This holds for $𝑠 = 1$ . If it holds for $𝑠$ , then row $𝑠$ has zeros in columns $1, \dots, 𝑠 - 1$ (as those columns are $𝐞_{1}, \dots, 𝐞_{𝑠 - 1}$ ), a $1$ in column $𝑠$ , and zeros after it; so row $𝑠$ is $𝐞_{𝑠}^{𝖳}$ . Adding a multiple of it to row $𝑖 > 𝑠$ changes only the $(𝑖, 𝑠)$ entry, which becomes $0$ . So afterwards column $𝑠$ is $𝐞_{𝑠}$ and the claim holds for $𝑠 + 1$ . At the end the matrix is $𝐼_{𝑛}$ , so $𝐺 𝐿 = 𝐼_{𝑛}$ , where $𝐺$ is the product of the elementary matrices $𝐸_{𝑠 𝑐 𝑖}$ with $𝑠 < 𝑖$ that were used. Each of these is unit lower triangular (its only off-diagonal entry is in position $(𝑖, 𝑠)$ ), so $𝐺$ is unit lower triangular by (a). Since $𝐺$ is invertible (Corollary 3.2.11), $𝐿 = 𝐺^{- 1}$ , and $𝐿^{- 1} = 𝐺$ .

(c) A matrix is (unit) upper triangular if and only if its transpose is (unit) lower triangular. If $𝑈, 𝑈^{'}$ are upper triangular, then $𝑈 𝑈^{'} =$ ${(𝑈^{' 𝖳} 𝑈^{𝖳})}^{𝖳}$ by Proposition 2.4.23, which is upper triangular by (a), with the same diagonal entries. If $𝑈$ is unit upper triangular, then $𝑈^{𝖳}$ has a unit lower triangular inverse $𝑉$ by (b), and transposing $𝑈^{𝖳} 𝑉 =$ $𝑉 𝑈^{𝖳} =$ $𝐼_{𝑛}$ shows that $𝑉^{𝖳}$ , which is unit upper triangular, is the inverse of $𝑈$ . □

A permutation matrix is a product of swap matrices $𝐸_{𝑖 𝑗}$ (equivalently, a matrix with exactly one $1$ in each row and each column and zeros elsewhere; see Definition 5.2.29).

Theorem 3.3.33 (PLU and LU factorizations). Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ .

(a)There are a permutation matrix $𝑃 \in 𝐹^{𝑚 \times 𝑚}$ , a unit lower triangular $𝐿 \in 𝐹^{𝑚 \times 𝑚}$ , and a matrix $𝑈 \in 𝐹^{𝑚 \times 𝑛}$ in row echelon form such that $𝑃 𝐴 = 𝐿 𝑈$ .
(b)If Gaussian elimination on $𝐴$ never needs a swap, then $𝐴 = 𝐿 𝑈$ , where $𝑈$ is the output of Gaussian elimination and the entry of $𝐿$ in position $(𝑖, 𝑠)$ , for $𝑖 > 𝑠$ , is the multiplier $ℓ_{𝑖 𝑠}$ of pass $𝑠$ (and $0$ if there is no pass $𝑠$ ).

Proof.hard

Uses. Definition 2.4.33 (Block matrix), Definition 3.3.31 (Triangular matrices), Definition 3.3.28 (Row echelon form), Definition 5.2.29 (Permutation matrix), induction on $𝑚$

Hint 1. Induct on the number of rows. Perform the first pass of Gaussian elimination and write the result in block form.

Hint 2. After moving a row with a nonzero entry

𝑎

in the first nonzero column

𝑗

to the top, write the first pass of Gaussian elimination as a factorization

𝑃_{1} 𝐴 =

(\begin{matrix} 1 & 0 \\ ℓ & 𝐼 \end{matrix}) (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝐴^{'} \end{matrix})

Hint 3. Apply the induction hypothesis

𝑃^{'} 𝐴^{'} = 𝐿^{'} 𝑈^{'}

and assemble

𝑃

𝐿

𝑈

in block form. Where does

𝑃^{'}

have to act on

ℓ

Sketch. Bring a nonzero entry

𝑎

of the first nonzero column

𝑗

to the top with a swap

𝑃_{1}

. With

𝐛

the rest of column

𝑗

and

ℓ = 𝑎^{- 1} 𝐛

𝑃_{1} 𝐴 =

(\begin{matrix} 1 & 0 \\ ℓ & 𝐼 \end{matrix}) (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝐴^{'} \end{matrix})

, the first pass of elimination. If

𝑃^{'} 𝐴^{'} = 𝐿^{'} 𝑈^{'}

, then

𝑃 = (\begin{matrix} 1 & 0 \\ 0 & 𝑃^{'} \end{matrix}) 𝑃_{1}

𝐿 = (\begin{matrix} 1 & 0 \\ 𝑃^{'} ℓ & 𝐿^{'} \end{matrix})

𝑈 = (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝑈^{'} \end{matrix})

work, by block multiplication. Without swaps

𝑃 = 𝐼_{𝑚}

, and the columns of

𝐿

are the multipliers, pass by pass.

(a) We induct on $𝑚$ . If $𝑚 = 1$ , take $𝑃 = 𝐿 = (1)$ and $𝑈 = 𝐴$ ; a single row is in row echelon form. Let $𝑚 \geq 2$ . If $𝐴 = 0$ , take $𝑃 = 𝐿 = 𝐼_{𝑚}$ and $𝑈 = 0$ . Otherwise, let $𝑗$ be the first nonzero column of $𝐴$ , choose a row $𝑖$ with $𝑎_{𝑖 𝑗} \neq 0$ , and let $𝑃_{1} = 𝐸_{1 𝑖}$ (or $𝑃_{1} = 𝐼_{𝑚}$ if $𝑖 = 1$ ). Then $𝐵 = 𝑃_{1} 𝐴$ has first $𝑗 - 1$ columns zero and a nonzero entry $𝑎 = 𝑏_{1 𝑗}$ . Write

𝐵 = (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 𝐛 & 𝐵^{'} \end{matrix}),

where the zero blocks have $𝑗 - 1$ columns, $𝐛 \in 𝐹^{𝑚 - 1}$ is the rest of column $𝑗$ , $𝐰 \in 𝐹^{1 \times (𝑛 - 𝑗)}$ , and $𝐵^{'} \in$ $𝐹^{(𝑚 - 1) \times (𝑛 - 𝑗)}$ . Let $ℓ = 𝑎^{- 1} 𝐛$ and $𝐴^{'} = 𝐵^{'} - ℓ 𝐰$ . Multiplying blockwise (Definition 2.4.33),

𝐵 = (\begin{matrix} 1 & 0 \\ ℓ & 𝐼_{𝑚 - 1} \end{matrix}) (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝐴^{'} \end{matrix}),

(3.3.3)

since the lower blocks of the product are $ℓ 𝑎 = 𝐛$ and $ℓ 𝐰 + 𝐴^{'} = 𝐵^{'}$ . (The right factor is the result of the first pass of Gaussian elimination on $𝐵$ .) If $𝑗 = 𝑛$ , the blocks $𝐰$ , $𝐵^{'}$ , $𝐴^{'}$ are empty, and (3.3.3) is the required factorization with $𝑃 = 𝑃_{1}$ . If $𝑗 < 𝑛$ , the induction hypothesis gives a permutation matrix $𝑃^{'}$ , a unit lower triangular $𝐿^{'}$ , and a row echelon form $𝑈^{'}$ with $𝑃^{'} 𝐴^{'} = 𝐿^{'} 𝑈^{'}$ . Put

𝑃 = (\begin{matrix} 1 & 0 \\ 0 & 𝑃^{'} \end{matrix}) 𝑃_{1}, 𝐿 = (\begin{matrix} 1 & 0 \\ 𝑃^{'} ℓ & 𝐿^{'} \end{matrix}), 𝑈 = (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝑈^{'} \end{matrix}) .

By (3.3.3) and blockwise multiplication,

𝑃 𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 𝑃^{'} \end{matrix}) 𝐵 = (\begin{matrix} 1 & 0 \\ 𝑃^{'} ℓ & 𝑃^{'} \end{matrix}) (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝐴^{'} \end{matrix}) = (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 𝑃^{'} ℓ 𝑎 & 𝑃^{'} ℓ 𝐰 + 𝑃^{'} 𝐴^{'} \end{matrix}),

𝐿 𝑈 = (\begin{matrix} 1 & 0 \\ 𝑃^{'} ℓ & 𝐿^{'} \end{matrix}) (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 0 & 𝑈^{'} \end{matrix}) = (\begin{matrix} 0 & 𝑎 & 𝐰 \\ 0 & 𝑃^{'} ℓ 𝑎 & 𝑃^{'} ℓ 𝐰 + 𝐿^{'} 𝑈^{'} \end{matrix}),

and these agree because $𝑃^{'} 𝐴^{'} = 𝐿^{'} 𝑈^{'}$ . Here $𝐿$ is unit lower triangular because $𝐿^{'}$ is. $𝑃$ is a permutation matrix, because if $𝑃^{'}$ is a product of swaps $𝐸_{𝑘 𝑙}$ of size $𝑚 - 1$ , then $(\begin{matrix} 1 & 0 \\ 0 & 𝑃^{'} \end{matrix})$ is the product of the swaps $𝐸_{(𝑘 + 1) (𝑙 + 1)}$ of size $𝑚$ . Finally, $𝑈$ is in row echelon form: its first row has leading entry $𝑎$ in column $𝑗$ , its other rows vanish in columns $1, \dots, 𝑗$ , and below the first row it has the shape of $𝑈^{'}$ , which is in row echelon form.

(b) If Gaussian elimination needs no swaps, then at every stage of the induction the $(1, 𝑗)$ entry is already nonzero and we may take $𝑃_{1} = 𝐼$ ; then $𝑃 = 𝐼_{𝑚}$ . In (3.3.3) the entries of $ℓ = 𝑎^{- 1} 𝐛$ are the multipliers of the first pass, and $𝐴^{'}$ is the lower right part of the matrix after the first pass, on which the later passes operate. So by induction column $𝑠$ of $𝐿$ holds the multipliers of pass $𝑠$ below the diagonal, and $𝑈$ is the output of Gaussian elimination. □

Example 3.3.34 (An LU factorization). Let

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

Pass $1$ uses the multipliers $ℓ_{21} = 2$ and $ℓ_{31} = 4$ and leaves rows $(0, 1, 1)$ and $(0, 3, 5)$ ; pass $2$ uses $ℓ_{32} = 3$ and leaves $(0, 0, 2)$ . So

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

The multipliers drop into $𝐿$ with no further computation. By contrast, $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ has no LU factorization: if $(\begin{matrix} 1 & 0 \\ ℓ & 1 \end{matrix}) (\begin{matrix} 𝑢 & 𝑣 \\ 0 & 𝑤 \end{matrix}) =$ $(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})$ , then $𝑢 = 0$ from the $(1, 1)$ entry, and then the $(2, 1)$ entry is $ℓ 𝑢 = 0 \neq 1$ . A swap is unavoidable here, and $𝑃 = 𝐸_{12}$ gives $𝑃 𝐴 = 𝐼_{2} = 𝐼_{2} 𝐼_{2}$ .

Once $𝑃 𝐴 = 𝐿 𝑈$ is known, $𝐴 𝐱 = 𝐲$ is equivalent to $𝐿 (𝑈 𝐱) = 𝑃 𝐲$ . One solves $𝐿 𝐳 = 𝑃 𝐲$ from the top down ( $𝑧_{1}$ first, then $𝑧_{2}$ , and so on: forward substitution) and then $𝑈 𝐱 = 𝐳$ from the bottom up (back substitution). For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ each of these costs about $𝑛^{2}$ arithmetic operations, while the factorization itself costs a multiple of $𝑛^{3}$ :

Remark 3.3.35 (How much work elimination takes). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be invertible, and suppose no swaps are needed. In pass $𝑘$ of Gauss–Jordan elimination the pivot is in position $(𝑘, 𝑘)$ , and the pivot row vanishes in columns $1, \dots, 𝑘 - 1$ (Lemma 3.3.7(d)). So the scaling touches $𝑛 - 𝑘 + 1$ entries, and each of the $𝑛 - 1$ replacements touches $𝑛 - 𝑘 + 1$ entries, with one multiplication and one addition each. The total number of multiplications is at most

\sum_{𝑘 = 1}^{𝑛} 𝑛 (𝑛 - 𝑘 + 1) = 𝑛 \cdot \frac{𝑛 (𝑛 + 1)}{2} \approx \frac{𝑛^{3}}{2},

and there are about as many additions: roughly $𝑛^{3}$ arithmetic operations in all. Gaussian elimination only clears the $𝑛 - 𝑘$ rows below the pivot, which costs

\sum_{𝑘 = 1}^{𝑛} (𝑛 - 𝑘) (𝑛 - 𝑘 + 1) = \frac{𝑛^{3} - 𝑛}{3}

multiplications and divisions, and about as many additions: about $2 𝑛^{3} / 3$ operations in all; back substitution adds only about $𝑛^{2}$ per right-hand side. Either way, doubling the size of the matrix multiplies the work by about $8$ . A system with a few thousand unknowns is routine for a computer, whereas the formula for the solution that comes out of determinants in Section 5.5 involves sums with $𝑛!$ terms.

Example 3.3.36 (A PLU factorization). For the matrix $𝐴$ of Example 3.3.25, the $(1, 1)$ entry is $0$ , so the proof of Theorem 3.3.33 starts with $𝑃_{1} = 𝐸_{12}$ . Then $ℓ = (0, 2)$ , and the remaining $2 \times 2$ block $𝐴^{'} = (\begin{matrix} 2 & 1 \\ - 1 & 0 \end{matrix})$ needs no swap: its multiplier is $- 1 / 2$ , leaving $1 / 2$ . So

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

3.3.8Symmetric matrices: $𝐿 𝐷 𝐿^{𝖳}$ Beyond 21-242

A matrix $𝐴$ is symmetric if $𝐴^{𝖳} = 𝐴$ . Elimination does not see symmetry: the $𝑈$ of an LU factorization of a symmetric matrix is usually not symmetric. But the symmetry is hiding in the factorization, and it can be recovered.

Theorem 3.3.37 ( $𝐿 𝐷 𝐿^{𝖳}$ factorization). Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ be symmetric, and suppose $𝐴 = 𝐿 𝑈$ with $𝐿$ unit lower triangular and $𝑈$ upper triangular with nonzero diagonal entries. Let $𝐷$ be the diagonal matrix with the same diagonal entries as $𝑈$ . Then $𝑈 = 𝐷 𝐿^{𝖳}$ , so

𝐴 = 𝐿 𝐷 𝐿^{𝖳} .

Proof.hard

Uses. Lemma 3.3.32 (Products and inverses of triangular matrices), Proposition 2.4.23 (Transpose of a product), Definition 3.3.31 (Triangular matrices)

Hint 1. Factor

𝑈 = 𝐷 𝑈_{1}

with

𝑈_{1}

unit upper triangular, so

𝐴 = 𝐿 𝐷 𝑈_{1}

. Transpose this equation.

Hint 2. You get

𝐿 𝐷 𝑈_{1} =

𝑈_{1}^{𝖳} 𝐷 𝐿^{𝖳}

. Rearrange it so that one side is lower triangular and the other upper triangular.

Hint 3. A matrix that is both lower and upper triangular is diagonal. Compare diagonal entries.

Sketch. Write

𝑈 = 𝐷 𝑈_{1}

with

𝑈_{1} = 𝐷^{- 1} 𝑈

unit upper triangular. Transposing

𝐴 = 𝐿 𝐷 𝑈_{1}

gives

𝐴 = 𝑈_{1}^{𝖳} 𝐷 𝐿^{𝖳}

, and moving the outer factors across shows that

{(𝑈_{1}^{𝖳})}^{- 1} 𝐿 𝐷

, which is lower triangular with diagonal

𝐷

, equals

𝐷 𝐿^{𝖳} 𝑈_{1}^{- 1}

, which is upper triangular. So both equal

𝐷

. Hence

{(𝑈_{1}^{𝖳})}^{- 1} 𝐿 = 𝐼_{𝑛}

, so

𝑈_{1} = 𝐿^{𝖳}

and

𝑈 = 𝐷 𝐿^{𝖳}

Since the diagonal entries $𝑑_{𝑖} = 𝑢_{𝑖 𝑖}$ are nonzero, $𝐷$ is invertible, with $𝐷^{- 1}$ diagonal with entries $𝑑_{𝑖}^{- 1}$ . Let $𝑈_{1} = 𝐷^{- 1} 𝑈$ ; this scales row $𝑖$ of $𝑈$ by $𝑑_{𝑖}^{- 1}$ , so $𝑈_{1}$ is unit upper triangular, and $𝑈 = 𝐷 𝑈_{1}$ . Then $𝐴 = 𝐿 𝐷 𝑈_{1}$ , and transposing (Proposition 2.4.23, with $𝐷^{𝖳} = 𝐷$ ) gives

𝐿 𝐷 𝑈_{1} = 𝐴 = 𝐴^{𝖳} = 𝑈_{1}^{𝖳} 𝐷 𝐿^{𝖳} .

Here $𝑈_{1}^{𝖳}$ is unit lower triangular and $𝐿^{𝖳}$ is unit upper triangular. Multiplying on the left by ${(𝑈_{1}^{𝖳})}^{- 1}$ and on the right by $𝑈_{1}^{- 1}$ , which exist by Lemma 3.3.32, gives

{(𝑈_{1}^{𝖳})}^{- 1} 𝐿 𝐷 = 𝐷 𝐿^{𝖳} 𝑈_{1}^{- 1} .

By Lemma 3.3.32, ${(𝑈_{1}^{𝖳})}^{- 1} 𝐿$ is unit lower triangular, so the left side is lower triangular with diagonal entries $𝑑_{1}, \dots, 𝑑_{𝑛}$ ; the right side is upper triangular. So both sides are diagonal, and comparing diagonals they equal $𝐷$ . Thus ${(𝑈_{1}^{𝖳})}^{- 1} 𝐿 𝐷 = 𝐷$ , and multiplying on the right by $𝐷^{- 1}$ gives ${(𝑈_{1}^{𝖳})}^{- 1} 𝐿 = 𝐼_{𝑛}$ , that is, $𝐿 = 𝑈_{1}^{𝖳}$ . Hence $𝑈_{1} = 𝐿^{𝖳}$ and $𝑈 = 𝐷 𝐿^{𝖳}$ . □

The hypothesis holds whenever $𝐴$ is invertible and Gaussian elimination on $𝐴$ needs no swaps. Then $𝐴 = 𝐿 𝑈$ by Theorem 3.3.33(b), and by Proposition 3.3.30 the pivots of $𝑈$ lie in the pivot columns of $𝐴$ , which are $1, \dots, 𝑛$ since $rref (𝐴) = 𝐼_{𝑛}$ (Theorem 3.3.23); so the diagonal entries of $𝑈$ are its pivots, which are nonzero.

Example 3.3.38 (An $𝐿 𝐷 𝐿^{𝖳}$ factorization). For the symmetric matrix

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

Gaussian elimination uses the multipliers $ℓ_{21} = 2$ , $ℓ_{31} = 3$ , $ℓ_{32} = 2$ , and its output $𝑈$ has rows $(1, 2, 3)$ , $(0, - 1, - 2)$ , $(0, 0, 1)$ . So $𝐷 = diag (1, - 1, 1)$ and

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

Over $ℝ$ , when every diagonal entry of $𝐷$ is positive, $𝐷 = 𝐷_{0}^{2}$ with $𝐷_{0}$ diagonal with entries $\sqrt{𝑑_{𝑖}}$ , and $𝐴 =$ $(𝐿 𝐷_{0}) {(𝐿 𝐷_{0})}^{𝖳}$ is a product of a lower triangular matrix and its transpose. This is the Cholesky factorization of a positive definite matrix (Section 8.3). The signs of the $𝑑_{𝑖}$ are not an accident of the computation either: by Sylvester’s law of inertia (Section 12.2), the numbers of positive and of negative $𝑑_{𝑖}$ are determined by $𝐴$ .

Exercises

Exercise 3.3.39.routine Let

𝐴 = (\begin{matrix} 1 & 2 & 1 & 0 & 1 \\ 2 & 4 & 3 & 1 & 0 \\ 1 & 2 & 2 & 2 & 1 \end{matrix}) \in ℚ^{3 \times 5} .

(a) Find $rref (𝐴)$ , its pivot columns, and a matrix $𝐺$ with $𝐺 𝐴 = rref (𝐴)$ .

(b) Without further row reduction, write each non-pivot column of $𝐴$ as a linear combination of the pivot columns.

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Proposition 3.3.11 (Carrying extra columns along), Corollary 3.3.19 (Pivot columns, intrinsically)

Hint 1. No swaps are needed. Carry

𝐼_{3}

along to get

𝐺

Hint 2. For (b), the entries of a non-pivot column of

rref (𝐴)

are the coefficients (Corollary 3.3.19).

Sketch.

rref (𝐴)

has rows

(1, 2, 0, 0, 5)

(0, 0, 1, 0, - 4)

(0, 0, 0, 1, 2)

, so the pivot columns are

1, 3, 4

, and

𝐺

has rows

(4, - 2, 1)

(- 3, 2, - 1)

(1, - 1, 1)

. Then

𝐚_{2} = 2 𝐚_{1}

and

𝐚_{5} =

5 𝐚_{1} -

4 𝐚_{3} +

2 𝐚_{4}

(a) We row reduce $(𝐴 | 𝐼_{3})$ , scanning only the first five columns (Proposition 3.3.11). Pass $1$ : the pivot is the $(1, 1)$ entry; add $- 2$ times row $1$ to row $2$ and $- 1$ times row $1$ to row $3$ . Pass $2$ : column $2$ now vanishes in rows $2$ and $3$ , so the pivot is the $(2, 3)$ entry, which is $1$ ; add $- 1$ times row $2$ to rows $1$ and $3$ . Pass $3$ : the pivot is the $(3, 4)$ entry, which is $1$ ; add row $3$ to row $1$ and $- 1$ times row $3$ to row $2$ . The stages after each pass are

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

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

rref (𝐴) = (\begin{matrix} 1 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & - 4 \\ 0 & 0 & 0 & 1 & 2 \end{matrix}), 𝐺 = (\begin{matrix} 4 & - 2 & 1 \\ - 3 & 2 & - 1 \\ 1 & - 1 & 1 \end{matrix}),

with pivot columns $1, 3, 4$ . As a check, row $1$ of $𝐺 𝐴$ is

4 (1, 2, 1, 0, 1) - 2 (2, 4, 3, 1, 0) + (1, 2, 2, 2, 1) = (1, 2, 0, 0, 5) .

(b) By Corollary 3.3.19(b), $𝐚_{2} = 2 𝐚_{1}$ and $𝐚_{5} =$ $5 𝐚_{1} -$ $4 𝐚_{3} +$ $2 𝐚_{4}$ . Indeed,

5 (1, 2, 1) - 4 (1, 3, 2) + 2 (0, 1, 2) = (1, 0, 1) = 𝐚_{5} .

Exercise 3.3.40.routine Find the reduced row echelon form of

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

over $ℚ$ and over $𝔽_{2}$ . Where do the two computations part ways, and why?

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Corollary 3.3.19 (Pivot columns, intrinsically)

Hint 1. The first two passes involve only the scalars

1

and

- 1

, so they read the same over both fields (remember

- 1 = 1

𝔽_{2}

Hint 2. After two passes the third row is

(0, 0, 2, 0)

. Can

2

be a pivot?

Sketch. After two passes both computations reach the rows

(1, 0, - 1, 0)

(0, 1, 1, 1)

(0, 0, 2, 0)

. Over

ℚ

2

is a pivot and

rref (𝐴)

has rows

(1, 0, 0, 0)

(0, 1, 0, 1)

(0, 0, 1, 0)

. Over

𝔽_{2}

2 = 0

and

- 1 = 1

, so

rref (𝐴)

has rows

(1, 0, 1, 0)

(0, 1, 1, 1)

(0, 0, 0, 0)

Pass $1$ adds $- 1$ times row $1$ to row $3$ , which becomes $(0, - 1, 1, - 1)$ . Pass $2$ , with pivot $(2, 2)$ , adds $- 1$ times row $2$ to row $1$ and row $2$ to row $3$ :

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

So far every operation makes sense over any field.

Over $ℚ$ . The third row has the entry $2 \neq 0$ in column $3$ , which becomes the pivot of pass $3$ . Scaling row $3$ by $1 / 2$ and adding row $3$ to row $1$ and $- 1$ times row $3$ to row $2$ gives

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

Over $𝔽_{2}$ . Here $2 = 0$ and $- 1 = 1$ , so after pass $2$ the matrix is

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

Its unpivoted row is zero, so the algorithm halts, and this is $rref (𝐴)$ over $𝔽_{2}$ .

The computations part ways at the entry $2$ in pass $3$ , which is a valid pivot over $ℚ$ and is $0$ over $𝔽_{2}$ . In terms of Corollary 3.3.19: over $𝔽_{2}$ the third column of $𝐴$ is the sum of the first two, $(1, 0, 1) +$ $(1, 1, 0) =$ $(0, 1, 1)$ , so column $3$ is not a pivot column. Over $ℚ$ , a combination $𝑥 (1, 0, 1) +$ $𝑦 (1, 1, 0)$ equal to $(0, 1, 1)$ would need $𝑥 = 1$ and $𝑦 = 1$ (from the third and second entries), but then the first entry is $2 \neq 0$ ; so the third column is a pivot column.

Exercise 3.3.41.routine Over $ℂ$ , let

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

Use Algorithm 3.3.24 to find $𝐴^{- 1}$ , and to show that $𝐵$ is not invertible. For $𝐵$ , find the linear relation among its rows that the algorithm produces.

Solution.

Uses. Algorithm 3.3.24 (Inverting a matrix by row reduction), Theorem 3.3.23 (Invertibility and RREF)

Hint 1. In pass

1

for

𝐴

, add

- 𝑖

times row

1

to row

3

, and remember

𝑖^{2} = - 1

Hint 2. Pass

3

for

𝐴

divides by

1 - 𝑖

, whose inverse is

(1 + 𝑖) / 2

. For

𝐵

, the left block gets a zero row in pass

2

; read the relation off the right block.

Sketch. For

𝐴

, the passes use

𝐸_{1, - 𝑖, 3}

, then

𝐸_{2, - 𝑖, 1}

and

𝐸_{2, - 1, 3}

, then a scaling by

(1 + 𝑖) / 2

and two replacements; the inverse has entries

(\pm 1 \pm 𝑖) / 2

. For

𝐵

, two passes leave the left row

(0, 0, 0)

with right row

(- 𝑖, - 1, 1)

, so

𝐵

is not invertible, and

- 𝑖

times row

1

, minus row

2

, plus row

3

is zero.

The matrix $𝐴$ . Pass $1$ adds $- 𝑖$ times row $1$ to row $3$ , which becomes $(0, - 𝑖^{2}, 1 | - 𝑖, 0, 1) =$ $(0, 1, 1 | - 𝑖, 0, 1)$ . Pass $2$ (pivot $(2, 2)$ ) adds $- 𝑖$ times row $2$ to row $1$ and $- 1$ times row $2$ to row $3$ :

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

Pass $3$ scales row $3$ by ${(1 - 𝑖)}^{- 1} = (1 + 𝑖) / 2$ , which turns the right part of row $3$ into $\frac{1}{2} (1 - 𝑖, - 1 - 𝑖, 1 + 𝑖)$ , and then adds $- 1$ times row $3$ to row $1$ and $- 𝑖$ times row $3$ to row $2$ . The result is

𝐴^{- 1} = \frac{1}{2} (\begin{matrix} 1 + 𝑖 & 1 - 𝑖 & - 1 - 𝑖 \\ - 1 - 𝑖 & 1 + 𝑖 & 1 - 𝑖 \\ 1 - 𝑖 & - 1 - 𝑖 & 1 + 𝑖 \end{matrix}) .

Check: the first row of $𝐴$ times the first column of $2 𝐴^{- 1}$ is $(1 + 𝑖) +$ $𝑖 (- 1 - 𝑖) =$ $1 +$ $𝑖 -$ $𝑖 +$ $1 =$ $2$ , times the second column it is $(1 - 𝑖) + 𝑖 (1 + 𝑖) = 0$ , and times the third $(- 1 - 𝑖) +$ $𝑖 (1 - 𝑖) =$ $0$ ; the other rows are similar.

The matrix $𝐵$ . Pass $1$ adds $- 𝑖$ times row $1$ to row $3$ : the left part becomes $(𝑖, 1, 0) -$ $𝑖 (1, 0, 𝑖) =$ $(0, 1, 1)$ and the right part $(- 𝑖, 0, 1)$ . Pass $2$ adds $- 1$ times row $2$ to row $3$ , which becomes $(0, 0, 0 | - 𝑖, - 1, 1)$ . The left block now has a zero row, so $𝐵$ is not invertible. The right part of the zero row says that $- 𝑖$ times row $1$ of $𝐵$ , minus row $2$ , plus row $3$ , is zero:

- 𝑖 (1, 0, 𝑖) - (0, 1, 1) + (𝑖, 1, 0) = (0, 0, 1 - 1) = 𝟎 .

Exercise 3.3.42.standard For a scalar $𝑐$ , let

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

(a) Find $rref (𝐴_{𝑐})$ for every $𝑐 \in ℝ$ . For which $𝑐$ is $𝐴_{𝑐}$ invertible?

(b) Answer the same questions over $𝔽_{3}$ , for $𝑐 \in 𝔽_{3}$ .

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Theorem 3.3.23 (Invertibility and RREF)

Hint 1. Pass

1

works for every

𝑐

. Write down the resulting rows

2

and

3

Hint 2. They are

(0, 𝑐 - 4, 0)

and

(0, 0, 𝑐 - 1)

. Split into cases according to which of

𝑐 - 4

and

𝑐 - 1

vanish. In

𝔽_{3}

4 = 1

Sketch. After pass

1

the rows are

(1, 2, 1)

(0, 𝑐 - 4, 0)

(0, 0, 𝑐 - 1)

. Over

ℝ

rref (𝐴_{𝑐}) = 𝐼_{3}

for

𝑐 \neq 1, 4

;

rref (𝐴_{4})

has rows

(1, 2, 0)

(0, 0, 1)

𝟎

;

rref (𝐴_{1})

has rows

(1, 0, 1)

(0, 1, 0)

𝟎

. Over

𝔽_{3}

𝑐 - 4 = 𝑐 - 1

rref (𝐴_{1})

has rows

(1, 2, 1)

𝟎

𝟎

, and

rref (𝐴_{𝑐}) = 𝐼_{3}

for

𝑐 = 0, 2

Pass $1$ adds $- 2$ times row $1$ to row $2$ and $- 1$ times row $1$ to row $3$ , giving

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

(a) If $𝑐 \neq 4$ and $𝑐 \neq 1$ : pass $2$ scales row $2$ by ${(𝑐 - 4)}^{- 1}$ , making it $(0, 1, 0)$ , and adds $- 2$ times it to row $1$ , which becomes $(1, 0, 1)$ . Pass $3$ scales row $3$ to $(0, 0, 1)$ and subtracts it from row $1$ . So $rref (𝐴_{𝑐}) = 𝐼_{3}$ .

If $𝑐 = 4$ : the rows are $(1, 2, 1)$ , $(0, 0, 0)$ , $(0, 0, 3)$ . In pass $2$ , column $2$ vanishes in rows $2$ and $3$ , so the scan moves to column $3$ ; the $(2, 3)$ entry is $0$ , so rows $2$ and $3$ are swapped. Scaling by $1 / 3$ and subtracting the new row $2$ from row $1$ gives

rref (𝐴_{4}) = (\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) .

If $𝑐 = 1$ : the rows are $(1, 2, 1)$ , $(0, - 3, 0)$ , $(0, 0, 0)$ . Pass $2$ scales row $2$ to $(0, 1, 0)$ and adds $- 2$ times it to row $1$ , so

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

By Theorem 3.3.23, $𝐴_{𝑐}$ is invertible exactly when $𝑐 \neq 1$ and $𝑐 \neq 4$ .

(b) In $𝔽_{3}$ , $𝑐 - 4 = 𝑐 - 1$ , since $3 = 0$ . If $𝑐 = 1$ , rows $2$ and $3$ are both zero after pass $1$ , and

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

If $𝑐 = 0$ or $𝑐 = 2$ , then $𝑐 - 4 = 𝑐 - 1 \neq 0$ , and the computation of the first case of (a) applies verbatim: $rref (𝐴_{𝑐}) = 𝐼_{3}$ . So over $𝔽_{3}$ , $𝐴_{𝑐}$ is invertible exactly when $𝑐 \neq 1$ .

Exercise 3.3.43.routine Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝑅 = rref (𝐴)$ .

(a)Show that $rref (𝑐 𝐴) = 𝑅$ for every nonzero $𝑐 \in 𝐹$ .
(b)Show that $rref ((𝐴 | 𝐴)) =$ $(𝑅 | 𝑅)$ .
(c)Let $(\begin{matrix} 𝐴 \\ 𝐴 \end{matrix}) \in 𝐹^{2 𝑚 \times 𝑛}$ be the matrix with $𝐴$ stacked on top of itself. Show that $rref (\begin{matrix} 𝐴 \\ 𝐴 \end{matrix}) = (\begin{matrix} 𝑅 \\ 0 \end{matrix})$ .

Solution.

Uses. Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.12 (Matrices in RREF), Proposition 3.3.11 (Carrying extra columns along)

Hint 1. In each part, find a matrix in RREF that is row equivalent to the given one, and use Corollary 3.3.18(c).

Hint 2. For (b),

𝐺 (𝐴 | 𝐴) = (𝑅 | 𝑅)

. Check (R1)–(R4) for

(𝑅 | 𝑅)

: where are its leading entries?

Hint 3. For (c), first subtract each of the top rows from the corresponding bottom row.

Sketch. (a) Scaling every row by

𝑐

turns

𝐴

into

𝑐 𝐴

, so

𝑐 𝐴 \sim 𝐴

. (b)

(𝐴 | 𝐴) \sim (𝑅 | 𝑅)

, whose nonzero rows have their leading entries in the left block, and whose pivot columns are those of

𝑅

; so it satisfies (R1)–(R4). (c) Subtracting rows gives

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

, and the run of the algorithm on

𝐴

, performed on the top

𝑚

rows, gives

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

, which satisfies (R1)–(R4).

In each part we exhibit a matrix that satisfies (R1)–(R4) and is row equivalent to the given matrix; by Corollary 3.3.18(c) it is the reduced row echelon form.

(a) Scaling each of the $𝑚$ rows of $𝐴$ by $𝑐$ turns $𝐴$ into $𝑐 𝐴$ , so $𝑐 𝐴 \sim 𝐴 \sim 𝑅$ , and $𝑅$ is in RREF. So $rref (𝑐 𝐴) = 𝑅$ .

(b) By Proposition 3.3.11(a), $𝐺 (𝐴 | 𝐴) =$ $(𝐺 𝐴 | 𝐺 𝐴) =$ $(𝑅 | 𝑅)$ , so $(𝐴 | 𝐴) \sim (𝑅 | 𝑅)$ . The nonzero rows of $(𝑅 | 𝑅)$ are the nonzero rows of $𝑅$ , in the same positions, and since the left block is $𝑅$ , their leading entries are the leading entries of $𝑅$ . So (R1), (R2), and (R3) hold for $(𝑅 | 𝑅)$ because they hold for $𝑅$ . The columns containing leading entries are the pivot columns of $𝑅$ , in the left block, and each of them is a standard basis vector; this is (R4). So $rref ((𝐴 | 𝐴)) =$ $(𝑅 | 𝑅)$ .

(c) For $𝑖 = 1, \dots, 𝑚$ , add $- 1$ times row $𝑖$ to row $𝑚 + 𝑖$ . This turns $(\begin{matrix} 𝐴 \\ 𝐴 \end{matrix})$ into $(\begin{matrix} 𝐴 \\ 0 \end{matrix})$ . Then perform the row operations of the run of Gauss–Jordan elimination on $𝐴$ , applied to rows $1, \dots, 𝑚$ only; they turn $(\begin{matrix} 𝐴 \\ 0 \end{matrix})$ into $(\begin{matrix} 𝑅 \\ 0 \end{matrix})$ . This matrix satisfies (R1)–(R4): its nonzero rows are those of $𝑅$ , at the top, and it is $𝑅$ with $𝑚$ zero rows appended. So $rref (\begin{matrix} 𝐴 \\ 𝐴 \end{matrix}) = (\begin{matrix} 𝑅 \\ 0 \end{matrix})$ .

Exercise 3.3.44.standard Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐵 \in 𝐹^{𝑚 \times 𝑝}$ .

(a)Show that the first $𝑛$ columns of $rref ((𝐴 | 𝐵))$ form $rref (𝐴)$ .
(b)Give an example in which the last $𝑝$ columns of $rref ((𝐴 | 𝐵))$ differ from the matrix $𝐺 𝐵$ of Proposition 3.3.11.

Solution.

Uses. Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Proposition 3.3.11 (Carrying extra columns along), Theorem 3.3.12 (Matrices in RREF), Corollary 3.3.18 (RREF and row equivalence)

Hint 1. Write

rref ((𝐴 | 𝐵)) =

(𝑆 | 𝑇) =

𝐻 (𝐴 | 𝐵)

with

𝐻

invertible. Then

𝑆 = 𝐻 𝐴

. It suffices to show that

𝑆

is in RREF. Why?

Hint 2. Some nonzero rows of

(𝑆 | 𝑇)

may have their leading entry in the right block. What do these rows look like in

𝑆

, and where are they?

Hint 3. For (b), try

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

and

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

Sketch.

(𝑆 | 𝑇) =

(𝐻 𝐴 | 𝐻 𝐵)

. The rows of

(𝑆 | 𝑇)

whose leading entries lie in the left block come first, by (R3), and the remaining rows vanish in the left block; so

𝑆

satisfies (R1)–(R4), with pivot columns the pivot columns of

(𝑆 | 𝑇)

among

1, \dots, 𝑛

. Then

𝑆 =

rref (𝐻 𝐴) =

rref (𝐴)

. For

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

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

rref ((𝐴 | 𝐵)) = 𝐼_{2}

, while

𝐺 𝐵 = (1, 1)

(a) By Theorem 3.3.10 and Proposition 3.3.11(a), $rref ((𝐴 | 𝐵)) =$ $𝐻 (𝐴 | 𝐵) =$ $(𝐻 𝐴 | 𝐻 𝐵)$ for some invertible $𝐻$ . Write $𝑆 = 𝐻 𝐴$ and $𝑇 = 𝐻 𝐵$ . We show that $𝑆$ is in RREF; then $𝑆 =$ $rref (𝑆) =$ $rref (𝐻 𝐴) =$ $rref (𝐴)$ by Corollary 3.3.18(a).

Let rows $1, \dots, 𝑟$ be the nonzero rows of $(𝑆 | 𝑇)$ , with leading entries in columns $𝑐_{1} < \dots < 𝑐_{𝑟}$ , and let $𝑡$ be the number of $𝑐_{𝑠}$ that are at most $𝑛$ , so that $𝑐_{1},$ $\dots,$ $𝑐_{𝑡} \leq$ $𝑛 <$ $𝑐_{𝑡 + 1},$ $\dots,$ $𝑐_{𝑟}$ . For $𝑠 \leq 𝑡$ , row $𝑠$ of $𝑆$ is nonzero, with the same leading entry as row $𝑠$ of $(𝑆 | 𝑇)$ . For $𝑠 > 𝑡$ , the leading entry of row $𝑠$ of $(𝑆 | 𝑇)$ is in the right block, so row $𝑠$ of $𝑆$ is zero; and rows $𝑟 + 1, \dots, 𝑚$ of $𝑆$ are zero as well. So the nonzero rows of $𝑆$ are rows $1, \dots, 𝑡$ , which is (R1), and (R2) and (R3) for $𝑆$ follow from (R2) and (R3) for $(𝑆 | 𝑇)$ . Finally, for $𝑠 \leq 𝑡$ , column $𝑐_{𝑠}$ of $(𝑆 | 𝑇)$ is $𝐞_{𝑠}$ by (R2) and (R4), and it is a column of $𝑆$ . This is (R4) for $𝑆$ . By Theorem 3.3.12, $𝑆$ is in RREF.

(b) Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix})$ and $𝐵 = (\begin{matrix} 1 \\ 2 \end{matrix})$ . The run on $𝐴$ is the single operation $𝐸_{1, - 1, 2}$ , so $𝐺 = (\begin{matrix} 1 & 0 \\ - 1 & 1 \end{matrix})$ and $𝐺 𝐵 = (\begin{matrix} 1 \\ 1 \end{matrix})$ . But $(𝐴 | 𝐵) = (\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix})$ reduces to $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ and then to $𝐼_{2}$ , whose last column is $(\begin{matrix} 0 \\ 1 \end{matrix}) \neq 𝐺 𝐵$ . The full algorithm also pivots in the column of $𝐵$ , and then clears above that pivot.

Exercise 3.3.45.standard Prove or disprove each statement. Throughout, $𝐴$ and $𝐵$ are matrices over $𝐹$ of sizes for which the expressions make sense.

(a) $rref (𝐴^{𝖳}) =$ ${rref (𝐴)}^{𝖳}$ for every square $𝐴$ .
(b) $rref (𝐴 𝐵) =$ $rref (𝐴) rref (𝐵)$ .
(c)If $rref (𝐴) = rref (𝐵)$ , then $im 𝑇_{𝐴} = im 𝑇_{𝐵}$ .
(d)If $𝐴$ and $𝐵$ have the same size and $im 𝑇_{𝐴} = im 𝑇_{𝐵}$ , then $rref (𝐴) = rref (𝐵)$ .
(e) $rref (rref (𝐴) 𝐵) =$ $rref (𝐴 𝐵)$ .

Solution.

Uses. Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ ), Theorem 3.3.12 (Matrices in RREF)

Hint 1. Only one of the statements is true. Look for

2 \times 2

counterexamples, or even

1 \times 2

ones, with many zeros.

Hint 2. For (e), write

rref (𝐴) = 𝐺 𝐴

with

𝐺

invertible.

Sketch. (a) False for

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

. (b) False for

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

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

. (c) False for

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

and

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

. (d) False for

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

and

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

. (e) True:

rref (𝐴) 𝐵 =

𝐺 (𝐴 𝐵)

, so Corollary 3.3.18(a) applies.

(a) False. Let $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ . It satisfies (R1)–(R4), so $rref (𝐴) = 𝐴$ and ${rref (𝐴)}^{𝖳} = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ , which violates (R1) and so is not even in RREF. In fact $rref (𝐴^{𝖳}) = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ .

(b) False. Let $𝐴 = (\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix})$ . Then $rref (𝐴) = 𝐴$ , $rref (𝐵) = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , and $rref (𝐴) rref (𝐵) =$ $0$ . But $𝐴 𝐵 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ , which is its own reduced row echelon form.

(c) False. Let $𝐴 = (\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) = 𝐸_{12} 𝐴$ . Then $rref (𝐴) =$ $rref (𝐵) =$ $𝐴$ , but $im 𝑇_{𝐴} = span (𝐞_{1})$ and $im 𝑇_{𝐵} = span (𝐞_{2})$ .

(d) False. Let $𝐴 = (\begin{matrix} 1 & 0 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 1 \end{matrix})$ in $𝐹^{1 \times 2}$ . Both images are all of $𝐹$ , but both matrices are in RREF and they are different.

(e) True. By Theorem 3.3.10, $rref (𝐴) = 𝐺 𝐴$ with $𝐺$ invertible, so $rref (𝐴) 𝐵 =$ $𝐺 (𝐴 𝐵)$ , and Corollary 3.3.18(a) gives $rref (𝐺 (𝐴 𝐵)) =$ $rref (𝐴 𝐵)$ .

Exercise 3.3.46.standard

(a)Find the error in the following argument, and give a counterexample to its conclusion.
Claim. If $𝑅 \in 𝐹^{𝑚 \times 𝑛}$ is in RREF and $𝐺 \in 𝐹^{𝑚 \times 𝑚}$ is invertible with $𝐺 𝑅 = 𝑅$ , then $𝐺 = 𝐼_{𝑚}$ .
Proof. Apply the first proof of Theorem 3.3.17 with $𝑅^{'} = 𝑅$ . Its induction shows that $𝐠_{𝑠} = 𝐞_{𝑠}$ for every $𝑠$ , so every column of $𝐺$ is the corresponding column of $𝐼_{𝑚}$ .
(b)Suppose $𝑅$ has $𝑟$ pivots. Describe all invertible $𝐺$ with $𝐺 𝑅 = 𝑅$ .

Solution.

Uses. Theorem 3.3.17 (Uniqueness of the reduced row echelon form), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.4.33 (Block matrix), Definition 2.5.12 (Invertible)

Hint 1. Reread the statement proved by induction in the first proof of Theorem 3.3.17. For which

𝑠

does it say anything about

𝐠_{𝑠}

Hint 2. Try

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

Hint 3. For (b), show that

𝐺 𝑅 = 𝑅

exactly when

𝐺 𝐞_{𝑠} = 𝐞_{𝑠}

for

𝑠 \leq 𝑟

, and write

𝐺

in block form.

Sketch. The induction gives

𝐠_{𝑠} = 𝐞_{𝑠}

only when

𝑝_{𝑠} \leq 𝑛

, that is, for

𝑠 \leq 𝑟

. Counterexample:

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

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

. In general

𝐺 𝑅 = 𝑅

if and only if

𝐺 = (\begin{matrix} 𝐼_{𝑟} & 𝑋 \\ 0 & 𝑌 \end{matrix})

, and such a

𝐺

is invertible exactly when

𝑌

is.

(a) The induction in the first proof of Theorem 3.3.17 shows $𝑝_{𝑠} = 𝑞_{𝑠}$ for all $𝑠$ , but $𝐠_{𝑠} = 𝐞_{𝑠}$ only when $𝑝_{𝑠} \leq 𝑛$ , that is, for $𝑠 \leq 𝑟$ . It says nothing about the columns $𝐠_{𝑟 + 1}, \dots, 𝐠_{𝑚}$ , so the claim does not follow. It is false: for $𝑅 = (\begin{matrix} 1 \\ 0 \end{matrix})$ and $𝐺 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ , $𝐺$ is invertible (with inverse $(\begin{matrix} 1 & - 1 \\ 0 & 1 \end{matrix})$ ) and $𝐺 𝑅 = 𝑅$ , but $𝐺 \neq 𝐼_{2}$ .

(b) Let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be the pivot columns of $𝑅$ . If $𝐺 𝑅 = 𝑅$ , then $𝐺 𝐞_{𝑠} =$ $𝐺 𝐫_{𝑝_{𝑠}} =$ $𝐫_{𝑝_{𝑠}} =$ $𝐞_{𝑠}$ for $𝑠 \leq 𝑟$ (Lemma 3.3.16(b)). Conversely, if $𝐺 𝐞_{𝑠} = 𝐞_{𝑠}$ for $𝑠 \leq 𝑟$ , then by Lemma 3.3.16(a) (with $𝑠 = 𝑟$ ) every column of $𝑅$ is a combination $\sum_{𝑡 \leq 𝑟} 𝑐_{𝑡} 𝐞_{𝑡}$ , and $𝐺$ fixes it; so $𝐺 𝑅 = 𝑅$ . Hence $𝐺 𝑅 = 𝑅$ if and only if the first $𝑟$ columns of $𝐺$ are $𝐞_{1}, \dots, 𝐞_{𝑟}$ , that is,

𝐺 = (\begin{matrix} 𝐼_{𝑟} & 𝑋 \\ 0 & 𝑌 \end{matrix})

for some $𝑋 \in 𝐹^{𝑟 \times (𝑚 - 𝑟)}$ and $𝑌 \in$ $𝐹^{(𝑚 - 𝑟) \times (𝑚 - 𝑟)}$ .

Such a $𝐺$ is invertible if and only if $𝑌$ is. If $𝑌$ is invertible, block multiplication (Definition 2.4.33) shows that $(\begin{matrix} 𝐼_{𝑟} & - 𝑋 𝑌^{- 1} \\ 0 & 𝑌^{- 1} \end{matrix})$ is a two-sided inverse of $𝐺$ . Conversely, let $𝐻 =$ $(\begin{matrix} 𝐻_{11} & 𝐻_{12} \\ 𝐻_{21} & 𝐻_{22} \end{matrix})$ be an inverse of $𝐺$ , in the same block sizes. The first block column of $𝐻 𝐺$ is $(\begin{matrix} 𝐻_{11} \\ 𝐻_{21} \end{matrix})$ , which must be $(\begin{matrix} 𝐼_{𝑟} \\ 0 \end{matrix})$ , so $𝐻_{21} = 0$ . Then the lower right blocks of $𝐻 𝐺 = 𝐼_{𝑚}$ and $𝐺 𝐻 = 𝐼_{𝑚}$ say $𝐻_{22} 𝑌 = 𝐼_{𝑚 - 𝑟}$ and $𝑌 𝐻_{22} = 𝐼_{𝑚 - 𝑟}$ . So $𝑌$ is invertible.

So the invertible $𝐺$ with $𝐺 𝑅 = 𝑅$ are exactly the matrices $(\begin{matrix} 𝐼_{𝑟} & 𝑋 \\ 0 & 𝑌 \end{matrix})$ with $𝑋$ arbitrary and $𝑌$ invertible. Only when $𝑟 = 𝑚$ is $𝐺 = 𝐼_{𝑚}$ forced.

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

Claim. Change step 1 of Algorithm 3.3.1 of Algorithm 3.3.1 so that it picks any column with a nonzero entry in an unpivoted row, not necessarily the leftmost one. The output of the modified algorithm is still in RREF.

Proof. The proofs of Lemma 3.3.7 and Proposition 3.3.8 go through word for word.

Solution.

Uses. Lemma 3.3.7 (The loop invariant), Proposition 3.3.8 (Properties of the output)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Find the place in the proof of Lemma 3.3.7 where the choice of the leftmost column was used.

Hint 2. Run the modified algorithm on

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

, choosing column

2

in the first pass.

Sketch. The proof used that rows

𝑘 + 1, \dots, 𝑚

vanish to the left of the chosen column, which is what the leftmost choice guarantees; parts (b), (d), (e) of the invariant depend on it. Choosing column

2

first in

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

gives the output

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

, which violates (R3).

The proof of Lemma 3.3.7 began with the observation that rows $𝑘 + 1, \dots, 𝑚$ vanish in the columns before the chosen column $𝑗$ . That is exactly what choosing the leftmost column guarantees, and parts (b), (d), and (e) were derived from it. With an arbitrary choice, none of them survives.

Counterexample: run the modified algorithm on $𝐴 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ , choosing column $2$ in pass $1$ . The $(1, 2)$ entry is already $1$ , so it becomes a pivot with $𝑝_{1} = 2$ , and clearing column $2$ adds $- 1$ times row $1$ to row $2$ , giving $(\begin{matrix} 1 & 1 \\ - 1 & 0 \end{matrix})$ . In pass $2$ , the only unpivoted row is $(- 1, 0)$ , so $𝑗 = 1$ ; scaling by $- 1$ gives $(1, 0)$ , and clearing adds $- 1$ times row $2$ to row $1$ . The output is

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

which violates (R3), so it is not in RREF. (Here $𝑝_{1} = 2 > 1 = 𝑝_{2}$ , so (b) of the invariant fails.)

What does survive is (a) and (c): the output is still row equivalent to $𝐴$ , and each pivot column is a standard basis vector, because a column $𝐞_{𝑠}$ has zeros in all unpivoted rows whichever column is chosen next. Only the staircase is lost.

Exercise 3.3.48.standard Let $𝑝$ be a prime.

(a)Show that exactly $2 𝑝^{2} + 2 𝑝 + 3$ matrices in $𝔽_{𝑝}^{2 \times 3}$ are in RREF.
(b)Deduce that $𝔽_{𝑝}^{2 \times 3}$ splits into exactly $2 𝑝^{2} + 2 𝑝 + 3$ row equivalence classes. How many is that for $𝑝 = 2$ ?

Solution.

Uses. Theorem 3.3.12 (Matrices in RREF), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Corollary 3.3.18 (RREF and row equivalence)

Hint 1. Sort the matrices in RREF by their set of pivot columns. Which entries are then forced, and which are free?

Hint 2. By Lemma 3.3.16(a), a non-pivot column has zeros below the rows of the pivots to its left, and is arbitrary in those rows.

Hint 3. For (b), how many matrices in RREF does a row equivalence class contain?

Sketch. No pivots:

1

matrix. One pivot in column

1

2

3

𝑝^{2}

𝑝

1

matrices. Two pivots in columns

(1, 2)

(1, 3)

(2, 3)

𝑝^{2}

𝑝

1

. Total

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

. By Corollary 3.3.18(b), each class contains exactly one matrix in RREF; for

𝑝 = 2

there are

15

classes.

(a) By Theorem 3.3.12 we count the matrices satisfying (R1)–(R4), sorted by their pivot columns. The pivot columns are $𝐞_{1}, 𝐞_{2}, \dots$ in order, and by Lemma 3.3.16(a) a non-pivot column has zeros in every row below the rows of the pivots to its left, while its entries in those rows are arbitrary.

No pivots: only the zero matrix. That is $1$ matrix.
One pivot, in column $1$ : $(\begin{matrix} 1 & 𝑎 & 𝑏 \\ 0 & 0 & 0 \end{matrix})$ , so $𝑝^{2}$ matrices. In column $2$ : $(\begin{matrix} 0 & 1 & 𝑎 \\ 0 & 0 & 0 \end{matrix})$ , so $𝑝$ . In column $3$ : $(\begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix})$ , so $1$ .
Two pivots, in columns $1, 2$ : $(\begin{matrix} 1 & 0 & 𝑎 \\ 0 & 1 & 𝑏 \end{matrix})$ , so $𝑝^{2}$ . In columns $1, 3$ : $(\begin{matrix} 1 & 𝑎 & 0 \\ 0 & 0 & 1 \end{matrix})$ , so $𝑝$ . In columns $2, 3$ : $(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$ , so $1$ .

Each displayed matrix satisfies (R1)–(R4) for every choice of $𝑎, 𝑏$ . The total is $1 +$ $2 (𝑝^{2} + 𝑝 + 1) =$ $2 𝑝^{2} +$ $2 𝑝 +$ $3$ .

(b) Every class contains a matrix in RREF, namely $rref (𝐴)$ for any $𝐴$ in it, and by Corollary 3.3.18(b) two matrices in RREF are row equivalent only if they are equal (as $rref (𝑅) = 𝑅$ ). So $𝑅 \mapsto$ (the class of $𝑅$ ) is a bijection from the matrices in RREF to the classes, and there are $2 𝑝^{2} + 2 𝑝 + 3$ classes. For $𝑝 = 2$ this is $15$ .

Exercise 3.3.49.standard Find all matrices

𝐴 \in ℝ^{2 \times 3}

with

ker 𝑇_{𝐴} =

span ((1, 1, 1))

Solution.

Uses. Corollary 3.3.20 (The kernel is a complete invariant), Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.10 ( $𝐺 𝐴 = rref (𝐴)$ )

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. Find one matrix in RREF with this kernel.

Hint 2.

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

works. By Corollary 3.3.20,

𝐴

has the same kernel as

𝑅_{0}

exactly when

rref (𝐴) = 𝑅_{0}

. Which matrices have this reduced row echelon form?

Sketch. The matrix

𝑅_{0}

is in RREF and has kernel

span ((1, 1, 1))

. By Corollary 3.3.20,

ker 𝑇_{𝐴} = ker 𝑇_{𝑅_{0}}

if and only if

rref (𝐴) = 𝑅_{0}

, if and only if

𝐴 = 𝐻 𝑅_{0}

with

𝐻

invertible. So

𝐴 =

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

with

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

invertible.

Let $𝑅_{0} = (\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & - 1 \end{matrix})$ , which is in RREF. Its kernel consists of the $𝐱$ with $𝑥_{1} - 𝑥_{3} = 0$ and $𝑥_{2} - 𝑥_{3} = 0$ , that is, $𝐱 = 𝑥_{3} (1, 1, 1)$ ; so $ker 𝑇_{𝑅_{0}} =$ $span ((1, 1, 1))$ . By Corollary 3.3.20, $ker 𝑇_{𝐴} =$ $span ((1, 1, 1))$ if and only if $rref (𝐴) =$ $rref (𝑅_{0}) =$ $𝑅_{0}$ .

If $rref (𝐴) = 𝑅_{0}$ , then by Theorem 3.3.10, $𝐺 𝐴 = 𝑅_{0}$ with $𝐺$ invertible, so $𝐴 = 𝐺^{- 1} 𝑅_{0}$ . Conversely, if $𝐴 = 𝐻 𝑅_{0}$ with $𝐻$ invertible, then $rref (𝐴) =$ $rref (𝑅_{0}) =$ $𝑅_{0}$ by Corollary 3.3.18(a). So the answer is the set of matrices

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

with $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})$ invertible.

Exercise 3.3.50.standard For $𝐮, 𝐱 \in 𝐹^{𝑛}$ write $𝐮 \cdot$ $𝐱 =$ $𝑢_{1} 𝑥_{1} +$ $\dots +$ $𝑢_{𝑛} 𝑥_{𝑛}$ . The row space of $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ is the span of its rows, viewed as vectors in $𝐹^{𝑛}$ .

(a)Show that $𝐱 \in ker 𝑇_{𝐴}$ if and only if $𝐯 \cdot 𝐱 = 0$ for every $𝐯$ in the row space of $𝐴$ .
(b)Deduce that $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ are row equivalent if and only if they have the same row space.

Solution.

Uses. Definition 2.3.8 (Matrix–vector product), Corollary 3.3.20 (The kernel is a complete invariant), Exercise 3.2.46, Definition 1.3.10 (Span)

Techniques. Reduce to RREF (Technique 3.3.22)

Hint 1. The

𝑖

th entry of

𝐴 𝐱

is (row

𝑖

𝐴

)

\cdot 𝐱

. How does

𝐯 \cdot 𝐱

behave when

𝐯

is a linear combination?

Hint 2. For (b), one direction is Exercise 3.2.46. For the other, use (a) and Corollary 3.3.20.

Sketch. (a)

𝐴 𝐱 = 𝟎

says that every row is orthogonal to

𝐱

in this sense, and

𝐯 \mapsto 𝐯 \cdot 𝐱

respects linear combinations. (b) Row equivalent matrices have the same row space by Exercise 3.2.46. If the row spaces agree, (a) shows that the kernels agree, and Corollary 3.3.20 gives

𝐴 \sim 𝐵

(a) Let $𝐯_{1}, \dots, 𝐯_{𝑚}$ be the rows of $𝐴$ . By Definition 2.3.8, the $𝑖$ th entry of $𝐴 𝐱$ is $𝑎_{𝑖 1} 𝑥_{1} +$ $\dots +$ $𝑎_{𝑖 𝑛} 𝑥_{𝑛} =$ $𝐯_{𝑖} \cdot$ $𝐱$ , so $𝐴 𝐱 = 𝟎$ if and only if $𝐯_{𝑖} \cdot 𝐱 = 0$ for all $𝑖$ . By distributivity, $(𝑐 𝐮 + 𝑐^{'} 𝐮^{'}) \cdot$ $𝐱 =$ $𝑐 (𝐮 \cdot 𝐱) +$ $𝑐^{'} (𝐮^{'} \cdot 𝐱)$ , so if $𝐯 =$ $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑚} 𝐯_{𝑚}$ and every $𝐯_{𝑖} \cdot 𝐱 = 0$ , then $𝐯 \cdot 𝐱 = 0$ . Conversely, each $𝐯_{𝑖}$ lies in the row space. This proves (a).

(b) If $𝐴 \sim 𝐵$ , they have the same row space by Exercise 3.2.46. Conversely, suppose $𝐴$ and $𝐵$ have the same row space. By (a), $ker 𝑇_{𝐴}$ and $ker 𝑇_{𝐵}$ are both the set of $𝐱$ with $𝐯 \cdot 𝐱 = 0$ for all $𝐯$ in this common row space. So $ker 𝑇_{𝐴} = ker 𝑇_{𝐵}$ , and $𝐴 \sim 𝐵$ by Corollary 3.3.20.

Exercise 3.3.51.standard Let $𝑎 \in 𝐹$ , and let $𝐵 \in 𝐹^{𝑛 \times 𝑛}$ have $1$ in every diagonal position, $𝑎$ in every position $(𝑖, 𝑖 + 1)$ directly above the diagonal, and $0$ elsewhere.

(a)Row reduce $(𝐵 | 𝐼_{𝑛})$ to show that $𝐵$ is invertible, and that $𝐵^{- 1}$ has entry ${(- 𝑎)}^{𝑗 - 𝑖}$ in position $(𝑖, 𝑗)$ for $𝑗 \geq 𝑖$ , and $0$ for $𝑗 < 𝑖$ .
(b)Find the inverse of the $𝑛 \times 𝑛$ matrix $𝑈$ with $𝑢_{𝑖 𝑗} = 1$ for $𝑗 \geq 𝑖$ and $𝑢_{𝑖 𝑗} = 0$ for $𝑗 < 𝑖$ .

Solution.

Uses. Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.23 (Invertibility and RREF), Proposition 3.3.11 (Carrying extra columns along)

Hint 1. Work from the bottom up: for

𝑖 = 𝑛 - 1, 𝑛 - 2, \dots, 1

, add

- 𝑎

times row

𝑖 + 1

to row

𝑖

. Any sequence of row operations that reaches

(𝐼_{𝑛} | 𝐶)

will do, by Corollary 3.3.18(c).

Hint 2. Prove by downward induction on

𝑖

what row

𝑖

looks like after it has been processed.

Hint 3. For (b),

𝑈

is the answer to (a) for

𝑎 = - 1

Sketch. Processing rows from the bottom up, row

𝑖

becomes

(𝐞_{𝑖}^{𝖳} | 𝐜_{𝑖})

with

𝐜_{𝑖} =

\sum_{𝑗 \geq 𝑖} {(- 𝑎)}^{𝑗 - 𝑖} 𝐞_{𝑗}^{𝖳}

, because

𝐞_{𝑖}^{𝖳} -

𝑎 𝐜_{𝑖 + 1} =

𝐜_{𝑖}

. So

𝐻 (𝐵 | 𝐼_{𝑛}) =

(𝐼_{𝑛} | 𝐶)

for a product

𝐻

of elementary matrices, and

𝐵^{- 1} = 𝐶

. For

𝑎 = - 1

, (a) says that the matrix with

1

on the diagonal and

- 1

just above it has inverse

𝑈

; so

𝑈^{- 1}

is that matrix.

(a) For $𝑖 = 1, \dots, 𝑛$ , let

𝐜_{𝑖} = \sum_{𝑗 = 𝑖}^{𝑛} {(- 𝑎)}^{𝑗 - 𝑖} 𝐞_{𝑗}^{𝖳},

the row vector we expect as row $𝑖$ of $𝐵^{- 1}$ . For $𝑖 < 𝑛$ , row $𝑖$ of $(𝐵 | 𝐼_{𝑛})$ has left part $𝐞_{𝑖}^{𝖳} + 𝑎 𝐞_{𝑖 + 1}^{𝖳}$ and right part $𝐞_{𝑖}^{𝖳}$ . Row $𝑛$ has left part $𝐞_{𝑛}^{𝖳}$ and right part $𝐞_{𝑛}^{𝖳} = 𝐜_{𝑛}$ .

For $𝑖 = 𝑛 - 1, 𝑛 - 2, \dots, 1$ in this order, add $- 𝑎$ times row $𝑖 + 1$ to row $𝑖$ . We claim that afterwards row $𝑖$ is $(𝐞_{𝑖}^{𝖳} | 𝐜_{𝑖})$ . When row $𝑖$ is processed it has not been changed yet, and row $𝑖 + 1$ is already $(𝐞_{𝑖 + 1}^{𝖳} | 𝐜_{𝑖 + 1})$ (for $𝑖 + 1 = 𝑛$ this was noted above, and otherwise by induction). So row $𝑖$ becomes

(𝐞_{𝑖}^{𝖳} + 𝑎 𝐞_{𝑖 + 1}^{𝖳} - 𝑎 𝐞_{𝑖 + 1}^{𝖳} | 𝐞_{𝑖}^{𝖳} - 𝑎 𝐜_{𝑖 + 1}) = (𝐞_{𝑖}^{𝖳} | 𝐜_{𝑖}),

since

𝐞_{𝑖}^{𝖳} - 𝑎 \sum_{𝑗 \geq 𝑖 + 1} {(- 𝑎)}^{𝑗 - 𝑖 - 1} 𝐞_{𝑗}^{𝖳} = 𝐞_{𝑖}^{𝖳} + \sum_{𝑗 \geq 𝑖 + 1} {(- 𝑎)}^{𝑗 - 𝑖} 𝐞_{𝑗}^{𝖳} = 𝐜_{𝑖} .

At the end the matrix is $(𝐼_{𝑛} | 𝐶)$ , where $𝐶$ has rows $𝐜_{1}, \dots, 𝐜_{𝑛}$ . Let $𝐻$ be the product of the elementary matrices used, so $𝐻 (𝐵 | 𝐼_{𝑛}) =$ $(𝐻 𝐵 | 𝐻) =$ $(𝐼_{𝑛} | 𝐶)$ . Since $𝐼_{𝑛}$ is in RREF and $𝐵 \sim 𝐼_{𝑛}$ , Corollary 3.3.18(c) gives $rref (𝐵) = 𝐼_{𝑛}$ , and $𝐻$ is a product of elementary matrices with $𝐻 𝐵 = rref (𝐵)$ . By Theorem 3.3.23, $𝐵$ is invertible and $𝐵^{- 1} = 𝐻 = 𝐶$ , whose $(𝑖, 𝑗)$ entry is ${(- 𝑎)}^{𝑗 - 𝑖}$ for $𝑗 \geq 𝑖$ and $0$ otherwise.

(b) Take $𝑎 = - 1$ in (a): the matrix $𝐵$ with $1$ on the diagonal and $- 1$ directly above it has inverse with entries $1^{𝑗 - 𝑖} = 1$ for $𝑗 \geq 𝑖$ and $0$ below the diagonal, which is $𝑈$ . So $𝑈 = 𝐵^{- 1}$ is invertible and $𝑈^{- 1} = 𝐵$ : it has $1$ on the diagonal, $- 1$ in each position $(𝑖, 𝑖 + 1)$ , and $0$ elsewhere.

Exercise 3.3.52.standard Let

𝑛 \geq 1

, and let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

have every diagonal entry

0

and every other entry

1

. Write

𝑐 = (𝑛 - 1) * 1 = 1 + \dots + 1

(

𝑛 - 1

terms) in

𝐹

. Show that

𝐴

is invertible if and only if

𝑐 \neq 0

, and find

𝐴^{- 1}

in that case. For which

𝑛

𝐴

invertible over

𝔽_{𝑝}

Solution.

Uses. Definition 2.5.12 (Invertible), Definition 2.4.1 (Matrix product)

Hint 1. Row reduce for

𝑛 = 2

and

𝑛 = 3

over

ℚ

and look for a pattern.

Hint 2. Let

𝐽

be the all-ones matrix, so

𝐴 = 𝐽 - 𝐼_{𝑛}

. Compute

𝐽^{2}

, and look for an inverse of the form

𝛼 𝐽 + 𝛽 𝐼_{𝑛}

Hint 3. If

𝑐 = 0

, compute

𝐴 𝐽

Sketch. With

𝐽

the all-ones matrix,

𝐴 = 𝐽 - 𝐼_{𝑛}

and

𝐽^{2} = (𝑛 * 1) 𝐽

. If

𝑐 \neq 0

, then

𝑐^{- 1} 𝐽 - 𝐼_{𝑛}

is a two-sided inverse of

𝐽 - 𝐼_{𝑛}

, by direct multiplication. If

𝑐 = 0

, then

𝐴 𝐽 = 𝑐 𝐽 = 0

with

𝐽 \neq 0

, so

𝐴

is not invertible. Over

𝔽_{𝑝}

: invertible exactly when

𝑝

does not divide

𝑛 - 1

Let $𝐽 \in 𝐹^{𝑛 \times 𝑛}$ be the matrix all of whose entries are $1$ , so $𝐴 = 𝐽 - 𝐼_{𝑛}$ . Each entry of $𝐽^{2}$ is a sum of $𝑛$ products $1 \cdot 1$ , so $𝐽^{2} =$ $(𝑛 * 1) 𝐽 =$ $(𝑐 + 1) 𝐽$ .

Suppose $𝑐 \neq 0$ , and let $𝐶 = 𝑐^{- 1} 𝐽 - 𝐼_{𝑛}$ . Then

𝐴 𝐶 = (𝐽 - 𝐼_{𝑛}) (𝑐^{- 1} 𝐽 - 𝐼_{𝑛}) = 𝑐^{- 1} 𝐽^{2} - 𝐽 - 𝑐^{- 1} 𝐽 + 𝐼_{𝑛} = 𝑐^{- 1} (𝑐 + 1) 𝐽 - 𝐽 - 𝑐^{- 1} 𝐽 + 𝐼_{𝑛} = 𝐼_{𝑛},

and the same computation, with the factors in the other order, gives $𝐶 𝐴 = 𝐼_{𝑛}$ (all the matrices involved are combinations of $𝐽$ and $𝐼_{𝑛}$ , which commute). So $𝐴$ is invertible and $𝐴^{- 1} = 𝑐^{- 1} 𝐽 - 𝐼_{𝑛}$ : its diagonal entries are $𝑐^{- 1} - 1$ and its other entries are $𝑐^{- 1}$ . For instance, for $𝑛 = 3$ over $ℚ$ ,

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

Suppose $𝑐 = 0$ . Then $𝐴 𝐽 =$ $𝐽^{2} -$ $𝐽 =$ $(𝑐 + 1) 𝐽 -$ $𝐽 =$ $𝑐 𝐽 =$ $0$ . If $𝐴$ were invertible, we would get $𝐽 = 𝐴^{- 1} 𝐴 𝐽 = 0$ , which is false. So $𝐴$ is not invertible. (This includes $𝑛 = 1$ , where $𝐴 = (0)$ .)

Over $𝔽_{𝑝}$ , $𝑐 = 0$ exactly when $𝑝$ divides $𝑛 - 1$ . So $𝐴$ is invertible over $𝔽_{𝑝}$ if and only if $𝑛 - 1$ is not a multiple of $𝑝$ ; for example, over $𝔽_{2}$ , if and only if $𝑛$ is even.

Exercise 3.3.53.standard A matrix $𝑈 \in 𝐹^{𝑛 \times 𝑛}$ is upper triangular if $𝑢_{𝑖 𝑗} = 0$ whenever $𝑖 > 𝑗$ .

(a)Let $𝑈$ be upper triangular with every diagonal entry nonzero. Show that Gauss–Jordan elimination on $𝑈$ performs no swaps, and that every elementary matrix it uses is upper triangular. Deduce that $𝑈$ is invertible, and that $𝑈^{- 1}$ is upper triangular with diagonal entries $𝑢_{11}^{- 1}, \dots, 𝑢_{𝑛 𝑛}^{- 1}$ .
(b)Let $𝑈$ be upper triangular with some diagonal entry $0$ . Find a nonzero $𝐱$ with $𝑈 𝐱 = 𝟎$ , and conclude that $𝑈$ is not invertible.

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Theorem 3.3.23 (Invertibility and RREF), Definition 2.4.1 (Matrix product)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. For (a), show by induction on

𝑘

that before pass

𝑘

the current matrix is upper triangular, its first

𝑘 - 1

columns are

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

, and rows

𝑘, \dots, 𝑛

are still the rows of

𝑈

Hint 2. In pass

𝑘

the pivot is the

(𝑘, 𝑘)

entry, and only rows above row

𝑘

need clearing. Where is the off-diagonal entry of

𝐸_{𝑘 𝑐 𝑖}

when

𝑖 < 𝑘

? Products of upper triangular matrices are upper triangular: check it entrywise.

Hint 3. For (b), take the first

𝑘

with

𝑢_{𝑘 𝑘} = 0

, put

𝑥_{𝑘} = 1

and

𝑥_{𝑗} = 0

for

𝑗 > 𝑘

, and solve for

𝑥_{𝑘 - 1}, \dots, 𝑥_{1}

from the bottom up.

Sketch. (a) In pass

𝑘

, rows

𝑘, \dots, 𝑛

vanish in columns

1, \dots, 𝑘 - 1

and the

(𝑘, 𝑘)

entry is

𝑢_{𝑘 𝑘} \neq 0

, so the pivot is

(𝑘, 𝑘)

with no swap; the scaling is diagonal, and the replacements add multiples of row

𝑘

to rows

𝑖 < 𝑘

, with elementary matrices

𝐸_{𝑘 𝑐 𝑖}

whose extra entry

(𝑖, 𝑘)

is above the diagonal. So

𝑈^{- 1} = 𝐺

is a product of upper triangular matrices, and its diagonal is the product of their diagonals. (b) With

𝑘

minimal and

𝑢_{𝑘 𝑘} = 0

, back substitution gives

𝐱 \neq 𝟎

with

𝑥_{𝑘} = 1

and

𝑈 𝐱 = 𝟎

(a) We show by induction on $𝑘 = 1, \dots, 𝑛$ that before pass $𝑘$ , the current matrix $𝑀$ is upper triangular, its first $𝑘 - 1$ columns are $𝐞_{1}, \dots, 𝐞_{𝑘 - 1}$ , and its rows $𝑘, \dots, 𝑛$ are those of $𝑈$ . For $𝑘 = 1$ , $𝑀 = 𝑈$ .

Assume this before pass $𝑘$ . Rows $𝑘, \dots, 𝑛$ of $𝑀$ vanish in columns $1, \dots, 𝑘 - 1$ (as $𝑀$ is upper triangular), and the $(𝑘, 𝑘)$ entry is $𝑢_{𝑘 𝑘} \neq 0$ . So step 1 of Algorithm 3.3.1 picks column $𝑘$ , and there is no swap. step 3 of Algorithm 3.3.1 multiplies by the diagonal matrix $𝐸_{𝑘, 𝑢_{𝑘 𝑘}^{- 1}}$ . In column $𝑘$ , the rows $𝑖 > 𝑘$ have entry $𝑢_{𝑖 𝑘} = 0$ , so step 4 of Algorithm 3.3.1 only changes rows $𝑖 < 𝑘$ , using the matrices $𝐸_{𝑘 𝑐 𝑖}$ with $𝑖 < 𝑘$ ; the single off-diagonal entry of such a matrix is in position $(𝑖, 𝑘)$ , above the diagonal. Adding a multiple of row $𝑘$ , which vanishes in columns $1, \dots, 𝑘 - 1$ , to a row $𝑖 < 𝑘$ changes it only in columns $𝑘, \dots, 𝑛$ , all to the right of the diagonal entry $(𝑖, 𝑖)$ . So after the pass, $𝑀$ is still upper triangular, column $𝑘$ is $𝐞_{𝑘}$ , columns $1, \dots, 𝑘 - 1$ are unchanged, and rows $𝑘 + 1, \dots, 𝑛$ are untouched. This completes the induction.

After pass $𝑛$ the matrix is $𝐼_{𝑛}$ , so $rref (𝑈) = 𝐼_{𝑛}$ , and by Theorem 3.3.23 $𝑈$ is invertible with $𝑈^{- 1} = 𝐺$ , the product of the elementary matrices used. Each of them is upper triangular. If $𝑉$ and $𝑊$ are upper triangular, then ${(𝑉 𝑊)}_{𝑖 𝑗} =$ $\sum_{𝑙} 𝑣_{𝑖 𝑙} 𝑤_{𝑙 𝑗}$ and a term can be nonzero only if $𝑖 \leq 𝑙 \leq 𝑗$ ; so ${(𝑉 𝑊)}_{𝑖 𝑗} = 0$ for $𝑖 > 𝑗$ , and ${(𝑉 𝑊)}_{𝑖 𝑖} =$ $𝑣_{𝑖 𝑖} 𝑤_{𝑖 𝑖}$ . Hence $𝐺$ is upper triangular, and its diagonal is the entrywise product of the diagonals of its factors. The scaling in pass $𝑘$ has diagonal entry $𝑢_{𝑘 𝑘}^{- 1}$ in position $𝑘$ and $1$ elsewhere, and the replacements have only $1$ s on the diagonal, so $𝐺_{𝑘 𝑘} = 𝑢_{𝑘 𝑘}^{- 1}$ .

(b) Let $𝑘$ be the smallest index with $𝑢_{𝑘 𝑘} = 0$ , so $𝑢_{𝑖 𝑖} \neq 0$ for $𝑖 < 𝑘$ . Put $𝑥_{𝑗} = 0$ for $𝑗 > 𝑘$ and $𝑥_{𝑘} = 1$ , and for $𝑖 = 𝑘 - 1, 𝑘 - 2, \dots, 1$ in turn, put

𝑥_{𝑖} = - 𝑢_{𝑖 𝑖}^{- 1} \sum_{𝑗 = 𝑖 + 1}^{𝑘} 𝑢_{𝑖 𝑗} 𝑥_{𝑗} .

Since $𝑈$ is upper triangular, entry $𝑖$ of $𝑈 𝐱$ is $\sum_{𝑗 \geq 𝑖} 𝑢_{𝑖 𝑗} 𝑥_{𝑗}$ . For $𝑖 > 𝑘$ this involves only $𝑥_{𝑗}$ with $𝑗 > 𝑘$ , which are $0$ . For $𝑖 = 𝑘$ it is $𝑢_{𝑘 𝑘} \cdot 1 = 0$ . For $𝑖 < 𝑘$ it is $𝑢_{𝑖 𝑖} 𝑥_{𝑖} +$ $\sum_{𝑗 = 𝑖 + 1}^{𝑘} 𝑢_{𝑖 𝑗} 𝑥_{𝑗} =$ $0$ by the choice of $𝑥_{𝑖}$ . So $𝑈 𝐱 = 𝟎$ with $𝐱 \neq 𝟎$ . If $𝑈$ were invertible, then $𝐱 = 𝑈^{- 1} 𝑈 𝐱 = 𝟎$ . So $𝑈$ is not invertible.

Together, (a) and (b) show that an upper triangular matrix is invertible if and only if all its diagonal entries are nonzero.

Exercise 3.3.54.standard Let $𝐹$ be a subfield of a field $𝐾$ (for example $ℚ \subseteq ℝ$ or $ℝ \subseteq ℂ$ ), and let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ , so that $𝐴$ is also a matrix over $𝐾$ .

(a)Show that $rref (𝐴)$ is the same whether it is computed over $𝐹$ or over $𝐾$ .
(b)Deduce that if $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ is invertible as a matrix over $𝐾$ , then $𝐴^{- 1}$ has all its entries in $𝐹$ .
(c)Show that $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ are row equivalent over $𝐾$ (using elementary matrices with entries in $𝐾$ ) if and only if they are row equivalent over $𝐹$ .

Solution.

Uses. Definition 1.1.32 (Subfield), Algorithm 3.3.1 (Gauss–Jordan elimination), Theorem 3.3.23 (Invertibility and RREF), Corollary 3.3.18 (RREF and row equivalence)

Hint 1. Compare the two runs step by step. Which field operations does the algorithm use, and do they give the same results in

𝐹

and in

𝐾

Hint 2. For (b), run Algorithm 3.3.24 over

𝐹

Hint 3. For (c), one direction is free. For the other, use (a) and Corollary 3.3.18(b) twice.

Sketch. The algorithm only tests entries for being

0

, inverts nonzero entries, and adds and multiplies; a subfield is closed under these operations and computes them as

𝐾

does. So by induction the runs over

𝐹

and

𝐾

perform the same operations. (b) Over

𝐾

rref (𝐴) = 𝐼_{𝑛}

; so the run over

𝐹

gives

(𝐼_{𝑛} | 𝐺)

with

𝐺

over

𝐹

, and

𝐺 = 𝐴^{- 1}

. (c)

{rref}_{𝐹} (𝐴) =

{rref}_{𝐾} (𝐴) =

{rref}_{𝐾} (𝐵) =

{rref}_{𝐹} (𝐵)

(a) By Definition 1.1.32, the sum and product of elements of $𝐹$ , computed in $𝐾$ , are their sum and product in $𝐹$ , and the inverse in $𝐾$ of a nonzero element of $𝐹$ lies in $𝐹$ and is its inverse there (inverses are unique). We show by induction on the number of operations performed that the runs of Algorithm 3.3.1 on $𝐴$ over $𝐹$ and over $𝐾$ perform the same operations, with the same current matrices, all of whose entries lie in $𝐹$ . At the start both current matrices are $𝐴$ . If the current matrices agree and have entries in $𝐹$ , then every decision of the next step (which column, whether an entry is $0$ , which row to swap) is the same, the scalars used (inverses and negatives of entries) are the same elements of $𝐹$ , and the operation produces the same matrix, with entries in $𝐹$ . So the outputs agree.

(b) Over $𝐾$ , $𝐴$ is invertible, so $rref (𝐴) = 𝐼_{𝑛}$ by Theorem 3.3.23, and by (a) this also holds over $𝐹$ . Running Algorithm 3.3.24 over $𝐹$ produces $(𝐼_{𝑛} | 𝐺)$ with $𝐺 \in 𝐹^{𝑛 \times 𝑛}$ and $𝐺 𝐴 = 𝐼_{𝑛}$ , and by Theorem 3.3.23 $𝐺$ is the inverse of $𝐴$ , over $𝐹$ and hence over $𝐾$ (where inverses are unique).

(c) An elementary matrix over $𝐹$ is an elementary matrix over $𝐾$ , so row equivalence over $𝐹$ implies row equivalence over $𝐾$ . Conversely, if $𝐴$ and $𝐵$ are row equivalent over $𝐾$ , then by Corollary 3.3.18(b) over $𝐾$ and by (a),

{rref}_{𝐹} (𝐴) = {rref}_{𝐾} (𝐴) = {rref}_{𝐾} (𝐵) = {rref}_{𝐹} (𝐵),

where the subscript records the field used. By Corollary 3.3.18(b) over $𝐹$ , $𝐴$ and $𝐵$ are row equivalent over $𝐹$ .

Exercise 3.3.55.standard

(a)Describe a procedure that, given $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ , decides whether $𝐴 \sim 𝐵$ and, if so, finds an invertible $𝐺$ with $𝐺 𝐴 = 𝐵$ .
(b)Carry it out for $𝐴 = (\begin{matrix} 1 & 2 & 1 \\ 2 & 4 & 3 \end{matrix})$ and $𝐵 = (\begin{matrix} 0 & 0 & 1 \\ 1 & 2 & 2 \end{matrix})$ over $ℚ$ .

Solution.

Uses. Proposition 3.3.11 (Carrying extra columns along), Corollary 3.3.18 (RREF and row equivalence), Theorem 3.3.23 (Invertibility and RREF)

Hint 1. Compute

rref (𝐴) = 𝐺_{𝐴} 𝐴

and

rref (𝐵) = 𝐺_{𝐵} 𝐵

. When can

𝐴 \sim 𝐵

hold, and how would you get from

𝐴

𝐵

Hint 2. If

𝐺_{𝐴} 𝐴 = 𝐺_{𝐵} 𝐵

, then

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

. To compute

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

, you can row reduce

(𝐺_{𝐵} | 𝐺_{𝐴})

Sketch. Row reduce

(𝐴 | 𝐼_{𝑚})

and

(𝐵 | 𝐼_{𝑚})

(𝑅_{𝐴} | 𝐺_{𝐴})

and

(𝑅_{𝐵} | 𝐺_{𝐵})

. If

𝑅_{𝐴} \neq 𝑅_{𝐵}

, then

𝐴

and

𝐵

are not row equivalent. If

𝑅_{𝐴} = 𝑅_{𝐵}

, then

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

works. In (b),

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

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

, and

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

(a) Row reduce $(𝐴 | 𝐼_{𝑚})$ and $(𝐵 | 𝐼_{𝑚})$ , scanning only the first $𝑛$ columns. By Proposition 3.3.11 this gives $(𝑅_{𝐴} | 𝐺_{𝐴})$ and $(𝑅_{𝐵} | 𝐺_{𝐵})$ with $𝑅_{𝐴} =$ $rref (𝐴) =$ $𝐺_{𝐴} 𝐴$ and $𝑅_{𝐵} =$ $rref (𝐵) =$ $𝐺_{𝐵} 𝐵$ , where $𝐺_{𝐴}, 𝐺_{𝐵}$ are invertible. If $𝑅_{𝐴} \neq 𝑅_{𝐵}$ , then $𝐴$ and $𝐵$ are not row equivalent, by Corollary 3.3.18(b). If $𝑅_{𝐴} = 𝑅_{𝐵}$ , then $𝐺_{𝐴} 𝐴 = 𝐺_{𝐵} 𝐵$ , so $𝐵 = 𝐺 𝐴$ with $𝐺 = 𝐺_{𝐵}^{- 1} 𝐺_{𝐴}$ , which is invertible. To compute it, row reduce $(𝐺_{𝐵} | 𝐺_{𝐴})$ , scanning only the first $𝑚$ columns: since $𝐺_{𝐵}$ is invertible, $rref (𝐺_{𝐵}) = 𝐼_{𝑚}$ , and the run’s product is $𝐺_{𝐵}^{- 1}$ (Theorem 3.3.23), so the result is $(𝐼_{𝑚} | 𝐺_{𝐵}^{- 1} 𝐺_{𝐴})$ by Proposition 3.3.11.

(b) For $𝐴$ : adding $- 2$ times row $1$ to row $2$ gives $(\begin{matrix} 1 & 2 & 1 \\ 0 & 0 & 1 \end{matrix})$ , and adding $- 1$ times row $2$ to row $1$ gives $𝑅_{𝐴} = (\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{matrix})$ . The same operations on $𝐼_{2}$ give $𝐺_{𝐴} = (\begin{matrix} 3 & - 1 \\ - 2 & 1 \end{matrix})$ . For $𝐵$ : swapping the rows gives $(\begin{matrix} 1 & 2 & 2 \\ 0 & 0 & 1 \end{matrix})$ , and adding $- 2$ times row $2$ to row $1$ gives $𝑅_{𝐵} =$ $(\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{matrix}) =$ $𝑅_{𝐴}$ . The same operations on $𝐼_{2}$ give $𝐺_{𝐵} = (\begin{matrix} - 2 & 1 \\ 1 & 0 \end{matrix})$ . So $𝐴 \sim 𝐵$ . Since $𝐺_{𝐵} = 𝐸_{2, - 2, 1} 𝐸_{12}$ , its inverse is $𝐸_{12} 𝐸_{2, 2, 1} =$ $(\begin{matrix} 0 & 1 \\ 1 & 2 \end{matrix})$ (Corollary 3.2.11), and

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

Check:

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

Exercise 3.3.56.hard Let $𝔽$ be $ℝ$ or $ℂ$ . A matrix $𝐴 \in 𝔽^{𝑛 \times 𝑛}$ is strictly diagonally dominant if in every row the diagonal entry outweighs the rest:

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

Show that Gauss–Jordan elimination on such an $𝐴$ never needs a swap, and conclude that $𝐴$ is invertible.

Solution.

Uses. Algorithm 3.3.1 (Gauss–Jordan elimination), Theorem 3.3.23 (Invertibility and RREF), Definition B.1.7 (Modulus)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. Pass

1

is fine, since

𝑎_{11} \neq 0

. Find an invariant that makes every later pass equally fine.

Hint 2. After pass

1

, the entries in rows and columns

2, \dots, 𝑛

are

𝑎_{𝑖 𝑗} -

𝑎_{𝑖 1} 𝑎_{1 𝑗} / 𝑎_{11}

. Show that this

(𝑛 - 1) \times (𝑛 - 1)

block is again strictly diagonally dominant.

Hint 3. Bound

\sum_{𝑗 \geq 2, 𝑗 \neq 𝑖} | 𝑎_{1 𝑗} |

using row

1

, and

\sum_{𝑗 \geq 2, 𝑗 \neq 𝑖} | 𝑎_{𝑖 𝑗} |

using row

𝑖

, and finish with

| 𝑥 | - | 𝑦 | \leq | 𝑥 - 𝑦 |

Sketch. Invariant before pass

𝑘

: columns

1, \dots, 𝑘 - 1

are

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

, rows

𝑘, \dots, 𝑛

vanish in those columns, and the block of rows and columns

𝑘, \dots, 𝑛

is strictly diagonally dominant. Then the

(𝑘, 𝑘)

entry is a nonzero pivot, and the new block entries are

𝑚_{𝑖 𝑗} -

𝑚_{𝑖 𝑘} 𝑚_{𝑘 𝑗} / 𝑚_{𝑘 𝑘}

. Bounding the off-diagonal entries of row

𝑖

of the new block with the dominance of rows

𝑘

and

𝑖

and the triangle inequality shows that the new block is again strictly diagonally dominant. After

𝑛

passes the matrix is

𝐼_{𝑛}

We show by induction on $𝑘 = 1, \dots, 𝑛$ that before pass $𝑘$ the current matrix $𝑀$ satisfies: (i) columns $1, \dots, 𝑘 - 1$ of $𝑀$ are $𝐞_{1}, \dots, 𝐞_{𝑘 - 1}$ ; (ii) rows $𝑘, \dots, 𝑛$ of $𝑀$ vanish in columns $1, \dots, 𝑘 - 1$ ; (iii) the block ${(𝑚_{𝑖 𝑗})}_{𝑘 \leq 𝑖, 𝑗 \leq 𝑛}$ is strictly diagonally dominant. For $𝑘 = 1$ , $𝑀 = 𝐴$ and this is the hypothesis.

Assume (i)–(iii) before pass $𝑘$ . By (iii), $| 𝑚_{𝑘 𝑘} | >$ $\sum_{𝑗 > 𝑘, 𝑗 \neq 𝑘} | 𝑚_{𝑘 𝑗} | \geq$ $0$ , so $𝑚_{𝑘 𝑘} \neq 0$ . By (ii), the scan picks column $𝑘$ , and the $(𝑘, 𝑘)$ entry is nonzero, so there is no swap. The pass scales row $𝑘$ by $𝑚_{𝑘 𝑘}^{- 1}$ and then, for each $𝑖 \neq 𝑘$ , adds $- 𝑚_{𝑖 𝑘}$ times the new row $𝑘$ to row $𝑖$ . Row $𝑘$ vanishes in columns $1, \dots, 𝑘 - 1$ by (ii), so these columns do not change, and column $𝑘$ becomes $𝐞_{𝑘}$ . This gives (i) and (ii) for $𝑘 + 1$ . For $𝑖, 𝑗 > 𝑘$ , the new entries are

𝑚_{𝑖 𝑗}^{'} = 𝑚_{𝑖 𝑗} - 𝑚_{𝑖 𝑘} \frac{𝑚_{𝑘 𝑗}}{𝑚_{𝑘 𝑘}} .

To prove (iii) for $𝑘 + 1$ , fix $𝑖 > 𝑘$ , and let $\sum^{'}$ denote a sum over $𝑗 > 𝑘$ with $𝑗 \neq 𝑖$ . The dominance of row $𝑘$ and of row $𝑖$ in the old block give

\sum^{'} | 𝑚_{𝑘 𝑗} | < | 𝑚_{𝑘 𝑘} | - | 𝑚_{𝑘 𝑖} |, \sum^{'} | 𝑚_{𝑖 𝑗} | < | 𝑚_{𝑖 𝑖} | - | 𝑚_{𝑖 𝑘} | .

Using the triangle inequality and then these two bounds (the first multiplied by $| 𝑚_{𝑖 𝑘} | / | 𝑚_{𝑘 𝑘} | \geq$ $0$ , so it may become an equality),

\begin{aligned} \sum^{'} | 𝑚_{𝑖 𝑗}^{'} | & \leq \sum^{'} | 𝑚_{𝑖 𝑗} | + \frac{| 𝑚_{𝑖 𝑘} |}{| 𝑚_{𝑘 𝑘} |} \sum^{'} | 𝑚_{𝑘 𝑗} | \\ < | 𝑚_{𝑖 𝑖} | - | 𝑚_{𝑖 𝑘} | + \frac{| 𝑚_{𝑖 𝑘} |}{| 𝑚_{𝑘 𝑘} |} (| 𝑚_{𝑘 𝑘} | - | 𝑚_{𝑘 𝑖} |) \\ = | 𝑚_{𝑖 𝑖} | - | \frac{𝑚_{𝑖 𝑘} 𝑚_{𝑘 𝑖}}{𝑚_{𝑘 𝑘}} | \leq | 𝑚_{𝑖 𝑖} - \frac{𝑚_{𝑖 𝑘} 𝑚_{𝑘 𝑖}}{𝑚_{𝑘 𝑘}} | = | 𝑚_{𝑖 𝑖}^{'} |, \end{aligned}

where the last inequality is $| 𝑥 | - | 𝑦 | \leq | 𝑥 - 𝑦 |$ . So the new block is strictly diagonally dominant, which completes the induction.

So every pass finds its pivot on the diagonal without a swap, and after pass $𝑛$ the matrix is $𝐼_{𝑛}$ by (i). Hence $rref (𝐴) = 𝐼_{𝑛}$ , and $𝐴$ is invertible by Theorem 3.3.23.

Exercise 3.3.57.hard Let

𝐴 \in 𝐹^{𝑚 \times 𝑛}

, and let

𝐺 \in 𝐹^{𝑚 \times 𝑚}

be invertible with

𝐺 𝐴 = rref (𝐴)

, which has

𝑟

pivots. For a row vector

𝐳 = (𝑧_{1}, \dots, 𝑧_{𝑚})

, the product

𝐳 𝐴

𝑧_{1}

times row

1

𝐴

, plus

\dots

, plus

𝑧_{𝑚}

times row

𝑚

. Call

𝐳

a relation among the rows of

𝐴

𝐳 𝐴 = 𝟎

. Show that the relations among the rows of

𝐴

are exactly the linear combinations of the last

𝑚 - 𝑟

rows of

𝐺

Solution.

Uses. Definition 2.4.1 (Matrix product), Proposition 3.3.8 (Properties of the output), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Definition 2.5.12 (Invertible)

Hint 1. The rows of

𝐺

numbered

𝑟 + 1, \dots, 𝑚

are relations, since the corresponding rows of

𝐺 𝐴

are zero.

Hint 2. Conversely, if

𝐳 𝐴 = 𝟎

, put

𝐰 = 𝐳 𝐺^{- 1}

, so that

𝐳 = 𝐰 𝐺

and

𝐰 rref (𝐴) = 𝟎

Hint 3. Look at the entries of

𝐰 rref (𝐴)

in the pivot columns.

Sketch. Row

𝑖

𝐺 𝐴

is (row

𝑖

𝐺

)

𝐴

, so the last

𝑚 - 𝑟

rows of

𝐺

are relations, and so are their combinations. If

𝐳 𝐴 = 𝟎

, then

𝐰 = 𝐳 𝐺^{- 1}

satisfies

𝐰 𝑅 = 𝟎

with

𝑅 = rref (𝐴)

; the entry of

𝐰 𝑅

in column

𝑝_{𝑠}

𝑤_{𝑠}

, so

𝑤_{1} = \dots = 𝑤_{𝑟} = 0

, and

𝐳 = 𝐰 𝐺

is a combination of rows

𝑟 + 1, \dots, 𝑚

𝐺

Let $𝑅 = rref (𝐴) = 𝐺 𝐴$ and let $𝛄_{1}, \dots, 𝛄_{𝑚}$ be the rows of $𝐺$ . By Definition 2.4.1, row $𝑖$ of $𝐺 𝐴$ is $𝛄_{𝑖} 𝐴$ , and $(𝑐 𝐳 + 𝑐^{'} 𝐳^{'}) 𝐴 =$ $𝑐 𝐳 𝐴 +$ $𝑐^{'} 𝐳^{'} 𝐴$ .

By Proposition 3.3.8(a), rows $𝑟 + 1, \dots, 𝑚$ of $𝑅$ are zero, so $𝛄_{𝑖} 𝐴 = 𝟎$ for $𝑖 > 𝑟$ . Hence every linear combination of $𝛄_{𝑟 + 1}, \dots, 𝛄_{𝑚}$ is a relation.

Conversely, let $𝐳 𝐴 = 𝟎$ , and put $𝐰 = 𝐳 𝐺^{- 1}$ . Then $𝐳 = 𝐰 𝐺$ , and

𝐰 𝑅 = 𝐰 𝐺 𝐴 = 𝐳 𝐴 = 𝟎 .

Now $𝐰 𝑅$ is $𝑤_{1}$ times row $1$ of $𝑅$ , plus $\dots$ , plus $𝑤_{𝑚}$ times row $𝑚$ of $𝑅$ . Let $𝑝_{1} < \dots < 𝑝_{𝑟}$ be the pivot columns. Column $𝑝_{𝑠}$ of $𝑅$ is $𝐞_{𝑠}$ (Lemma 3.3.16(b)), so row $𝑖$ of $𝑅$ has entry $1$ in column $𝑝_{𝑠}$ if $𝑖 = 𝑠$ and $0$ otherwise, and the entry of $𝐰 𝑅$ in column $𝑝_{𝑠}$ is $𝑤_{𝑠}$ . Hence $𝑤_{𝑠} = 0$ for $𝑠 \leq 𝑟$ , and

𝐳 = 𝐰 𝐺 = 𝑤_{𝑟 + 1} 𝛄_{𝑟 + 1} + \dots + 𝑤_{𝑚} 𝛄_{𝑚} .

In the language of transposes, $𝐳 𝐴 = 𝟎$ says $𝐴^{𝖳} 𝐳^{𝖳} = 𝟎$ . So the transposes of the last $𝑚 - 𝑟$ rows of $𝐺$ span $ker 𝑇_{𝐴^{𝖳}}$ , one of the four fundamental subspaces of Section 4.3.

Exercise 3.3.58.hard Let $𝑝$ be a prime. For $0 \leq 𝑟 \leq 𝑛$ , let $𝑁 (𝑟, 𝑛)$ be the number of $𝑟 \times 𝑛$ matrices over $𝔽_{𝑝}$ that are in RREF and have no zero row; put $𝑁 (0, 𝑛) = 1$ , and $𝑁 (𝑟, 𝑛) = 0$ for $𝑟 > 𝑛$ .

(a)Show that for $1 \leq 𝑟 \leq 𝑛$ and $𝑛 \geq 2$ ,
$𝑁 (𝑟, 𝑛) = 𝑝^{𝑟} 𝑁 (𝑟, 𝑛 - 1) + 𝑁 (𝑟 - 1, 𝑛 - 1) .$
(b)For $𝑝 = 2$ , compute $𝑁 (2, 4)$ , and the number of row equivalence classes in $𝔽_{2}^{2 \times 4}$ .

Solution.

Uses. Theorem 3.3.12 (Matrices in RREF), Lemma 3.3.16 (Reading the columns of a matrix in RREF), Corollary 3.3.18 (RREF and row equivalence)

Hint 1. Split according to whether the last column is a pivot column.

Hint 2. If column

𝑛

is a pivot column, it must hold the last pivot. Delete the last row and the last column. If it is not, delete only the last column. In each case, what can the deleted column have been?

Hint 3. For (b), a class contains exactly one matrix in RREF, and a

2 \times 4

matrix in RREF has

0

1

, or

2

nonzero rows, all at the top.

Sketch. If column

𝑛

is a pivot column, it is the last one, so it is

𝐞_{𝑟}

, row

𝑟

(0, \dots, 0, 1)

, and deleting row

𝑟

and column

𝑛

gives a bijection onto the

(𝑟 - 1) \times (𝑛 - 1)

matrices in RREF without zero rows. Otherwise all

𝑟

pivots lie in columns

1, \dots, 𝑛 - 1

, those columns form an

𝑟 \times (𝑛 - 1)

matrix in RREF without zero rows, and column

𝑛

is arbitrary:

𝑝^{𝑟}

choices. For

𝑝 = 2

𝑁 (1, 𝑛) = 2^{𝑛} - 1

𝑁 (2, 3) = 7

𝑁 (2, 4) = 4 \cdot 7 + 7 = 35

, and there are

1 + 15 + 35 = 51

classes.

(a) Let $𝑅$ be an $𝑟 \times 𝑛$ matrix in RREF with no zero row. By Theorem 3.3.12, it has $𝑟$ pivots, one in each row, in columns $𝑝_{1} < \dots < 𝑝_{𝑟}$ .

Column $𝑛$ is a pivot column. Then $𝑝_{𝑟} = 𝑛$ , column $𝑛$ is $𝐞_{𝑟}$ , and row $𝑟$ , whose leading entry is in column $𝑛$ , is $(0, \dots, 0, 1)$ . Deleting row $𝑟$ and column $𝑛$ leaves an $(𝑟 - 1) \times (𝑛 - 1)$ matrix $𝑅_{0}$ . Rows $1, \dots, 𝑟 - 1$ of $𝑅$ have zero entries in column $𝑛$ , so they keep their leading entries, and $𝑅_{0}$ satisfies (R1)–(R4) with no zero row. Conversely, for any such $𝑅_{0}$ , the matrix $(\begin{matrix} 𝑅_{0} & 0 \\ 0 & 1 \end{matrix})$ satisfies (R1)–(R4) with no zero row and has column $𝑛$ as a pivot column. So there are $𝑁 (𝑟 - 1, 𝑛 - 1)$ matrices in this case.

Column $𝑛$ is not a pivot column. Then all $𝑟$ pivots lie in columns $1, \dots, 𝑛 - 1$ , and deleting column $𝑛$ leaves an $𝑟 \times (𝑛 - 1)$ matrix in RREF without zero rows (the leading entries are unchanged). Conversely, given such a matrix, appending any column $𝐜 \in 𝔽_{𝑝}^{𝑟}$ gives a matrix satisfying (R1)–(R4): the leading entries are unchanged, and (R4) says nothing about a column without a leading entry. So there are $𝑝^{𝑟} 𝑁 (𝑟, 𝑛 - 1)$ matrices in this case. (When $𝑟 = 𝑛$ there are none, consistent with $𝑁 (𝑛, 𝑛 - 1) = 0$ .)

Adding the two cases gives the recursion.

(b) With $𝑝 = 2$ : $𝑁 (1, 1) = 1$ and $𝑁 (1, 𝑛) =$ $2 𝑁 (1, 𝑛 - 1) +$ $1$ , so $𝑁 (1, 2) = 3$ , $𝑁 (1, 3) = 7$ , $𝑁 (1, 4) = 15$ . Next $𝑁 (2, 2) =$ $4 \cdot$ $0 +$ $𝑁 (1, 1) =$ $1$ , $𝑁 (2, 3) = 4 \cdot 1 + 3 = 7$ , and

𝑁 (2, 4) = 4 \cdot 𝑁 (2, 3) + 𝑁 (1, 3) = 28 + 7 = 35 .

A $2 \times 4$ matrix in RREF has $𝑟 \in {0, 1, 2}$ nonzero rows, which by (R1) are its top $𝑟$ rows, and they form an $𝑟 \times 4$ matrix in RREF without zero rows. So there are $𝑁 (0, 4) +$ $𝑁 (1, 4) +$ $𝑁 (2, 4) =$ $1 +$ $15 +$ $35 =$ $51$ of them. As in Exercise 3.3.48, each row equivalence class contains exactly one matrix in RREF, so $𝔽_{2}^{2 \times 4}$ has $51$ classes.

The recursion is a $𝑝$ -analogue of Pascal’s rule $(\binom{𝑛}{𝑟}) =$ $(\binom{𝑛 - 1}{𝑟}) +$ $(\binom{𝑛 - 1}{𝑟 - 1})$ . Using row spaces and dimension (Chapter 4), one can show that $𝑁 (𝑟, 𝑛)$ is the number of $𝑟$ -dimensional subspaces of $𝔽_{𝑝}^{𝑛}$ .

Exercise 3.3.59.routineBeyond 21-242 Let

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

(a) Find the LU factorization of $𝐴$ .

(b) Find the $𝐿 𝐷 𝐿^{𝖳}$ factorization of the symmetric matrix $𝑆$ , and write $𝑆 = 𝑀 𝑀^{𝖳}$ with $𝑀$ lower triangular.

Solution.

Uses. Theorem 3.3.33 (PLU and LU factorizations), Theorem 3.3.37 ( $𝐿 𝐷 𝐿^{𝖳}$ factorization)

Hint 1. Run Gaussian elimination and record the multipliers; they are the entries of

𝐿

below the diagonal.

Hint 2. For (b), the diagonal of

𝑈

gives

𝐷

. Here all its entries are equal.

Sketch. (a) The multipliers are

ℓ_{21} = 3

ℓ_{31} = - 2

ℓ_{32} = 3

, and

𝑈

has rows

(1, 2, 0)

(0, 1, 2)

(0, 0, - 1)

. (b) The multipliers are

1 / 2

- 1 / 2

1 / 2

, and

𝑈

has diagonal

4, 4, 4

, so

𝐷 = 4 𝐼_{3}

and

𝑆 = (2 𝐿) {(2 𝐿)}^{𝖳}

; the rows of

𝑀 = 2 𝐿

are

(2, 0, 0)

(1, 2, 0)

(- 1, 1, 2)

(a) Pass $1$ uses the multipliers $ℓ_{21} = 3$ and $ℓ_{31} = - 2$ , leaving rows $(0, 1, 2)$ and $(0, 3, 5)$ . Pass $2$ uses $ℓ_{32} = 3$ , leaving $(0, 0, - 1)$ . By Theorem 3.3.33(b),

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

Check the last row:

- 2 (1, 2, 0) + 3 (0, 1, 2) + (0, 0, - 1) = (- 2, - 1, 5) .

(b) Pass $1$ uses $ℓ_{21} = 2 / 4 = 1 / 2$ and $ℓ_{31} = - 2 / 4 = - 1 / 2$ , leaving rows $(0, 4, 2)$ and $(0, 2, 5)$ . Pass $2$ uses $ℓ_{32} = 1 / 2$ , leaving $(0, 0, 4)$ . So

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

and $𝐷 = 4 𝐼_{3}$ . By Theorem 3.3.37, $𝑆 = 𝐿 (4 𝐼_{3}) 𝐿^{𝖳}$ ; indeed $4 𝐿^{𝖳} = 𝑈$ . So $𝑆 =$ $(2 𝐿) {(2 𝐿)}^{𝖳} =$ $𝑀 𝑀^{𝖳}$ with

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

Check: the rows of $𝑀$ have pairwise products $4, 2, - 2$ (row $1$ with rows $1, 2, 3$ ), $1 + 4 = 5$ , $- 1 + 2 = 1$ , and $1 + 1 + 4 = 6$ , which are the entries of $𝑆$ .

Exercise 3.3.60.standardBeyond 21-242 Show that an invertible matrix

𝐴 \in 𝐹^{𝑛 \times 𝑛}

has at most one factorization

𝐴 = 𝐿 𝑈

with

𝐿

unit lower triangular and

𝑈

upper triangular.

Solution.

Uses. Lemma 3.3.32 (Products and inverses of triangular matrices), Exercise 3.3.53, Definition 2.5.12 (Invertible)

Hint 1. Suppose

𝐿_{1} 𝑈_{1} = 𝐿_{2} 𝑈_{2}

. Why are

𝑈_{1}

and

𝑈_{2}

invertible, and why is

𝑈_{1}^{- 1}

upper triangular?

Hint 2. Rearrange to

𝐿_{2}^{- 1} 𝐿_{1} = 𝑈_{2} 𝑈_{1}^{- 1}

, and look at both sides.

Sketch.

𝑈_{𝑖} = 𝐿_{𝑖}^{- 1} 𝐴

is invertible, so by Exercise 3.3.53 it has nonzero diagonal entries and an upper triangular inverse. Then

𝐿_{2}^{- 1} 𝐿_{1} = 𝑈_{2} 𝑈_{1}^{- 1}

is unit lower triangular and upper triangular, hence

𝐼_{𝑛}

Suppose $𝐴 = 𝐿_{1} 𝑈_{1} = 𝐿_{2} 𝑈_{2}$ with $𝐿_{1}, 𝐿_{2}$ unit lower triangular and $𝑈_{1}, 𝑈_{2}$ upper triangular. By Lemma 3.3.32, $𝐿_{𝑖}$ is invertible, so $𝑈_{𝑖} = 𝐿_{𝑖}^{- 1} 𝐴$ is invertible, as a product of invertible matrices. By Exercise 3.3.53(b), the diagonal entries of $𝑈_{1}$ are nonzero, and then by Exercise 3.3.53(a), $𝑈_{1}^{- 1}$ is upper triangular. Multiplying $𝐿_{1} 𝑈_{1} = 𝐿_{2} 𝑈_{2}$ on the left by $𝐿_{2}^{- 1}$ and on the right by $𝑈_{1}^{- 1}$ gives

𝐿_{2}^{- 1} 𝐿_{1} = 𝑈_{2} 𝑈_{1}^{- 1} .

By Lemma 3.3.32, the left side is unit lower triangular and the right side is upper triangular. A matrix that is both is diagonal, with the diagonal entries of the left side, which are $1$ . So $𝐿_{2}^{- 1} 𝐿_{1} =$ $𝐼_{𝑛} =$ $𝑈_{2} 𝑈_{1}^{- 1}$ , that is, $𝐿_{1} = 𝐿_{2}$ and $𝑈_{1} = 𝑈_{2}$ .

Exercise 3.3.61.challengeBeyond 21-242 Call an $𝑛 \times 𝑛$ matrix an integer elementary matrix if it is a swap $𝐸_{𝑖 𝑗}$ , a sign change $𝐸_{𝑖, - 1}$ , or a replacement $𝐸_{𝑖 𝑐 𝑗}$ with $𝑐 \in ℤ$ . Show that for $𝐴 \in ℤ^{𝑛 \times 𝑛}$ the following are equivalent:

(i) $𝐴$ is invertible (over $ℚ$ ), and $𝐴^{- 1}$ has integer entries;
(ii) $𝐴$ is a product of integer elementary matrices.

In other words, the matrices that can be inverted without leaving $ℤ$ are exactly those that can be row reduced to $𝐼_{𝑛}$ without leaving $ℤ$ .

Solution.

Uses. Exercise 3.2.54, Proposition 3.2.10 (Inverses of elementary matrices), Definition 2.4.33 (Block matrix), induction on $𝑛$

Hint 1. (ii)

\Rightarrow

(i) is quick. For the converse, induct on

𝑛

and imitate the first pass of Gauss–Jordan elimination, using only integer operations.

Hint 2. Let

𝐵 = 𝐴^{- 1}

. The

(1, 1)

entry of

𝐵 𝐴 = 𝐼_{𝑛}

shows that the entries of the first column of

𝐴

have greatest common divisor

1

Hint 3. Use Exercise 3.2.54 on rows

1

and

𝑖

, for

𝑖 = 2, \dots, 𝑛

in turn, to make the first column

𝐞_{1}

. Then show the lower right

(𝑛 - 1) \times (𝑛 - 1)

block has an integer inverse.

Sketch. (ii)

\Rightarrow

(i): inverses of integer elementary matrices are integer elementary. (i)

\Rightarrow

(ii): the first column of

𝐴

has gcd

1

, because

\sum_{𝑘} 𝑏_{1 𝑘} 𝑎_{𝑘 1} = 1

. Euclid’s algorithm on pairs of rows, done with integer elementary matrices, gives

𝐻 𝐴 = (\begin{matrix} 1 & 𝐰 \\ 0 & 𝐴^{'} \end{matrix})

. This matrix has an integer inverse, and comparing blocks shows that

𝐴^{'}

has one too. By induction

𝐴^{'}

reduces to

𝐼_{𝑛 - 1}

by integer operations on rows

2, \dots, 𝑛

, and integer replacements clear

𝐰

. So

𝑃 𝐴 = 𝐼_{𝑛}

for a product

𝑃

of integer elementary matrices, and

𝐴 = 𝑃^{- 1}

(ii) $\Rightarrow$ (i). Integer elementary matrices have integer entries, and by Proposition 3.2.10 their inverses $𝐸_{𝑖 𝑗}$ , $𝐸_{𝑖, - 1}$ , $𝐸_{𝑖 (- 𝑐) 𝑗}$ are again integer elementary. If $𝐴 = 𝐸_{1} \dots 𝐸_{𝑘}$ with all $𝐸_{𝑙}$ integer elementary, then $𝐴$ is invertible with $𝐴^{- 1} = 𝐸_{𝑘}^{- 1} \dots 𝐸_{1}^{- 1}$ , a product of integer matrices, so it has integer entries.

(i) $\Rightarrow$ (ii). We show by induction on $𝑛$ that there is a product $𝑃$ of integer elementary matrices with $𝑃 𝐴 = 𝐼_{𝑛}$ ; then $𝐴 = 𝑃^{- 1}$ is a product of integer elementary matrices by the first part. For $𝑛 = 1$ , $𝐴 = (𝑎)$ with $𝑎$ and $1 / 𝑎$ integers, so $𝑎 = \pm 1$ , and $𝑃 = (1)$ or $𝑃 = 𝐸_{1, - 1}$ works.

Let $𝑛 \geq 2$ and $𝐵 = 𝐴^{- 1} \in ℤ^{𝑛 \times 𝑛}$ . The $(1, 1)$ entry of $𝐵 𝐴 = 𝐼_{𝑛}$ is $\sum_{𝑘} 𝑏_{1 𝑘} 𝑎_{𝑘 1} = 1$ , so every common divisor of $𝑎_{11}, \dots, 𝑎_{𝑛 1}$ divides $1$ . For $𝑖 = 2, \dots, 𝑛$ in turn, if the current entries in positions $(1, 1)$ and $(𝑖, 1)$ are not both $0$ , apply Exercise 3.2.54(b) to them: it gives $2 \times 2$ integer elementary matrices that turn this pair into (their gcd, $0$ ), and acting on rows $1$ and $𝑖$ only, they are $𝑛 \times 𝑛$ integer elementary matrices. Row operations of this kind do not change the set of common divisors of the entries of the first column (each new entry is an integer combination of old ones, and the operations can be undone by integer elementary matrices), so at the end the first column is $(𝑔, 0, \dots, 0)$ , where $𝑔 \geq 1$ is a common divisor of the original entries; hence $𝑔 = 1$ . So we have a product $𝐻_{1}$ of integer elementary matrices with

𝐻_{1} 𝐴 = (\begin{matrix} 1 & 𝐰 \\ 0 & 𝐴^{'} \end{matrix}), 𝐰 \in ℤ^{1 \times (𝑛 - 1)}, 𝐴^{'} \in ℤ^{(𝑛 - 1) \times (𝑛 - 1)} .

This matrix is invertible with integer inverse $𝐶 = 𝐴^{- 1} 𝐻_{1}^{- 1}$ . Write $𝐶 = (\begin{matrix} 𝑐 & 𝐱 \\ 𝐲 & 𝐶^{'} \end{matrix})$ in the same block sizes. Comparing first block columns in $𝐶 (𝐻_{1} 𝐴) = 𝐼_{𝑛}$ gives $𝑐 = 1$ and $𝐲 = 𝟎$ , and then the lower right blocks of $𝐶 (𝐻_{1} 𝐴) = 𝐼_{𝑛}$ and $(𝐻_{1} 𝐴) 𝐶 = 𝐼_{𝑛}$ give $𝐶^{'} 𝐴^{'} = 𝐼_{𝑛 - 1}$ and $𝐴^{'} 𝐶^{'} = 𝐼_{𝑛 - 1}$ . So $𝐴^{'}$ is invertible with integer inverse $𝐶^{'}$ , and by the induction hypothesis there is a product $𝑃^{'}$ of $(𝑛 - 1) \times (𝑛 - 1)$ integer elementary matrices with $𝑃^{'} 𝐴^{'} = 𝐼_{𝑛 - 1}$ . Each factor $𝐹$ of $𝑃^{'}$ gives the $𝑛 \times 𝑛$ integer elementary matrix $(\begin{matrix} 1 & 0 \\ 0 & 𝐹 \end{matrix})$ (with indices shifted by one), so $𝐻_{2} = (\begin{matrix} 1 & 0 \\ 0 & 𝑃^{'} \end{matrix})$ is a product of integer elementary matrices, and $𝐻_{2} 𝐻_{1} 𝐴 =$ $(\begin{matrix} 1 & 𝐰 \\ 0 & 𝐼_{𝑛 - 1} \end{matrix})$ . Finally, adding $- 𝑤_{𝑗}$ times row $𝑗 + 1$ to row $1$ , for $𝑗 = 1, \dots, 𝑛 - 1$ , clears $𝐰$ with integer replacements. This gives $𝑃 𝐴 = 𝐼_{𝑛}$ with $𝑃$ a product of integer elementary matrices.

For the matrix of Example 3.3.25, which has an integer inverse, this explains why fractions could have been avoided there.

More practice

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

3.3.6Row echelon form Beyond 21-242

3.3.7LU and PLU factorizations Beyond 21-242

3.3.8Symmetric matrices: 𝐿𝐷𝐿𝖳 Beyond 21-242

More practice

3.3.8Symmetric matrices: $𝐿 𝐷 𝐿^{𝖳}$ Beyond 21-242