Séminaire Lotharingien de Combinatoire 45 (2001), Article B45g

IDEAL DECOMPOSITIONS AND COMPUTATION OF TENSOR NORMAL FORMS

BERND FIEDLER

Abstract. Symmetry properties of r-times covariant tensors T can be described by certain linear subspaces W of the group ring 𝕂[S_{r}] of a symmetric group S_{r}. If for a class of tensors T such a W is known, the elements of the orthogonal subspace W^{⊥} of W within the dual space 𝕂[S_{r}]^{∗} of 𝕂[S_{r}] yield linear identities needed for a treatment of the term combination problem for the coordinates of the T. We give the structure of these W for every situation which appears in symbolic tensor calculations by computer. Characterizing idempotents of such W can be determined by means of an ideal decomposition algorithm which works in every semisimple ring up to an isomorphism. Furthermore, we use tools such as the Littlewood-Richardson rule, plethysms and discrete Fourier transforms for S_{r} to increase the efficience of calculations. All described methods were implemented in a Mathematica package called PERMS.

1. The Term Combination Problem for Tensors

The use of computer algebra systems for symbolic calculations with tensor expressions is very important in differential geometry, tensor analysis and general relativity theory. The investigations of this paper^{1} are motivated by the following term combination problem or normal form problem which occurs within such calculations.

Let us consider real or complex linear combinations

(1.1)  τ = ∑_{i=1}^{n} α_{i}T_{(i)} , α_{i} ∈ ℝ, ℂ

of expressions T_{(i)} which are formed from the coordinates of certain tensors A, B, C, … by multiplication and, possibly, contractions of some pairs of indices. An example of such an expression is

A_{iabc} A_{jkd}^{a} B_{e}^{bd} C^{ec} . (1.2)

In (1.2) we use Einstein’s summation convention. Further we assume that each of the numbers of A, B, C, … is constant if we run through the set of the T_{(i)}. Now we aim to carry out symbolic calculations with expressions of the type (1.1), (1.2)

Date: December 2000. 1991 Mathematics Subject Classification. 16D60, 15A72, 05E10, 16D70, 16S50, 05-04. 1This paper is a summary of our Habilitationsschrift [10], where all proofs can be found. A

part of the proofs were published in earlier papers [8, 9, 12], too. An abridged version of this summary is the paper [13].

according to the rules of the Ricci calculus. We assume that there is a metric tensor g which allows us to raise or lower indices, for instance

T_{i}^{jkb} = g^{bc} T_{i c}^{jk} , T_{ia k}^{j} = g_{ac} T_{i k}^{cj} .

If now the tensors A, B, C, … have symmetries and/or fulfil linear identities^{2}, then there exist relations between the T_{(i)} in (1.1). (We restrict us to linear relations.) Thus the problem arises to detect such relations in sums (1.1), generated by symbolic calculations, and to reduce (1.1) to linear combinations of linearly independent T_{(i)} (normal forms).

It is well-known that the representation theory of symmetric groups S_{r} yields powerful tools to treat this term combination problem. The connection between tensors and the representation theory of S_{r} has been considered already in books of J.A. Schouten [26] (1924), H. Weyl [27] (1939) and H. Boerner [2] (1955). In the 1940s Littlewood has developed and used tools such as the Littlewood-Richardson rule and plethysms for the investigation of tensors (see S.A. Fulling et al. [14] (references) and D.E. Littlewood [20] (appendix)).

Applying the same methods, Fulling, King, Wybourne and Cummins [14] have calculated large lists of normal form terms of polynomials of the Riemann curvature tensor and its covariant derivatives (by means of the program package Schur [28]). In their paper [14] they formulated the following steps to solve the above term combination problem for tensors:

(a) Generate the space spanned by the set of homogeneous monomials of a definite ’order’ or ’degree of homogeneity’ formed from the coordinates of tensors of relevance by multiplication and index-pair contraction.

(b) Construct a basis of this space (normal forms).

(c) Present an algorithm for expressing an arbitrary element of the space in

terms of the basis. Our present paper yields a method to solve (b) and (c) for arbitrary tensors.

2. Tensors and the Group Ring of a Symmetric Group

We make use of the following connection between r-times covariant tensors T ∈ T_{r}V over a finite-dimensional 𝕂-vector space V and elements of the group ring 𝕂[S_{r}] of a symmetric group S_{r} over a field 𝕂 = ℝ or 𝕂 = ℂ.

Definition 2.1. Any tensor T ∈ T_{r}V and any r-tuple b := (v_{1}, …, v_{r}) ∈ V^{r} of r vectors from V induce a function T_{b} : S_{r} → 𝕂 according to the rule

(2.1)  T_{b}(p) := T (v_{p(1)}, …, v_{p(r)}) , p ∈ S_{r} .

We identify this function with the group ring element T_{b} := ∑_{p∈S_{r}} T_{b}(p) p ∈ 𝕂[S_{r}].

2For instance, the Riemann tensor has the symmetry R_{ijkl} = −R_{jikl} = −R_{ijlk} = R_{klij} and fulfils R_{ijkl} + R_{iklj} + R_{iljk} = 0. See P. Günther [15] for a large collection of identities for the curvature tensor, Weyl tensor, etc. and covariant derivatives of these tensors.

We allow the linear dependence of the v_{i} and repetitions of vectors in the above r-tuple b. Obviously, two tensors S, T ∈ T_{r}V fulfil S = T iff S_{b} = T_{b} for all b ∈ V^{r}.

We try to describe symmetry properties of tensors with the help of the T_{b} by the following principle: If a ”class” of tensors with a certain symmetry property is given, then we search such a linear subspace W ⊆ 𝕂[S_{r}] that contains all T_{b} of the tensors from the ”class” being considered. The linear identities which characterize W yield then identities for the coordinates of the T which can be used in the treatment of the term combination problem.

Every a = ∑_{p∈S_{r}} a(p) p ∈ 𝕂[S_{r}] acts as so-called symmetry operator a : T ↦ aT on tensors T ∈ T_{r}V if we define

(2.2)  (aT)(v_{1}, …, v_{r}) := ∑_{p∈S_{r}} a(p) T (v_{p(1)}, …, v_{p(r)}) , v_{i} ∈ V.

We denote by ’∗’ the mapping ∗ : a = ∑_{p∈S_{r}} a(p) p ↦ a^{∗} := ∑_{p∈S_{r}} a(p) p^{−1}. Furthermore, if p ∈ S_{r} and b = (v_{1}, …, v_{r}) ∈ V^{r}, then we denote by pb the r-tuple pb := (v_{p(1)}, …, v_{p(r)}). Many of our calculations are based on

