*This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.*

# Counting Operations in Gaussian Elimination

We have seen from The Gaussian Elimination Algorithm and the Computing the Inverse of a Matrix with Gaussian Elimination pages that solving a system of $n$ linear equations in $n$ unknowns, or finding the inverse (provided that it exists) of a square $n \times n$ matrix requires a lot of arithmetic steps, especially when $n$ is very large. It is thus important to determine the length of the computation in terms of counting the number of operations done in the process.

Consider a system of $n$ linear equations in $n$ unknowns and the corresponding $n \times n$ coefficient matrix $A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}$, the $n \times 1$ solution matrix $x = \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}$, and the $n \times 1$ constant matrix $b = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$. Then $Ax = b$. Earlier we saw that at the $(n-1)^{\mathrm{th}}$ step of Gaussian Elimination, we obtain the following system of equations:

(1)The values of the $u$'s and the $g$'s were described on the The Gaussian Elimination Algorithm page. Let $U = \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{nn}\\ 0 & u_{22} & \cdots & u_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & u_{nn}\end{bmatrix}$ be the $n \times n$ coefficient matrix for this equivalent system, and let $g = \begin{bmatrix} g_1\\ g_2\\ \vdots\\ g_n \end{bmatrix}$ be the $n \times 1$ equivalent constant matrix. Then $Ux = g$. Then the following table states the operations count from going from $A$ to $U$ at each step $1, 2, ..., n -1$.

Step Number | Number of Additions/Subtractions from $A \to U$ | Number of Multiplications from $A \to U$ | Number of Divisions from $A \to U$ |
---|---|---|---|

$1$ | $(n - 1)^2$ | $(n - 1)^2$ | $n - 1$ |

$2$ | $(n - 2)^2$ | $(n - 2)^2$ | $n - 2$ |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |

$1$ | $4$ | $4$ | $2$ |

$n-1$ | $1$ | $1$ | $1$ |

Totals: | $\mathrm{Total \: Num. \: of \: Add/Sub} = \frac{n(n-1)(2n-1)}{6}$ | $\mathrm{Total \: Num. \: of \: Multiplications} = \frac{n(n-1)(2n-1)}{6}$ | $\mathrm{Total \: Num. \: of \: Divisions} = \frac{n(n-1)}{2}$ |

We will count the number of additions/subtractions together and the number of multiplications/divisions together. The total number of additions/subtractions and multiplications/divisions in going from $A \to U$ is:

(2)We will now count the number of additions/ subtractions and the number of multiplications/divisions in going from $b \to g$. We have that:

(4)Lastly we count the number of additions/subtractions and multiplications/divisions for finding the solutions from the back-substitution method.

(6)Therefore the total number of operations to obtain the solution of a system of $n$ linear equations in $n$ variables using Gaussian Elimination is:

(8)