Séminaire Lotharingien de Combinatoire, B39e(1997), 26pp.

An Algorithm for the Decomposition of Ideals of the Group Ring of a Symmetric Group

B. Fiedler Institut für Informatik, Universität Leipzig Augustusplatz 10/11, D-04109 Leipzig email: fiedler@rz.uni-leipzig.de

Abstract

We present an algorithm which produces a decomposition of left or right ideals of the group ring of a symmetric group into minimal left or right ideals and a corresponding set of primitive pairwise orthogonal idempotents by means of a computer. The algorithm can be used to determine generating idempotents of (left or right) ideals which are given as sums or intersections of (left or right) ideals.

We discuss several subjects such as minimal sets of test permutations and the application of fast Fourier transforms which contribute to a good efficiency of the algorithm. Further we show possibilities of use of the algorithm in the computer algebra of tensor expressions.

1 Introduction

Let ℂ[S_{r}] be the group ring of a symmetric group S_{r} over the field of complex numbers ℂ. In this paper we present a computer algorithm which can produce a decomposition of an arbitrary left ideal I := ℂ[S_{r}] · a of ℂ[S_{r}] with given generating element a ∈ ℂ[S_{r}] into a direct sum of minimal left ideals

I = ⨁_{j=1}^{l} I_{j}  (1)

and which moreover yields a generating idempotent e of I and a system of orthogonal primitive idempotents e_{j} corresponding to this decomposition (1):

e = ∑_{j=1}^{l} e_{j} , e_{j} ∈ I_{j} , I = ℂ[S_{r}] · e .  (2)

We have described already the basic ideas of this algorithm in [6]. We complete the version of the algorithm from [6] by some considerations about possibilities of the improvement of the efficiency of the algorithm. Such possibilities are the construction of minimal sets of test permutations which are used by our algorithm (section 4) and the application of fast Fourier transforms for symmetric groups (section 5) realized by the fast algorithms of Clausen and Baum [4, 3].

In section 3 we consider left ideals for which a generating element is not known, for instance intersections of left ideals and non-direct sums of left ideals. The algorithm can be used to construct a generating idempotent for such an ideal. Of course, a version of the algorithm for right ideals can be formed, too.

A special reason to develop our decomposition algorithm comes for us from the computer algebra of tensor expressions which aims to do conversions of tensor expressions according to the rules of the Ricci calculus by means of a computer algebra system. Symbolic calculations with tensor expressions require effective methods of the determination of normal forms of tensors and of the investigation of tensor symmetries.

The connection between tensors and the representation theory of symmetric groups is well-known [17, 10, 1, 2]. A very informative paper is [7] which demonstrates the application of important tools of the representation theory such as the Littlewood-Richardson rule and plethysms to the construction of normal form expressions for polynomial terms in the coordinates of the Riemannian curvature tensor and its covariant derivatives.

We have discussed several aspects of the use of our decomposition algorithm in the computer algebra of tensor expressions in [6]. Some essential points of these considerations are summarized in section 6.

We have realized a Mathematica package called PERMS [5] which contains among other things tools for the decomposition algorithm.

2 Decomposition of ideals with given generating elements into minimal ideals

In this section we give a short description of our decomposition algorithm. More details can be found in [6]. In particular, [6] presents a version of the algorithm which works in the group ring ℂ[G] of a finite group G.

We consider the group ring ℂ[S_{r}] of a symmetric group^{1} S_{r} over the field of complex numbers ℂ. Let I := ℂ[S_{r}] · a be a left ideal of this group ring with known generating element a ∈ ℂ[S_{r}]. We search for a decomposition of I in a direct sum of minimal left ideals I_{j} of ℂ[S_{r}]

I = I_{1} ⊕ I_{2} ⊕ … ⊕ I_{l} .  (3)

1We use the convention (p∘q) : i ↦ (p∘q)(i) := p(q(i)) for the multiplication of permutations.

Furthermore, we want to determine a generating idempotent e of I and the decomposition of e in a sum of orthogonal primitive idempotents e_{j} which corresponds to the decomposition (3),

e = e_{1} + e_{2} + … + e_{l} , e_{j} ∈ I_{j} , I = ℂ[S_{r}] · e  (4)
e_{j} · e_{j} = e_{j} , e_{j} · e_{k} = 0 (j ≠ k) .

Our algorithm is based on the well-known fact that the group ring ℂ[S_{r}] can be decomposed into minimal left ideals by means of Young symmetrizers (see e.g. [1, Chapter IV/§4 and §6] or [9, vol. I/pp.73,74]).

Theorem 1 Let ST_{λ} denote the set of all standard tableaux of a Young frame which is characterized by a partition λ ⊢ r of the natural number r as usual. Further, let y_{t} be the Young symmetrizer of a Young tableaux t belonging to r. Then the group ring ℂ[S_{r}] has the decomposition

ℂ[S_{r}] = ⨁_{λ⊢r} ⨁_{t∈ST_{λ}} ℂ[S_{r}] · y_{t} .  (5)

A Young symmetrizer y_{t} of a Young tableau t is defined by

y_{t} := ∑_{q∈V_{t}} ∑_{p∈H_{t}} χ(q) p ∘ q ∈ ℂ[S_{r}] .  (6)

Here, H_{t} and V_{t} are the groups of the horizontal and vertical permutations of the Young tableau t, respectively, and χ(q) denotes the signature of the permutation q.

Every Young symmetrizer y_{t} differs from a primitive idempotent e_{t} only by a factor 0 ≠ μ ∈ ℂ, i.e. e_{t} = μy_{t}. A left ideal ℂ[S_{r}] · y_{t}, generated by a Young symmetrizer, is minimal^{2}. However, the Young symmetrizers y_{t} of standard tableaux t ∈ ST_{λ} are not pairwise orthogonal in general ([10, p.76], [1, p.103]).

If we multiply equation (5) by the generating element a of the ideal I, we obtain

I = ℂ[S_{r}] · a = ∑_{λ⊢r} ∑_{{t∈ST_{λ} \atop y_{t}·a≠0}} ℂ[S_{r}] · y_{t} · a .  (7)

Unfortunately, the sums in (7) are no longer direct. Thus, the following problem arises. We have to delete left ideals ℂ[S_{r}] · y_{t} · a in (7) in such a way that we obtain a direct sum which results still in I. We will solve this problem.

First we notice (see [6])

Lemma 1 If y_{t} · a ≠ 0, then the left ideals I_{t} := ℂ[S_{r}] · y_{t} and W_{t} := ℂ[S_{r}] · y_{t} · a are equivalent that means there exists a vector space isomorphism ϕ : I_{t} → W_{t} which fulfils ϕ(p · f) = p · ϕ(f) for all p ∈ S_{r}, f ∈ I_{t} . Since I_{t} is a minimal left ideal, W_{t} is minimal, too.

2About Young symmetrizers and Young tableaux see for instance [2, 7, 8, 9, 10, 11, 12, 13, 16, 17].

Next we show a simple method to produce a generating idempotent of a left ideal W_{t} = ℂ[S_{r}] · y_{t} · a.

Proposition 1 Let e ∈ ℂ[S_{r}] be a primitive idempotent and let a ∈ ℂ[S_{r}] be a group ring element with e · a ≠ 0. Then there exists a permutation p ∈ S_{r} such that

e · a · p · e ≠ 0 .  (8)

Moreover, the group ring element b := p · e · a formed with this p is essentially idempotent and generates the left ideal W = ℂ[S_{r}] · e · a.

Proof. The left ideal W = ℂ[S_{r}] · e · a possesses a generating idempotent f [1, p. 54] which can be written as f = x · e · a with a certain x ∈ ℂ[S_{r}]. Now, the relation

e · a · x · e ≠ 0  (9)

follows from 0 ≠ f = f · f = x · e · a · x · e · a. But then a permutation p ∈ S_{r} has to exist which satisfies (9) with x = p since otherwise the left-hand side of (9) would vanish for every x ∈ ℂ[S_{r}].

As e is a primitive idempotent, we get

e · a · p · e = μ e

with a complex number μ ∈ ℂ [1, p. 56] and μ ≠ 0 on account of (8). Consequently, b := p · e · a is essentially idempotent, because

b · b = p · (e · a · p · e) · a = μ b ,

and b generates W since ℂ[S_{r}] · p = ℂ[S_{r}]. □

Remark. The assertion of proposition 1 remains true if we replace the permutation p by a group ring element h. If h ∈ ℂ[S_{r}] satisfies (8), then, obviously, b := h · e · a is essentially idempotent. Furthermore, b generates the left ideal W = ℂ[S_{r}] · e · a, too, since W′ := ℂ[S_{r}] · h · e · a is a non-vanishing left subideal of W which has to coincide with W because of the minimality of W. This version of an idempotent construction is used in section 5.

