es
Gaussian Elimination

Preliminaries

Motivation

REF

Counting Operations

 

Preliminary Information

In this short subsection, we collect a neccessary information that is used in exposition of the Gauss--Jordan method. You can skip it if you feel comfortable with the terminology and material and go directly to the the main algorithm.

We consider the system of linear equations in standard form:

\begin{equation} \label{EqGauss.1} \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n &= b_1 , \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n &= b_2 , \\ \cdots \qquad \cdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n &= b_m . \\ \end{cases} \end{equation}
Since system (1) has m equations and n unknown variables, it is called the m×n system of equations. Correspondingly, the m×n matrix and m × 1 column vector
\[ {\bf A} = \begin{bmatrix} a_{11}& a_{12} & a_{13} & \cdots & a_{1n} \\ a_{21}& a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots& \vdots& \vdots& \ddots & \vdots \\ a_{m1}& a_{m2} & a_{m3} & \cdots & a_{mn} \end{bmatrix} \qquad \mbox{and} \qquad {\bf b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} \]
are called the coefficient matrix and the constant term, respectively. The standard form of system (1) requires placing all constant terms "bi" to the right-hand side of the equations and keeping the same order of unknown variables for every equation. Although mathematical rules and computer solvers allow swapping the order of summation in every equation, the standard form of system (1) requires the same order of summation for every equation. For instance, it is prohibited to write the following equations as
\[ \begin{split} 2\, x + 3\,y &= 5, \\ 4\, y + 7\, x &= 1 , \end{split} \qquad\mbox{but standard form is} \qquad \begin{split} 2\, x + 3\,y &= 5, \\ 7\, x + 4\, y &= 1 . \end{split} \]
Note that you can swap the order of summation in every equation of system (1), but this must be done for every single equation and then reindexing unknown variables. Actually, this operation is equivalent swapping corresponding columns in the augmented matrix.

For our exposition and for computer manipulations, we need a shorthand way of writing systems of equations (1). Upon writing right-hand terms in column vector form, we can rewrite system in matrix/vector form

\begin{equation} \label{EqGauss.2} {\bf A}\,{\bf x} = {\bf b}, \qquad {\bf x} \in \mathbb{F}^{n\times 1} , \quad {\bf b} \in \mathbb{F}^{m\times 1} . \end{equation}
A system of linear equations above, written in matrix/vector form A x = b, is said to be consistent if it has at least one solution and inconsistent if there is no solution.
Two linear systems are said to be equivalent if they have the same solution set.
Actually, notation for unknown variable as x in Eq.(1) or Eq.(2) is completely subjective and any character can be used instead of x.
For a linear system of equation A x = b, where A is an m×n matrix and b is a known m column vector, we assign the m×(n+1) augmented matrix, denoted [A|b] or [A b], which is A with column b tagged on.
The augmented matrix provides a precise and concise information about a linear system of equations:
\[ \left[ {\bf A} \vert {\bf b} \right] = \left[ \begin{array}{ccccc|c} a_{11}& a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\ a_{21}& a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\ \vdots& \vdots& \vdots& \ddots & \vdots & \vdots \\ a_{m1}& a_{m2} & a_{m3} & \cdots & a_{mn} & b_n \end{array} \right] . \]
Sometimes a vertical line is used to separate the coefficient entries from the constants can be dropped and then augmented matrix is written as [A b] .
An elementary row operation on a matrix M is any one of the following three ways of modifying M to produce a new equivalent matrix.
  1. Interchanging the positions of two rows. We abbreviate it as Ri ↕ Rj.
  2. Multiplying one row of the matrix by a nonzero scalar. This operation is denoted as Ri ← c·Ri for row i.
  3. Adding a constant multiple of a row to another row. The following notation is used: Ri ← Ri + c·Rj.
Two rectangular matrices of the same dimensions are said to be row equivalent, denoted by the symbol \( \displaystyle \underset{R}{\sim} \) placed between the two matrices, if there exists a sequence of elementary row operations that transfers one matrix into another one.

 

 

  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.