1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ E.g. $CA^{-1}=D$. That's embarrassingly easy. Thanks! $\endgroup$
    – Alex R.
    Mar 26 '14 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.