5

I'm not understanding the following passage and I'm hoping someone could elucidate (for context, this is in the lead up to the definition of the sign of a permutation) where the author says:

Let $f$ be a function of $n$ variables, say $f\space\colon\mathbb{Z}^n\to\mathbb{Z}$, so we can evaluate $f\left(x_1,\ldots,x_n\right)$. Let $\sigma$ be a permutation of $J_n$ (the author previously defined $J_n=\left\{1,\ldots,n\right\}$). We define the function $\pi\left(\sigma\right)f$ by $$\pi\left(\sigma\right)f\left(x_1,\ldots,x_n\right)=f\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right).$$ Then for $\sigma,\tau\in{S_n}$ we have $\pi\left(\sigma\tau\right)=\pi\left(\sigma\right)\pi\left(\tau\right)$. Indeed, we use the definition applied to the function $g=\pi\left(\tau\right)f$ to get \begin{align*} \pi\left(\sigma\right)\pi\left(\tau\right)f\left(x_1,\ldots,x_n\right)&=\left(\pi\left(\tau\right)f\right)\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right)\\ &=f\left(x_{\sigma\tau\left(1\right)},\ldots,x_{\sigma\tau\left(n\right)}\right) \\ &=\pi\left(\sigma\tau\right)f\left(x_{1},\ldots,x_{n}\right). \end{align*} Since the identity in $S_n$ operates as the identity on functions, it follows that we have obtained an operation of $S_n$ on the set of functions.

Now if I let $G$ be the set of functions $\mathbb{Z}^n\to\mathbb{Z}$, then I agree the mapping $S_n\times G\to G$ defined by $\left(\varpi,f\left(x_1,\ldots,x_n\right)\right)\mapsto{f\left(x_{\varpi\left(1\right)},\ldots,x_{\varpi\left(n\right)}\right)}$ is well-defined since functions are well-defined, by definition.

Where I get lost is (and let me note how pleased I am that the align* environment works) \begin{align*} \pi\left(\sigma\right)\pi\left(\tau\right)f\left(x_1,\ldots,x_n\right)&=\left(\pi\left(\tau\right)f\right)\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right)\\ &=f\left(x_{\sigma\tau\left(1\right)},\ldots,x_{\sigma\tau\left(n\right)}\right) \\ &=\pi\left(\sigma\tau\right)f\left(x_{1},\ldots,x_{n}\right). \end{align*}

I would go about it as \begin{align*} \pi\left(\sigma\right)\pi\left(\tau\right)f\left(x_1,\ldots,x_n\right)&=\pi\left(\sigma\right)f\left(x_{\tau\left(1\right)},\ldots,x_{\tau\left(n\right)}\right)\\ &=f\left(x_{\sigma\tau\left(1\right)},\ldots,x_{\sigma\tau\left(n\right)}\right) \\ &=\pi\left(\sigma\tau\right)f\left(x_{1},\ldots,x_{n}\right). \end{align*}

I'm not sure why the author used $\left(\pi\left(\tau\right)f\right)$ in the RHS of the first line of the aligned equation instead of $\left(\pi\left(\tau\right)f\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right)\right)$ and I don't follow why the $\pi(\sigma)$ term 'acts' first. I get why we can take out $\sigma\tau$ since function composition is associative, thus, $(\sigma\circ\tau)(1)=\sigma(\tau(1))$.

Nobody
  • 999
  • 1
    The only reason is that perhaps the author uses a different notation for permutations, where $\sigma \tau$ really means, do $\sigma$ first, then $\tau.$ – Not a grad student Dec 25 '14 at 02:02

2 Answers2

2

