# Calculate inverse of arbitrarily sized, lower triangle matrix with a specific pattern.

I have a matrix of the following form:

$$A=\begin{bmatrix} 2 & 0 & 0 & 0 \\-1 & 2 & 0 & 0\\ 0 & -1 & 2 & 0\\ 0 & 0 & -1 & 2 \end{bmatrix}$$

which, in general, can be any size with the pattern continued parallel the diagonal. (I didn't know how to show ellipsis in a matrix with LaTeX, feel free to edit if you know how).

I want to find an inverse for this matrix in general for any given size of the matrix. What should I do? I had thought of maybe splitting the matrix up into two matrices, one with all the diagonal terms and one with all the off-diagonal terms and finding the inverse of their sum but I didn't know if that would be helpful/possible.

• i would suggets to use induction to generaliase from a few initial cases (if of course a pattern is there, you should check it if you find the pattern) – Nikos M. Mar 8 '15 at 2:07

## 3 Answers

HINT: The inverse of your matrix is $$\dfrac{1}{16}\begin{bmatrix}8&0&0&0\\4&8&0&0\\2&4&8&0\\1&2&4&8\end{bmatrix}$$ i.e. for a $4\times 4$ matrix, $$\dfrac{1}{2^4}\begin{bmatrix}2^3&0&0&0\\2^2&2^3&0&0\\2^1&2^2&2^3&0\\2^0&2^1&2^2&2^3\end{bmatrix}$$

You can generalize this result for the inverse of an $n\times n$ matrix that follows your pattern (where $2^4\to 2^n$, $2^3\to 2^{n-1}$ and so on).

QUESTION: Can you prove it?

• That's the question I have too. – NeutronStar Mar 8 '15 at 2:45

Instead of using the matrix write it as linear transformation: so the given one is the matrix of $T$ satisfying $Te_i = 2e_i -e_{i+1}$ for $i<n$ and $Te_n = 2e_n$.

Now the inverse $S$ of this $T$ has to send the vectors in the rhs to those in the corresponding lhs. $S(2e_n) = e_n$ and so $S(e_n) =\frac12e_n$. Then $S(2e_{n-1})= Se_n+e_{n-1}$ And so $Se_{n-1} = \frac12e_{n-1} +\frac12e_n$. Ths way you can work it out for any size without going through inverse calculation (though both are esentally the same).

Here's sort of an abstract algebra- flavored approach:

Notice that the given matrix may be written as

$A = 2I - N, \tag{1}$

where $I$ is the $4 \times 4$ identity matrix and $N$ is the $4 \times 4$ matrix with ones along the subdiagonal and zeroes elsewhere. The present solution extends to similarly structured matrices of any size $n$, so we will use the same notation to represent the corresponding matrices of size $n$. Indeed, much of what is said here will hold independently of $n$; there is a very general, abstract solution to this problem. In fact, there is no essential reason to restrict the multiplier of the matrix $I$ in (1) to the value $2$; we will in fact consider the case

$A = \alpha I - N \tag{2}$

since the essential operations are the same for any non-zero value of $\alpha$. We observe that $N$ is in fact always a nilpotent matrix; that is, no matter what the value of the size $n$ may be, there is always a positive integer $m$ such that

$N^m = 0. \tag{3}$.

For the case $n = 4$ we may in fact take $m = 4$ as well, as direct calculation reveals; indeed, we have in this case

$N = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \tag{4}$

$N^2 = NN =\begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}, \tag{5}$

$N^3 = N^2 N = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}; \tag{6}$

from this point showing that

$N^4 = N^3 N = 0 \tag{7}$

is so simple that I'll omit the details. The essential fact we shall need here is that, for $N$ of size $n$, we have

$N^n = 0, \tag{8}$

but

$N^m \ne 0 \tag{9}$

