Rank and the shape of the solution set

One, none or infinitely many

The system of lesson 3.3.1 had exactly one solution, the point where two lines cross. Lesson 1.2.1 found two other ways two lines can sit: parallel, or one line written twice.

Keep the first equation, $x_1 + 2x_2 = 3$, and change the second:

• $2x_1 + x_2 = 3$: the lines cross once, at $(1, 1)$. One solution.
• $2x_1 + 4x_2 = 5$: halved, this is $x_1 + 2x_2 = 2.5$, a parallel line. No solution.
• $2x_1 + 4x_2 = 6$: halved, this is the first equation again. Every point of the line solves both. Infinitely many solutions.

What elimination shows

Run elimination (lesson 3.3.1) on the three systems. In each, $R_2 - 2R_1$ clears the first column and leaves one new row.

A row $0 = -1$ is false whatever the unknowns are, so the system has no solution. A row $0 = 0$ is true for every choice: it adds no condition, so only $x_1 + 2x_2 = 3$ is left.

In that last case $x_2$ can be anything. Call it $t$; then $x_1 = 3 - 2t$. Every value of $t$ gives a solution:

The column picture

Lesson 3.3.1 read $A\mathbf{x} = \mathbf{b}$ as a question: which combination of the columns gives $\mathbf{b}$? Here the columns are $\mathbf{a}_1 = (1, 2)$ and $\mathbf{a}_2 = (2, 4)$. The second is twice the first, so both point along the same line through 0.

Every combination $x_1\mathbf{a}_1 + x_2\mathbf{a}_2$ is a multiple of $(1, 2)$ and stays on that line. The point $\mathbf{b} = (3, 6)$ lies on it and is reached in many ways: $3\mathbf{a}_1$, or $\mathbf{a}_1 + \mathbf{a}_2$, or $-\mathbf{a}_1 + 2\mathbf{a}_2$. The point $(3, 5)$ is off the line, and no combination reaches it.

Rank: the number of pivots

The rank of a matrix is the number of pivots in its row echelon form. It counts the equations that really constrain the unknowns, once repeats and combinations are cleared away.

• $\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ has rank 2: elimination leaves pivots 1 and $-3$.
• $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ has rank 1: the second row becomes zeros.
• The 3 × 3 matrix of lesson 3.3.1 has rank 3, with pivots 1, 1 and 3.

A square $n \times n$ matrix of rank $n$ has a pivot in every column. Then $A\mathbf{x} = \mathbf{b}$ has exactly one solution for every $\mathbf{b}$, and $A$ has an inverse (lesson 3.2.3).

With rank below $n$, some column of $A$ is a combination of the others, as $\mathbf{a}_2 = 2\mathbf{a}_1$ above. Such a matrix has no inverse. Lesson 3.4.1 tests for this with the determinant, and lesson 3.5.1 calls the columns dependent.

Free variables and the shape of the solutions

In row echelon form, each column with a pivot gives a pivot variable. The unknowns of the other columns are free variables: they may take any value, and back substitution then fixes the pivot variables.

A line in space. Take three equations in three unknowns, with $\mathbf{b} = (4, 9, 13)$:

The steps $R_2 - 2R_1$, $R_3 - 3R_1$ and then $R_3 - R_2$ give

The pivots sit in columns 1 and 3, so the rank is 2 and $x_2$ is free.

Set $x_2 = t$. Row 2 gives $x_3 = 1$, and row 1 gives $x_1 = 4 - 2t - 1 = 3 - 2t$. The solutions form a line in $\mathbb{R}^3$, through $(3, 0, 1)$ in the direction $(-2, 1, 0)$:

A plane. In $x_1 + x_2 + x_3 = 1$, $2x_1 + 2x_2 + 2x_3 = 2$, $3x_1 + 3x_2 + 3x_3 = 3$, rows 2 and 3 are multiples of row 1. Elimination leaves one pivot, so the rank is 1 and two unknowns are free.

