4
$\begingroup$

How many integer matrices with the spectral radius bounded by a fixed constant are there? Without any restrictions the answer is infinitely many. Indeed, $nJ_0$, where $J_0$ is the Jordan cell with the eigenvalue $0$ and $n$ is any integer, all have spectral radius $0$. On the other hand, for symmetric matrices the spectral radius is equal to the spectral norm so there are only finitely symmetric integer matrices with bounded spectral radius.

What about other conditions that rule out Jordan cells and other nilpotents? For example, matrices with strictly positive entries, invertible or diagonalizable matrices. I suspect that there are infinitely many invertible or diagonalizable ones, but cannot think of any general construction.

The motivation comes from trying to constructively generate large collections of invertible "random" integer matrices whose spectral radius stays between $1$ and $2$ (it cannot be less than $1$), so that their powers do not explode too quickly. This comes up in encryption.

EDIT: For integer matrices with strictly positive entries this is answered in Does small Perron-Frobenius eigenvalue imply small entries for integral matrices? on MathOverflow There are finitely many because the sum of all entries is bounded by the square of the spectral radius.

$\endgroup$

1 Answer 1

2
$\begingroup$

Mere invertibility and diagonalisability do not work, as shown by the counterexample $\pmatrix{1&k\\ 0&2}$ for an arbitrary $k$. In general, for a reducible matrix of the form $B=\pmatrix{B_1&B_2\\ 0&B_4}$ where $B_1$ and $B_4$ are square submatrices, the value of $B_2$ will not affect $\rho(B)$. The most obvious way to limit the choices of $B_2$ is to set it to zero. That is, to consider matrices that are similar via permutations of rows and columns to a block-diagonal form $$ B=B_1\oplus B_2\oplus\cdots\oplus B_m\oplus0,\tag{1} $$ where each diagonal sub-block $B_i$ is a square irreducible nonnegative matrix. Symmetric matrices and positive matrices can be transformed into the above form via permutations. So, we are considering a more general case here. The argument in an answer to the linked question can be modified to deal with this case. First, suppose $B$ is an irreducible nonnegative integer $n\times n$ matrix for some $n\ge2$. Then $A=(I+B)^{n-1}$ is positive. The linked answer has shown that $\sum_{i,j}a_{ij}\le\rho(A)$. Hence \begin{align} (1+\rho(B))^{n-1} &=\left(\rho(I+B)\right)^{n-1} =\rho\left((I+B)^{n-1}\right) =\rho(A)\\ &\ge\sum_{i,j}a_{ij} =\sum_{i,j}\left((I+B)^{n-1}\right)_{ij}\\ &=\sum_{i,j}\left(\sum_{k=0}^{n-1}\binom{n-1}{k}B^k\right)_{ij}\tag{2}\\ &\ge\sum_{i,j}\left(I+(n-1)B\right)_{\,ij}\\ &=n+(n-1)\sum_{i,j}b_{ij}. \end{align} That is, $$ \sum_{i,j}b_{ij}\le\frac{(1+\rho(B))^{n-1}-n}{n-1}. $$ It follows that if $B$ is a nonnegative integer matrix that is similar via permutations of rows and columns to the form of $(1)$, then there are only finitely many choices of $B$.

Unfortunately, the upper bound above is impractical if you want to generate the desired matrices using the rejection method, because the bound, derived by dropping many higher order terms in the binomial expansion on line $(2)$, is very loose.

$\endgroup$
2
  • $\begingroup$ Thank you. This does not mean that there are finitely many invertible or diagonalizable integer matrices of bounded radius, just those with non-negative entries, right? $\endgroup$
    – Conifold
    Jul 25, 2021 at 16:45
  • $\begingroup$ @Conifold Yes, I was only talking about the number of nonnegative integer matrices that are similar via permutations to the form of $(1)$. $\endgroup$
    – user1551
    Jul 25, 2021 at 16:51

You must log in to answer this question.

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