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

  • $\begingroup$ Welcome to math.SE. I am going to edit your question to make the math look nice. (Mostly, this just involves wrapping mathematical expressions in \$s.) Check to see that it still reflects your original intent. $\endgroup$ – Sammy Black Apr 12 '13 at 5:16
  • $\begingroup$ Thanks. I need to brush up on my LaTeX/MathTeX skills. $\endgroup$ – Phil Kurtis Apr 12 '13 at 5:17
  • $\begingroup$ If you know about elementary matrices, it would probably be easier to encode the upward pass of the Gauss-Jordan elimination as elementary matrices to find the inverse. $\endgroup$ – EuYu Apr 12 '13 at 5:22
  • 1
    $\begingroup$ You can easily solve an upper triangular system such as $A x = e_i$ (where $A$ is upper triangular) using "back substitution". Note that $x_n$ (the last component of the unknown vector $x$) is determined immediately. Then you can use $x_n$ to get $x_{n-1}$, and so on. Btw, do you really need to form the inverse of $A$? A rule of thumb is that you almost never want to explicity construct the inverse of a matrix. $\endgroup$ – littleO Aug 19 '13 at 23:35
  • $\begingroup$ @littleO It is really dangerous to write $x=A^{-1}b$ in papers since some might think of it as inv(A)*b instead of A\b :) $\endgroup$ – Algebraic Pavel Apr 19 '14 at 15:30

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.


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.