2.6 Systems of equations and elimination

Solving Ax = b asks whether b is in the range of A and how much freedom is left over. Row operations answer both without changing the solutions, and the pivots they expose give the rank, the four fundamental subspaces and the inverse.

Chapter 2.3 ended with a promise: if $T(x) = b$ has one solution, then all solutions are that one plus the null space. This chapter turns the promise into a method. You are given a system of equations like the ones you solved by substitution in school. Does it have a solution? Is that solution the only one? How do you find every solution, even when there are hundreds of equations? Spagnolie opened his course with exactly these questions (Lecture 1, “Whence linear algebra?”) and answered them in Lectures 11 to 13. The answer is Gaussian elimination. The numbers it produces, called pivots, also count the rank, the nullity and the dimensions of the four fundamental subspaces, and they compute inverses.

Before you start

2.3: null space, range, and the rank–nullity theorem. 2.2: basis and dimension. 2.5: a matrix times a vector, matrix multiplication, the identity matrix and the transpose. 2.4: the inverse of a map, and the fact that a map is invertible exactly when it is both one-to-one and onto.

Quick checkA linear map

T: \mathbb R^5 \to \mathbb R^3

has rank 2. What is its nullity?

Quick checkAre the vectors

(1, 2)

and

(2, 4)

linearly independent?

Quick check

A

is a

3 \times 2

matrix (3 rows, 2 columns). The map

x \mapsto Ax

goes from which space to which?

Where this came from· Elimination is older than Gauss

The Chinese book Nine Chapters on the Mathematical Art has an eighth chapter, “fangcheng” (rectangular arrays), that solves systems of linear equations (the book took its final form around the first century CE). The coefficients are laid out as an array of counting rods, and columns are combined to clear unknowns one at a time. That is elimination on an augmented matrix. In Europe Newton wrote a lesson on it around 1670. The method carries Gauss’s name because of the problem astronomers and surveyors had in the early 1800s: more measurements than unknowns, so no exact solution. Gauss published the method of least squares for such systems in 1809, and in 1810 he gave a compact notation for eliminating on their “normal equations”. In the same period, in 1801, he worked out from 41 days of observations where the lost asteroid Ceres would reappear, and it was found again close to his prediction. The “too many measurements” situation is the second system in the picture below and returns in chapter 2.10.

The picture

Take the system $x + y = 1$ , $2x + 2y = 3$ . As lines in the plane the two equations are parallel and never meet, so there is no solution. That is the row picture: one line per equation. There is a second way to read the same system, by columns:

x\begin{bmatrix}1\\2\end{bmatrix} + y\begin{bmatrix}1\\2\end{bmatrix} = \begin{bmatrix}1\\3\end{bmatrix}.

Now the question is whether $(1, 3)$ is a combination of the two columns. Both columns are $(1, 2)$ , so every combination is a multiple of $(1, 2)$ , and $(1, 3)$ is not one. Pick “Squash to a line” below and press “Apply the map”. (This preset has columns $(1, \tfrac12)$ and $(2, 1)$ instead of $(1, 2)$ twice, but the same thing happens: the second column is a multiple of the first.) The two arrows $\hat\imath$ and $\hat\jmath$ land on the same line, and the whole plane is flattened onto it. That green line is the range, the set of right sides $b$ the map can reach. The red line is the null space, everything the map sends to the origin. A right side $b$ on the green line can be reached, and because the whole red line is sent to one point, each reachable $b$ is reached by a whole line of inputs. A right side off the green line cannot be reached at all.

Now pick “Shear”. The two columns $(1, 0)$ and $(1, 1)$ point in different directions, so the map does not flatten anything. Every point of the plane is hit, and hit exactly once. Solving $Ax = b$ here means asking where in the plane the point $b$ came from, and there is always exactly one answer.

Spagnolie’s Lecture 1 listed four systems to show that the answer is not decided by counting equations and unknowns:

system	equations, unknowns	what happens
$2x + 3y - z = 4$ , $x - 4y + 2z = -1$ , $3x + 10y - 4z = 9$	3, 3	infinitely many solutions, because equation 3 is $2 \times$ (equation 1) $-$ equation 2
$3x_1 + x_2 = 1$ , $2x_1 - x_2 = 0$ , $4x_1 + 7x_2 = 2$	3, 2	none: the first two force $x_1 = \tfrac15$ , $x_2 = \tfrac25$ , and then $4x_1 + 7x_2 = \tfrac{18}5 \ne 2$
$3x_1 + x_2 + 2x_3 = 1$ , $x_1 + x_2 + x_3 = 2$	2, 3	infinitely many
$x + y = 1$ , $3x - y = 2$	2, 2	exactly one, $(\tfrac34, \tfrac14)$

We solve the first three below with the method of this chapter. The second one comes back in chapter 2.10, where “no exact solution” turns into “find the best approximate one”.

The idea, in words

Write the system as $Ax = b$ , where $A$ is the matrix of the linear map $T(x) = Ax$ (2.5). Then a solution is a point $x$ that $T$ sends to $b$ . Three questions have three answers from earlier chapters.

Why· Three questions, three tools

Does a solution exist? Only if $b$ is in the range of $T$ . The range is spanned by the columns of $A$ , so this asks whether $b$ is a combination of the columns.

Is it the only one? Only if the null space of $T$ is $\{O\}$ . Two solutions differ by a vector of the null space.

How do I find it? By elimination: rewrite the equations, step by step, into a system with the same solutions but with the answer visible. Each rewriting step is something you did in school (add a multiple of one equation to another to cancel an unknown). The only new things are a proof that it is allowed, and a way to know when to stop.

Because solutions come as “one particular solution plus the null space”, the number of solutions can only be $0$ , $1$ or infinitely many. It is never exactly two. A line through two solutions consists of solutions, and a line has infinitely many points. The proof is below.

In JEE you met 3 by 3 systems with a determinant $\Delta$ , and rules such as “if $\Delta \ne 0$ there is exactly one solution” and “if $\Delta = 0$ and $\Delta_1 = \Delta_2 = \Delta_3 = 0$ there are infinitely many solutions”. The second rule is not quite right. The system $x + y + z = 1$ , $x + y + z = 2$ , $x + y + z = 3$ has all of these determinants equal to $0$ and no solution at all. Determinant rules apply only to square systems, and even there they cannot always tell you which case you are in. Elimination works for every shape, tells you the case, and writes the solutions out. Chapter 2.7 shows what the determinant rules really say.

Definitions and theorems

Systems and the solution set

Definition T

System of linear equations

A system of $m$ linear equations in $n$ unknowns is

\begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &= b_1,\\ &\ \,\vdots\\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &= b_m. \end{aligned}

The numbers $a_{ij}$ are the coefficients, the $b_i$ are the right-hand sides and $x_1, \dots, x_n$ are the unknowns. A solution is an $n$ -tuple $x = (x_1, \dots, x_n)$ that makes all $m$ equations true at once. Collect the coefficients into the $m \times n$ matrix $A = (a_{ij})$ and the right sides into $b \in \mathbb R^m$ . The system is then the single equation $Ax = b$ (Apostol 2.17, equation 2.23). It is homogeneous if $b = O$ (Spagnolie: “homos” means same, “genos” means kind). The homogeneous system $Ay = O$ that shares the same $A$ always has the solution $y = O$ .

In one line $m$ equations in $n$ unknowns, each of the form (numbers) times $x_1, \dots, x_n$ added up, equal to a number. Written $Ax = b$ .

Why it existsIt is the oldest question in linear algebra, and it is exactly the question 'which inputs does the linear map $x \mapsto Ax$ send to $b$ ?'.

Theorem T Apostol Thms 2.18 and 2.19; Spagnolie Lecture 11

Solutions are a particular solution plus the null space

Let $A$ be an $m \times n$ matrix and suppose $Ax_p = b$ . Then $x$ solves $Ax = b$ if and only if $x - x_p$ is in the null space $N(A)$ . So the solution set is $\{x_p + y : y \in N(A)\}$ . If $v_1, \dots, v_k$ is a basis of $N(A)$ , every solution is

x = x_p + t_1 v_1 + \dots + t_k v_k

for some scalars $t_i$ . Apostol calls this the general solution.

In one lineIf $x_p$ solves $Ax = b$ , then the solutions are exactly $x_p + y$ with $y$ in the null space of $A$ .

Why it is trueSubtracting two solutions kills $b$ , so the difference solves the homogeneous system. This is the $+\,C$ of integration, now for matrices.

ProofSpagnolie Lecture 11; Apostol 2.17

The idea: One line of linearity, read in both directions. It is the same argument as the '+ C' application in 2.3.

A(x - x_p) = Ax - Ax_p = Ax - b

Linearity of

x \mapsto Ax

: matrix times vector respects subtraction.

Ax = b

if and only if

A(x - x_p) = O

The right side is

O

exactly when

Ax = b

Ax = b

if and only if

x - x_p \in N(A)

That is the definition of the null space.

The solutions are exactly

x_p + y

with

y \in N(A)

, and

y = t_1 v_1 + \dots + t_k v_k

Write

y = x - x_p

. Then

x = x_p + y

. Every

y \in N(A)

is a combination of the basis

v_1, \dots, v_k

In the picture. Go back to “Squash to a line” in the first viewer. The red line is $N(A)$ , and it is squashed onto the origin. Take any point on the green line. The inputs that land on it form a line parallel to the red one: one particular input $x_p$ , plus every vector of the red line. Step 1 of the proof is the statement that two inputs landing on the same point differ by something that lands on $O$ .

Corollary T Apostol 2.17; Spagnolie Lecture 11

A system has zero, one or infinitely many solutions

For $Ax = b$ :

there is no solution exactly when $b$ is not in the range of $A$ ;
there is exactly one solution exactly when $b$ is in the range of $A$ and $N(A) = \{O\}$ ;
there are infinitely many solutions exactly when $b$ is in the range of $A$ and $N(A) \ne \{O\}$ .

In one lineNo solution if $b$ is not in the range of $A$ . Otherwise one solution if the null space is $\{O\}$ , and infinitely many if it is bigger.

Why it is trueThe solutions form a translated copy of the null space, and a subspace with a non-zero vector has infinitely many vectors.

ProofApostol 2.17

The idea: Case 1 is the definition of range. Cases 2 and 3 come from the previous theorem.

A solution exists exactly when

b

is in the range. This is case 1.

x

is a solution if and only if

Ax = b

, and the range is the set of all

Ax

b

is in the range and

N(A) = \{O\}

, there is exactly one solution.

Previous theorem: the solution set is

x_p + N(A)

. If

N(A) = \{O\}

, that set is the single vector

x_p

N(A) \ne \{O\}

, the vectors

x_p + ty

for

t \in \mathbb R

are all different solutions, so there are infinitely many.

Pick a non-zero

y \in N(A)

. For different scalars

t \ne s

ty \ne sy

because

(t - s)y \ne O

for a non-zero

y

So each of the three outcomes happens in exactly the stated situation and no other.

The three cases (not in the range; in the range with

N(A) = \{O\}

; in the range with

N(A) \ne \{O\}

) cover every possibility and exclude each other.

Quick checkThe system

Ax = b

has two different solutions. How many solutions does it have in total?

Definition T

Column space

