Linear Algebra · Lesson 05

Elimination

A system can be rewritten as a simpler one with exactly the same solutions. Three moves are enough, and each of them can be undone, which is why nothing is lost and nothing is invented.

Foundations8 min readRevision 1

Read freely. Sign in when you want to save your place.

Sign in to save progress

R_{i} \leftarrow R_{i} + c R_{j}

R_{i} \leftrightarrow R_{j}

Sol (S)

A x = b

Chapter navigation

Prerequisites

Complete Systems of linear equations first.

Intuition

A system can be rewritten as a simpler one with exactly the same solutions. Three moves are enough, and each of them can be undone, which is why nothing is lost and nothing is invented.

A balanced scale stays balanced when both pans are doubled, and pouring the contents of one balanced scale onto another leaves that one balanced too.

Elementary row operations

Three operations may be performed on the equations of a system: exchange two of them, multiply one of them by a non-zero number, or add a multiple of one equation to another. Multiplying by zero is excluded, and the reason is that it cannot be undone.

\begin{aligned}&E_i\leftrightarrow E_j\\ &E_i\to cE_i\quad(c\neq 0)\\ &E_i\to E_i+cE_j\end{aligned}

Why the moves are safe

Write $\operatorname{Sol}(S)$ for the set of all lists that solve the system S.
Two systems are equivalent when $\operatorname{Sol}(S)=\operatorname{Sol}(S')$ , whatever they look like on the page.
Each operation is undone by another of the same kind: exchange back, multiply by $1/c$ , or add $-c$ times the same equation.
Multiplying an equation by 0 turns it into $0=0$ , which every list satisfies, so solutions would be gained and the move is barred.

Adding the first equation to the second replaces it with $2x=4$ , the green line. It is a different line, and it still passes through the same crossing point — which is exactly what it means for the move to keep every solution.

Row operations preserve the solutions

S\to S'\implies\operatorname{Sol}(S)=\operatorname{Sol}(S')

Take any solution of the original. It satisfies every equation the operation used, so it satisfies the equation the operation produces, which puts it among the solutions of the new system. The operation has an inverse of the same kind, so running the identical argument backwards puts every solution of the new system among those of the old.

Proof steps

\mathbf{x}\in\operatorname{Sol}(S)

Take any list of numbers that solves the original system.

E_i\to E_i+cE_j

Consider the third operation. The other two are simpler instances of the same argument.

\mathbf{x}\ \text{satisfies}\ E_i\ \text{and}\ E_j

It solves the whole system, so in particular it satisfies these two equations.

\operatorname{Sol}(S)\subseteq\operatorname{Sol}(S')

Adding equals to equals keeps an equality, so $\mathbf{x}$ satisfies the replacement equation and every equation left untouched.

\operatorname{Sol}(S')\subseteq\operatorname{Sol}(S)

The inverse operation $E_i\to E_i-cE_j$ is of the same kind, so the same argument runs the other way and the two sets contain each other.

Applications

Practice

Three moves, and only three

E_2\to E_2+5E_1

The third move. Equation 1 is unchanged; only equation 2 is replaced.

Try it

Which operation on a system is not permitted?