MATHEMATICS OF COMPUTATION Volume 00, Number 0, Pages 000–000 S 0025-5718(XX)0000-0

COMPUTING IN GROUPS OF LIE TYPE

ARJEH M. COHEN, SCOTT H. MURRAY, AND D. E. TAYLOR

Abstract. We describe two methods for computing with the elements of untwisted groups of Lie type: using the Steinberg presentation and highest weight representations. We give algorithms for element arithmetic within the Steinberg presentation. Conversion between this presentation and linear representations is achieved using a new generalisation of row and column reduction.

1. Introduction

The groups of Lie type are among the most important structures in modern mathematics. Examples of such groups include reductive Lie groups, reductive algebraic groups, and finite groups of Lie type (which include most of the finite simple groups). Many problems in the representation theory of groups of Lie type have been solved using computers [vLCL92, GHL^{+}96]. In this paper, we give methods for computing within the groups themselves, a problem which has only recently been tackled [Hal00, Rie98]. We have implemented these algorithms in the Magma computer algebra system [BC97]. We confine our attention to the untwisted groups; automorphisms and twisted groups will be dealt with in subsequent work.

Computational group theory has three main strands: permutation groups, matrix groups, and finitely presented groups. The permutation group approach has traditionally been the most effective because of the very efficient Schreier-Sims family of algorithms [But91]. Recently, effective algorithms for matrix groups over finite fields have started to appear, in particular, the matrix group recognition project based on Aschbacher’s theorem [LG01]. The Todd-Coxeter and Knuth-Bendix algorithms for finitely presented groups [Sim94] are the oldest methods in computational group theory.

Permutation group methods are clearly useless for infinite groups of Lie type. Even for finite groups of Lie type, these methods soon become impractical; for example, the smallest permutation representation of E_{8}(2) has degree

293, 091, 386, 578, 365, 375 ≈ 2.9 × 10^{17},

well beyond the reach of existing computers [LS87].

\begin{matrix}c \\ ◯ \end{matrix}2000 American Mathematical Society

Received by the editor December 28, 2002.

2000 Mathematics Subject Classification. Primary 20G15, 20C40.

Key words and phrases. Group of Lie type, reductive algebraic group, computational algebra.

This paper was written during a stay of the first author at the University of Sydney. We wish to thank the institute for its hospitality.

On the other hand, for any field 𝔽, there is a faithful linear representation of E_{8}(𝔽) over 𝔽 of degree 248, which makes it feasible to do element operations (provided we can compute in 𝔽). [HRT01] constructs matrix representations for finite Chevalley groups; this has been implemented in Magma.

The groundbreaking work of [Ste62, Ste68] gives a presentation for the groups of Lie type. In the presentation for E_{8}(𝔽), each element can be expressed as a word of length at most 368. This does not necessarily give a finitely presented group, however, because some of our generators are parametrised by the field (more precisely, 240 terms are parametrised by the additive group 𝔽, 8 are parametrised by the multiplicative group 𝔽^{×}, and 120 are field independent). A word in this presentation requires less memory than a matrix representation, except for type A_{n} where the memory usage is asymptotically the same. An additional advantage is that there is a normal form for elements (the Bruhat decomposition) which reflects the Lie theoretic structure of the group, thus facilitating the use of Lie theoretic techniques. Another computationally important presentation for finite groups of Lie type is described in [BGK^{+}97, HS01].

In this paper, we describe methods for doing arithmetic in the Steinberg presentation over any field 𝔽 in which computation is possible. We note that [Rie98], mainly for 𝔽 = 𝔽_{2}, and [Hal00], mainly for unipotent subgroups, have done part of this work before. We also give algorithms for conversion between the Steinberg presentation and highest weight representations over the field 𝔽. Converting a word to a matrix builds on the methods of [dG01] for Lie algebras. Converting a matrix to a word requires a generalisation of row and column reduction—this is the main result of this paper. Given these conversion algorithms, we can compute with either the presentation or a linear representation, whichever is most effective for the problem at hand.

A motivating application for this work is the matrix group recognition project [LG01], which provides a framework for decomposing a matrix group over a finite field into a subnormal subgroup chain whose quotients are almost simple. Our methods are useful for this project since most almost simple groups are finite groups of Lie type. Firstly the Steinberg presentation gives a computer representation of these groups in which conjugacy classes and other such properties can be computed efficiently using Lie theory. Secondly our generalised row and column reduction algorithm gives a membership test for these groups as matrix groups, which is necessary for recognising simple groups of Lie type [KS01].

We use standard group theoretic notation [AB95]. Our group actions are on the right, so conjugation is given by x^{y} = y^{−1}xy and the commutator by [x, y] = x^{−1}y^{−1}xy. We occasionally use left conjugation: ^{y}x = yxy^{−1}.

In Sections 2 and 3, we discuss the computation of root systems and structure constants. Section 4 describes the Steinberg presentation. Section 5 contains element arithmetic and canonical form algorithms for the presentation; an implementation of these algorithms is available in release 2.8 of Magma. We describe algorithms for converting between the Steinberg presentation and highest weight representations in Sections 6 and 7; these will be available in the next release of Magma. In Section 8, we discuss applications of our algorithms and give an example.

2. Root data

A root system is the basic structure used for the classification of complex semisimple Lie algebras; a pair of root systems in duality is the structure used for the classification of reductive algebraic groups—such a pair is called a root datum. We assume that all permutation and matrix actions are on the right. This is in keeping with the conventions of computational group theory but leads to differences between our formulas and those found in standard references such as [Dem65], [Car93], and [Spr98].

2.1. Definition. Let X and Y be free ℤ-modules of rank d with a bilinear pairing ⟨∘, ∘⟩ : X × Y → ℤ putting them in duality. Assume we have a basis e_{1}, …, e_{d} for X and a dual basis f_{1}, …, f_{d} for Y, so that ⟨e_{i}, f_{j}⟩ = δ_{ij}. Let Φ be a finite subset of X and suppose that for each α in Φ we have a corresponding α^{⋆} in Y; set Φ^{⋆} = {α^{⋆} | α ∈ Φ} and α^{⋆⋆} = α. We call the elements of Φ roots and the elements of Φ^{⋆} coroots.

Given a root α we define linear maps s_{α} : X → X by xs_{α} = x − ⟨x, α^{⋆}⟩α and s_{α}^{⋆} : Y → Y by ys_{α}^{⋆} = y−⟨α, y⟩α^{⋆}. These maps are reflections if one of the following equivalent properties hold: ⟨α, α^{⋆}⟩ = 2; s_{α}^{2} = 1; ⟨xs_{α}, ys_{α}^{⋆}⟩ = ⟨x, y⟩ for all x ∈ X and y ∈ Y; αs_{α} = −α.

We say that R = (X, Φ, Y, Φ^{⋆}) is a root datum if the following are satisfied for every root α in Φ: s_{α} and s_{α}^{⋆} are reflections; Φ is closed under the action of s_{α}; and Φ^{⋆} is closed under the action of s_{α}^{⋆}. Furthermore, we require that all our root data be reduced, i.e. if α and β are roots with β a multiple of α, then β = ±α. The Weyl group W is the group generated by the reflections s_{α}.

2.2. Simple roots and positive roots. The roots α_{1}, …, α_{n} are simple roots for R if they are a basis of ℚ Φ ≤ ℚ ⊗X and Φ = Φ^{+} ∪Φ^{−}, where Φ^{+} is the set of roots that are linear combinations of the simple roots with nonnegative coefficients and Φ^{−} = −Φ^{+}. The elements of Φ^{+} are called positive roots and the elements of Φ^{−} are called negative roots. The coroots corresponding to the simple (resp. positive, negative) roots are called simple (resp. positive, negative) coroots.

We call n the rank and d the dimension of R; if n = d then R is semisimple. The Cartan matrix of R is C = [⟨α_{i}, α_{j}^{⋆}⟩]_{i,j=1}^{n}. Given a root α = ∑_{i=1}^{n} a_{i}α_{i}, we define its height by h(α) = ∑_{i=1}^{n} a_{i}. We can define a reflection invariant bilinear form on ℚ ⊗ X by

(x, y) = ∑_{α∈Φ}⟨x, α^{⋆}⟩⟨y, α^{⋆}⟩.

and a corresponding norm ∥x∥^{2} = (x, x). The fundamental weights ω_{1}, …, ω_{n} are the elements of ℚ Φ such that ⟨ω_{i}, α_{j}^{⋆}⟩ = δ_{ij}. An element λ of ℚ ⊗ X is dominant if ⟨λ, α_{i}^{⋆}⟩ ≥ 0 for all i.

Given an element w in the Weyl group W, define

Φ_{w} = {α ∈ Φ^{+} | αw^{−1} ∈ Φ^{−}} = Φ^{+} ∩ Φ^{−}w.

The length l(w) is the cardinality of Φ_{w}; W contains a unique longest element, which we denote w_{0}.

Lemma 2.1.

(1) Given a reduced expression w = s_{β_{1}} ⋯ s_{β_{l}} we have

Φ_{w} = { β_{l}, β_{l−1}s_{β_{l}}, β_{l−2}s_{β_{l}−1}s_{β_{l}}, …, β_{1}s_{β_{2}} ⋯ s_{β_{l}} }.

