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?


1 Answer 1


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$ Jan 9, 2015 at 16:05
  • 1
    $\begingroup$ You're right. I've corrected that. $\endgroup$ Jan 9, 2015 at 16:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .