Sales Toll Free No: 1-855-666-7446

Gaussian Elimination

Top

In mathematics, various methods have been adopted to find the solution of system of linear equations. Gaussian elimination method happens to be among the most important methods in linear algebra. It is also called "row reduction method". In this method, a sequence of operations are applied to the coefficient matrix of linear equations. Not only for finding solutions of linear system, this method is also used to find the determinant of a matrix, to determine the rank of a matrix and to find the inverse of a matrix. Gaussian elimination method was named after Carl Friedrich Gauss who used it first. After successful understanding of this chapter, the students will be able to learn the following notions :

(1) What is Gaussian elimination method and its rules ?

(2)
 How to use row operations in Gaussian elimination method ?

(3)
 What are Echelon forms ?

(4)
 What is LU decomposition ?

Definition

Back to Top
The basic idea behind Gaussian elimination method is to add constants of one equation to others for the elimination of a variable and to keep continuing this method until only one variable remains. This step‐by‐step elimination of variables is known as Gaussian elimination.

In Gaussian elimination, a sequence of operations called row operations (discussed below) are performed on a matrix in order to modify the given matrix until upper triangular matrix is obtained, i.e. lower left corner elements become zeros as much as possible. Once the row echelon form (discussed below) is obtained, the elimination is over. Such final form of matrix is unique and independent of sequence of row operations. Then, we can easily find out the solution of system of linear equations.

Row Operations

Back to Top
There are few operations that can be applied to the rows of given matrix. These operations are termed as "elementary row operations" or simply "row operations". These are :
(1) Interchanging Rows
The value of a matrix will not change if the positions of any two rows are interchanged.

(2) Multiplication by scalar
The value of a matrix does not alter when a row is multiplied by a scalar quantity which is not equal to zero.

(3) Add a row to scalar multiple of another
A row can be multiplied by a nonzero scalar and then added to another row. This will also not change the value of the matrix.

Echelon Forms

Back to Top
Row Echelon Form

A matrix to be in row echelon form, in short "ref", it should satisfies the following conditions.

(1) In each row, first non-zero element should be 1. The first non-zero entry in a row is known as leading entry. i.e. the leading entry in each row must be 1.

(2) In a column, the leading entry must be located in the right side of leading entry in a row previous to it.

(3) If there is any row having all zero elements, then it must be located below the rows containing
a non-zero element.

For example :

$\begin{bmatrix} 1 & 4 & 2 & 3\\ 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix}$
Reduced Row Echelon Form

A matrix is said to acquire reduced row echelon form (abbreviated as "rref"), if the following conditions are satisfied.

(1)
 Matrix is in row echelon form.

(2)
 In each row, the 
leading entry should be the only non-zero entry in corresponding column.

For example :

$\begin{bmatrix} 1 & 4 & 0 & 0\\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rules

Back to Top
The Gaussian elimination method uses the above mentioned row operations in order to obtain a matrix in the form of reduced echelon form. This method can be classified into two main parts.

In first part, row operations are performed on the given matrix so as to obtain a reduced echelon form. Through this form, you may determine if there is unique solution, no solutions, a unique solution or infinitely many solutions.

In second part, the row operations are to be continued in order to obtain a reduced row echelon form which concludes the solution directly.

Examples

Back to Top
How to apply this method practically? Understand Gaussian elimination with the help of following examples.
Example 1: 

Solve $x\ +\ 2y$ = $4$ and $2x\ +\ y$ = $2$ using Gaussian elimination.

Solution:

Follow steps mentioned below.

Step 1: Write augmented form
            $x\ +\ 2y$ = $4$
            $2x\ +\ y$ = $2$

            can be written as,

            $\begin{bmatrix} 1 & 2 &|\ 4 \\ 2 & 1 &|\ 2 \end{bmatrix}$

Step 2: Apply row operations

            Multiply -$2$ to row $1$ and add it to row $2$,

            $\begin{bmatrix} 1 & 2 &|\ 4 \\ 0 & -3 &|\ -6 \end{bmatrix}$

Step 3: Write again the form of equations
           
            
$x\ +\ 2y$ = $4$ ____(1)    
           -$3y$ = -$6$ _____(2)

Step 4: Obtain value of one variable
           
             From equation (2), we get
             $y$ = $2$

Step 5: Substitute in other equation
           
            From e
quation (1),
            $x\ +\ 4$ = $4$
            $x$ = $0$
           
            Hence, solution is 
$x$ = $0$ and $y$ = $2$
Example 2: 

Solve using Gaussian elimination

$y\ +\ z$ = $2$
$2x\ +\ 3z$ = $5$
$x\ +\ y\ +\ z$ = $3$

Solution :

Step 1: Augmented matrix

           $\begin{bmatrix} 0 & 1 & 1 &|\ 2 \\ 2 & 0 & 3 &|\ 5 \\ 1 & 1 & 1 &|\ 3 \end{bmatrix}$

Step 2: Apply Row Operations

            Interchange row $1$ and $2$

           $\begin{bmatrix} 2 & 0 & 3 &|\ 5 \\ 0 & 1 & 1 &|\ 2 \\ 1 & 1 & 1 &|\ 3 \end{bmatrix}$

            Multiply row $2$ by -$1$ and add it to row $3$

            $\begin{bmatrix} 2 & 0 & 3 &|\ 5 \\ 0 & 1 & 1 &|\ 2 \\ 1 & 0 & 0 &|\ 1 \end{bmatrix}$

            Multiply row $3$ by -$2$ and add it to row $1$

          $\begin{bmatrix} 0 & 0 & 3 &|\ 3 \\ 0 & 1 & 1 &|\ 2 \\ 1 & 0 & 0 &|\ 1 \end{bmatrix}$

Step 3: Form Equations

           $3z$ = $3$ ___(1)

           $y\ +\ z$ = $2$ __(2)

           $x$ = $1$ _____(3)

           We get $x$ = $1$ and $z$ = $1$

Step 4: Substitute

            Substitute the values of z into equation (2)

           $y\ +\ 1$ = $2$
           $y$ = $1$

            Hence, the solution is $x$ = $1,\ y$ = $1,\ z$ = $1$