Encoding of general linear groups

From Groupprops
Jump to: navigation, search

Template:Particular IAPS encoding

Template:General linear groups

Here, we describe a method to encode general linear groups over a finite field with q elements.

Encoding using matrix entries in the standard basis

We describe the encoding over a three-letter alphabet, with two of the letters functioning as bits (0 and 1) and the third letter serving as a comma, or a separator.

We start out with a map b from F_q to the set of binary words. Let l denote the maximum possible length of a binary word arising from b. Further, we assume we have algorithms to add, subtract, multiply, and divide field elements based on their encodings.

We can choose a map where l = \log_2 q. However, such a map may not be the most optimal, or natural, from the viewpoint of field operations.


Encoding a group element

Let g be an element of GL_n(F_q). We encode g as follows. First, think of the matrix entries of g as a sequence of n^2 entries (reading in row-major format), each of which has q possibilities.

Now encode g as follows: Let the sequence be x_1,x_2,\ldots,x_{n^2}. Then the encoding is b(x_1) followed by a comma, followed by b(x_2) followed by a comma, and so on.

Maximum length of a code-word

The maximum length of a code-word is n^2 ( l + 1). Since l is independent of n, the maximum length of a code-word grows as n^2.

The order of the general linear group grows roughly as q^{n^2}, so the maximum length of a code-word is logarithmic in the size of the group. Thus, the encoding is dense.

Algorithms for inverting and multiplying

For multiplying we can do the usual multiplication rule. This rule requires time that is polynomial in the maximum possible size of a code-word.PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

For inverting again, we need to compute the determinant, and then use the formula for the inverse in terms of the adjugate matrix and the determinant. This again takes time polynomial in the maximum possible length of a code-word.

Algorithm for block concatenation

The algorithm for block concatenation is simple: just put in the entries at the relevant places, and insert enouh zeroes in between!