Solving and Characterising Linear Systems

Two equations can carry the same information written differently. Elimination works because it changes the writing without changing which points satisfy the system, and every operation that preserves the solution set is reversible, which is the test for whether a move is legal at all.

What follows from that is a complete answer to a question the arithmetic alone does not settle: a linear system has no solution, exactly one, or infinitely many. Never two. The reduced form tells you which, and the count of equations against unknowns does not.

The canonical intuition states that row operations preserve the solution set and that the reduced form determines which of three cases holds. This block shows the three cases side by side in the same three variables.

A contradiction. Reducing $x+y+z=3$, $2x+2y+2z=7$ gives the row $0=1$. No assignment of $x,y,z$ satisfies it, so the solution set is empty. The first two equations were inconsistent from the start; reduction made that visible as a row with zero coefficients and a nonzero right-hand side.

A unique solution. Reducing $x+y=3$, $y+z=5$, $x+z=4$ gives pivots in all three columns and the solution $(1,2,3)$. Every variable is pinned, so no choice remains.

A line of solutions. Reducing $x+y+z=6$, $2x+2y+2z=12$ leaves one pivot and two free variables. Taking $y$ and $z$ as free gives $x=6-y-z$, so the solutions form a plane: the particular solution $(6,0,0)$ plus any combination of the directions $(-1,1,0)$ and $(-1,0,1)$.

The count that distinguishes the cases is the number of pivots. With $n$ variables and no contradictory row, $r$ pivots leave $n-r$ free variables, and the solution set is a flat of dimension $n-r$: a point when $r=n$, a line when $r=n-1$, and so on.

The third case is where a linear program can have several optimal plans, since the objective may be constant along the directions the free variables open up.

Three things in the definition above are worth slowing down on, because each is where the reasoning usually goes wrong.

"None of which changes the solution set" is the whole licence. Every row operation is reversible, undo a swap by swapping back, a scaling by scaling by the reciprocal, an addition by subtracting the same multiple. That reversibility is what guarantees no solutions are lost or gained along the way, and it is the test for whether a move you are tempted to make is legal at all. Multiplying a row by zero is not: nothing undoes it, and the information in that row is gone.

The cases are read off pivot positions, not off counting. The augmented column holding a pivot means some row says $0=c$ with $c\ne 0$, which no $x$ satisfies. A pivot in every variable column means back-substitution determines each variable in turn. A variable column without one means that variable was never pinned, and choosing its value forces the rest. Nothing in that reading consults how many equations there were.

"Infinitely many" has a shape. The solution set is not a scattered collection. It is one particular solution plus every combination of the directions the free variables generate. A point plus a flat through it. Describing that set means naming the free variables and giving the directions, not producing one member of it and stopping.

These three cases are exhaustive and mutually exclusive: a linear system never has exactly two solutions, because the moment two distinct solutions exist, every point on the line between them is a solution too.

Apply these steps to the augmented matrix $[A\mid b]$.

Choose a pivot. Take the leftmost column not yet used, and find a row with a nonzero entry in it. Swap that row into position if needed.
A zero column is skipped entirely: it carries no pivot, and its variable will be free.

Clear below. Add multiples of the pivot row to the rows beneath it so every entry below the pivot becomes zero.
This is the only operation that changes other rows, and it preserves the solution set because it adds a true equation to a true equation.

Repeat down and to the right. Move to the next row and the next unused column, and take the next pivot.

Read the shape. Once no rows remain, inspect the result. A row of the form $00\cdots 0\mid c$ with $c\ne 0$ says $0=c$, so the system is inconsistent and you stop.

Count the pivots against the variables. If every variable column holds a pivot, back-substitute for the unique solution. If any variable column does not, those variables are free.

Describe the set, not a point. With free variables, give a particular solution and the direction each free variable contributes, rather than picking one member and calling it the answer.

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

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

No solution. $x+y=3$ and $2x+2y=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 $2x+2y=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:

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.

Problem. Characterise the solutions of

Goal. Reduce, name the case, and describe the solution set.

Relevant principle. Row operations preserve the solution set; the pivot structure of the reduced form decides the case.

Step 1: clear the first column. Subtract $2\times$ row 1 from row 2, and row 1 from row 3:

Reason: both operations add a multiple of a true equation to another, so nothing about the solution set has changed.

Step 2: clear the third row. Rows 2 and 3 are now identical; subtracting one from the other gives $0=0$.

Reason: the third equation carried no information the second did not. That is redundancy, not contradiction.

Step 3: identify the pivots. Pivots sit in the $x$ column and the $z$ column. The $y$ column has none, so $y$ is free.

Step 4: name the case. A variable column without a pivot, and no row of the form $0=c$ with $c\ne 0$: infinitely many solutions.

Step 5: describe the set. From $z=3$ and $x=4-2y-z=1-2y$:

Result. Infinitely many solutions: the point $(1,0,3)$ plus any multiple of the direction $(-2,1,0)$.

Check. Try $y=2$, giving $(-3,2,3)$. First equation: $-3+4+3=4$. Third: $-3+4+6=7$. Both hold.

Interpretation. Three equations and three unknowns, and yet not a unique solution, because one equation repeated another. Counting equations would have predicted the wrong answer; only the pivots told the truth.

Before the contrast that follows, do one reduction with the steps still in view.

First, subtract $3\times$ the first row from the second. Write what the second row becomes.

Then count the pivots against the variables, and name the case.

Finally, and this is the step most often skipped, describe the solution set rather than producing a point.

---

The second row becomes $0=0$: the equations were the same statement written at different scales, so the second carried nothing new. One pivot serves two variables, $y$ is free, and the case is infinitely many solutions.

The set is $x=5-2y$ with $y$ arbitrary, or

If you answered $(5,0)$, you named one member of the set. That is the error the next section is about: a point is not a description of a line.

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 $2x+2y=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.

1: fully structured. Solve and classify: $2x+y=5$, $x-y=1$.

(a) Reduce the system. (b) How many pivots, and in which columns? (c) Name the case and give the solution.

Check: (a) adding the two equations gives $3x=6$, so $x=2$, then $y=1$; (b) two pivots, one in each variable column; (c) exactly one solution, $(2,1)$.

2: partly structured. Consider $x+3y-z=2$ and $2x+6y-2z=5$.

(a) Reduce. (b) What does the reduced row say? (c) Name the case, and say what would change if the $5$ were a $4$.

Check: (a) subtracting twice the first from the second gives $0=1$; (b) a contradiction. No $x$ satisfies it; (c) no solution. With a $4$ instead, the second row reduces to $0=0$, leaving one pivot for three variables and therefore infinitely many solutions with two free variables.

3: unstructured. A colleague reports: "The model has 40 constraints and 40 variables, so it is square and must have exactly one feasible point. The solver returning 'infeasible' has to be a bug."

Assess the claim and say what you would check.

Check: the reasoning is wrong at every step. Squareness does not imply a unique solution: it implies one only when the columns are independent, and 40 constraints can easily contain redundancy or contradiction. A square system can have no solutions, $x+y=1$ with $x+y=2$ scaled up, or infinitely many, if some constraints repeat others. What to check: reduce the constraint matrix and look at the pivot structure, which will show either a row asserting $0=c$ for nonzero $c$ (genuine infeasibility, and the solver is right) or a variable column without a pivot (a flat of solutions). Note also that a linear program's constraints are usually inequalities, where feasibility is not the same question as solvability of an equality system at all, so the square-system intuition does not transfer even when it is correct about equations.