The column space of an $m \times n$ matrix $A$ with columns $a_1, \dots, a_n \in \mathbb R^m$ is the span $L(a_1, \dots, a_n)$ of its columns, a subspace of $\mathbb R^m$ .

In one lineThe span of the columns of $A$ . It equals the range of $x \mapsto Ax$ .

Why it existsIt lets you decide whether $Ax = b$ is solvable by asking whether $b$ is a combination of the columns.

Theorem T Spagnolie Lecture 13 page 1

Matrix times vector is a combination of the columns

For an $m \times n$ matrix $A$ with columns $a_1, \dots, a_n$ and $x \in \mathbb R^n$ ,

Ax = x_1 a_1 + x_2 a_2 + \dots + x_n a_n.

Consequently the range of $x \mapsto Ax$ equals the column space of $A$ , and $\operatorname{rank} A = \dim(\text{column space})$ . The rank of a matrix means the rank of the map $x \mapsto Ax$ from 2.3.

In one line $Ax = x_1 a_1 + \dots + x_n a_n$ , so the column space is the range of $x \mapsto Ax$ and the rank of $A$ is its dimension.

Why it is trueEntry $i$ of $Ax$ is $\sum_j a_{ij}x_j$ , which is entry $i$ of $\sum_j x_j a_j$ .

ProofSpagnolie Lecture 13

The idea: Compare the two sides one entry at a time.

Entry

i

Ax

\sum_{j=1}^n a_{ij}x_j

Definition of matrix times vector, from 2.5.

Entry

i

x_1 a_1 + \dots + x_n a_n

\sum_{j=1}^n x_j a_{ij}

. The two entries agree for every

i

, so

Ax = \sum_j x_j a_j

Entry

i

of the column

a_j

a_{ij}

, and scaling by

x_j

and adding act entry by entry.

So the set of all

Ax

is the span of the columns.

The right side ranges over all combinations of the columns as

x

ranges over

\mathbb R^n

Worked example Spagnolie Lecture 11 page 4, adapted

Is b in the column space? Then find all solutions of Ax = b, for A with rows (1, 2) and (2, 4)

Solution.

Write the columns. The columns of $A$ are $a_1 = (1, 2)$ and $a_2 = (2, 4)$ . $Ax$ is a combination of the columns, so the question about solvability is a question about their span.
Find the span. $a_2 = 2a_1$ , so the column space is $\{c\,(1, 2)\}$ , a line in the plane. A column that is a multiple of another adds nothing to the span (2.2).
Test $b = (3, 6)$ . $(3, 6) = 3\,(1, 2)$ is on the line, so solutions exist. A particular solution is $x_p = (3, 0)$ , because $3a_1 + 0a_2 = b$ . Take the coefficients of the combination as the entries of $x$ .
Find the null space. $Ay = O$ means $y_1 + 2y_2 = 0$ (the second equation is twice the first). So $y = t\,(-2, 1)$ . One equation in two unknowns leaves one unknown free.
Assemble. The solutions are $(3, 0) + t(-2, 1)$ . Particular solution plus null space.
Test $b = (3, 7)$ . $(3, 7)$ is not a multiple of $(1, 2)$ , so it is not on the line and there is no solution. The second equation $2x_1 + 4x_2 = 7$ contradicts twice the first, $2x_1 + 4x_2 = 6$ .

Answer. For $b = (3, 6)$ the solutions are $(3, 0) + t(-2, 1)$ . For $b = (3, 7)$ there are none.

Row operations

Elimination needs a bookkeeping device. Writing $x_1, x_2, x_3$ again and again is a waste, so we keep only the numbers.

Definition T

Augmented matrix

The augmented matrix of $Ax = b$ is the $m \times (n + 1)$ matrix $[A \mid b]$ whose last column is $b$ . The vertical bar is only a reminder; it is not part of the matrix. Row $i$ stands for the equation $a_{i1}x_1 + \dots + a_{in}x_n = b_i$ .

In one lineThe matrix $[A \mid b]$ : the coefficient matrix with the right-hand side added as an extra last column.

Why it existsEach row is one equation. Doing something to an equation is doing it to a row.

Definition T

Row operations

A row operation is one of three moves:

Swap two rows ( $R_i \leftrightarrow R_j$ ).
Scale a row by a number $c \ne 0$ ( $R_i \to cR_i$ ).
Add a multiple of one row to a different row ( $R_j \to R_j + cR_i$ with $i \ne j$ ).

On an augmented matrix these are: reorder the equations, multiply an equation by a non-zero constant, add a multiple of one equation to another. Spagnolie’s Lecture 12 lists the same three.

In one lineThe three allowed moves on the rows of a matrix: swap two rows, multiply a row by a non-zero number, add a multiple of one row to another row.

Why it existsThey are exactly the moves of school elimination, and each one can be undone, so none of them changes the solutions.

Theorem T Spagnolie Lecture 12 page 6; Apostol 2.18

Row operations do not change the solutions

