show/hide this revision's text 2 deleted 256 characters in body

I claim that any algebraic integer $\lambda$ is the eigenvalue of a nonnegative matrix with integer coefficients. This answer relies on Doug Lind's answer here. Let $\lambda_1$, $\lambda_2$, ..., $\lambda_r$ be the Galois conjugates of $\lambda$. Let $\ell = \max(|\lambda_i|)$. Choose an integer $L$ large enough that $L^n \cdot (L-2)/(L-1) > \ell^n \cdot \ell/(\ell-1)$ for all positive integers $n$. I claim there will be a nonnegative integer matrix with eigenvalues $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$ where there are $r$ copies of $L$.

Let $\mu_1$, $\mu_2$, ..., $\mu_{2r}$ be $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$. According to Lind's answer, all we have to check is that, for all $n>0$, $$\frac{1}{n} \sum_k \sum_{d|n} \mu(n/d) \mu_k^d$$ is a nonnegative integer.

It's an integer: Let $g(x) = \prod_{i=1}^{2r} (x-\mu_i)$. Since $\lambda$ is an algebraic integer, $g$ is a monic polynomial with integer coefficients. So there is a $(2r) \times (2r)$ integer matrix $B$ with characteristic polynomial $g$ -- the companion matrix. The above sum is $$\sum_{(i_1 i_2 \cdots i_n)} B_{i_1 i_2} B_{i_2 i_3} \cdots B_{i_{n-1} i_n} B_{i_n i_1}$$ where As explained on the sum runs over "primitive necklaces second paper Lind links, if $(i_1 i_2 \cdots i_n)$". What this g$ is that we are summing over equivalence classes of sequences $(i_1 i_2 \cdots i_n)$, where the equivalence is $$(i_1, i_2, \ldots, i_n) \sim (i_2, \ldots, i_n, i_1) \sim \cdots \sim (i_n, i_1characteristic polynomial of an integer matrix, \ldots, i_{n-1})$$ and where we discard the equivalence classes with fewer than $n$ sequences in them. (This then there is a graph theoretic interpretation of the adjective "primitive".)

This formula above quantity which is manifestly an integerintegral. (I gave a slightly incorrect description of this interpretation before; I'll stick to just citing for now.)

It's nonnegative

We have $$\sum_{d|n} \mu(n/d) L^d \geq L^n - \sum_{-\infty < d<n} L^d = L^n - \frac{L^{n-1}}{1-1/L}=L^n \frac{L-2}{L-1}.$$ and $$\left| \sum_{d|n} \mu(n/d) \lambda^d \right| \leq \sum_{- \infty < d \leq n} |\lambda|^d = \frac{|\lambda|^n}{1-1/|\lambda|} = |\lambda|^n \frac{|\lambda|}{|\lambda|-1}$$

So, for every $i$, $\sum_{d|n} \mu(n/d) L^d$ is a positive integer which is greater than the norm of $\sum_{d|n} \mu(n/d) \lambda_i^d$.

So the real part of $$\sum_{i=1}^r \left( \sum_{d|n} \mu(n/d) L^d + \sum_{d|n} \mu(n/d) \lambda_i^d \right)$$ is nonnegative. By Galois symmetry, the sum is real, so it is a nonnegative real, as desired.

Disclaimer: I haven't read the paper Lind cites.
show/hide this revision's text 1

I claim that any algebraic integer $\lambda$ is the eigenvalue of a nonnegative matrix with integer coefficients. This answer relies on Doug Lind's answer here. Let $\lambda_1$, $\lambda_2$, ..., $\lambda_r$ be the Galois conjugates of $\lambda$. Let $\ell = \max(|\lambda_i|)$. Choose an integer $L$ large enough that $L^n \cdot (L-2)/(L-1) > \ell^n \cdot \ell/(\ell-1)$ for all positive integers $n$. I claim there will be a nonnegative integer matrix with eigenvalues $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$ where there are $r$ copies of $L$.

Let $\mu_1$, $\mu_2$, ..., $\mu_{2r}$ be $(\lambda_1, \lambda_2, \ldots, \lambda_r, L,L,\ldots, L)$. According to Lind's answer, all we have to check is that, for all $n>0$, $$\frac{1}{n} \sum_k \sum_{d|n} \mu(n/d) \mu_k^d$$ is a nonnegative integer.

It's an integer: Let $g(x) = \prod_{i=1}^{2r} (x-\mu_i)$. Since $\lambda$ is an algebraic integer, $g$ is a monic polynomial with integer coefficients. So there is a $(2r) \times (2r)$ integer matrix $B$ with characteristic polynomial $g$ -- the companion matrix. The above sum is $$\sum_{(i_1 i_2 \cdots i_n)} B_{i_1 i_2} B_{i_2 i_3} \cdots B_{i_{n-1} i_n} B_{i_n i_1}$$ where the sum runs over "primitive necklaces $(i_1 i_2 \cdots i_n)$". What this is that we are summing over equivalence classes of sequences $(i_1 i_2 \cdots i_n)$, where the equivalence is $$(i_1, i_2, \ldots, i_n) \sim (i_2, \ldots, i_n, i_1) \sim \cdots \sim (i_n, i_1, \ldots, i_{n-1})$$ and where we discard the equivalence classes with fewer than $n$ sequences in them. (This is the adjective "primitive".)

This formula is manifestly an integer.

It's nonnegative

We have $$\sum_{d|n} \mu(n/d) L^d \geq L^n - \sum_{-\infty < d<n} L^d = L^n - \frac{L^{n-1}}{1-1/L}=L^n \frac{L-2}{L-1}.$$ and $$\left| \sum_{d|n} \mu(n/d) \lambda^d \right| \leq \sum_{- \infty < d \leq n} |\lambda|^d = \frac{|\lambda|^n}{1-1/|\lambda|} = |\lambda|^n \frac{|\lambda|}{|\lambda|-1}$$

So, for every $i$, $\sum_{d|n} \mu(n/d) L^d$ is a positive integer which is greater than the norm of $\sum_{d|n} \mu(n/d) \lambda_i^d$.

So the real part of $$\sum_{i=1}^r \left( \sum_{d|n} \mu(n/d) L^d + \sum_{d|n} \mu(n/d) \lambda_i^d \right)$$ is nonnegative. By Galois symmetry, the sum is real, so it is a nonnegative real, as desired.

Disclaimer: I haven't read the paper Lind cites.