# Finite subgroup of $Gl(n,\mathbb Z)$ and congruences

Suppose we have an invertible matrix q in a finite subgroup $Q$ of $Gl(n,\mathbb Z)$, the group of all invertible integer matrices. Now I want to find all $x\; mod\; \mathbb Z^n$ for which

$(q+q^2+q^3+...+q^m).x = 0\quad mod\; \mathbb Z^n$

where $m$ is the order of $q$ in the finite subgroup $Q$ of $Gl(n,\mathbb Z)$ so that $q^m=1$. I tried using the Smith normal form so that

$(q+q^2+q^3+...+q^m) = U.D.V$

where $U,V$ in $Gl(n,\mathbb Z)$ and $D$ the Smith normal form, so we have to solve

$D.V.x=0\quad mod\; \mathbb Z^n$

Since $D.V$ is diagonal, $x$ must have rational components unless the diagonal element is zero. Now my question is, what is the maximal denominator of the components in $x$ ? So what is the maximal absolute value in $D.V$ ?I think this must be $m$, but I can't figure out why.

Edit: Let me clarify why I expect x to be rational with an upper bound on the denominator. Suppose G is a subgroup of the Euclidean Group with isometries (t,q) as elements (t: translational part, q: linear part). The subgroup T which contains all isometries in G with trivial linear part is a normal subgroup of G. Suppose now that T can be identified with a $\mathbb Z$-lattice in $\mathbb R^n$, then G/T is isomorph with a finite subgroup Q of $GL(n,\mathbb Z)$. Crystallographers call G a space group and Q a point group.

There are only finite many conjugacy classes of finite subgroups in $GL(n,\mathbb Z)$, so there are only finite many point groups up to conjugacy in $GL(n,\mathbb Z)$. Now I want to understand why from this finite number of point groups, a finite number of (non-equivalent) space groups can be deduced. If we write G as the union of cosets of T

$G=\bigcup_{i=1}^{|Q|}(t_{qi},q_{i})T$

we see that (composition of two isometries and q belongs to exactly one coset)

$t_{q_1.q_2}=t_{q_1}+q_1.t_{q_2} \quad mod\ \mathbb Z^n$

So we know that $t_{q}$ is a real vector $0\leq t_{q}<1$. Using the previous property we also find that (m order of q)

$(t_{q},q)^{m}=(q^{1}\cdot t_{q}+\cdots+q^{m}\cdot t_{q},q^m)\in (0,id)T$

$\Leftrightarrow (q^{1}+\cdots+q^{m})\cdot t_{q}=0\quad mod\ \mathbb{Z}^{n}$

If an appropriate origin is chosen in Euclidean space, $t_{q}$ should be rational with maximal denominator $m$. Maybe investigating $(t_{q},q)^{m}$ is not the best way to find bounds on $t_{q}$?

-
I don't get it. Isn't $q+q^2+q^3+...+q^m=1+q+q^2+...+q^{m-1}$ the inverse of $1-q$ (where $1$ means the identity matrix), and thus invertible over $\mathbb Q/\mathbb Z$ as well? –  darij grinberg Sep 2 '11 at 16:05
No, it isn't the inverse, since $(1+ q + \dots + q^{m-1})(1-q)=0$. But this shows that the columns of $1-q$ are in the "kernel" of $1+q+\dots +q^{m-1}$. –  Ralph Sep 2 '11 at 16:41
Isn't the point that your matrix has the form $mE$ for some idempotent matrix $E$, and is also integral? –  Geoff Robinson Sep 2 '11 at 18:22
Ah, right. Another of my $0$-$1$ mixups. –  darij grinberg Sep 2 '11 at 18:33
@Ralph: you're right, fixed it. –  Wox Sep 5 '11 at 8:12

Edit: I couldn't resist my predilection for generalizations: Using darij grinberg's simplification, the proof below shows:

Let $k$ be a field, $q \in GL_n(k)$ a matrix of finite exponent $m$ with char$(k) \nmid m$ and $M \subseteq k^n$. Futhermore, let $E$ be the eigenspace of $q$ corresponding to the eigenvalue $1$ and let $U \le k^n$ be the space spanned by the columns of $1-q$. Then the following is true for $A := 1+q+\dots + q^{m-1}$:

• $\lbrace x \in k^n \mid Ax \in M \rbrace = U + \frac{1}{m}(E \cap M)$
• $U$ and $(1/m)(E \cap M)$ intersect in $0$ iff $0 \in M$, otherwise the intersection is empty
• $A$ is diagonizable with diagonal $(m,...,m,0,...,0)$ where the number of m's equals $\dim E$

(Older formulation)

