Inverse of an invertible triangular matrix (either upper or lower) is triangular of the same kind

Question

How can we prove that the inverse of an upper (lower) triangular matrix is upper (lower) triangular?

Answer 1

Suppose that $U$ is upper. The $i$th column $x_i$ of the inverse is given by $Ux_i=e_i$ where $e_i$ is the $i$th unit vector. By backward subsitution you can see that $(x_i)_j=0$ for $i+1\leq j\leq n$. I.e all the entries in the $i$th column of the inverse below the diagonal are zero. This is true for all $i$ and hence the inverse $U^{-1}=[x_1|\ldots|x_n]$ is upper triangular.

The same thing works for lower triangular using forward subsitution.

Answer 2

I'll add nothing to alext87 answer, or J.M. comments. Just "display" them. :-)

Remeber that you can compute the inverse of a matrix by reducing it to row echelon form and solving the simultaneous systems of linear equations $ (A \vert I)$, where $A$ is the matrix you want to invert and $I$ the unit matrix. When you have finished the process, you'll get a matrix like $(I\vert A^{-1})$ and the matrix on the right, yes!, is the inverse of $A$. (Why?)

In your case, half of the work is already done:

$$ \begin{pmatrix} a^1_1 & a^1_2 & \cdots & a^1_{n-1} & a^1_n & 1 & 0 & \cdots & 0 & 0 \\\ & a^2_2 & \cdots & a^2_{n-1} & a^2_n & & 1 & \cdots & 0 & 0 \\\ & & \ddots & \vdots & \vdots & & & \ddots & \vdots & \vdots \\\ & & & a^{n-1}_{n-1} & a^{n-1}_n & & & & 1 & 0 \\\ & & & & a^n_n & & & & & 1 \end{pmatrix} $$

Now, what happens when you do back substitution starting with $a^n_n$ and then continuing with $a^{n-1}_{n-1}$...?

Answer 3

Another method is as follows. An invertible upper triangular matrix has the form $A=D(I+N)$ where $D$ is diagonal (with the same diagonal entries as $A$) and $N$ is upper triangular with zero diagonal. Then $N^n=0$ where $A$ is $n$ by $n$. Both $D$ and $I+N$ have upper triangular inverses: $D^{-1}$ is diagonal, and $(I+N)^{-1}=I-N+N^2-\cdots +(-1)^{n-1}N^{n-1}$. So $A^{-1}=(I+N)^{-1}D^{-1}$ is upper triangular.

Answer 4

Personally, I prefer arguments which are more geometric to arguments rooted in matrix algebra. With that in mind, here is a proof.

First, two observations on the geometric meaning of an upper triangular invertible linear map.

1. Define $S_k = {\rm span} (e_1, \ldots, e_k)$, where $e_i$ the standard basis vectors. Clearly, the linear map $T$ is upper triangular if and only if $T S_k \subset S_k$.

2. If $T$ is in addition invertible, we must have the stronger relation $T S_k = S_k$.

   Indeed, if $T S_k$ was a strict subset of $S_k$, then $Te_1, \ldots, Te_k$ are $k$ vectors in a space of dimension strictly less than $k$, so they must be dependent: $\sum_i \alpha_i Te_i=0$ for some $\alpha_i$ not all zero. This implies that $T$ sends the nonzero vector $\sum_i \alpha_i e_i$ to zero, so $T$ is not invertible.

With these two observations in place, the proof proceeds as follows. Take any $s \in S_k$. Since $TS_k=S_k$ there exists some $s' \in S_k$ with $Ts'=s$ or $T^{-1}s = s'$. In other words, $T^{-1} s$ lies in $S_k$, so $T^{-1}$ is upper triangular.

Answer 5

