Elimination

Introduction

Consider the below system of equations.

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

Algebra

The first step to solving this system is eliminating x. Note that x = 2 - 2y - z (from the first equation) and substitute into the second equation.

3x + 8y + z = 12
3(2 - 2y - z) + 8y + z = 12
6 - 6y - 3z + 8y + z = 12
2y - 2z = 6

Now x has been eliminated. But can either y or z be eliminated the same way?

Linear Algebra

Matrix Picture

This system can be expressed in the form Ax = b:

┌      ┐ ┌  ┐   ┌  ┐
│ 1 2 1│ │ x│   │ 2│
│ 3 8 1│ │ y│ = │12│
│ 0 4 1│ │ z│   │ 2│
└      ┘ └  ┘   └  ┘

A -> U

The first step to solving this system is eliminating the first column. This means identifying a pivot and reducing all below numbers to 0. The pivot in this case is the boxed 1 in the top-left.

[1] 2 1
 3  8 1
 0  4 1

In order to eliminate the 3 below the pivot, the pivot's row should be multiplied by some number such that, by subtracting the rows, the transformed row will have a zero in that position. 3 - m1 = 0; m is trivially 3.

   3     8     1
- 1m  - 2m  - 1m
 ___   ___   ___
   0     2    -2

[1] 2 1    [1] 2  1
 3  8 1 ->  0  2 -2
 0  4 1     0  4  1

This process repeats until the matrix is fully eliminated.

[1]  2   1
 0  [2] -2
 0   4   1

4 - 2m = 0
     m = 2

   4      1
- 2m  - -2m
____  _____
   0      5

[1]  2   1    [1]  2   1
 0  [2] -2 ->  0  [2] -2
 0   4   1     0   0   5

This transformed matrix is called U.

┌           ┐
│[1]  2   1 │
│ 0  [2] -2 │
│ 0   0  [5]│
└           ┘

b -> c

Now, to balance the original equation, replicate the subtractions on b. Recall that the multipliers were 3 and 2:

  12
- 2m
____
   6

┌  ┐    ┌  ┐
│ 2│    │ 2│
│12│ -> │ 6│
│ 2│    │ 2│
└  ┘    └  ┘

   2
- 6m
____
 -10

┌  ┐    ┌   ┐
│ 2│    │  2│
│ 6│ -> │  6│
│ 2│    │-10│
└  ┘    └   ┘

Ux = c

The system has been reduced to Ux = c:

┌           ┐ ┌  ┐   ┌   ┐
│[1]  2   1 │ │ x│   │  2│
│ 0  [2] -2 │ │ y│ = │  6│
│ 0   0  [5]│ │ z│   │-10│
└           ┘ └  ┘   └   ┘

x + 2y + z = 2
2y = 2z = 6
5x = -10

Algebraic substitution can now be used to solve; x=2, y=1, z=-2.

Failure of Elimination

Elimination is the process to transform A -> U, where U must have n non-zero pivots for n unknowns.

If the equations align such that a pivot would be 0, you have temporary failure. Re-align the equations and re-eliminate.

If the equations cannot be re-aligned to solve, you hve permanent failure

CategoryRicottone

LinearAlgebra/Elimination