Lemma 2.2. ^{3} If a = ∑_{q∈S_{r}} a(q) q ∈ 𝕂[S_{r}], T ∈ T_{r}V, p, q ∈ S_{r} and b = (v_{1}, …, v_{r}) ∈ V^{r}, then we have

(2.3)  T_{b}(p ∘ q) = (qT)_{b}(p) = T_{pb}(q)
(2.4)  q(pb) = (p ∘ q)b
(2.5)  (aT)_{b} = T_{b} · a^{∗}
(2.6)  T_{b} = p · T_{pb} .

The following symmetry concepts are used for tensors. (See B. Fiedler [10, Sec.III.2] and B. Fiedler [12]. See also R. Merris [22, pp.151,153,157], H. Boerner [2, p.127], G. Eisenreich [7, p.601].)

Definition 2.3. (a) Let 𝔯 ⊆ 𝕂[S_{r}] be a right ideal of 𝕂[S_{r}] for which an a ∈ 𝔯 and a T ∈ T_{r}V exist such that aT ≠ 0. Then the tensor set T_{𝔯} := {aT | a ∈ 𝔯 , T ∈ T_{r}V } is called the symmetry class of tensors defined by 𝔯.

(b) Let a_{1}, …, a_{n} ∈ 𝕂[S_{r}] be a finite set of group ring elements. We say that a tensor T ∈ T_{r}V possesses a symmetry defined by a_{1}, …, a_{n} if T satisfies the linear equation system a_{i}T = 0, (i = 1, …, n).

If e is a generating idempotent of a right ideal 𝔯 = e · 𝕂[S_{r}] that defines a symmetry class T_{𝔯} then T_{𝔯} fulfils T_{𝔯} = {eT | T ∈ T_{r}V } and a tensor T ∈ T_{r}V belongs to T_{𝔯} iff eT = T. (See H. Boerner [2, p.127] or B. Fiedler [10, Sec.III.2.1].)

Now it can be shown that all T_{b} of tensors T which have a symmetry (a) or (b) lie in a certain left ideal of 𝕂[S_{r}].

3See B. Fiedler [10, Sec.III.1] and B. Fiedler [12].

Proposition 2.4.^{4} Let e ∈ 𝕂[S_{r}] be an idempotent. Then a T ∈ T_{r}V fulfils the condition eT = T iff T_{b} ∈ 𝔩 := 𝕂[S_{r}] · e^{∗} for all b ∈ V^{r}, i.e. all T_{b} of T lie in the left ideal 𝔩 generated by e^{∗}. Proposition 2.5.^{5} Let a_{1}, …, a_{m} ∈ 𝕂[S_{r}] be given group ring elements. A T ∈ T_{r}V satisfies a system of linear identities a_{i}T = 0 , (i = 1, …, m), iff T_{b} ∈ 𝔩 := {x ∈ 𝕂[S_{r}] | x · a_{i}^{∗} = 0 , i = 1, …, m} for all b ∈ V^{r}, i.e. all T_{b} of T lie in the left annihilator ideal 𝔩 of the set {a_{1}^{∗}, …, a_{m}^{∗}}.

The proofs follow easily from (2.5). A further result is

Proposition 2.6. ^{6} If dim V ≥ r, then every left ideal 𝔩 ⊆ 𝕂[S_{r}] fulfils 𝔩 = L_{𝕂}{T_{b} | T ∈ T_{𝔩^{∗}} , b ∈ V^{r}}. (Here L_{𝕂} denotes the forming of the linear closure.)

If dim V < r, then the T_{b} of the tensors from T_{𝔩^{∗}} will span only a linear subspace of 𝔩 in general.

In the case of tensors T with index contractions the role of the T_{b} is played by certain sums ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b}, which we now define.

Definition 2.7. Let g ∈ T_{2}V be a fundamental tensor with arbitrary signature on V and B = {n_{1}, …, n_{d}} be an orthonormal basis of V with respect to g. Further let r, l be integers with 2 ≤ 2l < r and b_{0} = (v_{2l+1}, …, v_{r}) ∈ B^{r−2l} be a fixed (r − 2l)-tuple of vectors from B. Then we denote by 𝔅_{b_{0}} the set ^{7} of r-tuples of basis vectors

𝔅_{b_{0}} := {(w_{1}, w_{1}, w_{2}, w_{2}, …, w_{l}, w_{l}, v_{2l+1}, …, v_{r}) ∈ B^{r} | (w_{1}, …, w_{l}) ∈ B^{l}} .

Moreover, we set γ_{b} := ∏_{i=1}^{l} g(w_{i}, w_{i}) ∈ {1, −1} for every b ∈ 𝔅_{b_{0}}.

Proposition 2.8.^{8} Let T ∈ T_{r}V be a tensor and g ∈ T_{2}V be a fundamental tensor. We determine all tensor coordinates with respect to an orthonormal basis B = {n_{1}, …, n_{d}} of V. Let b_{0} = (n_{i_{2l+1}}, …, n_{i_{r}}) ∈ B^{r−2l} be a fixed (r − 2l)-tuple of basis vectors. Then

(2.7)  ∑_{p∈S_{r}} (pT)_{j_{1} j_{2} ... j_{l} i_{2l+1}...i_{r}}^{j_{1} j_{2} ... j_{l}} p = ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} .

Due to Prop. 2.8 the ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} are objects which contain information about the tensor coordinates of T with l index-pair contractions. In the case of tensors T with index contractions we search for linear subspaces W ⊆ 𝕂[S_{r}] which contain all ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} for a fixed b_{0}.

4See B. Fiedler [12] or B. Fiedler [10, Prop. III.2.5, III.3.1, III.3.4].

5See B. Fiedler [12] or B. Fiedler [10, Prop. III.3.3, III.3.4].

6See B. Fiedler [12] or B. Fiedler [10, Prop. III.2.6].

7We set b_{0} := ∅ and 𝔅_{∅} := {(w_{1}, w_{1}, w_{2}, w_{2}, …, w_{l}, w_{l}) ∈ B^{r} | (w_{1}, …, w_{l}) ∈ B^{l}} in the case r = 2l > 0.

8See B. Fiedler [12] or B. Fiedler [10, Prop. III.3.31].

The left ideals 𝔩 from the Propositions 2.4, 2.5 and 2.6 are the simplest examples of linear subspaces W describing tensor symmetries. Before we give such subspaces W in more complicated cases, we will explain how they can be used in the treatment of the term combination problem for tensors.^{9}

3. The Treatment of the Term Combination Problem

The term combination problem from Sec. 1 can be reformulated as the problem to find all linear identities between the summands of given tensor expressions

