Elimination

Elimination solves equations by taking one from another. Watch what that does to the lines: one turns, and the crossing stays.

Clear one unknown

Here are the two equations from Two pictures of a linear system:

If the second equation had no $x$ in it, it would give $y$ at once. So take a multiple of the first equation away from the second, chosen to remove the $x$. The first equation has $2x$ and the second has $1x$, so take away one half of the first:

The $2$ that we divided by is the pivot: the first number in the row we keep. The $\tfrac12$ is the multiplier: the number below the pivot, divided by the pivot. I’ll write the multiplier that clears row $p$ using row $q$ as

Here $\ell_{21}=1/2$. The new second row starts with 0, and its first nonzero number, $1.5$, is the second pivot.

Back substitution

The system now looks like a staircase:

Solve from the bottom up. The last equation gives $y=2$. Put it into the first: $2x-2=4$, so $x=3$. Solving from the bottom row upwards like this is back substitution.

Why the answer never moves

Look at the picture at the top of the page again. The second line turned, but it turned about the crossing point, so the answer stayed $(3,2)$.

That is no accident. Any pair that makes both old equations true also makes the new one true, because the new equation is the old second one minus half the old first one. And we can go back: adding half of the first equation to the new one gives the old second equation again. So the old system and the new system have exactly the same solutions. Elimination does not change the problem. It changes how the problem is written, until the answer can be read off.

Three equations

The same steps work for any size. Take three equations in three unknowns:

The first pivot is the 1 in front of $x$. The second row has $3x$, so $\ell_{21}=3$: take 3 times row 1 from row 2, which leaves $2y-2z=6$. The third row has no $x$, so $\ell_{31}=0$. Now the second pivot is the 2 in front of $y$. The third row has $4y$, so $\ell_{32}=4/2=2$: take 2 times the new row 2 from row 3, which leaves $5z=-10$.

Watch the same steps on the table of numbers.

Every number below the diagonal is now zero. A matrix like that is upper triangular, and I’ll call it $\mathbf{U}$:

Its diagonal holds the three pivots, 1, 2 and 5. Back substitution then runs from the bottom: $5z=-10$ gives $z=-2$; $2y-2(-2)=6$ gives $y=1$; and $x+2(1)+(-2)=2$ gives $x=2$. Check in the original equations: $2+2-2=2$, $6+8-2=12$ and $4-2=2$.

When elimination breaks

A zero pivot. Take $2y=4$ and $3x+y=5$. The first equation has no $x$, so the first pivot is 0, and dividing by it is impossible. The fix is to swap the two equations, a row exchange. Now the system is $3x+y=5$ and $2y=4$: already a staircase. So $y=2$ and $3x+2=5$, which gives $x=1$.

No fix. Take $x+y=2$ and $2x+2y=5$. The multiplier is 2, and taking twice the first from the second leaves $0=1$. That is false whatever $x$ and $y$ are, so there is no solution: the lines are parallel. With $2x+2y=4$ instead, the same step leaves $0=0$. That is always true, so it puts no limit on anything, and there are infinitely many solutions: both equations are the same line. In both cases a pivot came out 0 and no lower row could replace it. A system like that is called singular.

Steps as matrices

Each step is itself a matrix. Taking 3 times row 1 from row 2 is the same as multiplying on the left by

It is the identity with $-\ell_{21}$ placed in row 2, column 1. Row 2 of $\mathbf{E}_{21}\mathbf{A}$ is $-3$ times row 1 of $\mathbf{A}$ plus row 2, exactly the step. Multiplying matrices comes from Matrix multiplication. With one such matrix for each step, the whole of elimination is

where here $\mathbf{E}_{31}$ is the identity, because $\ell_{31}=0$, and $\mathbf{E}_{32}$ holds $-2$ in row 3, column 2. The page LU factorisation runs these steps backwards.

How much work it takes

How long does elimination take on a big system? Count the multiply-and-subtract steps. With $n$ equations, clearing the first column changes about $n$ numbers in each of about $n$ rows, so about $n^2$ steps. The next column needs about $(n-1)^2$, then $(n-2)^2$, and so on. Added up, that is about

For $n=1000$ equations, that is about $3.3\times10^8$ multiply-and-subtract steps: a fraction of a second on a laptop. But double $n$ and the work grows eight times.

Worked example

1. Two equations. $2x-y=4$, $x+y=5$. Pivot 2, multiplier $\tfrac12$, second pivot $1.5$. So $1.5y=3$, $y=2$, then $x=3$.
2. Three equations. Multipliers 3, 0 and 2; pivots 1, 2 and 5; $z=-2$, $y=1$, $x=2$.
3. A multiplier. What multiplier clears a 6 below a pivot of 2? $6/2=3$.
4. A zero pivot. $2y=4$, $3x+y=5$: exchange the rows, then $y=2$ and $x=1$.
5. A zero row. If a step leaves $0=0$, one unknown is free and there are infinitely many solutions. If it leaves $0=1$, there are none.
6. Predict. Does the crossing point move while elimination runs? No: each step keeps exactly the same solutions.

Where you’ll meet this

Most programs that solve a dense system run elimination, usually in the form of the page LU factorisation. A circuit simulator solves one system for the voltages at all the junctions of a chip. Programs that work out how a bridge or an aircraft wing bends cut the shape into small pieces and solve a system with one equation per piece, often hundreds of thousands. The solver in SciPy, a free Python library, does the same.

Reference card