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?
 A: 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.  
A: 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$.  