By proposition 1 it is possible to construct a generating idempotent for every minimal left ideal ℂ[S_{r}] · y_{t} · a in (7) with y_{t} · a ≠ 0.

The determination of the permutation p for the forming of the essentially idempotent element b can be done by a computer program which tests the validity of condition (8) for the finitely many group elements p ∈ S_{r} one after another. The search stops if the first p ∈ S_{r} is found which fulfils (8). We have realized such an algorithm in PERMS. Though symmetric groups have a very large cardinality |S_{r}| = r! in general, all examples treated with this algorithm claim a small number of search steps to reach a permutation p ∈ S_{r} which satisfies (8).

In section 4 we give minimal sets of permutations which contain certainly a permutation satisfying (8). Furthermore, in section 5 we will see that the use of fast Fourier transforms makes the search for such permutations unnecessary.

Now we consider an orthogonalization problem. Let be given the direct sum of two left ideals

(ℂ[S_{r}] · e_{1}) ⊕ (ℂ[S_{r}] · e_{2})

with generating idempotents e_{1}, e_{2} which are non-orthogonal. We search for new generating idempotents f_{1}, f_{2} of these ideals which fulfil

f_{1} · f_{2} = f_{2} · f_{1} = 0 .

To solve this problem the following characterization of the set of all generating idempotents of a given left ideal is very helpful.

Proposition 2 Let G be a finite group and e ∈ ℂ[G] be a generating idempotent of a left ideal I = ℂ[G] · e. Then a group ring element f ∈ ℂ[G] is a generating idempotent^{3} of I if and only if there exists a group ring element x ∈ ℂ[G] such that

f = e − x · e + e · x · e .  (10)

Proof. First we show that every group ring element (10) is a generating idempotent of I. Since e is an idempotent we obtain f · e = f. Further, e · f = e follows immediately from −e · x · e + e · e · x · e = 0, i.e. f is a generating element of I. Now the idempotent property of f is verified by

f · f = (e − x · e + e · x · e) · f = e − x · e + e · x · e = f .

On the other hand, every generating idempotent f of I can be represented in the form (10). From f ∈ I there follows f − e ∈ I. Therefore we can write f − e = −y · e with a certain y ∈ ℂ[G]. Then e · f = e yields e · y · e = 0 such that f = e − y · e + e · y · e is correct. □

Corollary 1 ^{4} Let e ∈ ℂ[G] be an idempotent. Then the following assertions hold true for all x ∈ ℂ[G]:

1. n := x · e − e · x · e is nilpotent, i.e. n · n = 0.

3The idea to produce a new idempotent f from a given idempotent e in this way was taken out of [14, p. 137]. However, in [14] the forming of new idempotents is carried out only by means of group elements x = g ∈ G of the underlying group G.

4This remarkable property is mentioned in [14, p. 138], too. According to [14], first Zalesskii becomes aware of it.

2. u := id − n is an invertible element or a unit of ℂ[G] with the inverse u^{−1} = id + n, where id denotes the identity element of G.

3. The idempotent f = e−x·e+e·x·e in accordance with proposition 2 fulfils f = u · e · u^{−1}.

Proof. Corollary 1 can be proved by straightforward calculations (see [6]). □

Since formula (10) describes the complete set of generating idempotents of a left ideal I we can search the idempotents f_{1}, f_{2} of the orthogonalisation problem in the form of (10). The next proposition is the basis of our orthogonalization procedure.

Proposition 3 Let I = ℂ[S_{r}] · e and Ĩ = ℂ[S_{r}] · ẽ be two left ideals of ℂ[S_{r}], generated by the idempotents e, ẽ. We assume that e is primitive, i.e. I is minimal. Further we require e · ẽ ≠ e such that I and Ĩ form a direct sum I ⊕ Ĩ since I ⊈ Ĩ. Then there holds true:

1. A permutation p ∈ S_{r} can be found such that

e · (id − ẽ) · p · e ≠ 0 .  (11)

Moreover, a complex number λ ∈ ℂ belonging to that p is available such that f := e − x · e + e · x · e with x := λ (id − ẽ) · p is a generating idempotent of I which satisfies ẽ · f = 0.

2. For a given idempotent f according to 1 a permutation p̃ ∈ S_{r} exists such that

f · (id − ẽ) · p̃ · f ≠ 0 .  (12)

Besides, a complex number λ̃ ∈ ℂ can be chosen such that f̃ := ẽ − x̃ · ẽ with x̃ := λ̃ (id − ẽ) · p̃ · f is a generating idempotent of Ĩ which fulfils f · f̃ = f̃· f = 0.

Proof. From e · ẽ ≠ e we obtain e · (id − ẽ) ≠ 0. Then, proposition 1 yields the existence of a p ∈ S_{r} such that e · (id − ẽ) · p · e ≠ 0. Thus (11) is proved. Since e is primitive, a relation

e · (id − ẽ) · p · e = μ e  (13)

is valid with a complex number μ ∈ ℂ [1, p. 56], and μ ≠ 0 on account of (11). Now, if f is an idempotent according to statement 1 of proposition 3 which generates I by proposition 2, we get

ẽ · f = ẽ · e − ẽ · x · e + ẽ · e · x · e
= ẽ · e + λμ ẽ · e

by considering ẽ · x = 0 and (13). Then λ = −1/μ leads to ẽ · f = 0.

As f likewise generates I, there follows f · ẽ ≠ f. Otherwise, there would be I ⊆ Ĩ in contradiction to e · ẽ ≠ e. Now the existence of a p̃ ∈ S_{r} which satisfies (12) arises from the application of statement 1 of proposition 3 to the idempotents f, ẽ. We change to a new idempotent f̃ := ẽ − x̃ · ẽ + ẽ · x̃ · ẽ of Ĩ with x̃ := λ̃ (id − ẽ) · p̃ · f. Then ẽ · x̃ = 0 yields ẽ · x̃ · ẽ = 0. Being a generating idempotent of the minimal left ideal I, f is primitive and (12) results consequently in f · (id − ẽ) · p̃ · f = μ̃ f with 0 ≠ μ̃ ∈ ℂ. Thus, we get for f̃ = ẽ − x̃ · ẽ

f · f̃ = f · ẽ − λ̃ f · (id − ẽ) · p̃ · f · ẽ = (1 − λ̃μ̃) f · ẽ ,

and the choice λ̃ = 1/μ̃ gives f · f̃ = 0. The relation f̃· f = 0 follows simply from ẽ · f = 0. □

Now, we can describe our

Decomposition Algorithm (L) for Left Ideals:

Let be given a left ideal I = ℂ[S_{r}] · a of ℂ[S_{r}] with known generating element a ∈ ℂ[S_{r}]. We start with formula (7), i.e.

I = ℂ[S_{r}] · a = ∑_{λ⊢r} ∑_{{t∈ST_{λ} \atop y_{t}·a≠0}} ℂ[S_{r}] · y_{t} · a .  (14)

Then we can carry out the following steps:

1. The first left ideal in the sum (14) is minimal. We denote it by I_{1} and we can determine a generating idempotent e_{1} of I_{1} by means of proposition 1.

2. We search for the first minimal left ideal in (14) which is not contained in I_{1} that means for which there holds true

y_{t} · a · e_{1} ≠ y_{t} · a .  (15)

We denote it by I_{2} and we construct a generating idempotent e_{2} of I_{2} by means of proposition 1. Furthermore we determine new generating idempotents f̂_{1}, f_{2} of I_{1}, I_{2} according to proposition 3 which are orthogonal. Then we form the leftideal Ĩ_{2} := I_{1} ⊕ I_{2} for which f̃_{2} := f̂_{1} + f_{2} is a generating idempotent.

3. Now we search for the next minimal left ideal in (14) which is not contained in Ĩ_{2} that means for which there holds true

y_{t} · a · f̃_{2} ≠ y_{t} · a .  (16)

We denote it by I_{3}. We construct a generating idempotent e_{3} of I_{3} and pass over to new orthogonal idempotents f̂_{2}, f_{3} instead of f̃_{2}, e_{3}. This leads us to the left ideal Ĩ_{3} := Ĩ_{2}⊕I_{3} which has the generating idempotent f̃_{3} := f̂_{2}+f_{3}.

4. We continue this procedure until we have investigated all left ideals in (14). The result is the searched decomposition

I = I_{1} ⊕ I_{2} ⊕ … ⊕ I_{m}  (17)

of I and a generating idempotent f̃_{m} of I.

According to statement 2 of proposition 3 every idempotent f̂_{k} of the left ideal Ĩ_{k} of the (k + 1)-th step can be written as f̂_{k} = (id − x_{k}) · f̃_{k} with x_{k} ∈ ℂ[S_{r}] which we have already determined to carry out the orthogonalization (e_{k+1}, f̃_{k}) ↦ (f_{k+1}, f̂_{k}). Thus we can write

