Gaussian Elimination

In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix.

Note: In mathematics we can use AX=b as the representation of the systems of linear equations.

Elimination is the most widely used technique to solve a system of linear equations in computer applications whenever the matrix A is invertible.

Before diving into the gaussian elimination, it is important to understand Elementary row operations.

Elementary row operations

1. Row switching: A row within the matrix can be switched with another row.
2. Row multiplication: This is also known as scaling row, each element in a row can be multiplied by non-zero constant.
3. Row addition: A row can be replaced by the sum of that row and a multiple of another row.

Using these operations, a matrix can be transformed into an upper triangular matrix.

Let’s look at the following system of linear equations to understand how row operations are applied in gaussian elimination,

• x + 2y + z = 2
• 3x + 8y + z = 12
• 4y + z = 2

Let’s start elimination for the variable “x”, which means pivot column 1(C1). First step of the elimination is to select a row and multiply by a scalar such that we can eliminate a variable.

Ex: -3*R1 + R2 -> R2 will eliminate x of R2.

(Note: Should apply the same operation for the right-hand side.)

Second step is to finish the column, which means to make zero positions except 1. Here, (R1, C1) =1, (R2, C1) =0, (R3, C1) =0, hence we don’t need any other operation for this column.

Now, let’s do the elimination for the variable “y”, which means pivot column 2(C2). -2*R2+R3 -> R3 will eliminate “y” of R3.

1*R2+R1 -> R1 will eliminate y in R1.

0.5*R2 -> R1 will make the variable of y to 1.

Now, let’s do the elimination for the variable “z”, which means pivot column 3(C3). First, 0.2*R3 -> R3 will make the variable of z to 1.

R3+R2 -> R2 will eliminate variable “z” in R2.

3*R3+R1 -> R1 will eliminate variable “z” in R1

Now we have solved the system of linear equations.

The answer is: x =2, y =1, z =-2

Note: Pivot position cannot be zero. When there is zero for the pivot position you can exchange rows to make the pivot non-zero (only on some cases).

This is the method used by most software to solve the linear equations. However, this method is a very slow procedure and takes a fair amount of time to solve the equation.

Written by: Ruwan Sri Wickramarathna, Senior Data Scientist

Reference:

https://en.wikipedia.org/wiki/Gaussian_elimination