0
$\begingroup$

Find the inverse of the following lower triangular Toeplitz matrix

$$\mathbf{A}_{M\times M}=\left[\begin{array}{ccccc} 1\\ -a_{1} & 1\\ -a_{2} & -a_{1} & 1\\ \vdots & & & \ddots\\ -a_{M-1} & \cdots & -a_{2} & -a_{1} & 1 \end{array}\right], $$

where $$a_i=\frac{c\Gamma(i-c)}{\Gamma(i+1)\Gamma(1-c)}$$ and $c\in(0,1)$ is a real constant.

I hope to find the closed-form expression of $\Vert \mathbf{A} ^{-1} \Vert_1$, where $\Vert\cdot\Vert_1$ represents the $L_1$ induced norm. (Actually, in this case, it is the summation of the first column of $\mathbf{A}^{-1}$.) And if possible, I hope to find how the matrix size $M$ affects the value of $\Vert \mathbf{A} ^{-1} \Vert_1$, i.e., $$ f(M)=\Vert \mathbf{A}_{M\times M} ^{-1} \Vert_1. $$ Even a tight approximation or bounds are acceptable.

There are some properties of $\{a_i\}$, for example, $\sum_{i=1}^{\infty}a_i=1$. But by now I haven't had ideas how to solve it. I appreciate if anyone could help me.

$\endgroup$
2
$\begingroup$

You can try to start by using a "closed" form formula for the inverse of $A$. Set $A=I-N$, where $N$ is strict lower triangular ($a$'s with $+$ signs), then $$ A^{-1}=(I-N)^{-1}=\sum_{i=0}^{M-1}N^i. $$ So if $\|A^{-1}\|_1=\|A^{-1}e_1\|_1$ (which is true provided that $a$'s are non-negative as $A^{-1}$ is Toeplitz as well), then you would need to evaluate the terms $N^{-1}e_1$.

Another possible hint: Partition $A$ as $$ A=\begin{bmatrix}\tilde{A}&\\a^T&1\end{bmatrix}, $$ where $\tilde{A}$ is the leading principal $(M-1)\times(M-1)$ sub-matrix of $A$ and $a^T=[-a_{M-1},\ldots,-a_1]$. The inverse can be written explicitly as $$ A^{-1}=\begin{bmatrix}\tilde{A}^{-1} & 0 \\ -a^T\tilde{A}^{-1} & 1\end{bmatrix}, $$ so $$ A^{-1}e_1 = \begin{bmatrix}\tilde{A}^{-1}e_1 \\ -a^T\tilde{A}^{-1}e_1\end{bmatrix}. $$ Hence if $x_i$ is the $i$th component of $A^{-1}e_1$ (with $x_1=1$), there is a recursion for $x_M$ in the form $$ x_M=\sum_{i=1}^{M-1}a_{M-i}x_i. $$

$\endgroup$
  • $\begingroup$ Hi @Pavel Jiranek, thanks so much for your reply. For the first part of your answer, I can understand, and I have tried before. But I cannot get the result, since the power of $N$ is also complicated. However, I am not clear your last sentence. What is $e_1$ here? What's $N^{-1}e_1$ stands for? I think the inverse of $N$ doesn't exist. $\endgroup$ – Chang Apr 24 '14 at 11:41
  • $\begingroup$ @Chang $e_1=[1,0,\ldots,0]^T$. So $A^{-1}e_1$ is the first column of $A^{-1}$. $\endgroup$ – Algebraic Pavel Apr 24 '14 at 11:43
  • $\begingroup$ Thanks for your clarification. I think your point is $\Vert \mathbf{A}^{-1} \Vert_1 = \mathbf{A}^{-1}e_1 = \sum_{i=0}^{M-1}N^i e_1$. Is it correct? Now the problem is that even I do so, I cannot get clear expression of $N^i$. I hope the expression of $a_i$ could help... $\endgroup$ – Chang Apr 24 '14 at 11:54
  • $\begingroup$ @Chang Yes, I've meant $\|A^{-1}\|_1=\|A^{-1}e_1\|_1=\|\sum_{i=0}^{M-1}N^ie_1\|_1$. Maybe also you could get some reasonable bound by using the triangle inequality in the last term. $\endgroup$ – Algebraic Pavel Apr 24 '14 at 12:02
  • $\begingroup$ Thanks @Pavel Jiranek. You are so nice. The inverse of the lower triangular Toeplitz matrix has the recursion form, exactly as what you have written. You can have a look at the link: ramanujan.math.trinity.edu/wtrench/research/papers/… But still, I need to think about how to solve it. Thanks. $\endgroup$ – Chang Apr 24 '14 at 12:59

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.