(3.1)  τ_{i_{1}...i_{r}} := ∑_{p∈P} c_{p} T_{i_{p(1)}...i_{p(r)}} , c_{p} ∈ 𝕂 , P ⊆ S_{r} or
(3.2)  τ_{i_{2l+1}...i_{r}} := ∑_{p∈P} c_{p} (pT)_{j_{1} j_{2} ... j_{l} i_{2l+1}...i_{r}}^{j_{1} j_{2} ... j_{l}} , c_{p} ∈ 𝕂 , P ⊆ S_{r}

where T ∈ T_{𝔩^{∗}} is a tensor from a given symmetry class defined by a left ideal 𝔩 (or a right ideal 𝔯 = 𝔩^{∗}). We assume that (3.1) and (3.2) are results of symbolic computer calculations. P is a subset of permutations, which is determined by the concrete form of the given expressions (3.1) or (3.2).

Let W ⊆ 𝔩 be a linear subspace which contains all T_{b} or ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} of T. If we consider the orthogonal subspace W^{⊥} := {x ∈ 𝕂[S_{r}]^{⋆} | ∀ w ∈ W : ⟨x, w⟩ = 0} of W, then every x ∈ W^{⊥} yields a linear identity for the coordinates of T since

(3.3) 0 = ⟨x, T_{b}⟩ = ∑_{p∈S_{r}} x_{p} T_{b}(p) = ∑_{p∈S_{r}} x_{p} T_{i_{p(1)}...i_{p(r)}} or
0 = ⟨x, ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b}⟩ = _{∑_{b∈𝔅_{b_{0}}} ; p∈S_{r}}γ_{b} T_{b}(p) x_{p} = ∑_{p∈S_{r}} x_{p} (pT)_{j_{1} ... j_{l} i_{2l+1}...i_{r}}^{j_{1} ... j_{l}}

where x_{p} := ⟨x, p⟩, p ∈ S_{r}. (The last steps are correct if all b occurring in (3.3) are r-tuples of basis vectors of V.) Every identity (3.3) can be used to eliminate certain summands in (3.1), (3.2). If W is spanned by all T_{b} or ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} of the tensors considered, then W^{⊥} contains all linear identities which are possible between summands of expressions (3.1), (3.2) (compare Prop. 2.6).

If a basis {h_{1}, …, h_{k}} of W is known, then the coefficients x_{p} of the x ∈ W^{⊥} can be obtained from the linear equation system

(3.4)  ⟨x, h_{i}⟩ = ∑_{p∈S_{r}} h_{i}(p) x_{p} = 0  (i = 1, …, k) .

Thus an important goal is to find such a basis {h_{1}, …, h_{k}} of W. (An efficient algorithm for that purpose is given in Prop. 5.1.)

Note that (3.4) is a very large system with a (k × r!)-coefficient matrix, k = dim W. However, since we only need identities to reduce sums (3.1), (3.2), we can restrict us to solutions of (3.4) which fulfil x_{p} = 0 for p ∈ S_{r} \ P. This reduces the number of columns to |P|. Furthermore, every of our spaces W is a linear subspace of a left ideal 𝔩 = 𝕂[S_{r}] · e. A decomposition e = e_{1} + … + e_{m} of the generating idempotent into pairwise orthogonal, primitive idempotents e_{i} induces a decomposition W = W_{1} ⊕ … ⊕ W_{m} with W_{i} ⊆ 𝕂[S_{r}] · e_{i} and a decomposition of the tensors T ∈ T_{𝔩^{∗}}: T = e_{1}^{∗}T + … + e_{m}^{∗}T. Then we can transform (3.1), (3.2) into expressions formed from the e_{i}^{∗}T, for instance

9See B. Fiedler [12] or B. Fiedler [10, Sec. III.1, III.4.1].

(3.5)  (3.2) ⇒ τ_{i_{2l+1}...i_{r}} := ∑_{i=1}^{m} ∑_{p∈P} c_{p} (p(e_{i}^{∗}T))_{j_{1} j_{2} ... j_{l} i_{2l+1}...i_{r}}^{j_{1} j_{2} ... j_{l}} ,

and use the smaller equation systems of the smaller spaces W_{i} to determine linear identities for the coordinates of the e_{i}^{∗}T. Note, however, that a reduction of expressions such as (3.5) by means of identities of the W_{i} leads to a linear combination of coordinates of the e_{i}^{∗}T which cannot be reckoned back into a linear combination of the coordinates of T in general.

4. The Algorithm for Ideal Decompositions

Two problems became visible up to now: We need methods

(a) to determine generating idempotents e for left/right ideals of 𝕂[S_{r}] for which such idempotents are unknown (such as in Prop. 2.5).

(b) to decompose a given idempotent e ∈ 𝕂[S_{r}] into a sum e = e_{1} + … + e_{m} of

pairwise orthogonal primitive idempotents e_{i}. We developed an algorithm which solves these problems. First versions of this algorithm were designed for 𝕂[S_{r}] (see B. Fiedler [8, 9]). But it turned out that this algorithm works even in an arbitrary semisimple ring ℜ which fulfils:

(A) We know explicitly a decomposition

(4.1)  ℜ = ⨁_{i=1}^{m} ℜ · y_{i} or ℜ = ⨁_{i=1}^{m} y_{i} · ℜ

of the full ring ℜ into minimal left or right ideals generated by known primitive idempotents y_{i}. Pairwise orthogonality of the y_{i} is not required.

(B) We know in ℜ a method to construct explicitly a solution x ∈ ℜ for every equation

(4.2)  e · a · x · e = e or e · x · a · e = e ,

where e ∈ ℜ is a primitive idempotent and a ∈ ℜ is a ring element with e · a ≠ 0 or a · e ≠ 0, respectively.

We describe now a version (L) of the algorithm for left ideals of a semisimple ring ℜ. Obviously an analogous version (R) for right ideals can be formulated, too. (See B. Fiedler [10, Sec.I.2] and B. Fiedler [8, 9].)

A frequent step of the algorithm is the construction of a generating idempotent for a left ideal 𝔩 = ℜ · e · a, where e ∈ ℜ is a primitive idempotent and a ∈ ℜ is a ring element with e · a ≠ 0. This is possible by Proposition 4.1.^{10} For the above e, a ∈ ℜ there exists such an x ∈ ℜ that

(4.3)  e · a · x · e = e .

Moreover, the ring element e′ := x · e · a formed with this x is an idempotent which generates the minimal left ideal ℜ · e · a.

A second construction orthogonalizes idempotents. Let 𝔩 = ℜ · e and 𝔩̃ = ℜ · ẽ be two left ideals with known generating idempotents e and ẽ. Assume that e is primitive and e · ẽ ≠ e, i.e. 𝔩 ⊈ 𝔩̃. Then the sum 𝔩 + 𝔩̃ = 𝔩 ⊕ 𝔩̃ is direct since the minimality of 𝔩 yields 𝔩 ∩ 𝔩̃ = {0}. Now we search for new generating idempotents f and f̃ of 𝔩 and 𝔩̃ which fulfil f · f̃ = f̃· f = 0.

