18
$\begingroup$

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 question 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?
  • About its determinant?

Thanks!

  • 2
    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.)2011-05-11
  • 0
    I have yet to read it, but [this](http://dx.doi.org/10.1137/0613034) might be of use. See also [this interesting letter](http://ramanujan.math.trinity.edu/wtrench/research/papers/TN-1.pdf) by Trench.2011-05-11
  • 0
    @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?2011-05-11
  • 1
    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$.2011-05-11
  • 2
    [Crossposted to MO](http://mathoverflow.net/questions/64658). Some patience would be good for you, you know.2011-05-11
  • 0
    @Calle: You are right Gershgorin guarantees you invertibility but it is too weak for most of the cases.2011-05-13
  • 0
    @ght: Have you looked through [this](http://ee.stanford.edu/~gray/toeplitz.pdf) by Robert Gray. It's been several years since I looked and takes a more asymptotic viewpoint, but there may be something of value there for you.2011-05-13
  • 0
    @cardinal: Yes, I did look at this monograph. As you said it is more about the asymptotic behavior and Szego's type theorems. It has a lot of details for Toeplitz matrices that arise as the coefficients of Fourier transforms. It's very nice written and easy to read.2011-05-13
  • 0
    If you're interesting in inferring something from the sequence of elements, consider the sequential [Levinson-Durbin algorithm](https://en.wikipedia.org/wiki/Levinson_recursion) for inverting Toeplitz matrices ($\Theta(n^2)$); it also works on block Toeplitz matrices, according to Wikipedia. There appear to be even faster variants cited therein.2013-12-28

1 Answers 1

2

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\begin{equation} detA^{(2)}=(a_0^2 - a_1^2) \end{equation} If n=3 then \begin{equation} detA^{(3)}=(a_0 - a_2) (a_0^2 - 2 a_1^2 + a_0 a_2) \end{equation} Already at n=4 the formula is not so simple. Indeed if we have n=4 we the determinant become: \begin{equation} detA^{(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 \end{equation} What happens is that when you have to calculate $detA^{(n)}$ the minor determinants of order $n-1$ are matrices where the condition of symmetry that alouded huge semplifications 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...