# Positive semidefiniteness of sparse Hermitian Toeplitz matrix

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!

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.