Positive matrix with integer eigenvalues

The $n \times n$ matrix with diagonal entries $b$ and off-diagonal entries $a$ has eigenvalues $b-a$ (with multiplicity $n-1$) and $b + (n-1) a$.


If you are fine with some restrictions on eigenvalues, then this procedure might be helpful:

  1. Generate orthonormal matrix $S$ with the first column being in the direction of $u=(1,1,\ldots 1)$. For example, you can start with the vector $u$ and $d-1$ random vectors and apply Gram-Schmidt process to them.

  2. Create $J=\begin{pmatrix}\lambda_1&0&\cdots\\0&\lambda_2&\cdots\\\cdots&\cdots&\cdots\end{pmatrix}$. Where all lambdas are positive and $\lambda_1$ is sufficiently large.

  3. Now matrix $M=SJS^{-1}$ has all positive values (if not, increase $\lambda_1$) and eigenvalues $\lambda_i$.

You can also make matrix $M$ integer by replacing $S$ with its rational approximation ($S_1=\frac1N[NS]$) and multiplying the matrix $M$ by the common denominator of its elements. That will also increase the eigenvalues, but if you don't care what they are, that's fine.

Example: Start with $$ S_0 = \begin{pmatrix}1&0&0&0\\1&1&0&0\\1&0&1&0\\1&0&0&1\end{pmatrix}. $$ After Gram-Schmidt and rationalization: $$ S_1 = \begin{pmatrix}0.5&-0.29&-0.41&-0.71\\0.5&0.87&0&0\\0.5&-0.29&0.82&0\\0.5&-0.29&-0.41&0.71\end{pmatrix}. $$ Take $$ M=S_1\begin{pmatrix}5&0&0&0\\0&1&0&0\\0&0&2&0\\0&0&0&3\end{pmatrix}S_1^{-1} = \frac16\begin{pmatrix}19&6&4&1\\6&12&6&6\\4&6&16&4\\1&6&4&19\end{pmatrix}. $$ Thus, matrix $M'=6M$ is integer and has eigenvalues $(30,6,12,18)$.


The problem of determining which complex spectrum can be realised by a nonnegative matrix is known as a nonnegative inverse eigenvalue problem. For an overview, you may read the following survey paper:

Egleston, Lenker, and Narayan, The nonnegative inverse eigenvalue problem, Linear Algebra and Its Applications, 379 (2004), 475-490.

Your requirement is more demanding because the matrix in question is not just nonnegative, but positive. Certainly, not every spectrum is realisable, because the spectrum has to satisfy the Perron condition (that the spectral radius is a simple eigenvalue) and some other necessary conditions (such as the trace condition $\operatorname{tr}(A^k)=\sum_i\lambda_i^k>0$ for every positive integer $k$). Since the literature is vast, I am not sure if the problem has been solved yet, or whether there is a constructive method for a wide class of spectra, but I'll exhibit a simple constructions below that is applicable for some spectra.

Given any decreasing sequence of integers $\lambda_1>\lambda_2\ge\cdots\ge \lambda_n\ge0$, the matrix $$ \begin{aligned} A&=\pmatrix{1\\ t&1\\ t&&1\\ \vdots&&&\ddots\\ t&&&&1} \pmatrix{\lambda_1&1&1&\cdots&1\\ &\lambda_2\\ &&\lambda_3\\ &&&\ddots\\ &&&&\lambda_n} \pmatrix{1\\ -t&1\\ -t&&1\\ \vdots&&&\ddots\\ -t&&&&1}\\ &=\pmatrix{\lambda_1-(n-1)t&1&1&\cdots&1\\ (\lambda_1-\lambda_2)t-(n-1)t^2&\lambda_2+t&t&\cdots&t\\ (\lambda_1-\lambda_3)t-(n-1)t^2&t&\lambda_3+t&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&t\\ (\lambda_1-\lambda_n)t-(n-1)t^2&t&\cdots&t&\lambda_n+t} \end{aligned} $$ is entrywise positive when $t>0$ is sufficiently small, and the eigenvalues of $A$ are the integers $\lambda_1,\lambda_2,\ldots,\lambda_n$. When $\lambda_1-\lambda_2\ge n$, we may choose $t=1$, so that the previous construction gives a positive integer matrix with a prespecified integer spectrum.

This construction can be generalised to the case where $$ \begin{cases} \lambda_1>\lambda_2\ge\cdots\ge\lambda_k\ge0>\lambda_{k+1}\ge\cdots\ge\lambda_n \text{ and}\\ \lambda_1-\lambda_2>\sum_{i=k+1}^n|\lambda_i|. \end{cases} $$ Let $e$ and $\tilde{e}$ denote the all-one vector in $\mathbb R^{k-1}$ and $\mathbb R^{n-k}$ respectively, $\Lambda=\operatorname{diag}(\lambda_2,\ldots,\lambda_k)$ and $\widetilde{\Lambda}=\operatorname{diag}(\lambda_{k+1},\ldots,\lambda_n)$. Now let $t>0$ be sufficiently small. Define $$ \begin{aligned} A&= \pmatrix{1\\ te&I\\ \tilde{e}&&I} \pmatrix{\lambda_1&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ &\Lambda\\ &&\widetilde{\Lambda}} \pmatrix{1\\ -te&I\\ -\tilde{e}&&I}\\ &= \pmatrix{\lambda_1&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1te&tee^T+\Lambda&te\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1\tilde{e}&\tilde{e}e^T&\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}} \pmatrix{1\\ -te&I\\ -\tilde{e}&&I}\\ &= \pmatrix{\lambda_1-te^Te-\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}&e^T&\tilde{e}^T(tI-\widetilde{\Lambda})\\ t\lambda_1e-t(tee^T+\Lambda)e-te\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}&tee^T+\Lambda&te\tilde{e}^T(tI-\widetilde{\Lambda})\\ \lambda_1\tilde{e}-t\tilde{e}e^Te-\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})\tilde{e}-\widetilde{\Lambda}\tilde{e}&\tilde{e}e^T&\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}}. \end{aligned} $$ The first column of $A$ is given by $$ a_{i1}= \begin{cases} \lambda_1-\sum_{i=k+1}^n|\lambda_i|-(n-1)t&\text{when } i=1,\\ \left(\lambda_1-\lambda_i-\sum_{i=k+1}^n|\lambda_i|-(n-1)t\right)t&\text{when } 1<i\le k,\\ \left(\lambda_1-\lambda_i-\sum_{i=k+1}^n|\lambda_i|-(n-1)t\right)&\text{when } i>k \end{cases} $$ and hence it is positive. The second block column of $A$ is clearly positive. On the last block column, since $\tilde{e}^T(tI-\widetilde{\Lambda})$ is a positive vector, the first two sub-blocks are positive. The last sub-block $\tilde{e}\tilde{e}^T(tI-\widetilde{\Lambda})+\widetilde{\Lambda}$ is equal to $$ \pmatrix{t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|\\ t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|\\ \vdots&\vdots&&\vdots\\ t+|\lambda_{k+1}|&t+|\lambda_{k+2}|&\cdots&t+|\lambda_n|} -\pmatrix{|\lambda_{k+1}|\\ &|\lambda_{k+2}|\\ &&\ddots\\ &&&|\lambda_n|}, $$ which is positive too. Therefore $A$ is a positive matrix.