- #1
lpetrich
- 988
- 180
Over in the thread The eight-queens chess puzzle and variations of it | Physics Forums I discovered that with a toroidal board, one with periodic boundary conditions, the amount of symmetries becomes surprisingly large (A group-based search for solutions of the n-queens problem - ScienceDirect).
I will use a r-dimensional board with n squares along each dimension. A standard chessboard has r = 2 and n = 8. The toroidal-board symmetry group is an affine-symmetry group, a group whose elements are rotation/reflection and translation (R,T), elements that act on a vector x to make vector x' with ##x' = R\cdot x + T##, where x, x', and T are r-vectors, R is an r*r matrix, and all components are in Zn. Affine symmetry thus generalizes the Euclidean group to components in arbitrary rings, like Zn under addition and multiplication modulo n. The rings do need additive and multiplicative identities, 0 and 1, for constructing the identity element R = identity matrix and T = zero vector.
For components being in a commutative ring, one can find the inverse of each R by using Cramer's rule. Though impractical for all but the smallest matrices, Cramer's rule is good for theoretical results. It is evident from that algorithm that invertibility requires that each R have a determinant that is a "unit" in that ring, an element with a multiplicative inverse. For ##Z_n##, this is all elements relatively prime to n, or ##Z^\times_n##. It is easy to show that the units of a ring form a group under multiplication.
So I must find the structure of the group of (R,T) for all invertible R and all T over Zn and number of dimensions r.The first step is to note that with I the identity matrix, the affine group's subgroup of all (I,T) is a normal subgroup. Its structure is ##(Z_n)^r##, (the component ring's additive group)r. Its quotient group is the group of R's under matrix multiplication, the homogeneous affine group. This group is ##GL(r,Z_n)##, the general linear group over ring ##Z_n##.One can proceed further by selecting out all the elements with determinant 1, giving the special linear group: ##SL(r,Z_n)##, The center of the general linear group is all elements ##mI## where m is in ##Z^\times_n##, all the component ring's units times the identity matrix. The quotient group of ##GL(r,Z_n)## and its center is the projective general linear group ##PGL(r,Z_n)##. The special linear group has a similar center, but with the further condition ##m^r = 1##. Its quotient group is the projective special linear group ##PSL(r,Z_n)##.
For r = 1, the group ##GL(1,Z_n) = Z^\times_n##, the units group, and the groups ##SL(1,Z_n)##, ##PGL(1,Z_n)##, and ##PSL(1,Z_n)## are all the identity group.
For n = 2, ##Z^\times_2## is the identity group, and ##GL(r,Z_2) = SL(r,Z_2) = PGL(r,Z_2) = PSL(r,Z_2)##.One can simplify these groups in another direction, by using a theorem of matrices over rings and their ideals (Combinatorics of Vector Spaces over Finite Fields). A two-sided ideal I of a ring R satisfies ##R\cdot I = I \cdot R = I##, with a left ideal and a right ideal being for only one side. An ideal of the integer ring ##Z## is ##n \cdot Z## for integer n.
The theorem: consider matrix ring ##M(r,C)## of r*r matrices over component ring C. Consider ideals of C, Jk, that are "disjoint". Their intersection ##J = \cap_k J_k##. Then ##M(r,C/J) = \prod_k M(r,C/J_k)##, where each C/J is a quotient ring. This result readily gives analogous results for the GL, SL, PGL, and PSL groups.
Applying to Zn, that ring is is the quotient ring Z/(nZ), and I've sometimes seen that notation used instead. An appropriate set of disjoint ideals is from prime factors: ##n = \prod_p p^m##, powers m of prime factors p. Thus, ##Z_n = \prod_p Z_{p^m}##. This is also true of the multiplicative group over its units, ##Z^\times_n = \prod_p Z^\times_{p^m}##, of its matrix rings ##M(r,Z_n) = \prod_p M(r,Z_{p^m})##, and of the GL, SL, PGL, and PSL groups.
Multiplicative group of integers modulo n - Wikipedia goes further with ##Z^\times_n = \prod_p Z^\times_{p^m}##, stating the structure of each group ##Z^\times_{p^m}##:
Continuing with ##M(r,Z_{p^m})## and its groups, I've only seen stuff on the groups for a related matrix ring, ##M(r,GF(p^m))##, with its component ring being a Galois field. But ##Z_{p^m}## is only a field for m = 1: GF(p).
However, that combinatorics reference states the order of ##GL(r,Z_{p^m})##. It is ##p^{(m-1)r^2} \prod_{k=0}^{r-1} (p^r - p^k)## or ##p^{(m-1)r^2} |GL(r,Z_p)|##. More generally,
$$ |GL(r,Z_n)| = n^{r^2} \prod_p \prod_{k=1}^r \left( 1 - \frac{1}{p^k} \right) $$
over all prime factors p of n. For r = 1, one gets the formula for the Euler totient function. But for Galois fields,
$$ |GL(r,GF(q))| = q^{r^2} \prod_{k=1}^r \left( 1 - \frac{1}{q^k} \right) $$
My question: What has been done on the structure of the group ##PSL(r,Z_{p^m})## for r > 1 and m > 1? For r = 1, it is the identity group. For m = 1, it is simple for all r and m except for r = 2 and m = 2 and 3. That is as far as I can go without doing brute-force calculations.
I will use a r-dimensional board with n squares along each dimension. A standard chessboard has r = 2 and n = 8. The toroidal-board symmetry group is an affine-symmetry group, a group whose elements are rotation/reflection and translation (R,T), elements that act on a vector x to make vector x' with ##x' = R\cdot x + T##, where x, x', and T are r-vectors, R is an r*r matrix, and all components are in Zn. Affine symmetry thus generalizes the Euclidean group to components in arbitrary rings, like Zn under addition and multiplication modulo n. The rings do need additive and multiplicative identities, 0 and 1, for constructing the identity element R = identity matrix and T = zero vector.
For components being in a commutative ring, one can find the inverse of each R by using Cramer's rule. Though impractical for all but the smallest matrices, Cramer's rule is good for theoretical results. It is evident from that algorithm that invertibility requires that each R have a determinant that is a "unit" in that ring, an element with a multiplicative inverse. For ##Z_n##, this is all elements relatively prime to n, or ##Z^\times_n##. It is easy to show that the units of a ring form a group under multiplication.
So I must find the structure of the group of (R,T) for all invertible R and all T over Zn and number of dimensions r.The first step is to note that with I the identity matrix, the affine group's subgroup of all (I,T) is a normal subgroup. Its structure is ##(Z_n)^r##, (the component ring's additive group)r. Its quotient group is the group of R's under matrix multiplication, the homogeneous affine group. This group is ##GL(r,Z_n)##, the general linear group over ring ##Z_n##.One can proceed further by selecting out all the elements with determinant 1, giving the special linear group: ##SL(r,Z_n)##, The center of the general linear group is all elements ##mI## where m is in ##Z^\times_n##, all the component ring's units times the identity matrix. The quotient group of ##GL(r,Z_n)## and its center is the projective general linear group ##PGL(r,Z_n)##. The special linear group has a similar center, but with the further condition ##m^r = 1##. Its quotient group is the projective special linear group ##PSL(r,Z_n)##.
For r = 1, the group ##GL(1,Z_n) = Z^\times_n##, the units group, and the groups ##SL(1,Z_n)##, ##PGL(1,Z_n)##, and ##PSL(1,Z_n)## are all the identity group.
For n = 2, ##Z^\times_2## is the identity group, and ##GL(r,Z_2) = SL(r,Z_2) = PGL(r,Z_2) = PSL(r,Z_2)##.One can simplify these groups in another direction, by using a theorem of matrices over rings and their ideals (Combinatorics of Vector Spaces over Finite Fields). A two-sided ideal I of a ring R satisfies ##R\cdot I = I \cdot R = I##, with a left ideal and a right ideal being for only one side. An ideal of the integer ring ##Z## is ##n \cdot Z## for integer n.
The theorem: consider matrix ring ##M(r,C)## of r*r matrices over component ring C. Consider ideals of C, Jk, that are "disjoint". Their intersection ##J = \cap_k J_k##. Then ##M(r,C/J) = \prod_k M(r,C/J_k)##, where each C/J is a quotient ring. This result readily gives analogous results for the GL, SL, PGL, and PSL groups.
Applying to Zn, that ring is is the quotient ring Z/(nZ), and I've sometimes seen that notation used instead. An appropriate set of disjoint ideals is from prime factors: ##n = \prod_p p^m##, powers m of prime factors p. Thus, ##Z_n = \prod_p Z_{p^m}##. This is also true of the multiplicative group over its units, ##Z^\times_n = \prod_p Z^\times_{p^m}##, of its matrix rings ##M(r,Z_n) = \prod_p M(r,Z_{p^m})##, and of the GL, SL, PGL, and PSL groups.
Multiplicative group of integers modulo n - Wikipedia goes further with ##Z^\times_n = \prod_p Z^\times_{p^m}##, stating the structure of each group ##Z^\times_{p^m}##:
- For p = 2, ##Z^\times_2## is the identity group and ##Z^\times_{2^m} = Z_{2^{m-2}} \times Z_2##.
- For odd p, every other value: ##Z^\times_{p^m} = Z_{p^{m-1}} \times Z_{p-1} = Z_{(p-1)p^{m-1}}##.
Continuing with ##M(r,Z_{p^m})## and its groups, I've only seen stuff on the groups for a related matrix ring, ##M(r,GF(p^m))##, with its component ring being a Galois field. But ##Z_{p^m}## is only a field for m = 1: GF(p).
However, that combinatorics reference states the order of ##GL(r,Z_{p^m})##. It is ##p^{(m-1)r^2} \prod_{k=0}^{r-1} (p^r - p^k)## or ##p^{(m-1)r^2} |GL(r,Z_p)|##. More generally,
$$ |GL(r,Z_n)| = n^{r^2} \prod_p \prod_{k=1}^r \left( 1 - \frac{1}{p^k} \right) $$
over all prime factors p of n. For r = 1, one gets the formula for the Euler totient function. But for Galois fields,
$$ |GL(r,GF(q))| = q^{r^2} \prod_{k=1}^r \left( 1 - \frac{1}{q^k} \right) $$
My question: What has been done on the structure of the group ##PSL(r,Z_{p^m})## for r > 1 and m > 1? For r = 1, it is the identity group. For m = 1, it is simple for all r and m except for r = 2 and m = 2 and 3. That is as far as I can go without doing brute-force calculations.