Gaussian elimination

Introduction

Gaussian elimination, also known as row reduction, is a method in linear algebra for solving systems of linear equations. It is named after the German mathematician Carl Friedrich Gauss. The method involves two types of elementary row operations: swapping two rows and multiplying a row by a non-zero number.

Overview

The Gaussian elimination method is used to convert a system of linear equations into a form that is easier to solve. The goal is to transform the original matrix into an row echelon form or reduced row echelon form, where the solution can be found by back substitution.

A photograph of a matrix before and after Gaussian elimination.

Elementary Row Operations

There are three types of elementary row operations used in Gaussian elimination:

1. Swapping two rows. 2. Multiplying a row by a non-zero number. 3. Adding a multiple of one row to another row.

These operations are used to manipulate the rows of the matrix, with the aim of creating a matrix in row echelon form or reduced row echelon form.

Row Echelon Form

A matrix is in row echelon form if it satisfies the following conditions:

1. All non-zero rows are above any rows of all zeroes. 2. The leading coefficient (the first non-zero number from the left, also called the pivot) of a non-zero row is always strictly to the right of the leading coefficient of the row above it.

This form is used as an intermediate step in Gaussian elimination, as it simplifies the system of equations, making it easier to find the solution.

Reduced Row Echelon Form

A matrix is in reduced row echelon form if it satisfies the conditions for row echelon form, and also the following additional conditions:

1. The leading coefficient in each non-zero row is 1. 2. All elements in the column above and below a leading 1 are zero.

This form is the final goal in Gaussian elimination, as it provides the solution to the system of equations.

Gaussian Elimination Procedure

The procedure for Gaussian elimination involves a series of steps:

1. Arrange the system of linear equations in matrix form. 2. Perform elementary row operations to transform the matrix into row echelon form. 3. Continue with the elementary row operations to transform the matrix into reduced row echelon form. 4. Interpret the resulting matrix to find the solution to the system of equations.

Applications

Gaussian elimination is used in various fields, including engineering, physics, and computer science. It is a fundamental tool in numerical linear algebra, where it is used to solve systems of linear equations, compute the rank of a matrix, find the determinant of a matrix, and compute the inverse of an invertible matrix.