I have an upper triangular matrix that I want to solve the inverse for.
I have $[Ax_i e_i]$ where $x_i$ is the $i$th column from the inverse of $A$ and $e_i$ is the $i$th column of the identity matrix.
If I'm solving for a specific $x_i$, do I need to work with the whole matrix $A$ or just a certain part of it?
I'm thinking I have to use all of matrix $A$, but because it's already in upper triangular form – hence echelon form, I don't need the entirety of $A$.
Best Answer
You can solve this problem inductively. First assume the inverse matrix is upper triangular as well. Then work with the last entry $A_{nn}$ and find its inverse; then try to work with the second to last row with entries $A_{n-1,n-1},A_{n-1,n}$, etc. This should give you enough information to find all the entries of $A^{-1}$ at every step. You may need to solve some questions for elements in the upper right corner in the end. But it is not clear to me if this is computationally any superior to blindly using Cramer's rule, for example.
Another rather silly method is to write out the matrix in blocks. Since it is upper triangular, you may divide it into four blocks with one block a $n-1,n-1$ matrix, one block a $n-1,1$ matrix, one block a $1,1$ matrix and the rest $1,n-1$ block full of $0$. This may reduce the computational complexity slightly if you know the formula for $n-1,n-1$ case already.