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?

  • About its determinant?


  • 2
    $\begingroup$ 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.) $\endgroup$ May 11 '11 at 12:53
  • $\begingroup$ I have yet to read it, but this might be of use. See also this interesting letter by Trench. $\endgroup$ May 11 '11 at 13:34
  • $\begingroup$ @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? $\endgroup$
    – ght
    May 11 '11 at 14:19
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Calle
    May 11 '11 at 18:24
  • 5
    $\begingroup$ Crossposted to MO. Some patience would be good for you, you know. $\endgroup$ May 11 '11 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

\begin{equation} \det A^{(2)} = a_0^2 - a_1^2 \end{equation}

If $n=3$ then

\begin{equation} \det A^{(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} \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 \end{equation}

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


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.