(2) Φ_{vw} is the disjoint union of Φ_{w} and Φ_{v}w whenever l(vw) = l(v) + l(w);

(3) Φ_{w^{−1}} = −Φ_{w}w^{−1};

(4) Φ^{+} is the disjoint union of Φ_{w} and Φ_{w_{0}w}, where w_{0} is the longest element of W.

Proof. Parts (1) and (2) are proved in [Bou81]. Part (3) follows from the definition as follows

−Φ_{w}w^{−1} = −(Φ^{−}w ∩ Φ^{+})w^{−1} = Φ^{+} ∩ Φ^{−}w^{−1} = Φ_{w^{−1}}.

Finally, Φ is the disjoint union of Φ^{−}w and Φ^{+}w, so Φ^{+} is the disjoint union of Φ^{+} ∩ Φ^{−}w = Φ_{w} and Φ^{+} ∩ Φ^{+}w = Φ^{+} ∩ Φ^{−}w_{0}w = Φ_{w_{0}w}, and so we have (4). □

2.3. Computation. We now give a construction of root data suitable for computation. Take X and Y to be ℤ^{d} with e_{1}, …, e_{d} and f_{1}, …, f_{d} both the standard basis. A root datum is determined by a pair of n×d integer matrices A and B such that the rows of A are the simple roots and the rows of B are the corresponding coroots; i.e. A_{ij} = ⟨α_{i}, f_{j}⟩ and B_{ij} = ⟨e_{j}, α_{i}^{⋆}⟩. The Cartan matrix is C = AB^{t}.

Given a root β and a simple root α_{i}, knowledge of the Cartan matrix is sufficient to determine whether or not β+α_{i} is a root. Thus Φ^{+} can be constructed recursively from the simple roots. The positive roots are constructed and stored in an order compatible with height, i.e. h(α) < h(β) implies that α < β. We extend this to a linear ordering on Φ^{−} ∪ {0} ∪ Φ^{+} in the obvious way. The coroots are computed similarly.

3. Structure constants

We now briefly discuss the constants used to define semisimple Lie algebras and groups of Lie type, and efficient methods for computing them. See [Car72] or [Rie98] for more details.

Fix a root datum R = (X, Φ, Y, Φ^{⋆}). For every pair of linearly independent roots α and β, we define p_{αβ} to be the largest integer such that −p_{αβ}α + β is a root and q_{αβ} to be the largest integer such that q_{αβ}α + β is a root. The vectors

−p_{αβ}α + β, …, −α + β, β, α + β, …, q_{αβ}α + β

are all roots; they form the chain through β in the direction of α. Furthermore ⟨β, α^{⋆}⟩ = p_{αβ} − q_{αβ}.

The semisimple Lie algebra with root system Φ has basis elements e_{α}, for α a root, and h_{α}, for α a simple root, satisfying the relations

[h_{α}, h_{β}] = 0,  [e_{α}, h_{β}] = ⟨α, β^{⋆}⟩ e_{α},
[e_{−α}, e_{α}] = ∑_{i=1}^{n}⟨ω_{i}, α^{⋆}⟩h_{α_{i}},  [e_{α}, e_{β}] = \begin{cases}N_{αβ} e_{α+β} & if α + β ∈ Φ, \\ 0 & otherwise. \end{cases}

Chevalley (1955) showed that the constants N_{αβ} may be chosen to have the form ε_{αβ}(p_{αβ} + 1) where ε_{αβ} = ±1. This ensures that all the constants that appear in these relations are integral, so we can define a Lie algebra over ℤ, and hence over an arbitrary field. For convenience, we take N_{αβ} = 0 when α + β is not a root.

The constants p_{αβ}, q_{αβ}, and ∥α∥^{2} can be computed directly from the root datum. Hence it only remains to compute the constants ε_{αβ}. From Theorem 4.1.2 of [Car72], we get the equations

(3.1)  ε_{αβ} = −ε_{βα},
(3.2)  ε_{αβ} = −ε_{−α,−β}

for arbitrary roots α and β;

(3.3)  \frac{N_{αβ}}{∥γ∥^{2}} = \frac{N_{βγ}}{∥α∥^{2}} = \frac{N_{γα}}{∥β∥^{2}} ,
(3.4)  ε_{αβ} = ε_{βγ} = ε_{γα}

whenever α + β + γ = 0; and

(3.5)  \frac{N_{αβ}N_{γδ}}{∥α + β∥^{2}} + \frac{N_{βγ}N_{αδ}}{∥β + γ∥^{2}} + \frac{N_{γα}N_{βδ}}{∥γ + α∥^{2}} = 0

whenever α + β + γ + δ = 0 and no pair is antipodal. Given a nonsimple positive root ξ, take the positive roots α, β such that ξ = α + β and α is as small as possible with respect to the ordering of Section 2.3. We call (α, β) the extraspecial pair of ξ. We can choose the signs ε_{αβ} on the extraspecial pairs arbitrarily and then all the structure constants are determined [Car72, Proposition 4.2.2]. This method gives us every possible system of structure constants; hence, if a user does hand calculations using a particular formula for the constants, it is possible to set the constants in our code to agree with those calculations. An algorithm for determining the structure constants from their values on extraspecial pairs is given in [GS88]. Note that the number of extraspecial pairs is N − n where N is the number of positive roots. Furthermore N is easily shown to be O(n^{2}) by checking the number of roots for each of the classical types A_{n}, B_{n}, C_{n}, D_{n}.

In order to multiply elements in the Steinberg presentation efficiently, we must compute the structure constants very rapidly. Just storing the constants for the O(n^{2}) extraspecial pairs and using the algorithm mentioned above is too slow. On the other hand, storing the constants for all O(n^{4}) pairs uses too much memory. Hence we store the structure constants for pairs (α, β) with 0 < α < β and α + β ∈ Φ, which we call special pairs. There are O(n^{3}) such pairs, as can be shown by a case-by-case analysis for the classical types. We compute ε_{αβ} for the special pairs in the following order: first by the height of ξ = α + β, then by the position of α in the ordering of Section 2.3, then by the position of β in the same ordering. Take (α′, β′) to be the extraspecial pair of ξ. By (3.5) we have ε_{αβ} = sign(t_{1} − t_{2}) where

t_{1} = \frac{N_{−α′β}N_{β′α}}{∥β − α′∥^{2}} , and t_{2} = \frac{N_{−α′α}N_{β′β}}{∥α − α′∥^{2}} .

However β′ may be larger than α so N_{β′α} and N_{β′β} may not be among the constants we have already computed, and we would like to eliminate the negative root −α′ from these equations. If β − α′ = β′ − α ∉ Φ, then t_{1} = 0; otherwise, by (3.3),

t_{1} = \frac{∥β − α′∥^{2}N_{α′,β−α′}}{∥β∥^{2}} · \frac{∥β − α′∥^{2}N_{α′,β′−α}}{∥β′∥^{2}} · \frac{1}{∥β − α′∥^{2}}

= \frac{∥β − α′∥^{2}}{∥β∥^{2}∥β′∥^{2}} N_{α′,β−α′}N_{α,β′−α};

begin let ξ = α + β, let (α′, β′) be the extraspecial pair of ξ if β − α′ ∈ Φ then t_{1} = \frac{∥β−α′∥^{2}}{∥β∥^{2}} N_{α′,β−α′}N_{α,β′−α} else t_{1} = 0 end if if α − α′ ∈ Φ then t_{2} = \frac{∥α−α′∥^{2}}{∥α∥^{2}} N_{α′,α−α′}N_{β,β′−β} else t_{2} = 0 end if return sign(t_{1} − t_{2})

end

Algorithm 1. Computing ε_{αβ} for special pairs given extraspecial pairs

begin let m = 1 if α + β ∉ Φ then return 0 if β < 0 then α = −α; β = −β; m = −m using (3.2) 0 < β if α < 0 then

if −α < β then α < 0 < α + β < β

replace (α, β) by (α + β, −α) using (3.4) else α < α + β < 0 < β

replace (α, β) by (β, −α − β) using (3.4) end if

end if 0 < α, β if α > β then swap α and β; m = −m using (3.1) 0 < α < β look up ε_{αβ} return m · ε_{αβ}.

end

Algorithm 2. Computing ε_{αβ} for all pairs given special pairs

both of the constants that appear here have already been computed. Similarly, if α − α′ = β′ − β ∉ Φ, then t_{2} = 0; otherwise

t_{2} = \frac{∥α − α′∥^{2}}{∥α∥^{2}∥β′∥^{2}} N_{α′,α−α′}N_{β,β′−β}.

We can now cancel the common factor of 1/∥β′∥^{2} from t_{1} and t_{2} to get Algorithm 1.

An alternative method is the cochain formula, which was developed for simply laced types by [FK81] and [Spr98], and has been extended to all types by [Ryl01]. A modification of the cochain formula is given in [dG00] and has been implemented by him in both [GAP99] and Magma [BC97].

Once we have stored the constants for all special pairs, we need algorithms to compute them for an arbitrary pairs of roots. Since these algorithms are called many times for every multiplication in our group, it is vital that they be as efficient as possible. In particular, we eliminate all recursive calls to improve the speed of the algorithm. In Algorithm 2 we compute ε_{αβ}—similar methods are used to compute N_{αβ}, p_{αβ}, q_{αβ} and the root chains, once they have been stored for all special pairs.