f̃_{m} = f̂_{m−1} + f_{m}
= (id − x_{m−1}) · f̃_{m−1} + f_{m}
= (id − x_{m−1}) · (f̂_{m−2} + f_{m−1}) + f_{m}
= (id − x_{m−1}) · (id − x_{m−2}) · f̃_{m−2} + (id − x_{m−1}) · f_{m−1} + f_{m}
⋮
= ∑_{k=1}^{m−1}(id − x_{m−1}) · (id − x_{m−2}) · . . . · (id − x_{k}) · f_{k} + f_{m} .  (18)

Formula (18) presents a decomposition f̃_{m} = ∑_{k=1}^{m} h_{k} of f̃_{m} the summands of which fulfil

h_{k} := (id − x_{m−1}) · (id − x_{m−2}) · . . . · (id − x_{k}) · f_{k} ∈ I_{k}  (19)
h_{m} := f_{m} ∈ I_{m} .

Therefore, f̃_{m} = ∑_{k=1}^{m} h_{k} is the decomposition of f̃_{m} corresponding to the direct sum I = ⨁_{k=1}^{m} I_{k} and the h_{k} are orthogonal generating idempotents of the minimal left ideals I_{k} [1, p. 55].

Theorem 2 Let I = ℂ[S_{r}] · a be a left ideal of ℂ[S_{r}], generated by a given group ring element a ∈ ℂ[S_{r}] , a ≠ 0. Then the algorithm (L) produces a generating idempotent e ∈ ℂ[S_{r}] of I and a decomposition e = h_{1} + h_{2} + … + h_{m} of e into primitive pairwise orthogonal idempotents h_{k} which defines a decomposition I = ⨁_{k=1}^{m} I_{k} of I into minimal left ideals I_{k} = ℂ[S_{r}] · h_{k}.

Essentially, the correctness of theorem 2 follows from the description of algorithm (L). A detailed proof is given in [6, Theorem 4.1].

It is clear that there are still some possibilities to increase the efficiency of the algorithm (L). Since minimal left ideals ℂ[S_{r}]·y_{t} ·a and ℂ[S_{r}]·y_{t′} ·a automatically form a direct sum if the standard tableaux t ∈ ST_{λ} and t ∈ ST_{λ′} belong to different partitions λ, λ′ ⊢ r, we have to apply the algorithm only to sets of left ideals ℂ[S_{r}] · y_{t} · a which lie in the same two-sided ideal

I_{λ} := ⨁_{t∈ST_{λ}} ℂ[S_{r}] · y_{t} ,  (20)

characterized by a partition λ ⊢ r that means which belong to the same class of equivalent minimal left ideals.

Furthermore, the knowledge of multiplicities of equivalent minimal left ideals in the searched decomposition of I is very helpful. If for a fixed λ ⊢ r the algorithm has found a direct sum of minimal left ideals ℂ[S_{r}] · y_{t} · a with t ∈ ST_{λ}, the number of which is equal to the known multiplicity, then the investigation of the remaining left ideals ℂ[S_{r}]·y_{t} ·a of λ can be canceled. The calculation of such multiplicities is possible if the given left ideal I = ℂ[S_{r}] · a can be identified with the representation space of a certain linear representation α of the symmetric group S_{r}, the character of which is known. In particular, if α turns out to be an induced representation of an outer tensor product of representations or of a certain representation of a wreath product of certain symmetric groups, then the Littlewood-Richardson rule (see [10, pp. 94], [9, vol. I p. 84], [11, pp. 68] and [7]) or plethysms (see [9], [15, pp. 8]) are important tools to determine such multiplicities.

A further efficiency problem of the algorithm arises from the fact that the naive calculation of the product a · b of two group ring elements a, b ∈ ℂ[S_{r}] entails a high need of calculation time and computer memory, if we have a large r. The use of fast Fourier transforms shows a way out of this problem (section 5).

We finish this section with a remark on decompositions of rigth ideals.

Proposition 4 Let J := a · ℂ[S_{r}] be a right ideal of ℂ[S_{r}], generated by a given group ring element a ∈ ℂ[S_{r}] , a ≠ 0. Then a version (R) of the algorithm (L) can be stated which produces a generating idempotent e ∈ ℂ[S_{r}] of J and a decomposition e = h_{1} + h_{2} + … + h_{m} of e into primitive pairwise orthogonal idempotents h_{k} defining a decomposition J = ⨁_{k=1}^{m} J_{k} of J into minimal right ideals J_{k} = h_{k} · ℂ[S_{r}].

Proof. The version (R) of the decomposition algorithm starts with the decomposition

ℂ[S_{r}] = ⨁_{λ⊢r} ⨁_{t∈ST_{λ}} y_{t} · ℂ[S_{r}]  (21)

of ℂ[S_{r}] into minimal right ideals y_{t} · ℂ[S_{r}] which can be proved in the same way as (5) (see [9, vol. I/pp.73,74] and [1, footnote on p.105]). Then we obtaine a description of the version (R) from the description of the version (L) if we write all products of group ring elements, which occur in the description (L), in reverse order. Furthermore, we have to transform the given versions of lemma 1 and of the propositions 1, 2 and 3 for left ideals into statements on right ideals by inversion of the factor sequence in all appearing products. Then, the proofs of propositions 1, 2, 3 can be rewritten easily into proofs for right ideals. □

The involution

∗ : ℂ[S_{r}] → ℂ[S_{r}] , a = ∑_{p∈S_{r}} a(p) p ↦ a^{∗} := ∑_{p∈S_{r}} a(p) p^{−1} (22)

of ℂ[S_{r}] presents an other possibility to decompose right ideals by means of the algorithm (L). The involution ∗ maps (primitive) itempotents to (primitive) idempotents, direct sums of left (rigth) ideals to direct sums of rigth (left) ideals and preserves the minimality of ideals. Thus we can construct a decomposition of a given right ideal J = a·ℂ[S_{r}] by passing over to the left ideal I = J^{∗} = ℂ[S_{r}]·a^{∗}, determining a generating Idempotent e and a decomposition

I = ℂ[S_{r}] · e = ⨁_{k=1}^{m} ℂ[S_{r}] · e_{k} , e = ∑_{k=1}^{m} e_{k}

of I by means of (L) and returning to the right ideal J,

J = I^{∗} = e^{∗} · ℂ[S_{r}] = ⨁_{k=1}^{m} e_{k}^{∗} · ℂ[S_{r}] , e^{∗} = ∑_{k=1}^{m} e_{k}^{∗} .

However, the transformation ∗ causes extra costs in time and memory. In particular, the use of two algorithms (L) and (R) is more advantageous in the case of applying fast Fourier transforms.

3 Determination of generating idempotents by means of the decomposition algorithm

In this section we discuss some cases of left (or right) ideals for which no generating elements are known, but for which the determination of generating idempotents can be done by the help of the decomposition algorithm.

At first, we give some lemmas on annihilator ideals of a group ring ℂ[G] of a finite group G. We denote by Z_{r}(I) the right annihilator ideal and by Z_{l}(I) the left annihilator ideal of an ideal I of ℂ[G],

Z_{r}(I) := { h ∈ ℂ[G] | ∀ f ∈ I : f · h = 0 }
Z_{l}(I) := { h ∈ ℂ[G] | ∀ f ∈ I : h · f = 0 } .

Lemma 2 Let I and J be a left ideal and a right ideal of ℂ[G], respectively. Then there holds true

J = Z_{r}(I) ⟺ I = Z_{l}(J) .  (23)

Proof. Let J = Z_{r}(I). The ideal I has a generating idempotent e. Then Z_{r}(I) = J is generated^{5} by the idempotent id − e and further Z_{l}(J) is generated by id − (id − e) = e, i.e. Z_{l}(J) = I. The reverse case follows in the same way. □

Lemma 3 Let I be a left ideal of ℂ[G] and a ∈ ℂ[G] be a group ring element with a ≠ 0. Then there holds true:

1. There is I = ℂ[G] · a if and only if Z_{r}(I) = {h ∈ ℂ[G] | a · h = 0}.

2. There is I = {f ∈ ℂ[G] | f · a = 0} if and only if Z_{r}(I) = a · ℂ[G].

Proof. We prove statement 1. Let I satisfy I = ℂ[G] · a. We use the notation K := {h ∈ ℂ[G] | a · h = 0}. Obviously, there is Z_{r}(I) ⊆ K since a · Z_{r}(I) = 0. If e is a generating idempotent of I, then id − e generates Z_{r}(I). Now we assume that there exists a group ring element h ∈ e · ℂ[G], h ≠ 0, with a · h = 0. But since e can be written as e = x · a with a certain x ∈ ℂ[G], we would obtain the contradiction x · a · h = h ≠ 0. Consequently, there is K = Z_{r}(I).

