1.5 Solution sets of linear systems

Big idea

Solution sets get described as objects here, not just listed. The description has a standard shape: one vector plus a combination of a few others, with the weights free to be anything. That shape is the parametric vector form, and it turns an infinite solution set into a short formula you can write, check, and compare.

The organizing move is to split the problem in two. First solve $A\mathbf{x} = \mathbf{0}$, the homogeneous version with the right-hand side wiped out. Then, if you need $A\mathbf{x} = \mathbf{b}$, find any single solution of it and add the homogeneous solutions to that one. The homogeneous part carries all the freedom; the single solution carries the offset.

Geometrically the picture is a shift. The homogeneous solution set always contains the origin and is a line, a plane, or a higher-dimensional flat through it. The solution set of $A\mathbf{x} = \mathbf{b}$ is that same flat slid over so it passes through one particular solution, which is why the two sets always have the same shape and dimension.

Decoder

Homogeneous means the right-hand side is the zero vector. Such a system is never inconsistent: setting every unknown to zero always works. That solution, $\mathbf{x} = \mathbf{0}$, is called the trivial solution, and the only interesting question is whether anything else solves the system.

The homogeneous equation has a solution other than zero exactly when its system has at least one free variable.

Nothing deep is hiding in that sentence. Row reduce $A$. If some column holds no pivot, its unknown is free, and choosing a nonzero value for it produces a nonzero solution. If every column holds a pivot, every unknown is forced to zero and only the trivial solution exists. So the test runs on columns, unlike the spanning test of the previous section, which runs on rows.

The word “trivial” is about the solution, not about the system. Saying a homogeneous system has only the trivial solution is a strong statement; it is the uniqueness half of the existence and uniqueness pair.

Definitions and results

Homogeneous system. A system that can be written $A\mathbf{x} = \mathbf{0}$. It is always consistent, since $\mathbf{x} = \mathbf{0}$ satisfies it.

Trivial and nontrivial solutions. $\mathbf{x} = \mathbf{0}$ is the trivial solution. Any other solution is nontrivial.

When nontrivial solutions exist. $A\mathbf{x} = \mathbf{0}$ has a nontrivial solution exactly when the system has at least one free variable, which happens exactly when some column of $A$ holds no pivot. Consequently, if $A$ has more columns than rows, nontrivial solutions always exist, because there are not enough pivots to go around.

Parametric vector form. Solve the homogeneous system, write each basic variable in terms of the free ones, then collect the result as a vector expression. The output looks like

$$ \mathbf{x} = t_1\mathbf{v}_1 + \cdots + t_k\mathbf{v}_k $$

with one parameter per free variable. The vectors $\mathbf{v}_i$ come from reading off the coefficients of each free variable, and they are the special solutions you get by setting one free variable to $1$ and the rest to $0$.

The homogeneous solution set is a span. Written that way, the solution set of $A\mathbf{x} = \mathbf{0}$ is $\text{Span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$. It contains the origin, and it is a line through the origin when there is one free variable, a plane through the origin when there are two, and so on.

Structure of the general solution. Suppose $A\mathbf{x} = \mathbf{b}$ is consistent and $\mathbf{p}$ is one particular solution. Then the full solution set is the set of all vectors $\mathbf{p} + \mathbf{v}$, where $\mathbf{v}$ runs over the solutions of $A\mathbf{x} = \mathbf{0}$. In parametric vector form,

$$ \mathbf{x} = \mathbf{p} + t_1\mathbf{v}_1 + \cdots + t_k\mathbf{v}_k $$

Why it works in one line: if $A\mathbf{p} = \mathbf{b}$ and $A\mathbf{v} = \mathbf{0}$, then $A(\mathbf{p} + \mathbf{v}) = \mathbf{b} + \mathbf{0} = \mathbf{b}$; and if $A\mathbf{x} = \mathbf{b}$, then $A(\mathbf{x} - \mathbf{p}) = \mathbf{0}$, so $\mathbf{x}$ is $\mathbf{p}$ plus a homogeneous solution.

Consequence for shape. Every consistent system has a solution set that is a translate of the solution set of its homogeneous version. One solution means the homogeneous set is just the origin. Infinitely many means it is a line or larger, shifted off the origin unless $\mathbf{b} = \mathbf{0}$.

Same system, different parametrizations. The vectors $\mathbf{v}_i$ are not unique; a different choice of which variables to call free, or a different scaling, gives different vectors describing the same set. The set is what matters, not the formula.

Worked examples

A homogeneous system with one free variable

Solve $A\mathbf{x} = \mathbf{0}$ for

$$ A = \begin{bmatrix} 1 & -2 & 1 \\ 2 & -3 & 0 \end{bmatrix} $$

Reduce $A$. Subtract $2$ times row 1 from row 2 to get row 2 equal to $(0, 1, -2)$, then add $2$ times that row to row 1:

$$ \begin{bmatrix} 1 & 0 & -3 \\ 0 & 1 & -2 \end{bmatrix} $$

Columns 1 and 2 hold pivots, so $x_1$ and $x_2$ are basic and $x_3$ is free. The rows give $x_1 = 3x_3$ and $x_2 = 2x_3$. Set $x_3 = t$:

$$ \mathbf{x} = t\begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} $$