The following constants are now easily computed, for roots α, β and positive integers i, j: whenever (i − 1)α + β is a root define

M_{αβi} = \binom{p_{αβ} + i}{i}ε_{βα} ⋯ ε_{(i−1)α+β,α};

whenever iα + jβ is a root define

C_{ijαβ} = \begin{cases}−M_{αβi} & for j = 1, \\ M_{βαj} & for i = 1, \\ −\frac{2}{3}M_{α+β,α,2} & for i = 3, j = 2, \\ −\frac{1}{3}M_{α+β,β,2} & for i = 2, j = 3; \end{cases}

and for p = p_{αβ} and q = q_{αβ} define

η_{αβ} = (−1)^{p} \frac{ε_{β−pα,α} ⋯ ε_{β−α,α}}{ε_{β−pα,α} ⋯ ε_{β+(q−p−1)α,α}} .

Note that these constants are also integral, thus allowing the presentations given in the next section to be defined for an arbitrary field.

4. The Steinberg presentation

In this section we describe a presentation for the group of Lie type with root datum R = (X, Φ, Y, Φ^{⋆}) over an arbitrary field 𝔽. More details on this presentation can be found in, for example, [Spr98].

4.1. The presentation. The Steinberg presentation for the group of Lie type G_{R}(𝔽) has generators x_{α}(a), for α a root and a ∈ 𝔽, and y ⊗ t, for y ∈ Y and t ∈ 𝔽^{×}. We also define auxiliary generators n_{α} = x_{α}(1)x_{−α}(−1)x_{α}(1) corresponding to the reflections s_{α} in the Weyl group. The relations are

(4.1)  (y ⊗ t)(y ⊗ u) = y ⊗ (tu),
(4.2)  (y ⊗ t)(z ⊗ t) = (y + z) ⊗ t,
(4.3)  α^{⋆} ⊗ t = x_{α}(−1)x_{−α}(1)x_{α}(−1) · x_{α}(t)x_{−α}(−t^{−1})x_{α}(t)
(4.4)  (y ⊗ t)^{n_{α}} = ys_{α}^{⋆} ⊗ t
(4.5)  x_{α}(a)x_{α}(b) = x_{α}(a + b),
(4.6)  x_{α}(a)^{x_{β}(b)} = x_{α}(a) ∏_{i,j>0} x_{iα+jβ}(C_{ijαβ}a^{i}b^{j}),
(4.7)  x_{α}(a)^{x_{−α}(t)} = x_{−α}(−t^{2}a)^{x_{α}(t^{−1})}

where α and β are linearly independent roots, y, z ∈ Y, a, b ∈ 𝔽 and t, u ∈ 𝔽^{×}. The product on the right hand side of (4.6) runs over roots of the form iα + jβ (for i and j positive integers) in the order described in Section 2.3. Relation (4.7) is redundant except when the rank is one.

4.2. Structure. The group G_{R}(𝔽) is linear algebraic, even though we have described it abstractly. We have not used the presentations described in [Car93] or [Ste68] because they define groups which are not necessarily algebraic when 𝔽 is not algebraically closed.

The following result follows from Section 11.1 of [Car72].

Theorem 4.1. If R is irreducible, then G_{R}(𝔽)′/Z(G_{R}(𝔽)′) is a simple group, unless R has type A_{1} with |𝔽 | ≤ 3, or type B_{2} or G_{2} with |𝔽 | = 2.

More generally, suppose G = G_{R}(𝔽) where R does not contain a summand of type A_{1} with |𝔽 | ≤ 3, or of type B_{2} or G_{2} with |𝔽 | = 2. Then G′/Z(G′) is a direct sum of simple groups. At the top we have G/G′ = (Y ⊗ 𝔽^{×})/(ℤΦ^{⋆} ⊗ 𝔽^{×}). At the bottom we have

Z(G) = {∏_{i=1}^{n} f_{i} ⊗ h_{i} | ∏_{i=1}^{n} h_{i}^{⟨x,f_{i}⟩} = 1 for all x in ℤΦ} .

We define the following important subgroups of G_{R}(𝔽).

• The maximal torus H is the subgroup generated by the elements y ⊗ t. It is isomorphic to the tensor product of the abelian groups Y and 𝔽^{×}. Note that Y is an additive group and 𝔽^{×} is a multiplicative group, so that, for instance, ny ⊗ t = y ⊗ t^{n} for an integer n.

• N is the subgroup generated by the maximal torus and the Weyl terms n_{α}; it is the normaliser of H, except in certain cases where the field is small. For w in the Weyl group W, take a reduced expression w = s_{β_{1}} ⋯ s_{β_{l}} and set ẇ = n_{β_{1}} ⋯ n_{β_{l}}; this is well defined by Proposition 9.3.2 of [Spr98]. There is an isomorphism between N/H and W given by Hẇ ↔ w.

• The unipotent subgroup U is generated by the elements x_{α}(a) for α a positive root and a ∈ 𝔽. Note that U is a nilpotent group and, if 𝔽 has characteristic p, U is a p-group. For w in W, define U_{w} to be the subgroup of U generated by the elements x_{α}(a) for α in Φ_{w} and a ∈ 𝔽.

• The Borel subgroup B = HU. Its double cosets correspond to the elements of the Weyl group by BẇB ↔ w.

4.3. Example: Type A_{n}. Suppose R is a semisimple root datum of type A_{n}. Then the quotient X/ℤΦ is a subgroup of the cyclic group of order n + 1; suppose it is the subgroup of size d for some d dividing n + 1. The group of Lie type G_{R}(𝔽) is isomorphic to SL_{n+1,d}(𝔽) /Z_{d}, where

SL_{n+1,d}(𝔽) = {X ∈ GL_{n+1}(𝔽) | det(X)^{d} = 1} and
Z_{d} = {tI_{n+1} | t^{d} = 1}.

In particular, for d = 1 we get SL_{n+1}(𝔽) and for d = n + 1 we get PGL_{n+1}(𝔽). Note that some properties of these groups are dependent on the field. For example, if 𝔽 is algebraically closed, then PGL_{n+1}(𝔽) = PSL_{n+1}(𝔽) which is simple as an abstract group. In general PGL_{n+1}(𝔽) /PSL_{n+1}(𝔽) ≅ 𝔽^{×}/(𝔽^{×})^{n+1} and PSL_{n+1}(𝔽) may not be algebraic.

5. Arithmetic and data structures

We now describe algorithms for element arithmetic in the group of Lie type G = G_{R}(𝔽). A normal form for elements is a very useful tool for doing computations in a group. In the case of permutation groups, for example, we get a normal form from a base and strong generating set. In our case, we use the Bruhat decomposition [Car72, Corollary 8.4.4]: each g ∈ G, can be expressed uniquely in the form

g = uhẇu′,

where u ∈ U, h ∈ H, w ∈ W, and u′ ∈ U_{w}.

5.1. Actions. The generators of G are of three types: unipotent terms x_{α}(a), Weyl terms n_{α}, and torus terms y ⊗ t. The following equations describe how these generators act on each other, thus allowing us to exchange unipotent, Weyl and torus terms in a word. We also give equations for unipotent terms with negative roots. It is convenient to introduce the notation h_{α}(t) = α^{⋆} ⊗ t.

• The action of the Weyl terms on the maximal torus:

(5.1)  (y ⊗ t)^{n_{α}} = ys_{α}^{⋆} ⊗ t
(5.2)  ^{n_{α}}(y ⊗ t) = ys_{α}^{⋆} ⊗ t

• The action of the Weyl terms on the unipotent subgroup:

(5.3)  x_{β}(a)^{n_{α}} = x_{βs_{α}}(η_{α,β}a)
(5.4)  ^{n_{α}}x_{β}(a) = x_{βs_{α}}(η_{α,β}(−1)^{⟨α,β^{⋆}⟩}a)

• The action of the maximal torus on the unipotent subgroup:

(5.5)  x_{β}(a)^{y⊗t} = x_{β}(t^{⟨β,y⟩}a)
(5.6)  ^{y⊗t}x_{β}(a) = x_{β}(t^{−⟨β,y⟩}a)

• Negative roots:

(5.7)  x_{−α}(t) = x_{α}(t^{−1})n_{α}h_{α}(−t^{−1})x_{α}(t^{−1})
(5.8)  x_{α}(t)n_{α} = x_{−α}(t^{−1})h_{α}(−t^{−1})x_{α}(−t^{−1})

We now discuss computation with torus elements, Weyl group representatives and unipotent elements in turn; before putting it all together in Section 5.5.

5.2. Torus elements. The torus is H = Y ⊗ 𝔽^{×}. Recall that Y has a basis f_{1}, …, f_{d}, so every element of Y ⊗𝔽^{×} can be written uniquely in the form ∏_{i=1}^{d} f_{i}⊗ h_{i} where h_{i} ∈ 𝔽^{×}. This element can be represented on the computer by the vector (h_{1}, …, h_{d}). Multiplication and inversion are just coordinatewise operations.

Given an automorphism of Y whose matrix with respect to f_{1}, …, f_{d} is M, we get an induced automorphism of Y ⊗ 𝔽^{×}