Conversely, if Z_{r}(I) fulfils Z_{r}(I) = {h ∈ ℂ[G] | a · h = 0}, then there follows from the just drawn conclusions that Z_{r}(ℂ[G]·a) = {h ∈ ℂ[G] | a·h = 0} = Z_{r}(I). Thus lemma 2 yields I = ℂ[G] · a.

Statement 2 can be proved in the same way as statement 1. □

Lemma 4 Let I_{1}, I_{2}, …, I_{m} ⊆ ℂ[G] be left ideals of ℂ[G]. Then there holds true

Z_{r}( ⋂_{k=1}^{m} I_{k}) = ∑_{k=1}^{m} Z_{r}(I_{k}) .  (24)

Proof. Instead of (24), we show the equivalent relation

⋂_{k=1}^{m} I_{k} = Z_{l}( ∑_{k=1}^{m} Z_{r}(I_{k})) .  (25)

The inclusion ⋂_{k=1}^{m} I_{k} ⊇ Z_{l}( ∑_{k=1}^{m} Z_{r}(I_{k})) follows from the fact that every f ∈ Z_{l}( ∑_{k=1}^{m} Z_{r}(I_{k})) fulfils f · h_{k} = 0 for all h_{k} ∈ Z_{r}(I_{k}) and all k = 1, …, m, i.e. f ∈ Z_{l}(Z_{r}(I_{k})) = I_{k} for all k = 1, …, m.

Conversely, every f ∈ ⋂_{k=1}^{m} I_{k} satisfies f · h = f · h_{1} + … + f · h_{m} = 0 for all h = h_{1} + … + h_{m} ∈ ∑_{k=1}^{m} Z_{r}(I_{k}), h_{k} ∈ Z_{r}(I_{k}). This leads to ⋂_{k=1}^{m} I_{k} ⊆ Z_{l}( ∑_{k=1}^{m} Z_{r}(I_{k})). □

Proposition 5 Let a ∈ ℂ[S_{r}], a ≠ 0, be a group ring element of ℂ[S_{r}] which annihilates a given left ideal I ⊆ ℂ[S_{r}], i.e. I = {f ∈ ℂ[S_{r}] | f · a = 0}. Then we can construct a generating idempotent of I by means of the decomposition algorithm (R).

5On the one hand, every h ∈ ℂ[G] can be written as h = e · h + (id − e) · h such that there follows h = (id − e) · h for h ∈ Z_{r}(I) since e · h = 0. On the other hand, every group ring element (id − e) · y lies in Z_{r}(I), because x · e · (id − e) · y = 0 for every x · e ∈ I.

Proof. From lemma 3 there follows that Z_{r}(I) = a · ℂ[S_{r}]. Thus we can use algorithm (R) to determine a generating idempotent e of Z_{r}(I) from which we obtain the generating idempotent id − e of I. □

Proposition 6 Let I_{1}, I_{2}, …, I_{m} ⊆ ℂ[S_{r}] be a finite set of left ideals of the group ring ℂ[S_{r}]. We assume that every left ideal I_{k} is defined either by a generating element a_{k} ∈ ℂ[S_{r}], i.e. I_{k} = ℂ[S_{r}]·a_{k}, or by an annihilating element n_{k} ∈ ℂ[S_{r}], i.e. I_{k} = {f ∈ ℂ[S_{r}] | f · n_{k} = 0}. Then we can construct generating idempotents of the left ideals ∑_{k=1}^{m} I_{k} and ⋂_{k=1}^{m} I_{k} by means of the algorithms (L) or (R).

Proof. At first we consider the (non-direct) sum J = ∑_{k=1}^{m} I_{k}. We can assume that we know a generating element a_{k} for every left ideal I_{k} because we can determine generating idempotents e_{l} according to proposition 5 for all such left ideals I_{l} which are characterized only by annihilating elements n_{l}.

By using equation (5) we can write

J = ∑_{λ⊢r} ∑_{k=1}^{m} ∑_{{t∈ST_{λ} \atop y_{t}·a_{k}≠0}} ℂ[S_{r}] · y_{t} · a_{k} .  (26)

Now we apply our decomposition algorithm (L) to the set I of all minimal left ideals ℂ[S_{r}] · y_{t} · a_{k} in (26), to select such a subset Ĩ of I that J is the direct sum of the ideals in Ĩ. The occurrence of more than one generating element a_{k} does not disturb the effectiveness of the algorithm. Obviously, algorithm (L) yields a generating idempotent e of J in this case, too.

To process the intersection K = ⋂_{k=1}^{m} I_{k}, we determine generating idempotents e_{l} by means of algorithm (L) for all such left ideals I_{l} which are described by a generating element a_{l}. Then id − e_{l} is an annihilating element of I_{l} = ℂ[S_{r}] · e_{l}. Thus we can assume that all left ideals I_{k} are characterized by annihilating elements n_{k}. Taking into account lemma 3 and 4 we obtain

Z_{r}(K) = ∑_{k=1}^{m} Z_{r}(I_{k}) = ∑_{k=1}^{m} n_{k} · ℂ[S_{r}] .

Now the application of algorithm (R) to ∑_{k=1}^{m} n_{k} · ℂ[S_{r}] produces a generating idempotent e of Z_{r}(K) wich leads to the generating idempotent id − e of K. □

4 Minimal sets of test permutations

In this section we will determine minimal sets of permutations in which we can find certainly such a permutation that a condition of type (8), (11) or (12) is fulfilled.

Proposition 7 Let us consider the algorithm (L) which is based on the decomposition (5) of the group ring ℂ[S_{r}]. Then every of the conditions (8), (11) and (12) can be reduced to a condition

y_{t} · w · p · y_{t} ≠ 0  (27)

with a certain Young symmetrizer y_{t} of a standard tableau t and a certain group ring element w ∈ ℂ[S_{r}], satisfying y_{t} · w ≠ 0, in the course of every step of the algorithm.

Proof. Let us consider the k-th step of the algorithm (L). The first time we have to use condition (8), if we have found a group ring element y_{t_{k}} · a ≠ 0 such that y_{t_{k}} ·a·f̃_{k−1} ≠ y_{t_{k}} ·a with the resulting idempotent f̃_{k−1} of the (k-1)-th step. Then we have to construct an idempotent from y_{t_{k}} · a by means of proposition 1. But in this case condition (8) takes a form (27), i.e.

y_{t_{k}} · a · p · y_{t_{k}} ≠ 0 .  (28)

The idempotent produced from y_{t_{k}}·a according to proposition 1 is e_{k} = α_{k} p_{k}·y_{t_{k}}·a with a constant α_{k} ∈ ℂ and a permutation p_{k} ∈ S_{r} fulfilling (28).

Next we have to determine an idempotent f_{k} from e_{k} according to statement 1 of proposition 3 such that f̃_{k−1} · f_{k} = 0. Let us consider the condition

y_{t_{k}} · a · (id − f̃_{k−1}) · s · y_{t_{k}} ≠ 0  (29)

of the type (27). The permutation s ∈ S_{r} is searched. From y_{t_{k}} · a · f̃_{k−1} ≠ y_{t_{k}} · a there follows y_{t_{k}} · a · (id − f̃_{k−1}) ≠ 0. Thus proposition 1 yields the existence of a permutation s_{k} ∈ S_{r} which satisfies (29). Since y_{t_{k}} differs from a primitive idempotent only by a constant factor the relation

y_{t_{k}} · a · (id − f̃_{k−1}) · s_{k} · y_{t_{k}} = κ y_{t_{k}} , κ = const. ≠ 0  (30)

arises from (29). Multiplying (30) by p_{k} and a from the left and the right, respectively, we obtain (11),

e_{k} · (id − f̃_{k−1}) · s_{k} · p_{k}^{−1} · e_{k} = α_{k} κ e_{k} ≠ 0 ,

fulfilled by the permutation s_{k}·p_{k}^{−1}. Now we can form the idempotent f_{k}. Because of corollary 1 there holds true f_{k} = u_{k} · e_{k} · u_{k}^{−1} with a certain unit u_{k} ∈ ℂ[S_{r}] which we can calculate according to proposition 2 and corollary 1.

At last, we have to construct an idempotent f̂_{k−1} from f̃_{k−1} according to statement 2 of proposition 3 such that f_{k} · f̂_{k−1} = f̂_{k−1} · f_{k} = 0. To this end, we search for a permutation ŝ_{k} ∈ S_{r} which satisfies the condition

y_{t_{k}} · a · u_{k}^{−1} · (id − f̃_{k−1}) · s · y_{t_{k}} ≠ 0  (31)

of the type (27). From f_{k} · f̃_{k−1} ≠ f_{k} there follows y_{t_{k}} · a · u_{k}^{−1} · (id − f̃_{k−1}) ≠ 0 such that proposition 1 guarantees the existence of such a permutation ŝ_{k}. Then relation (31) leads to

