In this article, I describe Gauss’ algorithm for solving *n* linear equations with *n* unknowns. I also give a sample implementation in C.

#### The Problem

Let’s say you want to solve the following system of *3* equations with *3* unknowns:

Humans learn that there a two ways to solve this system. Reduction and substitution. Unfortunately, neither of these methods is suitable for a computer.

A simple algorithm (and the one used everywhere even today), was discovered by Gauss more than two hundred years ago. Since then, some refinements have been found, but the basic procedure remains unchanged.

#### Gaussian Elimination

Start by writing the system in matrix form:

If you recall how matrix multiplication works, you’ll see that’s true. If not, it’s enough to notice how the matrix is written: the coefficients of *x*, *y* and *z* are written, side by side, as the rows of a 3×3 matrix; *x*, *y* and *z* are then written as rows of a 3×1 matrix; finally, what’s left of the equality sign is written one under the other as a 3×1 matrix.

So far, this doesn’t actually help, but it does make the following process easier to write. The goal is, through simple transformations, to reach the system, where *a*, *b* and *c* are known.

How do you transform the initial system into the above one? Here’s Gauss’ idea.

Start with the initial system, then perform some operations to get *0*s on the first column, on every row but the first.

The operations mentioned are multiplying the first rows by *-3/2* and substracting it from the second. Then multiplying the first rows by *-1* and substracting it from the third. What is *-3/2*? It’s first element of the second row divided by the first element of the first row. And *-1*? It’s the first element of the third row divided by the first element of the first row. **NOTE** The changes to row 1 are never actually written back into the matrix.

For now we’re done with row 1, so we move on to row 2. The goal here is to get every row on the second column under row 2 to 0. We do this by multiplying the second rows by *4* (i.e. *2 / (1 / 2)*) and substracting it from the third rows.

Now it’s easy to find the value of *z*. Just multiply the third column by *-1* (i.e. *-1/1*).

**ERRATA**: The *7* in the above matrix should be an *8*.

Knowing the value of *z*, we can now eliminate it from the other two equations.

Now, we can find the value of *y* and eliminate *y* from the first equation.

And, finally, the value of *x* is:

And with that, we’re done.

#### The Programme

Unfortunately, this is easier said than done. The actual computer programme has to take into account divisions by zero and numerical instabilities. This adds to the complexity of **forwardSubstitution()**.

Here’s the code in C (gauss.c):

#include

int n;

float a[10][11];

void forwardSubstitution() {

int i, j, k, max;

float t;

for (i = 0; i < n; ++i) {
max = i;
for (j = i + 1; j < n; ++j)
if (a[j][i] > a[max][i])

max = j;

for (j = 0; j < n + 1; ++j) {
t = a[max][j];
a[max][j] = a[i][j];
a[i][j] = t;
}
for (j = n; j >= i; –j)

for (k = i + 1; k < n; ++k)
a[k][j] -= a[k][i]/a[i][i] * a[i][j];
/* for (k = 0; k < n; ++k) {
for (j = 0; j < n + 1; ++j)
printf("%.2f\t", a[k][j]);
printf("\n");
}*/
}
}
void reverseElimination() {
int i, j;
for (i = n - 1; i >= 0; –i) {

a[i][n] = a[i][n] / a[i][i];

a[i][i] = 1;

for (j = i – 1; j >= 0; –j) {

a[j][n] -= a[j][i] * a[i][n];

a[j][i] = 0;

}

}

}

void gauss() {

int i, j;

forwardSubstitution();

reverseElimination();

for (i = 0; i < n; ++i) {
for (j = 0; j < n + 1; ++j)
printf("%.2f\t", a[i][j]);
printf("\n");
}
}
int main(int argc, char *argv[]) {
int i, j;
FILE *fin = fopen("gauss.in", "r");
fscanf(fin, "%d", &n);
for (i = 0; i < n; ++i)
for (j = 0; j < n + 1; ++j)
fscanf(fin, "%f", &a[i][j]);
fclose(fin);
gauss();
return 0;
}
[/sourcecode]
In the above code, the first two for-s of **forwardSubstitution()**, just swap two rows so as to diminish the possibilities of some bad rounding errors. Also, if it exists with a division by zero error, that probably means the system cannot be solved.

And here’s the input file for the example (gauss.in) (save it as gauss.in):

`3`

2 1 -1 8

-3 -1 2 -11

-2 1 2 -3

That’s it. Good luck. Always open to comments.

2008-11-15 at 23:34

thx a lot

2008-11-23 at 23:36

Thanks buddy…

2009-01-15 at 5:06

hi, i’m new to programming, does this code involve a pivoting? is it possible that you could help me doing a gaussian elimination for a 3000*3000 matrix with initial assumption at 1, thank you so much.

2009-05-26 at 13:53