If $[A' \mid b']$ is obtained from $[A \mid b]$ by a sequence of row operations, then $Ax = b$ and $A'x = b'$ have the same set of solutions. In particular (take $b = O$ ), $N(A) = N(A')$ .

In one lineIf $[A' \mid b']$ comes from $[A \mid b]$ by row operations, the two systems have exactly the same solutions.

Why it is trueEvery row operation can be undone by another row operation, so no solution can be lost or gained.

ProofSpagnolie Lecture 12; Apostol 2.18

The idea: Show that one row operation never loses a solution. Then notice that every row operation has an opposite row operation, so it never gains one either.

Suppose

x

solves the old system. After a swap,

x

still satisfies every equation.

Swapping lists the same equations in a different order, and a solution satisfies every equation in the list.

After scaling row

i

c

, the new equation

i

holds for

x

Write

a_i \cdot x

for

a_{i1}x_1 + \dots + a_{in}x_n

, the left side of equation

i

(row

i

A

times

x

). If

a_i \cdot x = b_i

then multiplying both sides by

c

gives

(c\,a_i) \cdot x = c\,b_i

After adding

c

times row

i

to row

j

, the new equation

j

holds for

x

Equals added to equals are equal: if

a_i \cdot x = b_i

and

a_j \cdot x = b_j

, then

(a_j + c\,a_i) \cdot x = b_j + c\,b_i

Every row operation is undone by a row operation of the same kind.

Swap again to undo a swap. Scale by

1/c

to undo scaling by

c

(this is where

c \ne 0

is needed). Add

-c

times row

i

to row

j

to undo adding

c

times.

So every solution of the new system is a solution of the old system. Together with the earlier steps, the two systems have the same solutions.

Apply the first three steps to the undoing operation: it carries the new system back to the old one without losing a solution.

The same holds for any sequence of row operations.

Induction on the number of operations: the claim for one operation, applied again and again.

In the picture. Two lines in the plane cross at one point. Replace the second line’s equation by (second equation) plus $c \times$ (first equation). The new line is a different line, but it still passes through the crossing point, because that point satisfies both old equations. Tilting a line about the common point is what “add a multiple” does, and turning it back is what “subtract that multiple” does.

Quick checkWhich of these is NOT a legal row operation?

Echelon form

Definition T

Row echelon form

In a non-zero row, the first non-zero entry from the left is the leading entry of that row. A matrix is in row echelon form if

every zero row is below every non-zero row, and
the leading entry of each non-zero row is strictly to the right of the leading entry of the row above it.

(Spagnolie draws this as a staircase. Everything below the staircase is zero.)

In one lineA staircase shape: zero rows at the bottom, and the first non-zero entry of each row is further right than the first non-zero entry of the row above.

Why it existsA system in this shape can be solved from the bottom row up, and the staircase shows at once how many independent equations there are.

Definition T

Pivot

In a matrix in row echelon form, a pivot is the leading entry of a non-zero row. A pivot column is a column containing a pivot.

In one lineA leading entry of a matrix in echelon form. A column that holds one is a pivot column.

Why it existsThe pivots count the independent equations, so they will turn out to count the rank.

Definition T

Reduced row echelon form

A matrix is in reduced row echelon form (RREF) if it is in row echelon form, every pivot equals 1, and every pivot is the only non-zero entry in its column. Spagnolie’s example $U = \begin{bmatrix}1&3&3&2\\0&0&3&1\\0&0&0&0\end{bmatrix}$ is in echelon form with pivots $1$ (column 1) and $3$ (column 3). It is not reduced, because the second pivot is not 1 and the $3$ above it is not zero. The matrix $\begin{bmatrix}1&3&0&1\\0&0&1&\tfrac13\\0&0&0&0\end{bmatrix}$ is in RREF.

In one lineEchelon form where every pivot is 1 and is the only non-zero entry in its column.

Why it existsHere the answers can be read straight off, with no back substitution.

Definition T

Free variable

Let $R$ be an echelon form of the coefficient matrix. The unknown $x_j$ is a pivot variable if column $j$ of $R$ is a pivot column, and a free variable otherwise.

In one lineAn unknown whose column has no pivot. You may choose its value freely, and the others follow.

Why it existsThe free variables are the freedom left over in the solution set, so they count the nullity.

The non-example $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ fails condition 2: the leading entry of row 2 is in column 1, which is to the left of the leading entry of row 1. One swap puts it in echelon form.

Theorem T Apostol 2.18 (Gauss–Jordan); Spagnolie Lecture 12

Every matrix reduces to reduced row echelon form

Every $m \times n$ matrix can be turned into a matrix in reduced row echelon form by a finite sequence of row operations.

In one lineRow operations can turn any matrix into one in reduced row echelon form.

Why it is trueThe algorithm is the one you already know: pick a pivot, clear the column below it, repeat on what is left, then clear above.

ProofApostol 2.18

The idea: Induction on the number of rows. Make the first pivot, clear below it, and apply the induction hypothesis to the rows underneath. Then clear above each pivot from the bottom up.

m = 1

, scale the row so that its leading entry is 1. The matrix is in RREF.

Base case. One row: it is a zero row (already in RREF) or it has a leading entry.

Suppose

m \ge 2

and the matrix is not zero. Let

j

be the first column with a non-zero entry.

If the whole matrix is zero it is already in RREF, and there is nothing to do.

Swap rows if needed so that the entry in row 1, column

j

is non-zero.

A swap is a row operation. Now the entry in row 1, column

j

is non-zero.

Scale row 1 so that this entry is 1. This is the first pivot.

Scaling by the non-zero number

1/(\text{that entry})

is a row operation.

Clear column

j

below the pivot: it is now

1, 0, \dots, 0

For each lower row

i

, add

-(\text{entry in column } j)

times row 1. This is the third kind of row operation.

The rows

2, \dots, m

form a matrix with

m - 1

rows. By the induction hypothesis, row operations on those rows alone bring them to RREF.

Columns

1

j

are zero in rows

2

m

. Row operations among those rows keep them zero, and never touch row 1.

The whole matrix is now in row echelon form with every pivot equal to 1.

The result is a staircase: row 1 has its pivot in column

j

, and the pivots below sit strictly to the right of column

j

, because columns

1

j

are zero in those rows.

Starting at the bottom pivot and moving up, subtract multiples of each pivot row from the rows above to make the rest of that pivot’s column zero. The matrix is now in RREF.

A pivot row has a 1 at its pivot, zeros to the left of it, and (because we work from the bottom up) zeros in the pivot columns of the rows below it, which were cleared earlier. So subtracting a multiple of it from a higher row changes that row only in the pivot column (making it zero) and in non-pivot columns, and leaves the columns already cleared alone.

(The RREF of a matrix is in fact unique, but we never need that. Rank will be defined without reference to any particular reduction.)

Now we can see why this solves systems. Suppose $[R \mid d]$ is the RREF of $[A \mid b]$ . By the theorem on row operations, $Rx = d$ has the same solutions as $Ax = b$ , and $Rx = d$ can be read.

Theorem T Apostol 2.18; Spagnolie Lecture 12 pages 4 and 5

Reading the solutions off the reduced form

Let $[R \mid d]$ be in reduced row echelon form, where $R$ is $m \times n$ with $r$ pivots in columns $j_1 < \dots < j_r$ , and let $F$ be the set of free columns.

If some row of $[R \mid d]$ is $[0\ \dots\ 0 \mid c]$ with $c \ne 0$ (equivalently, the last column is a pivot column), there is no solution.
Otherwise the solutions are exactly the vectors with $x_{j_i} = d_i - \sum_{k \in F} R_{ik}x_k$ for $i = 1, \dots, r$ and $x_k$ arbitrary for $k \in F$ . Equivalently $x = x_p + \sum_{k \in F} x_k v_k$ , where $x_p$ has $x_{j_i} = d_i$ and zeros at free positions, and $v_k$ has $1$ in position $k$ , $-R_{ik}$ in position $j_i$ , and $0$ at the other free positions.
The vectors $v_k$ are a basis of $N(R) = N(A)$ . So $\dim N(A)$ is the number of free variables, and the solution is unique when there are none.

In one lineThe system is inconsistent exactly when the last column is a pivot column. Otherwise each pivot variable equals its right side minus a combination of the free variables.

Why it is trueIn RREF each row has one pivot variable with coefficient 1 and no other pivot variable, so each row says exactly what that pivot variable is.

ProofApostol 2.18

The idea: Write the rows of the reduced system out as equations and solve each for its pivot variable.

Case 1: such a row gives the false equation

0 = c

, so no

x

solves

Rx = d

A row

[0 \dots 0 \mid c]

reads

0 = c

. No

x

makes that true when

c \ne 0

Case 2: row

i

reads

x_{j_i} + \sum_{k \in F} R_{ik}x_k = d_i

. Solving,

x_{j_i} = d_i - \sum_{k \in F}R_{ik}x_k

Row

i

of RREF has a

1

in pivot column

j_i

, zeros in the other pivot columns, and arbitrary numbers

R_{ik}

only in free columns

k

So the solutions are exactly the stated vectors. Substituting the formulas gives

x = x_p + \sum_k x_k v_k

Zero rows read

0 = 0

and impose nothing. Any choice of the free

x_k

gives values of the pivot variables that satisfy every row.

\sum_k t_k v_k = O

, then reading the free position

k

gives

t_k = 0

. So the

v_k

are independent.

Case 3. Take

d = O

so that the solutions are

N(R)

. Look at the free positions:

v_k

has a 1 in position

k

and 0 in the other free positions.

The

v_k

span

N(R)

, so they are a basis, and

N(A) = N(R)

by the theorem on row operations.

From the formula, an element of

N(R)

\sum_k x_k v_k

with

x_k

its own free entries.

Worked example Spagnolie Lecture 12 pages 3 and 4

Solve 2x + y + z = 5, 4x − 6y = −2, −2x + 7y + 2z = 9

Solution.

Write the augmented matrix. The first slide of the visualizer below. Only the numbers matter; the unknowns can be restored at the end.
Clear the first column below the pivot. Use the $2$ in row 1 as the first pivot, and subtract $2R_1$ from $R_2$ , add $R_1$ to $R_3$ . Each is “add a multiple of one row to another”, which does not change the solutions.
Clear the second column below its pivot. Use the $-8$ as the second pivot and add $R_2$ to $R_3$ . The matrix is now in echelon form with three pivots. Three pivots in three unknowns: no free variable, so the solution is unique if it exists.
Continue upwards and scale. Clear above the pivots and divide each row by its pivot, until the left block is $I$ . This is Gauss–Jordan elimination. The last column is then the solution.

Answer. $(x, y, z) = (1, 1, 2)$ , the only solution.

Your answerSolve

x + y + z = 6

x + 2y + 3z = 14

2x + y + z = 7

by elimination. What is

z

Worked example Spagnolie Lecture 1 page 1

Spagnolie's opener: 2x + 3y − z = 4, x − 4y + 2z = −1, 3x + 10y − 4z = 9 (infinitely many solutions)

Solution.

Start with a pivot of 1 to avoid fractions. Swap rows 1 and 2. A swap does not change the solutions, and the leading $1$ makes the arithmetic cleaner.
Clear column 1 below the pivot. Subtract $2R_1$ from $R_2$ and $3R_1$ from $R_3$ . The pivot row is used to cancel the unknown $x$ in the other equations.
Look at what appears. Row 3 becomes twice row 2, so subtracting $2R_2$ from it gives a zero row. A zero row $0 = 0$ means that equation was a consequence of the others (equation 3 was $2\times$ equation 1 minus equation 2), so there are only two independent equations for three unknowns.
Scale and clear above. Divide $R_2$ by $11$ and add $4R_2$ to $R_1$ . That puts the matrix in RREF, where the pivot variables $x, y$ can be read off in terms of the free variable $z$ .
Read the answer. Column 3 has no pivot, so $z$ is free. Theorem above: each pivot variable equals its right side minus a multiple of the free variable.

Answer. The solutions are $\left(\tfrac{13}{11}, \tfrac{6}{11}, 0\right) + t\,(-2, 5, 11)$ , a line in $\mathbb R^3$ (the intersection of two independent planes). Check with $t = 1$ : $(-\tfrac9{11}, \tfrac{61}{11}, 11)$ gives $\tfrac{-18 + 183 - 121}{11} = 4$ in equation 1.

Worked example Spagnolie Lecture 1 page 1

Spagnolie's overdetermined system: 3x₁ + x₂ = 1, 2x₁ − x₂ = 0, 4x₁ + 7x₂ = 2

Solution.

Write the augmented matrix and eliminate. Three equations, two unknowns. We expect to run out of unknowns before equations.
Reduce to echelon form. The steps are in the visualizer. Only the pivot pattern matters: a pivot in the last column is a contradiction.
Read the last row. It says $0 = -\tfrac85$ . Theorem above, case 1: a row $[0\ 0 \mid c]$ with $c \ne 0$ means no solution.

Answer. No solution. (The first two equations alone give $x_1 = \tfrac15$ , $x_2 = \tfrac25$ , and the third equation then fails: $\tfrac45 + \tfrac{14}5 = \tfrac{18}5 \ne 2$ .) The right side $(1, 0, 2)$ is not in the column space of $A$ , which is only a plane in $\mathbb R^3$ .

The third system in the picture table is short enough to do by eye. For $3x_1 + x_2 + 2x_3 = 1$ and $x_1 + x_2 + x_3 = 2$ the RREF is $\left[\begin{array}{ccc|c}1&0&\frac12&-\frac12\\0&1&\frac12&\frac52\end{array}\right]$ . Column 3 is free, so the solutions are $(-\tfrac12, \tfrac52, 0) + t(-1, -1, 2)$ . With two equations and three unknowns there is always at least one free variable (rank is at most 2 and there are 3 columns), so such a system never has a unique solution.

Worked example Spagnolie Lecture 12 page 5 (sign corrected)

Two equations, four unknowns: y − z + u = 2 and 4x + 2y + z = 1

Solution.

Pick pivots. Put the equation with the $x$ term first, and scale: $x + \tfrac12 y + \tfrac14 z = \tfrac14$ and $y - z + u = 2$ . Swapping equations is allowed. Note we reorder equations, never the unknowns.
Find the pivot and free columns. Pivots are in columns of $x$ and $y$ . So $z$ and $u$ are free. There are 4 unknowns and 2 pivots, so the nullity is $4 - 2 = 2$ .
Solve for the pivot variables. $y = 2 + z - u$ . Then $x = \tfrac14 - \tfrac12(2 + z - u) - \tfrac14 z = -\tfrac34 - \tfrac34 z + \tfrac12 u$ . Back substitution, which is Theorem “Reading the solutions” for a non-reduced form.
Split into particular plus null space. With $z = a$ and $u = b$ ,

(x, y, z, u) = (-\tfrac34, 2, 0, 0) + a\,(-\tfrac34, 1, 1, 0) + b\,(\tfrac12, -1, 0, 1).

Set the free variables to $0$ for the particular solution. Set one free variable to $1$ and the other to $0$ for each null vector. 5. Check by multiplying. Particular solution $(-\tfrac34, 2, 0, 0)$ : the equation $y - z + u = 2$ gives $2 - 0 + 0 = 2$ , and $4x + 2y + z = 1$ gives $-3 + 4 + 0 = 1$ . Null vectors: $(-\tfrac34, 1, 1, 0)$ gives $1 - 1 + 0 = 0$ and $-3 + 2 + 1 = 0$ . $(\tfrac12, -1, 0, 1)$ gives $-1 - 0 + 1 = 0$ and $2 - 2 + 0 = 0$ . Always check null vectors by multiplying. The printed lecture notes had the sign of the $u$ term wrong, and the check catches that.

Answer. $(-\tfrac34, 2, 0, 0) + a(-\tfrac34, 1, 1, 0) + b(\tfrac12, -1, 0, 1)$ for all real $a, b$ . The set of solutions is a plane in $\mathbb R^4$ .

Rank, pivots and the four fundamental subspaces

Now the central count. The pivots found by elimination measure the rank, and we prove it.

Theorem T Spagnolie Lecture 12 page 6 and Lecture 13; Apostol 2.18

Rank equals the number of pivots

Let $A$ be an $m \times n$ matrix and let $R$ be an echelon form of $A$ with $r$ pivots. Then:

$\dim N(A) = n - r$ (the number of free variables);
the pivot columns of $A$ itself (not of $R$ ) are a basis of the column space of $A$ ;
$\operatorname{rank} A = r$ , so $n = r + (n - r)$ is the rank–nullity theorem read off the staircase.

In one lineIf an echelon form of $A$ has $r$ pivots, then rank $A = r$ , nullity $= n - r$ , and the pivot columns of the original $A$ are a basis of the column space.

Why it is trueRow operations do not change which combinations of columns equal zero, so they do not change which columns depend on which.

ProofSpagnolie Lecture 12 page 6 and Lecture 13 page 3

The idea: Row operations preserve every relation Σ cⱼaⱼ = O among the columns. In the reduced form the pivot columns are the standard vectors, so they are independent and every other column is a combination of them. The same is then true in A.

Let

R

be the RREF of

A

, with

r

pivots in columns

j_1 < \dots < j_r

Reduce further if needed so

R

is the RREF of

A

. The pivot count does not change: further operations only clear and scale.

The nullity is the number of free variables,

n - r

. This proves part 1.

Theorem on reading solutions, case 3, with

d = O

Any coefficients

c_1, \dots, c_n

give

\sum c_j a_j = O

if and only if

\sum c_j a'_j = O

Row operations do not change the solutions of

Ax = O

, and

Ax = \sum x_j a_j

(columns), so

\sum x_ja_j = O

exactly when

\sum x_j a'_j = O

, where

a'_j

are the columns of

R

The pivot columns of

R

are

e_1, \dots, e_r

, which are independent.

In RREF, pivot column

j_i

is the standard vector

e_i

(a 1 in row

i

and 0 elsewhere).

So the pivot columns of

A

are independent.

Step 3 with a combination that uses only pivot columns: if

\sum_i c_i a_{j_i} = O

then

\sum_i c_ia'_{j_i} = O

, so all

c_i = 0

Every non-pivot column of

R

is a combination of the pivot columns of

R

A non-pivot column

a'_k

R

has non-zero entries only in rows

1, \dots, r

(the rows below are zero), so

a'_k = \sum_{i \le r} R_{ik}e_i = \sum_i R_{ik} a'_{j_i}

a_k = \sum_i R_{ik}a_{j_i}

for every non-pivot column

k

Step 3 again: the relation

a'_k - \sum_i R_{ik}a'_{j_i} = O

among columns of

R

is also a relation among the columns of

A

The pivot columns of

A

are a basis of the column space, so

\operatorname{rank}A = r

. This proves parts 2 and 3.

Every column is a combination of the pivot columns, so they span the column space (a span of all columns). They are independent.

Proof workshopRebuild the proof that the pivot columns of A are a basis of the column space

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

In the picture. In the first viewer, “Squash to a line” has columns $(1, 0.5)$ and $(2, 1)$ . Column 2 is a multiple of column 1, so there is one pivot and the rank is 1, which is the green line. The second column is the non-pivot column and gives the free variable: the red line, of dimension $2 - 1 = 1$ . The “Shear” map has two independent columns, two pivots, rank 2, and a null space of dimension 0.

Quick checkRow reducing

A

gives an echelon form

U

with pivots in columns 1 and 3. Which vectors are a basis of the column space of

A

Your answerWhat is the rank of

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

Your answerThe reduced row echelon form of a

3 \times 5

matrix

A

has pivots in columns 1, 2 and 4. What is

\dim N(A)

The word “original” matters. Spagnolie’s example in Lecture 13 is $A = \begin{bmatrix}1&1&0\\1&1&0\end{bmatrix}$ , which reduces to $U = \begin{bmatrix}1&1&0\\0&0&0\end{bmatrix}$ . The column space of $A$ is the line through $(1, 1)$ , and the column space of $U$ is the line through $(1, 0)$ . They are different lines of the same dimension. Row operations preserve the null space, the row space (next), and the dependences among columns, but they move the column space.

This answers a question from chapter 2.2: how do you find a basis for the span of some given vectors? Put the vectors in as the columns of a matrix, row reduce to find the pivot columns, and keep the original vectors in those columns.

Definition T

Row space

The row space of an $m \times n$ matrix $A$ is the span of its $m$ rows, a subspace of $\mathbb R^n$ . It equals the column space of $A^{\mathsf T}$ .

In one lineThe span of the rows of $A$ , which is the column space of the transpose $A^{\mathsf T}$ .

Why it existsIt is the row-wise partner of the column space, and its dimension turns out to be the same number.

Definition T

Left null space

The left null space of an $m \times n$ matrix $A$ is $N(A^{\mathsf T}) = \{y \in \mathbb R^m : A^{\mathsf T}y = O\}$ . Since $A^{\mathsf T}y = O$ says $y^{\mathsf T}A = O$ (the row vector $y^{\mathsf T}$ multiplies $A$ from the left), this is the set of combinations of the rows of $A$ that equal zero. It is a subspace of $\mathbb R^m$ .

In one lineThe null space of the transpose: all $y \in \mathbb R^m$ with $A^{\mathsf T}y = O$ , equivalently $y^{\mathsf T}A = O$ .

Why it existsIt records which combinations of the equations (the rows) add up to nothing, and so which right sides $b$ are impossible.

Theorem T Spagnolie Lecture 13 page 3

Row rank equals column rank

For every $m \times n$ matrix $A$ of rank $r$ :

\dim(\text{row space}) = \dim(\text{column space}) = r,\quad \dim N(A) = n - r,\quad \dim N(A^{\mathsf T}) = m - r.

In one lineThe row space and the column space of a matrix have the same dimension, the number of pivots. So rank $A$ = rank $A^{\mathsf T}$ .

Why it is trueRow operations do not change the row space, and in echelon form the non-zero rows are visibly independent, as many as there are pivots.

ProofSpagnolie Lecture 13 page 3; Apostol 2.18

The idea: Show the row space is unchanged by row operations. In echelon form the non-zero rows are independent. Then apply rank–nullity to the transpose.

A row operation replaces rows by combinations of rows, so the row space can only shrink.

After a row operation each new row is a combination of old rows, so the new span is inside the old one.

It cannot shrink either. So

A

and its echelon form

R

have the same row space.

Row operations are reversible (previous theorem's proof), so the old rows are combinations of the new rows too.

The row space of

R

is spanned by its

r

non-zero rows.

Zero rows add nothing to a span.

The

r

non-zero rows are independent, so

\dim(\text{row space}) = r

Suppose

\sum_i c_i R_i = O

. Look at the first pivot column: every row below row 1 has a zero there, so only

c_1

contributes, and it forces

c_1 = 0

. Repeat with row 2's pivot column, and so on.

Therefore

\dim N(A^{\mathsf T}) = m - r

The row space of

A

is the column space of

A^{\mathsf T}

, so

\operatorname{rank}A^{\mathsf T} = r

. Rank–nullity applies to

A^{\mathsf T}: \mathbb R^m \to \mathbb R^n

, whose domain has dimension

m

Also

\dim(\text{column space}) = r

and

\dim N(A) = n - r

Parts 1 and 3 of the previous theorem.

This is surprising. A matrix can have 100 rows and 3 columns, and it still has the same number of independent rows as independent columns, which is at most 3. Spagnolie’s notes call it “not remotely obvious”.

Put the four subspaces on one page. This is Strang’s picture, and Spagnolie boxes it in Lecture 13 as the fundamental theorem of linear algebra.

subspace	lives in	dimension
column space (the range of $A$ )	$\mathbb R^m$	$r$
left null space $N(A^{\mathsf T})$	$\mathbb R^m$	$m - r$
row space (the range of $A^{\mathsf T}$ )	$\mathbb R^n$	$r$
null space $N(A)$	$\mathbb R^n$	$n - r$

The input space $\mathbb R^n$ is split as row space ( $r$ ) plus null space ( $n - r$ ), and the output space $\mathbb R^m$ as column space ( $r$ ) plus left null space ( $m - r$ ). The dimensions in each pair add to $n$ and to $m$ .

Your answerA

5 \times 8

matrix has rank 3. What is the dimension of its LEFT null space

N(A^{\mathsf T})

Quick checkA

3 \times 4

matrix has rank 2. Which statement is true?

A preview· Preview: perpendicular subspaces

Each entry of $Ax = O$ says that a row of $A$ , dotted with $x$ , is zero. So every vector of the null space is perpendicular to every row, and the null space and row space meet only at $O$ . The same holds for the left null space and the column space. Chapter 2.9 defines “perpendicular” properly, and 2.10 uses it to find best approximate solutions when $Ax = b$ has no solution.

Worked example Spagnolie Lecture 13 page 3

Find bases for all four subspaces of A with rows (1, 3, 3, 2), (2, 6, 9, 5), (−1, −3, 3, 0)

Solution.

Row reduce. $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 + R_1$ give rows $(0, 0, 3, 1)$ and $(0, 0, 6, 2)$ . Then $R_3 \to R_3 - 2R_2$ gives $(0,0,0,0)$ . So $U = \begin{bmatrix}1&3&3&2\\0&0&3&1\\0&0&0&0\end{bmatrix}$ . Standard elimination to echelon form. The pivots are in columns 1 and 3.
Count. $r = 2$ pivots, $m = 3$ , $n = 4$ . The theorem gives dimensions $2, 2, 4 - 2 = 2$ and $3 - 2 = 1$ .
Column space. Columns 1 and 3 of the ORIGINAL $A$ : $(1, 2, -1)$ and $(3, 9, 3)$ . Pivot columns of $A$ form a basis; the pivot columns of $U$ would be wrong.
Row space. The non-zero rows of $U$ : $(1, 3, 3, 2)$ and $(0, 0, 3, 1)$ . Row operations keep the row space, so the rows of $U$ are a basis of the row space of $A$ .
Null space. Reduce to RREF: $R_1 \to R_1 - R_2$ and $R_2 \to R_2/3$ give $\begin{bmatrix}1&3&0&1\\0&0&1&\frac13\\0&0&0&0\end{bmatrix}$ . Free variables $x_2, x_4$ . Then $x_1 = -3x_2 - x_4$ and $x_3 = -\tfrac13 x_4$ . Take $x_2 = 1, x_4 = 0$ and $x_2 = 0, x_4 = 3$ : $(-3, 1, 0, 0)$ and $(-3, 0, -1, 3)$ . One null vector per free variable. Multiply back to check: the second gives $-3 - 3 + 6 = 0$ , $-6 - 9 + 15 = 0$ , $3 - 3 + 0 = 0$ .
Left null space. Track the operations: $U$ ‘s third row is $R_3 + R_1 - 2(R_2 - 2R_1) = 5R_1 - 2R_2 + R_3$ of $A$ , and it is zero. So $y = (5, -2, 1)$ . The zero row records a combination of rows of $A$ that vanishes; that is exactly $y^{\mathsf T}A = O$ . The dimension count $m - r = 1$ says one such vector is enough. Check: $5(1, 3, 3, 2) - 2(2, 6, 9, 5) + (-1, -3, 3, 0) = (0, 0, 0, 0)$ .

Answer. Column space: $\{(1, 2, -1), (3, 9, 3)\}$ . Row space: $\{(1,3,3,2), (0,0,3,1)\}$ . Null space: $\{(-3,1,0,0), (-3,0,-1,3)\}$ . Left null space: $\{(5,-2,1)\}$ . Dimensions $2, 2, 2, 1$ , adding to $n = 4$ and $m = 3$ in pairs.

Inverses

Definition T

Inverse matrix

Let $A$ be an $n \times n$ matrix. An inverse matrix of $A$ is an $n \times n$ matrix $B$ with $AB = BA = I$ , where $I$ is the identity matrix. If it exists, it is unique (2.4), written $A^{-1}$ , and $A$ is called invertible (Apostol: nonsingular; a matrix with no inverse is singular). Since $(AB)x = A(Bx)$ , this says the map $x \mapsto Bx$ is the inverse of the map $x \mapsto Ax$ .

In one lineFor a square matrix $A$ , a matrix $B$ with $AB = BA = I$ . It is written $A^{-1}$ .

Why it existsIt undoes $A$ : $A^{-1}b$ is the solution of $Ax = b$ .

Apostol defines “nonsingular” with a left inverse only ( $BA = I$ ). The next theorem shows that for square matrices this is equivalent.

Theorem T Apostol Thm 2.20

A left inverse of a square matrix is a full inverse

Let $A, B$ be $n \times n$ matrices with $BA = I$ . Then $A$ is invertible and $B = A^{-1}$ .

In one lineIf $A$ and $B$ are $n \times n$ and $BA = I$ , then $AB = I$ too, so $B = A^{-1}$ .

Why it is true $BA = I$ forces the null space of $A$ to be zero, and for a map from $\mathbb R^n$ to itself that makes the map one-to-one and onto.

ProofApostol 2.19

The idea: Show that A is one-to-one, hence onto by dimension counting, hence invertible. Then identify B with the inverse.

x = Ix = (BA)x = B(Ax) = BO = O

. So

N(A) = \{O\}

Suppose

Ax = O

. Multiply by

B

on the left.

x \mapsto Ax

is one-to-one.

2.4, 'Equivalent forms of one-to-one for linear maps': a linear map is one-to-one exactly when its null space is only

O

The map is also onto, so it has an inverse map on all of

\mathbb R^n

. Let

C

be the matrix of that inverse, so

AC = CA = I

2.4, 'One-to-one in finite dimension': the range has dimension

n

, and a dimension-

n

subspace of

\mathbb R^n

is all of

\mathbb R^n

(2.2). Then 2.5, 'The matrix of an inverse is the inverse of the matrix', gives a matrix

C

with

AC = CA = I

B = BI = B(AC) = (BA)C = IC = C

Associativity of matrix multiplication (2.5), then

AC = I

and

BA = I

AB = I

as well, and

B = A^{-1}

C

is the inverse, so

AC = I

Proof workshopMatch each line of the left-inverse proof to its reason

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

Suppose $Ax = O$ . Then $x = Ix = (BA)x = B(Ax) = BO = O$ .
So $N(A) = \{O\}$ and $x \mapsto Ax$ is one-to-one.
The range has dimension $n$ , so it is all of $\mathbb R^n$ and the map is onto.
There is a matrix $C$ with $AC = CA = I$ .
$B = BI = B(AC) = (BA)C = IC = C$ .
So $AB = AC = I$ , and $B = A^{-1}$ .

The method for computing inverses needs a way to say “do a row operation” as a matrix.

Definition T

Elementary matrix

An elementary matrix is an $n \times n$ matrix obtained from $I$ by one row operation: swapping two rows, scaling a row by $c \ne 0$ , or adding $c$ times a row to another row.

In one lineThe matrix you get by doing one row operation to the identity matrix.

Why it existsMultiplying by an elementary matrix on the left does that row operation. So a whole row reduction is one matrix product.

For $n = 3$ : $\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}$ swaps rows 1 and 2; $\begin{bmatrix}1&0&0\\0&1&0\\0&0&c\end{bmatrix}$ scales row 3; $\begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}$ is " $R_2 \to R_2 - 3R_1$ " done to $I$ .

