es
Gaussian Elimination

Preliminaries

Motivation

REF

Counting Operations

Gaussian Elimination

Suppose M = [A | b] is the augmented matrix of a linear system A x = b. We can solve the linear system by performing elementary row operations on M. A leading entry of a row refers to the leftmost nonzero entry.

The leftmost non-zero entry in every row is called the leading term.
A leading term having all zero entries bellows it in its column is called the pivot.
If a column in a matrix has a pivot, it is called the pivot column.

In other words, if A is

Sometimes a vertical line to separate the coefficient entries from the constants can be dropped and then augmented matrix is written as [A b] .

=========================== to be checked ===========

The Gaussian elimination method is basically a series of operations carried out on a given matrix, in order to mathematically simplify it to its echelon form. When it is applied to solve a linear system Ax=b, it consists of two steps: forward elimination (also frequently called Gaussian elimination procedure) to reduce the matrix to upper triangular form, and back substitution. Therefore, solving a linear system of algebraic equations using this elimination procedure can also be called forward elimination and back substitution and abbreviated as FEBS.

A rectangular matrix is said to be in echelon form or row echelon form if it has the following three properties:
  1. All nonzero rows are above any rows of all zeroes.
  2. Each leading entry, called the pivot, of a row is in a column to the right of the leading entry of the row above it.
  3. All entries in a column below a leading entry are zeroes.
An echelon matrix is one that is in echelon form.
A matrix is said to be in its row echelon form when it meets the following two conditions:

  1. Any present zero rows are placed all the way at the bottom of the matrix.
  2. The very first value of the matrix (termed as the leading entry or pivot) is a non-zero term (some texts prefer it be �1�, but it is not necessarily).
Example: The following matrices are in the echelon form:
\[ \begin{bmatrix} \color{red}{♦} & \ast & \ast & \ast \\ 0& \color{red}{♦} & \ast & \ast \\ 0&0&0&0 \\ 0&0&0&0 \end{bmatrix} , \quad \begin{bmatrix}\color{red}{ ♦} & \ast & \ast & \ast \\ 0&0 & \color{red}{♦} & \ast \\ 0&0&0& \color{red}{⊚} \\ 0&0&0&0 \end{bmatrix} , \quad \begin{bmatrix} \color{red}{♦} & \ast & \ast & \ast & \ast & \ast \\ 0&0&0 & \color{red}{♦} & \ast & \ast \\ 0&0&0&0& \color{red}{♦} & \ast \\ 0&0&0&0&0& \color{red}{⊚} \end{bmatrix} . \]
where ♦ denotes the pivot's position (the entry cannot be zero), * denotes arbitrary element that could be zero or not, and ⊚ denotes lonely nonzero entry that looks as a pivot but it indicates that the corresponding system has no solution. From theoretical point of view, a pivot could be in the last column, but when dealing with augmented matrices corresponding to the linear system of equations, we avoid this. For consistent systems, pivots cannot be in lonely position at the end of a row; otherwise, the system has no solution. ■
A pivot position in a matrix A is a location in A that corresponds to a leading term in the row echelon form of A. A pivot column is a column of A that contains a pivot position.

Any nonzero matrix may be row reduced (that is, transformed by elementary row operations) into more than one matrix in echelon form, using different sequences of row operations. However, the leading entries are always in the same positions in any echelon form obtained from a given matrix.

Theorem: A linear system has a solution if and only if the rightmost column of the associated augmented matrix is not a pivot column---that is, if and only if its echelon form does not contain a row of the form
[ 0 0 ... 0 ⊚ ] with ⊚ nonzero.
If a linear system is consistent, then the solution set contains either a unique solution (with no free variables) or infinitely many solutions, when there is at least one free variable.

Row echelon form states that the Gaussian elimination method has been specifically applied to the rows of the matrix. It uses only those operations that preserve the solution set of the system, known as elementary row operations:

  1. Addition of a multiple of one equation to another.
    Symbolically: (equation j) \( \mapsto \) (equation j) + k (equation i).
  2. Multiplication of an equation by a nonzero constant k.
    Symbolically: (equation j) \( \mapsto \) k (equation j).
  3. Interchange of two equations>
    Symbolically: (equation j) \( \Longleftrightarrow \) (equation i).
Maxime B�cher

