Inverse of a Toeplitz matrix

A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is an $$n\times n$$ Toeplitz matrix:

$$A = \begin{bmatrix} a_{0} & a_{-1} & a_{-2} & \ldots & \ldots &a_{-n+1} \\\ a_{1} & a_0 & a_{-1} & \ddots & & \vdots \\ a_{2} & a_{1} & \ddots & \ddots & \ddots& \vdots \\\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2}\\\ \vdots & & \ddots & a_{1} & a_{0}& a_{-1} \\ a_{n-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{bmatrix}$$

I'm interested in the self-adjoint case ($$a_{-k}=a_{k}\in\mathbb{R}$$).

My questions are:

• Is there a relatively simple criterion to know when these matrices are invertible by just analyzing the sequence $$\{a_{0},\ldots,a_{n-1}\}$$?

• In the invertible case, what is known about its inverse?

Thanks!

• If $\mathbf A$ is symmetric positive definite and Toeplitz, then there is an $O(n^2)$ method due to Trench for inverting it. So the SPD case is easy at least; what I'm fuzzy with is if (stable) methods for the symmetric indefinite case have been developed. (There are $O(n\log n)$ methods based on FFT, but I have no experience with using them.) Commented May 11, 2011 at 12:53
• I have yet to read it, but this might be of use. See also this interesting letter by Trench. Commented May 11, 2011 at 13:34
• @Tom: Interesting. Your comment also raised a good question. What are the conditions on the sequence $\{a_0,\ldots,a_{n-1}\}$ for $A$ to be positive definite?
– ght
Commented May 11, 2011 at 14:19
• You can apply the Gershgorin circle theorem to get a sufficient result for $A$ to be invertible, namely that it is strictly diagonally dominant $$|a_0| > \sum_{i=1}^{n-1} |a_i|$$ If this is true, a sufficient condition for it to be positive definite is that $a_0>0$. Commented May 11, 2011 at 18:24
• Crossposted to MO. Some patience would be good for you, you know. Commented May 11, 2011 at 18:32

About the last point of you question I think it's not really simple to state a closed simple formula for the determinants. I tried to see if there are symmetries. There are but not really useful (at least as far as I can see).

Just to have an idea the first 3 steps of the induction you have the following determinants.

If $$n=2$$ then

$$$$\det A^{(2)} = a_0^2 - a_1^2$$$$

If $$n=3$$ then

$$$$\det A^{(3)} = (a_0 - a_2) (a_0^2 - 2 a_1^2 + a_0 a_2)$$$$

Already at $$n=4$$ the formula is not so simple. Indeed if we have $$n=4$$ we the determinant become:

$$$$\det A^{(4)} = a_0^4 + a_1^4 + a_2^4 - 2 a_1 a_2^2 a_3 +4 a_0 a_1^2 a_2 - 3 a_1^2a_0^2 -2 a_2^2a_1^2 - 2 a_2^2a_0^2 + a_3^2a_1^2 - a_3^2a_0^2 - 2 a_1^3 a_3 + 4 a_0 a_1 a_2 a_3$$$$

What happens is that when you have to calculate $$\det A^{(n)}$$ the minor determinants of order $$n-1$$ are matrices where the condition of symmetry that allowed huge simplifications disappears. With n=2,3 the problem is not so big since the minors are trivial, but when n gets bigger the problems arise. In fact the minors are not really Toeplitz matrix, but "block Toeplitz Matriz" (sort of saying). So maybe there could be a way of enclosing the writing in a simple notation formula, but it wouldn't be a real computational gain...

I’m not sure whether this counts as ‘relatively simple’: Xiao-Guang Lv and Ting-Zhu Huang published A note on inversion of Toeplitz matrices. According to their Theorem 1, checking invertibility can be reduced to the solvability of just two specific systems of linear equations, and the inverse is described explicitly in terms of the solutions of these equations.