Rank, null space and solution sets

A matrix with determinant zero flattens the space it acts on, and the useful questions are what exactly gets flattened and what is left.

The previous lesson gave a yes or no answer to invertibility. That is not enough, for two reasons. A three by three matrix can collapse space onto a plane, onto a line or onto the origin, and all three have determinant zero. And most matrices in practice are not square at all: fitting a straight line to fifty measurements produces a fifty by two matrix, which has no determinant and no inverse, and yet the system is not hopeless.

Two subspaces belong to every matrix

Let $A$ be an $m$ by $n$ matrix, so it maps $R^{n}$ to $R^{m}$ .

The column space of $A$ , written $C (A)$ , is the span of its columns. Since $A x$ is the combination of the columns weighted by the components of $x$ , the column space is exactly the set of vectors of the form $A x$ : everything the transformation can reach. It lives in $R^{m}$ , the output space.

The null space of $A$ , written $N (A)$ , is the set of $x$ with $A x = 0$ : everything the transformation destroys. It lives in $R^{n}$ , the input space.

Both are subspaces, by the test from the lesson on bases. The column space is a span, so it is one automatically. The null space is closed under both operations because $A (u + v) = A u + A v = 0 + 0$ and $A (c u) = c A u = 0$ , which is linearity doing the work.

Take a concrete matrix and keep it for the rest of the lesson:

A = [(1, 2, 3), (2, 4, 6), (0, 1, 1)]

Its second column is twice its first, so the columns are dependent and the matrix is singular. The column space is the span of $(1, 2, 3)$ and $(0, 1, 1)$ , which are not multiples of each other, so it is a plane in $R^{3}$ : the transformation squashes all of space onto that plane. For the null space, solve $x_{1} (1, 2, 3) + x_{2} (2, 4, 6) + x_{3} (0, 1, 1) = 0$ . Because the first two columns are parallel, the equation reads $(x_{1} + 2 x_{2}) (1, 2, 3) + x_{3} (0, 1, 1) = 0$ , and since those two vectors are independent both coefficients must vanish: $x_{3} = 0$ and $x_{1} = - 2 x_{2}$ . So the null space is the line spanned by $(- 2, 1, 0)$ , and indeed $- 2 (1, 2, 3) + 1 (2, 4, 6) = 0$ .

A whole line of inputs is sent to the origin, and a whole plane of outputs is reachable. One dimension was destroyed and two survived, which is the shape of the answer this lesson formalises.

Rank

The rank of $A$ is the dimension of its column space, written $r$ . It counts how many genuinely different directions the columns supply, which is how many independent directions survive the transformation. The example above has rank two.

Rank is found by elimination rather than by inspection. Row reducing $A$ produces a staircase in which each step begins with a pivot, the first non-zero entry of its row, and the number of pivots is the rank. Columns carrying a pivot are called pivot columns and correspond to independent columns of the original matrix; the others are free columns, each of them a combination of the pivot columns to its left.

The nullity is the dimension of the null space. Each free column supplies exactly one basis vector of the null space, obtained by setting that free variable to one, all other free variables to zero, and solving back for the pivot variables. The example has one free column, the second, and correspondingly one null space basis vector.

That correspondence proves the central counting theorem, since every column is either a pivot column or a free one and no column is both:

rank + nullity = n

the number of columns. This is the rank-nullity theorem, and it is a conservation law: the input space has $n$ dimensions, the map destroys the nullity of them and delivers the rank of them to the output, and the two numbers always add back to $n$ . For the example, $2 + 1 = 3$ .

Example. Find the rank and nullity of $B = [(1, 1), (2, 2), (3, 3)]$ , a two by three matrix.

Every column is a multiple of $(1, 1)$ , so the column space is a line in $R^{2}$ and the rank is $1$ . There are three columns, so the nullity is $3 - 1 = 2$ : a whole plane of inputs collapses to the origin. One check: $2 (1, 1) - 1 (2, 2) = 0$ gives the null vector $(2, - 1, 0)$ , and $3 (1, 1) - 1 (3, 3) = 0$ gives $(3, 0, - 1)$ , and those two are independent.

Now you. Find the rank and nullity of $C = [(1, 0), (0, 1), (1, 1)]$ .

Answer