y_{t_{k}} · a · u_{k}^{−1} · (id − f̃_{k−1}) · ŝ_{k} · y_{t_{k}} = κ̂ y_{t_{k}} , κ̂ = const. ≠ 0 . (32)

Multiplying (32) by u_{k} · p_{k} and a · u_{k}^{−1} from the left and the right, respectively, we obtain (12),

f_{k} · (id − f̃_{k−1}) · h_{k} · f_{k} = α_{k} κ̂ f_{k} ≠ 0 ,

satisfied by the group ring element h_{k} := ŝ_{k} · p_{k}^{−1} · u_{k}^{−1}. Now we can form an idempotent f̂_{k−1} := f̃_{k−1}−x̂·f̃_{k−1} with x̂ := λ̂ (id−f̃_{k−1})·h_{k} ·f_{k}. The permutation p̃, used in proposition 3, is replaced by h_{k}. But the proof of statement 2 of proposition 3 works in this case, too. □

Now we present a set of permutations for a given relation (27) which is essentially smaller than S_{r} but contains definitely a permutation p satisfying (27).

Proposition 8 Let t_{0} ∈ ST_{λ} be a fixed standard tableau of a given partition λ ⊢ r of a natural number r ∈ ℕ and let y_{t_{0}} be the Young symmetrizer of t_{0}. We denote by P_{t_{0}} the set

P_{t_{0}} := {s ∈ S_{r} | s ∘ t_{0} ∈ ST_{λ}}  (33)

of all such permutations s ∈ S_{r} which transform t_{0} to the rest of the standard tableaux of λ. Then, for every w ∈ ℂ[S_{r}] with y_{t_{0}}·w ≠ 0 we can find a permutation s_{0} ∈ P_{t_{0}} such that

y_{t_{0}} · w · s_{0} · y_{t_{0}} ≠ 0 .  (34)

Proof. Since y_{t_{0}} · w ≠ 0, the left ideal W_{t_{0}} := ℂ[S_{r}] · y_{t_{0}} · w is equivalent to the minimal left ideal I_{t_{0}} := ℂ[S_{r}] · y_{t_{0}} (lemma 1). Therefore, W_{t_{0}} is a subideal of the two-sided ideal

I_{λ} := ⨁_{t∈ST_{λ}} ℂ[S_{r}] · y_{t}  (35)

which contains all ideals of the equivalence class of minimal left ideals of ℂ[S_{r}], characterized by λ. Thus y_{t_{0}} · w ∈ I_{λ} can be written as

y_{t_{0}} · w = ∑_{t∈ST_{λ}} x_{t} · y_{t} , x_{t} ∈ ℂ[S_{r}] ,  (36)

with suitable group ring elements x_{t}. At least one of the summands of (36) does not vanish.

We use the usual dictionary order for Young tableaux of the same partition λ ⊢ r [9, vol. I, p. 73]. A tableau t_{2} of λ is regarded as greater than a tableau t_{1} of λ, if the simultaneous run through the rows of both tableaux from left to right and from top to bottom reaches earlier in t_{2} a number which is greater than the number on the corresponding place in t_{1}.

Now, let t_{1} ∈ ST_{λ} be the smallest standard tableau of λ such that the summand of t_{1} in (36) fulfils x_{t_{1}} ·y_{t_{1}} ≠ 0. Since all Young symmetrizers y_{t} of standard tableaux t ∈ ST_{λ} with t > t_{1} satisfy y_{t} · y_{t_{1}} = 0 and, on the other hand, the symmetrizer y_{t_{1}} is essentially idempotent, i.e. y_{t_{1}} · y_{t_{1}} = μ y_{t_{1}} , μ = const. ≠ 0, the multiplication of (36) by y_{t_{1}} from the right yields

y_{t_{0}} · w · y_{t_{1}} = μ x_{t_{1}} · y_{t_{1}} ≠ 0 .  (37)

Let s_{0} ∈ P_{t_{0}} be that permutation which transforms t_{0} into t_{1}, i.e. t_{1} = s_{0} ∘ t_{0}. Then there holds true y_{t_{1}} = s_{0} · y_{t_{0}} · s_{0}^{−1} and we obtain from (37) the relation

y_{t_{0}} · w · s_{0} · y_{t_{0}} · s_{0}^{−1} ≠ 0

which leads to (34). □

The cardinality of P_{t_{0}} amounts to |P_{t_{0}}| = |ST_{λ}| ≪ |S_{r}| = r!. Now we will show that this value represents already the minimum.

Proposition 9 Let y_{t_{0}} be the Young symmetrizer of an arbitrary Young tableau t_{0} of a given partition λ ⊢ r. Further, let P ⊆ S_{r} be such a subset of permutations from S_{r} that for every group ring element w ∈ ℂ[S_{r}] with y_{t_{0}} · w ≠ 0 there exists a permutation s ∈ P which satisfies

y_{t_{0}} · w · s · y_{t_{0}} ≠ 0 .  (38)

Then there holds true

|P| ≥ |ST_{λ}| .  (39)

Proof. We assume |P| < |ST_{λ}|. Let us denote by Y_{P} the set

Y_{P} := {y_{t} | y_{t} Young symmetrizer of t = s ∘ t_{0} , s ∈ P}

of the Young symmetrizers of all those Young tableaux t which are generated from t_{0} by all permutations of P. The property of P, required in proposition 9, has the consequence that for every w ∈ ℂ[S_{r}] with y_{t_{0}} · w ≠ 0 there exists a Young symmetrizer y_{t} ∈ Y_{P} such that

y_{t_{0}} · w · y_{t} ≠ 0 .  (40)

If the permutation s_{0} ∈ P satisfies (38) for a given w then the Young symmetrizer y_{t_{1}} ∈ Y_{P} of the Young tableau t_{1} := s_{0}∘t_{0} fulfils y_{t_{1}} = s_{0}·y_{t_{0}}·s_{0}^{−1} and, consequently, there follows y_{t_{0}} · w · y_{t_{1}} ≠ 0 from (38).

Let us consider the right ideal

J_{P} := ∑_{y_{t}∈Y_{P}} y_{t} · ℂ[S_{r}]  (41)

to which we can apply the algorithm (R) according to proposition 6. Since the Young symmetrizers y_{t} are proportional to primitive idempotents, the right ideals y_{t} · ℂ[S_{r}] are minimal and algorithm (R) produces a subset Y′ ⊆ Y_{P} of Y_{P} such that

J_{P} := ⨁_{y_{t}∈Y′} y_{t} · ℂ[S_{r}] .  (42)

The right ideal J_{P} possesses a generating idempotent e which decomposes into primitive pairwise orthogonal idempotents e_{y_{t}} according to (42),

e = ∑_{y_{t}∈Y′} e_{y_{t}} , e_{y_{t}} ∈ y_{t} · ℂ[S_{r}] .

Now we form the left ideal I_{P} generated by e

I_{P} := ℂ[S_{r}] · e = ⨁_{y_{t}∈Y′} ℂ[S_{r}] · e_{y_{t}} .  (43)

Because all Young tableaux t in (41) belong to the same partition λ ⊢ r, all right ideals y_{t} ·ℂ[S_{r}] in (41) are equivalent to the right ideal y_{t_{0}} ·ℂ[S_{r}]. Therefore, for every y_{t} ∈ Y′ there exists a non-vanishing group ring element e_{y_{t}} · x · y_{t_{0}} ≠ 0, x ∈ ℂ[S_{r}], which describes the equivalence mapping y_{t_{0}} · ℂ[S_{r}] → e_{y_{t}} · ℂ[S_{r}] [1, p.56]. On the other hand, the existence of the elements e_{y_{t}} · x · y_{t_{0}} ≠ 0 guarantees that every left ideal ℂ[S_{r}]·e_{y_{t}} in (43) is equivalent to the left ideal I_{t_{0}} := ℂ[S_{r}]·y_{t_{0}}. Thus I_{P} is a subideal of the two-sided ideal I_{λ} (35) belonging to the given partition λ ⊢ r. The dimension of I_{P} is smaller than the dimension of I_{λ} since

dim I_{P} = |Y′| dim I_{t_{0}} ≤ |P| dim I_{t_{0}} < |ST_{λ}| dim I_{t_{0}} = (dim I_{t_{0}})^{2} = dim I_{λ} .

Now we consider the left ideal K which is annihilated by e, i.e.

K := {f ∈ ℂ[S_{r}] | f · e = 0} .

Because there holds true ℂ[S_{r}] = I_{P} ⊕ K and dim I_{P} < dim I_{λ}, the left ideal K has to obtain a minimal left ideal Ǐ which belongs to the equivalence class of minimal left ideals of λ.