The solution set is the span of that single vector, a line through the origin in $\mathbf{R}^3$.

Check the vector: the first row of $A$ against $(3, 2, 1)$ gives $3 - 4 + 1 = 0$, and the second gives $6 - 6 + 0 = 0$.

The same matrix with a nonzero right-hand side

Now solve $A\mathbf{x} = \mathbf{b}$ with $\mathbf{b} = (4, 5)$ and the same $A$. Reduce the augmented matrix

$$ \begin{bmatrix} 1 & -2 & 1 & 4 \\ 2 & -3 & 0 & 5 \end{bmatrix} $$

The same two operations give

$$ \begin{bmatrix} 1 & 0 & -3 & -2 \\ 0 & 1 & -2 & -3 \end{bmatrix} $$

So $x_1 = -2 + 3x_3$ and $x_2 = -3 + 2x_3$, with $x_3$ free. In parametric vector form:

$$ \mathbf{x} = \begin{bmatrix} -2 \\ -3 \\ 0 \end{bmatrix} + t\begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} $$

The direction vector is the one from the homogeneous case, exactly as the structure result predicts. Only the offset is new.

Check the offset $\mathbf{p} = (-2, -3, 0)$: row 1 gives $-2 + 6 + 0 = 4$ and row 2 gives $-4 + 9 + 0 = 5$. Check one more member, at $t = 1$, which is $(1, -1, 1)$: row 1 gives $1 + 2 + 1 = 4$ and row 2 gives $2 + 3 + 0 = 5$. The whole line solves the equation.

Two free variables

Solve $A\mathbf{x} = \mathbf{0}$ for

$$ A = \begin{bmatrix} 1 & 2 & -1 & 3 \\ 2 & 4 & -1 & 8 \end{bmatrix} $$

Subtract $2$ times row 1 from row 2, giving row 2 equal to $(0, 0, 1, 2)$, then add that row to row 1:

$$ \begin{bmatrix} 1 & 2 & 0 & 5 \\ 0 & 0 & 1 & 2 \end{bmatrix} $$

Pivots sit in columns 1 and 3, so $x_2$ and $x_4$ are free. The rows give $x_1 = -2x_2 - 5x_4$ and $x_3 = -2x_4$. Set $x_2 = s$ and $x_4 = t$ and split the result into one vector per parameter:

$$ \mathbf{x} = s\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + t\begin{bmatrix} -5 \\ 0 \\ -2 \\ 1 \end{bmatrix} $$

Check each vector against both rows of $A$. For the first: $-2 + 2 - 0 + 0 = 0$ and $-4 + 4 - 0 + 0 = 0$. For the second: $-5 + 0 + 2 + 3 = 0$ and $-10 + 0 + 2 + 8 = 0$. The solution set is a plane through the origin in $\mathbf{R}^4$.

Since $A$ has more columns than rows, nontrivial solutions were guaranteed before any arithmetic.

Practice

The first drill is the homogeneous case: decide whether only the trivial solution exists, and produce the nontrivial solutions when they do.

The second drill asks for the description of a general solution set, with the basic variables written in terms of the free ones.

Videos

The MIT lecture solves a homogeneous system and names the special solutions that come from setting one free variable to $1$. Watch how the count of free variables is read straight off the pivot pattern.

Quiz

Five items on homogeneous systems and parametric solution sets.