# 2.2 The Idea of Elimination

## Abstract

We have made a point that the central problem of linear algebra is solving linear equations. A systematic way to solve linear equations is “Elimination”. And in this post we will inspect “Elimination”.

**keywords**: *Elimination,Linear Equations,Upper Triangular System, Back Substitution, Triangular, Pivot, Multiplier, Permutaion, Sigular*

## The Map of Concepts

## Elimination

### What is “Elimination”

Elimination is a method to solve a system of linear equations, let’s take a $2\times2$ linear equations as an example:

– Before elimination

$$

\begin{eqnarray}

x-2y&=1 \tag{2.2.1a}\newline

3x+2y&=11\tag{2.2.1b}

\end{eqnarray}

$$

– After elimination

$$

\begin{eqnarray}

x-&2y&=1 \tag{2.2.1a}\newline

0x+&8y&=8\tag{2.2.1c}

\end{eqnarray}

$$

We have talked about how to eliminate in a high school way last post. The equation (2.2.1c) is the result of subtracting 3 times (2.2.1a) from (2.2.1b).

The goal of elimination is to produce an *upper triangular system*, and this *upper triangular system* is a middle in the process of solving linear equations. After *elimination*, *Back Substitution* will be used to *upper triangular system* of any size, and in the end we will get the solutions of the system of linear equations.

*Notice*: Different systems of linear equations may have the same solutions, but they are different things. For example, We can draw equation (2.2.1a)(2.2.1b)(2.2.1c) in a row picture, there are three lines in a 2-dimension plane:

– Before elimination

– After elimination

Two figures, each of them contains a pair of lines, and they have a same intersection at point $(3,1)$. So they have the same solutions, this can also be an evidence for the correctness of elimination. However, they are different systems.

### A Process of Elimination

Elimination, What we talked above, is a process of getting a new set of equations, which is easier to calculate the solutions. Addition and multiplication are foundamental operations of linear combination. And we may have an intuitive feeling that elimination mast have relevance to linear combination.

Eliminating $x$ is the key step of elimination in this chapter. To get a triangular system, we must eliminate something, without changing the solutions. We used a multiplier $3$ to produce equation (2.2.1c). Why it is $\ell =3$, but not 1, 2 or 4. That is because the pivot of equation(2.2.1a) is 1, which is the coefficient of the entry $1x$ in equation (2.2.1a). The second equantion (2.2.1b) contains $3x$, so the $\ell$ should be $3$ and then substract 3 times equantion (2.2.1a) from equantion (2.2.1b) to cancel $x$ from the seconde equation (2.2.1b). Then we get triangular equations.

### “Multiplier”, $\ell$, Has a Big Trap

If the equantions change to

$$

\begin{aligned}

4x-8y&=4 \newline

3x+2y&=11

\end{aligned}\tag{2.2.2}

$$

How can we eliminate $x$ from the second equantion of (2.2.2)?

The pivot of the first equation of (2.2.2) is $4$ and the coefficient of $x$ in second equation is $3$, to cancel $x$ in the second equation we would like to change $4$ to $3$ in first equation. So we get the multiplier:

$$

\ell=\frac{3}{4}=\frac{\text{coefficient of target entry}}{\text{pivot}}\tag{2.2.3}

$$

The target is the entry that should be eliminated to get triangular coefficients.

$$

\begin{aligned}

\text{Pivot}&= \text{ First nonzero in the row that does the elimination }\newline

\text{Multiplier}&=\text{ Entry to eliminate divide by pivot}

\end{aligned}

$$

The definition of pivot is not so strict. “The first nonzero coefficient in the row that does the elimination” may not the pivot, because sometimes we should exchange rows before elimination.

Important information: *Remember that, we do division here.*

Division always imply that there are some problems in this process. If there are no problems in process of elimination, pivots will be on the diagonal of the triangle (the triangle matrix after elimination) after elimination.

All above are extremely humble problems. To understand elimination, we should keep our goal in mind, that is to get triangular coefficients matrix. Elimination is a systematic way to solve a system of equations. To understand the whole process of elimination, we have to discuss in what condition the elimination will fail.

## Breakdown of Elimination

Normally, elimination produces the pivots that take us to the solutions. But elimination may fail, for instance, when pivot is zero, we can never divide a number by zero to calculate the multiplier, then failure happens. This kind of failures are unavoidable. There are three examples for three different conditions:

### No Solution to $0y=8$

$$

\begin{aligned}

x-2y&=1 \newline

3x-6y&=11

\end{aligned}\tag{2.2.4}

$$

As the process we discribe above, we choose the coefficient of the fist entry $x$ of first equaion, $1$, as the first pivot. Then we use the multiplier $\ell=\frac{3}{1}=3$ to times the first equantion of (2.2.4) and then substract the result fron the second equantion of (2.2.4):

$$

\begin{aligned}

x-2y&=1 \newline

0y&=8

\end{aligned}\tag{2.2.5}

$$

Aha, there is no solution to equation $0y=8$ . And this system of equations have no solution for ever. We can also see the condition in row picture or column picture

– In row picture:

*There is no intersection for two parallel lines — No Solution*

- In column picture:

*There is no linear combination of two vectors, that are in the same direction, which can produce a new vector of different direction — No Solution*

### Too many Solution to $0y=0$

The second example is similar with the first one, but the right side of the equation is changed:

$$

\begin{aligned}

x-2y&=1 \newline

3x-6y&=3

\end{aligned}\tag{2.2.6}

$$

With the same steps as we described above we can get:

$$