Theorem 4.2.^{11} The above orthogonalization problem can be solved in 2 steps: (i) We can find such a ring element x ∈ ℜ that

(4.4)  e · (1 − ẽ) · x · e = e .

If we use this x to form f := (1−ẽ)·x·e, then f is a generating idempotent of 𝔩 which satisfies ẽ · f = 0.

(ii) For a result f of step (i) there exists an x̃ ∈ ℜ such that

(4.5)  f · (1 − ẽ) · x̃ · f = f .

If we make use of x̃ to form f̃:= ẽ− (1 − ẽ) · x̃ · f · ẽ, then f̃ is a generating idempotent of 𝔩̃ which fulfils f · f̃ = f̃· f = 0.

Now we can describe our Algorithm (L), which allows us to decompose every left ideal 𝔩 = ℜ·a with known generating element a ≠ 0 into a direct sum 𝔩 = ⨁_{i=1}^{m} 𝔩_{i} of minimal left ideals 𝔩_{i} explicitly (see B. Fiedler [10, Sec.I.2] and B. Fiedler [8, 9]).

A multiplication of (4.1) by a yields a sum

(4.6)  𝔩 = ℜ · a = _{∑_{i=1}^{m} ; y_{i}·a≠0} ℜ · y_{i} · a

of minimal left ideals for 𝔩 which however is not direct in general. Now we can carry out the following steps:

(1) The first summand in (4.6) is a minimal left ideal. We denote it by 𝔩_{1} and we determine a generating idempotent e_{1} of 𝔩_{1} by means of Prop. 4.1.

(2) We search for the first minimal left ideal ℜ · y_{i} · a in (4.6) which is not contained in 𝔩_{1} that means for which

(4.7)  y_{i} · a · e_{1} ≠ y_{i} · a .

We denote it by 𝔩_{2} and we construct a generating idempotent e_{2} of 𝔩_{2} by means of Prop. 4.1. Since 𝔩_{2} is minimal and 𝔩_{2} ⊈ 𝔩_{1} , we obtain 𝔩_{1} ∩𝔩_{2} = {0}.

10See B. Fiedler [10, Prop. I.2.1]. Compare B. Fiedler [8, 9].

11B. Fiedler [10, Thm. I.2.4] and B. Fiedler [8, 9]. The proof uses the fact that the set {e − x · e + e · x · e | x ∈ ℜ} is the set of all generating idempotents of 𝔩 = ℜ · e (compare D.S.

Passman [23, p.137]).

Thus 𝔩_{1} and 𝔩_{2} form a direct sum 𝔩̃_{2} := 𝔩_{1} ⊕ 𝔩_{2}. Because e_{2} is primitive and e_{2} · e_{1} ≠ e_{2}, we can determine new, orthogonal, generating idempotents f̂_{1}, f_{2} of 𝔩_{1}, 𝔩_{2} by means of Theorem 4.2. Then f̃_{2} := f̂_{1} + f_{2} is a generating idempotent of 𝔩̃_{2}.

(3) Now we search for the next minimal left ideal ℜ · y_{i} · a in (4.6) which is not contained in 𝔩̃_{2} that means for which

(4.8)  y_{i} · a · f̃_{2} ≠ y_{i} · a .

We denote it by 𝔩_{3}. We construct a primitive generating idempotent e_{3} of 𝔩_{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} ⊕ 𝔩_{3} which has the generating idempotent f̃_{3} := f̂_{2} + f_{3}.

(4) We continue this procedure until we have processed all left ideals in (4.6). The result is a left ideal 𝔩̃_{n} := 𝔩_{1} ⊕ … ⊕ 𝔩_{n} and a generating idempotent f̃_{n} of 𝔩̃_{n}.

Obviously, 𝔩̃_{n} ⊆ 𝔩 since every left ideal 𝔩_{i} is a summand in (4.6). Furthermore, every summand ℜ · y_{i} · a from (4.6) which had been considered before we had reached the ideal 𝔩̃_{n} is contained in 𝔩̃_{n−1} = 𝔩_{1} ⊕ … ⊕ 𝔩_{n−1} ⊆ 𝔩̃_{n}. All other summands ℜ · y_{i} · a of (4.6) lie in 𝔩̃_{n}. This leads to 𝔩 ⊆ 𝔩̃_{n} and 𝔩 = 𝔩̃_{n}.

According to Theorem 4.2 (ii), every generating idempotent f̂_{k} of 𝔩̃_{k} can be written as f̂_{k} = (1 − z_{k}) · f̃_{k} with a z_{k} ∈ ℜ 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̃_{n} = f̂_{n−1} + f_{n} = (1 − z_{n−1}) · f̃_{n−1} + f_{n} = (1 − z_{n−1}) · (f̂_{n−2} + f_{n−1}) + f_{n}
= (1 − z_{n−1}) · (1 − z_{n−2}) · f̃_{n−2} + (1 − z_{n−1}) · f_{n−1} + f_{n}
⋮
(4.9) = ∑_{k=1}^{n−1}(1 − z_{n−1}) · (1 − z_{n−2}) · . . . · (1 − z_{k}) · f_{k} + f_{n} .

Formula (4.9) presents a decomposition f̃_{n} = ∑_{k=1}^{n} h_{k} of f̃_{n} into summands which fulfil h_{k} := (1 − z_{n−1}) · (1 − z_{n−2}) · . . . · (1 − z_{k}) · f_{k} ∈ 𝔩_{k} and h_{n} := f_{n} ∈ 𝔩_{n}. Thus, f̃_{n} = ∑_{k=1}^{n} h_{k} is the decomposition of f̃_{n} which corresponds to 𝔩 = ⨁_{k=1}^{n} 𝔩_{k} and the h_{k} are pairwise orthogonal generating idempotents of the 𝔩_{k}.

Obviously, the algorithm (L) solves the above problem (b). Furthermore, the algorithm (L) can be extended to left ideals which are non-direct sums 𝔩 = ∑_{i=1}^{h} ℜ· a_{i} by applying its steps to the summands of 𝔩 = ∑_{i=1}^{h} ∑_{j=1}^{m} ℜ · y_{j} · a_{i}. Likewise, we can construct generating idempotents and decompositions for right ideals 𝔯 = ∑_{i=1}^{h} a_{i} · ℜ by the algorithm version (R). If our left/right ideals are intersections 𝔩 = ⋂_{i=1}^{h} ℜ · e_{i} or 𝔯 = ⋂_{i=1}^{h} e_{i} · ℜ of left/right ideals (e_{i} idempotents), then their right/left annihilator ideals are A_{r}(𝔩) = ∑_{i=1}^{h}(1−e_{i})·ℜ or A_{l}(𝔯) = ∑_{i=1}^{h} ℜ·(1−e_{i}), respectively. In this case we can construct a generating idempotent e of A_{r}(𝔩) or A_{l}(𝔯) by (R) or (L), respectively, and form e′ := 1 − e to obtain a generating idempotent e′ of 𝔩 or 𝔯. Thus our algorithms solve problem (a) for non-direct sums or intersections of left/right ideals. See B.Fiedler [10, Sec.I.4] or B. Fiedler [9] for further details.

