nLab permutation representation

Redirected from "permutation representations".
Contents

Contents

Definition

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

ρ:G×SS. \rho \;\colon\; G \times S \longrightarrow S \,.

Equivalently this is a group homomorphism

ρ:GAut Set(S) \rho \;\colon\; G \longrightarrow Aut_{Set}(S)

from GG to the group of permutations of elements of SS. As such it is a representation of GG “by permutations”.

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

ρ:GS n \rho \;\colon\; G \longrightarrow S_n

to the symmetric group S nS_n on nn elements.

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

Definition

(linear permutation representation)

The linear permutation representation of a G-set (S,ρ)(S,\rho) is the following kk-linear representation of GG:

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

    k[S]={v=sS finSv ss|S finfinite subset,v sk} 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 SS with coefficients in kk, hence is the kk-vector space for which SS is a canonical linear basis.

  2. The linear GG-action

    k[ρ]:G×k[]k[] k[\rho] \;\colon\; G \times k[\mathbb{C}] \longrightarrow k[\mathbb{C}]

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

    k[ρ](g):vsS finSv sρ(g)(s). 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 GSetG Set to the category of linear representations GRepG Rep

GSetAAk[]AAGRep. 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[]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:

(GSet,,×)AAk[]AA(GRep,,). \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 GG 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)A(G), which is the Grothendieck ring of the rig-category (GSet,,×)(G Set, \sqcup, \times) of finite G-sets;

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

Definition

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

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

K(k[]):K(GSet,,×)=A(G)AAβAAR(G)=K(GRep,,) 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 GG 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 β=K(k[])\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)𝕊 G(*) A(G) \;\simeq\; \mathbb{S}_G(\ast)

    (see there)

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

    R(G)K G(*) 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

𝕊KU \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𝔽 1\mathbb{F}_1 (see there)

𝕊K𝔽 1 \mathbb{S} \simeq K \mathbb{F}_1

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

(1)𝕊K𝔽 1KKU. \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) cohomologyrepresenting
spectrum
equivariant cohomology
of the point *\ast
cohomology
of classifying space BGB G
(equivariant)
ordinary cohomology
HZBorel equivariance
H G (*)H (BG,)H^\bullet_G(\ast) \simeq H^\bullet(B G, \mathbb{Z})
(equivariant)
complex K-theory
KUrepresentation ring
KU G(*)R (G)KU_G(\ast) \simeq R_{\mathbb{C}}(G)
Atiyah-Segal completion theorem
R(G)KU G(*)compl.KU G(*)^KU(BG)R(G) \simeq KU_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {KU_G(\ast)} \simeq KU(B G)
(equivariant)
complex cobordism cohomology
MUMU G(*)MU_G(\ast)completion theorem for complex cobordism cohomology
MU G(*)compl.MU G(*)^MU(BG)MU_G(\ast) \overset{ \text{compl.} }{\longrightarrow} \widehat {MU_G(\ast)} \simeq MU(B G)
(equivariant)
algebraic K-theory
K𝔽 pK \mathbb{F}_prepresentation ring
(K𝔽 p) G(*)R p(G)(K \mathbb{F}_p)_G(\ast) \simeq R_p(G)
Rector completion theorem
R 𝔽 p(G)K(𝔽 p) G(*)compl.(K𝔽 p) G(*)^Rector 73K𝔽 p(BG)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𝔽 1Segal 74K \mathbb{F}_1 \overset{\text{<a href="stable cohomotopy#StableCohomotopyIsAlgebraicKTheoryOverFieldWithOneElement">Segal 74</a>}}{\simeq} SBurnside ring
𝕊 G(*)A(G)\mathbb{S}_G(\ast) \simeq A(G)
Segal-Carlsson completion theorem
A(G)Segal 71𝕊 G(*)compl.𝕊 G(*)^Carlsson 84𝕊(BG)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 SGSet finS \in G Set_{fin} a finite G-set, for kk any field and k[S]Rep k(G)k[S] \in Rep_k(G) the corresponding permutation representation, the character χ k[S]\chi_{k[S]} of the permutation representation at any gGg \in G equals the Burnside marks (Def. ) of SS under the cyclic group gG\langle g\rangle \subset G generated by gg:

χ k[S](g)=|X g|k. \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 GG-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

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

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

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

χ k[S](g) =sS{1 | g(s)=s 0 | otherwise =|S g| =|S g| \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 GG a group, write, for emphasis, G sG_s for its underlying set. Let

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

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

Example

(induced representation of the trivial representation)

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

ind H G(1)k[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)AAβK(k[])AAR(G) 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 GG-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 𝔽 1\mathbb{F}_1.

Proposition

(virtual linear reps from virtual permutation reps)

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

A(G)β=K(k[])R(G) 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 GG 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\; 2D 2n2 D_{2n} for (at least) 2n122 n \leq 12

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

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

  2. is not surjective for G=/3×Q 8G = \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 2D 2n2 D_{2n} for (at least) 2n122 n \leq 12, the binary tetrahedral group, binary octahedral group, binary icosahedral group and the general linear group GL(2,𝔽 3)GL(2,\mathbb{F}_3) is checked by computer experiment in Burton-Sati-Schreiber 18.

The non-surjectivity for G=/3×Q 8G = \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=k = \mathbb{Q} we have that

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

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

(tom Dieck 09, Prop. 4.5.4)

This means that for GG not a cyclic group we have that the free abelian group A(G))A(G)) has more generators than R(G)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=/2G = \mathbb{Z}/2 be the cyclic group of order 2.

It has two conjugacy classes of subgroups,

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

  2. H=1H = 1 the trivial group;

and hence two isomorphism classes of transitive G-sets

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

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

The corresponding linear permutation representations (Def. ) are

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

    the 1-dimensional trivial representation;

  2. k[(/2)/1]11 altk[ (\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 σ/2\sigma \in \mathbb{Z}/2 is represented on k[/2]e,σk[\mathbb{Z}/2] \simeq \langle e,\sigma\rangle by the permutation matrix

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

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

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

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

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

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

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

A(/2) AAβAA R(/2) 1(/2)/(/2)0(/2)/(/2) 1 1(/2)/11(/2)/(/2) 1 alt, \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 nG = S_n a symmetric group on nn elements, the comparison morphism from the Burnside ring to the representation ring (Def. )

A(S n)βR(S n) 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 4S_4 is made explicit for k=k =\mathbb{R} in Montaldi, bottom of this page, and for k=k =\mathbb{C} at Categorified Gram-Schmidt process.

References

Textbook accounts and lecture notes include

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

Last revised on May 31, 2024 at 04:39:39. See the history of this page for a list of all contributions to it.