# Checksum Invariants for Matrix Inversion via Gaussian Elimination

In general, when solving $Ax=b$, we make the $[A|b]$ matrix and doing row operations to reduce the left hand side to an identity.

It's painfully annoying to find mistakes in the process. Assuming we know the solution, one nice way that I know of is to plug in the solution into $[C|d]$, the current augmented form and see if both sides agree. I like to think of this an a checksum or an invariant. This is in the worst case an $O(n^2)$ operation if the matrix is $n\times n$.

Now, onto finding the inverse matrix with Gaussian Elimination. Then general setup here is the augmented form $[A|I]$ where $I$ is the $n\times n$ identity and the goal here is to do row operations to get to $[I|A^{-1}]$. Thus at any given point, we have two matrices $[C|D]$

Question: Supposing that I know what $A^{-1}$ is, is there a nice $O(n^3)$ checksum for each step of row elimination for finding the inverse? In other words, what are some nice invarients that $C,D$ must satisfy at any given step?

Consider an invertible matrix $A$. Then the 1st column of $A^{-1}$ is the system's response to $e_1=(1,0,\ldots,0)^T$ (i.e. the 1st column of $A^{-1}$ is the solution of the system $Ax=e_1$). Similarly the $i$th column of $A^{-1}$ is the response to $e_i$ (i.e. the $i$th column of $A^{-1}$ is the solution of the system $Ax=e_i$, where $e_i=(0,\ldots,0,1,0,\ldots,0)^T$ is the $i$th vector of the standard (impulse) basis). So, if we denote by $a_i$ the $i$th column of $A^{-1}$ then we should expect $C a_i = d_i$, where $d_i$ is the $i$th column of matrix $D$.
• E.g. $CA^{-1}=D$. That's embarrassingly easy. Thanks! Mar 26 '14 at 20:38