Let ě be a generating idempotent of Ǐ. Every Young symmetrizer y_{t} ∈ Y_{P} lies in J_{P} and can be written, consequently, as y_{t} = e · y_{t}. Since furthermore there is ě · e = 0, we obtain

∀ y_{t} ∈ Y_{P} : ě · y_{t} = 0 .

On the other hand, the left ideals Ǐ = ℂ[S_{r}] · ě and I_{t_{0}} = ℂ[S_{r}] · y_{t_{0}} are equivalent and the equivalence mapping I_{t_{0}} → Ǐ is described by a non-vanishing group ring element y_{t_{0}} · x · ě ≠ 0, x ∈ ℂ[S_{r}]. Now, if we choose w := x · ě, then there holds true y_{t_{0}} · w ≠ 0, but

∀ y_{t} ∈ Y_{P} : y_{t_{0}} · w · y_{t} = 0

in contradiction to (40). □

In the next section we will see that the search process for permutations is canceled if we use fast Fourier transforms. But, in the case of small symmetric groups S_{r} with approximately r ≤ 7, the algorithms (L) and (R) can be carried out with reasonable costs immediate in the group ring ℂ[S_{r}]. Then the results of section 4 are important.

5 Application of fast Fourier transforms

As mentioned in section 2, the naive calculation of the product a · b of two group ring elements a, b ∈ ℂ[S_{r}] entails high costs in calculation time and computer memory, if we have a large r. This reduces the efficiency of the algorithms (L) and (R). Now we discuss some ideas of the use of fast Fourier transforms which show a way out of this problem.

The basis of the concept of discrete Fourier transforms for arbitrary finite groups is Wedderburn’s Theorem which we give here only in the special form for symmetric groups S_{r} (see e.g. [1, p.61] or [3, p.38]).

Theorem 3 For every partition λ ⊢ r the two-sided ideal I_{λ} = ⨁_{t∈ST_{λ}} ℂ[S_{r}]·y_{t} of the group ring ℂ[S_{r}] is isomorphic to a full algebra of complex (d_{λ} ×d_{λ})-matrices:

I_{λ} ≃ ℂ^{d_{λ}×d_{λ}} ,  (44)

where d_{λ} denotes the dimension^{6} of any minimal left ideal from the equivalence class of λ. Furthermore, the group ring ℂ[S_{r}] is isomorphic to an algebra of block diagonal matrices:

ℂ[S_{r}] = ⨁_{λ⊢r} I_{λ} ≃ ⨁_{λ⊢r} ℂ^{d_{λ}×d_{λ}} .  (45)

Definition 1 Every isomorphism D : ℂ[S_{r}] → ⨁_{λ⊢r} ℂ^{d_{λ}×d_{λ}} of ℂ-algebras is called a discrete Fourier transform for ℂ[S_{r}] (or simply, for S_{r}).

6d_{λ} can be calculated from λ by means of the hook length formula (see e.g. [1, p.101], [9, p.81] or [7]).

We denote by D^{λ} the natural projections D^{λ} : ℂ[S_{r}] → ℂ^{d_{λ}×d_{λ}} of D which form a complete list of pairwise inequivalent irreducible representations of ℂ[S_{r}]. Then D can be written as

D : a ↦ A = diag(A^{(λ)} ; λ ⊢ r) = ( \begin{matrix}A^{(λ_{1})} \\ & . & . & . \\ & & & & A^{(λ_{m})} \end{matrix} )

a ∈ ℂ[S_{r}] , A^{(λ)} = D^{λ}(a) ∈ ℂ^{d_{λ}×d_{λ}} .

Clausen and Baum have shown that the isomporphism σ : ℂ[S_{r}] → ⨁_{λ⊢r} ℂ^{d_{λ}×d_{λ}}, called Young’s seminormal form, represents a discrete Fourier transform of S_{r} which can be handled by fast algorithms. In [3, chapter 9] they present efficient algorithms for the evaluation of σ and σ^{−1} (see also [4]). Upper bounds of the number of arithmetic operations for these evaluations are

σ :  (\frac{5}{12} r^{3} + \frac{1}{2} r^{2} − \frac{11}{12} r) r!
σ^{−1} :  (\frac{5}{12} r^{3} + \frac{4}{3} \sqrt{2} r^{3/2} + \frac{7}{12} r) r! .

Descriptions of Young’s seminormal form can be found e.g in [2], [9, pp.75,76], [8], [3], [4].

Now it is clear that the use of the Fourier transform σ can essentially improve the efficiency of our algorithms (L) and (R) in the case of large symmetric groups S_{r} . Instead of a group ring product a · b we can calculate A · B with A = σ(a) and B = σ(b) which can be done by isolated calculations of the block products A^{(λ)} · B^{(λ)} for all λ ⊢ r. If these blocks are large matrices we could employ algorithms for fast matrix multiplication.

Since σ is an isomorphism of ℂ-algebras, the complete decomposition algorithms (L) and (R) can be carried out in the space σ(ℂ[S_{r}]) of the Fourier transforms. We have to determine Fourier transforms only for the given input data, i.e. generating or annihilating elements of given ideals, and to calculate inverse Fourier transforms only for the results of the algorithms. Again, all calculations within the scope of these algorithms can be done blockwise.

There are two points on which the decomposition algorithms for σ(ℂ[S_{r}]) should be modified.

(i) It is not necessary, to use Fourier transforms σ(y_{t}) of Young symmetrizers y_{t}. We can replace the primitive idempotents σ(y_{t}) by other natural primitive idempotents Z_{(k)} of ℂ^{d_{λ}×d_{λ}}.

Proposition 10 Let Z_{(k)} ∈ ℂ^{d_{λ}×d_{λ}}, 1 ≤ k ≤ d_{λ}, be the matrix the elements z_{(k),ij} of which fulfil

z_{(k),ij} = \{ \begin{matrix}1 & if i = j = k \\ 0 & else \end{matrix} .

Then the matrices Z_{(1)}, …, Z_{(d_{λ})} form a set of primitive pairwise orthogonal idempotents, generating minimal left or right ideals, and ℂ^{d_{λ}×d_{λ}} decomposes into

ℂ^{d_{λ}×d_{λ}} = ⨁_{k=1}^{d_{λ}} ℂ^{d_{λ}×d_{λ}} · Z_{(k)} = ⨁_{k=1}^{d_{λ}} Z_{(k)} · ℂ^{d_{λ}×d_{λ}} .  (46)

Proof. The proof, that the Z_{(k)} form a set of pairwise orthogonal idempotents, is trivial. For every matrix A ∈ ℂ^{d_{λ}×d_{λ}} the product A · Z_{(k)} (or Z_{(k)} · A) is a matrix, the k-th column (row) of which is equal to the k-th column (row) of A, whereas all other elements vanish. Consequently, the left ideal I_{k} := ℂ^{d_{λ}×d_{λ}} · Z_{(k)} and the right ideal J_{k} := Z_{(k)} · ℂ^{d_{λ}×d_{λ}} have both the dimension d_{λ} such that they have to be minimal since σ^{−1}(I_{k}) and σ^{−1}(J_{k}) turn out to be minimal in ℂ[S_{r}] because of their dimensions. Relation (46) follows simply from the column structure or the row structure of the matrices A · Z_{(k)} or Z_{(k)} · A, respectively. □

If we use the idempotents Z_{(k)} instead of σ(y_{t}) in every matrix algebra ℂ^{d_{λ}×d_{λ}}, then the transfers of the propositions 1 and 3 and of the algorithms (L) and (R) to σ(ℂ[S_{r}]) keep their validity.

(ii) The search process for permutations p which satisfy inequalities as (8), (11) and (12) can be replaced by a simple search of non-vanishing elements in matrices.

Proposition 11 Let E ∈ ℂ^{d×d} be a primitive idempotent of ℂ^{d×d}, d ≥ 2, and let W ∈ ℂ^{d×d} be a matrix with E · W ≠ 0. Search for a non-vanishing element^{7} in each of the matrices E and E·W. If such non-vanishing elements have been found in the j_{0}-th column of E · W and the k_{0}-th row of E, then the matrix P = (p_{jk}) with p_{j_{0}k_{0}} = 1 and p_{jk} = 0 else fulfils

E · W · P · E ≠ 0 .

Thus we can determine matrices P which satisfy the transfers of the conditions (8), (11) and (12) to σ(ℂ[S_{r}]) by means of proposition 11. We remark that, in general, σ^{−1}(P) is not a permutation but some group ring element of ℂ[S_{r}]. However, the idempotent constructions of the propositions 1 and 3 remain correct if we use group ring elements instead of the original permutations p satisfying (8), (11) or (12). (See also the remark after the proof of proposition 1.)

Our considerations have the remarkable consequence that the algorithms (L) and (R) can be regarded as algorithms for the decomposition of left or right ideals of arbitrary matrix algebras ℂ^{d×d}, independent of their connection with group rings. This statement is supported by the fact that for every natural number d ≥ 2 the hook length formula yields a dimension d_{λ} = d for the partition λ = (d 1) ⊢ d + 1, i.e. ℂ^{d×d} is isomorphic to the two-sided ideal I_{λ} ⊂ ℂ[S_{d+1}] belonging to that partition λ.

7Such non-vanishing elements exist because of E · W ≠ 0.

20 B. Fiedler

Proposition 12 For every matrix algebra ℂ^{d×d}, d ≥ 2, the transfers of the algorithms (L) and (R) to ℂ^{d×d} can be used to decompose left or right ideals of ℂ^{d×d}, corresponding to all types of ideals from sections 2 and 3, into minimal (left or right) ideals and to determine generating idempotents of these ideals, decomposed in primitive pairwise orthogonal idempotents according to the ideal decomposition.

Example.^{8} We determine a decomposition of the left ideal I = ℂ^{3×3} · A given by the matrix

A = ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} ) .

