Getting the inverse of a lower/upper triangular matrix

Question

For a lower triangular matrix, the inverse of itself should be easy to find because that's the idea of the LU decomposition, am I right? For many of the lower or upper triangular matrices, often I could just flip the signs to get its inverse. For eg: $$\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -1.5 & 0 & 1 \end{bmatrix}^{-1}= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 1.5 & 0 & 1 \end{bmatrix}$$ I just flipped from -1.5 to 1.5 and I got the inverse.

But this apparently doesn't work all the time. Say in this matrix: $$\begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 3.5 & -2.5 & 1 \end{bmatrix}^{-1}\neq \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ -3.5 & 2.5 & 1 \end{bmatrix}$$ By flipping the signs, the inverse is wrong. But if I go through the whole tedious step of gauss-jordan elimination, I would get its correct inverse like this: $\begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 3.5 & -2.5 & 1 \end{bmatrix}^{-1}= \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 1.5 & 2.5 & 1 \end{bmatrix}$ And it looks like some entries could just flip its signs but not for others.

Then this is kind of weird because I thought the whole idea of getting the lower and upper triangular matrices is to avoid the need to go through the tedious process of gauss-jordan elimination and can get the inverse quickly by flipping signs? Maybe I have missed something out here. How should I get an inverse of a lower or an upper matrix quickly?

Answer 1

Ziyuang's answer handles the cases, where $N^2=0$, but it can be generalized as follows. A triangular $n\times n$ matrix $T$ with 1s on the diagonal can be written in the form $T=I+N$. Here $N$ is the strictly triangular part (with zeros on the diagonal), and it always satisfies the relation $N^{n}=0$. Therefore we can use the polynomial factorization $1-x^n=(1-x)(1+x+x^2+\cdots +x^{n-1})$ with $x=-N$ to get the matrix relation $$ (I+N)(I-N+N^2-N^3+\cdot+(-1)^{n-1}N^{n-1})=I + (-1)^{n-1}N^n=I $$ telling us that $(I+N)^{-1}=I+\sum_{k=1}^{n-1}(-1)^kN^k$.

Yet another way of looking at this is to notice that it also is an instance of a geometric series $1+q+q^2+q^3+\cdots =1/(1-q)$ with $q=-N$. The series converges for the unusual reason that powers of $q$ are all zero from some point on. The same formula can be used to good effect elsewhere in algebra, too. For example, in a residue class ring like $\mathbf{Z}/2^n\mathbf{Z}$ all the even numbers are nilpotent, so computing the modular inverse of an odd number can be done with this formula.

Answer 2

In case of a lower triangular matrix with arbitrary non-zero diagonal members, you may just need to change it in to: $T = D(I+N)$ where $D$ is a diagonal matrix and $N$ is again an strictly lower diagonal matrix. Apparently, all said about inverse in previous comments will be the same.

Answer 3

Computing the inverse misses the whole point of factorizing into triangular matrices. If you have a triangular matrix, you should almost never need to compute the inverse, because solving triangular systems can be done quickly by back/forward-substitution without ever inverting the matrix.

For example, if you have a lower-triangular matrix $L$, and you see an expression like $L^{-1} y$, you should almost never actually compute $L^{-1}$ and then multiply it by $y$. Instead, you would solve $Lx = y$ by forward-substitution, obtaining $x=L^{-1}y$.

More quantitatively, if you have an $m \times m$ upper/lower triangular matrix $T$, then you can solve $Tx=y$ by back/forward-substitution in $\Theta(m^2)$ operations, whereas computing $T^{-1}$ for a general triangular matrix requires $\Theta(m^3)$ operations. (In general, when you see $A^{-1}y$ and you want to compute it, you should read it as "solve $Ax=y$ by the best available method for $A$"; computational scientists almost never explicitly compute inverse matrices.)

Answer 4

Under the assumption of diagonal entries being 1, what you mean is $(I+N)^{-1}=(I-N)$, where $N$ is a nilpotent matrix, yielding $N^2=0$.

