# Inverse of a certain unit upper triangular matrix

I don't know if there is a certain name for this matrix. but I want to show

$$\begin{pmatrix}1&\gamma&\gamma^2& \ldots & \gamma^n\\ &1&\gamma&\ddots&\vdots\\ &&\ddots&\ddots&\gamma^2\\ &&&1&\gamma\\ &&&&1\end{pmatrix}^{-1}= \begin{pmatrix}1&-\gamma&& & \\ &1&-\gamma&&\\ &&\ddots&\ddots&\\ &&&1&-\gamma\\ &&&&1\end{pmatrix}\,\in\mathbb{C}^{(n+1)\times (n+1)}$$

Where the blank spaces of the matrices represent zero entries.

I am not sure how to give a concise proof for this. When I try to use the blockwise inversion or directly multiply these matrices together, I get bogged down in computations. Is any theorem or property I should consider for this proof?

• Can you explain more about your direct multiplication? – alexp9 Oct 2 '18 at 21:40
• @Rhcpy99 I would rewrite the right-hand matrix as a collection of column vectors, multiplying each to the left-hand matrix to get rows of what should be an identity matrix. Something like this. The problem is keeping track of the vectors and knowing what they are doing. So when i=j, jth column of the right hand matrix will give a 1 when multiplied with the ith row on the left hand side, and will give a 0 when i=/=j. However, it is hard to explain why, especially without an explicit description of each vector. – Andreu Payne Oct 2 '18 at 22:05

We can find a nice formula for $$M^{-1}$$, where $$M = \begin{pmatrix}1&-\gamma&& & \\ &1&-\gamma&&\\ &&\ddots&\ddots&\\ &&&1&-\gamma\\ &&&&1\end{pmatrix}$$ In particular, it is useful to note that $$M = I - N$$, where $$N = \begin{pmatrix}0&\gamma&& & \\ &0&\gamma&&\\ &&\ddots&\ddots&\\ &&&0&\gamma\\ &&&&0\end{pmatrix}$$ from there, we could use the Neumann series to compute $$M^{-1} = (I - N)^{-1} = I + N + N^2 + N^3 + \cdots$$ where we note that $$N^k = 0$$ whenever $$k \geq n+1$$. With that, you can conclude that $$M^{-1} = \pmatrix{1&\gamma&\gamma^2& \ldots & \gamma^n\\ &1&\gamma&\ddots&\vdots\\ &&\ddots&\ddots&\gamma^2\\ &&&1&\gamma\\ &&&&1}$$ which is equivalent to the result you're looking for.
A formal (inductive proof) for the formula of $$N^k$$: we wish to show that $$[N^k]_{i,j} = \begin{cases} \gamma^k & j-i = k\\ 0 & \text{otherwise} \end{cases}$$ where $$[A]_{i,j}$$ denotes the $$i,j$$ entry of $$A$$. The base case (either $$k=0$$ or $$k=1$$) holds trivially. For the inductive step: we note that if $$i,j$$ are between $$1$$ and $$n+1$$ $$[N^{k+1}]_{i,j} = [N N^{k}]_{i,j} = \sum_{p=1}^{n+1} N_{ip}[N^k]_{pj}$$ We note that $$N_{ip}[N^k]_{pj}$$ is only non-zero if $$N_{ip} \neq 0$$ and $$[N^k]_{pj} \neq 0$$. By our definition of $$N$$, $$N_{ip}$$ will only be non-zero if $$p = i+1$$. On the other hand: by our inductive hypothesis, $$[N^k]_{pj}$$ will only be non-zero if $$p = j-k$$. These can only be simultaneously true if $$i+1 = j-k$$, which is to say that $$j-i = k+1$$. Thus, we conclude that $$[N^{k+1}]_{i,j} = 0$$ whenever $$j-i \neq k+1$$.
Whenever $$j - i = k+1$$, we compute $$[N^{k+1}]_{i,j} = \sum_{p=1}^{n+1} N_{ip}[N^k]_{pj} = N_{i,(i+1)}[N^k]_{(j-k),j} = \gamma \cdot \gamma^k = \gamma^{k+1}$$ The conclusion follows.
• @AndreuPayne I see now that you're particularly concerned with having a detailed, rigorous proof for the formula. With that in mind, I've added a proof of the formula for $N^k$. I hope this suffices. – Omnomnomnom Oct 3 '18 at 15:44