36
$\begingroup$

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

  • 0
    Try http://www.math.lsa.umich.edu/~tfylam/Math217/proofs05-sol.pdf2013-12-10

6 Answers 6

47

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
31

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.

  • 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
13

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

6

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.

4

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$

3

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.