# How to show determinant of a specific matrix is nonnegative

How to show that $$\det A= \det \begin{pmatrix}\cos\frac{\pi}{n}&-\frac{\cos\theta_1}{2}&0&0&\cdots&0&-\frac{\cos\theta_n}{2} \\-\frac{\cos\theta_1}{2}&\cos\frac{\pi}{n}&-\frac{\cos\theta_2}{2}&0&0&\cdots&0\\ 0&-\frac{\cos\theta_2}{2}&\cos\frac{\pi}{n}&-\frac{\cos\theta_3}{2}&0&\cdots&0\\ \vdots&\vdots&-\frac{\cos\theta_3}{2}&\ddots&\ddots&\vdots&\vdots\\\vdots&\vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\vdots&\vdots&\ddots&\ddots&-\frac{\cos\theta_{n-1}}{2}\\ -\frac{\cos\theta_n}{2}&0&\cdots&0&0&-\frac{\cos\theta_{n-1}}{2}&\cos\frac{\pi}{n} \end{pmatrix} \geq 0,$$ where $\sum\limits_{i=1}^n\theta_i=\pi$, $0<\theta_i<\frac{\pi}{2}, i=1,\dots,n$, and $n\ge 3$?

-
Well, if the product of eigenvalues of a matrix are greater than $0$, then so is the determinant. – user9413 May 13 '11 at 17:33
It might be helpful to tell us where the matrix comes from. – Phira May 13 '11 at 17:42
@leonbloy: it is only positive definite for $n>3$. For $n=3$ the determinant is 0. – Fabian May 13 '11 at 21:47
@Sunni: The context can be quite helpful even for finding a "matricial" proof, in particular for finding the proper generalization. It is also helpful to know how you know that it is true before trying to prove it. But of course, you are not obligated to be helpful. – Phira May 14 '11 at 11:03
The condition of positive matrix (if true) would be equivalent to the following: $\sum x_i^2 cos(\pi/N) \ge \sum x_i x_{i+1} cos(w_i)$ for any $x_i$, any $w_i$ in the first cuadrant with sum $\pi$, $N \ge 3$ - and the $x_{i+1}$ is to be understood mod N. – leonbloy May 15 '11 at 20:25

It was pointed out in the comments that you can interpret the matrix as a bilinear form and obtain the inequality

$$x^T A x = \cos(\pi/N) \sum_{i=1}^N x_i^2 - \sum_{i=1}^N x_i x_{i+1} \cos\theta_i \geq 0 .$$

So, if this bilinear form is positive semidefinite, $x^T A x \geq 0$, then all eigenvalues are nonnegative and the determinant must also be nonnegative.

To show that, we rewrite the inequality by shuffling the terms a bit and adding $\sum x_i^2$ on both sides:

$$\sum \left((x_i^2+x_{i+1}^2)/2 - x_i x_{i+1} \cos\theta_i \right) \geq (1-\cos (\pi/N)) \sum x_i^2 .$$

The left-hand side looks suspiciously like the cosine formula for the side of a triangle. In particular, this looks like a set of vectors in the complex plane that emanate from the origin and are separated by angles $\theta_1,\theta_2,\dots$ and so on. This makes a lot of sense since the angles are meant to add up to $\pi$.

We can make this geometric insight explicit by defining complex numbers $z_i = x_i e^{\sum_{k=1}^{j-1} \theta_j}$ and $z_{N+1} = -z_1$. The inequality becomes

$$1/2 \sum |z_{i+1}-z_i|^2 \geq (1-\cos(\pi/N)) \sum |z_i|^2 .$$

This looks a lot easier, because the angles are finally gone. That said, we are now dealing with complex Hilbert spaces, but they tend to be easier anyway.

In particular, let $P$ be the "permutation operator"

$$P (z_1,z_2,\dots,z_n)^T := (z_2,z_3,\dots,z_n,-z_1)^T .$$

It is easy to check that this is a unitary operator, $P^\dagger=P^{-1}$. The inequality can be written as

$$||(P-1)z||^2 \geq (2-2\cos(\pi/N)) ||z||^2 ,$$

We can prove this by showing that the eigenvalues $\lambda_k$ of the operator $P-1$ are bounded from below by $|\lambda_k|^2 \geq 2-2\cos(\pi/N)$. After all, the operator $P-1$ is normal, so we can apply the spectral theorem.

Calculating the eigenvalues of the operator $P$ is easy, because repeated application of $P$ obviously yields $P^N=-1$, but this must already be the minimal polynomial. Hence, the eigenvalues of $P-1$ are

$$\lambda_k = e^{i\pi k/N}-1, \quad 0 \leq k \leq 2N, k \text{ odd} .$$

Clearly, the case $k=1$ has the smallest magnitude and we have

$$|\lambda_1|^2 = \sin^2(\pi/N) + (1-\cos^2(\pi/N)) = 2-2\cos(\pi/N) .$$

This proves the inequality. $\square$