Theorem T Apostol 2.19 (implicit); Strang

Row operations are multiplication by elementary matrices

Let $E$ be the elementary matrix of a row operation. Then for every matrix $A$ with $n$ rows, $EA$ equals $A$ after that row operation. Also $E$ is invertible, and $E^{-1}$ is the elementary matrix of the opposite operation.

In one lineDoing a row operation to $A$ gives the same result as multiplying $A$ on the left by the elementary matrix of that operation. Elementary matrices are invertible, with elementary inverses.

Why it is trueRow $k$ of $EA$ is a combination of rows of $A$ with coefficients taken from row $k$ of $E$ , and an elementary $E$ has very simple rows.

ProofStrang 2.3

The idea: Compute the rows of EA, case by case. Then use that every row operation has an opposite.

Row

k

EA

is the combination of the rows of

A

whose coefficients are the entries of row

k

E

Matrix multiplication (2.5):

(EA)_{kj} = \sum_l E_{kl}A_{lj}

, so row

k

EA

\sum_l E_{kl}\cdot(\text{row } l \text{ of } A)

Swap: row

i

EA

is row

j

A

, row

j

EA

is row

i

A

, and the others are unchanged.

Rows of

E

for a swap of rows

i, j

: row

i

e_j

, row

j

e_i

, other rows

