# Which n-tuples of positive integers can be the eigenvalues of some matrix with positive integer entries?

Given a tuple of positive integers (such as (1,2,5) ), is there a matrix A with positive integer entries such that the integers in the tuple are its eigenvalues (In our example, the matrix [ [2,1,1] , [1,2,1] , [1,1,4] ] does the job) ? I am only interested in tuples with distinct values.

Note, that the answer is trivial if zeros are allowed.

I came across the useful perron-frobenius-theorem, which rules out many possible tuples. The main question is : Is there any number n such that there is a nxn-matrix A with positive integers with the eigenvalues 1,...,n ?

For 2x2-matrices I have checked that every tuple [m,n] with n > m + 1 is possible. For 3x3-matrices I have checked that the lowest possible value for the largest eigenvalue is 5. For 4x4-matrices, my record for the lowest largest eigenvalue is 7, for 5x5 it is 8. A nice answer to an earlier question proves that for every n there is a matrix with largest eigenvalue 2n, but there is still room for the optimal.

• Concerning my main question : If there is a matrix with the desired property, it must have a row whose entries are all 1 and a column with the same property. Perhaps someone can answer the main question using this. – Peter Jul 10 '14 at 22:09
• Could you perhaps provide links to the relevant earlier questions? – Lee Mosher Jul 10 '14 at 23:27

Concerning your main question, it is impossible for a matrix $A_{n\times n}$ with positive integers to have the biggest eigenvalue equals to $n$, unless $A$ is the matrix with all entries equal to $1$.

If $n$ is the biggest eigenvalue of $A$ then associated to $n$ exists an eigenvector $v$ with strictly positive coordinates, by item 3 here in the subsection "positive matrices".

As you notice in your comment, $A$ has a row with all entries equal to $1$, wlog suppose it is the first row. Therefore the first coordinate of $Av=nv$ is $v_1+\ldots+v_n=n v_1$.

Assume $v_i=\min\{v_j, 1\leq j\leq n\}$.

Now, the coordinate $i$ of $Av=nv$ is $a_{i1}v_1+\ldots+a_{in}v_n=nv_i$.

Next, $a_{i1}v_1+\ldots+a_{in}v_n=nv_i\leq nv_1= v_1+\ldots+v_n$.

Since each $a_{ij}\geq 1$, we obtain $a_{i1}=\ldots=a_{in}=1$ and $v_i=v_1$.

Now, since $v_1=\min\{v_j, 1\leq j\leq n\}$ and $v_1+\ldots+v_n=n v_1$ then $v_1=\ldots=v_n$.

Thus, $\frac{1}{v_1}v=(1,\ldots,1)$ is an eigenvector of $A$ associated to $n$. Therefore every row sum of $A$ is $n$. Thus, $A$ is a matrix with all entries equal to $1$.