# Find the inverse of a lower triangular matrix of ones

Find the inverse of the matrix $A=(a_{ij})\in M_n$ where $$\begin{cases} a_{ij}=1, &i\geq j,\\ a_{ij}=0, &i<j. \end{cases}$$

The only method for finding inverses that I was taught was by finding the adjugate matrix. So $A^{-1}=\frac{1}{\det A}\operatorname{adj(A)}$

$$A=\begin{pmatrix} 1 & 0 &0 &\ldots &0\\ 1 & 1 & 0 &\ldots &0\\ 1 & 1 & 1 &\ldots &0\\ \vdots &\vdots & \vdots &\ddots & \vdots\\ 1 & 1 &1 & \ldots &1 \end{pmatrix}$$

This is a triangular matrix so $\det A=1.$ To find the adjugate I first need to find the cofactor matirx$(C)$ of $A$.

$$C=\begin{pmatrix} 1&-1&0&0&\ldots &0\\ 0 & 1& -1 &0&\ldots & 0\\ 0 & 0 & 1 & -1&\ldots &0\\ 0 & 0 & 0 &1 &\ldots &0\\ \vdots &\vdots &\vdots &\vdots&\ddots & \vdots\\ 0 & 0 &0 &0 &\ldots &1\end{pmatrix}$$

$$C^T=\operatorname{adj}(A)=\begin{pmatrix} 1 & 0 & 0 & 0&\ldots &0\\ -1 & 1& 0 & 0 &\ldots &0\\ 0&-1&1&0&\ldots &0\\ 0& 0 &-1 &1 &\ldots&0\\ \vdots &\vdots &\vdots &\vdots &\ddots&\vdots\\ 0&0&0&0&\ldots &1\end{pmatrix}=A^{-1}$$

Is this correct? Also, can I leave it like that or should I somehow write it more formally?

• try using elementary row operations. – vidyarthi Jan 24 '17 at 10:11
• Looks all right. – StubbornAtom Jan 24 '17 at 10:25
• Try multiplying your proposed $A^{-1}$ by $A$ to see whether you get the identity matrix. – Gerry Myerson Jan 24 '17 at 11:38

Yes, your inverse is correct. Let me show you an alternative approach of finding this inverse without the use of the adjugate matrix.

Denote $A_n$ as the $n \times n$ matrix that has elements $a_{ij} = 1$ if $i \geq j$, and $0$ otherwise. Then, $A_n$ can be constructed by applying the elementary row operations $$R_2 + R_1, R_3 + R_2, \ldots, R_n - R_{n-1}$$ to the identity matrix $I_n$. So, $$A_n = \prod_{i=1}^{n-1} E_i,$$ where $E_i$ is the elementary matrix representing the row operation $R_{i+1} - R_i$. Since det$(A)$ is nonzero, it is invertible, hence $$B_n = \left( A_n \right)^{-1} = \prod_{i = n-1}^{1} {E_i}^{-1},$$ where ${E_i}^{-1}$ is the row operation $R_{i+1} - R_i$. That is, $B_n$ can be constructed by applying the row operations $$R_n - R_{n-1}, R_{n-1} - R_{n-2},\ldots,R_2 - R_1$$ to the idenity matrix $I_n$. The inverse of $A_n$ is therefore given by the matrix
$$B_n = \begin{pmatrix} \phantom{-}1 & \phantom{-}0 &\phantom{-}0 &\ldots &0\\ -1 & \phantom{-}1 & \phantom{-}0 &\ldots &0\\ \phantom{-}0 & -1 & \phantom{-}1 &\ldots &0\\ \phantom{-}\vdots &\phantom{-}\vdots & \phantom{-}\vdots &\ddots & \vdots\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \cdots &1 \end{pmatrix}.$$ In order to check that this is the correct inverse, you can use the identity $$A_nB_n = I_n.$$

• How can we write this inverse like this $B_n=(b_{ij})= \begin{cases} 1, &i= j,\\ -1, &i-j=1\\ 0, & ? \end{cases}$ When is $(b_{ij})=0$? – lmc Jan 24 '17 at 13:31
• $b_{ij}$ is $1$ if $i =j$, $-1$ if $i = j + 1$ and $0$ otherwise. – user394255 Jan 24 '17 at 13:33

I would like to present a very simple solution by interpretation of these matrices as operators on $\mathbb{R^n}$ (which will surprise nobody...). Triangular matrix $A$ acts as a discrete integration operator:

For any $x_1,x_2,x_3,\cdots x_n$:

$$\tag{1}A (x_1,x_2,x_3,\cdots x_n)^T=(s_1,s_2,s_3,\cdots s_n)^T \ \ \text{with} \ \ \begin{cases}s_1&=&x_1&&&&\\s_2&=&x_1+x_2&&\\s_3&=&x_1+x_2+x_3\\...\end{cases}$$

(1) is equivalent to:

$$\tag{2}A^{-1} (s_1,s_2,s_3,\cdots x_n)^T=(x_1,x_2,x_3,\cdots x_n)^T \ \ \text{with} \ \ \begin{cases}x_1&=& \ \ s_1&&&&\\x_2&=&-s_1&+&s_2&&\\x_3&=&&&-s_2&+&s_3\\...\end{cases}$$