Let $E \le \mathbb{C}^n$ be the eigenspace of $1$ of the matrix $q$ and let $U \le \mathbb{C}^n$ be the space spanned by the columns of $1-q$.

Set $A := 1+q+\dots + q^{m-1}$ and $X:= \lbrace x \in \mathbb{C}^n \mid A\cdot x \in \mathbb{Z}^n \rbrace$ and $L := E \cap \mathbb{Z}^n$.

Then the following holds:

$X = U \oplus \frac{1}{m}L$.

Proof: Assume $\dim E = d$. Then $\dim U = \text{rank}(1-q) = n-d$.

Since each $x \in E$ satisfies $Ax = mx$, $E$ contains eigenvectors from $A$ of the eigenvalue $m$. From $A \cdot (1-q) = 0$ it follows that $U$ consists of eigenvectors of $A$ of the eigenvalue $0$. Hence $E \cap U = 0$ and for dimensional reasons $$\mathbb{C}^n = U \oplus E.$$ Since $q$ has integral entries, it's possible to chosse a basis of $E$ in $\mathbb{Q}^n$ and by multiplying with a suitable integer it's also possible to choose a basis in $\mathbb{Z}^n$. Therefore $L = E \cap \mathbb{Z}^n$ is a lattice of rank $d$. Let $\lbrace e_1, \dots, e_d \rbrace$ be a basis of $L$. Let $x \in X$ and write $$x = u + \sum_i \alpha_i e_i \text{ with } \alpha_i \in \mathbb{C}.$$ Then $Ax = \sum_i m\alpha_i e_i \in \mathbb{Z}^n$ and $q(Ax) = Ax$. It follows $Ax \in E \cap \mathbb{Z}^n = L = \oplus_i \mathbb{Z}e_i$ and therefore $m\alpha_i \in \mathbb{Z}$. This shows $X \subseteq U \oplus (1/m)L$. The converse inclusion is obvious. qed.

Edit: Also note that the image of $A$ is given by $$Y := \lbrace Ax \mid x \in X \rbrace = L.$$

-
Am I off track here or is it possible that your proof can be simplified as follows: Instead of writing $x = u+\sum\limits_i \alpha_i e_i$ with $\alpha_i\in \mathbb C$, let me write $x=u+e$ for some $u\in U$ and $e\in E$. Then, $Ax=me\in\mathbb Z^n$ and $q\left(Ax\right)=Ax$. This yields $Ax\in E\cap \mathbb Z^n = L$, so that $me=Ax\in L$ and thus $e\in\frac{1}{m}L$, so that $x = u + e \in U \oplus \frac{1}{m}L$. Nowhere we are using a basis of $E$ or any other property of lattices. Too simple to be true? –  darij grinberg Sep 3 '11 at 9:49
Looks good. So the problem can be solved completely by means of linear algebra. In fact, it would be a nice exercise in a LA course. –  Ralph Sep 3 '11 at 18:55
In your generalization, you should require $M$ to have some structure. –  darij grinberg Sep 4 '11 at 11:06
Well, you are right, the direct sum isn't appropriate. But the result holds for every subset $M$, if one defines (see the change in the last edit) $A+B := \lbrace a+b \mid a \in A, b \in B \rbrace$ for subsets $A, B \subseteq k^n$ (of course, $A+B = \emptyset$, if $A$ or $B$ empty). –  Ralph Sep 4 '11 at 13:10
I forgot to mention that $x\in \mathbb R^n$ –  Wox Sep 5 '11 at 15:45

That's an answer/comment to the secondary question.

I don't know, if the result can be derived from the finiteness of the matrix $q$ alone (it seems to me that you don't explore the fact that a space group consists of isometries). There is another point that makes me wonder: At the begining you are considering an isometry $(x,q)$ with $q \in GL(n,\mathbb{Z})$. But then $q \in GL(n,\mathbb{Z}) \cap O_n =P$, the group of permutation matrices with signed entries. Aren't there space groups, those rotational parts form larger groups than $P$ ?

That said, I was looking in the internet and found a paper (link), having a proof (section 5) that is somewhat related to your approach in the Edit-part of the original question.

The idea is roughly: Let $G$ be a space group with translation subgroup $T$ and let $L$ be the lattice correspnding to $T$. Choose a system of representatives $\lbrace q_1, ...,q_m \rbrace$ for $G/T$ and a basis $\lbrace b_1, ..., b_n \rbrace$ of $L$. Let $a_i$ be the translational part of $q_i$. By writing $a_i$ as linear combination of the $b_j$ it follows that $q_i$ can be choosen such that $|a_i| \le |b_1| + ... + |b_n| =: \alpha$ (Euklid-Norm). If $x_0 \in \mathbb{R}^n$ let $[x_0]$ denote translation by $x_0$. Then the following product can be expressed as