\begin{aligned}

x-2y&=1 \newline

0y&=0

\end{aligned}\tag{2.2.6}

$$

That is to say, any real number is the solution of $y$, and so $x$ has also infinite solutions. The row picture or column picture can be imagined spontaneously：

– The row picture

*The two equations are in a same line, So they have infinite intersections*

- The column picture

*Three vectors are in same direction, So, there are infinite solutions to the equations*

In this condition, we say $y$ is **free**

### Exchanging Equations to Get Nonzero Pivots

This example is a little embarrassing, it looks like a bad guy, but he is a real good one.

$$

\begin{aligned}

0x-2y&=1 \newline

3x-2y&=5

\end{aligned}\tag{2.2.7}

$$

When we look at the first equation, the first entry is 0, then the pivot is 0, we can never divide any number by 0, so these equations can not be solved.

That is totally wrong, the order of equations in the system can be changed to whatever you want. If we put the second equation to the first row, and take the first equation down. We get:

$$

\begin{aligned}

3x-2y&=5 \newline

0x-2y&=1

\end{aligned}\tag{2.2.8}

$$

Bingo! we get a triangular form just by exchanging!

>

1. Failure: For $n$ equations we do not get $n$ pivots

2. Elimination leads to an equation $0\neq 0$ (no solution) or $0=0$ (many solutions)

3. Success comes with $n$ pivots. But we may have to exchange the $n$ equations

To the coefficient matrix, system (2.2.6) and (2.2.7) are singular – there is no second pivot, and in this condition there many be no solution or infinite solutions. Example (2.2.8) has a full set pivots and exactly one solution.

## Three Equations in Three Unknowns

All the steps in elimination of $2\times 2$ equations can be used in $3\times 3$ equations, or even more equantions in more unknowns. We only use a $3\times 3$ equations as an example:

$$

\begin{eqnarray}

2x+4y-2z&=2\tag{2.2.9a}\newline

4x+9y-3z&=8\tag{2.2.9b}\newline

-2x-3y+7z&=10\tag{2.2.9c}

\end{eqnarray}

$$

Step 1: $(2.2.9b)-2\times(2.2.9a)$ get a new equation and replace the second equation:

$$

\begin{eqnarray}

2x+4y-2z&=2\tag{2.2.9a}\newline

1y+1z&=4\tag{2.2.9d}\newline

-2x-3y+7z&=10\tag{2.2.9c}

\end{eqnarray}

$$

Step 2: $(2.2.9c)+\times(2.2.9a)$ get a new equation and replace the second equation:

$$

\begin{eqnarray}

2x+4y-2z&=2\tag{2.2.9a}\newline

1y+1z&=4\tag{2.2.9d}\newline

1y+5z&=12\tag{2.2.9e}

\end{eqnarray}

$$

Untill now we have eliminated all first entry except the first equation. And then to get a triangular form, we are going on to eliminate the second entry of equations in the third row:

Step 3: $(2.2.9c)-\times(2.2.9d)$ get a new equation and replace the second equation:

$$

\begin{eqnarray}

2x+4y-2z&=2\tag{2.2.9a}\newline

1y+1z&=4\tag{2.2.9d}\newline

4z&=8\tag{2.2.9f}

\end{eqnarray}

$$

If we rewrite the equantions in matrix steal, we have the original equantion:

$$

A\vec{x}=\begin{bmatrix}

2&4&-2\newline

4&9&-3\newline

-2&-3&7

\end{bmatrix}\vec{x}=

\begin{bmatrix}

2\newline

8\newline

10

\end{bmatrix}=\vec{b}\tag{2.2.10}

$$

and, after elimination, it changes to:

$$

U\vec{x}=\begin{bmatrix}

2&4&-2\newline

0&1&1\newline

0&0&4

\end{bmatrix}\vec{x}=

\begin{bmatrix}

2\newline

4\newline

8

\end{bmatrix}=\vec{c}\tag{2.2.11}

$$

Elimination are done here. We get three pivot on the diagonal of $U$. Then we do back substitution from $U\vec{x}=\vec{c}$

In conlusion, we do elimination only want to get a **triangular matrix**:

$$

\begin{bmatrix}

x&x&x&x\newline

x&x&x&x\newline

x&x&x&x\newline

x&x&x&x

\end{bmatrix}

\to

\begin{bmatrix}

x&x&x&x\newline

&x&x&x\newline

&x&x&x\newline

&x&x&x

\end{bmatrix}

\to

\begin{bmatrix}

x&x&x&x\newline

&x&x&x\newline

& &x&x\newline

& &x&x

\end{bmatrix}

\to

\begin{bmatrix}

x&x&x&x\newline

&x&x&x\newline

& &x&x\newline

& &&x

\end{bmatrix}

$$

## Conclusion

- A linear system ($A\vec{x}=\vec{b}$) becomes upper triangular ($U\vec{x}=\vec{c}$) after elimination
- We subtract $\ell_{ij}$ times equation $j$ from equation $i$. to make the $(i,j)$ entru zero
- $\ell_{ij}=\frac{\text{ entry to eliminate in row }i}{\text{pivot in row }j}$ so pivot can not be zero
- A zero in pivot position can be repaired if there if there is a nonzero below it.
- The upper triangular system is solved by back substitution(starting at the bottom)
- When breakdown is permanent, the system has no solution or infinitely many.

## Reference

1.Strang G, Strang G, Strang G, et al. Introduction to linear algebra[M]. Wellesley, MA: Wellesley-Cambridge Press, 1993.

## Leave a Reply