Permutation representation
# Permutation representation

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

    $\rho \colon G\to \operatorname {Sym} (X).$

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

    $G\times X\to X.$

See the article on group action for further details.

## Linear permutation representation

If $G$ is a permutation group of degree $n$, then the permutation representation of $G$ is the linear representation of $G$

    $\rho \colon G\to \operatorname {GL} _{n}(K)$

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

## Character of the permutation representation

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

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

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

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