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?

  • $\begingroup$ Are you asking about the invertible elements in the integer group ring of the permutation group? $\endgroup$ Oct 3, 2016 at 11:12
  • 1
    $\begingroup$ @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). $\endgroup$ Oct 3, 2016 at 12:21
  • $\begingroup$ @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. $\endgroup$ Oct 3, 2016 at 12:28
  • $\begingroup$ 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. $\endgroup$ Oct 3, 2016 at 13:38
  • $\begingroup$ 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. $\endgroup$ Oct 3, 2016 at 14:00

2 Answers 2


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

  • $\begingroup$ There is a theorem of Birkhoff stating that all doubly stochastic matrices are convex linear combinations of permutation matrices. Could that be related to this question? $\endgroup$ Oct 4, 2016 at 7:13
  • $\begingroup$ Yes, this characterization of $T_n$ is an integer version of Birkhoff's theorem (which deals with $\Bbb{R}_{+}$-combinations). $\endgroup$ Oct 4, 2016 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.