# Explicit formula for inverse of upper triangular Toeplitz matrix inverse

I have $n \times n$ upper triangular matrix $A$ such as $$\begin{bmatrix} x_1 & x_2 & \ldots & x_n \\ 0 & x_1 & \ldots & x_{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & x_1 \end{bmatrix};$$ then i want to obtain explicit form of $a_{ij}$ of $A^{-1}$ where $a_{ij}$ is the element of $i$th row and $j$th column of $A^{-1}$.

• Have you tried something? – user88595 May 8 '14 at 8:25

You matrix $A = (a_{ij})$ is an upper triangular matrix ( $a_{ij} = 0$ whenever $i > j$ ) and a Toeplitz matrix ( $a_{ij}$ depends only on $i-j$ ) at the same time. I cannot find any reference online which teach you how to evaluate its inverse effectively. I hope this keywords can help you in your own search.

If you just want an inverse without too many other concerns, it is actually pretty easy to get the inverse ourselves. Let $\eta$ be the $n \times n$ matrix with $1$ on its superdiagonal and $0$ otherwise. i.e.

$$\eta = (\eta_{ij}),\quad \eta_{ij} = \begin{cases}1,& i - j = -1\\0,& \text{otherwise}\end{cases}$$

We have $\eta^n = 0$ and we can express $A$ as a polynomial in $\eta$.

$$A = x_1 I + x_2 \eta + x_3 \eta^2 + \cdots + x_n \eta^{n-1}$$

$A$ will be invertible when and only when $x_1$ is non-zero. When $A$ is invertible, $A^{-1}$ is also an upper triangular Toeplitz matrix. We can also represent it as a polynomial in $\eta$.

Introduce numbers $\displaystyle\;\alpha_i = \frac{x_{i+1}}{x_1}$ and $\beta_i$ ( $i = 1,\ldots,n-1$ ) such that

\begin{align} A &= x_1 \left(I + \alpha_1 \eta + \alpha_2 \eta^2 + \cdots + \alpha_{n-1} \eta^{n-1}\right)\\ A^{-1} &= x_1^{-1} \left(I + \beta_1 \eta + \beta_2 \eta^2 + \cdots + \beta_{n-1} \eta^{n-1}\right) \end{align} The condition $A^{-1} A = I$ can be expanded to following set of relations. They will alow you to compute $\beta_k$ in a recursive manner.

\begin{align} -\beta_1 &= \alpha_1\\ -\beta_2 &= \alpha_1 \beta_1 + \alpha_2\\ &\;\vdots\\ -\beta_k &= \alpha_1 \beta_{k-1} + \alpha_2 \beta_{k-2} + \cdots + \alpha_k\\ &\;\vdots \end{align}

When $n$ is small and you want individual $\beta_k$ as a function of $\alpha_k$. There is actually a trick to get it. You can ask a CAS to compute the Taylor expansion of the reciprocal of following polynomial in $t$:

$$\frac{1}{1 + \alpha_1 t + \alpha_2 t^2 + \cdots + \alpha_{n-1} t^{n-1}} = 1 + \beta_1 t + \beta_2 t^2 + \cdots + \beta_{n-1} t^{n-1} + O(t^n)$$

The coefficients of $t^k$ ($1 \le k < n$) in the resulting Taylor expansion will be the expression you want for $\beta_k$. e.g.

\begin{align} \beta_1 &= -\alpha_1,\\ \beta_2 &= \alpha_1^2 - \alpha_2,\\ \beta_3 &= -\alpha_1^3 + 2\alpha_1\alpha_2 - \alpha_3,\\ \beta_4 &= \alpha_1^4 - 3\alpha_1^2\alpha_2 + \alpha_2^2 + 2\alpha_1 \alpha_3 - \alpha_4\\ &\;\vdots \end{align}