I'm just starting a course on representation theory and I'm confused by this definition of permutation representation:
Given a finite set $X$ and a field $k$, we can form the vector space $kX$ of functions $X$ to $k$, with pointwise operations. Then an action of a group $G$ on $X$ induces a representation $\rho:G\rightarrow \text{Aut}(kX)$ via $\rho(g)(f)(x)=f(g^{-1}x),$ for $g\in G, f\in kX, x\in X.$ This is the permutation representation of $G$ on $X$.
In previous courses, given an action of a group $G$ on a finite set $X$, we've seen a homomorphism $G\rightarrow \text{Sym}(X)$ is induced, and called this the permutation representation of $G$.
The setup seems entirely too similar for these notions to be unrelated, but I don't understand what the connection between the two is. Also, is there a good reason for calling the $G\rightarrow \text{Sym}(X)$ homomorphism a representation, even though we have no vector space structure in this case?
Thanks.
Best Answer
You're entirely right in noticing this connection, and this is one place (of many) where some category theory makes the reason for the connection obvious.
We can represent a group $G$ as a category with one object (see here, for instance), call it $BG$. When we do this, a group action $G \curvearrowright X$ is exactly a functor $\alpha : BG \to \mathsf{Set}$ with the unique object in $BG$ sent to $X$.
More generally, if $X$ is an object of a category $\mathcal{C}$, then an action of $G$ on $X$ is a functor $\alpha : BG \to \mathcal{C}$ where the unique object is sent to $X$. For example, this gives continuous actions or smooth actions, by taking $\mathcal{C}$ to be the category of topological or smooth spaces, respectively, or linear actions (which we usually call representations) by taking $\mathcal{C}$ to be a category of modules or vector spaces.
So now say we have an action of $G$ on a set $X$, that is, we have a functor $\alpha : BG \to \mathsf{Set}$. Recall there are also functors $\mathsf{Set} \to k\text{Vect}$ sending a set $X$ to a certain $k$ vector space!
But now, since a group action (or a representation) is a functor out of $BG$, we can turn our action of $G$ on $X$ into an action of $G$ on $k^X$ (or $kX$): Compose the functors!
$$ BG^\text{op} \overset{\alpha^\text{op}}{\longrightarrow} \mathsf{Set}^\text{op} \overset{k^{-}}{\longrightarrow} k\text{Vect} $$
$$ BG \overset{\alpha}{\longrightarrow} \mathsf{Set} \overset{k[-]}{\longrightarrow} k\text{Vect} $$
Now, you're considering the first case. Notice, because $k^{-}$ is a contravariant functor that we had to take the opposite of our action $\alpha$ from $BG$ to $\mathsf{Set}$. As a quick exercise, you should convince yourself that this "opposite"-ness is the reason $(gf)(x) = f(g^{-1}x)$.
We could also consider the second case, and for completeness, I'll say something about it. The idea here is that each $x \in X$ is a basis element of $kX$. So each function $g \cdot - : X \to X$ extends linearly to a map on $kX$. Notice when we take this definition, because $k[-]$ is covariant, we don't have to worry about inverting $g$:
$$ g(x_1 + x_2) = gx_1 + gx_2 $$
As for why we call both of these things "representations", as I understand it, we historically thought of groups $G$ defined axiomatically as "abstract groups", and we used the word "representation" to indicate that we were representing an abstract group by something "concrete", like a group of symmetries of some object, a group of matrices, etc. This is why the theorem that each $G$ embeds into a symmetric group is sometimes called Cayley's Representation Theorem. Nowadays, though, we usually think of linear representations (that is, actions of $G$ on some module or vector space) when we think of representation theory, and so I believe this older terminology is falling out of fashion.
I hope this helps ^_^