With $x_2 = s$ and $x_3 = t$, every $x_1 = 1 - s - t$ works. The solutions form a plane, which contains $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$ and $(2, -1, 0)$.

Is there a solution at all?

A system with at least one solution is consistent. Elimination on $[A \mid \mathbf{b}]$ settles it: the system has no solution exactly when some row reads $0 = c$ with $c \neq 0$. That row has its pivot in the $\mathbf{b}$ column, so $[A \mid \mathbf{b}]$ has one more pivot than $A$.

Change the last entry of $\mathbf{b}$ above from 13 to 12. The same steps now end in the row $(0, 0, 0 \mid -1)$, which reads $0 = -1$. The rank of $A$ is still 2, but the rank of $[A \mid \mathbf{b}]$ is 3.

More equations than unknowns, or fewer

The rule works for systems of any shape. A tall system has more equations than unknowns. Take $x_1 + x_2 = 3$, $x_1 - x_2 = 1$ and $x_1 + 2x_2 = 4$: three lines in the plane.

Elimination with $R_2 - R_1$, $R_3 - R_1$ and $R_3 + \frac{1}{2}R_2$ leaves the row $(0, 0 \mid 0)$. Both ranks are 2, the number of unknowns, so there is one solution, $(2, 1)$. Change the 4 to 5 and the last row is $(0, 0 \mid 1)$: no solution.

Three lines rarely pass through one point, so a tall system usually has no solution. Its rank is at most the number of unknowns, below the number of equations, so some right-hand sides are always out of reach. Case study 3.3.4 meets this with three states of the world and two assets.

A wide system has fewer equations than unknowns. Take $x_1 + x_2 + x_3 = 6$ and $x_2 - x_3 = 1$: the rank is 2 and there are 3 unknowns, so one is free.

With $x_3 = t$, the solutions are $(5 - 2t,\ 1 + t,\ t)$, a line. A wide system never has exactly one solution.

Rank on a computer

On a computer, rounding hides zeros. In $\begin{pmatrix} 0.1 & 0.7 \\ 0.3 & 2.1 \end{pmatrix}$ the second row is 3 times the first, so the rank is 1. But 0.1, 0.3, 0.7 and 2.1 have no exact binary form, and elimination leaves $4.4 \times 10^{-16}$ where a 0 should be.

np.linalg.matrix_rank allows for this: it treats numbers that small, relative to the matrix, as zero, and returns 1. np.linalg.solve is less careful. Here it raises no error and returns numbers as large as $2 \times 10^{16}$, which mean nothing.

Nearly singular systems

A matrix can have full rank and still behave almost like a singular one. Take $x_1 + x_2 = 2$ and $x_1 + 1.001x_2 = 2.001$, two lines that are almost parallel. The answer is $(1, 1)$.

Now move the right-hand side of the second equation a little:

A change of 0.001 in $b_2$ moves each unknown by 1. When two lines are nearly parallel, sliding one a little slides their meeting point a long way.

Such a system is ill-conditioned: small errors in the data, such as rounding or a mistyped price, become large errors in the answer. np.linalg.cond puts a number on it, the condition number, here about 4002. Case study 3.4.3 meets this with assets that are almost copies of each other.

The explorer shows the cases of this lesson in both pictures. Pick each preset in turn. On "Nearly parallel", move $b_2$ by one step of 0.05 and watch the meeting point jump by a whole unit.

Common mistakes

1. A row $0 = 0$ is not a contradiction. It adds no condition; with fewer pivots than unknowns it means free variables.
2. A row $0 = c$ with $c \neq 0$ means no solution, not that some unknown is 0.
3. Count pivots after elimination. $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ has two nonzero rows but rank 1.
4. Free variables are unknowns minus rank, $n - \operatorname{rank} A$, where $n$ counts columns, not equations.
5. Shape is not the whole story. A tall system can have exactly one solution, as $(2, 1)$ above. A wide one can never have exactly one.
6. Do not trust a tiny pivot or a quiet solve. Check matrix_rank, and remember that a nearly singular system can magnify small errors.