5. Completions of the Decomposition Algorithms

The basic assumptions (A) and (B). Actual decomposition constructions can only be carried out by the algorithms (L) or (R) if our semisimple ring ℜ fulfils the above assumtions (A) and (B). This is the case for

(1) the group ring ℜ = 𝕂[S_{r}] of a symmetric group,

(2) a ring ℜ = ⨂_{i=1}^{m} 𝕊_{i}^{n_{i}×n_{i}}, that is an outer direct product of full (n_{i} × n_{i})- matrix rings over skew fields 𝕊_{i},

(3) all semisimple rings ℜ for which an isomorphism D : ℜ → ℜ′ = ⨂_{i=1}^{m} 𝕊_{i}^{n_{i}×n_{i}}

onto a ring ℜ′ of the second type is explicitly known. (See B. Fiedler [10, Sec.I.3].) According to Wedderburn’s Theorem every semisimple ring is isomorphic to a ring of type 2. Thus statement 2 means that the decomposition algorithms (L) and (R) work in every semisimple ring up to an isomorphism.

Let us consider ℜ = ⨂_{i=1}^{m} 𝕊_{i}^{n_{i}×n_{i}}. We denote by C_{kl} ∈ 𝕊_{i}^{n_{i}×n_{i}} a matrix in which exactly the element located in the k-th row and the j-th column is equal to 1 ∈ 𝕊_{i} whereas all other elements vanish. Then a decomposition of ℜ into minimal left/right ideals is given by the decompositions 𝕊_{i}^{n_{i}×n_{i}} = ⨁_{j=1}^{n_{i}} 𝕊_{i}^{n_{i}×n_{i}} · C_{jj} and 𝕊_{i}^{n_{i}×n_{i}} = ⨁_{j=1}^{n_{i}} C_{jj} · 𝕊_{i}^{n_{i}×n_{i}} of the matrix rings into minimal left/right ideals. Furthermore there exists a very fast procedure to solve (4.2) in ℜ.

Since a primitive idempotent e ∈ ℜ has only one non-vanishing block matrix (i.e. e = (0, …, E, …, 0), where E ∈ 𝕊_{i}^{n_{i}×n_{i}} is also a primitive idempotent), an equation such as e · a · x · e = e leads to a single matrix equation E · A · X · E = E. Moreover, E can be written as E = f^{t} · h with row vectors f, h ∈ 𝕊_{i}^{n_{i}}, where h is a non-vanishing row of E. If we set m = h · A and determine non-vanishing elements m_{j_{0}}, f_{k_{0}} of m, f, then X := (m_{j_{0}})^{−1}(f_{k_{0}})^{−1}C_{j_{0}k_{0}} is a solution of E · A · X · E = E, which yields a solution x = (0, …, X, …, 0) of e · a · x · e = e (B. Fiedler [10, Sec. I.1.2, I.3.2]). Obviously, this procedure will run very fast on a computer.

For 𝕂[S_{r}] the well-known decomposition of 𝕂[S_{r}] into minimal left/right ideals by means of Young symmetrizers guarantees (A). See B. Fiedler [8, 9] for (B).

If for a semisimple ring ℜ an above isomorphism D : ℜ → ℜ′ is known (and practicable on a computer), then every ideal decomposition problem for ℜ can be transferred to ℜ′ and treated there by the algorithms (L) and (R).

If ℜ = ℂ[G] is the group ring of a finite group G, then we have 𝕊_{i} = ℂ for all i and the isomorphism D is called a discrete Fourier transform for G. Explicit algorithms for such Fourier transforms are known at least for abelian groups, solvable groups, supersolvable groups and symmetric groups (see M. Clausen und U. Baum [5]).

Discrete Fourier transforms. In group rings ℜ = ℂ[G] of large finite groups G (such as G = S_{r}, r ≥ 8), even a single product a · b, a, b ∈ ℂ[G] can lead to high costs in time and computer memory (see B. Fiedler [10, Sec. I.1.3, I.5.1]). Here the use of a discrete Fourier transform D : ℜ = ℂ[G] → ℜ′ = ⨂_{i=1}^{k} ℂ^{n_{i}×n_{i}} and the transfer of ideal decomposition problems to ℜ′ is the most important tool to surmount difficulties. Calculations in ℜ′ have the following advantages:

(1) Decompositions (4.1) and solutions of (4.2) can be constructed very fast in ℜ′.

(2) Every product formed during a run of (L) or (R) contains a factor which is a primitive idempotent e ∈ ℜ′. Since every such e has only 1 non-vanishing block matrix E ∈ ℂ^{n_{i}×n_{i}}, i.e. e = (0, …, 0, E, 0, …, 0), the costs for every step of (L) or (R) reduce to the costs of calculations in a ring ℂ^{n_{i}×n_{i}}.

(3) The algorithms (L) and (R) can be carried out completely within ℜ′. Only input and output data have to be mapped between ℜ and ℜ′ by means of D and D^{−1}. Thus, ”less fast” Fourier transforms can be useful, too. (See B. Fiedler [10, Sec.I.5.1].)

(4) In ℜ′ there is a fast construction of bases of linear subspaces W, which we

need to form linear equation systems (3.4). To describe this construction, we denote by C_{i,a} ∈ 𝕂^{n×n} that matrix in which the i-th row is equal to a given a ∈ 𝕂^{n} whereas all other rows are filled with 0.

Proposition 5.1. Let 𝔩 = 𝕂^{n×n} · A be a minimal left ideal of 𝕂^{n×n} with known generating element 0 ≠ A ∈ 𝕂^{n×n} and B = [b_{ij}]_{n,n} ≠ 0 be a matrix from 𝕂^{n×n}. Determine a row a ≠ 0 of A and a parametric form Λ of the solution of the linear equation system

(5.1)  ∑_{j=1}^{n} b_{ij} λ_{j} = 0 , i = 1, …, n , λ_{i} ∈ 𝕂 (unknowns) .

Then B := { B · C_{i,a} | i index for which λ_{i} is not a parameter in Λ } is a basis of the 𝕂-vector space B · 𝔩 = B · 𝕂^{n×n} · A.