Row echelon and Reduced row echelon forms are the resulting matrices of the Gaussian elimination method. By applying Gaussian elimination to any matrix, one can easily deduce the following information about the given matrix:

  • the rank of the matrix;
  • the determinant of the matrix;
  • the inverse (invertible square matrices only);
  • the kernel vector (also known as �null vector�).
The main purpose of writing a matrix in its row echelon form and/or reduced row echelon, is to make it easier to examine the matrix and to carry out further calculations, especially when solving a system of algebraic equations.

When forward elimination procedure is applied to a system of algebraic equations Ax=b, the first step is create an augmented matrix, which is obtained by appending the columns vector b from right to the matrix of the system: \( {\bf B} = \left[ {\bf A} \, \vert \, {\bf b} \right] . \) The next step is to use elementary row operations to reduce the augmented matrix B to the new augmented matrix \( {\bf C} = \left[ {\bf U} \, \vert \, {\bf c} \right] , \) where U is upper triangular matrix. This means that the new system Ux=c is easy to solve.

The actual use of the term augmented matrix was evolved by the American mathematician Maxime B�cher (1867--1918) in his book Introduction to Higher Algebra, published in 1907. B�cher was an outstanding expositor of mathematics whose elementary textbooks were greatly appreciated by students. His achievements were documented by William F. Osgood (1919).

Variables in a linear system of equations that corresponds to pivot positions in the augmented matrix for the given system are called the leading variables. the remaining variables are called free variables.
Example: We consider the following augmented matrix:
\[ {\bf A} = \begin{bmatrix} \color{red}{-1}&3&-2&5&4&0&7 \\ 0&0& \color{red}{3}&6&-1&0&2 \\ 0&0&0&0&0&\color{red}{7}&49 \\ 0&0&0&0&0&0&0 \end{bmatrix} . \]
This matrix corresponds to four equations in six unknown variables. Since pivots are located in columns 1, 3, and 6, the leading variables for this system of equations are x1, x3, and x6. The other three variables x2, x4, and x5 are free variables. ■

Theorem: If a homogeneous linear system has n unknowns, and if the row echelon form of its augmented matrix has r nonzero rows, then the system has n-r free variables.

Row operations can be applied to any matrix, not merely to one that arises as the augmented matrix of a linear system. Two matrices are called row equivalent if there is a sequence of elementary row operations that transforms one matrix into the other. It is important to note that row operations are reversible. if two rows are interchanged, they can be returned to their original positions by another interchange. If a row scaled is scaled by a nonzero constant k, then multiplying the new row by 1/k produces the original row. Finally, consider a replacement operation involving two rows---say 1 and 3---and suppose that k times row 1 is added to row 3 to obtain a new row 3. To come back, just add -k times row 1 to new row 3 and you will get the original row 3.

Theorem: Let \( {\bf B} = \left[ {\bf A} \, \vert \, {\bf b} \right] \) be the augmented matrix corresponding to the linear equation Ax=b, and suppose B is row equivalent (using a sequence of elementary row operations) to the new augmented matrix \( {\bf C} = \left[ {\bf U} \, \vert \, {\bf c} \right] , \) which corresponds to the linear system Ux=c. Then the two linear systems have precisely the same solution set.


Naive Gaussian elimination algorithm for Ax=b with a square matrix A (pseudocode) 
 
for i=1 to n-1 
	for j=i+1 to n
		m=a(j,i)/a(i,i)
		for k=i+1 to n 
			a(j,k) = a(j,k) -m&a(i,k)
		endfor
		b(j) = b(j) - m*b(i)
	endfor
endfor
The outmost loop (the i loop) ranges over the columns of the matrix; the last column is skipped because we do not need to perform any eliminations there because there are no elements below the diagonal (if we were doing elimination on a nonsquare matrix with more rows than columns, we would have to include the last column in this loop).

The middle loop (the j loop) ranges down the i-th column, below the diagonal (hence j ranges only from i+1 to n---the dimension of the matrix A). We first compute the multiplier m, for each row. This is the constant by which we multiply the i-th row in order to eliminate the aji element. Note that we overwrite the previous values with the new ones, and we do not actually carry out computation that makes aji zero. Also this loop is where the right-side vector is modified to reflect the elimination step.

The innermost loop (the k loop) ranges across the j-th row, starting after the i-th column, modifying each element appropriately to reflect the elimination of aji.