e_k

. Each picks out one row of

A

Scale: row

i

EA

c

times row

i

A

, and the others are unchanged.

Row

i

E

c\,e_i

, other rows

e_k

Add: row

j

EA

is (row

j

A

)

+ c

(row

i

A

), and the others are unchanged.

For

R_j \to R_j + cR_i

, row

j

E

e_j + c\,e_i

, other rows

e_k

E'E = I

. By the same reasoning with the roles swapped,

EE' = I

. So

E^{-1} = E'

Let

E'

be the elementary matrix of the opposite operation. Doing the operation and then its opposite returns any matrix to itself, so

E'(EA) = A

for all

A

. Take

A = I

Worked example

Find the elementary matrix E that does R₂ → R₂ − 3R₁ on a 3 by 3 matrix, and its inverse

Solution.

Apply the operation to $I$ . Row 2 of $I$ is $(0, 1, 0)$ ; subtract $3\times(1, 0, 0)$ to get $(-3, 1, 0)$ . So $E = \begin{bmatrix}1&0&0\\-3&1&0\\0&0&1\end{bmatrix}$ . By definition, $E$ is $I$ with the operation done to it.
Write the opposite operation. It is $R_2 \to R_2 + 3R_1$ , so $E^{-1} = \begin{bmatrix}1&0&0\\3&1&0\\0&0&1\end{bmatrix}$ . Adding $3R_1$ undoes subtracting $3R_1$ .
Check. $E^{-1}E$ : row 2 is $3(1,0,0) + (-3, 1, 0) = (0, 1, 0)$ , and the other rows are those of $I$ . So $E^{-1}E = I$ . Always confirm an inverse by multiplying.

Answer. $E$ and $E^{-1}$ as above.

Theorem T Apostol 2.19 and 2.20; Spagnolie Lecture 13 page 5

Computing the inverse by row reducing [A | I]

Let $A$ be $n \times n$ and let $[R \mid B]$ be the RREF of $[A \mid I]$ . If $R = I$ , then $A$ is invertible and $B = A^{-1}$ . If $R \ne I$ , then $A$ is not invertible.

In one lineRow reduce $[A \mid I]$ . If the left block becomes $I$ , the right block is $A^{-1}$ . If the left block cannot become $I$ , $A$ has no inverse.

Why it is trueRow reducing with $A$ on the left solves $Ab_j = e_j$ for every column $b_j$ of the inverse at once.

ProofApostol 2.19; Spagnolie Lecture 13

The idea: Row operations are left multiplication by one matrix P. It turns A into R and I into P. If R = I then P is a left inverse of A.

The whole reduction multiplies

[A \mid I]

on the left by one matrix

P = E_k\cdots E_1

[PA \mid PI] = [R \mid B]

. So

R = PA

and

B = P

Each operation is left multiplication by an elementary matrix (previous theorem); do them one after another and multiply the matrices together.

R = I

, then

BA = I

Substitute

R = I

and

B = P

A

is invertible and

B = A^{-1}

Theorem: a left inverse of a square matrix is the inverse.

R \ne I

, then

R

has fewer than

n

pivots, so at least one free variable.

n \times n

RREF with

n

pivots has a pivot in every row and column, hence a 1 on each diagonal position and zeros elsewhere: it is

I

. So

R \ne I

means fewer than

n

pivots.

N(A) \ne \{O\}

, so

x \mapsto Ax

is not one-to-one, so

A

is not invertible.

Free variable means

N(R) \ne \{O\}

, and

N(A) = N(R)

by the row-operations theorem.

Why does this work, in words? Write $A^{-1}$ column by column as $[b_1 \mid \dots \mid b_n]$ . The equation $AA^{-1} = I$ says $Ab_j = e_j$ for each $j$ : $n$ systems with the same coefficient matrix $A$ and different right sides. Row operations on $[A \mid e_1 \mid \dots \mid e_n]$ solve all $n$ at once, as Spagnolie said. Applying the same row operations to $I$ is the bookkeeping of what the operations did.

Worked example method of Apostol 2.19 and 2.20 #15

Find the inverse of A with rows (1, 2, 3), (0, 1, 4), (5, 6, 0)

Solution.

Form $[A \mid I]$ . Put the $3\times3$ identity to the right of $A$ . The right block will record what the row operations do to $I$ .
Reduce to echelon form. Subtract $5R_1$ from $R_3$ , then add $4R_2$ to $R_3$ . The left block becomes upper triangular with three pivots, each 1. Three pivots means $A$ is invertible.
Clear above the pivots and finish. Use $R_3$ to clear column 3, then $R_2$ to clear column 2. That turns the left block into $I$ without needing any scaling.
Read $A^{-1}$ from the right block, then check.

Check one entry of $AA^{-1}$ : row 3 of $A$ times column 1 of $A^{-1}$ is $5(-24) + 6(20) + 0(-5) = 0$ , and row 3 times column 3 is $5(5) + 6(-4) + 0 = 1$ .

Answer. $A^{-1} = \begin{bmatrix}-24&18&5\\20&-15&-4\\-5&4&1\end{bmatrix}$ .

Your answerRow reduce

[A \mid I]

for

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

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

A^{-1}

For a $2 \times 2$ matrix the same reduction in letters gives the formula you may know from JEE. Reduce $\left[\begin{array}{cc|cc}a&b&1&0\\c&d&0&1\end{array}\right]$ (assume $a \ne 0$ ): subtract $\tfrac ca R_1$ from $R_2$ to get the second pivot $d - \tfrac{bc}{a} = \tfrac{ad - bc}{a}$ . The matrix has two pivots, and so is invertible, exactly when $ad - bc \ne 0$ . Finishing the reduction gives

A^{-1} = \frac{1}{ad - bc}\begin{bmatrix}d & -b\\ -c & a\end{bmatrix}.

(A problem below does all cases.) The number $ad - bc$ is the $2\times2$ determinant of chapter 2.7.

A non-example: $A = \begin{bmatrix}1&2\\2&4\end{bmatrix}$ . Reduce $[A \mid I]$ : $R_2 \to R_2 - 2R_1$ gives $\left[\begin{array}{cc|cc}1&2&1&0\\0&0&-2&1\end{array}\right]$ . The left block has a zero row and cannot become $I$ . So $A$ has no inverse. Indeed its second column is twice its first, so $A(2, -1) = O$ .

The invertible matrix theorem

We now have many ways to say the same thing about a square matrix. This list is called the invertible matrix theorem (a name from later courses; Apostol and Spagnolie never list it as one theorem).

Theorem B assembled from Apostol 2.17 to 2.20 and Spagnolie Lectures 11 to 13

Invertible matrix theorem

For an $n \times n$ matrix $A$ with $T(x) = Ax$ , the following are equivalent:

$A$ is invertible.
$T$ is one-to-one.
$N(A) = \{O\}$ : the only solution of $Ax = O$ is $x = O$ .
The columns of $A$ are linearly independent.
$\operatorname{rank}A = n$ .
The columns of $A$ span $\mathbb R^n$ (the column space is $\mathbb R^n$ ).
$T$ is onto.
$Ax = b$ has exactly one solution for every $b \in \mathbb R^n$ .
$A$ has $n$ pivots (no free variables), and its RREF is $I$ .
$A$ is a product of elementary matrices.
$A^{\mathsf T}$ is invertible. (So the rows are independent and span too.)

Chapter 2.7 adds one more: $\det A \ne 0$ .

In one lineFor an $n \times n$ matrix $A$ , eleven conditions are equivalent: invertible, one-to-one, null space zero, independent columns, rank $n$ , columns span $\mathbb R^n$ , onto, a unique solution for every $b$ , $n$ pivots, product of elementary matrices, invertible transpose.