I find your argument far easier to follow, but I believe that I understand the author's argument as well. And it's typical of these permutation things, which always mess me up. :(

Let's suppose that $\sigma$ sends $(1, 2, 3)$ to $(2, 3, 1)$, i.e., $\sigma(1) = 2; \sigma(2) = 3, \sigma(3) = 1$, (so $\sigma$, in my head, stands for "shift") and that $\tau$ sends $(1, 2, 3)$ to $(2, 1, 3)$ (so $\tau$ stands for "transpose").

Now let's follow through the author's statements one by one, in this context. (Note that $\sigma$ and $\tau$ do not commute, so we'll be able to check that things came out right!)

\begin{align*} \left((\pi\left(\sigma\right)\pi\left(\tau\right)\right)f\left(x_1,\ldots,x_n\right)&=\left(\pi\left(\tau\right)f\right)\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right)\\ &=\left(\pi\left(\tau\right)f\right)\left(x_2,x_3, x_1\right) \end{align*} What's going on here is that the author is applying $\pi(\sigma)$ to the function $\pi(\tau)f$. To do so, on the RHS he must apply $\pi(\tau)f$ to the permuted $x$s. That is, he must apply $\pi(\tau)f$ to $x_2, x_3, x_1$. Now he wants to further expand that expression, and writes (I'm translating to concrete indices here) \begin{align*} \left(\pi\left(\sigma\right)\pi\left(\tau\right)\right)f\left(x_1,x_2,x_3\right)&=\left(\pi\left(\tau\right)f\right)\left(x_{2},x_3,x_1\right)\\ &=f\left(\text{something}\right) \end{align*} But what should the "something" be? We have to apply the permutation $\sigma$ to the numbers $x_2, x_3, x_1$, which converts them to $x_3, x_2, x_1$.

Now if you're like me, you wanted to say "Well, just apply $\sigma$ to each of the numbers $2, 3, 1$". But that results in $1, 3, 2$. That's not what we want. The problem is that we need to swap the first and second arguments, and the way to do that is to swap the numbers to which $\sigma$ was applied in the first place! In other words, we need \begin{align*} \pi\left(\sigma\right)\pi\left(\tau\right)f\left(x_1,x_2,x_3\right)&=\left(\pi\left(\tau\right)f\right)\left(x_{2},x_3,x_1\right)\\ &=f\left(x_{\sigma(\tau(1)}, x_{\sigma(\tau(3)}, x_{\sigma(\tau(3)}\right) \end{align*} which turns out to be \begin{align*} f\left(x_{\sigma(\tau(1))}, x_{\sigma(\tau(2))}, x_{\sigma(\tau(3))}\right) &= f\left(x_{\sigma(2)}, x_{\sigma(1)}, x_{\sigma(3)}\right)\\ &= f\left(x_3, x_2, x_1\right) \end{align*} as desired.

I hope this helps. The short form is "all permutation stuff is either $ab$ or $ba$, and you can usually work out which with a simple example in $S_3$."

John Hughes
  • 93,729
  • Why should the permutation $\sigma$ applied to $(x_2,x_3,x_1)$ result in $(x_3,x_2,x_1)$ instead of $(x_1,x_2,x_3)$? I think I understand you argument up to that point, like you said, it's either $ab$ or $ba$, and, here, we're emphasizing that $\pi(\sigma)$ acts ON $\pi(\tau)f(x_1,x_2,x_3)$, so we're applying $\pi(\sigma)$ first, in a sense.

    I'm still confused why you say $(\pi(\tau)f)(x_2,x_3,x_1)$ instead of just$\pi(\tau)f(x_2,x_3,x_1)$

    I'm not sure why you have $(\pi(\tau)f)(x_{\sigma(1)},\ldots,x_{\sigma(n)})=(\pi(\tau)f)(x_2,x_3,x_1)$ because $(2,3,1)$ corresponds to $\tau$ not sigma.

     – Nobody Dec 25 '14 at 15:02
  • Actually, when you say that we have $(\pi(\tau)f)(x_2,x_3,x_1)$, did you perhaps have in mind $\pi(\sigma)f$? Because the order triple $(2,3,1)$ corresponds to the permutation $\tau$ on $(1,2,3)$, unless that is still me not understanding the notation $(\pi(\tau)f)$. As I understand it still, $(\pi(\tau)f)(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)})\equiv(\pi(\tau)f)(x_2,x_3,x_1)$ right? – Nobody Dec 25 '14 at 15:14
  • 1
    My apologies: I wrote a coherent explanation, utterly destroyed by swapping the names of $\tau$ and $\sigma$ at the start! I've changed those so that $\tau$ is the transposition, while $\sigma$ is the "right shift" permutation, and now I believe that the rest is coherent (and possibly correct!). – John Hughes Dec 25 '14 at 16:30
  • No problem! All right, this makes much more sense.

    So, if I understand, you're applying the permutation $\tau$ on the ordered tuple in the sense of permuting the 'holes' in which each element has fallen (i.e., we're labelling the 'slots' $(1,2,3)$ and permuting the the 'position' of the 'slots' themselves, as opposed to the index of the elements in these 'slots'), which ends being the same as the permutation $\sigma\circ\tau$ of the indices.

    Is that correct? The only thing I'm still unclear on, then, is the notation $\pi(\sigma)(\pi(\tau)f)$, why not (continued below...)

     – Nobody Dec 25 '14 at 17:13
  • $\pi(\sigma)(\pi(\tau)f(x_1,\ldots,x_n)$)? – Nobody Dec 25 '14 at 17:16
  • 1
    Your interpretation -- that the permutation acts on the slots, rather than the indices of elements in those slots, isperfect, and a great way to phrase it! Re: notation: you ask "Why not $\pi(\sigma)(\pi(\tau)f(x_1,\ldots,x_n)$?" Well, $\pi(\sigma)$ transforms a function (like $f$) to a new function $\pi(\sigma)(f)$ (which your author confusingly denotes $\pi(\sigma)f$). So $\pi(\sigma)$ takes "funcs $\mathbb Z^n \to Z$" to "funcs $\mathbb Z^n \to Z$" The notation you wrote would have $\pi(\sigma)$ acting on one of the values taken by the function, i.e, on $Z$...and that's a type-mismatch! – John Hughes Dec 25 '14 at 20:42
  • Excellent, thank you for the help! – Nobody Dec 26 '14 at 21:41
1

One pair of parentheses will make things clearer (hopefully):

\begin{align*} \pi\left(\sigma\right)\pi\left(\tau\right)f\left(x_1,\ldots,x_n\right)&=\pi(\sigma)\Bigl(\pi(\tau)f\Bigr)(x_1,\dots,x_n)\\ &=\left(\pi\left(\tau\right)f\right)\bigl(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\bigr). \end{align*}

Now let $\Sigma$ be the $n$ by $n$ permutation matrix associated with $\sigma$.You can rewrite $\bigl(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\bigr)$ as $(x_1,\ldots,x_n)\Sigma$. So $$\pi\left(\sigma\right)f\left(x_1,\ldots,x_n\right)=f\bigl((x_1,\ldots,x_n)\Sigma\bigr).$$ If $T$ is the permutation matrix associated with $\tau$, we can end the above computation thus: \begin{align} \left(\pi\left(\tau\right)f\right)\bigl(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\bigr)&=\left(\pi\left(\tau\right)f\right)\bigl((x_1,\ldots,x_n)\Sigma\bigr)\\ &= f\Bigl(\bigl((x_1,\ldots,x_n)\Sigma\bigr)T\Bigr)=f\bigl((x_1,\ldots,x_n)\Sigma T\bigr)\\ &=\pi(\sigma\tau)f(x_1,\dots,x_n). \end{align}

Bernard
  • 175,478