∏_{i=1}^{d} f_{i} ⊗ h_{i} ↦ ∏_{i=1}^{d} (∑_{j=1}^{d} M_{ij}f_{j}) ⊗ h_{i} = ∏_{j=1}^{d} f_{j} ⊗ (∏_{i=1}^{d} h_{i}^{M_{ij}}) .

Using equation (5.1), we can compute the action of n_{α} on a torus element by taking M to be the matrix of s_{α}^{⋆}.

A torus element is in the centre of G if it is of the form ∏_{i=1}^{n} f_{i} ⊗ h_{i} with ∏_{i=1}^{n} h_{i}^{⟨x,f_{i}⟩} = 1 for all x ∈ ℤΦ. This is equivalent to

1 = ∏_{i=1}^{d} h_{i}^{⟨α_{j},f_{i}⟩} = ∏_{i=1}^{d} h_{i}^{A_{ji}}

for j = 1, …, n.

5.3. Weyl group representatives. Recall that the Weyl group W is a Coxeter group and ẇ = n_{β_{1}} ⋯ n_{β_{l}} where w has reduced expression s_{β_{1}} ⋯ s_{β_{l}}. The following equations are useful for computation:

(5.9)  n_{β}^{n_{α}} = n_{βs_{α}}h_{βs_{α}}(η_{α,β}),
(5.10)  n_{α}^{−1} = n_{−α} = h_{α}(−1)n_{α} = n_{α}h_{α}(−1),
(5.11)  n_{α}^{2} = h_{α}(−1).

We compute products by repeated use of the formula

(5.12)  ẇn_{α} = \begin{cases}(ws_{α}). & if α ∉ Φ_{w}, α simple, \\ h_{αw^{−1}}(−1) (ws_{α}). & if α ∈ Φ_{w}, α simple. \end{cases}

The inverse of ẇ is computed as follows, using Lemma 2.1(1):

ẇ^{−1} = ṡ_{β_{l}}^{−1} ⋯ ṡ_{β_{2}}^{−1}ṡ_{β_{1}}^{−1}

= n_{β_{l}}h_{β_{l}}(−1) ⋯ n_{β_{2}}h_{β_{2}}(−1) · n_{β_{1}}h_{β_{1}}(−1)

= (n_{β_{l}} ⋯ n_{β_{1}})h_{β_{l}s_{β_{l−1}} ···s_{β_{1}}} (−1) ⋯ h_{β_{2}s_{β_{1}}} (−1)h_{β_{1}}(−1)

= (w^{−1}). ∏_{α∈Φ_{w^{−1}}} h_{α}(−1).

Note that when α is a nonsimple root, n_{α} = hṡ_{α} where the torus element h can be computed using (5.9) and the fact that s_{α} is conjugate to a simple reflection of W.

5.4. The unipotent subgroup. The unipotent subgroup U is generated by the elements x_{α}(a) for α a positive root and a ∈ 𝔽. It is shown in [Car72] that every element of U can be written uniquely in the form ∏_{α∈Φ^{+}} x_{α}(a_{α}) where the product is in the order described in Section 2.3. This proof is constructive and proceeds by collection using the commutator formulas (4.6) and (4.5). Computationally we use collection from the left to put a unipotent element into this normal form. This is generally the most efficient known collection algorithm [LGS90] and our testing indicates that it is most efficient in this case as well. We invert a unipotent element by reversing the order of the terms and replacing the field elements by their negatives, then doing collection to put the terms back in the right order.

Given a Weyl group element w, [Car72] proves that we can collect any unipotent element into the form

(5.13)  ∏_{α∈Φ^{+}\Φ_{w}} x_{α}(a_{α}) · ∏_{α∈Φ_{w}} x_{α}(a_{α}).

Note that ∏_{α∈Φ_{w}} x_{α}(a_{α}) is a general element of the subgroup U_{w}. This is used to normalise an element of the form uhẇu′ with u′ in U but not necessarily in U_{w}: put u′ in the form (5.13), then exchange the first part with hẇ using (5.3) and (5.5) and multiply u by the result.

Finally note that we can easily collect all terms corresponding to a fixed root α, so every unipotent element can be put in the form

(5.14)  x_{α}(a) · u′ where no term of the form x_{α}(a′) appears in u′.

begin write u′ in the form x_{α}(t) · u′ of (5.14) uhẇx_{α}(t)u′n_{α} exchange n_{α} and u′ by (5.3) uhẇx_{α}(t)n_{α}u′ if t ≠ 0 and α ∈ Φ_{w} (i.e. gn_{α} ∈ BẇB) then

apply (5.8) to x_{α}(t)n_{α} uhẇx_{−α}(t^{−1})h_{α}(−t^{−1})x_{α}(−t^{−1})u′ replace u′ by x_{α}(−t^{−1})u′ uhẇx_{−α}(t^{−1})h_{α}(−t^{−1})u′ exchange x_{−α}(−t^{−1}) with hẇ by (5.4) and (5.6)

and multiply u by the result uhẇh_{α}(−t^{−1})u′ exchange h_{α}(−t^{−1}) with ẇ by (5.2)

and multiply h by the result uhẇu′ else (gn_{α} ∈ Bẇn_{α}B)

if t ≠ 0 then

exchange x_{α}(t) with hẇ by (5.4) and (5.6)

and multiply u by the result uhẇn_{α}u′ end if multiply w by s_{α} if α ∈ Φ_{w} then

multiply h by h_{αw^{−1}}(−1) in accordance with (5.12) end if uhẇu′

end if end

Algorithm 3. Multiplication by a Weyl term

5.5. Normalisation and arithmetic. Recall that we can exchange unipotent, Weyl and torus terms in a word using the equations in Section 5.1. Our goal is to efficiently use these equations to put a word into Bruhat normal form. It suffices to give an algorithm for normalising the product of a normalised element by a unipotent element, torus element or Weyl term. Note that we assume that all the terms x_{α}(t) which appear in our word have α positive—any negative roots that appear in the original word can be eliminated with equation (5.7). Much of the difficulty in this algorithm is ensuring that the roots remain positive when we exchange unipotent terms with Weyl terms.

Suppose g = uhẇu′ is in normal form. To multiply g by a torus element, exchange the torus element with ẇu′ using (5.5) and (5.2), then multiply h by the result. To multiply g by a unipotent element, multiply u′ by the unipotent element and normalise uhẇu′ as in the previous subsection.

Finally consider the more complicated case of multiplication by a Weyl term n_{α}. Recall that

gn_{α} = uhẇu′n_{α} ∈ BẇBn_{α} ⊆ Bẇn_{α}B ∪ BẇB,

where the union is disjoint. This gives us the two main cases of Algorithm 3. In order to clarify the pseudocode we write the word we are working on to the right, but note that the values of the symbols u, h, w and u′ change from line to line.

It is now easy to normalise the product of two normalised words. We invert a normalised word by inverting each term and reversing their order, then swapping h and ẇ and normalising the unipotent parts as in Section 5.4. We can do conjugation more efficiently using the formulas of Section 5.1 directly rather than computing the product y^{−1}xy, but the result still needs to be normalised. Commutators are computed with one inversion, one conjugation, and one multiplication: [x, y] = x^{−1} · x^{y}.

Note that the most time consuming part of these arithmetic operations is collecting unipotent elements. Collection is also the only part of this algorithm which is not known to run in polynomial time. In Section 8.1, we show that there is a provably polynomial time alternative to collection, which nevertheless seems to be slower in practice.

6. Computing linear representations

Computing an irreducible highest weight representation for a group of Lie type is fairly straightforward since the representations for semisimple Lie algebras can already be computed by the algorithm of [dG01]. Let G be a group of Lie type, so the derived group G′ is a semisimple group. Let L be the integral Lie algebra corresponding to G′ and let ρ : L → 𝔤𝔩(V) be the irreducible highest weight representation on the free ℤ-module V with highest weight λ ∈ X. We define x_{α}(T) as exp(T ρ(e_{α})) ∈ End_{ℤ[T]}(V), where T is an indeterminate. The matrix for x_{α}(a) for a ∈ 𝔽 is simply gotten by substitution; this acts on the 𝔽-vector space V ⊗_{ℤ} 𝔽. We also need matrices for the elements of the torus Y ⊗ 𝔽^{×} which are not contained in ℤΦ^{⋆} ⊗ 𝔽^{×}—this requires a linear algebra calculation the details of which we omit.

This algorithm runs in polynomial time in the coefficients of λ for a fixed group G. It is not possible for the algorithm to be polynomial in the rank of G and the coefficients of λ, since the dimension of the irreducible highest weight module is not polynomial in these parameters.

The efficiency of this computation can be improved by noticing that the matrices corresponding to terms in the Steinberg presentation are sparse. So rather than multiplying on the left or right by the matrices, we use the corresponding row or column operations. This observation motivates the algorithm of the next section.

7. Generalised row and column reduction

We now consider the converse problem of converting from a representation to the Steinberg presentation. Together with the previous section, this allows us to transfer between representations and the Steinberg presentation, so we can use whichever is most appropriate for the computation at hand.

Our algorithm is a generalisation of row and column reduction or, more specifically, the LUP algorithm. It works for any nontrivial quotient of a highest weight representation. In many cases it can be extended to an arbitrary representation: First note that we can reduce to the case of an irreducible representation by working our way down a composition series of the module. If 𝔽 is algebraically closed or finite, then every irreducible module is a quotient of a highest weight module.