Why it is trueA square matrix has as many unknowns as equations, so losing nothing (null space zero) and reaching everything (onto) are the same, by rank–nullity.

ProofApostol 2.19 and 2.20; Spagnolie Lecture 13 page 5

The idea: Link the conditions in a loop of implications, each one a result you already have.

(1)

\Rightarrow

(2) and (1)

\Rightarrow

(7).

Let

B

be the inverse matrix, so

BA = AB = I

. If

Ax = Ay

, multiply by

B

on the left:

x = BAx = BAy = y

. For onto, any

b

equals

A(Bb)

(2) and (7) together are the same as (8).

'Exactly one solution for every

b

' is 'at least one solution for every

b

' (onto) together with 'at most one' (one-to-one, since two solutions of

Ax = b

differ by a null vector).

(2)

\Leftrightarrow

(3).

Ax = Ay

then

A(x - y) = O

, so

x - y \in N(A)

. Conversely

O

and

x

would both map to

O

x \in N(A)

non-zero.

(3)

\Leftrightarrow

(4).

Ax = \sum x_j a_j

. 'Only trivial combination of the columns is

O

' is the definition of linear independence.

(3)

\Leftrightarrow

(5).

Rank–nullity:

n = \operatorname{rank} + \operatorname{nullity}

, so nullity 0 means rank

n

(5)

\Leftrightarrow

(6)

\Leftrightarrow

(7).

The range is the column space, a subspace of

\mathbb R^n

. A subspace of dimension

n

\mathbb R^n

is all of

\mathbb R^n

(2.2).

(2) and (7) together give (1). With the steps above, every one of (1) to (8) now implies every other.

(3) gives (2) and (5) gives (7), so

T

is one-to-one and onto. Then 2.5, 'The matrix of an inverse is the inverse of the matrix', and 2.4 give a two-sided inverse map, whose matrix

B

has

AB = BA = I

(3)

\Leftrightarrow

(9).

Rank–nullity theorem read off the staircase: nullity is the number of free variables. No free variables with

n

columns means

n

pivots, and

n

pivots in an

n\times n

RREF force

I

(9)

\Rightarrow

(10).

If the RREF is

I

, the operations multiply

A

I

, so

E_k \cdots E_1 A = I

and

A = E_1^{-1}\cdots E_k^{-1}

, a product of elementary matrices.

(10)

\Rightarrow

(1).

Elementary matrices are invertible, and a product of invertible matrices is invertible with inverse the product of inverses in reverse order.

(1)

\Leftrightarrow

(11).

Row rank equals column rank (theorem above), so

\operatorname{rank}A^{\mathsf T} = \operatorname{rank}A

, and (5) for

A

is (5) for

A^{\mathsf T}

In the picture. “Shear” in the viewer is an invertible matrix: no direction is squashed (null space zero), every point is reached (onto), and “Undo the map” is the inverse. “Squash to a line” fails every condition on the list at once.

Quick checkA

4 \times 4

matrix has rank 3. Which statement is true?

Worked example Apostol 2.21 #2(e); MATH 375 HW7

Let A be a square matrix with A³ = O. Show that A − I is invertible

Solution.

Choose the cheapest equivalent condition. To show $A - I$ is invertible, it is enough to show its null space is $\{O\}$ . Condition 3 of the invertible matrix theorem: for a square matrix, trivial null space already means invertible.
Take an arbitrary vector in the null space. Let $(A - I)x = O$ . Then $Ax = x$ . Rewrite the equation so that $A$ acts on $x$ and gives $x$ back.
Apply $A$ again and again. $A^2x = A(Ax) = Ax = x$ , and then $A^3x = x$ . Each time $A$ hits $x$ it returns $x$ .
Use the hypothesis. $A^3x = Ox = O$ , so $x = O$ . We found two values for $A^3x$ , namely $x$ and $O$ , so they are equal.
Conclude. $N(A - I) = \{O\}$ , so $A - I$ is invertible.

Answer. Yes. (Alternatively, $(A - I)(A^2 + A + I) = A^3 - I = -I$ shows the inverse is $-(A^2 + A + I)$ .)

