Order formulas for linear groups

From Groupprops
Jump to: navigation, search

This article gives a list of formulas for the orders of the general linear group of finite degree n \ge 1 and some other related groups, both for a finite field of size q and for related rings.

Contents

For a finite field of size q

Formulas

In the formulas below, the field size is q and the degree (order of matrices involved, dimension of vector space being acted upon) is n. The characteristic of the field is a prime number p. q is a prime power with underlying prime p. We let r = \log_pq, so q = p^r and r is a nonnegative integer.

In the table below, \Phi_d(q) stands for the d^{th} cyclotomic polynomial evaluated at q.

Group Symbolic notation Order formula Order formula (powers of q taken out) Order formula (maximally factorized) Degree as polynomial in q (same as algebraic dimension) Multiplicity of factor q Multiplicity of factor q - 1 Quick explanation for order
general linear group GL(n,q) or GL(n,\mathbb{F}_q) \prod_{i=0}^{n-1} (q^n - q^i) q^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) q^{\binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 \binom{n}{2} = \frac{n(n- 1)}{2} n See full explanation below.
special linear group SL(n,q) or SL(n,\mathbb{F}_q) \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} q^{\binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) q^{\binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 - 1 \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 |GL(n,q)|/|\mathbb{F}_q^\ast|; see full explanation below.
projective general linear group PGL(n,q) or PGL(n,\mathbb{F}_q) \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} q^{\binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) q^{\binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 - 1 \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 |GL(n,q)|/|\mathbb{F}_q^\ast|; see full explanation below.
projective special linear group PSL(n,q) or PSL(n,\mathbb{F}_q) \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{(q - 1)\operatorname{gcd}(n,q-1)} q^{\binom{n}{2}} \frac{\prod_{i=0}^{n-2} (q^{n-i} - 1)}{\operatorname{gcd}(n,q-1)} q^{\binom{n}{2}} \frac{(q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor}}{\operatorname{gcd}(n,q-1)} n^2 - 1 (ignoring gcd term) \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 (ignoring gcd term) |SL(n,q)| divided by the number of n^{th} roots in \mathbb{F}_q^\ast; see full explanation below.
general semilinear group \Gamma L(n,q) or \Gamma L(n,\mathbb{F}_q) r \prod_{i=0}^{n-1} (q^n - q^i) rq^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) rq^{\binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 \binom{n}{2} = \frac{n(n- 1)}{2} n r times the order of GL(n,q); see full explanation below.
outer linear group OL(n,q) or OL(n,\mathbb{F}_q) 2 \prod_{i=0}^{n-1} (q^n - q^i) 2q^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) 2q^{\binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 \binom{n}{2} = \frac{n(n- 1)}{2} n Twice the order of GL(n,q); see full explanation below.
outer semilinear group O\Gamma L(n,q) or O \Gamma L(n,\mathbb{F}_q) 2r \prod_{i=0}^{n-1} (q^n - q^i) 2rq^{\binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) 2rq^{\binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 \binom{n}{2} = \frac{n(n- 1)}{2} n 2r times the order of GL(n,q); see full explanation below.
special semilinear group  ? r\frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} rq^{\binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) rq^{\binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 - 1 \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 r times the order of SL(n,q); explanation similar to that for general semilinear group.
projective semilinear group P\Gamma L(n,q) or P \Gamma L(n,\mathbb{F}_q) r\frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} rq^{\binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) rq^{\binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2 - 1 \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 r times the order of PGL(n,q); explanation similar to that for general semilinear group.
projective special semilinear group  ? r\frac{\prod_{i=0}^{n-1} (q^n - q^i)}{(q - 1)\operatorname{gcd}(n,q-1)} rq^{\binom{n}{2}} \frac{\prod_{i=0}^{n-2} (q^{n-i} - 1)}{\operatorname{gcd}(n,q-1)} rq^{\binom{n}{2}} \frac{(q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor}}{\operatorname{gcd}(n,q-1)} n^2 - 1 (ignoring gcd term) \binom{n}{2} = \frac{n(n- 1)}{2} n - 1 (ignoring gcd term) r times the order of PGL(n,q); explanation similar to that for general semilinear group.
general affine group GA(n,q) or GA(n,\mathbb{F}_q) q^n \prod_{i=0}^{n-1} (q^n - q^i) q^{\binom{n + 1}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) q^{\binom{n + 1}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n(n + 1) \binom{n + 1}{2} = \frac{n(n + 1)}{2} n q^n times the order of GL(n,q)
special affine group SA(n,q) or SA(n,\mathbb{F}_q) q^n \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} q^{\binom{n + 1}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) q^{\binom{n + 1}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2  + n - 1 \binom{n + 1}{2} = \frac{n(n- 1)}{2} n - 1 q^n times the order of GL(n,q)
general semiaffine group \Gamma A(n,q) or \Gamma A(n,\mathbb{F}_q) rq^n \prod_{i=0}^{n-1} (q^n - q^i) rq^{\binom{n + 1}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) rq^{\binom{n + 1}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n(n + 1) \binom{n + 1}{2} = \frac{n(n + 1)}{2} n r times the order of GA(n,q)
special semiaffine group  ? rq^n \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q - 1} rq^{\binom{n + 1}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) rq^{\binom{n + 1}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2  + n - 1 \binom{n + 1}{2} = \frac{n(n- 1)}{2} n - 1 r times the order of SA(n,q)
unitriangular matrix group UT(n,q) or UT(n,\mathbb{F}_q) \prod_{i = 0}^{n- 1} q^{n-1-i} q^{\binom{n}{2}} q^{\binom{n}{2}} \binom{n}{2} = \frac{n(n-1)}{2} \binom{n}{2} = \frac{n(n-1)}{2} 0 Each of the entries above the diagonal can take any of the values in \mathbb{F}_q; there are \binom{n}{2} entries to choose.
triangular matrix group (diagonal entries not required to be one); this is an example of a Borel subgroup  ? \prod_{i=0}^{n-1} (q^{n-1-i}(q-1)) q^{\binom{n}{2}}(q -1)^n q^{\binom{n}{2}}(q -1)^n \binom{n + 1}{2} = \frac{n(n+1)}{2} \binom{n}{2} = \frac{n(n-1)}{2} n Each of the entries above the diagonal can take any of the values in \mathbb{F}_q; there are \binom{n}{2} entries to choose. Each of the n entries of the diagonal can take any of |\mathbb{F}_q^\ast| = q - 1 values.

Explanation for order of general linear group over a finite field

We describe here the reasoning behind the formula for the order of the general linear group GL(n,q) = GL(n,\mathbb{F}_q).

The order equals the number of invertible n \times n matrices with entries over \mathbb{F}_q. The set of such matrices is in correspondence with the set of ordered bases for \mathbb{F}_q^n, the n-dimensional vector space over \mathbb{F}_q (for instance, we can identify the columns of the matrix with the vectors in the ordered basis). Thus, it suffices to count the number of possible ordered bases for \mathbb{F}_q^n.

For the first vector of the ordered basis, there are q^n - 1 possible choices (all nonzero vectors work). For the second vector, there are q^n - q choices (all vectors that are not in the span of the first vector work). After the first i basis vectors are chosen, the number of possibilities for the next basis vector are q^n - q^i, because q^i is the size of the subspace spanned by the first i basis vectors. By the product rule in combinatorics, we get that the total number of possibilities is:

\prod_{i=1}^n (q^n - q^i) = (q^n - 1)(q^n - q) \dots (q^n - q^{n-1})

Explanation for order of special linear group over a finite field

The group SL(n,q) is the kernel of the determinant map, a surjective homomorphism from GL(n,q) to \mathbb{F}_q^\ast. The homomorphism is surjective because for any a \in \mathbb{F}_q^\ast, we can construct a diagonal matrix with one diagonal entry a and the remaining entries equal to 1, and this maps to a under the determinant map.

Essentially by Lagrange's theorem and the first isomorphism theorem, we know that the order of the kernel is the order of the whole group divided by the order of the image. Thus:

|SL(n,q)| = \frac{|GL(n,q)|}{|\mathbb{F}_q^\ast|}

We now use the expression obtained for |GL(n,q)| and use that |\mathbb{F}_q^\ast| = q - 1.

Explanation for order of projective general linear group over a finite field

The group PGL(n,q) is the quotient of GL(n,q) by the center of GL(n,q).

The center of GL(n,q) is the subgroup of scalar matrices (see center of general linear group is group of scalar matrices over center), and is isomorphic to \mathbb{F}_q^\ast.

Thus, by Lagrange's theorem, the order of the quotient PGL(n,q) is:

|PGL(n,q)| = \frac{|GL(n,q)|}{|\mathbb{F}_q^\ast|}

We now use the expression obtained for |GL(n,q)| and use that |\mathbb{F}_q^\ast| = q - 1.

Explanation for order of projective special linear group over a finite field

The group PSL(n,q) is the quotient group of SL(n,q) by its intersection with the center of GL(n,q).

The intersection of SL(n,q) and the center of GL(n,q) is the subgroup of scalar matrices of determinant 1. The determinant of a n \times n scalar matrix is the n^{th} power of the scalar value, so the intersection comprises those scalar matrices whose scalar values are n^{th} roots of unity. Since \mathbb{F}_q^\ast is cyclic of order q - 1 (see multiplicative group of a finite field is cyclic), the number of such elements is \operatorname{gcd}(n,q-1).

Thus, the kernel of the quotient map from SL(n,q) to PSL(n,q) has order \operatorname{gcd}(n,q-1). We thus get, by Lagrange's theorem:

|PSL(n,q)| = \frac{|SL(n,q)|}{\operatorname{gcd}(n,q-1)}

Simplifying this gives the expressions in the table above.

Explanation for order of general semilinear group over a finite field

The general semilinear group \Gamma L (n,q) is a semidirect product:

\Gamma L(n,q) = GL(n,q) \rtimes \operatorname{Aut}(\mathbb{F}_q)

Therefore, we have:

|\Gamma L(n,q)| = |GL(n,q)||\operatorname{Aut}(\mathbb{F}_q)|

Since q = p^r, \mathbb{F}_q is a degree r extension of its prime subfield \mathbb{F}_p. The extension is a Galois extension, and the automorphism group is therefore equal to the Galois group of the extension, and is cyclic of order r (it is generated by the Frobenius automorphism x \mapsto x^p). We thus get:

|\Gamma L(n,q)| = |GL(n,q)| \cdot r

We substitute the formulas calculated for |GL(n,q)| and obtain the formulas for |\Gamma L(n,q)|.

Explanation for order of outer linear group over a finite field

The outer linear group OL(n,q) is a semidirect product:

OL(n,q) = GL(n,q) \rtimes \mathbb{Z}/2\mathbb{Z}

where the non-identity element of \mathbb{Z}/2\mathbb{Z} acts via the transpose-inverse map. Thus:

|OL(n,q)| = |GL(n,q)| \cdot 2

We substitute the formulas calculated for |GL(n,q)| and obtain the formulas for |OL(n,q)|.

Explanation for order of outer semilinear group over a finite field

The outer semilinear group O\Gamma L (n,q) is a semidirect product:

O\Gamma L(n,q) = GL(n,q) \rtimes (\operatorname{Aut}(\mathbb{F}_q) \times \mathbb{Z}/2\mathbb{Z})

Therefore, we have:

|O\Gamma L(n,q)| = |GL(n,q)||\operatorname{Aut}(\mathbb{F}_q)| \cdot 2

Since q = p^r, \mathbb{F}_q is a degree r extension of its prime subfield \mathbb{F}_p. The extension is a Galois extension, and the automorphism group is therefore equal to the Galois group of the extension, and is cyclic of order r (it is generated by the Frobenius automorphism x \mapsto x^p). We thus get:

|O\Gamma L(n,q)| = |GL(n,q)||\operatorname{Aut}(\mathbb{F}_q)| \cdot r \cdot 2

We substitute the formulas calculated for |GL(n,q)| and obtain the formulas for |O\Gamma L(n,q)|.

General justification for degree of polynomial describing the order

The degree of the polynomial giving the order of the group can be thought of as corresponding to the algebraic dimension, using, for instance, the Zariski topology. Note that applying the Zariski topology on a finite field won't work, because the topology for a variety over a finite field is discrete. However, we can look at the corresponding concept for an infinite field and then intersect with the points realized over the finite field \mathbb{F}_q. We go over these justifications briefly for the important cases:

Group Degree of polynomial giving the order Justification in terms of algebraic dimension
general linear group n^2 Over an infinite field, the general linear group is an open, and hence dense, subset of the n^2-dimensional space of matrices over the field, because it is defined by the determinant (a degree n polynomial in the n^2 variables) being nonzero.
special linear group n^2 - 1 Over an infinite field, the special linear group is a codimension-one closed subset of the n^2-dimensional space of matrices over the field, because it is defined by the determinant (a degree n polynomial in the n^2 variables) being exactly one.
projective general linear group n^2 - 1 Over an infinite field, the projective general linear group is a quotient variety of the general linear group by the equivalence relation of being scalar multiples of each other. It therefore has dimension one less than the general linear group.
general affine group n^2 + n The dimension of this is the sum of the dimension of the vector space (n) and the dimension of the general linear group (n^2).
special affine group n^2 + n - 1 The dimension of this is the sum of the dimension of the vector space (n) and the dimension of the general linear group (n^2 - 1).

General justification for largest power of q dividing the order

For all linear groups, the largest power of q dividing the order is \binom{n}{2}. All of these factors of q are attained in the unitriangular matrix group (the group of upper triangular matrices with 1s on the diagonal).

For affine groups, we get an additional factor of q^n, and thus an addition of n to the exponent.

General justification for largest power of q -1 dividing the order

The largest power of q - 1 dividing the order corresponds to the dimension of the maximal torus (without considering extensions, i.e., the torus realizable over \mathbb{F}_q). We go over the justifications briefly for some important cases:

Group Power of q - 1 in order Justification in terms of algebraic dimension of largest torus
general linear group n The torus is the group of invertible diagonal matrices. The points in this torus over \mathbb{F}_q form the group (\mathbb{F}_q^\ast)^n, and the dimension is n
special linear group n -1 The torus is the group of invertible diagonal matrices where the product of the diagonal entries is 1. There are n - 1 entries that can be freely chosen from the multiplicative group, and the n^{th} entry is constrained by them. The points in this torus over \mathbb{F}_q form the group (\mathbb{F}_q^\ast)^{n - 1}, and the dimension is n - 1
projective general linear group n - 1 The torus is the group of invertible matrices where the product of the diagonal entries is 1, modulo the scalar matrices. There are n - 1 degrees of freedom, because 1 degree of freedom is taken away by the ability to scale the matrix.

General justification for largest power of other cyclotomic polynomials dividing the order

For any d with 1 \le d \le n, the exponent for the largest power of the cyclotomic polynomial \Phi_d(q) dividing the order is \lfloor \frac{n}{d} \rfloor. This can also be justified in terms of a "torus" as follows:

  • The field extension \mathbb{F}_{q^d} can be embedded in the ring of d \times d matrices over \mathbb{F}_q as a subring, through its action on itself as a d-dimensional vector space over \mathbb{F}_q. With this, \mathbb{F}_{q^d}^\ast gets embedded in GL(d,q).
  • Inside GL(n,q), we can think of GL(d,q) as occupying a block of size d \times d. Thus, a block of size d \times d can accommodate \mathbb{F}_{q^d}^\ast.
  • There is space for \lfloor \frac{n}{d} \rfloor such blocks, so \left(\mathbb{F}_{q^d}^\ast\right)^{\lfloor \frac{n}{d} \rfloor} can be embedded in GL(n,q), but no larger power of \mathbb{F}_{q^d}^\ast can.

Notes on primes that divide the order of linear groups

The following are equivalent conditions determining whether a prime t other than q divides the order of GL(n,q). These conditions also work for SL(n,q), PGL(n,q), and PSL(n,q) for n \ge 2:

  • The order of q modulo t is less than or equal to n.
  • t divides q^d - 1 for some d between 1 and n.
  • t divides \Phi_d(q) for some d between 1 and n.

Further notes:

  • All the primes less than or equal to n divide the order of GL(n,q) . This can be seen from the above description; it can also be seen from the embedding of the symmetric group S_n inside GL(n,q).

For a finite discrete valuation ring (DVR) of length l over a field of size q

Formulas

In the formulas below, the length of the discrete valuation ring R is l and the size of the residue field is q. The size of the discrete variation ring is therefore q^l.

The degree (order of matrices involved, or dimension of free module over the DVR being acted upon) is n.

The characteristic of the field is a prime number p. q is a prime power with underlying prime p. We let r = \log_pq, so q = p^r and r is a nonnegative integer.

Example discrete variation rings to consider:

  • \mathbb{F}_q[t]/(t^l)
  • \mathbb{Z}/p^l\mathbb{Z} (here r = 1 so p = q)

The special case l = 1 reduces to the previous section.

For PSL(n,R), there is an additional variable, w, which is the number of n^{th} roots of unity in the multiplicative group of R. The value of w doesn't have a formula in terms of the parameters discussed so far, and it can vary for different rings with the same values of q and l. (For more discussion, see the section #Explanation for order of projective special linear group over a finite discrete valuation ring).

For \Gamma L(n,R), there is an additional parameter, a, for the order of the automorphism group of R. The value of w doesn't have a formula in terms of the parameters discussed so far, and it can vary for different rings with the same values of q and l. (For more discussion, see the section #Explanation for order of general semilinear group over a finite discrete valuation ring).


Group Symbolic notation Order formula Order formula (powers of q taken out) Order formula (maximally factorized) Degree as polynomial in q (same as algebraic dimension) Multiplicity of factor q Multiplicity of factor q - 1 Quick explanation for order
general linear group GL(n,R)  \prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)}) q^{n^2(l - 1) + \binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) q^{n^2(l - 1) + \binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2l n^2(l - 1) + \binom{n}{2} = \frac{n(2nl - n - 1)}{2} n See full explanation below.
special linear group SL(n,R) \frac{\prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)})}{q^{l - 1}(q - 1)} q^{(n^2 - 1)(l - 1) + \binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) q^{(n^2 - 1)(l - 1) + \binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} (n^2 - 1)l (n^2 - 1)(l - 1) + \binom{n}{2} n - 1 See full explanation below
projective general linear group PGL(n,R) \frac{\prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)})}{q^{l - 1}(q - 1)} q^{(n^2 - 1)(l - 1) + \binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1) q^{(n^2 - 1)(l - 1) + \binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor} (n^2 - 1)l (n^2 - 1)(l - 1) + \binom{n}{2} n - 1 See full explanation below
projective special linear group PSL(n,R) \frac{\prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)})}{q^{l - 1}(q - 1)w} \frac{q^{(n^2 - 1)(l - 1) + \binom{n}{2}} \prod_{i=0}^{n-2} (q^{n-i} - 1)}{w} \frac{q^{(n^2 - 1)(l - 1) + \binom{n}{2}} (q - 1)^{n - 1} \prod_{d=2}^n (\Phi_d(q))^{\lfloor n/d \rfloor}}{w} (n^2 - 1)l (n^2 - 1)(l - 1) + \binom{n}{2} (ignoring w) n - 1 (ignoring w) Here w is the number of n^{th} roots of unity in R^\ast. See full explanation below
general semilinear group \Gamma L(n,R) a \prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)}) q^{n^2(l - 1) + \binom{n}{2}} \prod_{i=0}^{n-1} (q^{n-i} - 1) q^{n^2(l - 1) + \binom{n}{2}} \prod_{d=1}^n (\Phi_d(q))^{\lfloor n/d \rfloor} n^2l n^2(l - 1) + \binom{n}{2} = \frac{n(2nl - n - 1)}{2} n Here a is the size of \operatorname{Aut}(R). See full explanation below.

