Can you tell me an algebraic integer, with all archimedean absolute values less than 2, which is not an eigenvalue of $\pi\_1 + \pi\_2$ for any two permutation matrices $\pi\_1,\pi\_2$? 


Is it conceivable that *every* algebraic integer satisfying the archimedean condition can be so expressed? 



Tell me an algebraic integer that isn't an eigenvalue of the sum of two permutations
Yes: if $\alpha$ is an algebraic integer which obeys $|\alpha| < 2$ for all archimedean norms $|\ |$ then $\alpha$ is an eigenvalue of a sum of two permutations matrices.


I remark that this is not true when $|\alpha|=2$, for example, $(1+\sqrt{-15})/2$ is an algebraic integer with absolute value $2$ which is not twice a root of unity.


**Notation:** Let $A = \mathbb{Z}[\alpha]$ and let $V = A \otimes \mathbb{R}$. Since $\alpha$ is an algebraic integer, $A$ is a discrete full rank sublattice of $V$. Each archimedean norm $| \ |\_v$ extends to a continuous homogenous function $V \to \mathbb{R}\_{\geq 0}$ and we define $|\ |$ on $V$ by 
$$|x|^2 = \sum\_v |x|\_v^2$$
where the sum is over archimedean places, this is a positive definite norm on $V$. Let $c = \max\_v |\alpha|\_v$, so $c<2$. Note that $|\alpha x| \leq c |x|$ for any $x \in V$.
All references to "distance", "radius", etc on $V$ are with respect to the norm $|\ |$. Write $B\_R$ for the closed ball of radius $R$ around $0$.


**Step $1$:** There is a nonnegative integer matrix $C$ whose rows sum to $2$ with eigenvalue $\alpha$.


Choose $M$ large enough that a ball of radius $M$, centered anywhere in $V$, contains a point of $A$. In other words, choose $M$ larger than the covering radius of the lattice $A$.
Choose $R$ large enough that $cR/2+M < R$. 
I claim that, for any $z \in B\_R \cap A$, there are $z\_1$ and $z\_2 \in B\_R \cap A$ such that $\alpha z = z\_1 + z\_2$. Proof: Let $z\_1$ be the nearest point of $A$ to $\alpha z/2$, and let $z\_2 = \alpha z - z\_1$. Then $|z\_1 - \alpha z/2| = |z\_2 - \alpha z/2| \leq M$ so $|z\_1|$, $|z\_2| \leq |\alpha z/2| + M \leq cR/2 + M \leq R$. We have shown that $z\_1$ and $z\_2$ are in $B\_R \cap A$ as desired.


Let $z\_1$, $z\_2$, ..., $z\_N$ be the points of $B\_R \cap A$ and choose a way to write each $\alpha z\_i$ as $z\_{j\_1}+z\_{j\_2}$. Then the matrix $C$ which has $1$'s in positions $(i,j\_1)$ and $(i,j\_2)$ (and a $2$ if $j\_1=j\_2$) and $0$'s elsewhere has eigenvector $(z\_1 \ z\_2 \ \cdots \ z\_N)^T$ with eigenvalue $\alpha$ and all rows sum to $2$.


Before heading into step $2$, it is convenient to modify this argument slightly. Take $M$ large enough that any ball of radius $M$ contains at least $3$ points of $A$. In this way, we can ensure that, for any $z \in B\_R \cap A$ we can write $\alpha z = z\_1 + z\_2$ with $z\_1$, $z\_2 \in B\_R \cap A \setminus \{ 0 \}$. 
We can then take $z\_1$, $z\_2$, $\dots$, $z\_N$ be the points of $B\_R \cap A \setminus \{ 0 \}$. It will be convenient at the next step to make sure none of the entries of our eigenvector are $0$.


**Step $2$:** We may assume that there is no way to permute the rows and columns of $C$ to give it the block structure $\left( \begin{smallmatrix} \ast & 0 \\ \ast & \ast \end{smallmatrix} \right)$. In other words, $C$ is irreducible in the sense of the [Perron-Frobenius theorem](https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Non-negative_matrices).


Suppose we could permute the rows and columns, so $C = \left( \begin{smallmatrix} C\_{11} & 0 \\ C\_{21} & C\_{22} \end{smallmatrix} \right)$ and $C \vec{z} = \alpha \vec{z}$ where we can write the eigenvector $\vec{z}$ as $\left( \begin{smallmatrix} \vec{z}\_1 \\ \vec{z}\_2 \end{smallmatrix} \right)$. Then $C\_{11}\vec{z}\_1 = \alpha \vec{z}\_1$ We arranged above that none of the components of $\vec{z}$ is $0$, so $\vec{z}\_1 \neq 0$. We see $C\_{11}$ is a smaller matrix with eigenvalue $\alpha$ and row sums $2$, and we may consider it instead.


**Step $3$:** Making the column sums $2$. So now $C$ has row sums $2$, meaning that $(1 \ 1 \ \cdots \ 1)^T$ is a right eigenvector with eigenvalue $2$. Let $(d\_1 \ d\_2\ \cdots \ d\_n)$ be the corresponding left eigenvector. By Perron-Frobenius, the $d\_i$ are all positive. Since the corresponding eigenvalue is rational, the $d\_i$ can be taken to be integers. 


Build a new matrix $D$ of size $\sum d\_i \times \sum d\_i$, broken into $d\_i \times d\_j$ blocks. We will arrange that it has eigenvalue $\alpha$ with corresponding eigenvector $\vec{w}:=(z\_1 \ z\_1 \cdots z\_1 z\_2 z\_2 \cdots z\_2 \cdots )^T$ where $z\_i$ is repeated $d\_i$ times. 
Within the $d\_i \times d\_j$ block, we will place $C\_{ij}$ ones in each row. This is enough to force $D \vec{w} = \alpha \vec{w}$ and to force the row sums to be $2$.
Moreover, within the $d\_j$ columns in the $j$-th block, there will be a total of $\sum\_i C\_{ij} d\_i$ ones. We have $\sum\_i C\_{ij} d\_i = 2 d\_j$ by the choice of $d$ as a left eigenvector. 
So we can place $2$ of them in each column and we win.


By the Birkhoff-von Neumann theorem, a nonnegative integer matrix with row and column sums $2$ is a sum of two permutation matrices. **QED**




---


Here is an illustration of the trick at the end. Let
$$C = \begin{bmatrix} 1&1&0\\1&0&1\\2&0&0 \end{bmatrix}.$$
 The left eigenvector of $2$ is $(4,2,1)$. 


Let 
$$D = 
\left[ 
\begin{array}{|cccc|cc|c|}
\hline
1& 0 & 0&0 & 1& 0 &0\\
1& 0 & 0&0 & 1& 0 &0\\
0& 1 & 0&0 & 0& 1 &0\\
0& 1 & 0&0 & 0& 1 &0\\
\hline
0& 0 & 1&0 &0& 0 &1\\
0& 0 & 1&0 &0& 0 &1\\
\hline
0& 0 & 0&2 &0& 0 &0\\
\hline
\end{array} \right]$$
Then $D$ has the same eigenvalues as $C$, plus a bunch of $0$ eigenvalues.


