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) |

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

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$.

\[ 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 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.