In mathematics, the term permutation representation of a (typically finite) group G {\displaystyle G} can refer to either of two closely related notions: a representation of 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} on a set X {\displaystyle X} is a homomorphism from G {\displaystyle G} to the symmetric group of X {\displaystyle X} :
ρ : G → Sym ( X ) . {\displaystyle \rho \colon G\to \operatorname {Sym} (X).}The image ρ ( G ) ⊂ Sym ( X ) {\displaystyle \rho (G)\subset \operatorname {Sym} (X)} is a permutation group and the elements of G {\displaystyle G} are represented as permutations of X {\displaystyle X} .1 A permutation representation is equivalent to an action of G {\displaystyle G} on the set X {\displaystyle X} :
G × X → X . {\displaystyle G\times X\to X.}See the article on group action for further details.
Linear permutation representation
If G {\displaystyle G} is a permutation group of degree n {\displaystyle n} , then the permutation representation of G {\displaystyle G} is the linear representation of G {\displaystyle G}
ρ : G → GL n ( K ) {\displaystyle \rho \colon G\to \operatorname {GL} _{n}(K)}which maps g ∈ G {\displaystyle g\in G} to the corresponding permutation matrix (here K {\displaystyle K} is an arbitrary field).2 That is, G {\displaystyle G} acts on 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} as a group of permutation matrices. One first represents G {\displaystyle G} as a permutation group and then maps each permutation to the corresponding matrix. Representing 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} and a finite set X {\displaystyle X} with G {\displaystyle G} acting on the set X {\displaystyle X} then the character χ {\displaystyle \chi } of the permutation representation is exactly the number of fixed points of X {\displaystyle X} under the action of ρ ( g ) {\displaystyle \rho (g)} on X {\displaystyle X} . That is χ ( g ) = {\displaystyle \chi (g)=} the number of points of X {\displaystyle X} fixed by ρ ( g ) {\displaystyle \rho (g)} .
This follows since, if we represent the map ρ ( g ) {\displaystyle \rho (g)} with a matrix with basis defined by the elements of X {\displaystyle X} we get a permutation matrix of 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} 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} .
For example, if G = S 3 {\displaystyle G=S_{3}} and 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)=} the number of points of X {\displaystyle X} fixed by 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} 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} as no elements of 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} as every element of X {\displaystyle X} is fixed.External links
References
Dixon, John D.; Mortimer, Brian (2012-12-06). Permutation Groups. Springer Science & Business Media. pp. 5–6. ISBN 9781461207313. 9781461207313 ↩
Robinson, Derek J. S. (2012-12-06). A Course in the Theory of Groups. Springer Science & Business Media. ISBN 9781468401288. 9781468401288 ↩