Exact inversion of matrix complexity (by Gaussian elimination)

[kalish1]

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

**Problem statement:** Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination to find $A^{-1}$. Provide the operation counts for this algorithm.

**My attempted algorithm and operations count:**

Let $[A|I]$ be an augmented $n$ x $2n$ matrix.

INPUT: number of unknowns and equations n, augmented matrix

OUTPUT: $A^{-1}$, provided that the inverse exists

STEP 1: For $i=1,\dots,n-1$ do STEPS 2-4

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

STEP 3: If $p \neq i$ then perform $E_p \leftrightarrow E_i$

STEP 4: For $j=i+1, \dots, n$ do STEPS 5-6

STEP 5: Set $m_{ji}=a_{ji}/a_{ii}$.

STEP 6: Perform $(E_j - m_{ji}E_i) \rightarrow (E_j)$

STEP 7: If $a_{nn}=0$ then output NO UNIQUE SOLUTION EXISTS and STOP

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

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

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

STEP 11: for 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.

 

[jvicens]

Hello,

Your algorithm looks correct and the operation count seems to be correct as well. However, there are a few things to consider:

1. The operation counts for Gaussian elimination can vary depending on the implementation and the specific matrix. So, it is always a good idea to double check your calculations and algorithm for different matrices.

2. The operation counts you have provided seem to be assuming that the inverse exists. If the inverse does not exist, then the algorithm would require additional operations to check for this and output the necessary message.

3. It is also important to note that the operation counts for Gaussian elimination are typically given in terms of Big O notation, which represents the worst-case scenario. So, your operation counts may vary for different matrices.

Overall, your algorithm and operation counts seem to be correct. I hope this helps and good luck with your research.