Finally, we must be aware that the algorithm does not actually create the zeroes in the lower triangular half of B; this would be wasteful of computer time since we don't need t have these zeroes in place for the algorithm to work. The algorithm works because we utilize only the upper triangular part of the matrix from this point forward, so the lower triangular elements need never be referenced.

Backward solution algorithm for A (pseudocode) 

 
x(n) = b(n)/a*n,n)
for i=n-1 to 1 
	sum = 0
	for j=i+1 to n
		sum = sum + a(i,j)*x(j)
	endfor
	x(i) = (b(i) - sum)/a(i,i) 
endfor
This algorithm simply matches backward up the diagonal, computing each xi in turn. Finally, we are computing
\[ x_i = \frac{1}{a_{ii}} \left( b_i - \sum_{j=i+1}^n a_{ij} x_j \right) , \]
which is what is necessary to solve a triangular system. The j loop is simply accumulating the summation term in this formula. The algorithm stops if one of the diagonal terms is zero because we cannot divide by it. This case requires a special attention that yields interchange of row.
Example: Consider system of algebraic equations
\[ \begin{split} 3\,x-3\,y-6\,z &=3, \\ 2\,x + 4\,y + z &= 1 ,\\ -x + y + 2\,z &= -1. \end{split} \]
The idea of Gaussian elimination is to replace the above system by another system with the same solutions, it is just easier to solve. First, we build the augmented matrix corresponding to the given system of equations:
\[ \left[ {\bf A}\,{\bf b}\right] = \begin{bmatrix} 3&-3&-6&3 \\ 2&4& 1 & 1 \\ -1 &1&2&-1 \end{bmatrix} . \]
Multiplying the first row by -2/3 and adding to the second one, we obtain an equivalent augmented matrix:
\[ \left[ {\bf A}\,{\bf b}\right] \sim \begin{bmatrix} 3&-3&-6&3 \\ 0&6&4&-1 \\ -1 &1&2&-1 \end{bmatrix} . \]
Next, we multiply the first row by 1/3 and add to the third row:
\[ \left[ {\bf A}\,{\bf b}\right] \sim \begin{bmatrix} 3&-3&-6&3 \\ 0&6&4&-1 \\ 0 &0&0&0 \end{bmatrix} . \]
Therefore, we obtain an equivalent augmented matrix in row echelon form. Since it contains one row of all zeroes, the given system has infinite many solutions that we obtain by solving the second equation:
\[ 6\,y + 4\,z = -1 \qquad \Longrightarrow \qquad z = - \frac{3}{2}\, y - \frac{1}{4} . \]
Using this expression, we get from the first equation
\[ 3\,x-3\,y-6\,z = 3x + 6\,y + \frac{3}{2} = 3 \qquad \Longrightarrow \qquad x = -2\,y + \frac{3}{2} . \]
So y is a free variable, and we obtain the general solution:
\[ x = -2\,y + \frac{3}{2} , \quad z = - \frac{3}{2}\, y - \frac{1}{4} . \]

Example: Consider system of algebraic equations
\[ \begin{split} 3\,x-3\,y-6\,z &=3, \\ 2\,x + 4\,y + z &= 1 ,\\ -x + y + 2\,z &= 1. \end{split} \]
We apply the same procedure as in the previous example: forward elimination. The procedure to be used expresses some of unknowns in terms of others by eliminating certain unknowns from all the equations except one. To begin, we eliminate x from every equation except the first one by adding -2/3 times the first equation to the second and 1/3 times the first equation to the third. The result is the following new system:
\[ \begin{bmatrix} 1&-1&-2&1 \\ 2&4&1&1 \\ -1&1&2&1 \end{bmatrix} \qquad \Longrightarrow \qquad \begin{bmatrix} 1&-1&-2&1 \\ 0&6&5&3 \\ 0&0&0&2 \end{bmatrix} . \]
Since the pivot is situated in the last column of the augmented matrix, the given system of equations has no solution because it is impossible to satisfy the equation 0 = 2.

Example: When using the Gaussian elimination technique, you can at any time exchange rows, meaning that you can switch any two rows an unlimited number of times. This is very helpful if your matrix contains a 0 in the (1,1) position.

For example, consider the system of equations