$$q_i \circ q_j = [\sum_k l_{ijk}b_k] \circ q_{\eta(i,j)},\hspace{10pt} l_{ijk} \in \mathbb{Z},\quad \eta(i,j) \in \lbrace 1,...,m \rbrace \hspace{50pt} (\ast)$$

It's easy to see, that the group law of $G$ is uniquely determined by $(\ast)$.

If $G'$ is another space group with $(G':T') = (G:T)$, repeat the same procedure and define a mapping $G \to G'$ by $q_i \to q'_i$, $b_j \to b_j'$. If $l_{ijk}' = l_{ijk}$ and $\eta(i,j)' = \eta(i,j)$ for all $i,j,k$, this is an isomorphism. Therefore there are only finitely many space groups $G$ for fixed $(G:T)$ (up to isomorphism), if it can be shown that there are only finitely many possible values for the $l_{ijk}$.

If the rotational part of $q_i$ is the matrix $A_i \in O_n$, $(\ast)$ shows $$| \sum_k l_{ijk}b_k | = |a_i + A_ia_j-A_iA_j(A_{\eta(i,j)})^{-1} a_{\eta(i,j)}| \le |a_i| + |a_j| + |a_{\eta(i,j)}| \le 3\alpha$$

Suppose $\lbrace b_1, ..., b_n\rbrace$ is an orthonormal base of $\mathbb{R}^n$. Then $\alpha = n$ and each $|l_{ijk}| \le 3n$ is bounded. Thus the result is shown in this case. In general, a similar estimate holds, but it's harder to establish (that's step 2 on page 144 that relies on lemmas 4.1, 4.2).

Remark: Using the theory of group extensions, the result follows easily from the finiteness of $H^2(Q; \mathbb{Z}^n)$ for finite groups $Q$.

-
Why is $q \in GL(n,\mathbb{Z}) \cap O_n$? The linear parts of isometries are orthogonal transformations, but don't necessarily correspond to orthogonal matrices (only for an orthonormal basis). So either $q\in O(n,\mathbb{R})$ or $q \in GL(n,\mathbb{Z})$. So loosing orthogonality is the price we pay for wanting integer matrices. Or am I missing something? –  Wox Sep 12 '11 at 8:32
The fact that $(q+q^2+q^3+...+q^m).x = 0\quad mod\; \mathbb Z^n$ results from considering isometries and the properties of space groups, so I do explore the fact that a space group consists of isometries. –  Wox Sep 12 '11 at 8:35
Anyway, you answered my original question and got me on the right track for the secondary problem. Thanks Ralph! –  Wox Sep 14 '11 at 7:41

Edit: This is a secondary question on how Ralph's solution can be simplified by choosing an appropriate origin in Euclidean space.

Ralph's solution to my original question, in the context of space groups, states that an isometry $(x,q)$ in a space group $G$ with linear part $q\in Q< GL(Z^n)$, must have a translational part x for which

$X_q=\lbrace x\in\mathbb R^n: (q^{1}+\cdots+q^{m})\cdot x\in \mathbb Z^n\rbrace =Col(q-1)+\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)$

Note first that from the composition of isometries we find that

$(t_1,q_1)(t_2,q_2)=(t_1+q_1\cdot t_2,q_1\cdot q_2)$

$\Leftrightarrow X_{q_{1}\cdot q_{2}}=X_{q_{1}}+(q_{1}-1)\cdot X_{q_{2}}$

This means that we must only consider the $X_q$ for the generators of the finite group $Q< GL(Z^n)$ (i.e. the point group).

After a shift of origin in Euclidean space, i.e. an affine transformation $(v,1)$ with $v\in \mathbb R^n$, we can write that

$X_q'=Col(q-1)+\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)+(q-1)\cdot v$

Since $(q-1)\cdot v\in Col(q-1)$, we can find for every $u\in Col(q-1)$ a vector $v\in \mathbb R^n$ for which $(q-1)\cdot v=-u$. Thus for a proper choice of origin we can write for a generator q

$X_q=\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)$

so that $t_q = X_q\ mod\ \mathbb Z^n$ is a rational number with maximal denominator $|Q|$ (which is the maximal possible m). The question is now, can we find one $v\in \mathbb R^n$ so that this simplification can be done for all $X_q$? For this, the column spaces $Col(q-1)$ for generators q of Q should be linear independent. If we call $S$ the generating set of Q, then this can be expressed as

$\forall q,p\in S: Col(q-1)\cap Col(p-1)=\lbrace 0 \rbrace$

Is this true?

-
One can't always find generators q with $Col(q-1)$ intersection $\lbrace 0 \rbrace$ for a point group, so this is not the way to go. –  Wox Sep 14 '11 at 7:39