Let Z_{(1)}, Z_{(2)}, Z_{(3)} be the idempotents of ℂ^{3×3} described in proposition 10. Since Z_{(1)}·A ≠ 0 we obtain I_{1} := ℂ^{3×3} ·Z_{(1)} ·A as first minimal subideal of I. Further there is Z_{(1)} ·A·Z_{(1)} ·Z_{(1)} ≠ 0 such that proposition 1 yields as generating idempotent of I_{1}

E_{1} = Z_{(1)} · Z_{(1)} · A = ( \begin{matrix}1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) .

Next we check Z_{(2)} ·A ≠ 0 and Z_{(2)} ·A·E_{1} ≠ Z_{(2)} ·A such that the next minimal subideal of I is I_{2} := ℂ^{3×3}·Z_{(2)}·A. I_{1} and I_{2} form a direct sum Ĩ_{2} = I_{1}⊕I_{2} ⊆ I. There is Z_{(2)}·A·Z_{(2)}·Z_{(2)} ≠ 0 such that the construction of proposition 1 gives

E_{2} = \frac{1}{5} Z_{(2)} · Z_{(2)} · A = ( \begin{matrix}0 & 0 & 0 \\ 4/5 & 1 & 6/5 \\ 0 & 0 & 0 \end{matrix} )

as a generating idempotent of I_{2}.

Now we have to orthogonalize E_{1} and E_{2}. Taking into account

Id − E_{2} = ( \begin{matrix}1 & 0 & 0 \\ −4/5 & 0 & −6/5 \\ 0 & 0 & 1 \end{matrix} ) ,

we can check E_{1}·(Id−E_{2})·Z_{(1)}·E_{1} ≠ 0. Thus we can make an ansatz F_{1} = E_{1}−X·E_{1}+E_{1}·X·E_{1} with X = λ (Id − E_{2}) · Z_{(1)} for a new idempotent F_{1} of I_{1} according to proposition 3. The condition E_{2} · F_{1} = 0 leads to λ = 5/3 and

F_{1} = ( \begin{matrix}−5/3 & −10/3 & −5 \\ 4/3 & 8/3 & 4 \\ 0 & 0 & 0 \end{matrix} ) .

Next we obtain

F_{1} · (Id − E_{2}) = ( \begin{matrix}1 & 0 & −1 \\ −4/5 & 0 & 4/5 \\ 0 & 0 & 0 \end{matrix} )

and F_{1} · (Id − E_{2}) · Z_{(1)} · F_{1} ≠ 0 such that we can use the ansatz F_{2} = E_{2} − X · E_{2} with X = λ (Id − E_{2}) · Z_{(1)} · F_{1}. Now the condition F_{1} · F_{2} = 0 yields λ = 1 and

F_{2} = ( \begin{matrix}8/3 & 10/3 & 4 \\ −4/3 & −5/3 & −2 \\ 0 & 0 & 0 \end{matrix} ) .

8All calculations of this example have been carried out by means of Mathematica 2.2 [18].

Then Ĩ_{2} has the generating idempotent

F̃_{2} = F_{1} + F_{2} = ( \begin{matrix}1 & 0 & −1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{matrix} ) .

Since Z_{(3)} · A ≠ 0 but Z_{(3)} · A · F̃_{2} = Z_{(3)} · A we finish with I = Ĩ_{2} = ℂ^{3×3} · F̃_{2} .

6 Application of the decomposition algorithms to investigations of tensors

In this section we summarize shortly ideas from [6] which refer to applications of our algorithms to investigations of symmetry properties of tensors and to problems of reduction of tensor expressions arising in symbolic computer calculations.

We make use of the following connection between tensors and elements of the group ring of a symmetric group. Let T_{r}V be the space of all complex-valued covariant tensors of order r on a vector space V over the field of complex numbers ℂ. The tensors T ∈ T_{r}V are multilinear mappings of the r-fold cartesian product of V onto ℂ,

T : \underbrace{V × V × ... × V}_{r factors} → ℂ , (v_{1}, …, v_{r}) ↦ T (v_{1}, …, v_{r}) .

Let T ∈ T_{r}V be a covariant tensor of order r and let b := {v_{1}, …, v_{r}} ⊂ V be an arbitrary subset of r vectors from V. Then T and b induce a complex-valued function T_{b} on the symmetric group S_{r}

T_{b} : S_{r} → ℂ , T_{b} : p ↦ T_{b}(p) := T (v_{p(1)}, …, v_{p(r)})

which we will identify with the group ring element ∑_{p∈S_{r}} T_{b}(p) p denoted by T_{b}, too. The action of a group ring element a = ∑_{p∈S_{r}} a(p)p ∈ ℂ[S_{r}] on a tensor T is defined by

a : T ↦ aT , (aT)_{i_{1}...i_{r}} := ∑_{p∈S_{r}} a(p) T_{i_{p(1)}...i_{p(r)}} .

Using the involution ∗ from (22) one can show by a straightforward calculation (see [6])

(aT)_{b} = T_{b} · a^{∗} .  (47)

Now we consider tensors which possess a symmetry relating to permutations of their indices.

Definition 2 We call a pair (C, ϵ) a tensor symmetry, if C ⊆ S_{r} is a subgroup of the symmetric group S_{r} and ϵ : C → S^{1} is a homomorphism of C onto a finite subgroup of the group of the unimodular numbers S^{1} := {z ∈ ℂ | |z| = 1}. We say that a tensor T ∈ T_{r}V possesses the symmetry (C, ϵ), if

∀c ∈ C : cT = ϵ(c) T .  (48)

The T_{b} of a tensor with a tensor symmetry lie in a special left ideal.

Proposition 13 Let (C, ϵ), C ⊆ S_{r}, be a tensor symmetry. Then the group ring element

ϵ := ∑_{c∈C} ϵ(c) c ∈ ℂ[S_{r}] ,  (49)

is essentially idempotent. Furthermore, every T_{b} of a covariant tensor T ∈ T_{r}V with the symmetry (C, ϵ) is contained in the left ideal I := ℂ[S_{r}] · ϵ of ℂ[S_{r}].

Proof. There holds true ϵ(c) ϵ · c = ϵ for all c ∈ C since

ϵ(c) ϵ · c = ∑_{c′∈C} ϵ(c)ϵ(c′) c′ · c = ∑_{c′′∈C} ϵ(c)ϵ(c′′ · c^{−1}) c′′ = ∑_{c′′∈C} ϵ(c′′)c′′ = ϵ.

Thus we obtain ϵ · ϵ = ∑_{c∈C} ϵ(c) ϵ · c = |C| ϵ, i.e. ϵ is essentially idempotent.

Because of (47) equation (48) turns into T_{b} · c^{−1} = ϵ(c) T_{b} or T_{b} = ϵ(c) T_{b} · c for every vector set b = {v_{1}, …, v_{r}} ⊂ V. Then the sum of these relations over all c ∈ C yields |C| T_{b} = T_{b} · ϵ, i.e. T_{b} lies in the left ideal ℂ[S_{r}] · ϵ. □

Now, let us consider tensors T which satisfy a certain system of linear identities.

Proposition 14 Let T ∈ T_{r}V be a covariant tensor which fulfils a system of m linear identities

u_{j}T = 0 , j = 1, …, m ,  (50)

given by m group ring elements u_{1}, …, u_{m} ∈ ℂ[S_{r}]. Then every T_{b} of T lies in the intersection J = ⋂_{k=1}^{m} J_{k} of those left ideals J_{k} of ℂ[S_{r}] which are annihilated by the group ring elements u_{k}^{∗}, i.e. J_{k} := {f ∈ ℂ[S_{r}] | f · u_{k}^{∗} = 0}.

Proof. On account of (47) the relations (50) are equivalent to

∀b = {v_{1}, v_{2}, …, v_{r}} ⊂ V :  T_{b} · u_{j}^{∗} = 0 , j = 1, 2, ..., m . □

