0
$\begingroup$

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

$\endgroup$
6
  • $\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
    Commented Apr 12, 2013 at 5:16
  • $\begingroup$ Thanks. I need to brush up on my LaTeX/MathTeX skills. $\endgroup$
    – Phil Kurtis
    Commented Apr 12, 2013 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
    Commented Apr 12, 2013 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
    Commented Aug 19, 2013 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
    Commented Apr 19, 2014 at 15:30

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .