nLab permutation representation

Definition

For $G$ a group (typically a finite group), consider a G-set $(S, \rho)$, hence a set $S$ (typically a finite set), equipped with an action of $G$

$$\rho \;\colon\; G \times S \longrightarrow S \,.$$

Equivalently this is a group homomorphism

$$\rho \;\colon\; G \longrightarrow Aut_{Set}(S)$$

from $G$ to the group of permutations of elements of $S$. As such it is a representation of $G$ “by permutations”.

Specifically, if $S$ is a finite set and an isomorphism $S \simeq \{1, 2, 3, \cdots, n\}$ is understood, it is equivalently a group homomorphism

$$\rho \;\colon\; G \longrightarrow S_n$$

to the symmetric group $S_n$ on $n$ elements.

For $k$ any field (or, more generally, any commutative ring, but one mostly considers fields) this $G$-action may be linearized to a $k$-linear representation of $G$ in an evident way:

Definition

(linear permutation representation)

The linear permutation representation of a G-set $(S,\rho)$ is the following $k$-linear representation of $G$:

1. The underlying $k$-vector space is the freely spanned vector space $k[S]$, whose elements (vectors) are the formal linear combinations

   $$k[S] \;=\; \left\{ v =\underset{ s \in S_{fin} \subset S }{\sum} v_s \, s \;\vert\; S_{fin} \, \text{finite subset} ,\; v_s \in k \right\}$$

   of elements of $S$ with coefficients in $k$, hence is the $k$-vector space for which $S$ is a canonical linear basis.

2. The linear $G$-action

   $$k[\rho] \;\colon\; G \times k[\mathbb{C}] \longrightarrow k[\mathbb{C}]$$

   is given on linear basis-elements $s \in S \hookrightarrow k[S]$ by $\rho$, which uniquely defines it by linearity to act on a general vector as

   $$k[\rho]\left(g\right) \;\colon\; v \;\mapsto\; \underset{ s \in S_{fin} \subset S }{\sum} v_s \, \rho(g)(s) \,.$$

This concept immediately generalizes to groupoid representations and so forth, see also at infinity-action the section Examples – Discrete group actions on sets.

Properties

Functoriality

Proposition

(functoriality of linear permutation representations)

The construction of linear permutation representations (Def. ) evidently extends to a functor from the category of G-sets $G Set$ to the category of linear representations $G Rep$

$$G Set \overset{ \phantom{AA} k[-] \phantom{AA} }{\longrightarrow} G Rep \,.$$

Both of these categories are rig categories with respect to disjoint union and Cartesian product on the left, and direct sum and tensor product of representations on the right.

The functor $k[-]$ is canonically a homomorphism of rig-categories in that in that it is canonically a strong monoidal functor for both “addition” and “multiplication” monoidal structures:

$$\big(G Set, \sqcup, \times\big) \overset{ \phantom{AA} k[-] \phantom{AA} }{\longrightarrow} \big(G Rep, \oplus, \otimes \big) \,.$$

Comparison from Burnside- to representation ring

Let $G$ be a finite group and assume all G-sets in the following to be finite sets and all linear representations to be finite dimensional.

Consider

1. the Burnside ring $A(G)$, which is the Grothendieck ring of the rig-category $(G Set, \sqcup, \times)$ of finite G-sets;

2. the representation ring $R(G)$, which is the Grothendieck ring of the rig category $(G Rep, \oplus, \otimes)$ of finite-dimensional linear G-representations.

Definition

(permutation representations make ring homomorphism from Burnside ring to representation ring)

Since forming $k$-linear permutation representations (Def. ) is a rig-functor $G Set\overset{k[-]}{\longrightarrow} G Rep$ (Prop. ), under passing to Grothendieck rings it induces a ring homomorphism

$$K(k[-]) \;\colon\; K( G Set, \sqcup, \times ) = \; A(G) \overset{\phantom{AA} \beta \phantom{AA}}{\longrightarrow} R(G) \; = K( G Rep, \oplus, \otimes)$$

from the Burnside ring of $G$ to its representation ring.

This homomorphism is traditionally denoted $\beta$, as shown.

Its kernel is known as the Brauer relations (e.g. Bartel-Dokchitser 11).

Remark

(virtual linear permutation representations)

The image of the comparison morphism $\beta = K(k[-])$ (Def. ) may be called the virtual linear permutation representations.

Remark

(virtual permutation representations from equivariant stable cohomotopy into equivariant K-theory)

Under the identification

1. of the Burnside ring with the equivariant stable cohomotopy of the point

   $$A(G) \;\simeq\; \mathbb{S}_G(\ast)$$

   (see there)

2. of the representation ring with the equivariant K-theory of the point

   $$R(G) \;\simeq\; K_G(\ast)$$

   (see there)

the ring homomorphism of Def. should be image under forming equivariant cohomology of the point of the initial morphism of E-infinity ring spectra

$$\mathbb{S} \longrightarrow KU$$

from the sphere spectrum to KU.

Noticing that we may regard stable cohomotopy/the sphere spectrum as being the algebraic K-theory of the “field with one element” $\mathbb{F}_1$ (see there)

$$\mathbb{S} \simeq K \mathbb{F}_1$$

we may regard this as extension of scalars along $\mathbb{F}_1 \to \mathbb{C}$ followed by the comparison map between algebraic and topological K-theory:

(1)$$\mathbb{S} \simeq K\mathbb{F}_1 \to K\mathbb{C} \to KU \,.$$

graphics grabbed from SS19

See also at equivariant Hopf degree theorem.

(equivariant) cohomology	representing spectrum	equivariant cohomology of the point $\ast$	cohomology of classifying space $B G$
(equivariant) ordinary cohomology	HZ	Borel equivariance $H^\bullet_G(\ast) \simeq H^\bullet(B G, \mathbb{Z})$
(equivariant) complex K-theory	KU	representation ring $KU_G(\ast) \simeq R_{\mathbb{C}}(G)$	Atiyah-Segal completion theorem $R(G) \simeq KU_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {KU_G(\ast)} \simeq KU(B G)$
(equivariant) complex cobordism cohomology	MU	$MU_G(\ast)$	completion theorem for complex cobordism cohomology $MU_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {MU_G(\ast)} \simeq MU(B G)$
(equivariant) algebraic K-theory	$K \mathbb{F}_p$	representation ring $(K \mathbb{F}_p)_G(\ast) \simeq R_p(G)$	Rector completion theorem $R_{\mathbb{F}_p}(G) \simeq K (\mathbb{F}_p)_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {(K \mathbb{F}_p)_G(\ast)} \!\! \overset{\text{<a href="https://ncatlab.org/nlab/show/Rector+completion+theorem">Rector 73</a>}}{\simeq} \!\!\!\!\!\! K \mathbb{F}_p(B G)$
(equivariant) stable cohomotopy	$K \mathbb{F}_1 \overset{\text{<a href="stable cohomotopy#StableCohomotopyIsAlgebraicKTheoryOverFieldWithOneElement">Segal 74</a>}}{\simeq}$ S	Burnside ring $\mathbb{S}_G(\ast) \simeq A(G)$	Segal-Carlsson completion theorem $A(G) \overset{\text{<a href="https://ncatlab.org/nlab/show/Burnside+ring+is+equivariant+stable+cohomotopy+of+the+point">Segal 71</a>}}{\simeq} \mathbb{S}_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {\mathbb{S}_G(\ast)} \!\! \overset{\text{<a href="https://ncatlab.org/nlab/show/Segal-Carlsson+completion+theorem">Carlsson 84</a>}}{\simeq} \!\!\!\!\!\! \mathbb{S}(B G)$

Characters

The characters of permutation representations are the Burnside marks of the underlying G-sets:

Proposition

(mark homomorphism on cyclic groups agrees with characters of corresponding permutation representations)

For $S \in G Set_{fin}$ a finite G-set, for $k$ any field and $k[S] \in Rep_k(G)$ the corresponding permutation representation, the character $\chi_{k[S]}$ of the permutation representation at any $g \in G$ equals the Burnside marks (Def. ) of $S$ under the cyclic group $\langle g\rangle \subset G$ generated by $g$:

$$\chi_{k[S]}\big( g \big) \;=\; \left\vert X^{\langle g \rangle} \right\vert \;\in\; \mathbb{Z} \longrightarrow k \,.$$

Hence the mark homomorphism (Def. ) of $G$-sets restricted to cyclic subgroups coincides with the characters of their permutation representations.

This statement immediately generalizes from plain representations to virtual representations, hence to the Burnside ring.

(e.g. tom Dieck 09, (2.15))

Proof

By definition of character of a linear representation, we have that

$$\chi_{k[S]}(g) = tr_{k[S]}(g)$$

is the trace of the linear endomorphism $k[S] \overset{g}{\to} k[S]$ of the given permutation representation.

Now the canonical $k$-linear basis for $k[S]$ is of course the set $S$ itself, and so

$$\begin{aligned} \chi_{k[S]}(g) & = \underset{ s \in S }{\sum} \left\{ \array{ 1 &\vert& g(s) = s \\ 0 &\vert& \text{otherwise} } \right. \\ & = \left\vert S^g \right\vert \\ & = \left\vert S^{\langle g \rangle} \right\vert \end{aligned}$$

Here in the first step we spelled out the definition of trace in the canonical basis, and in the second step we observed that the fixed point set of a cyclic group equals that of any one of its generating elements.

Examples

Basic examples

Example

(regular representation)

For $G$ a group, write, for emphasis, $G_s$ for its underlying set. Let

$$\array{ G \times G_s &\overset{ \rho_\ell }{\longrightarrow}& G_s \\ (g,s) &\mapsto& g \cdot s }$$

be the canonical action of $G$ on itself, by left multiplication in the group. The corresponding linear permutation representation $(k[G_s], k(\rho_\ell))$ (Def. ) is called the regular representation of $G$.

Example

(induced representation of the trivial representation)

Let $G$ be a finite group and $H \overset{\iota}{\hookrightarrow} G$ a subgroup-inclusion. Then the induced representation in Rep(G) of the trivial representation $\mathbf{1} \in Rep(H)$ is the permutation representation $k[G/H]$ of the coset G-set $G/H$:

$$\mathrm{ind}_H^G\big( \mathbf{1}\big) \;\simeq\; k[G/H] \,.$$

This follows directly as a special case of the general formula for induced representations of finite groups (this Example).

See at induced representation of the trivial representation for more.

Virtual permutation representations

We discuss here examples of the operation of forming virtual linear permutation representations (Remark ), regarded as the canonical ring homomorphism

$$A(G) \overset{ \phantom{AA} \beta \coloneqq K(k[-]) \phantom{AA} }{\longrightarrow} R(G)$$

from Def. .

For emphasis, notice that among plain linear representations the linear permutation representations generally form but a tiny sub-class, i.e. generically a linear representation is not a linear permutation representation. But this statement may change radically as we pass to virtual representations:

If the ring homomorphism $\beta$ (Def. ) is a surjective function, this means that in fact all virtual linear $G$-representation are virtual linear permutation representations. This is not the case for all groups, but it is the case for large classes of groups! This is the content of Prop. below.

Notice that when this is the case, it means that the representation theory of the given group is, in a precise sense, purely combinatorial, or equivalently, in view of (1), that it is fully determined over the absolute ground field $\mathbb{F}_1$.

Proposition

(virtual linear reps from virtual permutation reps)

For ground field $k = \mathbb{Q}$ the rational numbers, the comparison morphism

$$A(G) \overset{ \beta = K(k[-]) }{\longrightarrow} R(G)$$

from Def. , which sends virtual G-sets to their permutation rep virtual linear G-representations,

1. is surjective for $G$ among one of the following classes of finite groups (not mutually exclusive)

   1. cyclic groups,

   2. symmetric groups,

   3. p-groups,

   4. binary dihedral groups$\;$ $2 D_{2n}$ for (at least) $2 n \leq 12$

   5. the binary tetrahedral group, binary octahedral group, binary icosahedral group,

   6. the general linear group $GL(2,\mathbb{F}_3)$

2. is not surjective for $G = \mathbb{Z}/3 \times Q_8$ (direct product of cyclic group of order 3 with quaternion group or order 8);

3. is injective precisely for cyclic groups,

4. hence is an isomorphism precisely for cyclic groups.

Proof

Isomorphy for the case of cyclic groups is spelled out in tom Dieck 09, Example (4.4.4).

Surjectivity for the case of symmetric groups follows from the theory of Young diagrams (Dress 86, section 3), see also Example below for further pointers.

The proof of surjectivity for p-primary groups is due to Segal 72. (As Segal remarks on his first page, it may also be deduced from Feit 67 (14.3). See also Ritter 72.) The proof is recalled as tom Dieck 79, Theorem 4.4.1.

Surjectivity for binary dihedral groups $2 D_{2n}$ for (at least) $2 n \leq 12$, the binary tetrahedral group, binary octahedral group, binary icosahedral group and the general linear group $GL(2,\mathbb{F}_3)$ is checked by computer experiment in Burton-Sati-Schreiber 18.

The non-surjectivity for $G = \mathbb{Z}/3 \times Q_8$ was remarked in Serre 77, p. 104.

To see that injectivity holds at most for cyclic groups, notice that over $k = \mathbb{Q}$ we have that

1. the number of isomorphism classes of irreducible representations of $G$ equals the number of conjugacy classes of cyclic subgroups;

2. the number of isomorphism classes of indecomposable (transitive) G-sets (i.e. $G$-orbit types) is the number of conjugacy classes of all subgroups.

(tom Dieck 09, Prop. 4.5.4)

This means that for $G$ not a cyclic group we have that the free abelian group $A(G))$ has more generators than $R(G)$, so that $\beta$ cannot be injective.

A more general analysis of the cokernel of $\beta$ is due to Berz 94, reviewed and expanded on in Hambleton-Taylor 99. See also Bartel-Dokchitser 14, p. 1.

Example

(virtual permutation representations of the group of order 2

Let $G = \mathbb{Z}/2$ be the cyclic group of order 2.

It has two conjugacy classes of subgroups,

1. $H =\mathbb{Z}/2$ the group itself,

2. $H = 1$ the trivial group;

and hence two isomorphism classes of transitive G-sets

1. $(\mathbb{Z}/2)/(\mathbb{Z}/2) = \ast$ the point with the trivial action,

2. $(\mathbb{Z}/2)/1 = \mathbb{Z}/2$ the group itself, with the regular action.

The corresponding linear permutation representations (Def. ) are

1. $k[ (\mathbb{Z}/2)/(\mathbb{Z}/2)] \;\simeq\; \mathbf{1}$,

   the 1-dimensional trivial representation;

2. $k[ (\mathbb{Z}/2)/1 ] \; \simeq\; \mathbf{1} \oplus \mathbf{1}_{alt}$,

   the direct sum of the 1d trivial representation with the alternating representation.

To see the second item, observe that the non-trivial element $\sigma \in \mathbb{Z}/2$ is represented on $k[\mathbb{Z}/2] \simeq \langle e,\sigma\rangle$ by the permutation matrix

$$\left( \array{ 0 & 1 \\ 1 & 0 } \right) \,,$$

which is diagonalizable over $k = \mathbb{Z}$ with eigenvectors

1. $\left[\array{ 1 \\ 1 }\right]$ of eigenvalue $1$, spanning the trivial representation $\mathbf{1}$ of dimension 1;

2. $\left[\array{ 1 \\ -1 }\right]$ of eigenvalue $-1$, spanning the alternating representation $\mathbf{1}_{alt}$ of dimension 1.

Hence, the abelian group underlying the representation ring may be identified with the linear span

$$R(\mathbb{Z}/2) \;\simeq_k\; \langle \mathbf{1}, \mathbf{1}_{alt} \rangle$$

and the comparison morphism from the Burnside ring (Def. ) is

$$\array{ A(\mathbb{Z}/2) &\overset{ \phantom{AA} \beta \phantom{AA}}{\longrightarrow}& R(\mathbb{Z}/2) \\ 1\, (\mathbb{Z}/2)/(\mathbb{Z}/2) \;-\; 0\, (\mathbb{Z}/2)/(\mathbb{Z}/2) &\mapsto& \mathbf{1} \\ 1\, (\mathbb{Z}/2)/1 \;-\; 1\, (\mathbb{Z}/2)/(\mathbb{Z}/2) &\mapsto& \mathbf{1}_{alt} \,, }$$

which is manifestly an isomorphism, in accord with Prop. .

Example

(virtual permutation representations of symmetric groups)

For $G = S_n$ a symmetric group on $n$ elements, the comparison morphism from the Burnside ring to the representation ring (Def. )

$$A(S_n) \overset{\beta}{\longrightarrow} R(S_n)$$

is a surjective map over $\mathbb{Q}$ but also over $\mathbb{R}$ and $\mathbb{C}$.

The special case of $S_4$ is made explicit for $k =\mathbb{R}$ in Montaldi, bottom of this page, and for $k =\mathbb{C}$ at Categorified Gram-Schmidt process.

Related concepts

• table of marks

• symmetric group

• covering space

• regular representation

• Burnside ring, stable cohomotopy

• groupoidification

• ∞-permutation representation

• permutation D-brane

• RR-field tadpole cancellation

References

Textbook accounts and lecture notes include

• Charles Curtis, Irving Reiner, from p. 43 on in Representation theory of finite groups and associative algebras, AMS 1962

• Walter Feit, Characters of Finite Groups, W. A. Benjamin New York, 1967

• Tammo tom Dieck, Section 4 of Transformation Groups and Representation Theory, Lecture Notes in Mathematics 766, Springer 1979 (doi:10.1007/BFb0085965)

• Tammo tom Dieck, section 1.2 of Representation theory, 2009 (pdf)

Original articles include

• D. L. Johnson, Minimal Permutation Representations of Finite Groups, American Journal of Mathematics Vol. 93, No. 4 (Oct., 1971), pp. 857-866 (jstor:2373739)

• J. Ritter, Ein Induktionssatz fuer rationale Charaktere von nilpotenten Gruppen, J. Reine Angew. Math. 254 (1972), 133–151

• Graeme Segal, Permutation representations of finite $p$-groups, Quart. J. Math. Oxford (2) 23 (1972), 375–381 (doi:10.1093/qmath/23.4.375)

• Jean-Pierre Serre, Linear Representations of Finite Groups, Graduate Texts in Math., vol. 42, Springer–Verlag, New York, 1977

• Andreas Dress, Congruence relations characterizing the representation ring of the symmetric group, Journal of Algebra 101, 350-364 (1986) (pdf, pdf)

• G. Berz, Permutationsbasen fuer endliche Gruppen, Ph.D. thesis, Augsburg, 1994 (Zbl0924.20003)

• I. Hambleton, L. R. Taylor, Rational permutation modules for finite groups, Math. Z. 231 (1999), 707–726 (pdf)

• Alex Bartel, Tim Dokchitser, Brauer relations in finite groups, J. Eur. Math. Soc. 17 (2015), 2473-2512 (arXiv:1103.2047)

• Alex Bartel, Tim Dokchitser, Rational representations and permutation representations of finite groups, Math. Ann. 364 no. 1 (2016), 539-558 (arXiv:1405.6616)

• Vladimir V. Kornyak, An Algorithm to Decompose Permutation Representations of Finite Groups: Polynomial Algebra Approach (arXiv:1801.09786)

• Simon Burton, Hisham Sati, Urs Schreiber, Lift of fractional D-brane charge to equivariant Cohomotopy theory (arXiv:1812.09679, Python code)

See also

• James Montaldi, Real representations of finite groups

• PlanetMath, representation ring vs burnside ring