                      UNIVERSITY OF WISCONSIN-MADISON
                   CENTER FOR THE MATHEMATICAL SCIENCES

Symmetries of linear functionals

Shayne Waldron^{∗} (waldron@math.wisc.edu)

                    CMS Technical Summary Report #95-04
                               October 1994

ABSTRACT

It is shown that a linear functional λ on a space of functions can be described by G, a group of its symmetries, together with the restriction of λ to certain G-invariant functions.

This simple consequence of invariant theory has long been used, implicitly, in the construction of numerical integration rules. It is the author’s hope that, by showing that these ideas have nothing to do with the origin of the linear functional considered, e.g., as an integral, they will be applied more widely, and in a systematic manner.

As examples, a complete characterisation of the rules of degree (precision) 3 with 4 nodes for integration on the square [−1, 1]^{2} is given, and a rule of degree 5 with 3 nodes for the linear functional f ↦ ∫_{−h}^{h} D^{2}f is derived.

AMS (MOS) Subject Classifications: primary 41A05, 13A50, 14D25 secondary 65D25, 65D30, 65D32

Key Words: linear functional, symmetry group, invariant theory, invariant polynomial, Poincaré series, Molien series, integrity basis, numerical integration rules, numerical differentiation rules

∗ Supported by the Chebyshev professorship of Carl de Boor and the Center for the mathematical sciences.

1. Introduction

In the lectures ‘Exploiting symmetry in applied and numerical analyis’ [AGM93], the editors contend that:

“Symmetry plays an important role in theoretical physics, applied analysis, classical differential equations, and bifurcation theory. Although numerical analysis has incorporated aspects of symmetry on an ad hoc basis, there is now a growing collection of numerical analysts who are currently attempting to use symmetry groups and representation theory as fundamental tools in their work.”

In the same spirit, this paper presents the abstract machinery for dealing with the ‘symmetries’ of linear functionals, together with some applications to numerical analysis.

The paper is set out as follows. Section 2 gives a definition of the symmetry group of a linear functional, with examples and discussion. In Section 3, the main result: that a linear functional can be represented by a finite group of its symmetries and its restriction to certain functions invariant under these symmetries, is given. Some illuminating applications to rule construction are given in Section 4. In Section 5, some relevant results from the classical theory of G-invariant polynomials are outlined. Finally, in Section 6, it is indicated how the ideas of this paper can be extended to describe the symmetries of linear maps.

2. Symmetries

Throughout, let P denote a space of functions Ω → IR, where Ω ⊂ IR^{n}. The algebraic dual of P, i.e., the space of linear functionals on P, will be denoted by P′. The group of affine transformations (invertible affine maps) on IR^{n} will be denoted by A := Aff(IR^{n}).

For a linear functional λ ∈ P′, and an affine map g ∈ A, let g∗λ be the linear functional given by

g∗λ : f ↦ λ(f ∘ g).

Definition. The symmetry group of a linear functional λ ∈ P′ is

sym(λ) := {g ∈ A : g∗λ = λ};

it is a subgroup of A.

Example 2.1. Consider the symmetry group of a (nonzero) weighted Lebesgue integral

I : f ↦ ∫ f w,

with w ≥ 0, which is defined at least on polynomials.

By the change of variables formula,

(g^{−1}∗I)f = ∫ (f ∘ g^{−1}) w = ∫ f | det g| w ∘ g.

Thus, g ∈ sym(I) if and only if w = | det g| w ∘ g. This implies that | det g| = 1, and so sym(I) is a subgroup of the unimodular (or special affine) group, which consists of the Lebesgue-measure-preserving affine transformations.

For integrals I that numerical analysts seek to approximate (see, e.g., Stroud [St71]), sym(I) has a fixed point and so, (after a suitable translation), can be thought of as a group of linear transformations. For example, if I is integration on the square

I(f) := ∫_{[a,b]^{2}} f,

and P is some suitably chosen space, such as L_{1}([a, b]^{2}), or C([a, b]^{2}), then sym(I) is the group of symmetries of the square (the dihedral group of order 8).

Example 2.2. Consider the symmetry group of a numerical integration formula for a weighted Lebesgue integral I (as in Example 2.1)

Q : f ↦ ∑_{θ∈Θ} w(θ)f(θ),

where Θ is a finite subset of IR^{n}.

If Θ contains n + 1 points in general position and each appears with nonzero weight – as is the case when Q is of precision 1 – then sym(Q) is a finite group. In this case, sym(Q) can be viewed as a group of permutations on the nodes Θ, with those nodes in the same orbit having equal weights. Additionally, sym(Q) is a subgroup of the unimodular group (as is every finite subgroup of A).