and it suffices now to "collect the coefficients" in the right order in order to constitute the inverse matrix.

(Thus the inverse operation is - in a natural way - a discrete derivation operator).

You can also use the induction along the dimension $n$ (leading to a simple but not very constructive proof though).

Let $A_n$ denote the matrix $A$ of dimension $n$ and $B_n$ its inverse. The statement is obviously true for $n=1$ and reduces to showing that $1=1$. Let the statement be true for $n-1$, that is, $A_{n-1}^{-1}=B_{n-1}$. If $1_{n-1}$ and $0_{n-1}$ the column vectors of ones and zeros, respectively, of dimension $n-1$, the matrix $A_n$ can be written in the block form $$A_n=\begin{bmatrix}A_{n-1}&0_{n-1}\\1_{n-1}^T&1\end{bmatrix}.$$ You can easily verify that $$A_n^{-1}=\begin{bmatrix}A_{n-1}^{-1}&0_{n-1}\\-1_{n-1}^TA_{n-1}^{-1}&1\end{bmatrix}$$ is the inverse of $A_n$. By the induction assumption, $A_{n-1}^{-1}=B_{n-1}$. It is easy to check that $1_{n-1}^TA_{n-1}^{-1}=1_{n-1}^TB_{n-1}=e_{n-1}^T:=[0,\ldots,0,1]^T$ (sum of the rows of $B_{n-1}$). So $$A_n^{-1}=\begin{bmatrix}B_{n-1}&0_{n-1}\\-1_{n-1}^TB_{n-1}&1\end{bmatrix}=\begin{bmatrix}B_{n-1}&0_{n-1}\\-e_{n-1}^T&1\end{bmatrix}=B_n.$$

Just to show a different approach.
Consider the matrix $\mathbf E$, having $1$ only on the first subdiagonal $$\mathbf{E} = \left\| {\,e_{\,n,\,m} = \left\{ {\begin{array}{*{20}c} 1 & {n = m + 1} \\ 0 & {n \ne m + 1} \\ \end{array} } \right.\;} \right\| = \left\| {\,\left( \begin{gathered} 0 \\ n - m - 1 \\ \end{gathered} \right)\;} \right\|$$ Multiply it by $\mathbf A$ , and it is easily seen that $$\mathbf E \, \mathbf A=\mathbf A-\mathbf I \quad \Rightarrow \quad \left( \mathbf I -\mathbf E \right)\,\mathbf A=\mathbf I$$

In another way, consider that the powers of $\mathbf E$ are readily found and have a simple formulation $$\begin{gathered} \mathbf{E}^{\,\mathbf{2}} = \left\| {\,\sum\limits_{0\, \leqslant \,k\,\left( { \leqslant \,n - 1} \right)} {\left( \begin{gathered} 0 \\ n - k - 1 \\ \end{gathered} \right)\left( \begin{gathered} 0 \\ k - m - 1 \\ \end{gathered} \right)} \;} \right\| = \left\| {\,\left( \begin{gathered} 0 \\ n - m - 2 \\ \end{gathered} \right)\;} \right\| = \left\| {\,\left\{ {\begin{array}{*{20}c} 1 & {n = m + 2} \\ 0 & {n \ne m + 2} \\ \end{array} } \right.\;} \right\| \hfill \\ \quad \vdots \hfill \\ \mathbf{E}^{\,\mathbf{q}} = \mathbf{E}^{\,\mathbf{q} - \mathbf{1}} \,\mathbf{E} = \left\| {\,\sum\limits_{0\, \leqslant \,k\,\left( { \leqslant \,n - 1} \right)} {\left( \begin{gathered} 0 \\ n - k - \left( {q - 1} \right) \\ \end{gathered} \right)\left( \begin{gathered} 0 \\ k - m - 1 \\ \end{gathered} \right)} \;} \right\| = \hfill \\ = \left\| {\,\left( \begin{gathered} 0 \\ n - m - q \\ \end{gathered} \right)\;} \right\|\quad \left| {\;0 \leqslant \text{integer}\;q} \right. \hfill \\ \end{gathered}$$ Therefore $$\mathbf{A} = \sum\limits_{0\, \leqslant \,j} {\mathbf{E}^{\,\mathbf{j}} } = \frac{\mathbf{I}} {{\mathbf{I} - \mathbf{E}}}$$ To connect to the answer of Jean Marie, note that $$\left( {\mathbf{I} - \mathbf{E}} \right)\left\| {\,\begin{array}{*{20}c} {x_{\,0} } \\ {x_{\,1} } \\ \vdots \\ {x_{\,n} } \\ \end{array} \;} \right\| = \left\| {\,\begin{array}{*{20}c} {x_{\,0} ( - 0)} \\ {x_{\,1} - x_{\,0} } \\ \vdots \\ {x_{\,n} - x_{\,n - 1} } \\ \end{array} \;} \right\| = \left\| {\,\begin{array}{*{20}c} {\nabla x_{\,0} \;\left| {x_{\, - 1} = 0} \right.} \\ {\nabla x_{\,1} } \\ \vdots \\ {\nabla x_{\,n} } \\ \end{array} \;} \right\|$$