Permutation representation

☆ Save On Wikipedia ↗

In mathematics, the term permutation representation of a (typically finite) group G {\displaystyle G} {\displaystyle G} can refer to either of two closely related notions: a representation of G {\displaystyle G} {\displaystyle G} as a group of permutations, or as a group of permutation matrices. The term also refers to the combination of the two.

Abstract permutation representation

A permutation representation of a group G {\displaystyle G} {\displaystyle G} on a set X {\displaystyle X} {\displaystyle X} is a homomorphism from G {\displaystyle G} {\displaystyle G} to the symmetric group of X {\displaystyle X} {\displaystyle X}:

ρ : G → Sym ⁡ ( X ) . {\displaystyle \rho \colon G\to \operatorname {Sym} (X).} {\displaystyle \rho \colon G\to \operatorname {Sym} (X).}

The image ρ ( G ) ⊂ Sym ⁡ ( X ) {\displaystyle \rho (G)\subset \operatorname {Sym} (X)} {\displaystyle \rho (G)\subset \operatorname {Sym} (X)} is a permutation group and the elements of G {\displaystyle G} {\displaystyle G} are represented as permutations of X {\displaystyle X} {\displaystyle X}.[1] A permutation representation is equivalent to an action of G {\displaystyle G} {\displaystyle G} on the set X {\displaystyle X} {\displaystyle X}:

G × X → X . {\displaystyle G\times X\to X.} {\displaystyle G\times X\to X.}

See the article on group action for further details.

Linear permutation representation

If G {\displaystyle G} {\displaystyle G} is a permutation group of degree n {\displaystyle n} {\displaystyle n}, then the permutation representation of G {\displaystyle G} {\displaystyle G} is the linear representation of G {\displaystyle G} {\displaystyle G}

ρ : G → GL n ⁡ ( K ) {\displaystyle \rho \colon G\to \operatorname {GL} _{n}(K)} {\displaystyle \rho \colon G\to \operatorname {GL} _{n}(K)}

which maps g ∈ G {\displaystyle g\in G} {\displaystyle g\in G} to the corresponding permutation matrix (here K {\displaystyle K} {\displaystyle K} is an arbitrary field).[2] That is, G {\displaystyle G} {\displaystyle G} acts on K n {\displaystyle K^{n}} {\displaystyle K^{n}} by permuting the standard basis vectors.

This notion of a permutation representation can, of course, be composed with the previous one to represent an arbitrary abstract group G {\displaystyle G} {\displaystyle G} as a group of permutation matrices. One first represents G {\displaystyle G} {\displaystyle G} as a permutation group and then maps each permutation to the corresponding matrix. Representing G {\displaystyle G} {\displaystyle G} as a permutation group acting on itself by translation, one obtains the regular representation.

Character of the permutation representation

Given a group G {\displaystyle G} {\displaystyle G} and a finite set X {\displaystyle X} {\displaystyle X} with G {\displaystyle G} {\displaystyle G} acting on the set X {\displaystyle X} {\displaystyle X} then the character χ {\displaystyle \chi } {\displaystyle \chi } of the permutation representation is exactly the number of fixed points of X {\displaystyle X} {\displaystyle X} under the action of ρ ( g ) {\displaystyle \rho (g)} {\displaystyle \rho (g)} on X {\displaystyle X} {\displaystyle X}. That is χ ( g ) = {\displaystyle \chi (g)=} {\displaystyle \chi (g)=} the number of points of X {\displaystyle X} {\displaystyle X} fixed by ρ ( g ) {\displaystyle \rho (g)} {\displaystyle \rho (g)}.

This follows since, if we represent the map ρ ( g ) {\displaystyle \rho (g)} {\displaystyle \rho (g)} with a matrix with basis defined by the elements of X {\displaystyle X} {\displaystyle X} we get a permutation matrix of X {\displaystyle X} {\displaystyle X}. Now the character of this representation is defined as the trace of this permutation matrix. An element on the diagonal of a permutation matrix is 1 if the point in X {\displaystyle X} {\displaystyle X} is fixed, and 0 otherwise. So we can conclude that the trace of the permutation matrix is exactly equal to the number of fixed points of X {\displaystyle X} {\displaystyle X}.

For example, if G = S 3 {\displaystyle G=S_{3}} {\displaystyle G=S_{3}} and X = { 1 , 2 , 3 } {\displaystyle X=\{1,2,3\}} {\displaystyle X=\{1,2,3\}} the character of the permutation representation can be computed with the formula χ ( g ) = {\displaystyle \chi (g)=} {\displaystyle \chi (g)=} the number of points of X {\displaystyle X} {\displaystyle X} fixed by g {\displaystyle g} {\displaystyle g}. So

χ ( ( 12 ) ) = tr ⁡ ( [ 0 1 0 1 0 0 0 0 1 ] ) = 1 {\displaystyle \chi ((12))=\operatorname {tr} ({\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}})=1} {\displaystyle \chi ((12))=\operatorname {tr} ({\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}})=1} as only 3 is fixed
χ ( ( 123 ) ) = tr ⁡ ( [ 0 1 0 0 0 1 1 0 0 ] ) = 0 {\displaystyle \chi ((123))=\operatorname {tr} ({\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}})=0} {\displaystyle \chi ((123))=\operatorname {tr} ({\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}})=0} as no elements of X {\displaystyle X} {\displaystyle X} are fixed, and
χ ( 1 ) = tr ⁡ ( [ 1 0 0 0 1 0 0 0 1 ] ) = 3 {\displaystyle \chi (1)=\operatorname {tr} ({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}})=3} {\displaystyle \chi (1)=\operatorname {tr} ({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}})=3} as every element of X {\displaystyle X} {\displaystyle X} is fixed.

See also

  • Cayley's theorem, which shows all groups have a regular permutation representation

References

  1. Dixon, John D.; Mortimer, Brian (2012-12-06). Permutation Groups. Springer Science & Business Media. pp. 5–6. ISBN 9781461207313.
  2. Robinson, Derek J. S. (2012-12-06). A Course in the Theory of Groups. Springer Science & Business Media. ISBN 9781468401288.