To help better understand the nature of sym(λ), let the symmetry group of the space P of functions be

sym(P) := {g ∈ A : P ∘ g = P },

and the symmetry group of the domain Ω be

sym(Ω) := {g ∈ A : gΩ = Ω}.

Then the following inclusion of groups holds:

sym(λ) ⊂ sym(P) ⊂ sym(Ω) ⊂ A.

Often sym(λ) = sym(Ω), as was the case for integration over the square Ω := [a, b]^{2} (mentioned in Example 2.1).

3. Representing symmetric linear functionals

Suppose G is a finite subgroup of sym(P), and #G is its order. For all p ∈ P, define

p_{G} := \frac{1}{#G} ∑_{g∈G} p ∘ g ∈ P.

Then the map

R_{G} : P → P : p ↦ p_{G}

is a linear projector. In keeping with the case when P is Π, the space of polynomials, we denote the range of R_{G}, i.e., the space of G-invariant functions in P, by P^{G}. The term G-invariant is appropriate since p ∘ g = p, ∀g ∈ G iff p ∈ P^{G}. The letter R is used because p ↦ p_{G} is referred to by some authors as the Reynold’s operator.

Next we present the main result, which is an abstract version of a result of Sobolev [So62].

Theorem 3.1. If λ ∈ P′, and G ⊂ sym(λ) is a finite subgroup of its symmetries, then

λ = λ ∘ R_{G}.

In other words, λ is determined by G and the restriction of λ to P^{G}.

Proof: Since g ∈ G ⊂ sym(λ), we have that λ(p ∘ g) = λ(p), ∀p ∈ P. Thus,

λ(R_{G}(p)) = \frac{1}{#G} ∑_{g∈G} λ(p ∘ g) = λ(p), ∀p ∈ P.

The result of Sobolev

Let I be the integral of Example 2.1, and Q be the integration formula (for I) of Example 2.2. Cools [C92] says that Q is invariant with respect to a group G ⊂ A when:

(a) I is of the form

I(f) := ∫_{Ω} f w,

where w ≥ 0, G ⊂ sym(Ω), and ∀g ∈ G, w ∘ g = w.

(b) Q is such that g ∈ G maps Θ onto Θ, with nodes in the same orbit having equal weight.

It can readily be seen that conditions (a), (b) are equivalent to:

(a′) G ⊂ sym(I).
(b′) G ⊂ sym(Q).

In particular, the condition that Q be invariant with respect to G implies

G ⊂ sym(I|_{Π_{k}}) ∩ sym(Q|_{Π_{k}}),

where |_{Π_{k}} denotes restriction to Π_{k} (the polynomials of degree k). Thus, as a corollary of Theorem 3.1, one obtains Sobolev’s theorem, as stated by Cools.

Sobolev’s theorem 3.2 (as in [C92]). If Q is invariant with respect to G, then Q is of degree k for I if (and only if)

I(f) = Q(f), ∀f ∈ (Π_{k})^{G}.

The original theorem of Sobolev [So62] dealt with the case when Ω is the sphere.

4. Applications

In this section we indicate how Theorem 3.1 can be used in numerical analysis by giving two examples that concern rule construction.

Cubature rules

An integral I is said to be centrally symmetric if it satisfies

g∗I = I,

when g is reflection through the origin, i.e., g : x ↦ −x. A numerical integration rule for an area-integral is commonly referred to as a cubature formula.

In his dissertation (1973), Möller proved that a cubature formula of degree 3 for a centrally symmetric integral must have at least 4 nodes. In addition, such a formula with 4 nodes must itself be centrally symmetric. For details see Möller [M79].

In Stroud [St71:p88], Sylvester’s law of inertia is used to compute all (centrally symmetric) cubature formulæ of degree 3 for the integral

I : f ↦ ∫_{[−1,1]^{2}} f.  (4.1)

This method, as pointed out by Stroud,

“is not readily extended to construct formulas of higher degree.”

By comparison, using Sobolev’s theorem, these, and higher order formulæ, can be obtained, see, e.g., Cools [C92].

We now use Sobolev’s theorem to find all the cubature formulæ Q of degree 3 for the integral I of (4.1) which have the minimum number of nodes. Since these formulæ are centrally symmetric, they must have nodes ±(r cos a, r sin a), ±(R cos A, R sin A) with weights w, W respectively.

Let G be the group (of order 2) generated by reflection through the origin. Since G is contained within the symmetry groups of I and Q restricted to P := Π_{3}, it follows from Theorem 3.1 that

I|_{Π_{3}} = I ∘ R_{G}, Q|_{Π_{3}} = Q ∘ R_{G},  (4.2)

where

R_{G} : Π_{3} → Π_{0} ⊕ Π_{2}^{0}.

Here Π_{2}^{0} denotes space of homogeneous quadratics. To see that the space (Π_{3})^{G} of Ginvariant cubics is Π_{0} ⊕ Π_{2}^{0}, one can simply find the image of a basis for Π_{3} under R_{G}. More details about G-invariant polynomials are given in Section 5.

From (4.2) it follows that Q is of degree 3, i.e., I|_{Π_{3}} = Q|_{Π_{3}}, if and only if

I|_{Π_{0}⊕Π_{2}^{0}} = Q|_{Π_{0}⊕Π_{2}^{0}}.  (4.3)

By requiring that I and Q agree at the monomials 1, (·)^{2,0}, (·)^{0,2}, (·)^{1,1} (which form a basis for Π_{0} ⊕ Π_{2}^{0}), the following nonlinear system:

w + W = 2,
wr^{2}cos^{2} a + W R^{2}cos^{2} A = 2/3,
wr^{2}sin^{2} a + W R^{2}sin^{2} A = 2/3,
wr^{2}sin a cos a + W R^{2}sin A cos A = 0,

(4.4)

which is equivalent to (4.3), is obtained.

The last three equations in (4.4) are linear in wr^{2} and W R^{2}, and the condition for them to have a solution is that

A = a + \frac{π}{2} .

For the choice A = a + π/2, there is a unique solution

wr^{2} = W R^{2} = \frac{2}{3}.

To additionally satisfy the first equation, i.e., that w + W = 2, one must have that

(2 − \frac{2}{3r^{2}} ) R^{2} = \frac{2}{3}.

Hence we have shown the following.

Theorem 4.5 (see [St71:Th.3.9-2]). Let I be integration over the square [−1, 1]^{2}.

Given any point

θ := (r cos a, r sin a)

which is outside the circle of radius 1/\sqrt{3}, there is a unique centrally symmetric cubature formula for I which is of degree 3 with 4 nodes, one of which is θ. By Möller’s result, these are all of the cubature formulæ for I of degree 3 that have a minimum number of nodes.

For such a formula the weight for θ and its antipodal point −θ is

w = \frac{2}{3r^{2}} .

The other two points in the formula are

±(R cos(a + π/2), R sin(a + π/2)),

where R := r/\sqrt{3r^{2} − 1}, which have weight

W = \frac{6r^{2} − 2}{3r^{2}} = \frac{2}{3R^{2}} .

Notice that R → ∞ as r → (1/\sqrt{3})^{+}.

a = π/4 ; r = R = \sqrt{2/3} ; w = W = 1  a = π/6 ; r = 1/\sqrt{2}, w = 4/3 ; R = 1, W = 2/3  a = π/4 ; r = \sqrt{2/5}, w = 5/3 ; R = \sqrt{2}, W = 1/3

Fig. 4.1 Some examples of cubature formulæ of degree 3 for integration over [−1, 1]^{2} which have the minimum number of nodes, with the circle of radius 1/\sqrt{3} inscribed.

Remark. Given the many possible rules of Theorem 4.5, it is natural to ask whether some might be preferred over others on the basis of considerations in addition to degree.

To the author’s mind, the rule with nodes (±\sqrt{1/3}, ±\sqrt{1/3}) each given weight 1, i.e., the first rule of Fig. 4.1, is the most desirable. This rule has a simple form, and its symmetry group (as a functional on a larger space than Π_{3}, such as C([−1, 1]^{2})) is the dihedral group of the square - which is the symmetry group of I. In addition, it can be obtained as the product of two univariate rules, and hence is exact for the space of polynomials of co-ordinate degree 3 (which is larger than Π_{3}).

Numerical differentiation rules

In this example, we seek to approximate the linear functional

λ : C^{2}(IR) → IR : f ↦ ∫_{a−h}^{a+h} D^{2}f

by a rule of high degree based on 3 nodes.

The symmetry group of λ, which we denote by G, is of order 2, and generated by reflection through a. Seeking a rule μ with the same symmetries, we must take

μ(f) := w_{1}f(a − δ) + w_{2}f(a) + w_{1}f(a + δ).

To simplify the calculations assume that a = 0. For this case the G-invariant polynomials are the even polynomials. Thus, from Theorem 3.1 we obtain that:

If w_{1}, w_{2}, and δ can be chosen so that λ and μ agree for the even monomials of degree upto 2s, then the rule μ has degree 2s + 1.

In this way we obtain:

μ(f) := f(a − \sqrt{2h}) − 2f(a) + f(a + \sqrt{2h});

which is a rule of degree 5 for λ.

Remark. One might expect that (2h)^{−1}μ is a good approximation to the linear functional

ν : f ↦ D^{2}f(a).

Indeed, we recognise (2h)^{−1}μ as the rule of precision 3 for ν based on 3 nodes (with stepsize \sqrt{2h}). To put it another way, the well-known rule

f ↦ \frac{f(a − h) − 2f(a) + f(a + h)}{h^{2}},

which is of degree 3 for ν, is of degree 5 for

f ↦ \frac{1}{h^{2}} ∫_{a−h^{2}/2}^{a+h^{2}/2} D^{2}f.

5. G-invariant polynomials

In the examples of Section 4, P is a space of polynomials. However, Theorem 3.1 is in no way limited to this case. Other choices for P of possible interest include spaces of splines, or complex functions. There has been little work on the G-invariance of such spaces of functions.

On the other hand, the theory of G-invariant polynomials is a well-developed branch of invariant theory, see, e.g., Humphreys [H90] and Benson [B93]. Here is a quick exposition of some relevant results of the theory.

We have already used (for example in (4.2)) the fact that

Π_{k}^{G} := (Π_{k})^{G} = Π^{G} ∩ Π_{k}.

It follows from the Hilbert basis theorem that Π^{G} is a finitely generated IR-algebra. If G is a group of linear transformations, then Π^{G} is homogeneous. The space Π^{G} is generated by n algebraically independent polynomials of positive degree (together with 1), which are called an integrity basis for G, if (and only if) G is a finite reflection group (of linear transformations).

The dimensions of Π_{k}^{G}, for G a finite group can be computed as follows. Let

M_{k} := dim Π_{k}^{G} − dim Π_{k−1}^{G}, with M_{0} := dim Π_{0}^{G} = 1.

The series ∑_{k} M_{k}t^{k} is called the Poincaré (also Molien) series for G. Molien’s theorem, see, e.g., [B93:p21], states that the following equality of formal power series holds:

∑_{k=0}^{∞} M_{k}t^{k} = \frac{1}{#G} ∑_{g∈G} \frac{1}{det(1 − tg)}.

6. Conclusion

All of the previous discussion about symmetries of linear functionals

λ : P → IR

holds more generally when IR is replaced by any linear space X, i.e., for a linear map

L : P → X.

For g ∈ A, let g ∗ L be the linear map

g ∗ L : P ∘ g^{−1} → X : f ↦ L(f ∘ g).

Definition. The symmetry group of a linear map L ∈ L(P, X) is

sym(L) := {g ∈ A : g ∗ L = L};

it is a subgroup of A.

With these definitions, the earlier arguments, with λ now replaced by L, continue to hold. In particular, so does the analogue of Thereom 3.1: if G ⊂ sym(L) is a finite group of symmetries of L, then

L = L ∘ R_{G}.

This representation of linear maps with symmetries could be used in numerical analysis in the same way as was indicated for the case of linear functionals. Roughly, one wants to approximate some linear map (quite possibly the identity) that has symmetries, by choosing a simpler map that has some of the same symmetries. To check that the approximation has the desired polynomial reproduction, it is only necessary to check that certain invariant polynomials are reproduced. Typical examples of such maps include quasi-interpolants and linear multi-step methods (for solving ordinary differential equations).

Finally, those interested in other applications of group theory to numerical analysis should see the book Fässler and Stiefel [FS92].

References

[AGM93] E. L. Allgower, K. Georg, and R. Miranda (eds.) (1993), Exploiting Symmetry in

Applied and Numerical Analysis, Lectures in Applied Math. 29, AMS (Providence).

[B93] D. J. Benson (1993), Polynomial invariants of finite groups, London Math. Soc. Lecture Note Series 190, Cambridge University Press (England).

[C92] R. Cools (1992), “A survey of methods for constructing cubature formulae”, in Numerical Integration(T. O. Espelid and A. Genz, eds), NATO ASI Ser. C, Vol. 357, Kluwer (Dordrecht), 1–24.

[FS92] A. Fässler and E. Stiefel (1992), Group theoretical methods and their applications, Birkhäuser (Basel).

[FS92] J. E. Humphreys (1990), Reflection groups and Coxeter groups, Cambridge University Presss (England).

[M79] H. M. Möller (1979), “Lower bounds for the number of nodes in cubature formulae”, in Numerische Integration(G. Hämmerlin, ed), Birkhäuser (Basel), 221–230.

[So62] S. L. Sobolev (1962), “Cubature formulas on the sphere invariant under finite groups of rotations”, Soviet Math. 3, 1307–1310.

[St71] A. H. Stroud (1971), Approximate calculation of multiple integrals, Prentice-Hill Inc (Englewood Cliffs).