# Inverse of a lower triangular Toeplitz matrix vs. the matrix size

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.

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.$$
• 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. – Chang Apr 24 '14 at 11:41
• @Chang $e_1=[1,0,\ldots,0]^T$. So $A^{-1}e_1$ is the first column of $A^{-1}$. – Algebraic Pavel Apr 24 '14 at 11:43
• 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... – Chang Apr 24 '14 at 11:54
• @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. – Algebraic Pavel Apr 24 '14 at 12:02