Gaussian Elimination Method

5.2 Gaussian Elimination Method

We assume that $\text{rank}(\mathsf{A})=n$ [or, that $\text{det}(\mathsf{A})\neq0$], i.e. the system $\mathsf{A}\vec{x} = \vec{b}$ is uniquely solvable. The idea of the Gaussian elimination method is to transform the original system $\mathsf{A}\vec{x} = \vec{b}$ to an equivalent system of equations in triangular form. The new system can then easily be solved from bottom to top.
Example:

\begin{equation*} \label{eq:example_dense} \begin{split} 2x_1 +\ x_2 + 3x_3 &=\ 73 ,\\ 6x_1 + 5x_2 + 4x_3 &= 168 ,\\ 4x_1 + 6x_2 + 7x_3 &= 209 . \end{split} \end{equation*}

(5.2)

Step 1: Eliminate $x_1$ from the 2nd and 3rd equations by applying to them appropriate multiples of the 1st equation; remember the relevant multipliers.

\begin{equation*} \begin{split} 2x_1 +\ x_2 + 3x_3 &=\ 73,\\ 2x_2 - 5x_3 &= -51, \qquad\mbox{(2nd Eq.\ minus $\frac{6}{2} \times$1st Eq.\ $\rightarrow m_{21}=3$)}\\ 4x_2 +\ x_3 &=\ 63. \qquad \ \ \mbox{(3rd Eq.\ minus $\frac{4}{2} \times$1st Eq.\ $\rightarrow m_{31}=2$)} \end{split} \end{equation*}

(5.3)

($m_{i1}$ — multipliers with which the 1st equation was multiplied so that the variable $x_1$ vanishes in the $i$-th equation.) Step 2: Similarly, eliminate $x_2$ from the 3rd equation.

\begin{equation*} \label{eq:step2} \begin{split} 2x_1 +\ x_2 + 3x_3 &=\ 73,\\ 2x_2 - 5x_3 &= -51,\\ 11x_3 &=165. \qquad \quad \mbox{(3rd Eq.\ minus $\frac{4}{2} \times$2nd Eq.\ $\rightarrow m_{32}=2$)} \end{split} \end{equation*}

(5.4)

($m_{32}$ — multiplier with which the 2nd equation was multiplied so that $x_2$ vanishes in the 3rd equation.) This system of equations obviously leads to the following results:

\begin{equation*} \begin{split} x_3 &= \textstyle\frac{165}{11} = 15, \\ x_2 &= \textstyle\frac{1}{2}(-51+5x_3) = 12, \\ x_1 &= \textstyle\frac{1}{2}[73-(x_2+3x_3)] = 8. \end{split} \end{equation*}

(5.5)

Note that according to Eq. (5.4), the linear system under consideration can also be written as $\mathsf{U}\vec{x} = \vec{g}$ with

\begin{equation*} \mathsf{U}=\left( \begin{array}{ccr} 2&1&3\\ 0&2&-5\\ 0&0&11 \end{array} \right), \quad \vec{g}=\left( \begin{array}{r} 73\\ -51\\ 165 \end{array} \right). \end{equation*}

(5.6)

The letter U is chosen here since in this matrix, only the upper triangular part (above the main diagonal) is occupied. Inverting the steps that led from Eq. (5.2) to Eq. (5.4), it becomes clear that $\vec{b} = \mathsf{L}\vec{g}$ with

\begin{equation*} \vec{b}=\left( \begin{array}{r} 73\\ 168\\ 209 \end{array} \right), \quad \mathsf{L}=\left( \begin{array}{ccc} 1&0&0\\ 3&1&0\\ 2&2&1 \end{array} \right). \end{equation*}

(5.7)

The letter L is chosen here since in this matrix, only the lower triangular part (below the main diagonal) is occupied. Obviously, the non-diagonal elements of L are the multipliers $m_{ij}$. Using $\mathsf{U}\vec{x} = \vec{g}$, one has that

\begin{equation*} \vec{b} = \mathsf{L}\vec{g} = \mathsf{L}\mathsf{U}\vec{x}, \end{equation*}

(5.8)

which by comparison with $\mathsf{A}\vec{x} = \vec{b}$ implies that

\begin{equation*} \label{eq:LU} \mathsf{A} = \mathsf{L}\mathsf{U}. \end{equation*}

(5.9)

This illustrates the following
Theorem: LU decomposition (without proof)
For a non-degenerate matrix $\mathsf{A}$ it holds that $\mathsf{A} = \mathsf{L}\mathsf{U}$ with lower ($\mathsf{L}$) and upper ($\mathsf{U}$) triangular matrices if all its leading principal minors (determinants of the upper left sub-matrices) are non-zero. This factorization is called LU decomposition of $\mathsf{A}$.
Remark: usage of LU decomposition for solving linear systems
Using the LU decomposition, the linear system $\mathsf{A}\vec{x} = \vec{b}$ can easily be solved in two steps: First, $\vec{g}$ is determined from $\mathsf{L}\vec{g} = \vec{b}$; second, $\vec{x}$ is determined from $\mathsf{U}\vec{x} = \vec{g}$. Since both $\mathsf{L}$ and $\mathsf{U}$ are triangular matrices, no further matrix inversion is needed; all variables can be determined successively, as shown in the example above. Note that since calculating the LU decomposition numerically (in Matlab this is done by lu) is a demanding task for larger matrices, this is worthwhile only if the same system $\mathsf{A}\vec{x} = \vec{b}$ has to be solved several times, for different $\vec{b}$.
Implication 1: calculation of the determinant
With the LU decomposition of $\mathsf{A}$ one has that $\det(\mathsf{A})=\det(\mathsf{L}\mathsf{U})=\det(\mathsf{L})\det(\mathsf{U})$. Since the determinant of a triangular matrix is given by the product of its diagonal elements, this can be calculated rather easily. Moreover, if (as in the example above) $\mathsf{L}$ is a unit lower triangular matrix (all the entries on its diagonal are 1), only the product of the diagonal elements of $\mathsf{U}$ remains (irrelevant entries are symbolized by asterisks):

\begin{equation*} \det(\mathsf{L})\det(\mathsf{U})= \det\left( \begin{array}{cccc} 1&0&\ldots&0\\ *&1&\ddots&0\\ \vdots&\ddots&\ddots&\vdots\\ *&*&\ldots&1 \end{array} \right) \det\left( \begin{array}{cccc} u_{11}&*&\ldots&*\\ 0&u_{22}&\ddots&*\\ \vdots&\ddots&\ddots&\vdots\\ 0&0&\ldots&u_{nn} \end{array} \right) =u_{11} u_{22} \cdots u_{nn}. \end{equation*}

(5.10)

Implication 2: calculation of the inverse matrix
Not only a linear system $\mathsf{A}\vec{x} = \vec{b}$ can be treated using the LU decomposition but also a matrix equation $\mathsf{A}\mathsf{X} = \mathsf{B}$, since in the latter equation the columns of $\mathsf{X}$ and $\mathsf{B}$ can be treated separately as the former vectors $\vec{x}$ and $\vec{b}$. If $\mathsf{B}$ is chosen to be the unit matrix, then $\mathsf{X}$ will be the inverse of $\mathsf{A}$. More explicitly: If $\vec{b}$ is the $i$-th unit vector $\vec{e}_i$ (having a 1 at position $i$ and zeros elsewhere), then the solution of $\mathsf{A}\vec{x}_i = \vec{e}_i$ will be the $i$-th column of ${\mathsf{A}}^{-1}$.