The summary of propositions 13 and 14 reads: If T ∈ T_{r}V is a tensor which possesses a tensor symmetry and/or satisfies linear identities, then all T_{b} of T lie in the intersection

I = ⋂_{j=1}^{m} I_{j}

of certain left ideals I_{j} ⊆ ℂ[S_{r}] which are given by generating or annihilating elements. Using proposition 6 we can construct a generating idempotent e = e_{1} +…+e_{n} of the intersection I and a decomposition of e into primitive pairwise orthogonal idempotents e_{k}. Then this idempotent e decomposes every T_{b} of T since we can write

∀ b = {v_{1}, …, v_{r}} ⊂ V : T_{b} = T_{b} · e = T_{b} · e_{1} + … + T_{b} · e_{n} .

This relation is equivalent to

T = e_{1}^{∗}T + … + e_{n}^{∗}T .  (51)

Formula (51) is a decomposition of the tensor T into parts belonging to so-called symmetry classes^{9} which are generated by the idempotents e_{k}^{∗} (see [1, p.127]).

The knowledge of a decomposition (51) of a tensor T can be very helpful in solving reduction problems which occur with symbolic tensor calculations by a computer. Let us consider a tensor expression τ which is a complex linear combination of certain isomers of a tensor T ∈ T_{r}V,

τ_{i_{1}...i_{r}} = ∑_{p∈P} β_{p} T_{i_{p(1)}...i_{p(r)}} , β_{p} ∈ ℂ , P ⊆ S_{r} ,  (52)

where the sum runs over a subset P of the symmetric group S_{r}. We assume that all T_{b}, belonging to T, lie in a left ideal I := ℂ[S_{r}] · a with known generating element a. Then there arises the problem to determine linear dependences between the terms T_{i_{p(1)}...i_{p(r)}} and to reduce (52) to a linear combination of linearly independent terms.

Lemma 5 A relation (52) exists between τ, T ∈ T_{r}V if and only if there holds true

∀ b = {v_{1}, …, v_{r}} ⊂ V : τ_{b}(id) = ∑_{p∈P} β_{p} T_{b}(p) .  (53)

Proof. (52) is equivalent to

∀ b = {v_{1}, …, v_{r}} ⊂ V : τ_{i_{1}...i_{r}} v_{1}^{i_{1}} … v_{r}^{i_{r}} = ∑_{p∈P} β_{p} T_{i_{p(1)}...i_{p(r)}}v_{1}^{i_{1}} … v_{r}^{i_{r}}

which can be written as (53). □

A set of complex numbers {x_{p} | p ∈ S_{r}} determines a linear identity for all elements of the left ideal I if

∀ f ∈ I : ∑_{p∈S_{r}} x_{p}f(p) = 0 .  (54)

9Let K be a right ideal of ℂ[S_{r}]. Then the symmetry class of tensors from T_{r}V characterized by K is the subspace S_{K} := {fT | f ∈ K , T ∈ T_{r}V } of T_{r}V. Every generating idempotent e of K generates the symmetry class S_{K}, i.e. S_{K} = {eT | T ∈ T_{r}V }.

If we know a non-trivial identity (54) with x_{p} = 0 for all p ∈ S_{r} \ P, we can use it to eliminate a term T_{b}(p) in (53). This leads to reduced variants of (53), (52)

τ_{b}(id) = ∑_{p∈P̃} β̃_{p} T_{b}(p) , τ_{i_{1}...i_{r}} = ∑_{p∈P̃} β̃_{p} T_{i_{p(1)}...i_{p(r)}} , P̃ ⊂ P .

Since every f ∈ I = ℂ[S_{r}] · a can be written as f = g · a = ∑_{p,p′∈S_{r}} g(p)a(p′)p · p′ with a g ∈ ℂ[S_{r}], we obtain from (54)

∀g ∈ ℂ[S_{r}] : ∑_{p∈S_{r}} ( ∑_{p′∈S_{r}} a(p^{−1} · p′)x_{p′})g(p) = 0 .

From this relation there follows the homogeneous linear equation system

∑_{p′∈S_{r}} a(p^{−1} · p′)x_{p′} = 0 , p ∈ S_{r}  (55)

for the numbers x_{p} that describe the linear identities of I. The coefficient matrix A := [a(p^{−1} · p′)]_{p,p′∈S_{r}} of (55) is a S_{r}-circulant of a ∈ ℂ[S_{r}] (see [3, p.141]).

The set {p·a | p ∈ S_{r}} generates the left ideal I = ℂ[S_{r}]·a and can be reduced to a basis of I. Because

p · a = ∑_{p′∈S_{r}} a(p′)p · p′ = ∑_{p′′∈S_{r}} a(p^{−1} · p′′)p′′ ,

we see that

rank A = dim I .  (56)

Now, if a decomposition (51) of T is known we can write (53) as

τ_{b}(id) = ∑_{k=1}^{n} ∑_{p∈P} β_{p} (e_{k}^{∗}T)_{b}(p)  (57)

and reduce the subsums ∑_{p∈P} β_{p} (e_{k}^{∗}T)_{b}(p) separately. The (e_{k}^{∗}T)_{b} lie in the minimal left ideals I_{k} := ℂ[S_{r}] · e_{k} since (e_{k}^{∗}T)_{b} = T_{b} · e_{k}. Then the equation system of type (55) for the reduction identities belonging to an ideal I_{k} possesses the circulant E_{k} of e_{k} as coefficient matrix. But rank E_{k} = dim I_{k} is much smaller than rank A = dim I such that we have better conditions to solve (55).

Further details of the handling of a system (55) can be found in [6]. In particular, a method is described in [6] which allows to determine a set of linearly independent rows of a system (55) without using the Gaussian algorithm.

References

[1] H. Boerner. Darstellungen von Gruppen, volume 74 of Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Springer-Verlag, Berlin, Göttingen, Heidelberg, 1955.

[2] H. Boerner. Representations of Groups. North-Holland Publishing Company, Amsterdam, 2. revised edition, 1970.

[3] M. Clausen and U. Baum. Fast Fourier Transforms. BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich, 1993.

[4] M. Clausen and U. Baum. Fast Fourier transforms for symmetric groups. In L. Finkelstein and W.M. Kantor, editors, Groups and Computation, volume 11 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 27 – 39, Providence, Rhode Island, 1993. DIMACS, American Mathematical Society. The DIMACS workshop on Groups and Computation was held at DIMACS, Rutgers University, Oct. 7 – 10, 1991.

[5] B. Fiedler. PERMS 2.1. Mathematisches Institut, Universität Leipzig, Leipzig, 1997. Will be sent in to MathSource, Wolfram Research Inc.

[6] B. Fiedler. A use of ideal decomposition in the computer algebra of tensor expressions. Z. f. Analysis u. ihre Anw., 16(1):145 – 164, 1997.

[7] S.A. Fulling, R.C. King, B.G. Wybourne, and C.J. Cummins. Normal forms for tensor polynomials: I. The Riemann tensor. Class. Quantum Grav., 9:1151 – 1197, 1992.

[8] G.D. James and A. Kerber. The Representation Theory of the Symmetric Group, volume 16 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company, Reading, Mass., London, Amsterdam, Don Mills, Ont., Sidney, Tokyo, 1981.

[9] A. Kerber. Representations of Permutation Groups, volume 240, 495 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, Heidelberg, New York, 1971, 1975.

[10] D.E. Littlewood. The Theory of Group Characters and Matrix Representations of Groups. Clarendon Press, Oxford, 2. edition, 1950.

[11] I.G. Macdonald. Symmetric Functions and Hall Polynomials. Clarendon Press, Oxford, 1979.

[12] W. Müller. Darstellungstheorie von endlichen Gruppen. Teubner Studienbücher Mathematik. B. G. Teubner, Stuttgart, 1980.

[13] M.A. Naimark and A.I. Štern. Theory of Group Representations, volume 246 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, Heidelberg, New York, 1982.

[14] D.S. Passman. The Algebraic Structure of Group Rings. Pure and Applied Mathematics. John Wiley & Sons, New York, London, Sydney, Toronto, 1977.

[15] F. Sänger. Plethysmen von irreduziblen Darstellungen symmetrischer Gruppen. Dissertation, Rheinisch-Westfälische Technische Hochschule, Mathematisch-Naturwissenschaftliche Fakultät, Aachen, 1980.

[16] B.L. van der Waerden. Algebra, volume I, II. Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, Hong Kong, Barcelona, Budapest, 9., 6. edition, 1993.

[17] H. Weyl. The Classical Groups, their Invariants and Representations. Princeton University Press, Princeton, New Jersey, 1939.

[18] S. Wolfram. Mathematica. Addison-Wesley, Bonn, München, Paris, Reading, Mass., 2. edition, 1992. In German.