Given two positive integers $n$ and $a \leq \frac{n}{2}$ consider a $n \times n$ matrix $A$ such that,

  • all the diagonal entries are either $a$ or $a+1$
  • all the non-zero off-diagonal entries are $\pm 1$
  • if $A_{ii} =a$ then the $i^{th}$ row and the $i^{th}$ column have $a$ non-zero off-diagonal entries. (..and similarly for $A_{ii} = a+1$..)

Is something known about such matrices? Are they characterized somehow? Like what would their maximum eigenvalue be?


Gerschgorin's circle theorem gives the upper bound $2(a+1)$ for the eigenvalues. This bound should be sharp if I'm not mistaken. I think the family of $n\times n$ circulant matrices $$\begin{pmatrix} 2 & -1 & 0 & \cdots & 0 & -1 \\ -1 & 2 & -1 & 0 & \cdots & 0 \\ \vdots & & \ddots & & & \vdots \\ 0 & \cdots & 0 & -1 & 2 & -1 \\ -1 & 0 & \cdots & 0 & -1 & 2 \end{pmatrix}$$ should have maximal eigenvalue arbitrarly close to $2\cdot (1+1)$ (here $a=1$) for $n\gg 0$. If I didn't make any mistakes the eigenvalues of this matrix are $2-2\cos(\frac{2\pi j}{n})$ for $j=0,1,\ldots,n-1$. For $j=\lfloor \frac{n}{2} \rfloor$ and $j=\lceil \frac{n}{2} \rceil$ this is maximal and arbitrary close to 4, even equal to 4 if $2\mid n$.

EDIT: And just as I finished writing the first part of this post I remembered the Perron-Frobenius theorem. Considere the matrices with constant diagonal $a+1$ and exactly $a+1$ times an entry equal to +1 off the diagonal in each row. These are positive matrices and have constant row sum $2(a+1)$. Therefore this row sum is an eigenvalue with eigenvector $(1,1,\cdots,1)^T$. It coincides with the $\infty$-operator norm (=row sum norm) of the matrix and is therefore equal to the spectral radius. These matrices therefore attain the upper bound exactly.

  • $\begingroup$ In the first part, what you write looks rather like the minimal positive eigenvalue. (For large $n$, it is almost zero). $\endgroup$ – Vladimir Dotsenko Jan 9 '15 at 16:05
  • 1
    $\begingroup$ You're right. I've corrected that. $\endgroup$ – Johannes Hahn Jan 9 '15 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.