I NEED ONLY THE GENERAL CODE ?

2009-05-26 at 14:40

still i cant get what i want i need only the code for gauss elimnation in solution of equation?

2009-05-26 at 23:14

Thanks, very helpful :)

2009-06-20 at 22:56

thank you

but when i run the program 2 warning errors appear

parameter ‘argc’ is never used

parameter ‘argv’ is never used

could you help me in that

waiting replay

2009-08-10 at 10:22

It is not a mistake, when the arguments argc, and *argv are not used. They are functioning as program parameters, when running this program from command line.

You can simply delete these two declarations and program will work too, but without warnings, while compiling.

OR you can ignore these two warnings.

2009-12-22 at 9:40

Thankx a lot;;

2010-02-07 at 4:33

How much longer should you expect Gaussion eliminjation to work on a system of 1000 equaitons versus a system of 500 equation?

2010-02-21 at 16:20

HI,

VERY GOOD ,I AM A STUDENT COMPUTER SCIENCE.

I WANT TO BE A PROGRAMMER LIKE YOU.

TTTTTTTTTHHHHHHAAAAAAANNNNNKKKKYYYYYOOOOOOOUUU!

2010-05-27 at 12:51

you know what, i think (and i test) it works, but my teacher doesn’t think the same. . .

i thought i’ve done a greateful test instead he said it was not ok because <>. . . so i got 3/10 ;-(

2010-06-06 at 20:24

hi!

1) can u update the code with elaborate comments? not being a computer science student makes it difficult to see how your code is working.

2)do you have any suggestions to make this code work on a parallel processor for 1000s of equations?

2010-11-08 at 18:54

hey it was very help ful thank u soo much

2010-11-11 at 23:53

Hey,

You need to take more car about zeros in your coefficients matrix. The question is “is it always possible to upper triangulate using your program?”. I mean there would be some conditions that is not processable by your code.

Be successful!

2011-09-10 at 14:53

XMAX and CHARLIE two beautiful tasks just ready for you to go and solve them on spoj.pl :) Great practise of GE.

2011-09-14 at 6:08

Does anyone know the name of the author of this code? I used it as part of my graduate project and would like to give credit.

Thanks, and, excellent code.

2011-10-24 at 16:16

check for no solutions and many solution

2012-02-20 at 19:29

I used this code to perform least squares regressions on data points. However I ran into a bug when varying the degree of the fit polynomial.

It is possible to run in a division by zero through these code lines:

for (j = i + 1; j a[max][i])

max = j;

changing them to this fixed the problem for me:

for (j = i + 1; j abs(a[max][i]))

max = j;

2012-02-20 at 19:32

ok apparently formatting failed…

this is the original lines:

for (j = i + 1; j < n; ++j)

if (a[j][i] > a[max][i])

max = j;

I changed them to this:

for (j = i + 1; j < n; ++j)

if (abs(a[j][i]) > abs(a[max][i]))

max = j;

2012-02-28 at 6:00

computer repair…[…]Gaussian Elimination « Computer programming[…]…

2012-04-29 at 5:45

masked…[…]Gaussian Elimination « Computer programming[…]…

2013-01-03 at 5:38

Thanku so much.

Its very much helpful for me

2013-01-03 at 13:21

This seems to work OK for specific inputs, like the ones provided in the example above. But if I change the input file to the following, the results provided are incorrect:

3

2 1 -1 8

-3 -1 2 -9

-2 1 2 -2

2013-02-24 at 22:49

I don’t know if it’s just me or if perhaps everybody else encountering issues with your

blog. It appears as if some of the text in your

content are running off the screen. Can somebody

else please provide feedback and let me know if

this is happening to them too? This might be a problem with my web browser because I’ve had this happen previously. Thanks

2014-09-08 at 15:21

When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get several emails with the same comment.

Is there any way you can remove people from that service?

Many thanks!

2014-11-11 at 2:16

[…] with Code Explanation […]

2014-12-29 at 17:18

guys thank you!!! but i cannot open the ( gauss.in) thanks a lot!!!!!!

2015-03-17 at 23:11

i couldnt download gauss.in file

2015-07-27 at 16:55

[…] Gaussian Elimination […]

2015-09-04 at 5:40

[…] : tutorial with implementation, tutorial with implementation Gaussian Elimination Pollard Rho Integer Factorization, problem Topological […]

2016-01-10 at 14:08

[…] Discussion: Gaussian Elimination is used to solve linear equations. This method can be applied to variety types of problem. The basic of this method can be found in wiki and here […]

2016-04-21 at 0:45

i need more programs using c++ code to solves using gaussian elimination…. the program should be user friendly,the size of matrix should be determined by the user( at run time) and finally the appropriate error should be provided to the user when the system has no solution or inappropriate data is fed by the user. help me !!!!!