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

# Gaussian Elimination

Top
 Sub Topics 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

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

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

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

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

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:

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$