Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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" criteria 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!

share|improve this question
5  
A few hours is not enough of a wait to cross post. Be more patient; I would say not everybody knows the Gohberg-Semencul formula for Toeplitz inversion, and it takes me a long time to type. –  J. M. May 11 '11 at 18:21
2  
I am interested in whether the positive definiteness of $A$ can be easily told with only the information of $\{a_0,...,a_{n-1}\}$. –  Sunni May 13 '11 at 17:35
2  
@JM: How this helps from the theoretical point of view? What you are saying is essentially check that all the eigenvalues are positive. The interesting question is to check positive definite by analyzing only the first row. –  ght May 14 '11 at 12:18
1  
@JM: I know but I still believe you are missing the point of the question, we are not looking for a "fast" or "good" algorithm in this case. –  ght May 14 '11 at 13:25
1  
... the criterion you are looking for can be checked with a finite algorithm. What exactly do you have against an algorithm? –  J. M. May 14 '11 at 13:38

2 Answers 2

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.

share|improve this answer
    
I think you confused it with a circulant matrix. That condition is not sufficient for diagonal dominance. The second row, for example, will have a_1 twice, right? –  Rojo Jan 4 at 1:39
    
@Rojo: I think it is correct as written (albeit too strong)---here each diagonal entry is $a_0$, and DD stipulates that the diagonal entry be larger than the sum of the remaining entries in that row (btw. the OPs matrix is Hermitian Toeplitz) –  Suvrit Jan 4 at 2:27
    
I'm thinking this. Say the matrix is 3x3. In row 2, the remaining entries would be a1 and a1, so the condition for that row would be a0>|a1|+|a1|, which can fail even if a0>|a1|+|a2| for rows 1 and 3 –  Rojo Jan 4 at 2:34
    
Ok, it seems I made a notational error. But rather than implying DD nature, one can check DD for this matrix very quickly. So I should edit the answer to reflect what I meant. Thanks. –  Suvrit Jan 4 at 3:04

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.