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.
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.
 All nonzero rows are above any rows of all zeroes.
 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.
 All entries in a column below a leading entry are zeroes.
 Any present zero rows are placed all the way at the bottom of the matrix.
 The very first value of the matrix (termed as the leading entry or pivot) is a nonzero term (some texts prefer it be �1�, but it is not necessarily).
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 columnthat 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:
 Addition of a multiple of one equation to another.
Symbolically: (equation j) \( \mapsto \) (equation j) + k (equation i).  Multiplication of an equation by a nonzero constant k.
Symbolically: (equation j) \( \mapsto \) k (equation j).  Interchange of two equations>
Symbolically: (equation j) \( \Longleftrightarrow \) (equation i).
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 actual use of the term augmented matrix was evolved by the American mathematician Maxime B�cher (18671918) 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).
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 nr free variables.
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 n1
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 ith column, below the diagonal (hence j ranges only from i+1 to nthe dimension of the matrix A). We first compute the multiplier m, for each row. This is the constant by which we multiply the ith row in order to eliminate the a_{ji} element. Note that we overwrite the previous values with the new ones, and we do not actually carry out computation that makes a_{ji} zero. Also this loop is where the rightside vector is modified to reflect the elimination step.
The innermost loop (the k loop) ranges across the jth row, starting after the ith column, modifying each element appropriately to reflect the elimination of a_{ji}.
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=n1 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
x_{i} in turn. Finally, we are computing
For example, consider the system of equations

For each set of matrices, determine which elementary operations can transform
matrix A to matrix B.

\[ {\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} ; \]

\[ {\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} ; \]

\[ {\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} . \]


For the following problems, use row operations to solve the system of equations.

\begin{equation*} x_{1}+2\,x_{2}=3 \end{equation*} \begin{equation*} 2\,x_{1}+3\,x_{2}=4 \end{equation*}

\begin{equation*} 3\,x_{1}+x_{2}=6 \end{equation*} \begin{equation*} 3\,x_{1}+3\,x_{2}=2 \end{equation*}


In the following problems, solve the systems of linear equations given
their augmented matrices.

\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*}

\begin{equation*} \begin{bmatrix} 1 & 2 & 2 &  & 4\\ 0 & 3 & 2 &  & 1\\ 0 & 0 & 0 &  & 3\\ \end{bmatrix} \end{equation*}


For the following problems, solve the system of equations.

\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*}

\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*}


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.

\[ \begin{bmatrix} 2 & f & 3\\ 4 & 8 & 6 \end{bmatrix} ; \]

\[ \begin{bmatrix} 1 & f & 3\\ 2 & 4 & 8 \end{bmatrix} ; \]

\[ \begin{bmatrix} 2 & 1 & f\\ 4 & 2 & 6\\ \end{bmatrix} . \]


For the following problems, use row operations to solve the system of equations.
 \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*}
 \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*}
 \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*}

Determine whether the following augmented matrices represent consistent
systems of equations and how many solutions exist.
 A= \begin{bmatrix} 1 & 4 & 2 &  & 8\\ 5 & 7 & 5 &  & 6\\ 3 & 2 & 6 &  & 6\\ \end{bmatrix}
 A= \begin{bmatrix} 1 & 1 & 1 &  & 3\\ 2 & 0 & 1 &  & 1\\ 0 & 1 & 1 &  & 0\\ \end{bmatrix}
 A= \begin{bmatrix} 1 & 1 & 1 &  & 1\\ 1 & 2 & 2 &  & 4\\ 3 & 2 & 1 &  & 12\\ \end{bmatrix}
 A= $\begin{bmatrix} 3 & 1 & 3 &  & 1\\ 1 & 2 & 2 &  & 1\\ 2 & 3 & 1 &  & 1\\ \end{bmatrix}$
 Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9th ed.), Wiley International
 Beezer, R., A First Course in Linear Algebra, 2015.
 Beezer, R., A Second Course in Linear Algebra, 2013.
 Casady, Chelsea, Gaussian Elimination and its History, Liberty University
 Grcar, Joseph F., Mathematicians of Gaussian Elimination, Notes of American Mathematical Society, 58, No 6, 2011, 782792.
 William F. Osgood, (1919). "The life and services of Maxime B�cher". Bull. Amer. Math. Soc. 25 (8): 337�350. doi:10.1090/s00029904191903198x.
 Gaussian elimination for dummies
 Examples of Gaussian Elimination, Dartmouth College.
 Higham, Nicholas, Gaussian Elimination, Manchester Institute for Mathematical Sciences, School of Mathematics, The University of Manchester, 2011.
 Systems of Linear Equations
 Elementary Row Operations
 Elementary Row Operations for Matrices
 Automatic Row Reduction Input Form, A program that performs Gaussian elimination similarly to a human working on paper.
 Reduce Row Echelon Form on line by Kardi Teknomo.
 An online tool for performing elementary operations with rows and columns,
 GaussJordan Elimination Calculator.