Let $A$ be a $n \times n$ matrix and we want to solve the system of linear equations expressed by $Ax=b$.
We start with the augmented matrix $[A : b]$ and follow the following steps.
- Step 1: Convert the augmented matrix to row echelon form
- Step 2: Convert pivot elements to 1 (leading coefficient of a non zero row) in the resulting matrix
- Step 3: Convert the resulting matrix to row reduced echelon form (equivalent to solve equations by backward substitutions)
Now let us analyze the number of operations performed in each step.
Step 1: It involves multiplying $i^{th}$ row by a constant $c_{ij}$ and subtracting from row $j>i$ to produce $0$ in $ji$ position.
- For first row we have maximum $n+1$ non-zero elements and this requires $(n+1)(n−1)$ operations (multiplication followed by subtraction/addition)
- For the second row we have maximum n non-zero elements and this requires $n(n−2)$ operations
- Like wise the last row will need $3\times 1$ operations.
Total number of multiplication followed by subtraction/addition operations in this step $=(n+1)(n−1)+n(n−2)+(n−1)(n−3)+\ldots+3\times1 = \displaystyle \sum_{i=1}^n i. (i + 2) = \sum_{i=1}^{n-1} i^2 + \sum_{i=1}^{n-1} 2i = \frac{(n-1).n(2n-1)}{6} + n. (n-1) = n(n-1)(2n+5)/6$
Step 2: To convert pivot elements to $1$ we need to divide each non zero row of the matrix obtained after step 1 by the leading coefficient.
Total number of divisions $= (n+1) + n+ (n-1) + (n-2) + \ldots + 2 = n(n+3)/2$
Step 3: It involves back substitutions such that all elements above the pivot elements are zero. To convert all elements to zero above the pivot of $i^{th}$ row, we need $2(n-i)$ number of multiplication followed by subtraction/addition operations.
Total number of multiplication followed by subtraction/addition operations in this step $= 2(1 + 2 + \ldots+ (n-1)) = n(n-1)$
Hence, total number of multiplication followed by subtraction/addition operations required to solve a system of linear equations using Gaussian Elimination $= n(n-1)(2n+5)/6 + n(n-1) = n(n-1)(2n+11)/6.$
