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?
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.
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.
