Permutation representation

In mathematics, the term permutation representation of a (typically finite) group [math]\displaystyle{ G }[/math] can refer to either of two closely related notions: a representation of [math]\displaystyle{ G }[/math] 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 [math]\displaystyle{ G }[/math] on a set [math]\displaystyle{ X }[/math] is a homomorphism from [math]\displaystyle{ G }[/math] to the symmetric group of [math]\displaystyle{ X }[/math]:

[math]\displaystyle{ \rho\colon G \to \operatorname{Sym}(X). }[/math]

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

[math]\displaystyle{ G\times X \to X. }[/math]

See the article on group action for further details.

Linear permutation representation

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

[math]\displaystyle{ \rho\colon G\to \operatorname{GL}_n(K) }[/math]

which maps [math]\displaystyle{ g\in G }[/math] to the corresponding permutation matrix (here [math]\displaystyle{ K }[/math] is an arbitrary field).^[2] That is, [math]\displaystyle{ G }[/math] acts on [math]\displaystyle{ K^n }[/math] 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 [math]\displaystyle{ G }[/math] as a group of permutation matrices. One first represents [math]\displaystyle{ G }[/math] as a permutation group and then maps each permutation to the corresponding matrix. Representing [math]\displaystyle{ G }[/math] as a permutation group acting on itself by translation, one obtains the regular representation.

Character of the permutation representation

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

This follows since, if we represent the map [math]\displaystyle{ \rho(g) }[/math] with a matrix with basis defined by the elements of [math]\displaystyle{ X }[/math] we get a permutation matrix of [math]\displaystyle{ X }[/math]. 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 [math]\displaystyle{ X }[/math] 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 [math]\displaystyle{ X }[/math].

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

[math]\displaystyle{ \chi((12))=\operatorname{tr}(\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{bmatrix})=1 }[/math] as only 3 is fixed

[math]\displaystyle{ \chi((123))=\operatorname{tr}(\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\end{bmatrix})=0 }[/math] as no elements of [math]\displaystyle{ X }[/math] are fixed, and

[math]\displaystyle{ \chi(1)=\operatorname{tr}(\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix})=3 }[/math] as every element of [math]\displaystyle{ X }[/math] is fixed.

References

External links

• https://mathoverflow.net/questions/286393/how-do-i-know-if-an-irreducible-representation-is-a-permutation-representation

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Permutation representation. Read more