SYMMETRICA-MANUAL -- Linear, affine and projective groups

Linear, affine and projective groups

Linear, affine and projective groups

Let q=p^r, where p is a prime, and let GF(q) be a finite field with q elements. The general linear group GL_k(q) is the group of all regular k´k matrices over GF(q). It acts on the k-dimensional vector space GF(q)^k by the following definition:

GL_k(q)´GF(q)^k -> GF(q)^k (A,v) -> A·v.

Furthermore let AFF_k(q) be the set {(A,b) | AÎGL_k(q), bÎGF(q)^k} . After defining a composition (A₁,b₁)(A₂,b₂):=(A₁A₂,b₁+A₁ b₂) this group acts as the group of all affine mappings on GF(q)^k by the following definition:

AFF_k(q)´GF(q)^k -> GF(q)^k ((A,b),v) -> A·v+b.

The cycle indices of these two actions [2] can be computed by

INT zykelind_glkq(k,q,c)   OP k,q,c;
INT zykelind_affkq(k,q,c)  OP k,q,c;

In both cases k and q are INTEGER objects, k takes the dimension of the vector space, q the cardinality of the finite field. The result c is a POLYNOM object.

The cardinalities of GL_k(q) and AFF_k(q) can be computed by

INT ordnung_glkq(k,q,c)    OP k,q,c;
INT ordnung_affkq(k,q,c)   OP k,q,c;

Again k and q are INTEGER objects, k takes the dimension of the vector space, q the cardinality of the finite field. The result c is an INTEGER object.

In [12] Kung gave a very elegant formula to compute the number of matrices in GL_k(q) which commute with a block diagonal matrix D(p,l) associated to a monic, irreducible polynomial p(x)ÎGF(q)[x] and a partition l, which tells how many companion matrices and hyper-companion matrices of p(x) occur in D(p,l). The function

INT kung_formel(d,lambda,q,c)  OP d,lambda,q,c;

computes c (an INTEGER object), which is the number of matrices, which commute with D(p,l), where d is the degree of the polynomial p(x) (an INTEGER object), lambda is the partition l (a PARTITION object) and q is the cardinality of the finite field. This formula can be used to determine the number of elements in the conjugacy class of a matrix in GL_k(q) given in a normal form.

The function

INT number_of_irred_poly_of_degree(d,q,c)   OP d,q,c;

computes c (an INTEGER object) to be the number of irreducible, monic polynomials of degree d (an INTEGER object) over a finite field with q (an INTEGER object) elements.

For the enumeration of classes of linear (n,k)-Codes over GF(q) (see [8][6][5]) one has to compute the cycle index of the projective group [2] PGL(k,q):=GF(q)^*\\GL_k(q) acting on the projective space PG(k-1,q):=GF(q)^*\\GF(q)^k \ {0} . This group action is given by

PGL(k,q)´PG(k-1,q) -> PG(k-1,q)

(GF(q)^*(A),GF(q)^*(v)) -> GF(q)^*(A·v).

The cycle index of this action can be computed by

INT zykelind_pglkq(k,q,c)   OP k,q,c;

where k and q are INTEGER objects as above, and c is the computed cycle index a POLYNOM object. In the case q=2 the cycle index of PGL(k,2) can be computed by

zykelind_glkq(k,q,c);zykelind_dec_apply(c);

as well.

It is also possible to define linear and affine groups for k-dimensional modules over residue-class-rings Z_n:=Z/nZ. At the moment the following two routines are just working for square free INTEGERs n.

INT zykelind_glkzn(k,n,c)   OP k,n,c;
INT zykelind_affkzn(k,n,c)  OP k,n,c;

In both cases k is the dimension of the module, n is the square free modulus (both are INTEGER objects) and c is the computed cycle index.

In the case k=1 Wei and Xu computed the cycle index of AFF₁(n) in [17] for arbitrary n. This formula is implemented in

INT zykelind_aff1zn(n,c)  OP k,n,c;

n is the modulus (an INTEGER object) and c is the computed cycle index.

harald.fripertinger@kfunigraz.ac.at,
last changed: November 19, 2001

Linear, affine and projective groups