See B. Fiedler [10, Sec.I.1.2] for the proof and other fast basis constructions. Spaces with a structure B · 𝔩 are typical examples of spaces W (see Sec. 6, 7). Further, we see that 𝔩 has the basis B = {C_{i,a} | i = 1, …, n} if we use the identity matrix B = Id ∈ 𝕂^{n×n} for B.

For our tensor investigations we need ℜ = 𝕂[S_{r}]. M. Clausen und U. Baum [5, 6] developed a very fast Fourier transform for 𝕂[S_{r}], which bases on Young’s seminormal representation of S_{r} (see also H. Boerner [3] and A. Kerber [17, Vol.I, p.75,76]). However, since the interpreter Mathematica does not allow the full speed and the optimal storage handling of this ingenious algorithm, we use Young’s natural representation of S_{r} as discrete Fourier transform in our Mathematica package PERMS [11]. (See H. Boerner [2, pp.102–108], B. Fiedler [10, Sec.I.5.2].) This implementation works good at least for S_{r}, r ≤ 8.

Multiplicities. Obviously, the efficiency of the algorithms (L) and (R) can be improved if we know before a run of (L) or (R) the multiplicities of equivalent minimal left/right ideals 𝔩_{i} or 𝔯_{i} within decompositions 𝔩 = ⨁_{i=1}^{m} 𝔩_{i} or 𝔯 = ⨁_{i=1}^{m} 𝔯_{i} searched for. If the algorithms have constructed such a direct sum of minimal left/right ideals of a fixed equivalence class that the number of summands equals the known multiplicity for this class, then the investigation of the remaining ideals of the class can be cancelled. This reduces the calculation time.

In the case of ℜ = 𝕂[S_{r}] such multiplicies can be calculated by means of the irreducible characters of S_{r}, Frobenius reciprocity, the Littlewood-Richardson rule and plethysms. The determination of the irreducible characters of S_{r} is possible by the Murnaghan-Nakayama formula. We implemented all these tools in our Mathematica package PERMS [11] (see B. Fiedler [10, Sec. II.3–II.6] for descriptions of implementations). For plethysms we use a very efficient method of F. Sänger [24, pp. 29–33]. (See B. Fiedler [10, Sec.II.6.3].)

6. Characterizing Left Ideals of Tensor Products

We continue to list linear subspaces W ⊆ 𝕂[S_{r}] describing tensor symmetries. In the case of tensor products two types of products can be considered: T^{(1)}⊗…⊗T^{(m)} with possibly different T^{(i)} and T ⊗ … ⊗ T.

Proposition 6.1.^{12} Let 𝔩_{i} ⊆ 𝕂[S_{r_{i}}] (i = 1, …, m) be left ideals and T^{(i)} ∈ T_{𝔩_{i}^{∗}} ⊆ T_{r_{i}}V be r_{i}-times covariant tensors from the symmetry classes characterized by the 𝔩_{i}. Consider the product

(6.1)  T := T^{(1)} ⊗ … ⊗ T^{(m)} ∈ T_{r}V , r := r_{1} + … + r_{m} .

For every i we define an embedding

(6.2) ι_{i} : S_{r_{i}} → S_{r} , (ι_{i}s)(k) := \{ \begin{matrix}Δ_{i} + s(k − Δ_{i}) & if r_{i−1} < k ≤ r_{i} \\ k & else \end{matrix}

where Δ_{i} := r_{0} + … + r_{i−1} and r_{0} := 0. Then the T_{b} of the tensor (6.1) fulfil

∀ b ∈ V^{r} : T_{b} ∈ 𝔩 := 𝕂[S_{r}] · L{𝔩̃_{1} · . . . · 𝔩̃_{m}} = 𝕂[S_{r}] · (𝔩̃_{1} ⊗ … ⊗ 𝔩̃_{m}) (6.3)

where 𝔩̃_{i} := ι_{i}(𝔩_{i}) are the embeddings of the 𝔩_{i} into 𝕂[S_{r}] induced by the ι_{i}. If dim V ≥ r, then the above left ideal 𝔩 is generated by all T_{b} ∈ 𝕂[S_{r}] which are formed from tensor products (6.1) of arbitrary tensors T^{(i)} ∈ T_{𝔩_{i}^{∗}}.

Proposition 6.2.^{13} Let 𝔩_{0} ⊆ 𝕂[S_{m}] be a left ideal and T ∈ T_{𝔩_{0}^{∗}} ⊆ T_{m}V be a tensor of order m from the symmetry class T_{𝔩_{0}^{∗}}. Consider the product

(6.4)  T̂ := \underbrace{T ⊗ … ⊗ T}_{n} ∈ T_{mn}V .

Then all T̂_{b}, b ∈ V^{mn}, lie in the left ideal

𝔩 := 𝕂[S_{mn}] · L{𝔩_{1} · . . . · 𝔩_{n} · 𝔩′} = 𝕂[S_{mn}] · (𝔩_{1} ⊗ … ⊗ 𝔩_{n} ⊗ 𝔩′) (6.5) where 𝔩_{i} := ι_{i}(𝔩_{0}) are embeddings of 𝔩_{0} into 𝕂[S_{mn}] which are formed by means of mappings (6.2) with r_{1} = … = r_{n} = m and r = mn. Further 𝔩′ denotes the 1-dimensional ideal 𝔩′ := L{∑_{q∈Q} q} of 𝕂[Q] where Q ⊂ S_{mn} is the subgroup

12See B. Fiedler [10, Sec.III.3.2] and B. Fiedler [12].

13See B. Fiedler [10, Sec.III.3.2] and B. Fiedler [12].

(6.6)  Q := \{q = \binom{k·m−l}{s(k)·m−l}_{\begin{matrix}1≤k≤n \\ 0≤l≤m−1 \end{matrix}} ∈ S_{mn} | s ∈ S_{n}\} ≅ S_{n} .

If dim V ≥ m · n, then the above left ideal 𝔩 is generated by all T̂_{b} ∈ 𝕂[S_{mn}] which are formed from tensor products (6.4) of arbitrary tensors T ∈ T_{𝔩_{0}^{∗}}.

Let ω̆_{G} : G → GL(𝕂[G]) denote the regular representation of a finite group G defined by ω̆_{g}(f) := g · f, g ∈ G, f ∈ 𝕂[G]. If we use the above left ideals 𝔩_{i}, 𝔩_{0}, 𝔩 to define subrepresentations α_{i} := ω̆_{S_{r_{i}}}|_{𝔩_{i}}, α := ω̆_{S_{m}}|_{𝔩_{0}}, β := ω̆_{S_{r}}|_{𝔩}, then the representation β is equivalent to a Littlewood-Richardson product or a plethysm^{14}, respectively (see B. Fiedler [10, Sec.III.3.2]):

(6.7)  𝔩 according to (6.3) ⟹ β ∼ α_{1} # … # α_{m} ↑ S_{r}
(6.8)  𝔩 according to (6.5) ⟹ β ∼ α ⊙ [n] .

These results correspond to statements of S.A. Fulling et al. [14]. (6.7) and (6.8) yield valuable information about multiplicities if one wishes to apply the algorithm (L) to 𝔩.

7. Subspaces Characterizing Tensors with Index Contractions

First we give a universal linear subspace which contains the group ring elements ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} of a tensor T with l index contractions for every value of dim V.

