## Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated.

**Problem statement:** Consider a non-singular matrix $\displaystyle$A_{nxn}$$. Construct an algorithm using Gaussian elimination to find \displaystyle A^{-1}. Provide the operation counts for this algorithm. **My attempted algorithm and operations count:** Let \displaystyle [A|I]$$ be an augmented $n$ x $2n$ matrix.

INPUT: number of unknowns and equations n, augmented matrix

OUTPUT: $\displaystyle$A^{-1}$$, provided that the inverse exists STEP 1: For \displaystyle i=1,\dots,n-1$$ do STEPS 2-4

STEP 2: Let $p$ be the smallest integer with $\displaystyle$i \leq p \leq n$$such that \displaystyle a_{pi} \neq 0$$. If no integer $p$ exists then output ('no unique solution exists'); STOP

STEP 3: If $\displaystyle$p \neq i$$then perform\displaystyle E_p \leftrightarrow E_i  STEP 4: For \displaystyle j=i+1, \dots, n$$ do STEPS 5-6

STEP 5: Set $\displaystyle$m_{ji}=a_{ji}/a_{ii}$$. STEP 6: Perform \displaystyle (E_j - m_{ji}E_i) \rightarrow (E_j)  STEP 7: If \displaystyle a_{nn}=0$$ then output NO UNIQUE SOLUTION EXISTS and STOP

STEP 8: For $\displaystyle$i=n-1,n-2,\dots ,1$$, For \displaystyle j=i+1,i,\dots ,1$$ do STEPS 9 and 10

STEP 9: Set $\displaystyle$m_{ij}=a_{ij}/a_{jj}

STEP 10: Perform $\displaystyle$(E_i - m_{ij}E_j) \rightarrow (E_i)

STEP 11: for $\displaystyle$i=1, ldots, n$, do$E_i/a_{ii} \rightarrow E_i

STEP 12: OUTPUT $A^{-1}$ and STOP.

**I am getting the operations count as follows:** A total of $(2n^3+9n^2+n)/3$ multiplications and divisions and a total of $(2n^3+6n^2-8n)/3$ additions and subtractions for a grand total of $4n^3/3 + 5n^2 - 7n/3$ operations. **Does this sound about right?**

Thanks for any help.