We assume that G is a group of Lie type G_{R}(𝔽) and that ρ : G → GL(V) is a nontrivial quotient of a highest weight representation on the 𝔽-space V. We consider V to be a G-module by vg := vρ(g). Let A be a matrix in GL(V); to simplify our exposition we assume that A ∈ ρ(G) (in fact, our algorithm is easily converted into a membership test for ρ(G), see Theorem 8.1). Our aim is to find g ∈ G so that A = ρ(g), where g is given as a word in Bruhat normal form.

7.1. The case of SL_{2}(α). Given a root α, define SL_{2}(α) to be the subgroup of G generated by the elements x_{α}(a) and x_{−α}(a) for all a ∈ 𝔽. This subgroup is isomorphic to a nontrivial quotient of SL_{2}(𝔽). We define a (projective linear) action of SL_{2}(α) on the polynomial algebra 𝔽[x, y] by

\begin{matrix}x_{α}(a) : & x ↦ x, & y ↦ ax + y; \\ x_{−α}(a) : & x ↦ x + ay, & y ↦ y; \\ n_{α} : & x ↦ −y, & y ↦ x; \\ h_{α}(t) : & x ↦ tx, & y ↦ t^{−1}y. \end{matrix}

The highest weight module for SL_{2}(α) of weight m is just the submodule of 𝔽[x, y] consisting of homogeneous polynomials of degree m; we denote this module by V (m). Note that, since SL_{2}(α) is a quotient of SL_{2}(𝔽), this may be a projective representation—for our purposes however this is not a problem. If 𝔽 has characteristic 0, V (m) is irreducible. If 𝔽 has characteristic p, then we get an irreducible module by quotienting out the submodule spanned by the terms x^{i}y^{m−i} for which p divides \binom{m}{i}.

Every irreducible SL_{2}(α)-module M is isomorphic to a nontrivial quotient of V (m) for some m. Suppose we are given such a module M, we now show how to compute the value of m. Let v be a nonzero fixed vector of x_{α}(1). Then v can be considered to be the image of x^{m} and we can compute m with the formula vh_{α}(t) = t^{m}v. If 𝔽 is finite of size q, then we can assume that m < q by the Steinberg tensor product theorem [Ste63] and so m is the smallest positive integer satisfying this formula for t a primitive element of 𝔽. We also know that (−1)^{m}vn_{α} is the image of y^{m} and the images of the subspaces 𝔽x^{i}y^{m−i} are found by taking eigenspaces of h_{α}(t). Hence we can compute an inner product ▪ on V so that these one-dimensional subspaces are orthogonal, and v and vn_{α} have norm one.

Given a matrix A ∈ GL(V), we want to find a, b ∈ 𝔽, t ∈ 𝔽^{×} and w ∈ W = {1, s_{α}} such that A = ρ(x_{α}(a)h_{α}(t)ẇx_{α}(b)). By an easy computation, we get

x^{m}g ▪ y^{m} = (−t)^{m}, x^{m}g ▪ x^{m} = (−bt)^{m};
x^{m}h ▪ y^{m} = 0,  x^{m}h ▪ x^{m} = t^{m},  y^{m}h ▪ x^{m} = (at)^{m};

where g = x_{α}(a)h_{α}(t)n_{α}x_{α}(b) and h = x_{α}(a)h_{α}(t). Hence we have Algorithm 4, using the fact that v is the image of x^{m} and (−1)^{m}vn_{α} is the image of y^{m}.

7.2. Computing weights and weight spaces. Given μ ∈ X, we define

V_{μ} = {v ∈ V | v(y ⊗ t) = t^{⟨μ,y⟩}v for all y ∈ Y, t ∈ 𝔽^{×}}.

Then V = ⨁_{μ} V_{μ} and we call μ a weight of V if V_{μ} is nontrivial. The dominance order for weights is defined by μ ⪯ ν if ν − μ = ∑_{i=1}^{n} m_{i}α_{i} where every m_{i} ≥ 0; we write μ ≺ ν when μ ⪯ ν and μ ≠ ν. Since V is a nontrivial quotient of a highest weight representation, it has a dominance-highest weight λ and V_{λ} is one dimensional. In many applications, λ and V_{λ} are assumed to be known. However they can be computed if necessary: V_{λ} is the intersection of the fixed spaces of the matrices ρ(x_{α}(1)) for α a simple root. The highest weight can be computed using the formula λ = ∑_{i=1}^{n}⟨λ, α_{i}^{⋆}⟩ω_{i}, and the fact that the SL_{2}(α_{i})-submodule generated by V_{λ} is a nontrivial quotient of V (m) with m = ⟨λ, α_{i}^{⋆}⟩. begin

if vA ▪ vn_{α} ≠ 0 then let w = s_{α} let c = (−1)^{m}(vA ▪ v)(vA ▪ vn_{α})^{−1} take b to be the mth root of c for which vn_{α}Ax_{α}(b)^{−1} ▪ vn_{α} = 0 let A = Aρ(n_{α}x_{α}(b))^{−1}

else

let w = 1, b = 0 end if let c = (−1)^{m}(vn_{α}A ▪ v)(vA ▪ v)^{−1} take a to be the mth root of c for which vn_{α}x_{α}(a)^{−1}A ▪ v = 0 let A = ρ(x_{α}(a))^{−1}A take t to be the mth root of vA ▪ v for which A = ρ(h_{α}(t)) return g = x_{α}(a)h_{α}(t)ẇx_{α}(b)

end

Algorithm 4. The SL_{2}(α) algorithm

We frequently use the following basic facts about the action of G on V:

(7.1)  V_{μ}x_{α}(t) ⊆ ⨁_{ν⪰μ} V_{ν} for α ∈ Φ^{+},
(7.2)  V_{μ}ẇ = V_{μw},
(7.3)  V_{μ}H = V_{μ}.

Fix a nonzero vector v_{λ} in V_{λ}. Write Ω for the orbit of λ under the action of W; for each μ ∈ Ω, choose some w ∈ W so that μ = λw and fix v_{μ} = v_{λ}ẇ. Note that V_{μ} = 𝔽v_{μ} and v_{μ} is well defined up to a sign. We can compute V_{μ} for a weight μ ∉ Ω by taking eigenspaces of torus elements. This allows us to compute a bilinear form ▪ on V for which the vectors v_{μ} for μ ∈ Ω are orthonormal, and ∑_{μ∉Ω} V_{μ} is contained in the radical.

By Theorem 29 of [Ste68], there is an automorphism of G such that

x_{α}(a) ↦ x_{−α}(ε_{α}a),  (y ⊗ t) ↦ y ⊗ t^{−1}

provided the signs ε_{α} satisfying the equation

ε_{α}ε_{β} = −ε_{α+β} (7.4)

whenever α + β is a root. We can now define an antiautomorphism δ on G by composition of inversion in G with the above automorphism, so that

x_{α}(a)^{δ} = x_{−α}(ε_{α}a)^{−1} = x_{−α}(−ε_{α}t),  (y ⊗ t)^{δ} = y ⊗ t.

We want the additional property that δ^{2} = 1, which is true if and only if

ε_{−α} = ε_{α} (7.5)

for every root α. It is easily shown that Hẇ^{δ} = Hẇ^{−1}. We take all ε_{α} = −1: clearly (7.4) is satisfied, so δ is an antiautomorphism, and (7.5) is satisfied, so it is an involution.

We define a left action of G on V by gv = vg^{δ}; we wish to show that this has the property that

ug ▪ v = u ▪ gv.

It suffices to take u and v of the form v_{μ} with μ ∈ Ω, since ∑_{σ∉Ω} V_{σ} is in the radical. Furthermore, it suffices to take g to be a generator; either a torus term or a unipotent term. For a torus term g = y ⊗ t, both sides are zero unless u = v = v_{μ} and v_{μ}(y ⊗ t) ▪ v_{μ} = t^{⟨μ,y⟩} = v_{μ} ▪ v_{μ}(y ⊗ t)^{δ}. For a unipotent term g = x_{α}(a), both sides are zero unless u = v = v_{μ}, or u = v_{μ} and v = v_{ν} with ν = μs_{α}. As in Section 7.1, the SL_{2}(α)-module generated by v_{μ} can be identified with a quotient of V (m) with m = ⟨ μ, α^{⋆} ⟩. The vector v_{μ} is identified with x^{m}, and v_{ν}n_{α} = ev_{μ} (e = ±1) is identified with y^{m}. Now

v_{μ}x_{α}(a) = e(v_{ν}n_{α})x_{α}(a)

= ey^{m}x_{α}(a)

= e(y + ax)^{m} ∈ v_{μ} + ea^{m}v_{ν} + ∑_{σ∉Ω} V_{σ} and

v_{ν}x_{α}(a)^{δ} = x^{m}x_{−α}(a)

= (x + ay)^{m} ∈ v_{ν} + ea^{m}v_{μ} + ∑_{σ∉Ω} V_{σ}.

Consequently, if u = v = v_{μ} then

ug ▪ v = v_{μ}x_{α}(a) ▪ v_{μ} = 1 = v_{μ} ▪ v_{μ}x_{α}(a) = u ▪ vg^{δ} = u ▪ gv,

