Associated Topics || Dr. Math Home || Search Dr. Math

### Gaussian Elimination

```
Date: 01/11/2000 at 06:47:18
From: Michael Harper
Subject: Gaussian Elimination

I am attempting to do Gaussian elimination and I am completely stuck.
```

```
Date: 01/11/2000 at 13:55:03
From: Doctor Rob
Subject: Re: Gaussian Elimination

Thanks for writing to Ask Dr. Math, Michael.

You are given a system of n or more simultaneous linear equations
involving n unknowns. Pick one of the unknowns, called the pivot
variable. Find an equation in which it appears, called the pivot
equation. Use that equation to eliminate the pivot variable from all
other equations in the following way.

If an equation doesn't contain the pivot variable, leave it alone.

If an equation does contain the pivot variable, subtract the right
multiple of the pivot equation from that equation to make the pivot
variable's coefficient zero.

When you have eliminated the pivot variable from all the rest of the
equations, set aside the pivot equation, and you will have a system of
one fewer simultaneous linear equations involving n-1 unknowns.

Repeat this process, driving down the number of unknowns appearing
until it reaches 0. Any remaining equations must look like c = c for
some constant c, and can be discarded (if not, the original system had
no solution).

Now look at the equations that you set aside and used as pivot
equations. The last equation will allow you to solve for the pivot
variable. Substitute that into all the remaining equations, set it
aside, and repeat. When you are done with this process, you'll have
each pivot variable solved for, and you are done.

Example:

-4*w + 3*x - 4*y -   z = -37
-2*w       - 5*y + 3*z = -20
-w -   x - 3*y - 4*z = -27
-3*w + 2*x + 4*y -   z =   7

Let w be the first pivot variable, and the first equation the first
pivot equation. w appears in the second equation, so we subtract
(-2)/(-4) = 1/2 times the first equation from the second, getting

-2*w           - 5*y +     3*z = -20,
-2*w + (3/2)*x - 2*y - (1/2)*z = -37/2
--------------------------------------
-(3/2)*x - 3*y + (7/2)*z = -3/2

w appears in the third equation so we subtract (-1)/(-4) times the
first equation from the third. w appears in the fourth equation, so we
subtract (-3)/(-4) times the first equation from the fourth. This
leaves

-4*w +    3*x - 4*y -        z = -37
-(3/2)*x - 3*y +  (7/2)*z = -3/2
-(7/4)*x - 2*y - (15/4)*z = -71/4
-(1/4)*x + 7*y -  (1/4)*z = 139/4

Now the last three equations are a system of three equations in three
unknowns, and we treat that similarly. Let x be the next pivot
variable, and the second equation the pivot equation. Since x appears
in the third equation, we subtract (-7/4)/(-3/2) = 7/6 times the
second equation from the third. Since x appears in the fourth equation
we subtract (-1/4)/(-3/2) = 1/6 times the second equation from the
fourth. This leaves

-4*w +    3*x -      4*y -        z = -37
-(3/2)*x -      3*y +  (7/2)*z = -3/2
(3/2)*y - (47/6)*z = -16
(15/2)*y -     16*z = 35

Now the last two equations are a system of two equations in two
unknowns, and we treat that similarly. Let y be the next pivot
variable, and the third equation the next pivot equation. Since y
appears in the fourth equation, we subtract (15/2)/(3/2) = 5 times the
third equation from the fourth. This leaves

-4*w +    3*x -     4*y -         z = -37
-(3/2)*x -     3*y +   (7/2)*z = -3/2
(3/2)*y -  (47/6)*z = -16
(115/3)*z = 115

This completes the first phase.

Now we start with the last equation, and solve for z. This gives
z = 3, and we substitute that into the preceding equations:

-4*w +    3*x -     4*y = -34
-(3/2)*x -     3*y = -12
(3/2)*y = 15/2

The last remaining equation tells us that y = 5, and we substitute
that into the preceding equations:

-4*w +    3*x = -14
-(3/2)*x = 3

The last remaining equation tells us that x = -2, and we substitute
that into the preceding equation:

-4*w = -8

That gives us the value w = 2, and so the solution is

(w,x,y,z) = (2,-2,5,3)

Understood?

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Linear Equations
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search