# Eigenvalues of cyclic stochastic matrices

Let's consider the following $$n \times n$$ cyclic stochastic matrix

$$M= \begin{pmatrix} 0 & a_2 & & & &b_n \\\ b_1 & 0& a_3& &&& \\\ & b_2 & 0& \ddots & & \\\ & &\ddots&\ddots &a_{n-1} & \\\ & && &0 &a_n \\\ a_1 & & & &b_{n-1} &0 \end{pmatrix}$$

such that $$\forall i$$, $$a_i,\,b_i$$ are positive real number, $$a_i+b_i = 1$$ and all other component of the matrix are zeros. This is a cyclic matrix in the sense that the associated graph is cyclic.

From the Perron-Frobenius theorem, the eigenvalues $$\lambda$$ of such matrix all belong to the unit disc. $$(\Re \lambda )^2 + (\Im \lambda )^2 \leq 1$$

From numerical explorations, I believe that all eigenvalues of $$M$$ belong to the ellipse $$(\Re \lambda )^2 + \frac{(\Im \lambda )^2}{(\tanh p)^2} \leq 1$$

where $$p$$ denote $$p = \frac{1}{2}\ln \frac{\sqrt[n]{\prod_i a_i}}{\sqrt[n]{\prod_i b_i}}$$, assumed to be positive, otherwise inverse $$a_i$$ and $$b_i$$.

One of the extremal case is the symmetric case $$a_i=b_i$$ where $$p=0$$ and all eigenvalues are real. The equality is reached in the uniform case of all $$a_i$$ to being equal to some value and all $$b_i$$ being equal to another value, the matrix being then a circulant matrix.

I can already prove that the imaginary part of the eigenvalue is bounded by $$\tanh p$$ (see below), but I am unable to extend the prove to include the real part. I also try to play with the Brauer theorem about oval of Cassini exposed into [Horn & Johnson, Matrix Analysis], but it did not get me anywhere

Do you have any hints or suggestions to prove the inclusion of the eigenvalue into the ellipse?

Proof for the imaginary part:

Denote $$z$$ the left eigenvector associated with an eigenvalue $$\lambda$$. We considere only eigenvalue with positive imaginary part, as the negative are recoved by complex conjugaison. We have from the eigenvalue equation $$\lambda z = z M$$, $$\forall i,\quad \lambda = a_i \frac{z_{i-1}}{z_i} + b_i\frac{z_{i+1}}{z_i} = \frac{a_i}{a_i+b_i} \frac{z_{i-1}}{z_i} + \frac{b_i}{a_i+b_i} \frac{z_{i+1}}{z_i},$$ where $$i+1$$ and $$i-1$$ ar evaluated modulo $$n$$, ad the second equality follow from $$a_i+b_i=1$$.

The imaginary part of the previous equation can be rewrite as $$\Im \lambda = \sqrt{|\Im \frac{z_{i-1}}{z_i} ||\Im \frac{z_{i+1}}{z_i}|} \frac{\left( \sqrt{\frac{a_i}{b_i}}\sqrt{\frac{|\Im \frac{z_{i-1}}{z_i}|}{|\Im \frac{z_{i+1}}{z_i}|}} - \sqrt{\frac{b_i}{a_i}}\sqrt{\frac{|\Im \frac{z_{i+1}}{z_i}|}{|\Im \frac{z_{i-1}}{z_i}|}} \right)}{\sqrt{\frac{a_i}{b_i}}+\sqrt{\frac{b_i}{a_i}}} = \sqrt{\Im |\frac{z_{i-1}}{z_i} ||\Im \frac{z_{i+1}}{z_i}|} \frac{\sinh (p_i+\frac{1}{2}\ln |\Im\frac{ z_{i+1} }{z_{i}}|-\frac{1}{2}\ln|\Im\frac{z_{i-1} }{z_{i}}| )}{\cosh p_i} \geq 0,$$ where $$p_i$$ denote $$p_i= \ln \sqrt{\frac{a_i}{bi}}$$. Note that we have $$\Im\frac{z_{i-1} }{z_{i}} \geq 0$$ and $$\Im\frac{z_{i+1} }{z_{i}} \leq 0$$ (I have a long argument for this part, I will think to a shorter one and add it later).

By taking the product of the imaginary part of previous equation for all $$i$$, we get $$\Im \lambda = \sqrt{\prod_i \,|\Im \frac{z_{i-1}}{z_i} ||\Im \frac{z_{i+1}}{z_i}| }\prod_i \frac{\sinh (p_i+\frac{1}{2}\ln |\Im\frac{ z_{i+1} }{z_{i}}|-\frac{1}{2}\ln|\Im\frac{z_{i-1} }{z_{i}}| )}{\cosh p_i} \leq \prod_i \frac{\sinh (p_i+\frac{1}{2}\ln |\Im\frac{ z_{i+1} }{z_{i}}|-\frac{1}{2}\ln|\Im\frac{z_{i-1} }{z_{i}}| )}{\cosh p_i}$$ The inequality use that $$\prod_i \Im \frac{z_{i-1}}{z_i}\leq 1$$. The concavity of $$\ln \sinh$$ and the convexity of $$\ln \cosh$$, give the result $$\Im \lambda \leq \tanh p.$$

• Erm... The displayed formula in your proof is garbled beyond recognition and you can use the concavity of $\log \sinh$ only if all arguments have the same sign – fedja Jun 17 at 13:50
• You're right, I forgot to add the positivity of the imaginary part as hypothesis. This gives a positive argument for the $\ln \sinh$. – Hadrien Jun 17 at 14:51
• I correct the formula and add intermediate steps. I hope it is clearer now. – Hadrien Jun 17 at 15:07