Let $$ A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-1} & a_{1,n}\\ & a_{22} & \cdots & a_{2,n-1} & a_{2,n}\\ & & \ddots & \vdots & \vdots\\ & & & a_{n-1,n-1} & a_{n-1,n}\\ & & & & a_{n,n} \end{pmatrix}. $$ Let $i,j$ be two integers such that $i,j\in\{1,\dots,n\} $ and $i<j$.
Let $A_{i,j}$ be an $n-1\times n-1$ matrix which is obtained by crossing out row $i$ and column $j$ of $A$.
Then, $A_{i,j}$ is
$$ \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,i-1} & a_{1,i} &a_{1,i+1}&a_{1,i+2}&\cdots&a_{1,j-1}&a_{1,j+1}&a_{1,j+2}&\cdots&a_{1n}\\ & a_{22} & \cdots & a_{2,i-1} & a_{2,i} &a_{2,i+1}&a_{2,i+2}&\cdots&a_{2,j-1}&a_{2,j+1}&a_{2,j+2}&\cdots&a_{2n}\\ & & \ddots & \vdots & \vdots &\vdots&\vdots&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ & & & a_{i-1,i-1} & a_{i-1,i} &a_{i-1,i+1}&a_{i-1,i+2}&\cdots&a_{i-1,j-1}&a_{i-1,j+1}&a_{i-1,j+2}&\cdots&a_{i-1,n}\\ & & & & 0 & a_{i+1,i+1}&a_{i+1,i+2}&\cdots&a_{i+1,j-1}&a_{i+1,j+1}&a_{i+1,j+2}&\cdots&a_{i+1,n}\\ & & & & & 0&a_{i+2,i+2}&\cdots&a_{i+2,j-1}&a_{i+2,j+1}&a_{i+2,j+2}&\cdots&a_{i+2,n}\\ & & & & & &0&\cdots&\vdots&\vdots&\vdots&\cdots&\vdots\\ & & & & & &&\ddots&a_{j-1,j-1}&a_{j-1,j+1}&a_{j-1,j+2}&\cdots&a_{j-1,n}\\ & & & & & &&&0&a_{j,j+1}&a_{j,j+2}&\cdots&a_{j,n}\\ & & & & & &&&&a_{j+1,j+1}&a_{j+1,j+2}&\cdots&a_{j+1,n}\\ & & & & & &&&&&a_{j+2,j+2}&\cdots&a_{j+2,n}\\ & & & & & &&&&&&\ddots&\vdots\\ & & & & & &&&&&&&a_{n,n}\\ \end{pmatrix}. $$

So, $\det A_{i,j}=0$ if $i,j$ are two integers such that $i,j\in\{1,\dots,n\} $ and $i<j$.
Let $C_{i,j}$ be the $(i,j)$-cofactor of $A$.
Then, $C_{i,j}=(-1)^{i+j}\det A_{i,j}=0$ if $i,j$ are two integers such that $i,j\in\{1,\dots,n\} $ and $i<j$.
So, $$A^{-1}=\frac{1}{\det A}\begin{pmatrix}C_{11}&C_{21}&\cdots&C_{n,1}\\ C_{12}&C_{22}&\cdots&C_{n,2}\\ \vdots&\vdots&&\vdots\\ C_{1n}&C_{2n}&\cdots&C_{n,n}\\ \end{pmatrix}=\frac{1}{\det A}\begin{pmatrix}C_{11}&C_{21}&\cdots&C_{n,1}\\ 0&C_{22}&\cdots&C_{n,2}\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&C_{n,n}\\ \end{pmatrix}.$$

Answer 6

The proof is based on cayley–hamilton theorem.

Suppose $A$ is upper triangular matrix. Then we know the characteristic polynomial of $A$ is $P_A(\lambda)=(\lambda-\lambda_1)(\lambda-\lambda_2)...(\lambda-\lambda_n)$. By cayley–hamilton theorem we know $P_A(A)=0$, i.e.$(A-\lambda _1I)(A-\lambda _2I)...(A-\lambda _nI)=0$, from where we can see that $I=A\frac{\sum_i{c_iA^i}}{\underset{i}{\Pi}\left( -\lambda _i \right)}$ where $c_i$ can be solved from $P_A(A)=0$. Compare $I=A\frac{\sum_i{c_iA^i}}{\underset{i}{\Pi}\left( -\lambda _i \right)}$ with $I=AA^{-1}$ we can see that $A^{-1}$ is also upper triangular matrix.

Answer 7

Just to be add a simple answer, I will add another one. Note that, by the $QR$ decomposition, for any invertible upper-triangular matrix $U$, there exist an upper-triangular matrix $R$ and an orthogonal matrix $Q$ so that $U^{-1} = Q R.$ Hence, ${(R U)^{-1}} = Q.$ This implies that, inverting both sides, $$R U = Q^{T}.$$ Since the product of two upper-triangular matrices are still upper triangular, we have found an orthogonal upper-triangular matrix, which is impossible unless $Q=D$, for some diagonal Matrix $D$, see this link.. Thus the result follows by noting that $$U^{-1}=Q R = DR,$$ which is upper-triangular.