Solving and Characterising Linear Systems

A linear system $A x = b$ has exactly one of three outcomes: no solution, exactly one, or infinitely many. Elimination finds them, and the shape of the reduced system says which case holds and why. Two of those cases occur in linear programming: an infeasible program is a system with no solution, and a program with many optima has a solution set with a free direction.

Definition

For $A \in R^{m \times n}$ and $b \in R^{m}$ , the system $A x = b$ is consistent when at least one $x$ satisfies it and inconsistent otherwise. Gaussian elimination applies row operations, swapping two rows, scaling a row by a nonzero constant, adding a multiple of one row to another, none of which changes the solution set, reducing $[A ∣ b]$ to row echelon form. Exactly one of three cases holds: a pivot in the augmented column alone means no solution; a pivot in every variable column means exactly one; a variable column without a pivot is free, and the system has infinitely many solutions forming $x = x_{p} + (combinations of the null directions)$ .

Formal statement

Row operations preserve the solution set; in echelon form, a pivot in the augmented column alone $\Rightarrow$ inconsistent; a pivot in every variable column $\Rightarrow$ unique; a pivot-free variable column $\Rightarrow$ infinitely many.

Assumptions and scope

Row operations preserve the solution set exactly. Scaling by zero is not permitted, because it destroys information and can turn an inconsistent system into a consistent-looking one.
More equations than unknowns does not imply inconsistency, and fewer does not imply infinitely many. Only the pivot structure decides, since equations may be redundant.
A free variable means infinitely many solutions over the reals. It does not mean the variable is unconstrained: the remaining variables are determined by whatever value it takes.
Consistency is a property of the pair $(A, b)$ , not of $A$ alone. The same coefficient matrix can be consistent for one right-hand side and inconsistent for another.
The three cases are exhaustive and mutually exclusive for a linear system over the reals. A system cannot have exactly two solutions.

Worked material

Example

The three cases, on nearly the same system

Three systems in two unknowns, differing only in the last row.

Unique. $x + y = 3$ and $x - y = 1$ . Subtracting gives $2 y = 2$ , so $y = 1$ and $x = 2$ . Both variable columns carry a pivot: exactly one solution, $(2, 1)$ .

No solution. $x + y = 3$ and $2 x + 2 y = 7$ . The second row is twice the first on the left but not on the right. Subtracting twice the first from the second gives $0 = 1$ . A pivot in the augmented column alone: inconsistent.

Infinitely many. $x + y = 3$ and $2 x + 2 y = 6$ . Now the second row is exactly twice the first, and subtracting leaves $0 = 0$ . No new information. One pivot for two variables, so $y$ is free:

x = 3 - y, y arbitrary,

or as a set, $(3, 0) + y (- 1, 1)$ for any $y$ .

What changed. Only the right-hand side of the second equation, from $7$ to $6$ . Consistency is a property of the pair $(A, b)$ , not of $A$ alone. The same coefficients gave no solutions and then infinitely many.

Contrast

What decides the case, and what does not

	Decides the case	Does not decide it
Evidence	Pivot structure after elimination	Count of equations vs unknowns
Inconsistent	A pivot in the augmented column alone	Having more equations than unknowns
Unique	A pivot in every variable column	Being square
Infinitely many	A variable column with no pivot	Having fewer equations than unknowns

Why counting fails. Equations can repeat one another, as in the worked example above: three equations, three unknowns, and one of them redundant. They can also contradict one another while being few in number. The count says how many statements were written down, not how many independent restrictions they impose.

The square case especially. A square system feels as though it should have exactly one solution, and often does, but only when its columns are independent. $x + y = 1$ with $2 x + 2 y = 2$ is square and has infinitely many solutions; the same pair with right-hand side $3$ is square and has none.

What to do instead. Reduce, then look. The reduced form is short and it is decisive, and it takes less time than arguing from shape.

Common errors

Common misconception

The number of equations against the number of unknowns decides how many solutions a system has: more equations than unknowns means no solution, fewer means infinitely many.

Common misconception

Any manipulation of the rows of a system is safe, because rearranging equations cannot change what solves them, so scaling a row by zero, or adding a row to itself and replacing both, is just tidying.

Related units

Requires

Matrices as Operators

Connected

Extreme Points and Basic Feasible Solutions (part of)
The Row and Column Pictures (suggested next)

Learn this topic

Solving and Characterising Linear Systems

Used in

Foundations for Operational Research

Sources

Introduction to Linear Algebra (2016)

Solving and Characterising Linear Systems

Assumptions and scope

Worked material

The three cases, on nearly the same system

What decides the case, and what does not

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history