# Tell me an algebraic integer that isn't an eigenvalue of the sum of two permutations

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?

• Is this the same as asking whether such an algebraic integer is the eigenvalue of a matrix with non-negative integer entries and row and column sums equal to $2?$ – Igor Rivin Mar 6 '17 at 16:00
• @IgorRivin : Yes, this is the Birkhoff-von Neumann theorem. – Timothy Chow Mar 6 '17 at 16:43
• Partial progress: Every such $\alpha$ is an eigenvalue of an nonnegative integer matrix whose columsn sum to $2$. Proof sketch: Let $A = \mathbb{Z}[\alpha]$ and let $V = A \otimes \mathbb{R}$. Let $|\ | : V \to \mathbb{R}$ be the maximum of the arch. abs. values and let $c<2$ be $|\alpha|$. Let $B \subset V$ be the ball of radius $R$ for the norm $|\ |$. Then, for any vector $v \in V$ with $|v| < cR$, the intersection $B \cap (v - B)$ has positive volume. – David E Speyer Mar 6 '17 at 19:31
• I think (not carefully checked) that we can make a compactness argument to show that, if we choose $R$ large enough, for any $v \in A$ with $|v| < cR$, the intersection $B \cap (v - B) \cap A$ is nonempty. So any such $v$ is a sum of two vectors in $A \cap B$. In particular, for any $u \in B \cap A$, we can write $\alpha u = u_1 + u_2$ for $u_1$, $u_2 \in A \cap B$. Choose a way of writing $\alpha u$ for each $u \in B \cap A$ to get a $\#(B \cap A) \times \#(B \cap A)$ matrix with the desired property. – David E Speyer Mar 6 '17 at 19:34
• @ACL : Yes, that's one version of the BvN theorem, but another version states exactly what Igor Rivin was asking about. A few seconds of Googling turned up these notes for example: galton.uchicago.edu/~lalley/Courses/388/Matching.pdf – Timothy Chow Mar 8 '17 at 16:59

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.

• This is awesome, David! – JSE Mar 9 '17 at 16:30