Explanation for order of general linear group over a finite discrete valuation ring

There are a couple of ways of looking at this.

Using the concept of freely generating sequences

NOTE: The statements below are not rigorously justified, but the argument can be made more rigorous.

GL(n,R) corresponds to the set of freely generating sequences (of length n) for the free module R^n. To obtain such a freely generating sequence:

  • The first element of the sequence can be any element of R^n that is not in M^n where M is the unique maximal ideal. The number of possibilities is q^{nl} - q^{n(l-1)}.
  • The second element has to be outside of the submodule generated by the first element with M^n. The number of possibilities is q^{nl} - q^{1 + n(l-1)}.
  • The (i + 1)^{th} element has to be outside the submodule generated by the first i elements with M^n. The number of possibilities is q^{nl} - q^{i+ n(l-1)}.

The total number of elements is therefore  \prod_{i=0}^{n-1} (q^{nl} - q^{i + n(l-1)})

Using kernels of homomorphisms

If M is the maximal ideal of R, we have a sequence of homomorphisms:

GL(n,R) =GL(n,R/M^l) \to GL(n,R/M^{l-1}) \to GL(n,R/M^{l-2}) \to \dots \to GL(n,R/M) = GL(n,q)

All elements in the kernel at each stage comprise matrices that are congruent to the identity matrix modulo the relevant power of M.