The first two columns already span $R^{2}$ , so the rank is $2$ and the nullity is $3 - 2 = 1$ . The null vector satisfies $x_{1} (1, 0) + x_{2} (0, 1) + x_{3} (1, 1) = 0$ , giving $x_{1} = - x_{3}$ and $x_{2} = - x_{3}$ , so the null space is spanned by $(- 1, - 1, 1)$ .

The complete solution of a system

Now return to $A x = b$ with the tools assembled.

Existence. A solution exists exactly when $b$ lies in the column space, since the column space is precisely the set of reachable vectors. For the example matrix, take $b = (1, 3, 4)$ , which is column one plus column three, so it is reachable and $x = (1, 0, 1)$ is a solution. Now take $b = (1, 3, 5)$ . Reaching it needs $a (1, 2, 3) + b (0, 1, 1) = (1, 3, 5)$ , and the first component forces $a = 1$ , the second then forces $b = 1$ , and the third would need $3 + 1 = 5$ , which is false. That target is off the plane and no solution exists.

Uniqueness. If $p$ is one solution and $n$ is any null space vector, then $A (p + n) = A p + A n = b + 0 = b$ , so $p + n$ is also a solution. Conversely if $p$ and $q$ are both solutions then $A (p - q) = 0$ , so they differ by a null space vector. Hence the complete solution set is

{p + n : n \in N (A)}

one particular solution plus the whole null space. Geometrically it is a copy of the null space, shifted away from the origin by $p$ . It is not a subspace unless $b = 0$ , since it misses the origin, which is why homogeneous systems are the well-behaved ones.

For the example with $b = (1, 3, 4)$ , the complete solution is $(1, 0, 1) + t (- 2, 1, 0)$ for any $t$ . Checking at $t = 3$ : the input $(- 5, 3, 1)$ gives $- 5 (1, 2, 3) + 3 (2, 4, 6) + 1 (0, 1, 1) = (- 5 + 6, - 10 + 12 + 1, - 15 + 18 + 1) = (1, 3, 4)$ , as promised.

Every statement of the first lesson now has a reason. No solution means $b$ outside the column space. Exactly one means the null space is ${0}$ , that is, nullity zero, that is, rank equal to the number of columns. Infinitely many means a non-trivial null space, and the solution set then has the dimension of that null space, so it is a line, a plane or larger, never a scattering of isolated points.

Example. With $A$ as above, solve $A x = (2, 5, 7)$ completely.

Is it reachable? Solve $a (1, 2, 3) + b (0, 1, 1) = (2, 5, 7)$ : the first component gives $a = 2$ , the second $4 + b = 5$ so $b = 1$ , and the third checks, $6 + 1 = 7$ . So $p = (2, 0, 1)$ is one solution, using two of column one and one of column three. The complete solution is $(2, 0, 1) + t (- 2, 1, 0)$ , a line of solutions.

Now you. A five by eight matrix has rank three. What is the dimension of its null space, and can $A x = b$ be solved for every $b$ in $R^{5}$ ?

Answer

Nullity is $8 - 3 = 5$ , by rank-nullity with $n = 8$ columns. The column space has dimension three inside $R^{5}$ , so it is not all of $R^{5}$ and most targets are unreachable. When a solution does exist it is never unique, since a five-dimensional family of null vectors can be added to it.

Tall, wide and square

The shape of a matrix bounds its rank, since the rank cannot exceed either the number of columns or the number of rows: the column space is spanned by $n$ columns and lives inside $R^{m}$ . So $r \leq \min (m, n)$ , and a matrix achieving that bound is said to have full rank. Three cases are worth separating, because each is a different practical situation.

A tall matrix, with $m > n$ , has more equations than unknowns. At best $r = n$ , in which case the columns are independent, the null space is trivial and any solution is unique, but the column space is an $n$ -dimensional sliver of $R^{m}$ and almost every $b$ misses it. Overdetermined systems are usually unsolvable and never have more than one solution. That is the case fitting a line to fifty data points produces.

A wide matrix, with $m < n$ , has more unknowns than equations. At best $r = m$ , in which case the column space is all of $R^{m}$ and every $b$ is reachable, but rank-nullity forces a null space of dimension $n - m \geq 1$ , so solutions always come in infinite families. Underdetermined systems are usually solvable and never uniquely. A structure with more supports than the equilibrium equations can determine is in exactly this situation, and engineers call it statically indeterminate.