Worked example new, JEE style (compare Apostol 2.20 #8)

Find all values of a and b for which x + y + z = 6, x + 2y + 3z = 10, x + 2y + az = b has no solution, exactly one, or infinitely many

Solution.

Eliminate. Subtract $R_1$ from $R_2$ and from $R_3$ : $y + 2z = 4$ and $y + (a - 1)z = b - 6$ . Then subtract the new $R_2$ from $R_3$ . Clear column 1 below the pivot, then column 2.
Look at the last row. It is $(a - 3)z = b - 10$ . This is the only row where $a$ and $b$ matter, so it decides everything.
Case $a \ne 3$ . Then $z = \tfrac{b - 10}{a - 3}$ , and $y, x$ follow. Three pivots: exactly one solution for every $b$ . Condition 9 of the theorem: the matrix is invertible, so every $b$ gives a unique solution.
Case $a = 3$ , $b = 10$ . The last row is $0 = 0$ . Two pivots, $z$ free: $y = 4 - 2z$ , $x = 6 - y - z = 2 + z$ . The solutions are $(2, 4, 0) + t(1, -2, 1)$ . Consistent with a free variable gives a line of solutions.
Case $a = 3$ , $b \ne 10$ . The last row is $0 = b - 10 \ne 0$ . A pivot in the last column: no solution.

Answer. Unique solution if $a \ne 3$ . Infinitely many if $a = 3$ and $b = 10$ . None if $a = 3$ and $b \ne 10$ .

Your answerFor the system

x + 2y = 3

2x + ay = 7

, there is NOT exactly one solution for exactly one value of

a

. Which value?

Beyond: remembering the row operations (LU)

Beyond the course: for understanding· LU decomposition, the form that numerical libraries store

Write down, as you eliminate, the multiplier used in each step “subtract $\ell_{ij}\times$ row $j$ from row $i$ ”. In the Lecture 12 example, $A = \begin{bmatrix}2&1&1\\4&-6&0\\-2&7&2\end{bmatrix}$ , the multipliers were $\ell_{21} = 2$ , $\ell_{31} = -1$ (adding $R_1$ is subtracting $-1\cdot R_1$ ) and $\ell_{32} = -1$ . The echelon form was $U = \begin{bmatrix}2&1&1\\0&-8&-2\\0&0&1\end{bmatrix}$ . Put the multipliers into a lower triangular matrix $L$ with ones on the diagonal:

A = LU, \qquad L = \begin{bmatrix}1&0&0\\2&1&0\\-1&-1&1\end{bmatrix},\ U = \begin{bmatrix}2&1&1\\0&-8&-2\\0&0&1\end{bmatrix}.

Check the first column of $LU$ : it is $2$ times the first column of $L$ (because the first column of $U$ is $(2, 0, 0)$ ), which is $(2, 4, -2)$ , the first column of $A$ . The reason it works: each step is multiplication by an elementary matrix, $E_3E_2E_1A = U$ , so $A = E_1^{-1}E_2^{-1}E_3^{-1}U$ , and the product of the inverses is lower triangular and has the multipliers as its entries. Solving $Ax = b$ becomes two cheap triangular solves, $Ly = b$ then $Ux = y$ . The costly part (about $n^3/3$ steps) is done once; every new $b$ costs only about $n^2$ . If a zero pivot forces a row swap, the factorization becomes $PA = LU$ with a permutation matrix $P$ . This is CS 532 material.

Examples and non-examples

The worked examples above cover each kind of question: deciding solvability by columns, a unique solution, infinitely many, none, a parameter family, bases for the four subspaces, an inverse, and a proof using the null space. Here are two further reminders of what elimination does not allow.

Not a row operation: multiplying a row by zero. Replacing $R_2$ by $0\cdot R_2$ turns the equation $x + y = 3$ into $0 = 0$ . That loses information, and the undoing step would need to divide by zero. This is why the scale operation requires $c \ne 0$ .

Not allowed: swapping columns without relabelling. Swapping two columns of $A$ swaps two unknowns. Lecture 12 marks this in the margin with “not reordered!” next to the unknowns. You may reorder the equations (rows) freely. Reordering the columns changes what each unknown means, so you must carry the relabelling along.

A singular square system. $x + 2y = 3$ , $2x + 4y = 6$ has 2 equations and 2 unknowns, yet infinitely many solutions $(3, 0) + t(-2, 1)$ . A square shape does not guarantee a unique solution. Only rank $n$ does.

Where it is used

Used inside maths· Inside maths: every find-the-coefficients problem is a system

Fitting a polynomial through points is a linear system in the coefficients. To find the quadratic $p(x) = c_0 + c_1x + c_2x^2$ through $(1, 2)$ , $(2, 3)$ , $(4, 9)$ , write $p(1) = c_0 + c_1 + c_2 = 2$ , $p(2) = c_0 + 2c_1 + 4c_2 = 3$ and $p(4) = c_0 + 4c_1 + 16c_2 = 9$ . Subtracting row 1 from row 2 and row 2 from row 3 gives $c_1 + 3c_2 = 1$ and $2c_1 + 12c_2 = 6$ , so $c_1 + 6c_2 = 3$ , hence $3c_2 = 2$ , $c_2 = \tfrac23$ , $c_1 = -1$ , $c_0 = \tfrac73$ . So $p(x) = \tfrac13(7 - 3x + 2x^2)$ . Check: $p(1) = \tfrac{6}{3} = 2$ , $p(2) = \tfrac{9}{3} = 3$ , $p(4) = \tfrac{27}{3} = 9$ . The solution is unique because the three columns $(1,1,1)$ , $(1,2,4)$ , $(1,4,16)$ are independent, which chapter 2.7 will prove with a determinant (Vandermonde). The same method decides whether a vector is in a span, whether vectors are independent, and finds null space bases: all the stepper exercises of chapter 2.2 were small linear systems.

Used in the real world· Circuits: Kirchhoff's laws are a linear system

A 12 V battery drives a current $I_1$ through a $2\,\Omega$ resistor. The wire then splits: $I_2$ flows through a $3\,\Omega$ resistor and $I_3$ through a $6\,\Omega$ resistor, and the branches rejoin. Kirchhoff’s current law (what flows into a junction flows out) gives $I_1 - I_2 - I_3 = 0$ . His voltage law (the drops around a loop add up to the battery voltage, with Ohm’s law “drop = resistance times current”) gives $2I_1 + 3I_2 = 12$ for the loop through the $3\,\Omega$ branch and $2I_1 + 6I_3 = 12$ for the loop through the $6\,\Omega$ branch. In matrix form

\begin{bmatrix}1&-1&-1\\2&3&0\\2&0&6\end{bmatrix}\begin{bmatrix}I_1\\I_2\\I_3\end{bmatrix} = \begin{bmatrix}0\\12\\12\end{bmatrix}.

Elimination ( $R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 - 2R_1$ , then clearing) gives $I_1 = 3$ A, $I_2 = 2$ A, $I_3 = 1$ A. Check: $3 = 2 + 1$ , $6 + 6 = 12$ , $6 + 6 = 12$ . A third loop equation, around the two resistors only, is $3I_2 - 6I_3 = 0$ , which is true ( $6 - 6$ ) and is just the difference of the other two loop equations. With four equations and three unknowns, the rank is still 3. Circuit simulators such as SPICE do this with a million nodes by exploiting that almost all entries of the matrix are zero.

Used in the real world· Chemistry: balancing an equation is finding a null vector

Burn propane: $a\,\mathrm{C_3H_8} + b\,\mathrm{O_2} \to c\,\mathrm{CO_2} + d\,\mathrm{H_2O}$ . Atoms must balance: carbon $3a = c$ , hydrogen $8a = 2d$ , oxygen $2b = 2c + d$ . Moving everything to one side gives a homogeneous system with matrix (rows C, H, O; columns $a, b, c, d$ )

\begin{bmatrix}3&0&-1&0\\8&0&0&-2\\0&2&-2&-1\end{bmatrix}\begin{bmatrix}a\\b\\c\\d\end{bmatrix} = O.

Rank 3 with 4 unknowns, so the nullity is 1: the solutions are the multiples of one vector, which is why a balanced equation is unique up to scaling. Solving: $c = 3a$ , $d = 4a$ , $2b = 6a + 4a$ , so $b = 5a$ . The null vector is $(1, 5, 3, 4)$ and the balanced equation is $\mathrm{C_3H_8} + 5\mathrm{O_2} \to 3\mathrm{CO_2} + 4\mathrm{H_2O}$ . Check oxygen: $10 = 6 + 4$ . Rust works the same way: $a\,\mathrm{Fe} + b\,\mathrm{O_2} \to c\,\mathrm{Fe_2O_3}$ gives $a = 2c$ , $2b = 3c$ , null vector $(4, 3, 2)$ , i.e. $4\mathrm{Fe} + 3\mathrm{O_2} \to 2\mathrm{Fe_2O_3}$ . If the nullity were 2 there would be two independent ways to balance it, which signals a reaction that is really two reactions combined.

Used in the real world· Traffic and pipe networks: conservation at every junction

Four one-way roads form a ring: $x_1$ cars per hour from A to B, $x_2$ from B to C, $x_3$ from C to D, $x_4$ from D to A. From outside, 60 cars/h enter at A and 30 at C, and 40 leave at B and 50 at D. At each junction, cars in equal cars out: A: $60 + x_4 = x_1$ , B: $x_1 = x_2 + 40$ , C: $x_2 + 30 = x_3$ , D: $x_3 = x_4 + 50$ . Row reduction gives rank 3 with one free variable $x_4 = t$ :

(x_1, x_2, x_3, x_4) = (60, 20, 50, 0) + t\,(1, 1, 1, 1).

Check C: $x_2 + 30 = 50 + t = x_3$ . The null vector $(1, 1, 1, 1)$ is a traffic jam circulating round the ring: it adds $t$ cars/h on every road and changes nothing at any junction. Traffic engineers need the free variable, because the network alone cannot say how many cars loop. The system is solvable only because the total entering, $60 + 30 = 90$ , equals the total leaving, $40 + 50 = 90$ . If 100 left instead, $b$ would not be in the column space and there would be no solution. A problem below proves this using the left null space.

Used in the real world· GPS: three distances give a linear system

A phone at an unknown point $(x, y)$ measures its distance to three towers: $5$ from $(5, 5)$ , $13$ from $(7, 13)$ and $10$ from $(10, 7)$ . Each distance gives a quadratic equation, for example $(x - 5)^2 + (y - 5)^2 = 25$ . The trick is to subtract equations: the $x^2 + y^2$ terms cancel and what remains is linear. Equation 2 minus equation 1 gives $-4x - 16y = -24$ , i.e. $x + 4y = 6$ . Equation 3 minus equation 1 gives $-10x - 4y = -24$ , i.e. $5x + 2y = 12$ . Eliminate: from the first, $x = 6 - 4y$ ; then $30 - 20y + 2y = 12$ gives $y = 1$ and $x = 2$ . Check in equation 1: $9 + 16 = 25$ . Real GPS works in 3D with satellites, and a fourth satellite fixes the unknown error of the phone’s clock. The distance equations are not linear, so the receiver linearizes them around a guess and solves a linear system, again and again, each time with a slightly better guess. The linear systems have more equations than unknowns and are solved by least squares (chapter 2.10).

Beyond the course: for understanding· Why computers avoid the inverse, and what a nearly singular matrix does

Spagnolie’s “computational horror story” (Lecture 13): $A = \begin{bmatrix}1&1\\1&1.0001\end{bmatrix}$ . Then $Ax = (2, 2)$ has solution $(2, 0)$ , but $Ax = (2, 2.0001)$ has solution $(1, 1)$ . A change of one part in $20{,}000$ in the data moves the answer by an amount of order 1. The two columns are almost parallel, so the matrix is almost singular, and tiny rounding errors get magnified. Such a matrix is called ill-conditioned. This is why libraries solve $Ax = b$ by LU with row swaps (partial pivoting) rather than by computing $A^{-1}$ and multiplying, which costs more and is less accurate.

Traps

Watch out· Row operations move the column space

Row operations keep the null space, the row space and the dependences among the columns. They do not keep the column space (Lecture 13: $\begin{bmatrix}1&1&0\\1&1&0\end{bmatrix}$ versus $\begin{bmatrix}1&1&0\\0&0&0\end{bmatrix}$ ). So a basis of the column space is the pivot columns of the ORIGINAL $A$ . Midterm 2 (Fall 2025), Problem 2(b), asks for a basis of the range of a map, and the correct answer takes columns 1 and 4 of the matrix itself, then translates back to polynomials. When you solve $Ax = c$ by operating on $A$ , you must also apply every operation to $c$ .

Watch out· [0 0 0 | 0] is harmless, [0 0 0 | c] is fatal

A zero row in the augmented matrix with a zero on the right means a redundant equation. A zero row with a non-zero number on the right is $0 = c$ , so there is no solution. The only difference is the last entry.

Watch out· Reorder equations, never unknowns

Swapping rows is free. Swapping columns renames the unknowns. If you swap columns to get a nicer pivot, keep a note of which unknown each column now belongs to, or just don’t.

Watch out· A sign slip in the printed Lecture 12 notes, and the habit that catches it

In the four-unknown example, the notes give the null vector $(-\tfrac12, -1, 0, 1)$ . The correct vector is $(\tfrac12, -1, 0, 1)$ . The slip happens when solving $x = \tfrac14 - \tfrac12(2 + z - u) - \tfrac14 z$ : the $u$ term carries a plus sign. Multiply the proposed null vector by $A$ . The row $(4, 2, 1, 0)$ applied to the wrong vector gives $-4$ , not $0$ . Spagnolie’s own advice, scribbled in Lecture 13, is “always check”.

Watch out· Shape does not decide the number of solutions

A square system can have none or infinitely many solutions (the example $x + 2y = 3$ , $2x + 4y = 6$ ). A system with more equations than unknowns can have one solution (when the extra equations are consequences of the others). Only the rank, counted by pivots, decides. Lecture 12 notes that “this can certainly happen with square matrices as well”.

Watch out· One solution for one b does not make a non-square matrix invertible

For the $3 \times 2$ matrix with rows $(1, 0), (0, 1), (0, 0)$ , the system $Ax = (1, 2, 0)$ has exactly one solution, but only some right sides are reachable and $A$ has no inverse. Invertibility belongs to square matrices, and for those, one solution for any single $b$ gives $N(A) = \{O\}$ and hence invertibility.

Problems

check

The reduced form of an augmented matrix is $\left[\begin{array}{ccc|c}1&0&2&3\\0&1&-1&4\\0&0&0&0\end{array}\right]$ . Which columns are pivot columns, which unknown is free, and what is the general solution?

Solution

Pivots are in columns 1 and 2, so $x_3$ is free. Row 1 gives $x_1 = 3 - 2x_3$ and row 2 gives $x_2 = 4 + x_3$ . Putting $x_3 = t$ , the solution is $(3, 4, 0) + t(-2, 1, 1)$ .

check

A $5 \times 7$ matrix has 3 pivots. State the dimensions of its column space, row space, null space and left null space.

Solution

Column space 3, row space 3, null space $7 - 3 = 4$ , left null space $5 - 3 = 2$ .

check

Write the $3 \times 3$ elementary matrix for $R_1 \leftrightarrow R_3$ . What is its inverse?

Solution

It is $I$ with rows 1 and 3 swapped: $\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}$ . Swapping again undoes the swap, so it is its own inverse.

check

True or false: if $Ax = b$ has exactly one solution for some $b$ , then $A$ is invertible. Consider (a) $A$ square, (b) $A$ not square.

Solution

(a) True. If $x$ is the only solution, then $N(A) = \{O\}$ , since a non-zero $y \in N(A)$ would give a second solution $x + y$ . By the invertible matrix theorem a square matrix with trivial null space is invertible. (b) False for the $3 \times 2$ matrix with rows $(1,0), (0,1), (0,0)$ : the system $Ax = (1, 2, 0)$ has the single solution $(1, 2)$ , but non-square matrices have no inverse.

useApostol 2.20 #1

Solve $x + y + 3z = 5$ , $2x - y + 4z = 11$ , $-y + z = 3$ by Gauss–Jordan elimination.

Solution

Augmented matrix $\left[\begin{array}{ccc|c}1&1&3&5\\2&-1&4&11\\0&-1&1&3\end{array}\right]$ . $R_2 \to R_2 - 2R_1$ gives row 2 as $(0, -3, -2 \mid 1)$ . $R_2 \to R_2 - 3R_3$ gives $(0, 0, -5 \mid -8)$ , so $z = \tfrac85$ . Row 3 gives $y = z - 3 = -\tfrac75$ . Row 1 gives $x = 5 - y - 3z = 5 + \tfrac75 - \tfrac{24}5 = \tfrac85$ . Check: $\tfrac85 - \tfrac75 + \tfrac{24}5 = 5$ ; $\tfrac{16}5 + \tfrac75 + \tfrac{32}5 = 11$ ; $\tfrac75 + \tfrac85 = 3$ . The solution is $(\tfrac85, -\tfrac75, \tfrac85)$ .

useApostol 2.20 #8

Find all solutions of $x - 2y + z + 2u = -2$ , $2x + 3y - z - 5u = 9$ , $4x - y + z - u = 5$ , $5x - 3y + 2z + u = 3$ . Give a particular solution and a basis of the null space.

Solution

$R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 - 4R_1$ , $R_4 \to R_4 - 5R_1$ give three identical rows $(0, 7, -3, -9 \mid 13)$ . Subtracting the first of them from the other two leaves two zero rows, so the rank is 2 and $z, u$ are free. From $7y - 3z - 9u = 13$ : $y = \tfrac{13}{7} + \tfrac37 z + \tfrac97 u$ . From row 1: $x = -2 + 2y - z - 2u = \tfrac{12}7 - \tfrac17 z + \tfrac47 u$ . With $z = a$ , $u = b$ the solutions are

\left(\tfrac{12}7, \tfrac{13}7, 0, 0\right) + a\left(-\tfrac17, \tfrac37, 1, 0\right) + b\left(\tfrac47, \tfrac97, 0, 1\right).

The two vectors multiplying $a, b$ are a basis of $N(A)$ . Check the first: row 1 gives $-\tfrac17 - \tfrac67 + 1 = 0$ , row 2 gives $-\tfrac27 + \tfrac97 - 1 = 0$ .

useApostol 2.20 #15

