Questions on Toeplitz matrices: invertibility, determinant, positive-definiteness

Question

These questions are probably very basic but I'll dare to ask them anyway since I didn't have much luck in Math Stack Exchange.

Let $A$ be an $n \times n$ Hermitian Toeplitz matrix:

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

My questions are:

• Is there a relatively "simple" criterion to determine if $A$ is invertible by analyzing the sequence $\{a_0, \ldots, a_{n-1} \}$?

• Idem as before with positive definite?

• In the invertible case, what is known about the structure of the inverse matrix? I seem to recall that this is well known.

• What about the determinant?

Thanks!

Answer 1

A boring answer to some of your questions occurred to me. Here it is.

Just look at the coefficients and check whether $|a_0| \ge \sum_{i \neq 0} |a_i|$. If this holds, then the matrix is diagonally dominant, so that if further, $a_0 \ge 0$, then the matrix will be positive (semidefinite). Also note that if the first inequality stated above is strict, then the matrix is guaranteed to be non-singular.

---

Other comments

Something else that might interest you is the paper: note on inversion of toeplitz matrices, where some necessary and sufficient conditions for invertibility of general Toeplitz matrices are given. In general, searching for "explicit inversion Toeplitz" should give you a large number of useful results.

Answer 2

This is a bit related:

P. Schmidt, F. Spitzer, The Toeplitz matrices of an arbitrary Laurent polynomial, Math. Scand., 8 (1960), 15–38.

For banded Toeplitz matrices, you can get nice asymptotic results for the roots of its characteristic polynomial. This is very much related to computing the determinant. For example, for large enough $n$, there should be a simple criterion for invertibility, in terms of the $a_i$:s.

I actually gave combinatorial proof of their result, by interpreting the determinant as evaluation of Schur polynomials in certain points. This technique might help you. The trick is to use something called the Jacobi-Trudi identities, and consider Schur polynomials for rectangular Young diagrams.

Answer 3

(This should be a comment to the question, you're welcome to change this to one if you can.)

Actually, your requirements are a bit confusing. For a (Hermitian) symmetric Toeplitz matrix, there are no more unique elements besides the first row or column!

1. The simple criterion is to check the diagonal elements of $\boldsymbol{D}$ of $\boldsymbol{L}\boldsymbol{D}\boldsymbol{L}^\text{H}$ which can be computed in $\mathcal{O}(n^2)$ as mentioned by "@J. M. is not a mathematician" in the comment to your question. For matrices, $\mathcal{O}(n^2)$ algorithms are generally considered efficient. It is also (known and) possible to compute inverse of $\boldsymbol{L}$ in $\mathcal{O}(n^2)$, e.g., on my blog.
2. Positive (semi-)definiteness can also be ascertained by looking at the diagonal elements of $\boldsymbol{D}$ for (non-negativity) positiveness.
3. Inverse matrix does not have Toeplitz structure in general. Also, take a look at a possible structure in terms of two triangular matrices here (Huckle, Computations with Gohberg-Semencul-type formulas for Toeplitz matrices, 1998.)
4. When well defined, determinant is the product of the diagonal elements of $\boldsymbol{D}.$