Positive semidefiniteness of sparse Hermitian Toeplitz matrix

Question

I would like to work out some simple condition on the entries of a particular sort of matrix for the matrix to be positive semidefinite. This matrix has the following form

$$ {\bf Q} = \begin{bmatrix}r_0 & r_1 & r_2 & \dots & r_n \\r_1^* & r_0 & r_1 &\dots &r_{n-1}\\r_2^* & r_1^* & r_0 &\dots &r_{n-2}\\\vdots & \vdots &\vdots &\ddots &\vdots\end{bmatrix} $$

where $*$ denotes complex conjugate; in other words it is a Hermitian Toeplitz matrix. In addition, it has a sparsity constraint, only a small number, $q$, of the $n$ coefficients are non-zero; so there are a large number ($2(n-q)$) of diagonal stripes of zeros. ($2(n-q)$ since the diagonal is never zero).

In general, I think it is hard to determine whether Hermitian Toeplitz matrices are positive (semi)definite without looking at the particular example matrix and explicitly checking its eigenvalues, see this question:

https://mathoverflow.net/questions/64658/questions-on-toeplitz-matrices-invertibility-determinant-positive-definitenes

However when the matrix has a particular form more progress can be made:

https://mathoverflow.net/questions/201017/the-maximal-eigenvalue-of-a-symmetric-toeplitz-matrix?noredirect=1&lq=1

https://mathoverflow.net/questions/68099/diagonalizing-a-certain-real-and-symmetric-toeplitz-matrix

How to prove the positive-definiteness of a symmetric Toeplitz matrix like this?

Is this matrix obviously positive definite?

I'm hopeful that the sparsity constraint might provide some foothold for progress, but I haven't managed to make this work myself.

Therefore my question is as stated before: is there some simple condition on the values $r_0, r_1, r_2, \dots, r_n$, of which only $q$ are non-zero, that is synonymous with ${\bf Q}$ being positive (semi)definite? A relaxation would be to consider only real numbers $r_0, r_1, r_2, \dots, r_n$ giving instead a sparse symmetric Toeplitz matrix to study. If you have something that works only for positive-definiteness not positive semidefiniteness I would be equally excited!

Answer 1

My best attempt so far is as follows.

You can test for positive-definiteness of a hermitian martrix by calculating its Cholesky Decomposition: $$Q = LL^{*T}$$, where $L$ is a lower triangular matrix and $^{*T}$ denotes conjugate transpose. If the matrix $Q$ is positive-definite the values in the diagonal of $L$ are real positive numbers and vice versa.

But calculating the cholesky decomposition is also hard, you need to solve for all the elements of the L matrix then check whether the diagonals are positive: order $n^2$ things to work out.

Thankfully the sparsity and Toeplitz-ness of the matrix $Q$ have a big effect on its cholesky decomposition, and you end up only having to work out order $q^2$ things since so much of the $L$ matrix turns out to be zeros or repeats of the same numbers.

I have had some limited success in my use case with this approach. In particular I wanted analytic constraints on the elements of Q for Q to be positive-definite, so that I can optimise a different objective subject to this constraint. I very laboriously derived analytic expressions for the diagonal elements of $L$ when q < 5, constrained them to be positive, then did KKT, and it appeared to work.

I will update this answer and maybe even accept it when I think through everything more comprehensively.