Find the inverse of $A = \begin{bmatrix}1&2&3&4\\0&1&2&3\\0&0&1&2\\0&0&0&1\end{bmatrix}$ .

Solution

Row reduce $[A \mid I]$ . The matrix is already upper triangular with 1s on the diagonal, so only clearing above the pivots remains. Use the bottom pivot first: $R_3 \to R_3 - 2R_4$ , then $R_2 \to R_2 - 3R_4 - 2R_3$ (using the new $R_3$ ), then $R_1 \to R_1 - 4R_4 - 3R_3 - 2R_2$ (using the new $R_3$ and $R_2$ ). Each is a sum of single add-a-multiple operations. The result is

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

Check the (1,3) entry of $AA^{-1}$ : $1\cdot1 + 2(-2) + 3(1) + 4(0) = 0$ , and the (1,4) entry: $0 + 2 - 6 + 4 = 0$ . Check (1,2): $-2 + 2 = 0$ .

useMidterm 2 (2013 practice) Q1(b), (c)

Let $A = \begin{bmatrix}1&2&0\\2&0&2\\3&2&2\end{bmatrix}$ and $b = (3, 2, 5)$ . Find a basis of the null space and all solutions of $Ax = b$ . Then change one entry of $b$ so that there is no solution, and explain.

Solution

Row 3 equals row 1 plus row 2, so the rank is 2 and there is one free variable. Solving $Ay = O$ : the first two rows give $y_1 + 2y_2 = 0$ and $2y_1 + 2y_3 = 0$ , so $y = t(2, -1, -2)$ . Check: row 3 gives $6 - 2 - 4 = 0$ . A basis of $N(A)$ is $\{(2, -1, -2)\}$ . Since $b_3 = 5 = 3 + 2 = b_1 + b_2$ , the system is consistent. A particular solution is $(1, 1, 0)$ : $1 + 2 = 3$ , $2 + 0 = 2$ , $3 + 2 = 5$ . All solutions: $(1, 1, 0) + t(2, -1, -2)$ . For no solution take $b = (3, 2, 6)$ . Row 3 $=$ row 1 $+$ row 2 forces $b_3 = b_1 + b_2 = 5$ for any solution, so $6$ is impossible. The vector $(3, 2, 6)$ is not in the column space.

usenew, JEE style

For which real $k$ does the homogeneous system $x + y + z = 0$ , $x + 2y + 3z = 0$ , $x + 2y + kz = 0$ have a non-zero solution? Find it.

Solution

Subtract $R_1$ from $R_2$ and $R_3$ , then subtract the new $R_2$ from the new $R_3$ : the last equation becomes $(k - 3)z = 0$ . If $k \ne 3$ , then $z = 0$ , then $y = 0$ and $x = 0$ : only the zero solution. If $k = 3$ , then $z$ is free: $y = -2z$ , $x = -y - z = z$ . The non-zero solutions are $t(1, -2, 1)$ . Check: $1 - 2 + 1 = 0$ , $1 - 4 + 3 = 0$ .

proveApostol 2.20 #11

Prove that $A = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ is invertible if and only if $ad - bc \ne 0$ , and that then $A^{-1} = \frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ .

Solution

Multiply directly: $\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}d&-b\\-c&a\end{bmatrix} = \begin{bmatrix}ad-bc & -ab+ba\\ cd-dc & -cb+da\end{bmatrix} = (ad-bc)I$ . The product in the other order is also $(ad - bc)I$ by the same computation. So if $ad - bc \ne 0$ , dividing by it shows that the stated matrix is a two-sided inverse.

Now suppose $ad - bc = 0$ ; we show $A$ is not invertible. Let $y = (d, -c)$ and $z = (-b, a)$ , the two columns of the matrix above. The product above says $Ay = (ad - bc, 0) = O$ and $Az = O$ . If $y$ and $z$ were both zero, then $a = b = c = d = 0$ and $A = O$ , which has $N(A)$ equal to the whole plane. So in every case at least one of $y, z$ is a non-zero vector of $N(A)$ , hence $N(A) \ne \{O\}$ , and by the invertible matrix theorem $A$ is not invertible.

prove

Prove that if $A$ is an $m \times n$ matrix with $m < n$ , then $Ax = O$ has a non-zero solution.

Solution

The range of $x \mapsto Ax$ is inside $\mathbb R^m$ , so the rank is at most $m$ . By rank–nullity, the nullity is $n - \operatorname{rank} \ge n - m > 0$ . So $N(A)$ contains a non-zero vector. (Equivalently: there are at most $m$ pivots but $n > m$ columns, so some column has no pivot and gives a free variable.)

prove

Prove that $\operatorname{rank}(AB) \le \operatorname{rank}A$ and $\operatorname{rank}(AB) \le \operatorname{rank}B$ , for matrices where $AB$ is defined.

Solution

Range of $AB$ : every $ABx = A(Bx)$ is of the form $Ay$ , so the range of $AB$ is inside the range of $A$ . A subspace inside another has dimension at most that of the other (a basis of the smaller is independent in the larger, and independent sets have size at most the dimension). So $\operatorname{rank}AB \le \operatorname{rank}A$ .

For $B$ : let $w_1, \dots, w_s$ be a basis of the range of $B$ , so $s = \operatorname{rank}B$ . Every vector in the range of $AB$ is $A(Bx)$ with $Bx = \sum c_iw_i$ , so equals $\sum c_i\,A w_i$ . Thus the $s$ vectors $Aw_1, \dots, Aw_s$ span the range of $AB$ , and a spanning set of $s$ vectors forces dimension at most $s$ (2.2). So $\operatorname{rank}AB \le \operatorname{rank}B$ .

proveApostol 2.21 #2(c) and (f), adapted

Let $A$ and $B$ be $n \times n$ . Prove: if $A$ and $B$ are invertible then $AB$ is invertible with inverse $B^{-1}A^{-1}$ . Prove the converse in this form: if $AB$ is invertible, then $A$ and $B$ are both invertible.

Solution

First part: $(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AA^{-1} = I$ , using associativity. By the theorem that a one-sided inverse of a square matrix is a full inverse, $B^{-1}A^{-1} = (AB)^{-1}$ .

Converse: argue with null spaces. If $Bx = O$ then $(AB)x = A(Bx) = O$ , and $AB$ is invertible so its null space is $\{O\}$ , giving $x = O$ . So $N(B) = \{O\}$ and $B$ is invertible by the invertible matrix theorem. Then $A = (AB)B^{-1}$ is a product of two invertible matrices, hence invertible by the first part.

stretch

Consider the traffic ring in the chapter, with external flows in at A and C, and out at B and D. Using only the equations at the four junctions, prove that if the numbers entering and leaving are $(p_A, p_C)$ in and $(q_B, q_D)$ out, a solution can exist only when $p_A + p_C = q_B + q_D$ . Which vector in the left null space of the coefficient matrix does your argument use?

Solution

The equations are A: $x_1 - x_4 = p_A$ , B: $x_1 - x_2 = q_B$ , C: $x_2 - x_3 = -p_C$ , D: $x_3 - x_4 = q_D$ . Form the combination A $-$ B $-$ C $-$ D, which is the row combination with coefficients $y = (1, -1, -1, -1)$ . On the left side the coefficient of $x_1$ is $1 - 1 = 0$ , of $x_2$ is $+1 - 1 = 0$ , of $x_3$ is $+1 - 1 = 0$ , and of $x_4$ is $-1 + 1 = 0$ . So the left side vanishes identically, and the right side must vanish too: $p_A - q_B + p_C - q_D = 0$ . This is the stated condition. The vector $y = (1, -1, -1, -1)$ satisfies $y^{\mathsf T}A = O$ , so it is in the left null space, and any solvable right side $b$ must satisfy $y^{\mathsf T}b = 0$ . (That this single condition is also enough here is what the rank 3 computation shows. The general statement, that $b$ is in the column space exactly when $y^{\mathsf T}b = 0$ for every $y$ in the left null space, can be proved with the perpendicularity of chapter 2.9.)

stretch

Let $A$ be an $m \times n$ matrix of rank $r$ . Prove that $A$ has an $r \times r$ submatrix (choose $r$ rows and $r$ columns and keep the entries where they cross) that is invertible.

Solution

Let $P$ be the $m \times r$ matrix formed by the $r$ pivot columns of $A$ . Its columns are independent (the rank theorem), so $\operatorname{rank}P = r$ . By the theorem that row rank equals column rank, the row space of $P$ has dimension $r$ . The $m$ rows of $P$ span the row space, and a spanning set contains a basis (2.2), so we can choose $r$ rows of $P$ that are independent. Let $Q$ be the $r \times r$ matrix of those rows. Its rows are independent, so its row space is $r$ -dimensional, hence its column space is $r$ -dimensional by the same theorem, and $\operatorname{rank}Q = r$ . By the invertible matrix theorem $Q$ is invertible. $Q$ consists of the entries of $A$ in the chosen $r$ rows and the $r$ pivot columns, so it is the required submatrix.

Summary

$Ax = b$ asks whether $b$ is in the range of $x \mapsto Ax$ . The range is the column space, spanned by the columns, because $Ax = x_1a_1 + \dots + x_na_n$ .
The solution set is empty, or one particular solution plus the null space. So there are $0$ , $1$ or infinitely many solutions, never exactly two.
The three row operations (swap, scale by non-zero, add a multiple) never change the solutions, because each is undone by another. Elimination uses them to reach echelon form and then reduced row echelon form.
Pivots are the staircase corners. Pivot columns of the original $A$ are a basis of the column space. Free variables, one per non-pivot column, give a basis of the null space. So rank $=$ number of pivots, and nullity $=$ number of free variables.
Four fundamental subspaces: column space and row space have dimension $r$ , null space $n - r$ , left null space $m - r$ . In particular rank $A$ = rank $A^{\mathsf T}$ .
Row reducing $[A \mid I]$ to $[I \mid A^{-1}]$ computes the inverse, because row operations are left multiplication by elementary matrices. If the left block cannot reach $I$ , $A$ is not invertible.
For a square matrix, invertible, one-to-one, onto, trivial null space, independent columns, rank $n$ , $n$ pivots, and unique solutions are all the same statement. Chapter 2.7 adds $\det A \ne 0$ .
Real systems (circuits, chemical balance, traffic, GPS) are linear systems. A free variable or null vector is meaningful there, and an inconsistent system means an impossible measurement.

Watch and read

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

2.6 Systems of equations and elimination

The picture

The idea, in words

Definitions and theorems

Systems and the solution set

System of linear equations

Solutions are a particular solution plus the null space

A system has zero, one or infinitely many solutions

Column space

Matrix times vector is a combination of the columns

Row operations

Augmented matrix

Row operations

Row operations do not change the solutions

Echelon form

Row echelon form

Pivot

Reduced row echelon form

Free variable

Every matrix reduces to reduced row echelon form

Reading the solutions off the reduced form

Rank, pivots and the four fundamental subspaces

Rank equals the number of pivots

Row space

Left null space

Row rank equals column rank

Inverses

Inverse matrix

A left inverse of a square matrix is a full inverse

Elementary matrix

Row operations are multiplication by elementary matrices

Computing the inverse by row reducing [A | I]

The invertible matrix theorem

Invertible matrix theorem

Beyond: remembering the row operations (LU)

Examples and non-examples

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere