# Which unimodular matrices are integer combinations of permutations?

Consider the set of all integer linear combinations of permutation matrices of some fixed dimension. Is there a description of the set of unimodular matrices in this lattice?

• Are you asking about the invertible elements in the integer group ring of the permutation group? – Jason Starr Oct 3 '16 at 11:12
• @JasonStarr: I think this is a different question ( only the same when the permutation representation is the regular representation of the permutation group in question). – Geoff Robinson Oct 3 '16 at 12:21
• @GeoffRobinson. You are correct. The group ring has rank $n!$, yet the ring above has rank less than $n^2$. So these are not the same ring. – Jason Starr Oct 3 '16 at 12:28
• Well, it's almost the same as finding the units in $\mathbf Z [\zeta]$, where $\zeta$ is a primitive $n$th root of unity, $n$ being the matrix size. – David Handelman Oct 3 '16 at 13:38
• To be more specific, I start with nxn 0-1 matrices with a single 1 in each row and column. @DavidHandleman, I can see how the units you point out will yield matrices as I wanted. But that is restricting to linear combinations whose support is a cyclic subgroup. – Arnaldo Mandel Oct 3 '16 at 14:00

If you take $\mathbb{Q}$ linear combination of permutation matrices, this is a ring which is the product $M_1(\mathbb{Q})\times M_{n-1}(\mathbb{Q})$ of matrix rings, since the standard representation of the permutation group is a direct sum of the trivial plus an absolutely irreducible representation of dimension $n-1$. Hence the set of integral linear combinations is an order in this product algebra. Therefore, the unit group of this order will contain a subgroup of finite index in the group $trivial\times SL_{n-1}(\mathbb{Z})$, and in fact, will be commensurable to it.
The $\Bbb{Z}$-span $T_n$ of the order $n$ permutation matrices consists of integer $n\times n$ matrices with the row and column sums equal to $k$ for some integer $k$. Thus it can be characterized as the subset (in fact, subring) of $M_n(\Bbb{Z})$ consisting of matrices $A$ such that $Av=kv$ and $A^t v=kv$ for some $k\in\Bbb{Z}$, where $v=(1,\dots,1)^t$ is the column with all entries $1$. Let $L\subset\Bbb{Z}^n$ be the sublattice of integer vectors with sum of the entries $0$, $L=\{u: u^t v=0\}$. Note that $\Bbb{Z}^n=L\oplus \Bbb{Z}v$ and $A\in T_n$ preserves this decomposition.
Clearly, $A\in T_n$ is invertible only if $k=\pm 1$ and the restriction of $A$ to $L$ is invertible. Conversely, any automorphism of $L$ can be extended in exactly two ways to an invertible matrix acting by $\pm 1$ on $v$. Since $L$ has rank $n-1$, it follows that the group in question is the direct product ${\rm GL}_{n-1}(\Bbb{Z})\times\{\pm 1\}$, with the first factor represented by the automorphisms of $L$ and the second factor represented by the scalar matrices $\pm I_n$.
• Yes, this characterization of $T_n$ is an integer version of Birkhoff's theorem (which deals with $\Bbb{R}_{+}$-combinations). – Victor Protsak Oct 4 '16 at 7:33