3
$\begingroup$

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}$.

Please answer or suggest related reference.

Thanks in advance.

$\endgroup$
  • $\begingroup$ Have you tried something? $\endgroup$ – user88595 May 8 '14 at 8:25
4
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.