and if u = v_{μ} and v = v_{ν} then

ug ▪ v = v_{μ}x_{α}(a) ▪ v_{ν} = ea^{m} = v_{μ} ▪ v_{ν}x_{α}(a) = u ▪ vg^{δ} = u ▪ gv,

so we are done.

7.3. The inductive step. In this section we show how to reduce from G to a reductive subgroup of smaller semisimple rank.

Since λ is a dominant weight, its stabiliser W_{λ} is actually the standard parabolic subgroup W_{J} with J = {s | ⟨λ, α_{s}^{⋆}⟩ = 0}. Within G we have opposite parabolic subgroups P_{J} = BẆ_{J}B and P_{J}^{δ} = B^{δ}Ẇ_{J}B^{δ}. The Levi complement L_{J} = P_{J} ∩ P_{J}^{δ} is reductive with root datum (X, Φ_{λ}, Y, Φ_{λ}^{⋆}), where

Φ_{λ} = {α ∈ Φ | ⟨λ, α^{⋆}⟩ = 0} = Φ_{J}

and Φ_{λ}^{⋆} = {α^{⋆} | α ∈ Φ_{λ}}. In particular, the semisimple rank of L_{J} is strictly smaller than the semisimple rank of G and the Weyl group of L_{J} is W_{J} = W_{λ}.

Proposition 7.1. Let g be an element of G. Then g ∈ L_{J} if, and only if, V_{λ}g = V_{λ} and gV_{λ} = V_{λ}.

Proof. First we show that g ∈ P_{J} if, and only if, V_{λ}g = V_{λ}. Since λ is the highest weight, V_{λ}B = V_{λ} and so V_{λ}BẇB = V_{λw}B = ∑_{μ⪰λw} V_{μ} by (7.1) and (7.3). Clearly this is equal to V_{λ} exactly when λw = λ, i.e. w ∈ W_{J}.

On the other hand, gV_{λ} = V_{λ} means V_{λ}g^{δ} = V_{λ} which is equivalent to g^{δ} ∈ P_{J}, i.e., g ∈ P_{J}^{δ}. Since L_{J} = P_{J} ∩ P_{J}^{δ}, we are done. □

Any element w of W can be decomposed in the form w_{J}w^{J} where w_{J} ∈ W_{J} and w^{J} is the unique W_{J}-reduced element of W such that λw^{J} = λw. We write W^{J} for the set of all W_{J}-reduced elements of W. By Lemma 2.1(2), Φ_{w} is a disjoint union of Φ_{w_{J}} w^{J} and Φ_{w^{J}}, and so we get a unique decomposition U_{w} = (U_{w_{J}})^{˙w^{J}} U_{w^{J}}. We are particularly interested in the factorisation w_{0} = w_{0J}w_{0}^{J} of the longest word in W. Now w_{0J} is the longest word of W_{J}. Since w_{0J} = w_{0}(w_{0}^{J})^{−1}, Lemma 2.1(4) implies that Φ^{+} is the disjoint union of Φ_{(w_{0}^{J})^{−1}} and Φ_{w_{0J}} so we get a unique decomposition U = U_{(w_{0}^{J})^{−1}}U_{w_{0J}}. We can now modify the Bruhat decomposition as follows:

G = ⋃_{w∈W} UHẇU_{w}

= ⋃_{w_{J} ∈W_{J} ,w^{J} ∈W^{J}} U_{(w_{0}^{J})^{−1}}U_{w_{0J}} Hẇ_{J}ẇ^{J}U_{w_{J}}^{˙w^{J}} U_{w^{J}}

= ⋃_{w^{J} ∈W^{J}} U_{(w_{0}^{J})^{−1}} ( ⋃_{w_{J} ∈W_{J}} U_{w_{0J}} Hẇ_{J}U_{w_{J}} ) ẇ^{J}U_{w^{J}}

= ⋃_{w^{J} ∈W^{J}} U_{(w_{0}^{J})^{−1}}L_{J}ẇ^{J}U_{w^{J}} .

Recall that we are given an element A ∈ ρ(G) and we wish to find a preimage g ∈ G. The first step is to find the value of w^{J} in this decomposition of g; then we can find u ∈ U_{(w_{0}^{J})^{−1}} and u′ ∈ U_{w^{J}} so that A ∈ ρ(uL_{J}ẇ^{J}u′). The problem is then reduced to finding a word for ρ(u)^{−1}Aρ(ẇ^{J}u′)^{−1} in the reductive subgroup L_{J}.

Since w^{J} is the unique W_{J}-reduced element of W with λw^{J} = λw, it can be found using the following lemma.

Lemma 7.2. Let g be an element of the double coset BẇB of G. If μ is the minimal element of Ω such that v_{λ}g ▪ v_{μ} ≠ 0, then λw = μ.

Proof. This follows from the facts that V_{λ}BẇB ⊆ ∑_{μ⪰λw} V_{μ} and v_{λ}g ▪v_{λw} ≠ 0. □

We now know that A = ρ(g) with g ∈ U_{(w_{0}^{J})^{−1}}L_{J}ẇ^{J}U_{w^{J}} for fixed w^{J}. Write g = uhẇ^{J}u′ where u ∈ U_{(w_{0}^{J})^{−1}}, h ∈ L_{J}, and u′ = ∏_{α∈Φ_{w^{J}}} x_{α}(a_{α}) ∈ U_{w^{J}}. Let γ be a dominance minimal root in Φ_{w^{J}} with a_{γ} ≠ 0. Using (5.14) we can rewrite u′ in the form ( ∏_{α∈Φ_{w^{J}} ,α⪯̸γ} x_{α}(a_{α}))x_{γ}(a_{γ}), with different values a_{α} but a_{γ} still nonzero. As in Section 7.1, the SL_{2}(γ)-module generated by v_{μ} can be identified with a quotient of V (m) with m = −⟨ μ, γ^{⋆} ⟩, the vector v_{μ} with the image of y^{m}, and v_{λ}n_{μ} with the image of x^{m}. Now

v_{λ}A = v_{λ}g = v_{λ}uhẇ^{J}u′ = v_{λ}hẇ^{J}u′

∈ 𝔽^{×}v_{μ}u′

= 𝔽^{×}v_{μ} ( ∏_{α∈Φ_{w^{J}} ,α⪯̸γ} x_{α}(a_{α})) x_{γ}(a_{γ})

⊆ 𝔽^{×} (v_{μ} + ∑_{ξ∈ℤ_{≥0}Φ_{w^{J}} \0} V_{μ+ξ}) x_{γ}(a_{γ})

⊆ 𝔽^{×}(a_{γ}^{m}v_{μ}n_{γ} + ma_{γ}^{m−1}x^{m−1}y + ⋯ + v_{μ}) + ∑_{ν⪯̸μs_{γ}} V_{ν}

The final line follows from the fact that the only weights that can appear are of the form ν = μ + ξ − iγ where i = 0, …, m and ξ is a nonzero linear combination of roots α ∈ Φ_{w^{J}}, α ⪯̸ γ with nonnegative coefficients. Such weights satisfy ν ⪯̸ μ − mγ = μs_{γ}. We can now compute a_{γ} by setting

c = (v_{λ}A ▪ v_{μ}n_{γ})(v_{λ}A ▪ v_{μ})^{−1},

and taking a_{γ} to be the mth root of c with the property that v_{λ}Ax_{γ}(a_{γ})^{−1}▪v_{μ}n_{γ} = 0. By repeating this process for all the roots in Φ_{w^{J}} in an order compatible with the dominance order, we can compute the value of u′. The order < of Section 2.3 has the required property.

We now have g = uhẇ^{J} and we wish to find u ∈ U_{(w_{0}^{J})^{−1}}. This is similar to the preceding case. We may write u = x_{γ}(b_{γ}) ∏_{β∈Φ_{(w^{J}_{0} )^{−1}} ,β⪰̸γ} x_{β}(b_{β}) and then

Av_{μ} = gv_{μ} = uhẇ^{J}v_{μ}

∈ 𝔽^{×}uv_{λ} = 𝔽^{×}v_{λ}u^{δ}

= 𝔽^{×}v_{λ} ( ∏_{β∈Φ_{w^{J}} ,α⪰̸γ} x_{−β}(b_{β})) x_{−γ}(b_{γ})

⊆ 𝔽^{×}(v_{λ} + ⋯ + b_{γ}^{m}v_{λ}n_{γ}) + ∑_{ν⪰̸μs_{γ}} V_{ν}

where m = ⟨λ, γ^{⋆}⟩. Hence we compute b_{γ} by taking

c = (v_{λ}n_{γ} ▪ Av_{μ})(v_{λ} ▪ Av_{μ})^{−1},

and computing the mth root b_{γ} of c such that v_{λ}n_{γ} ▪ x_{γ}(b_{γ})^{−1}Av_{μ} = 0.

We now have all the ingredients required for our algorithm, which we describe in detail in the next two sections.

7.4. A base for the Weyl group. By iterating the procedure of the previous section, we get a sequence of reductive subgroups

G = L_{J_{1}} ≥ L_{J_{2}} ≥ ⋯ ≥ L_{J_{k+1}} = H

where

