Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

such that

(g1g2)*x = g1 * (g2 * x) g1,g2 (- G, x (- X

and

1*x = x x (- X.

We usually write $gx$ instead of $g *x$ . A group action of $G$ on $X$ will be indicated as $GX$ . If $G$ and $X$ are finite sets, then we speak of a finite group action.

A group action $GX$ determines a group homomorphism $f$ from $G$ to the symmetric group $SX := {s|s : X --> X is bijective}$ by

f: G --> SX, g '--> f(g) := [x '--> gx],

which is called a permutation representation of $G$ on $X$ . Usually we abbreviate $f(g)$ by writing $g$ , which is the permutation of $X$ that maps $x$ to $gx$ . For instance $1$ is always the identity on $X$ . Accordingly, the image $f(G)$ is indicated by $G$ . It is a permutation group on $X$ , i.e. a subgroup of $SX$ .

A group action $GX$ defines the following equivalence relation on $X$ . Two elements $x1,x2$ of $X$ are called equivalent, we indicate it by $x1 ~ x2$ , if there is some $g (- G$ such that $x2 = gx1$ . The equivalence class $G(x)$ of $x (- X$ with respect to $~$ is the $G$ -orbit of $x$ . Hence, the orbit of $x$ under the action of $G$ is

G(x) = {gx|g (- G}.

The set of orbits of $G$ on $X$ is indicated as

G\\X := {G(x) |x (- X}.

In general, classification of a discrete structure means the same as describing the elements of $G\\X$ for a suitable group action $GX$ .

The following theorem is easy to prove, but it shows how generally group actions can be applied.

Theorem 1. The equivalence classes of any equivalence relation can be represented as orbits under a suitable group action.

If $X$ is finite then $G$ is a finite group since it is a subgroup of the symmetric group $SX$ which is of cardinality $|X|!$ . For any $x (- X$ we have $G(x) = G(x)$ , whence $G\\X = G\\X$ . Hence, whenever $X$ is finite, each group action $GX$ can be described by a finite group action $GX$ .