retagged by
3,238 views

1 Answer

Best answer
4 votes
4 votes

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

selected by

Related questions

22 votes
22 votes
3 answers
1
Kathleen asked Sep 25, 2014
7,049 views
Consider the following set of equations$x+2y=5$$4x+8y=12$$3x+6y+3z=15$This sethas unique solutionhas no solutionhas finite number of solutionshas infinite number of solut...
25 votes
25 votes
5 answers
2
Kathleen asked Sep 25, 2014
7,225 views
Consider the following determinant $\Delta = \begin{vmatrix} 1 & a & bc \\ 1 & b & ca \\ 1 & c & ab \end{vmatrix}$Which of the following is a factor of $\Delta$?$a+b$$a-b...
20 votes
20 votes
4 answers
3
Kathleen asked Sep 25, 2014
6,956 views
The rank of the matrix given below is:$$\begin{bmatrix} 1 &4 &8 &7\\ 0 &0& 3 &0\\ 4 &2& 3 &1\\ 3 &12 &24 &21 \end{bmatrix}$$$3$$1$$2$$4$
1 votes
1 votes
1 answer
4
admin asked Dec 15, 2022
268 views
With no unique solution, solve for $n$ with the following system of equations$$\begin{array}{r}a+b+2 c=3 \\a+2 b+3 c=4 \\a+4 b+n c=6\end{array}$$