Theorem 7.1. Let V, B, r, l, g, b_{0} have the meaning given in Def. 2.7 and Prop. 2.8. Consider the partition λ_{0} := (2^{l} , 1^{r−2l}) ⊢ r and the lexicographically smallest standard tableau t of λ_{0}. Form the group ^{15} G := H_{t} · Q where H_{t} is the group of all horizontal permutations of t and Q ⊂ V_{t} is the subgroup of all such vertical permutations of t which only permute full rows of t with length 2. Then every tensor T ∈ T_{𝔩^{∗}} ⊆ T_{r}V (𝔩 = 𝕂[S_{r}] · e, e idempotent) fulfils

(7.1)  ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} ∈ 1_{G} · 𝕂[S_{r}] · e , 1_{G} := ∑_{g∈G} g .

14See the references [17, 18, 16, 24, 20, 21, 14] for the Littlewood-Richardson rule and plethysms.

15G is a semidirect product H_{t} ⋊ Q and isomorphic to the wreath product S_{2} ≀ S_{l}.

Furthermore, if dim V ≥ r − l, then there is such a b_{0} ∈ B^{r−2l} that ^{16}

(7.2)  1_{G} · 𝕂[S_{r}] · e = L_{𝕂}{ ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} | T ∈ T_{𝔩^{∗}}} .

The proof can be found in Sec. III.3.4 of our Habilitationsschrift [10]. If dim V < r − l, then the ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} will span only a linear subspace of 1_{G} · 𝕂[S_{r}] · e in general. To describe this subspace, we define:

Definition 7.2. If λ = (λ_{1}, …, λ_{k}) ⊢ r is a partition with length |λ| = k and (v_{1}, …, v_{k}) ∈ V^{k} is a k-tuple of vectors, then we denote by ⟨λ; v_{1}, …, v_{k}⟩ or short ⟨λ; v_{i}⟩ that r-tuple from V^{r} which has the structure

(7.3)  ⟨λ; v_{1}, …, v_{k}⟩ := (\underbrace{v_{1}, …, v_{1}}_{λ_{1}}, \underbrace{v_{2}, …, v_{2}}_{λ_{2}}, …, \underbrace{v_{k}, …, v_{k}}_{λ_{k}}) ∈ V^{r} .

For every b = (v_{1}, …, v_{r}) ∈ V^{r}, there exists a unique partition λ ⊢ r and a permutation q ∈ S_{r} such that b can be written as b = q⟨λ; w_{1}, …, w_{|λ|}⟩ where w_{1}, …, w_{|λ|} are the pairwise different, suitably renumbered vectors from b. We call ⟨λ; w_{1}, …, w_{|λ|}⟩ a grouping of b and λ the grouping partition of b, which we also denote by λ = b^{⊢}.

Definition 7.3. Let B be an orthonormal basis with respect to a fundamental tensor g ∈ T_{2}V. We call (n_{i_{1}}, …, n_{i_{r′}}) ∈ B^{r′} smaller than (n_{j_{1}}, …, n_{j_{r′}}) ∈ B^{r′} if the first non-vanishing difference j_{k} − i_{k} fulfils j_{k} − i_{k} > 0. If ⟨λ; w_{1}, …, w_{|λ|}⟩ and ⟨λ; w′_{1}, …, w′_{|λ|}⟩ are two groupings of a fixed r-tuple b ∈ B^{r} of basis vectors, then we call ⟨λ; w_{1}, …, w_{|λ|}⟩ smaller than ⟨λ; w′_{1}, …, w′_{|λ|}⟩ if the |λ|-tuple (n_{i_{1}}, …, n_{i_{|λ|}}) := (w_{1}, …, w_{|λ|}) is smaller than the |λ|-tuple (n_{j_{1}}, …, n_{j_{|λ|}}) := (w′_{1}, …, w′_{|λ|}).

For every r-tuple b ∈ B^{r} there exists a permutation p_{b} ∈ S_{r} such that b has a representation b = p_{b}⟨λ; w_{1}, …, w_{|λ|}⟩ where ⟨λ; w_{1}, …, w_{|λ|}⟩ is the smallest grouping of b and λ = b^{⊢}. We denote by 𝔭 a single-valued mapping 𝔭 : B^{r} → S_{r}, b ↦ 𝔭(b) := p_{b} which assigns exactly one of such permutations p_{b} to b.

Let b_{0} ∈ B^{r−2l} be an (r − 2l)-tuple of vectors from the basis B. We denote by Λ_{b_{0}} the set Λ_{b_{0}} := {λ ⊢ r | ∃ b ∈ 𝔅_{b_{0}} : λ = b^{⊢}}. Furthermore, we assign to every partition λ ∈ Λ_{b_{0}} the lexicographically smallest standard tableau t_{λ} of λ and the set M_{b_{0},λ} := {𝔭(b)^{−1}b ∈ B^{r} | b ∈ 𝔅_{b_{0}} with b^{⊢} = λ} of such r-tuples which are the smallest groupings of the b ∈ 𝔅_{b_{0}} with grouping partition λ.

Theorem 7.4. Let V, B, r, l, g, b_{0}, T_{𝔩^{∗}} and e have the meaning given in Theorem 7.1 and 𝔭 : B^{r} → S_{r} be a mapping of the type described in Definition 7.3. Then we have

16Corollary: If r − 2l = 0, then the decomposition of 1_{G} · 𝕂[S_{r}] into minimal right ideals is characterized by a plethysm [2] ⊙ [l] ∼ ∑_{μ⊢l}[2μ]. Thus the number I of linearly independent invariants of T is bounded by the sum M of the multiplicities of minimal left ideals 𝔩_{i} belonging to partitions 2μ, μ ⊢ l, in 𝕂[S_{r}] · e = ⨁ 𝔩_{i}. If dim V ≥ l, then I = M. (See B. Fiedler [10, Sec.III.4.2]. Compare S.A. Fulling et al. [14].)

L_{𝕂}{ ∑_{b∈𝔅_{b_{0}}} γ_{b} T_{b} | T ∈ T_{𝔩^{∗}}} = ∑_{λ∈Λ_{b_{0}}} ∑_{⟨λ;w_{i}⟩∈M_{b_{0};λ}} a_{⟨λ;w_{i}⟩} · 1_{H_{t_{λ}}} · 𝕂[S_{r}] · e

