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$
$\endgroup$
6
-
$\begingroup$ Are you asking about the invertible elements in the integer group ring of the permutation group? $\endgroup$– Jason StarrOct 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$– Geoff RobinsonOct 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$– Jason StarrOct 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$– David HandelmanOct 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$– Arnaldo MandelOct 3, 2016 at 14:00
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
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.
answered Oct 4, 2016 at 4:39
$\begingroup$
$\endgroup$
2
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$.
answered Oct 4, 2016 at 7:02
-
$\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