We can also establish the converse:

  • The multiplicative monoid of all n \times n matrices over R/M^i that are congruent to the identity matrix modulo M^{i-1}/M^i is isomorphic to the additive group of n \times n matrices over \mathbb{F}_q. This can be seen by verifying the matrix multiplication.
  • Therefore, all matrices over R/M^i that are congruent to the identity matrix modulo M^{i-1}/M^i are invertible, and hence in the kernel of GL(n,R/M^i) \to GL(n,R/M^{i-1}).
  • The map GL(n,R/M^i) \to GL(n,R/M^{i-1}) is surjective: to see this, pick any element of GL(n,R/M^{i-1}). Lift both it and its inverse arbitrarily to n \times n matrices over R/M^i (we don't yet know if these lifts are invertible, but we'll show that in a moment). The product of these lifts is congruent to the identity matrix mod M^{i - 1}/M^i. As established right above, this product is invertible, hence so is the lift of the original matrix. Thus, the map is surjective.

Thus, by Lagrange's theorem and the first isomorphism theorem, we get:

|GL(n,R/M^i)| = q^{n^2}|GL(n,R/M^{i-1})|

Applying this for i = 2, 3, \dots, l we get:

|GL(n,R)| = q^{n^2(l - 1)} |GL(n,q)|

Explanation for order of special linear group over a finite discrete valuation ring

