Encoding of general linear groups
Here, we describe a method to encode general linear groups over a finite field with 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 from to the set of binary words. Let denote the maximum possible length of a binary word arising from . Further, we assume we have algorithms to add, subtract, multiply, and divide field elements based on their encodings.
We can choose a map where . However, such a map may not be the most optimal, or natural, from the viewpoint of field operations.
Encoding a group element
Let be an element of . We encode as follows. First, think of the matrix entries of as a sequence of entries (reading in row-major format), each of which has possibilities.
Now encode as follows: Let the sequence be . Then the encoding is followed by a comma, followed by followed by a comma, and so on.
Maximum length of a code-word
The maximum length of a code-word is . Since is independent of , the maximum length of a code-word grows as .
The order of the general linear group grows roughly as , 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 multiplyingFor 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!