for $0 \le m < n$. Furthermore, the pattern exhibited in the powers of $N$ (4) - (8), in which successive multiplications by $N$ each move the diagonal of ones a step further toward the lower left-hand corner, until $N^{n - 1}$ finally has but a lonely one in $n, 1$ postion, and zeroes everywhere else:

$(N^{n - 1})_{n1} = 1, \;\; (N^{n -1})_{ij} = 0, (i, j) \ne (n, 1). \tag{10}$

Knowledge of these particular properties of the $N^k$ will play a useful role in the explicit calculation of $(\alpha I - N)^{-1}$, as will be made evident in what follows. The preceding assertions are indeed quite well-known and so I have forgone the effort of offering detailed proofs. Finally, we observe that $N$ is not invertible; to see this, note that since $N^{n - 1} \ne 0$, there is some vector $v$ with $N^{n - 1} v \ne 0$; then $N(N^{n - 1} v) = N^n v = 0$; thus $0 \ne N^{n - 1} v \in \ker N$; $\ker N \ne \{0 \}$; $N^{-1}$ does not exist.

Bearing the above in mind, we compute the inverse of $\alpha I - N$, $\alpha \ne 0$, as follows (note that we have just eliminated the case $\alpha = 0$ by showing that $N$ has no inverse): we write

$A = \alpha I - N = \alpha (I - \alpha^{-1}N), \tag{11}$

and note that we have

$(I - \alpha^{-1}N)(\sum_0^{n - 1} (\alpha^{-1}N)^i) = I - (\alpha^{-n}N^n) = I; \tag{12}$

(12) shows that $I - \alpha^{-1}N$ is invertible with inverse $\sum_0^{n - 1} (\alpha^{-1}N)^i$, which sum terminates with $(\alpha^{-1} N)^{n - 1}$ since $N^n = 0$. Furthermore, $(I - \alpha^{-1}N)^{-1} = \sum_0^{n - 1} (\alpha^{-1}N)^i$ is relatively easy to calculate by virtue of the peculiar structure of the matrices $N^i$ pointed out in the above; indeed, having understood the structure of the powers of $N$ in general terms, it is not even necessary to formally add or multiply any matrices; we merely need to insert the powers of $\alpha^{-1}$ in the appropriate places, since the sum $\sum_0^{n - 1} (\alpha^{-1} N)^i$ almost directly describes the entries of a lower triangular matrix. Thus, the inverse of $I - \alpha^{-1}N$ is most easily had.

Based on the above, and observing that

$\alpha I - N = \alpha(I - \alpha^{-1}N), \tag{13}$

we see that

$(\alpha I - N)^{-1} = \alpha^{-1}(I - \alpha^{-1}N)^{-1} = \alpha^{-1}\sum_0^{n - 1} (\alpha^{-1}N)^i = \sum_0^{n - 1} \alpha^{-(i + 1)} N^i. \tag{14}$

Formula (14) presents a relatively simple and efficient algorithm for calculating $(\alpha I - N)^{-1}$; we apply it to the matrix $A$ of (1) by taking $\alpha = 2$, $n = 4$; then, using (4)-(6) in the role of what is essentially a template, we simply write down the result as

$(2 I - N)^{-1} = \begin{bmatrix} \dfrac{1}{2} & 0 & 0 & 0 \\ \dfrac{1}{4} & \dfrac{1}{2} & 0 & 0 \\ \dfrac{1}{8} & \dfrac{1}{4} & \dfrac{1}{2} & 0 \\ \dfrac{1}{16} & \dfrac{1}{8} & \dfrac{1}{4} & \dfrac{1}{2} \end{bmatrix}, \tag{15}$

in accord with the answer given by Demosthene, who asked

Can you prove it?

The preceeding arguments present both a description of the general pattern and a proof that this pattern applies. QED.

• Very well done, sir. Here, have my upvote :) – Demosthene Mar 9 '15 at 7:48
• @Demosthene: Thank you, my friend! Cheers! – Robert Lewis Mar 9 '15 at 9:36