Show that $ \varphi(\sigma) = (\sigma(p) \sigma (q))\sigma$ is a bijection.

Question

For fixed integers $p<q$ that are in $\{1,...,n\}$ define a map $\varphi:S_n \rightarrow S_n$ as: $$ \varphi(\sigma) = (\sigma(p), \sigma (q))\sigma$$ Show that $\varphi$ is a bijection.

My attempt was:

Since the cardinalities between the domain and codomain are equal we only need to show injectivity or surjectivity. We will show surjectivity. Let $\gamma$ equal an element of the codomain. Then:

$$\gamma = \varphi(\sigma) \Rightarrow \gamma = (\sigma(p), \sigma (q))\sigma \Rightarrow$$ $$(\sigma(p), \sigma (q))\gamma = (\sigma(p) ,\sigma (q))(\sigma(p), \sigma (q))\sigma $$

Since $(\sigma(p), \sigma (q))$ is a permutation of length two, if we multiply $(\sigma(p), \sigma (q))$ by itself we get the identity permutation. Therefore: $$(\sigma(p), \sigma (q))\gamma = \sigma $$

Which shows that every element in the domain maps back to an element in the codomain. Therfore surjectivity and therefore bijectivity.

However, I was informed that this proof is incorrect, but I cannot figure out where my logic is wrong. Any thoughts?

Ok, I appreciate the hint but I've struggled with this enough. How can I find a permutation $\rho$ such that: $$(\sigma(p), \sigma (q))\sigma = \sigma \rho$$

Thanks,

Answer 1

I think injective maybe easier.

Let $\sigma,\tau\in S_{n}$ be such that $\varphi(\sigma)=\varphi(\tau)$. Then $$ (\sigma(p), \sigma (q))\sigma =(\tau(p), \tau(q))\tau. $$ We want to show that $\sigma=\tau$. That is, $\sigma(x)=\tau(x)$ for all $x\in\{1,\cdots,n\}$.

Let $x\in \{1,\cdots,n\}$. Then $$((\sigma(p),\sigma(q))\sigma)(x)=((\tau(p), \tau(q))\tau)(x),$$ hence $$(\sigma(p),\sigma(q))(\sigma(x))=(\tau(p), \tau(q))(\tau(x)).$$ If $x=p$, then $\sigma(q)=\tau(q)$. If $x=q$, then $\sigma(p)=\tau(p)$. If $x\neq p,q$, then $\sigma(x)=\tau(x)$. Hence $\sigma(x)=\tau(x)$ for all $x\in\{1,\cdots,n\}$. So $\sigma=\tau$. Hence $\varphi$ is injective.

Edit: Surjectivity:

Let $\alpha\in S_{n}$. Define $\beta:\{1,\cdots,n\}\to \{1,\cdots,n\}$ by $\beta(p)=\alpha(q)$, $\beta(q)=\alpha(p)$, and $\beta(x)=\alpha(x)$ for $x\neq p,q$. We can check $\beta\in S_{n}$: ($\beta$ is injective): let $\beta(y)=\beta(z)$. If $y=p$, suppose $z=q$, then $\alpha(q)=\alpha(p)$, contradiction, since $\alpha$ is injective. Suppose $z\neq p,q$. Then $\alpha(q)=\alpha(z)$, contradiction. So $z=p$. Similarly, if $y=q$, we have $z=q$. If $y\neq p,q$, then $\alpha(y)=\beta(z)$. So $z\neq p,q$. So $\alpha(y)=\alpha(z)$. Hence $y=z$. So $\beta\in S_{n}$.

We show that $\varphi(\beta)=\alpha$.

Let $x\in\{1,\cdots,n\}$. Then $$(\varphi(\beta))(x)=((\beta(p),\beta(q))\beta)(x)=(\beta(p),\beta(q))(\beta(x)).$$ If $x=p$, then $(\varphi(\beta))(p)=(\beta(p),\beta(q))(\beta(p))=\beta(q)=\alpha(p)$. Similarly, $(\varphi(\beta))(q)=\alpha(q)$. If $x\neq p,q$, then $(\varphi(\beta))(x)=(\beta(p),\beta(q))(\beta(x))=\beta(x)=\alpha(x)$. So $(\varphi(\beta))(x)=\alpha(x)$ for all $x\in\{1,\cdots,n\}$. Hence $\varphi(\beta)=\alpha$. So $\varphi$ is surjective.

Answer 2

One problem with this proof is that $(\sigma(p)\ \sigma(q))$ isn't 'uniformly' defined; you can't get it from $\gamma$ without knowing the $\sigma$ that generated it, so you haven't shown that there aren't two different permutations $\sigma, \tau$ that map to the same $\gamma$.

To show the problem in a slightly different context: imagine the mapping $\mathcal{P}:S_n\mapsto S_{n-1}$ that's gotten by just 'removing' $n$ from the permutation and contracting; e.g. for $n=4$, if the initial permutation is $\sigma\in S_4=(1\ 2\ 4)$ then the new permutation is $\mathcal{P}(\sigma)\in S_3=(1\ 2)$, etc. Then it's absolutely the case that for every permutation $\sigma\in S_n$ there's a permutation $\rho_\sigma$ such that $\rho_\sigma P(\sigma)=\sigma$, so you can ostensibly 'recover' $\sigma$ from $P(\sigma)$ — but because $\rho_\sigma$ isn't the same permutation for each $\sigma$ this isn't actually the one-to-one mapping it looks like.

You're on the right track, though; you just need to find a 'uniform' way of doing this. Hint: can you find a permutation $\rho$ such that $(\sigma(p)\ \sigma(q))\sigma = \sigma\rho$, and show that $\rho$ is the same for all $\sigma$?