How can we prove that the inverse of an upper (lower) triangular matrix is upper (lower) triangular?
Inverse of an invertible triangular matrix (either upper or lower) is triangular of the same kind
-
0Try http://www.math.lsa.umich.edu/~tfylam/Math217/proofs05-sol.pdf – 2013-12-10
6 Answers
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.
-
0@J.M.isnotamathematician I see now. You were using the series to justify the claim that $I+N$ has an upper triangular inverse. To me it looked like an unjustified claim, followed by steps to work out what that inverse was. – 2017-09-11
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.
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$.
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.
-
0@jgcello: If $T$ is upper triangular with respect to the chosen basis, then by reading the columns of the matrix representation of $T$, then we see that the first column tells us that $T$ maps $e_1\mapsto T_{11}e_1$, $e_2\mapsto T_{12}e_1 + T_{22}e_2$, $e_3\mapsto T_{13}e_1+T_{23}e_2+T_{33}e_3$, and so on. Hence $TS_k = \mathrm{span}(Te_1,Te_2,Te_3,\dots,Te_k) = \mathrm{span}(T_{11}e_1, T_{12}e_1 + T_{22}e_2,\dots,\sum_{i\le k}T_{ik}e_i) \subset S_k$. – 2018-10-16
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}$...?
You can prove by induction.
Suppose $A$ is upper triangular. It is easy to show that this holds for any $2\times 2$ matrix. (In fact, A^{-1}=\left[\begin{array}{cc} a & b\\ 0 & d \end{array}\right]^{-1} =\frac{1}{ad}\left[\begin{array}{cc} d & -b\\ 0 & a \end{array}\right]. )
Suppose the result holds for any $n\times n$ upper triangular matrix. Let A=\left[\begin{array}{cc} A_{1} & a_{2}\\ 0 & x \end{array}\right], B=\left[\begin{array}{cc} B_{1} & b_{2}\\ b_{3}^{T} & y \end{array}\right] be any $(n+1)\times (n+1)$ upper triangular matrix and its inverse. (Mind that $a_2$, $b_2$, $b_3$ are $n\times 1$ vectors, $x$, $y$ are scalars.) Then $AB=BA=I_{n+1}$ implies that \left[\begin{array}{cc} A_{1} & a_{2}\\ 0 & x \end{array}\right] \left[\begin{array}{cc} B_{1} & b_{2}\\ b_{3}^{T} & y \end{array}\right]= \left[\begin{array}{cc} B_{1} & b_{2}\\ b_{3}^{T} & y \end{array}\right] \left[\begin{array}{cc} A_{1} & a_{2}\\ 0 & x \end{array}\right] =I_{n+1},
From the upper left corner of the second multiplication, we have $B_1 A_1 = I_n$. Hence $B_1$ is upper triangular from our hypothesis. From the lower left block of the multiplication , we know that $b_3=0$. ($x\ne 0$ since $A$ is invertible.) Therefore B=\left[\begin{array}{cc} B_{1} & b_{2}\\ 0 & y \end{array}\right] is also upper triangular.
Another proof is by contradiction. Let $A = [a_{ij}]$ be an upper triangular matrix of size $N$. Assume $B = A^{-1} = [b_{ij}]$ is not upper triangular. Thus there exists an entry $b_{ij} \neq 0$ for $i > j$. Let $b_{ik}$ be the element with the smallest $k$ in row $i$ such that $b_{ik} \neq 0$ and $ i > k$. Consider the product $C = B A$. The element $c_{ik}$ of matrix C is off-diagonal ($i > k$) and computed as $ c_{ik} = \sum b_{ij}a_{jk} = b_{i1}a_{1k} + b_{i2}a_{2k} + \dots + b_{ik}a_{kk} + \dots + b_{iN}a_{Nk} $
Since $b_{ik}$ is the first non-zero element in its row, all the terms to the left of $b_{ik}a_{kk}$ vanish. Since A is upper triangular (given), all the terms to the right of $b_{ik}a_{kk}$ vanish. Since $A$ is invertible, all its diagonal elements are non-zero. Thus $c_{ik} = b_{ik}a_{kk} \neq 0$. However, since $C$ is the identity matrix and $c_{ik}$ is off diagonal, this is a contradiction! Thus, $B = A^{-1}$ is upper triangular.
Same applies to lower triangular matrix by noticing that $(A^T)^{-1} = (A^{-1})^T$
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.