Solution of a System of Linear Equation by Gaussian Elimination

First Step: -

Consider the following system of m linear equations (or set of m simultaneous linear equations) in n unknown x1, x2 - - - - - - xn.

a11x1 + a12x2 + - - - - - - + a1nxn = b1

a21x1 + a22x2 + - - - - - - + a2nxn = b2

… …. …. ….. … … .. .. . .. . .. .. . .. .. .. .. . .. System (1)

. … . .. .. . .. .. . .. .. . .. . .. . .. .. . .. . .. . .. ..

am1x1 + am2x2 + - - - - - - + amnxn = bm

We reduce the System (1) to a simpler system as follows:

Step 1: -

Elimination of x1 from the second, third……..mth equations. We may assume that the order (rule) of the equations and the order (rule) of the unknowns in each equation such that a11 is not equal 0. The variables x1 can then be eliminated from the second, third ………………..mth equations by subtracting.

a21/a11 times the first equation from the second equation

a31/a11 times the first equation from the third equation

.. ………….. …….. ………… … .. .. . .. .. . .. .. .. . .. .

.. . .. . .. . .. … .. … . . .. . . . . . .. … . . . . .. . . . . . ...

am1/a11 times the first equation from the mth equation.

This gives a new system of equations of the form

a11x1 + a12x2 + - - - - - - + a1nxn = b1

c22x2 + - - - - - - + c2nxn = b’2

… …. …. ….. … … .. .. . .. . .. .. . .. .. .. .. . .. System (2)

. … . .. .. . .. .. . .. .. . .. . .. . .. .. . .. . .. . .. ..

cm2x2 + - - - - - - + cmnxn = b”m

Any solution of the system (1) is a solution of the system (2) and conversely.

Second Step: -

Elimination of x2 form the third, fourth, ………. …. mth equations in the system (2). If the co-efficient c22, c23, …… cmn, in the system (2) are not all zero. We may assume that the order (rule) of the equations and the unknowns such that c22 is not equal zero. Then we may eliminate x2 from the third, fourth, ……… mth equations of the system (2) by subtracting.

c32/c22 times the second equation from the third equation

c42/c22 times the second equation from the fourth equation

………….. ………………. ……………………

…………… ……………… ………………….

cm2/c22 times the second equation from the mth equation

The further steps are now obvious. In the fourth step we eliminate x3, in the fourth step we eliminate x4 etc.

This process will terminate only when no equations are left or when the co-efficient of all the unknowns in the remaining equations are zero. We have a system of the from.

a11x1 + a12x2 + - - - - - - + a1nxn = b1

c22x2 + - - - - - - + c2nxn = b’2

… …. …. ….. … … .. .. . .. . .. .. . .. .. .. ..

. … . .. .. . .. .. . .. .. . .. . .. . .. .. . .. . .. . ..System (3)

crsxr + - - - - - - + kmxn = br

0 = b r+1

…………

0 = bm

Where r< m. We see that there are three possible cases

(1) No solution if r <>b r+1 ………. bm is not zero.

(2) Precisely one solution if r = n and b r+1 ………. bm if present are zero.

This solution is obtained by solving the nth equation of the system (3) for xn, then the (n-1)th equation for xn-1 and so on up to the line.

(3) Infinitely many solutions if rb r+1 ………. bm if present is zero. Then any of this solutions is obtained by choosing values at pleasure for unknowns xr+1, …….. xn solving the rth equation for xr then (r-1)th equation for xr-1, and so on up to the line.