-
Wait, nevermind, that proof looks sound. Finally! – anon Jul 3 '11 at 18:59
That is great. Is it possible to find a matricial proof? – Sunni Jul 3 '11 at 23:14
@Sunni: What do you mean with "matricial" proof? The operator $P$ is given by a matrix (which I didn't write explicitly) and the key part of the proof is to estimate its eigenvalues. – Greg Graviton Jul 4 '11 at 6:40
Looks promising. But please remind me, why are we allowed to draw the conclusion $||(P-1)z||^2\ge|\lambda_1|^2||z||^2$ ? If $P-1$ were a Hermitian operator, this would be ok, but that doesn't seem to be the case here. I want to rule out the possibility like $$A=\left(\begin{array}{cc}1&a\\0&1\end{array}\right),$$ where the eigenvalues are both $1$ irrespective of the value of $a$, but $z=(a,-1)^T$ behaves badly: $Az=(0,-1)^T$ has norm 1, so with a choice of $a$ we can make $||Az||/||z||$ as small as we want. – Jyrki Lahtonen Jul 5 '11 at 9:31
Never mind. I figured it out. The eigenvectors belonging to different eigenvalues are orthogonal, and that is surely enough. That is automatic for Hermitian matrices, but can be verified here easily enough. The inner product of two eigenvectors belonging to distinct eigenvalues is a sum of $N^{th}$ roots of unity. – Jyrki Lahtonen Jul 5 '11 at 9:39

(too long for a comment, but hopefully somebody more skilled than me can flesh this out as a full answer.)

The matrix in question is a symmetric, cyclic tridiagonal (a.k.a. periodic tridiagonal) matrix, and can be decomposed as

$$\mathbf A=\begin{pmatrix}\cos\frac{\pi}{n}&-\frac12\cos\theta_1&&\\-\frac12\cos\theta_1&\cos\frac{\pi}{n}&\ddots&\\&\ddots&\ddots&-\frac12\cos\theta_{n-1}\\&&-\frac12\cos\theta_{n-1}&\cos\frac{\pi}{n}\end{pmatrix}+\begin{pmatrix}1&0\\0&\vdots\\\vdots&0\\0&1\end{pmatrix}\cdot\begin{pmatrix}0&\cdots&0&-\frac12\cos\theta_n\\-\frac12\cos\theta_n&0&\cdots&0\end{pmatrix}$$

or in abbreviated form, $\mathbf A=\mathbf T+\mathbf U\mathbf V^T$. Using the Sherman-Morrison-Woodbury formula for determinants, we have

$$\det\mathbf A=(\det\mathbf T)\det(\mathbf I+\mathbf V^T\mathbf T^{-1}\mathbf U)$$

Now, a three-term recurrence can be set up to compute $\det\mathbf T$; letting $p_0=1$ and $p_k$ be the determinant of the $k\times k$ leading submatrix of $\mathbf T$, we can establish the recurrence

$$p_k=p_{k-1}\cos\frac{\pi}{n}-\frac{\cos^2 \theta_{k-1}}{4}p_{k-2}$$

and then $\det\mathbf T=p_n$. There is also an explicit formula for the first and last columns of the inverse of a tridiagonal matrix (the result of $\mathbf T^{-1}\mathbf U$) which I will have to look up (unless somebody beats me to it), and proving the nonnegativity of $\det\mathbf A$ boils down to proving that either $p_n$ and $\det(\mathbf I+\mathbf V^T\mathbf T^{-1}\mathbf U)$ have the same sign, or that one of the two is zero.

-
I guess your $\det\mathbf A=(\det\mathbf T)\det(\mathbf I+\mathbf V^T\mathbf A^{-1}\mathbf U)$ should be $\det\mathbf A=(\det\mathbf T)\det(\mathbf I+\mathbf V^T\mathbf T^{-1}\mathbf U)$. the Sherman-Morrison-Woodbury formula for determinants is usually for $U,V$ of rank one, nd.edu/~jeff/Teaching/CBE60478/ShermanMorrison.pdf . Can you show me the reference for your formula $\det\mathbf A=(\det\mathbf T)\det(\mathbf I+\mathbf V^T\mathbf T^{-1}\mathbf U)$. – Sunni May 18 '11 at 0:18
Yes @Sunni; I'll correct that typo. Faddev/Faddeva or Aitken's old books should have it, but if you're knowledgable with Schur complements, it shouldn't be too hard to reckon it yourself. – J. M. Jun 2 '11 at 4:01

This is not an aswer, but was too long for a comment. I suspect that for $N>3$ the matrix is (semi)positive definite, a stronger property than what is asked. As I pointed in a comment, to prove this is equivalent to prove the following:

$$cos(\pi/N) \sum_{i=1}^N x_i^2 \ge \sum_{i=1}^N x_i x_{i+1} cos(\omega_i)$$

for any N angles $0<\omega<\pi/2$ that sum up to $\pi$, and any N real numbers $x_i$, $i=1\cdots N$ (the above formula assumes the convention $x_{N+1}\equiv x_1)$.

We can clearly assume $x_i>0$. Lets fix $N=4$ (only for illustration). Imagine now $N=4$ complex numbers in the upper semiplane, $(z_1, z_2, z_3, z_4)$ with increasing angles, each having modulus $x_i$, and $z_1=x_1$ (real). If we further assume that the consecutive angle differences do not exceed $\pi/2$ (you can imagine also an extra $z_{5}= -z_1$), the LHS can be writen as

$$\sum_{i=1}^N x_i x_{i+1} cos(\omega_i) = Re\left( z_2 \; \bar{z_1} + z_3 \bar{z_2} + z_4 \; \bar{z_3} - z_1 \; \bar{z_4} \right)$$

Notice, BTW, that the terms (all real and imaginary parts) are positive.

We know, applying the Cauchy–Schwarz inequality, that

$$\sum x_i^2 \ge | \left( z_2 \; \bar{z_1} + z_3 \bar{z_2} + z_4 \; \bar{z_3} - z_1 \; \bar{z_4} \right) |$$

We are not there yet - we'd need to show that the complex sum has -say- a substantial imaginary component, so that taking the real part we have a fraction, and that componsates for the missing factor $cos(\pi/N)$ - I'm not sure if it can be done.

-
The special case for $N=3$, in which the equality applies, is casually mentioned here: math.stackexchange.com/questions/49145/… – leonbloy Jul 3 '11 at 19:05