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$?
How to show determinant of a specific matrix is nonnegative
-
2The 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. – 2011-05-15
3 Answers
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$
-
0Nice! @leonboy: I think the $\theta_i$ can be arbitrary, provided they sum to $\pi$ (since this is what makes $z_{N+1}=-z_1$ work). – 2011-07-05
(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.
-
0Yes @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. – 2011-06-02
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.
-
0The special case for $N=3$, in which the equality applies, is casually mentioned here: http://math.stackexchange.com/questions/49145/cos-hatabc-a-cos-hatbc-ab-cos-hatc-frac-a2-b2-c22 – 2019-02-02