The special linear group SL(n,R) is the kernel of the determinant map GL(n,R) \to R^\ast.

The determinant map is surjective, because for each element of R^\ast, we have a diagonal matrix with that as the top left entry and the remaining diagonal entries as 1s.

Thus, by Lagrange's theorem and the first isomorphism theorem, we get:

|SL(n,R)| = \frac{|GL(n,R)|}{|R^\ast|} = \frac{|GL(n,R)|}{|GL(1,R)|} = \frac{|GL(n,R)|}{q^{l-1}(q - 1)}

Plugging in the value of |GL(n,R)| from the previous section, we get the formula we expect.

Explanation for order of projective general linear group over a finite discrete valuation ring

The group PGL(n,R) is the quotient of GL(n,R) by the center of GL(n,R).

The center of GL(n,R) is the subgroup of scalar matrices (see center of general linear group is group of scalar matrices over center), and is isomorphic to R^\ast.

Thus, by Lagrange's theorem, the order of the quotient PGL(n,R) is:

|PGL(n,R)| = \frac{|GL(n,R)|}{|R^\ast|} = \frac{|GL(n,R)|}{|GL(1,R)|} = \frac{|GL(n,R)|}{q^{l-1}(q - 1)}

Explanation for order of projective special linear group over a finite discrete valuation ring

