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
- ↑ Dixon, John D.; Mortimer, Brian (2012-12-06) (in en). Permutation Groups. Springer Science & Business Media. pp. 5–6. ISBN 9781461207313. https://books.google.com/books?id=1SPjBwAAQBAJ.
- ↑ Robinson, Derek J. S. (2012-12-06) (in en). A Course in the Theory of Groups. Springer Science & Business Media. ISBN 9781468401288. https://books.google.com/books?id=BFrTBwAAQBAJ.
External links
![]() | Original source: https://en.wikipedia.org/wiki/Permutation representation.
Read more |