If diagonal entries are not all 1's (and none is 0), denote the matrix with only those diagonal entries as $D$, it will be reduced to $N^2=ND^{-1}-DN=D^{-1}N-ND$. Waiting for further simplification.

Answer 5

Given that the diagonal elements of a triangular matrix $A$ are all $1$. It is immediate to see that the characteristic polynomial of $A$ is \begin{align*} f(\lambda) = \det(\lambda I_{(n)} - A) = (\lambda - 1)^n = \lambda^n - \binom{n}{1}\lambda^{n - 1} + \binom{n}{2}\lambda^{n - 2} + \cdots + (-1)^n. \end{align*} By Cayley-Hamilton theorem, this ensues \begin{align*} 0 = A^n - \binom{n}{1}A^{n - 1} + \binom{n}{2}A^{n - 2} + \cdots + (-1)^nI_{(n)}. \end{align*} Rearranging terms yields \begin{align*} A \left((-1)^nA^{n - 1} + (-1)^{n + 1}\binom{n}{1}A^{n - 2} + (-1)^{n + 2}\binom{n}{2}A^{n - 3} + \cdots + (-1)^{2n - 1}\binom{n}{n - 1}I_{(n)}\right) = I_{(n)}. \end{align*} By definition, this shows \begin{align*} A^{-1} = (-1)^nA^{n - 1} + (-1)^{n + 1}\binom{n}{1}A^{n - 2} + (-1)^{n + 2}\binom{n}{2}A^{n - 3} + \cdots + (-1)^{2n - 1}\binom{n}{n - 1}I_{(n)}. \end{align*}

When $n$ is small, this formula should be easy to apply.

Answer 6

I found incredible that, despite all good answers, no one have told the tricky, and key, fact about LU factorization. The Gaussian elimination applied in $A$, would give $P,L$ and $U$ during the process, which would garantee that $P A = L U$. Here, the $L$ matrix that corresponds to the matrix of Gaussian multipliers $m_{i,k}$ used to make zero the $i-$th row in the $k-$th column. For example, if you have multiplied the first row by $-4$ and added with the second row, then the element of the second row and first column of $L$ is $m_{2, 1}=4$ (not $-4$).

The point here is that, luckily, if $L^{-1}=M_n M_{n-1} \cdots M_1$ is a product of atomic matrices obtained during the Gaussian elimination steps which is applied to $A$ to give an upper triangular matrix $U$ (without row exchanges, for simplicity), i.e., $$M_n M_{n-1} \cdots M_1 A = U,$$ then it's easy to calculate $L=(M_n M_{n-1} \cdots M_1)^{-1}$, since $M_k = I - \gamma_k e_k^T$, for some $\gamma_k$ with $e_i^{T}\gamma_k = 0$, if $i \leq k$. The outcome of that all that matrix products is exactly $L$ as described in the first paragraph and here.

On the other hand, what you are asking is how to obtain the entries of matrix $$L^{-1}=M_n M_{n-1} \cdots M_1.$$ The problem is that the Gaussian elimination steps is not capable of retrieving efficiently the entries of that matrix. As you have noticed, some "randon values" that does not make part of elimination steps starts to appear. This way, what you are missing here is that actually nothing have to be inverted here, since the Gaussian steps already retrievies the outcomes of the matrix $L$. In this case, If, for some reason, you need to obtain the inverse of the matrix $A$ to calculate a product $C=A^{-1}B$, the best way is to solve the system $A C = B$ using the best algorithm for it. In the case that you have find that $LU$ factorization fits better in your case, solving first the system $L Y = B$, your product is the solution $C$ of the system $U C = Y,$ i.e., again $$C=A^{-1}B.$$ It's worth to mention that Gauss elimination with complete pivoting, which guarantees that $PAQ=LU,$ for some permutation matrices $P$ and $Q$, is recommended for medium sized problems with bad conditioned matrices and no special structure, since a good implementation of it would consider column and row permutations at once, as done in MATLAB

The MIT OpenCourseWare have a good video briefly explaining this problematic part of LU that you have found, and how $LU$ factorization is thought to be used.