**Gaussian Elimination**

Preliminary Information

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 "

*b*

_{i}" 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

Actually, notation for unknown variable as **equivalent**if they have the same solution set.**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

The augmented matrix provides a precise and concise information about a linear
system of equations:
**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.
\[
\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.-
Interchanging the positions of two rows. We abbreviate it as R
_{i}↕ R_{j}. -
Multiplying one row of the matrix by a nonzero scalar.
This operation is denoted as R
_{i}←*c*·R_{i}for row*i*. -
Adding a constant multiple of a row to another row. The following notation is used: R
_{i}← R_{i}+*c*·R_{j}.

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.

- 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.