The null space

Some inputs a matrix sends to zero. Watch a whole line of points in space fall into the origin and light up.

What a matrix erases

The matrix at the top of the page has a quiet habit. Its third row is the sum of the first two, so every output has its third entry equal to the sum of the first two. All of space lands on one plane, and something has to be lost on the way.

What is lost is a direction. Try the input $(-1,-1,1)$:

Every multiple of it goes to zero too, since $\mathbf{A}(c\,\mathbf{x})=c\,\mathbf{A}\mathbf{x}=c\,\mathbf{0}=\mathbf{0}$. That is the line that falls into the origin in the picture. Two inputs that differ by a point of this line give the same output, so from the output alone you can’t tell them apart.

The null space

The set of every input that a matrix sends to zero is its null space:

It is a subspace, as in Vector spaces and subspaces. If $\mathbf{A}\mathbf{x}=\mathbf{0}$ and $\mathbf{A}\mathbf{y}=\mathbf{0}$, then $\mathbf{A}(\mathbf{x}+\mathbf{y})=\mathbf{0}+\mathbf{0}=\mathbf{0}$, and $\mathbf{A}(c\,\mathbf{x})=\mathbf{0}$. The zero vector is always in it.

Finding it: reduced row echelon form

To find the null space, solve $\mathbf{A}\mathbf{x}=\mathbf{0}$. Elimination, from Elimination, does the work. Subtracting a multiple of one equation from another never changes the solutions, and the right-hand side stays all zeros, so I only need to track the matrix.

Take a wider example, with two equations and four unknowns:

Clear below the first pivot: row 2 $\leftarrow$ row 2 $-\ 2\cdot$ row 1 gives $(0,0,1,2)$. The second column now has 0 where a pivot would go, so the next pivot is the 1 in column 3. Then go one step further than elimination usually goes: clear above that pivot too, with row 1 $\leftarrow$ row 1 $-$ row 2, which gives $(1,2,0,1)$. The result is

This is the reduced row echelon form of $\mathbf{A}$, written $\mathrm{rref}(\mathbf{A})$. Its rules are simple:

• each row’s first nonzero entry is a 1, its pivot;
• each pivot sits to the right of the pivot above it;
• every other entry in a pivot’s column is 0;
• any all-zero rows sit at the bottom.

Columns 1 and 3 hold pivots: they are the pivot columns. Columns 2 and 4 have none: they are the free columns, and $x_2$, $x_4$ are the free variables. The number of pivots is the rank of the matrix, written $r$. Here $r=2$.

Special solutions

Read $\mathrm{rref}(\mathbf{A})\,\mathbf{x}=\mathbf{0}$ back as equations:

Each equation has one pivot variable, and the free variables may be anything. So choose the free variables, and the pivot variables follow: $x_1=-2x_2-x_4$ and $x_3=-2x_4$.

The simplest choices set one free variable to 1 and the others to 0. Each gives one special solution:

• $x_2=1$, $x_4=0$: then $x_1=-2$, $x_3=0$, so $\mathbf{s}_1=(-2,1,0,0)$.
• $x_2=0$, $x_4=1$: then $x_1=-1$, $x_3=-2$, so $\mathbf{s}_2=(-1,0,-2,1)$.

Any other choice of $x_2$ and $x_4$ is a mix of these two, so

where $x_2$ and $x_4$ run over all numbers.

Watch where the pivot entries of each special solution come from. They are the free column of $\mathrm{rref}(\mathbf{A})$ with its signs changed: column 2 is $(2,0)$ and gives $x_1=-2$, $x_3=0$; column 4 is $(1,2)$ and gives $x_1=-1$, $x_3=-2$.

Dimension

A line through the origin has one free direction, and a plane has two. The number of free directions of a subspace is its dimension, written $\dim$. Independence, basis and dimension makes this exact; here the count is easy.

Each free variable gives one special solution, and none of them is a mix of the others: each has a 1 where the others have 0. So the null space has one direction per free column. There are $n$ columns, and $r$ of them hold pivots, so

For the $2\times4$ example, $4-2=2$: the null space is a plane inside $\mathbb{R}^4$. For the $3\times3$ matrix at the top, the reduced form is $\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}$, with rank 2 and one free column, so its null space is the line of $(-1,-1,1)$, and $3-2=1$.

Worked example

1. The $2\times4$ matrix. Reduce $\mathbf{A}=\begin{bmatrix}1&2&1&3\\2&4&3&8\end{bmatrix}$ to $\mathrm{rref}(\mathbf{A})=\begin{bmatrix}1&2&0&1\\0&0&1&2\end{bmatrix}$: pivots in columns 1 and 3, free variables $x_2$ and $x_4$. The special solutions are $\mathbf{s}_1=(-2,1,0,0)$ and $\mathbf{s}_2=(-1,0,-2,1)$. Check them on the original matrix:

Four columns, rank 2, two free variables: $\dim N(\mathbf{A})=2$.

2. The $3\times3$ matrix. Row 1 plus row 2 gives row 3, so elimination leaves a zero row and rank 2. The free variable is $x_3$, and $\mathbf{A}(-1,-1,1)=\mathbf{0}$.

3. A $2\times2$ matrix. $\begin{bmatrix}1&2\\2&4\end{bmatrix}$ reduces to $\begin{bmatrix}1&2\\0&0\end{bmatrix}$. The free variable is $x_2$; setting it to 1 gives $x_1=-2$, so the null space is all multiples of $(-2,1)$.

4. Counting. A $3\times5$ matrix of rank 3 has $5-3=2$ free variables, so its null space has dimension 2. A square matrix with a pivot in every column, the opposite of the singular case in Elimination, has no free variables, so its null space is $\{\mathbf{0}\}$ alone.

Predict before you watch again: how many points of the line through $(-1,-1,1)$ land at the origin? All of them.

Where you’ll meet this

Aliasing. The tones that sampling can’t tell apart differ by a signal in its null space, as the callout above shows.

Currents round a loop. In a circuit, a current that flows round a closed loop adds nothing at any node. Such loop currents form a null space, and Graphs and networks finds them.

Balancing a reaction. Burning propane: $a$ molecules of $\text{C}_3\text{H}_8$ and $b$ of $\text{O}_2$ give $c$ of $\text{CO}_2$ and $d$ of $\text{H}_2\text{O}$. Counting each kind of atom on both sides gives three equations with zero on the right: carbon $3a-c=0$, hydrogen $8a-2d=0$, oxygen $2b-2c-d=0$. The null space is the line of $(1,5,3,4)$: one propane and five oxygen give three carbon dioxide and four water.

Reference card