A $d × d$ triangular matrix $L$ with non-zero diagonal entries can be expressed in the form $(\Delta + A)$, where $Δ$ is an invertible diagonal matrix and $A$ is a strictly triangular matrix. Show how to compute the inverse of $L$ using only diagonal matrix inversions and matrix multiplicatons/additions. Note that strictly triangular matrices of size $d × d$ are always nilpotent and satisfy $A^d = 0$.
It is mentioned a page before that $(I+A)^{-1}=I-A+A^2-A^3+A^4+\dots$ which I see is obtained via Taylor Expansions, using this hint, my attempt:
$(\Delta+A)^{-1}=\\\Delta^{-1}\Delta(A+\Delta)^{-1}=\\\Delta^{-1}[(A+\Delta)\Delta^{-1}]^{-1}=\\\Delta^{-1}(I+A\Delta^{-1})^{-1}$
Expanding:
$\Delta^{-1}[I-A\Delta^{-1}+(A\Delta^{-1})^2-(A\Delta^{-1})^3+\cdots]$
And since $A$ is a nilpotent matrix, any $A^d=0$, therefore:
$(\Delta+A)^{-1}=\Delta^{-1}(I-A\Delta^{-1})$
Although something in my mathematical gut tells me this is ridiculous.
SOURCE: Linear Algebra and Optimization for Machine Learning: A Textbook (Charu C. Aggarwal); page 18 problem 1.2.11
Best Answer
You have that $A^d=0$ only for $d$ the dimension of the triangular matrix. So what you actually have is that $A^k=0$ for $k\ge d$. (This can be seen easily for $A=\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}$)
Furthermore, in your taylor expansion, you have $\left(A\Delta^{-1}\right)^k=\underbrace{A\Delta^{-1}A\Delta^{-1}\ldots A\Delta^{-1}}_{k\text{ times}}\neq A^k(\Delta^{-1})^k$ since matrix multiplication is not commutative. However since $A\Delta^{-1}$ is also a strictly triangular matrix of size $d\times d$ we still have $\left(A\Delta^{-1}\right)^k=0$ for $k\ge d$.
Therefore
$$ (\Delta+A)^{-1}=\Delta^{-1}\sum_{k=0}^{d-1} \left(-A\Delta^{-1}\right)^k=\Delta^{-1}\left(I-\left(A\Delta^{-1}\right)+\ldots\left(-A\Delta^{-1}\right)^{d-1}\right) $$
Which satisfies the requirements (diagonal matrix inversion and matrix multiplication and addition). And a little sanity check never hurts : we indeed get that the inverse of $\begin{pmatrix}1&1&0\\0&1&1\\0&0&1\end{pmatrix}$ is $I-\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}+\begin{pmatrix}0&0&1\\0&0&0\\0&0&0\end{pmatrix}=\begin{pmatrix}1&-1&1\\0&1&-1\\0&0&1\end{pmatrix}$