The Nullspace of A: Solving Ax = 0

Linear-Algebra tutorial · PySpark.in

A Beginner's Guide to Linear Algebra | Part 5 of 4

The Nullspace of A: Solving Ax = 0

1. What Is the Nullspace?

So far we have studied the column space — the set of vectors b for which Ax = b has a solution. Now we ask a different question: which vectors x are sent to zero by A? That is, for which x does Ax = 0?

The set of all solutions to Ax = 0 is called the nullspace of A, written N(A). This might sound like a strange thing to study — why care about inputs that produce zero output? The answer is that the nullspace encodes everything about non-uniqueness: if x is a solution to Ax = b and n is in the nullspace, then x + n is also a solution.

The nullspace N(A) is the set of all vectors x satisfying Ax = 0. It is a subspace of Rⁿ (where n is the number of columns of A). It always contains the zero vector.

Let's verify it is actually a subspace. If Ax = 0 and Ay = 0, then A(x+y) = Ax + Ay = 0 + 0 = 0. If Ax = 0, then A(cx) = c(Ax) = c·0 = 0. Both closure conditions hold. The nullspace is genuinely a subspace.

2. Finding the Nullspace: Elimination

To find N(A), we solve Ax = 0 using Gaussian elimination. The process is exactly the same as solving any linear system — we just set b = 0 and keep track of what happens.

Let's work through a complete example. Take the 3×4 matrix:

A = [ 1 2 2 2 ]

[ 2 4 6 8 ]

[ 3 6 8 10]

We eliminate below the first pivot (row 1). Subtract 2 × row 1 from row 2, and 3 × row 1 from row 3:

[ 1 2 2 2 ]

[ 0 0 2 4 ]

Now eliminate below the second pivot. Subtract row 2 from row 3:

U = [ 1 2 2 2 ]

[ 0 0 2 4 ]

[ 0 0 0 0 ]

This is the upper triangular form U. We have two pivots: the 1 in column 1 and the 2 in column 3.

3. Pivot Variables and Free Variables

After elimination, we classify the columns by whether they contain a pivot.

Pivot columns: 1 and 3 (columns with pivots in U)

Free columns: 2 and 4 (columns with no pivots)

The variables corresponding to free columns — here x₂ and x₄ — can be set to any value we like. They are called free variables because they are unconstrained. Once we choose values for the free variables, the pivot variables x₁ and x₃ are determined by back substitution.

This is the key insight: every free variable produces one independent solution vector to Ax = 0. A matrix with k free variables has a nullspace of dimension k.

To find the null vectors, set each free variable to 1 (and all other free variables to 0), then solve for the pivot variables. Let us do this for our example.

Special Solution 1: set x₂ = 1, x₄ = 0

From row 2 of U: 0·x₁ + 0·x₂ + 2·x₃ + 4·x₄ = 0 → x₃ = 0

From row 1 of U: x₁ + 2·x₂ + 2·x₃ + 2·x₄ = 0 → x₁ = -2

Special solution 1: s₁ = (-2, 1, 0, 0)

Special Solution 2: set x₂ = 0, x₄ = 1

From row 2 of U: 2·x₃ + 4·(1) = 0 → x₃ = -2

From row 1 of U: x₁ + 2·(0) + 2·(-2) + 2·(1) = 0 → x₁ = 2

Special solution 2: s₂ = (2, 0, -2, 1)

4. The Complete Nullspace

The complete nullspace is all linear combinations of the special solutions:

N(A) = { c₁·s₁ + c₂·s₂ for any scalars c₁ and c₂ }

= { c₁·(-2,1,0,0) + c₂·(2,0,-2,1) for all c₁, c₂ in R }

This is a 2-dimensional subspace of R⁴ — a plane through the origin. You can verify: for any choice of c₁ and c₂, the vector c₁s₁ + c₂s₂ satisfies Ax = 0.

The dimension of the nullspace equals the number of free variables, which equals n − r, where n is the number of columns and r is the rank (number of pivots). This is called the nullity of A.

5. The Reduced Row Echelon Form R

After finding the nullspace using U, we can go one step further and reduce all the way to R — the reduced row echelon form. In R, we eliminate both above and below each pivot, and divide each pivot row to make the pivot equal to 1.

Starting from our U:

U = [ 1 2 2 2 ] R = [ 1 2 0 -2 ]

[ 0 0 2 4 ] [ 0 0 1 2 ]

[ 0 0 0 0 ] [ 0 0 0 0 ]

The beauty of R is that the special solutions can be read off immediately. Look at the free columns (2 and 4) in R. The special solutions are obtained by taking the negative of each free column and inserting it in the right position:

From free column 2: pivot entries are 2 and 0 → s₁ = (-2, 1, 0, 0)

From free column 4: pivot entries are -2 and 2 → s₂ = (2, 0, -2, 1)

The reduced echelon form R makes the nullspace completely transparent. The free columns of R are your 'instruction manual' for writing down the special solutions — just negate them and slot them into the correct positions.

6. The Rank-Nullity Theorem

We now have two fundamental numbers associated with any matrix A of size m×n:

Rank r = number of pivots = dim(C(A))

Nullity n-r = number of free variables = dim(N(A))

These two numbers add up to n, the total number of columns. This beautiful fact is the Rank-Nullity Theorem:

Rank + Nullity = n (the number of columns) or equivalently: r + (n-r) = n

For our example: rank r = 2 (two pivots), n = 4 columns, nullity = 4 − 2 = 2 (two free variables, two special solutions). Check: 2 + 2 = 4. ✓

This theorem is deceptively simple but deeply important. It says that the column space and the nullspace together account for all n dimensions of the input space Rⁿ. Nothing is 'left over'. The matrix uses r dimensions productively (mapping them to the column space) and kills the remaining n−r dimensions (sending them to zero).

References & Further Reading

Gilbert Strang. Introduction to Linear Algebra, 5th ed. Wellesley-Cambridge Press, 2016. (Chapter 3.2)

3Blue1Brown. Essence of Linear Algebra, Chapter 7: Inverse Matrices, Column Space, and Null Space. YouTube, 2016.

Khan Academy. Null space and column space. khanacademy.org/math/linear-algebra

End of Blog 5 — Linear Algebra Series