Permutation Characters

Given a group action, there is a representation, and a hence character; we will discuss these next.

Let $F$ be a field, which will soon be $\mathbb{C}$, and let $X$ be a set. We will describe the free vector space on $X$ over $F$. For our applications, $X$ will be finite, but we won't assume that. We can define $\mathfrak{F}$ to be the set of all formal linear combinations
\[ \sum_{x \in X} a_x \cdot x, \qquad a_x \in F, \qquad a_x = 0\quad\text{for all but finitely many $x \in X$}\}. \] (2.6.1)

That explanation is all you really need to know, but we will give another, more formal one. We will characterize the free vector space by a universal property.

We recall that if $V$ is a vector space, a subset $B$ is called a basis if every element of $V$ can be written uniquely as $\sum_{x \in B} a_x \cdot x$ where $a_x = 0$ for all but finitely many $x$. Note that even though this appears to be an infinite series if $B$ is infinite, the sum $\sum_{x \in B} a_x \cdot x$ is essentially a finite sum, so the definition makes sense without any recourse to analysis. It may be proved (using Zorn's Lemma) that every vector space has a basis.

Proposition 2.6.1: Fix a field $F$. Let $X$ be a set.

(i) There exists a map $\delta : X \longrightarrow \mathfrak{F}_X$ into a vector space $\mathfrak{F}_X$ such that if $f : X \longrightarrow V$ is any map into a vector space, then there is a unique linear transformation $F : \mathfrak{F}_X \longrightarrow V$ such that $f = F \circ \delta$.

(ii) If $\delta : X \longrightarrow \mathfrak{F}_X$ is as in (i), then $\delta$ is injective, and $\delta (X)$ is a basis of $\mathfrak{F}_X$.

Intuitively, if we identify $X$ with its image under $\delta$, the free vector space $\mathfrak{F}$ on $X$ is just a vector space with basis $X$, which takes us back to our original informal description.

Proof. (Click to Expand/Collapse)

Let $\mathfrak{F}_X$ be the vector space of maps $v : X \longrightarrow F$ such that $v (x) = 0$ for all but finitely many $x \in X$. Let $\delta (x) = \delta_x$ be the map $X \longrightarrow F$ defined by \[ \delta_x (y) = \left\{ \begin{array}{ll} 1 & \text{if $y = x$,}\\ 0 & \text{otherwise} . \end{array} \right. \] We note that $\mathfrak{F}_X$ is spanned by $\delta (X)$, and indeed $\delta (X)$ is a basis of $\mathfrak{F}_X$. This means that any element $v \in \mathfrak{F}_X$ can be written uniquely as

\[ v = \sum_{x \in X} a_x \cdot \delta_x, \hspace{2em} \text{$a_x = 0$ for all but finitely many $x \in X$} . \]

(2.6.2)

To see this, observe that \[ \sum_{x \in X} a_x \cdot \delta_x (y) = a_y . \] Thus the identity $v = \sum_x a_x \delta_x$ is equivalent to $a_x = v (x)$ for all $x \in X$; since $\mathfrak{F}_X$ is the set of functions that vanish off a finite set, it is indeed true that every $v \in \mathfrak{F}_X$ can be uniquely written this way, and so $\delta (X)$ is a basis of $\mathfrak{F}_X$.

To verify the universal property, let $f : X \longrightarrow V$ be any map of $X$ into a vector space. We want to show that there is a unique linear transformation $F : \mathfrak{F}_X \longrightarrow V$ such that $f = F \circ \delta$. Since $\delta (X)$ is a basis of $\mathfrak{F}_X$ every $v \in \mathfrak{F}_X$ can be written uniquely in the form (2.6.2), and then if $F$ is such a linear transformation, we must have \[ F (v) = \sum_{x \in X} a_x F (\delta_x) = \sum_{x \in X} a_x (F \circ \delta) (x) = \sum_{x \in X} a_x f (x) . \] This formula proves the uniqueness of $F$, and it also proves existence, since if we define $F$ by this formula it is easy to check that $F (\delta_x) = f (x)$, i.e. $f = F \circ \delta$. Thus (i) is proved.

Now to prove (ii), we note that we have proven that there exists $\delta : X \longrightarrow \mathfrak{F}_X$ satisfying the conditions of (i), and that particular $\delta$ was injective and had image a basis of $\mathfrak{F}_X$. However since the statement of (i) – as opposed to its proof – made no reference to a particular construction, what we actually need to show is that if $\delta' : X \longrightarrow \mathfrak{F}'_X$ is any map of $X$ into a vector space satisfying these conditions, then $\delta'$ is injective and has image a basis of $\mathfrak{F}_X'$. But it follows by the usual argument (see Proposition 1.8.1 and the discussion that follows it) that there exists an isomorphism $\alpha : \mathfrak{F}_X \longrightarrow \mathfrak{F}'_X$ such that $\delta' = \alpha \circ \delta$. It follows easily that the injectivity of $\delta$ and the fact that $\delta (X)$ is a basis of $\mathfrak{F}_X$ implies the corresponding properties for $\delta'$.

Since $\delta$ is injective, we will identify $X$ with its image in the free vector space $\mathfrak{F}_X$, regarding $\mathfrak{F}_X$ as, indeed, the "vector space with basis $X$.'' This brings us back to our original characterization of $\mathfrak{F}_X$ as the set of formal sums (2.6.1).

Example 2.6.1: If G is a finite group, the group algebra $\mathbb{C}[G]$ can be regarded as the free vector space over $G$, with the multiplication \[ \left( \sum_{x \in G} a_x \cdot x \right) \left( \sum_{y \in G} b_y \cdot y \right) = \sum_{z \in G} \left( \sum_{\begin{array}{c} x, y \in G\\ x y = z \end{array}} a_x b_y \right) \cdot z. \] This multiplication agrees with the original multiplication defined as the convolution (2.3.2) – see Exercise 2.6.1.

Exercise 2.6.1: Explain why the convolution multiplication defined in (2.3.2) agrees with the one just defined.

Now as with the free group, the free vector space is a functor (from the category of sets to the category of $F$-vector spaces). This means that if $\phi : X \longrightarrow Y$ is a map of sets, then there is induced a linear transformation $\mathfrak{F} \phi : \mathfrak{F}_X \longrightarrow \mathfrak{F}_Y$ such that \[ \begin{array}{lll} X & \mathop{\longrightarrow}\limits^{\phi} & Y\\ \downarrow \small{\delta} & & \downarrow \small{\delta}\\ \mathfrak{F}_X & \mathop{\longrightarrow}\limits^{\mathfrak{F} \phi} & \mathfrak{F}_Y \end{array} \] commutes. Indeed, the existence of a unique map $\mathfrak{F} \phi$ that makes this diagram commute follows from the universal property by taking $V =\mathfrak{F}Y$ and $f$ to be the composite $\delta \circ \phi$.

Exercise 2.6.2: If $\psi : Y \longrightarrow Z$ is another map, show how the universal property implies the functoriality property $\mathfrak{F}(\psi \circ \phi) =\mathfrak{F} \psi \circ \mathfrak{F} \phi$.

Now let $G$ be a finite group, and $X$ a finite set on which $G$ acts. We will consider a representation of $G$ on $\mathfrak{F}_X$, and its character. (The finiteness of $G$ and $X$ will will not be used until we get to the character, when we will need $\mathfrak{F}_X$ to be finite-dimensional.)

If $g \in G$ then let $\phi (g) : X \longrightarrow X$ be the map $\phi (g) x = g \cdot x$. Thus $\phi : G \longrightarrow \operatorname{Bij} (X)$ is he group homomorphism in Proposition 1.5.1. By the functoriality property of the free group, we get induced linear transformations $\mathfrak{F} \phi (G) : \mathfrak{F}_X \longrightarrow \mathfrak{F}_X$. It follows easily from Exercise 2.6.2 that since $\phi : G \longrightarrow \operatorname{Bij} (X)$ is a group homomorphism, $\mathfrak{F} \phi : G \longrightarrow \operatorname{GL} (\mathfrak{F}_X)$ is a group homomorphism, that is, a representation. This is the permutation representation obtained from the group action of $G$ on $X$; occasionally we might use the term permutation representation to refer to the group action itself.

To give an example, let us start with the action of $S_4$ on the standard set $X$ with 4 elements. To avoid confusion, we take $X =\{a, b, c, d\}$ instead of $\{1, 2, 3, 4\}$. Let $g = (a c) (b d)$. This is the linear transformation that interchanges the first and third basis vectors, and also the second and fourth. So using the basis $a, b, c, d$ of $\mathfrak{F}_X$ this transformation is represented by the matrix \[ \mathfrak{F} \phi (g) = \left(\begin{array}{cccc} & & 1 & \\ & & & 1\\ 1 & & & \\ & 1 & & \end{array}\right) . \] (As usual, entries that are left blank are zero.)

By a fixed point of a bijection $\Phi : X \longrightarrow X$ we mean an element $x \in X$ such that $\Phi (x) = x$. Or given a group action, a fixed point of $g \in G$ on $X$ will mean an element $x \in X$ such that $g x = x$; in our previous notation, this is the same as a fixed point of the bijection $\phi (g)$. Note that this terminology evokes the metaphor mentioned in Remark 1.5.2.

We will use the notation $\Pi_X : G \longrightarrow \operatorname{GL} (\mathfrak{F}_X)$ for the permutation representation, since it is less cumbersome. The character of $\Pi_X$ will be called the permutation character, and it is useful since it has a very concrete interpretation, and is easy to compute.

Proposition 2.6.2: Let $X$ be a set on which $G$ acts. Then the character $\chi$ of the permutation action is given by the following formula: \[ \chi (g) = \text{the number of fixed points of $g$ on $X$} . \]

Proof. (Click to Expand/Collapse)

Let us represent the linear transformation $\Pi_X (g)$ by its matrix with respect to the basis $X$. This is a permutation matrix, that is, one with one nonzero entry in each row and column, and the rows and columns are indexed by the elements of $X$. Thus in the $x$-th column the nonzero entry is in the $y$-th row, where $y = g \cdot x$. From this, it is clear that the nonzero diagonal entries correspond to fixed points of $g$ on $X$, and taking the trace counts the number of fixed points.

Exercise 2.6.3: Suppose that $G$ acts transitively on $X$, and let $H$ be the isotropy subgroup of an element $x \in X$. Let $\chi$ be the permutation character of this group action, and let $1_H$ be the trivial character of $H$. Prove that $\chi = (1_H)^G$ is the induced character.

Proposition 2.6.3: Let $\chi$ be the permutation character of an action of $G$ on $X$. Then \[ \frac{1}{|G|} \sum_{g \in G} \chi (g) \] is the number of orbits of $X$.

Proof. (Click to Expand/Collapse)

Let us count the set $\{(g, x) \in G \times X| g x = x\}$ in two different ways. First, the cardinality of this set equals \[ \sum_{g \in G} |\{x \in X| g x = x\}| = \sum_{g \in G} \chi (g) . \] On the other hand, it equals \[ \sum_{x \in X} |\{g \in G| g x = x\}| = \sum_{x \in X} |G_x |, \] where $G_x$ is the isotropy subgroup of $X$. Let $\mathcal{O}_1, \cdots, \mathcal{O}_h$ be the distinct orbits for the action of $G$ on $X$. Then by Theorem 1.5.1, if $x \in \mathcal{O}_i$ then $\mathcal{O}_i$ is in bijection with $G / G_x$, so $|\mathcal{O}_i | = |G| / |G_x |$. Thus $|G_x |$ has a constant value $|G| / |\mathcal{O}_i |$ on the orbit, and we see that \[ \sum_{g \in G} \chi (g) = \sum_{i = 1}^h \sum_{x \in \mathcal{O}_i} |G_x | = \sum_{i = 1}^h \sum_{x \in \mathcal{O}_i} \frac{|G|}{|\mathcal{O}_i |} = h|G|. \] Thus \[ \frac{1}{|G|} \sum_{g \in G} \chi (g) = h, \] the number of orbits.

Exercise 2.6.4: Give a different proof of this based on Lemma 2.4.8. Specifically, show that if \[ \xi = \sum_{x \in X} a_x \cdot x \in \mathfrak{F}_X \] then $\xi$ is an invariant if and only if $a_x$ is constant on each orbit. Hence conclude that the dimension of the module of invariants is equal to the number of orbits.

The special case where the action of $G$ on $X$ is transitive is particularly useful. In that case, $\Pi$ contains one copy of the trivial representation. By this we mean that when we write out the permutation representation as a direct sum of irreducible representations, exactly one of those irreducibles is the trivial representation. Indeed, Proposition 2.6.3 shows that $\left\langle \chi, 1 \right\rangle = 1$, where $1 = \chi_1$ is the character of the trivial representation: $\chi_1 (g) = 1$ for all $g \in G$ and the statement now follows from Lemma 2.4.8. Alternatively, if you did Exercise 2.6.4 you saw this directly.

Most useful of all is the case where the action of $G$ is doubly transitive. This means that $|X| > 1$, and given a pair of distinct elements $x_1, x_2 \in X$ and another pair of distinct elements $y_1, y_2 \in X$, there exists an element $g \in G$ such that $g x_1 = y_1$ and $g x_2 = y_2$. More generally, we say that the action is $n$-transitive if $|X| \ge n$ and if, given distinct elements $x_1, \cdots, x_n \in X$ and another batch distinct elements $y_1, \cdots, y_n$ of distinct elements, there exists $g \in G$ such that $g x_i = y_i$. Finally we say that the action is sharply $n$-transitive if it is $n$-transitive and moreover the $g \in G$ such that $g x_i = y_i$ is unique.

Exercise 2.6.5: Show that $S_n$ acting on $\{1, 2, \cdots, n\}$ is $n$-transitive, $A_n$ is sharply $(n - 2)$-transitive, and that in its action on $\mathbb{P}^1 (\mathbb{F}_p)$ the group $\operatorname{PGL}_2 (\mathbb{F}_p)$ is sharply 3-transitive.

The importance of doubly transitive permutation representations is that they give rise to irreducible characters, as we will now see.

Theorem 2.6.1: Let $X$ be a group on which $G$ acts transitively. The action is doubly transitive if and only if $\chi - 1$ is an irreducible character of $G.$

Proof. (Click to Expand/Collapse)

First, we have already seen that since the action of $G$ on $X$ is transitive we have $\left\langle \chi, 1 \right\rangle = 1$. Now when $\chi$ is decomposed into a sum of irreducible characters, \[ \chi = \sum_{i = 1}^h d_i \chi_i, \] if the irreducibles are ordered so that $\chi_1 = 1$, we have $d_i = 1$, and so \[ \left\langle \chi, \chi \right\rangle = \sum_{i = 1}^h d_i^2 = 1 + \sum_{i = 2}^h d_i^2 . \] Now $\chi - 1$ is an irreducible character if and only if exactly one $d_i = 1$ with $i \ge 2$, and the remaining $d_j = 0$ (with $j \ge 2$). This formula shows that $\chi - 1$ is an irreducible character if and only if $\left\langle \chi, \chi \right\rangle = 2$.

Since $\chi$ is real, \[ \left\langle \chi, \chi \right\rangle = \frac{1}{|G|} \sum_{g \in G} \chi (g)^2 = \left\langle \chi^2, 1 \right\rangle . \] We observe that $\chi^2$ is the permutation character of the action of $G$ on $X \times X$, since if $g \in G$ has $\chi (g)$ fixed points on $X$, it has $\chi (g)^2$ fixed points on $X \times X$ – one for every pair of fixed points in the action on $X$. Therefore $\left\langle \chi^2, 1 \right\rangle$ is the number of orbits in the action of $G$ on $X \times X$.

We have proved that $\chi - 1$ is irreducible if and only if there are exactly $2$ such orbits. One orbit is obvious – it is the diagonal $\Delta =\{(x, x) | x \in X\}$. So $\chi - 1$ is irreducible if and only if $X \times X - \Delta$ consists of a single orbit. Now this means that if $(x_1, x_2) \in X \times X - \Delta$ and $(y_1, y_2) \in X \times X - \Delta$, then there is a $g \in G$ such that \[ g (x_1, x_2) = (y_1, y_2), \] which is exactly the definition of double transitivity.

A particular permutation action that we like is the right regular representation. (We could also use the left regular representation and draw similar conclusions.) Let $G$ act on itself by the action $g \ast x = x g^{- 1}$, where we are avoiding the $\cdot$ notation for this group action in favor of $\ast$ to avoid confusion with the multiplication in the group itself, which appears in the definition of the action. Let us check that the permutation representation is the right regular representation on $G$, which was defined by (2.3.6). We must identify the free vector space on $G$ with the space $L^2 (G)$ of functions on $G$. Thus \[ \sum_{x \in G} a_x \cdot x \in \mathfrak{F}_G \] corresponds to the function $f (x) = a_x$. Now \[ g \ast \sum_{x \in G} a_x \cdot x = \sum_{x \in G} a_x \cdot x g^{- 1} = \sum_{x \in G} a_{x g} \cdot x \] corresponds to the function $(\rho (g) f) (x) = f (x g)$ as in (2.3.6).

Theorem 2.6.2: The character of the right regular representation has two expressions: \[ \chi_{\operatorname{reg}} = \sum_{i = 1}^h d_i \chi_i, \hspace{2em} d_i = \dim (V_i) = \chi_i (1), \] and \[ \chi_{\operatorname{reg}} (g) = \left\{ \begin{array}{ll} |G| & \text{if $g = 1,$}\\ 0 & \text{otherwise.} \end{array} \right. \]

Proof. (Click to Expand/Collapse)

We recall that as $G$-modules \[ L^2 (G) \cong \bigoplus_i \mathcal{R}_i, \hspace{2em} \mathcal{R}_i \cong d_i V_i \hspace{2em} ( \text{i.e. $V_i \oplus \cdots \oplus V_i$ with $d_i = \dim (V_i$) copies.)} \] This gives the first expression. As for the second, the character of the regular representation is a permutation character, so $\chi_{\operatorname{reg}} (g)$ is the number of fixed points, which is obviously zero unless $g = 1$ (since $g \ast x = x g^{- 1}$ equals $x$ if and only if $g = 1$) and $|G|$ otherwise.