A square matrix of full rank $r = n$ is the invertible case of the previous lesson, where existence and uniqueness both hold. It is the only shape that can manage both, and even then only when the rank is full.

Example. A $50$ by $2$ matrix has rank $2$ . What are the dimensions of its null space and column space, and what does that say about solving $A x = b$ ?

The null space has dimension $2 - 2 = 0$ , so the only vector sent to the origin is $0$ and a solution, if one exists, is unique. The column space has dimension $2$ inside $R^{50}$ , a plane in a fifty-dimensional space, so a $b$ assembled from measurements will not lie in it and no exact solution exists.

Now you. A $3$ by $7$ matrix has rank $3$ . Can $A x = b$ always be solved, and is the solution ever unique?

Answer

The column space has dimension $3$ inside $R^{3}$ , so it is all of $R^{3}$ and every $b$ is reachable. But the nullity is $7 - 3 = 4$ , so every solution comes with a four-dimensional family of others. Always solvable, never uniquely.

Row rank equals column rank

The rows of $A$ span a subspace of $R^{n}$ called the row space, and its dimension is the row rank. There is no obvious reason for it to match the column rank, since the rows and columns of a rectangular matrix are different objects living in different spaces, and yet:

row rank = column rank

The reason is elimination. Row operations do not change the row space, since each new row is a combination of old ones and the process is reversible. Row operations also do not change which combinations of columns vanish, since each equation is transformed into an equivalent one, so they preserve the null space and therefore the column rank as well. In the reduced staircase form, both ranks are visibly the number of pivots. Counting pivots therefore counts both.

For the example matrix, the rows are $(1, 2, 0)$ , $(2, 4, 1)$ and $(3, 6, 1)$ , and the third is the sum of the first two, so the row space is two-dimensional, matching the column rank of two.

One more consequence deserves stating, since it is where orthogonality enters. Every row of $A$ , dotted with any null space vector $x$ , gives zero, because that dot product is one component of $A x = 0$ . So the null space is perpendicular to the row space. Check it: the null vector $(- 2, 1, 0)$ dotted with $(1, 2, 0)$ gives $- 2 + 2 = 0$ , with $(2, 4, 1)$ gives $- 4 + 4 = 0$ , and with $(3, 6, 1)$ gives $- 6 + 6 = 0$ .

The two spaces have dimensions $r$ and $n - r$ and sit at right angles inside $R^{n}$ , splitting the input space between them. The same argument applied to $A^{T}$ splits the output space $R^{m}$ into the column space, of dimension $r$ , and the null space of $A^{T}$ , of dimension $m - r$ , which is what is left unreachable. For the example, $m - r = 1$ , and the unreachable direction is spanned by $(1, 1, - 1)$ : dotting it with each column gives $1 + 2 - 3 = 0$ , $2 + 4 - 6 = 0$ and $0 + 1 - 1 = 0$ . Anything with a component along $(1, 1, - 1)$ cannot be produced, which is precisely why $(1, 3, 5)$ failed earlier.

These four subspaces, with dimensions $r$ , $n - r$ , $r$ and $m - r$ , are the full anatomy of a matrix.

Honest limits

Rank is exact in theory and delicate in practice. The matrix with columns $(1, 2, 3)$ , $(2, 4, 6)$ and $(0, 1, 1)$ has rank two, but change one entry from $4$ to $4.000001$ and the columns become independent, giving rank three. Real measurements always contain such perturbations, so a matrix built from data is almost always of full rank arithmetically while being close to a lower-rank one. Numerical software therefore reports the number of singular values above a tolerance, using the decomposition mentioned in the last lesson of this course, and calls that the rank. The honest statement is that rank near a threshold is a judgement, not a computation.

Second, the complete solution $p + N (A)$ tells you the set but does not choose a member of it. When there are infinitely many solutions, applications need one, and the usual choice is the shortest, which is a projection problem. The tools for that are in the next lesson.

The awkward case is now the common one: $b$ outside the column space, so no solution exists at all. Fifty measurements and two unknowns produce that situation nearly always, because fifty points do not lie on one line. Giving up is not the practice. The next lesson replaces the unreachable target by the closest reachable one, and finds that the whole method follows from a single right angle.