The group PSL(n,R) is the quotient group of SL(n,R) by its intersection with the center of GL(n,R).

The intersection of SL(n,R) and the center of GL(n,R) is the subgroup of scalar matrices of determinant 1. The determinant of a n \times n scalar matrix is the n^{th} power of the scalar value, so the intersection comprises those scalar matrices whose scalar values are n^{th} roots of unity. Let the number of n^{th} roots of unity in R^\ast be w.

We then get:

|PSL(n,R)| = \frac{|SL(n,R)|}{w}

This gives the formulas in the table.

Examples to show that the number of roots of unity is not determined by the listed parameters

Consider the case l = 3, r = 1, so that p = q, with p > 2, and further, n = p. (For concreteness, we can take p = q = n = 3).

Consider two discrete valuation rings meeting these criteria:

  • R_1 = \mathbb{Z}/p^3\mathbb{Z}
  • R_2 = \mathbb{F}_p[t]/(t^3)

Then we have:

  • R_1^\ast is a cyclic group of order p^2(p - 1). In particular, the number of p^{th} roots of unity in it is p.
  • R_2^\ast is a group of exponent p(p - 1), and has p^2 many p^{th} roots of unity (in particular, an element is a p^{th} root of unity if its constant term, when it's written as a polynomial, is 1).

We thus see that the value w could be p or p^2 depending on the ring, even though both rings have the same values of all other listed parameters.

Explanation for order of general semilinear group over a finite field

The general semilinear group \Gamma L (n,R) is a semidirect product:

\Gamma L(n,R) = GL(n,R) \rtimes \operatorname{Aut}(R)

Therefore, we have:

|\Gamma L(n,R)| = |GL(n,R)||\operatorname{Aut}(R)|

Letting a = |\operatorname{Aut}(R)| and using the expressions for |GL(n,R)| gives the expressions for |\Gamma L(n,R)|.

Example to illustrate that the order of the automorphism group is not completely determined by the listed parameters

Consider the case l = 2, r = 1, so that p = q, with p > 2. For concreteness, we can take p = q = 3.

We will show that these two rings have different automorphism groups:

  • R_1 is the ring \mathbb{Z}/p^2\mathbb{Z}
  • R_2 is the ring \mathbb{F}_p[t]/(t^2)

R_1 has a trivial automorphism group, because the multiplicative unit 1 is fixed by any automorphism, and every element is a multiple of 1.

On the other hand, R_2 has automorphism group \mathbb{F}_p^\ast of order p - 1, with \alpha \in \mathbb{F}_p acting as the automorphism that sends t to \alpha t. Since p > 2, this is a nontrivial automorphism group.

General justification for degree of polynomial describing the order

In general, the degree of polynomial describing the order of a linear group over a discrete valuation ring is l times the degree of the corresponding polynomial over the residue field. The loose reason: we are operating over a ring of size q^l instead of a field of size q. More explicitly, we can use similar reasoning about algebraic dimension as we use over fields, but the algebraic dimension is now over the ring of size q^l instead of the field of size q, so all the degrees get multiplied by l.

Group Degree of polynomial describing the order, when on a field of size q Degree of polynomial describing the order, when on a discrete valuation ring of length l with residue field of size q
general linear group n^2 n^2l
special linear group n^2 - 1 (n^2 - 1)l
projective general linear group n^2 - 1 (n^2 - 1)l
general affine group n^2 + n (n^2 + n)l
special affine group n^2 + n - 1 (n^2 + n - 1)l