\[ \begin{split} 2\,x_2 + x_3 &=-8, \\ x_1 -2\,x_2 -3\,x_3 &= 0 ,\\ -x_1 + x_2 + 2\,x_3 &= 3; \end{split} \qquad \begin{bmatrix} 0&2&1&-8 \\ 1&-2&-3&0 \\ -1&1&2&3 \end{bmatrix} . \]
Because we cannot have 0 in the (1,1) position, we swap row 1 and row 2:
\[ \begin{bmatrix} 1&-2&-3&0 \\ 0&2&1&-8 \\ -1&1&2&3 \end{bmatrix} . \]
Adding row 1 to row 3 gives
\[ \begin{array}{c} 1 \cdot [\mbox{equation }1] \\ + [\mbox{equation }3] \\ \hline [\mbox{new equation }3] \end{array} \qquad \begin{array}{ccccc} x_1 &-2\,x_2& -3\, x_3& =&0 \\ -x_1&+ x_2 & +2\,x_3& =&3 \\ \hline &-x_2& -x_3 & =& 3 \end{array} \]
Now we swap row 2 and row 3:
\[ \begin{bmatrix} 1&-2&-3&0 \\ 0&-1&-1&3 \\ 0&2&1&-8 \end{bmatrix} . \]
Adding 2 times row 2 to row 3 gives us
\[ \begin{bmatrix} 1&-2&-3&0 \\ 0&-1&-1&3 \\ 0&0&-1&-2 \end{bmatrix} . \]
Now add -1 times row 3 to row 2 and add -3 times row 3 to row 1 which gives us
\[ \begin{bmatrix} 1&-2&0&-4 \\ 0&-1&0&5 \\ 0&0&-1&-2 \end{bmatrix} . \]
Add -2 times row 2 to row 1
\[ \begin{bmatrix} 1&0&0&-4 \\ 0&-1&0&5 \\ 0&0&-1&-2 \end{bmatrix} . \]
Finally, we multiply rows 2 and 3 by -1 to obtain Gauss-Jordan form:
\[ \begin{bmatrix} 1&0&0&-4 \\ 0&1&0&-5 \\ 0&0&1&2 \end{bmatrix} . \]
This gives x1 = -4, x2 = -5, and x3 = 2. ■

  1. For each set of matrices, determine which elementary operations can transform matrix A to matrix B.
    1. \[ {\bf A} = \begin{bmatrix} 1 & 5 & -3 & 2\\ 2 & 2 & 3 & 5\\ 0 & 2 & 4 & -3\\ \end{bmatrix} \qquad {\bf B} = \begin{bmatrix} 1 & 5 & -3 & 2\\ 0 & -8 & 9 & 1\\ 0 & 2 & 4 & -3\\ \end{bmatrix} ; \]
    2. \[ {\bf A} = \begin{bmatrix} 2 & 3 & 7 & 1\\ 0 & 4 & 3 & 5\\ 1 & 2 & 7 & 4\\ \end{bmatrix} \qquad {\bf B} = \begin{bmatrix} 2 & 3 & 7 & 1\\ 1 & 2 & 7 & 4\\ 0 & 4 & 3 & 5\\ \end{bmatrix} ; \]
    3. \[ {\bf A} = \begin{bmatrix} 3 & 2 & 1 & -1\\ 4 & 6 & 5 & 2\\ 1 & 7 & -2 & 3\\ \end{bmatrix} \qquad {\bf B} = \begin{bmatrix} 0 & -19 & 7 & -10\\ 4 & 6 & 5 & 2\\ 1 & 7 & -2 & 3\\ \end{bmatrix} . \]
  2. For the following problems, use row operations to solve the system of equations.
    1. \begin{equation*} x_{1}+2\,x_{2}=-3 \end{equation*} \begin{equation*} 2\,x_{1}+3\,x_{2}=4 \end{equation*}
    2. \begin{equation*} 3\,x_{1}+x_{2}=6 \end{equation*} \begin{equation*} 3\,x_{1}+3\,x_{2}=2 \end{equation*}
  3. In the following problems, solve the systems of linear equations given their augmented matrices.
    1. \begin{equation*} \begin{bmatrix} 1 & -1 & 2 & -1 & | & 5\\ 0 & 5 & -1 & 3 & | & 4\\ 0 & 0 & 3 & -1 & | & 5\\ 0 & 0 & 0 & 2 & | & 8\\ \end{bmatrix} \end{equation*}
    2. \begin{equation*} \begin{bmatrix} 1 & -2 & 2 & | & 4\\ 0 & 3 & -2 & | & 1\\ 0 & 0 & 0 & | & 3\\ \end{bmatrix} \end{equation*}
  4. For the following problems, solve the system of equations.
    1. \begin{equation*} 2\,x_{2}+x_{3}=3 \end{equation*} \begin{equation*} 2\,x_{1}+x_{2} -\,2x_{3}=-3 \end{equation*} \begin{equation*} 4\,x_{1}+4\,x_{2}-3\,x_{3}=-3 \end{equation*}
    2. \begin{eqnarray*} 3\,x_{1}-2\,x_{2}-1\,x_{3} &=-1 , \\ 2\,x_{1}-1\,x_{2}+2\,x_{3} &=4 , \\ x_{2}-2\,x_{3} &=-6. \end{eqnarray*}
  5. For the following problems, find the value or values of f, if any, which make the matrix an augmented matrix of a consistent linear system.
    1. \[ \begin{bmatrix} 2 & f & 3\\ -4 & -8 & -6 \end{bmatrix} ; \]
    2. \[ \begin{bmatrix} 1 & f & -3\\ 2 & 4 & -8 \end{bmatrix} ; \]
    3. \[ \begin{bmatrix} 2 & -1 & f\\ -4 & 2 & 6\\ \end{bmatrix} . \]
  6. For the following problems, use row operations to solve the system of equations.
    1. \begin{equation*} x_{1}+x_{2}-x_{3}=9 \end{equation*} \begin{equation*} x_{2}+3x_{3}=3 \end{equation*} \begin{equation*} -x_{1}-2x_{3}=2 \end{equation*}
    2. \begin{equation*} 4x_{1}+8x_{2}-4x_{3}=4 \end{equation*} \begin{equation*} 3x_{1}+8x_{2}+5_{3}=-11 \end{equation*} \begin{equation*} -2x_{1}+x_{2}+12x_{3}=-17 \end{equation*}
    3. \begin{equation*} x_{1}+2x_{2}+3x_{3}=4 \end{equation*} \begin{equation*} 2x_{1}+3x_{2}+3x_{3}=1 \end{equation*} \begin{equation*} 4x_{1}+2x_{2}+3x_{3}=1 \end{equation*}
  7. Determine whether the following augmented matrices represent consistent systems of equations and how many solutions exist.
    1. A= \begin{bmatrix} 1 & 4 & -2 & | & 8\\ 5 & 7 & -5 & | & 6\\ -3 & 2 & -6 & | & 6\\ \end{bmatrix}
    2. A= \begin{bmatrix} 1 & 1 & 1 & | & 3\\ 2 & 0 & -1 & | & 1\\ 0 & 1 & -1 & | & 0\\ \end{bmatrix}
    3. A= \begin{bmatrix} 1 & -1 & -1 & | & 1\\ -1 & 2 & 2 & | & -4\\ 3 & 2 & 1 & | & -12\\ \end{bmatrix}
    4. A= $\begin{bmatrix} 3 & 1 & -3 & | & 1\\ -1 & 2 & 2 & | & -1\\ 2 & 3 & -1 & | & 1\\ \end{bmatrix}$

  1. Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9th ed.), Wiley International
  2. Beezer, R., A First Course in Linear Algebra, 2015.
  3. Beezer, R., A Second Course in Linear Algebra, 2013.
  4. Casady, Chelsea, Gaussian Elimination and its History, Liberty University
  5. Grcar, Joseph F., Mathematicians of Gaussian Elimination, Notes of American Mathematical Society, 58, No 6, 2011, 782--792.
  6. William F. Osgood, (1919). "The life and services of Maxime B�cher". Bull. Amer. Math. Soc. 25 (8): 337�350. doi:10.1090/s0002-9904-1919-03198-x.
  7. Gaussian elimination for dummies
  8. Examples of Gaussian Elimination, Dartmouth College.
  9. Higham, Nicholas, Gaussian Elimination, Manchester Institute for Mathematical Sciences, School of Mathematics, The University of Manchester, 2011.
  10. Systems of Linear Equations
  11. Elementary Row Operations
  12. Elementary Row Operations for Matrices
  13. Automatic Row Reduction Input Form, A program that performs Gaussian elimination similarly to a human working on paper.
  14. Reduce Row Echelon Form on line by Kardi Teknomo.
    16. An online tool for performing elementary operations with rows and columns,
  16. Gauss--Jordan Elimination Calculator.