Calculation involving determinant of a matrix

Question

Suppose I have the following Toeplitz symmetric matrix

\begin{align} M=\begin{bmatrix} 1 & c & c & x \\ c & 1 & c & c \\ c & c & 1 & c \\ x & c & c & 1 \end{bmatrix} \end{align}

I want to write an algorithm that takes $c$ as input and calculates the range of $x$ for which matrix $M$ is positive semidefinite.

Currently, I do Gaussian elimination by hand and reduce the problem to checking the determinant of a $2 \times 2$ matrix. But how do I automate the process so I can write a function that takes $c$ and $n$ as inputs, where $n$ is the dimension of $M$, and returns the range of $x$. Thanks!

Answer 1

Hint:

Definiteness can be assessed by the signs of the leading principal minors. The minors of order up to $n-1$ have the same Toeplitz structure and are functions of $c$ alone, let $N_k(c)$.

Now notice that the determinant of the matrix $M$ is a quadratic function of $x$, and an obvious root is $x=1$. In addition, the determinant evaluated at $x=c$ is $N_n$. And finally, the coefficient of the term $x^2$ is $N_{n-2}$, by removing the top-right and bottom-left elements.

Hence the determinant is

$$\det(M)=N_{n-2}(x-r)(x-1)$$

with $$N_{n-2}(c-r)(c-1)=N_n$$

and the second root is

$$r=c-\frac{N_n}{N_{n-2}(c-1)}.$$

Answer 2

For your specific example, done with pen and paper, $$M_4=\left( \begin{array}{cccc} 1 & c & c & x \\ c & 1 & c & c \\ c & c & 1 & c \\ x & c & c & 1 \end{array} \right)$$ $$\Delta_4=\left(4 c^3-5 c^2+1\right)+\left(4 c^2-4 c^3\right) x+\left(c^2-1\right) x^2$$ With a computer $$M_5=\left( \begin{array}{ccccc} 1 & c & c & c & x \\ c & 1 & c & c & c \\ c & c & 1 & c & c \\ c & c & c & 1 & c \\ x & c & c & c & 1 \end{array} \right)$$ $$\Delta_5=\left(-6 c^4+14 c^3-9 c^2+1\right)+6 \left(c^4-2 c^3+c^2\right) x+\left(-2 c^3+3 c^2-1\right) x^2$$

Answer 3

Essentially, you want to compute the diameter of a $1$-dimensional spectrahedron. This diameter can be found by solving two semidefinite programs

$$\begin{array}{ll} \text{minimize} & \pm x\\ \text{subject to} & \begin{bmatrix} 1 & c & c & x \\ c & 1 & c & c \\ c & c & 1 & c \\ x & c & c & 1 \end{bmatrix} \succeq \mathrm O_4\end{array}$$

---

spectrahedra linear-matrix-inequality semidefinite-programming