{1, …, n} = J_{1} ⊇ J_{2} ⊇ ⋯ ⊇ J_{k+1} = ∅.

begin let λ_{1} = λ, J_{1} = {1, …, n}, J_{2} = {s ∈ J_{1} | ⟨λ_{1}, α_{s}^{⋆}⟩ = 0} let i = 2 while J_{i} is not empty

choose r ∈ J_{i−1} − J_{i} such that {s ∈ J_{i} | ⟨λ_{i−1}s_{α_{r}}, α_{s}^{⋆}⟩ = 0} ⊊ J_{i} let λ_{i} = λ_{i−1}s_{α_{r}}, and J_{i+1} = {s ∈ J_{i} | ⟨α_{r}, α_{s}^{⋆}⟩ = 0} increment i by 1

end while end

Algorithm 5. Computing a base of weights

Note that this chain of subgroups depends only on G, not on the particular matrix A. The subsets J_{i} and the highest weight for each L_{J_{i}} can be computed beforehand using the following theorem.

Theorem 7.3. Let G be a reductive group with highest weight representation V. Consider the Weyl group as a permutation group on the weights in Ω. Then W has a base λ_{1}, …, λ_{k} with the following properties:

(1) W_{λ_{1},...,λ_{i−1}} = W_{J_{i}} for some J_{i} ⊆ {1, …, n}; and

(2) λ_{i} is a highest weight for L_{J_{i}} = BẆ_{J_{i}}B acting on V.

Proof. We begin by putting λ_{1} = λ, J_{1} = {1, 2, …, n} and J_{2} = { s ∈ J_{1} | ⟨ λ_{1}, α_{s}^{⋆} ⟩ = 0 }. and we proceed by induction on i. Given λ_{1}, λ_{2}, …, λ_{i−1} and J_{1}, J_{2}, …, J_{i} satisfying (1) and (2) with J_{i} ≠ ∅ we find r ∉ J_{i} such that ⟨ λ_{i−1}s_{α_{r}}, α_{s}^{⋆} ⟩ ≠ 0 for some s ∈ J_{i}. Put λ_{i} = λ_{i−1}s_{α_{r}}. Then for all s ∈ J_{i} we have

⟨ λ_{i}, α_{s}^{⋆} ⟩ = ⟨ λ_{i−1}s_{α_{r}}, α_{s}^{⋆} ⟩
= ⟨ λ_{i−1} − ⟨ λ_{i−1}, α_{r}^{⋆} ⟩α_{r}, α_{s}^{⋆} ⟩
= −⟨ λ_{i−1}, α_{r}^{⋆} ⟩⟨ α_{r}, α_{s}^{⋆} ⟩ ≥ 0.

Thus J_{i+1} = { s ∈ J_{i} | ⟨ α_{r}, α_{s}^{⋆} ⟩ = 0 } = W_{λ_{1},...,λ_{i}} and λ_{i} satisfy (1) and (2). □

The weights λ_{i} and sets J_{i} are constructed using Algorithm 5. Suppose that w is an element of the Weyl group W. Then we have a unique factorisation w = w_{k} ⋯ w_{2}w_{1} where w_{i} is the unique W_{J_{i+1}}-reduced element of W_{J_{i}} such that λ_{i}w_{i} = λ_{i}ww_{1}^{−1} ⋯ w_{i−1}^{−1}. The element w_{0i} is fixed for a particular group G, and is the unique W_{J_{i+1}}-reduced element of W_{J_{i}} such that λ_{i}w_{0i}^{−1} = λ_{i}w_{0J_{i}}. Iterating the result in the previous subsection, we can now refine the Bruhat decomposition to

⋃_{w_{1},...,w_{k}} U_{w_{01}} U_{w_{02}} ⋯ U_{w_{0k}}Hẇ_{k} ⋯ ẇ_{2}ẇ_{1}(U_{w_{k}})^{ẇ_{k−1}···ẇ_{1}} ⋯ (U_{w_{2}})ẇ_{1} U_{w_{1}}. (7.6)

where w_{j} ranges over the W^{(j+1)}-reduced elements of W^{(j)}.

7.5. Row and column reduction. Putting together the ideas of the previous sections, we get Algorithm 6 (see Section 8.1 for the significance of the asterisks). We assume that λ_{i}, J_{i} and w_{0i} have already been computed using the techniques of Section 7.4. Note that the loop has an invariant ρ(u)Aρ(u′), which is always equal to the original value of A. At the end of this algorithm, A is the image of a torus element. begin

let u, h, u′ = 1.

for i from 1 to k do [Compute w_{i}] find the largest μ ∈ Ω so that v_{i}A ▪ v_{μ} ≠ 0. find the W_{J_{i+1}}-reduced element w_{i} ∈ W_{J_{i}} with λ_{i}w_{i} = μw_{1}^{−1} ⋯ w_{i−1}^{−1} (*) [Compute the component in (U_{w_{i}})^{ẇ_{i−1}···ẇ_{1}}] for β in Φ_{w_{i}}w_{i−1} ⋯ w_{1} in the order of Section 2.3 do let m = ⟨μ, β^{⋆}⟩, c = (v_{λ_{i}}A ▪ v_{μ}n_{β})(v_{λ_{i}}A ▪ v_{μ})^{−1} let b be the mth root of c so that v_{λ_{i}}Ax_{β}(b)^{−1} ▪ v_{μ}n_{β} = 0 (*) let u′ = x_{β}(b)u′, A = Aρ(x_{β}(b))^{−1}

end for

[Compute the component in U_{w_{0i}}]

for α in Φẇ_{0i} in the order of Section 2.3 do let m = ⟨λ_{i}, α^{⋆}⟩, c = (v_{λ_{i}}n_{α} ▪ Av_{μ})(v_{λ_{i}} ▪ Av_{μ})^{−1} let a be the mth root of c so that v_{λ_{i}}n_{α}x_{α}(a)^{−1} ▪ Av_{μ} = 0 (*) let u = ux_{α}(a), A = ρ(x_{α}(a))^{−1}A

end for end for let w = w_{k} ⋯ w_{1}, A = Aρ(ẇ)^{−1}

end

Algorithm 6. Generalised row and column reduction

7.6. Torus elements. We now suppose we have an element A ∈ ρ(H) where H is the torus of our group of Lie type G, and we wish to find h ∈ H so that ρ(h) = A. Note that ρ need not be faithful on H, so h may not be uniquely determined. Let Γ be the lattice generated by the weights of V and choose a basis γ_{1}, …, γ_{t} for Γ. Then the preimage of A in Γ ⊗ 𝔽^{×} is computed as ∏_{i=1}^{t} γ_{i} ⊗ t_{i} where vA = t_{i}v for v ∈ V_{γ_{i}}. This can be converted to the form ∏_{i=1}^{t} f_{i} ⊗ h_{i} using the methods of Section 5.2.

8. Applications and example

The algorithms described in this paper have been implemented in Magma. They are practical for computations in groups of Lie type up to (and sometimes beyond) rank 10. In particular, they are practical for all the exceptional groups. The timings for multiplication in the Steinberg presentation are highly dependent on the efficiency of the field operations. However, it is possible to do computations in E_{8} even for quite difficult fields, such as fields of rational functions. Rational function fields are particularly useful, since a computation with indeterminants allows us to derive general formulas that apply over any field.

Most of the applications of our algorithms are based on the ability to convert in both directions between the Steinberg presentation and a representation. This allows us to work in whichever of the two is most convenient for the problem at hand: in general the Steinberg presentation has the advantage of making the underlying Lie theory explicit, while a representation allows us to use the power of linear algebra. For example conjugacy classes are more easily computed in the presentation; while the Jordan decomposition and lattice subgroups can only be computed in a representation.

8.1. Application to matrix group recognition. One of the more difficult problems in matrix group recognition is finding a membership test for a known almost simple group. Our algorithm provides such a test for natural characteristic representations of finite groups of Lie type. We obtain a membership test for ρ(G) by running our algorithm for an arbitrary A ∈ GL(V): A is not a member of ρ(G) if the algorithm fails or the value of A at the end is not the identity matrix. Algorithm 6 can fail in three places, which are marked by (*). The torus element algorithm of Section 7.6 can also fail.

In this and other applications, it is of interest to determine whether our algorithm runs in polynomial time. When 𝔽 is a finite field of order q, it is straightforward to show that most of the algorithm runs in polynomial time in log(q) and the coefficients of λ. For example, the length k of our base is bounded by the reductive rank of G and radicals over finite fields can be computed in polynomial time by [FGP01]. The main sticking point is the computation of discrete logarithms in Section 7.1. This can be avoided, however, since the powers involved are bounded by m, and by Section 7.3 the values of m which appear are polynomial in the coefficients of λ. We now have the following result.

Theorem 8.1. Let G = G_{R}(𝔽_{q}) be a finite group of Lie type and let ρ : G → GL(V) be a quotient of a highest weight representation with known highest weight λ. Suppose A ∈ GL(V). We can decide whether A is in ρ(G) and, if it is, find a preimage in polynomial time in log(q) and the coefficients of λ.

Note that the condition that the highest weight be known is required, since computing the highest weight requires discrete logarithms. In fact, if G is a one-dimensional torus with representation V, then computing the weight of V is precisely the discrete logarithm problem.