where

a_{⟨λ;w_{i}⟩} := _{∑_{b∈𝔅_{b_{0}}} ; 𝔭(b)^{−1}b = ⟨λ;w_{i}⟩}γ_{b} 𝔭(b)^{−1} .

The proof is given in Sec. III.3.4 of our Habilitationsschrift [10]. Furthermore, we clear in Sec. III.3.4 to what extent the subspaces from Theorem 7.4 are independent from the choice of b_{0}.

8. Concluding Remarks

In Sec. III.3.3 of our Habilitationsschrift [10] we determined linear subspaces W ⊆ 𝕂[S_{r}] for tensors T ∈ T_{r}V for which the vector space V has a dimension dim V < r. Some details about this case can be found in the paper [12], too.

In Sec. III.4.2 of the Habilitationsschrift [10] we applied Theorem 7.1 to invariants (i.e. r = 2l and b_{0} = ∅). Footnote 16 gives one of the results.

We have tested our methods in computer calculations. Among other things, we treated the term combination problem for quadratic monomials in the coordinates of the Riemannian curvature tensor (B. Fiedler [10, Sec.III.5.1]). The correctness of this calculation was controlled by means of the results of S.A. Fulling et al. [14]. Furthermore, we used Theorem 7.4 to verify the standard identity^{17} ∑_{p∈S_{2n}} χ(p)A_{p(1)} · . . . · A_{p(2n)} = 0 for (n × n)-matrices A_{i} in the case n = 2 (B. Fiedler [10, Sec.III.5.2]). For this calculation the full algorithm (R) was required.

We implemented our methods in a Mathematica package PERMS. This package comprises tools for permutation groups and group rings, partitions and tableaux, special idempotents, characters, the Littlewood-Richardson rule, plethysms, discrete Fourier transforms and our algorithms (L) and (R). Furthermore, we used the packages SYMMETRICA [19] and GAP [25].

References

[1] S. A. Amitsur and J. Levitzki. Remarks on minimal identities for algebras. Proc. Amer. Math. Soc., 2:320 – 327, 1951.

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

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

[4] Siamack Bondari. Constructing the polynomial identities and central identities of degree < 9 of 3 × 3 matrices. J. Linear Algebra Appl., 258:233 – 249, 1997.

[5] Michael Clausen and Ulrich Baum. Fast Fourier Transforms. BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich, 1993.

17See S.A. Amitsur and J. Levitzki [1] and S. Bondari [4].

[6] Michael Clausen and Ulrich Baum. Fast Fourier transforms for symmetric groups. In Larry Finkelstein and William M. Kantor, editors, Groups and Computation, volume 11 of DI-MACS Series in Discrete Mathematics and Theoretical Computer Science, pages 27 – 39, Providence, Rhode Island, 1993. DIMACS: NSF Science and Technology Center in Discrete Mathematics and Theoretical Computer Science, a consortium of Rutgers University, Priceton University, AT&T Bell Labs, Bellcore, American Mathematical Society. The DIMACS workshop on Groups and Computation was held at DIMACS, Rutgers University, Oct. 7 – 10, 1991.

[7] G. Eisenreich. Lexikon der Algebra. Akademie-Verlag, Berlin, 1989.

[8] Bernd Fiedler. A use of ideal decomposition in the computer algebra of tensor expressions. Z. Anal. Anw., 16(1):145 – 164, 1997.

[9] Bernd Fiedler. An algorithm for the decomposition of ideals of the group ring of a symmetric group. In Adalbert Kerber, editor, Actes 39^{e} Séminaire Lotharingien de Combinatoire, Thurnau, 1997, Publ. I.R.M.A. Strasbourg. Institut de Recherche Mathématique Avancée, Université Louis Pasteur et C.N.R.S. (URA 01), 1998. Electronically published:

http://www.mat.univie.ac.at/~slc. B39e, 26 pp.

[10] Bernd Fiedler. An Algorithm for the Decomposition of Ideals of Semi-Simple Rings and its Application to Symbolic Tensor Calculations by Computer. Habilitationsschrift, Universität Leipzig, Leipzig, Germany, November 1999. Fakultät für Mathematik und Informatik.

[11] Bernd Fiedler. PERMS 2.1 (15.1.1999). Mathematisches Institut, Universität Leipzig, Leipzig, 1999. Will be sent in to MathSource, Wolfram Research Inc.

[12] Bernd Fiedler. Characterization of tensor symmetries by group ring subspaces and computation of normal forms of tensor coordinates. In Proceedings of the Euroconference Algebraic Combinatorics and its Applications, Gößweinstein 1999. Springer-Verlag, 2000. Submitted to the Conference Proceedings.

[13] Bernd Fiedler. Reduction of linear combinations of tensors by ideal decompositions. In Proceedings of the 6. International School on Theoretical Physics SSPCM’2000, Myczkowce 2000, page 10pp., Singapore, 2001. World Scientific Publishing Co. Submitted to the conference proceedings.

[14] 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.

[15] P. Günther. Huygens’ Principle and Hyperbolic Equations, volume 5 of Perspectives in Mathematics. Academic Press, Inc., Boston, San Diego, New York, Berkeley, London, Sydney, Tokyo, Toronto, 1988.

[16] Gordon D. James and Adalbert 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.

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

[18] A. Kerber. Algebraic combinatorics via finite group actions. BI-Wiss.-Verl., Mannheim, Wien, Zürich, 1991.

[19] A. Kerber, A. Kohnert, and A. Lascoux. SYMMETRICA, an object oriented computeralgebra system for the symmetric group. J. Symbolic Computation, 14:195 – 203, 1992.

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

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

[22] Russel Merris. Multilinear Algebra, volume 8 of Algebra, Logic and Applications Series. Gordon and Breach Science Publishers, Amsterdam, 1997.

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

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

[25] Martin Schönert et al. GAP – Groups, Algorithms, and Programming. Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, fifth edition, 1995.

[26] J. A. Schouten. Der Ricci-Kalkül, volume 10 of Die Grundlehren der Mathematischen Wissenschaften. Verlag von Julius Springer, Berlin, 1924.

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

[28] B. G. Wybourne and S. M. Christensen. Schur 5.1 (January 6, 1994), \begin{matrix}c \\ ◯ \end{matrix} 1993 - 1994. Program package.

Bernd Fiedler, Alfred-Rosch-Str. 13, D-04249 Leipzig, Germany

URL: http://home.t-online.de/home/Bernd.Fiedler.RoschStr.Leipzig/
E-mail address: Bernd.Fiedler.RoschStr.Leipzig@t-online.de