As an immediate corollary of Theorem 8.1, we get a polynomial time algorithm for multiplying elements in G: simply convert the elements to matrices in the natural representation (i.e. the smallest degree highest weight representation), multiply the matrices, then convert back. In the case of the natural representation, the running time of our algorithm is O(n^{3}), just like the LUP algorithm for general linear groups.

8.2. Example: GL_{n+1}(𝔽). We now describe how this algorithm works in the case of the standard representation of the general linear group. Take X = ℤ^{n+1} with standard basis vectors e_{i} and Y = ℤ^{n+1} with standard basis vectors f_{i}. The roots and coroots are of the form α_{ij} = e_{i} − e_{j} and α_{ij}^{⋆} = f_{i} − f_{j} for 1 ≤ i, j ≤ n + 1 with i ≠ j. A (co)root is positive when i > j and simple when i = j + 1.

The standard representation ρ : G → GL_{n+1}(𝔽) takes x_{α_{ij}}(a) to the matrix equal to the identity except for the (i, j)-entry which is equal to a, and f_{i} ⊗ t to the matrix equal to the identity except for the (i, i)-entry which is equal to t. The Weyl group of G is the symmetric group on n + 1 letters with reflections s_{α_{ij}} = (i, j). Here ρ(g^{δ}) is the usual transpose of ρ(g).

Algorithm 5 gives λ_{i} = e_{i} and J_{i} = {i, i + 1, …, n + 1}. Since we can take v_{λ_{i}} = b_{i}, these weights correspond to the rows and columns of the input matrix A.

We can compute

w_{0i} = s_{n} … s_{i+1}s_{i} = (i, i + 1, …, n + 1) and
Φ_{w_{0i}} = {α_{i+1,i}, …, α_{n+1,i}}.

In order to compute w_{i} we need to know the image

λ_{i}w_{i} = μw_{1}^{−1} ⋯ w_{i−1}^{−1}

where μ = e_{j} with j is the largest nonzero entry in the ith row of A. Now

w_{i} = s_{i}s_{i+1} … s_{iw_{i}−1} = (iw_{i}, …, i + 1, i) and
Φ_{w_{i}} = {α_{iw_{i},i}, α_{iw_{i},i+1}, …, α_{iw_{i},iw_{i}−1}}

and so

Φ_{w_{i}}w_{i−1} ⋯ w_{1} = {α_{iw,j} | j = lw_{i−1} ⋯ w_{1} for l = i, i + 1, …, iw_{i} − 1} (8.1)

Furthermore the constants m that appear in Algorithm 6 are all equal to 1. It is now easily seen that computing the U_{w_{0i}} component of (7.6) is just clearing the (iw_{i−1} ⋯ w_{1})th column of the matrix with row operations, and computing the (U_{w_{i}})^{ẇ_{i−1}···ẇ_{1}} component is just clearing the ith row of the matrix with column operations (the values of j that appear in (8.1) give exactly the entries in the row that have not been cleared by a previous column operation).

In order to relate this algorithm to the well-known LUP algorithm, we note that ρ can be chosen so that ρ(B) consists of lower triangular matrices. Suppose that g ∈ G decomposes as uhẇu′ for u ∈ U, h ∈ H, w ∈ W and u′ ∈ U_{w}. Then L = ρ(uh) is lower triangular, U = ρ(ẇu′ẇ^{−1}) is upper triangular, and P = ρ(ẇ) is a permutation matrix (up to signs), giving the usual LUP decomposition.

References

[AB95] J. L. Alperin and Rowen B. Bell, Groups and representations, Springer-Verlag, New York, 1995.

[BC97] W. W. Bosma and J. J. Cannon, Handbook of magma functions, School of Mathematics and Statistics, University of Sydney, Sydney, 1997.

[BGK^{+}97] L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks, and P. P. Pálfy, Short presen-

tations for finite groups, J. Algebra 194 (1997), no. 1, 79–112.

[Bou81] Nicolas Bourbaki, Éléments de mathématique, Masson, Paris, 1981, Groupes et algèbres de Lie. Chapitres 4, 5 et 6. [Lie groups and Lie algebras. Chapters 4, 5 and 6].

[But91] G. Butler, Fundamental algorithms for permutation groups, Springer-Verlag, Berlin, 1991.

[Car72] Roger W. Carter, Simple groups of Lie type, John Wiley & Sons, London-New York-Sydney, 1972, Pure and Applied Mathematics, Vol. 28.

[Car93] Roger W. Carter, Finite groups of Lie type, John Wiley & Sons Ltd., Chichester, 1993, Conjugacy classes and complex characters, Reprint of the 1985 original, A Wiley-Interscience Publication.

[Dem65] M. Demazure, Données radicielles, Schémas en Groupes (Sém. Géométrie Algébrique, Inst. Hautes Études Sci., 1964), Fasc. 6, Exposé 21, Inst. Hautes Études Sci., Paris, 1965.

[dG00] Willem A. de Graaf, Lie algebras: theory and algorithms, North-Holland Publishing Co., Amsterdam, 2000.

[dG01] W. A. de Graaf, Constructing representations of split semisimple Lie algebras, J. Pure Appl. Algebra 164 (2001), no. 1-2, 87–107, Effective methods in algebraic geometry (Bath, 2000).

[FGP01] P. Flajolet, X. Gourdon, and D. Panario, The complete analysis of a polynomial factorization algorithm over finite fields, J. Algorithms 40 (2001), no. 1, 37–81.

[FK81] I. B. Frenkel and V. G. Kac, Basic representations of affine Lie algebras and dual resonance models, Invent. Math. 62 (1980/81), no. 1, 23–66.

[GAP99] The GAP Group, Aachen, St Andrews, GAP – Groups, Algorithms, and Program-

ming, Version 4.1, 1999, (http://www.gap-system.org).

[GHL^{+}96] Meinolf Geck, Gerhard Hiss, Frank Lübeck, Gunter Malle, and Götz Pfeiffer, CHEVIE—a system for computing and processing generic character tables, Appl. Algebra Engrg. Comm. Comput. 7 (1996), no. 3, 175–210, Computational methods in Lie theory (Essen, 1994).

[GS88] Peter B. Gilkey and Gary M. Seitz, Some representations of exceptional Lie algebras, Geom. Dedicata 25 (1988), no. 1-3, 407–416, Geometries and groups (Noordwijkerhout, 1986).

[Hal00] Sergei Haller, Unipot—a system for computing with elements of unipotent subgroups of Chevalley groups, version 1.1, Tech. report, Justus-Liebig Universität, Germany,

July 2000, http://www.gap-system.org/Info4/deposit.html#pkg.

[HRT01] R. B. Howlett, L. J. Rylands, and D. E. Taylor, Matrix generators for exceptional groups of Lie type, J. Symbolic Comput. 31 (2001), no. 4, 429–445.

[HS01] Alexander Hulpke and Ákos Seress, Short presentations for three-dimensional unitary groups, J. Algebra 245 (2001), no. 2, 719–729.

[KS01] William M. Kantor and Ákos Seress, Black box classical groups, Mem. Amer. Math. Soc. 149 (2001), no. 708, viii+168.

[LG01] Charles R. Leedham-Green, The computational matrix group project, Groups and computation, III (Columbus, OH, 1999), de Gruyter, Berlin, 2001, pp. 229–247.

[LGS90] C. R. Leedham-Green and L. H. Soicher, Collection from the left and other strategies, J. Symbolic Comput. 9 (1990), no. 5-6, 665–675, Computational group theory, Part 1.

[LS87] Martin W. Liebeck and Jan Saxl, On the orders of maximal subgroups of the finite exceptional groups of Lie type, Proc. London Math. Soc. (3) 55 (1987), no. 2, 299–330.

[Rie98] R. J. Riebeek, Computations in association schemes, Ph.D. thesis, Eindhoven University of Technology, 1998.

[Ryl01] L. J. Rylands, A formula for signs of structure constants, Unpublished, 2001.

[Sim94] Charles C. Sims, Computation with finitely presented groups, Cambridge University Press, Cambridge, 1994.

[Spr98] T. A. Springer, Linear algebraic groups, second ed., Birkhäuser Boston Inc., Boston, MA, 1998.

[Ste62] Robert Steinberg, Générateurs, relations et revêtements de groupes algébriques, Colloq. Théorie des Groupes Algébriques (Bruxelles, 1962), Librairie Universitaire, Louvain, 1962, pp. 113–127.

[Ste63] Robert Steinberg, Representations of algebraic groups, Nagoya Math. J. 22 (1963), 33–56.

[Ste68] R. Steinberg, Lectures on Chevalley groups, Tech. report, Yale University, 1968.

[vLCL92] M. A. A. van Leeuwen, A. M. Cohen, and B. Lisser, LiE manual, CWI/CAN, Amsterdam, 1992, Manual for the software package LiE for Lie group theoretical compu-

tations. http://young.sp2mi.univ-poitiers.fr/ marc/LiE/.

Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands

E-mail address: A.M.Cohen@tue.nl

Department of Mathematics and Statistics, University of Sydney, Sydney, NSW 2006, Australia

E-mail address: murray@maths.usyd.edu.au

Department of Mathematics and Statistics, University of Sydney, Sydney, NSW 2006, Australia

E-mail address: D.Taylor@maths.usyd.edu.au