A Zephyr in Time: Parity and Sgn

Not that anyone (but me!) was interested, but last time we talked about permutations as an operation on a set of n symbols, L_n. Let us first digress into something seemingly unrelated material for a bit.

Let X₁, X₂, ..., X_n be n indeterminates (variables that do not stand for anything, if you will), and $\mathbb{Q}[X_{1},\ldots,X_{n}]$ be the vector space of polynomials on n variables with rational coefficients (over $\mathbb{Q}$ ). Then we can write a function $f\in\mathbb{Q}[X_{1},\ldots,X_{n}]$ as

$\begin{eqnarray*} f & = & f\left(\begin{array}{cccc} X_{1} & X_{2} & \ldots & X_{n}\end{array}\right)\end{eqnarray*}$

and we can apply a permutation σ on f as follows:

$\begin{eqnarray*} \sigma f & = & f\left(\begin{array}{cccc} X_{\sigma(1)} & X_{\sigma(2)} & \ldots & X_{\sigma(n)}\end{array}\right)\end{eqnarray*}$

As an example, let

$f(X_{1},X_{2},X_{3},X_{4})=4X_{1}+3X_{2}^{2}+2X_{3}^{3}+X_{4}^{4}$

and σ = (2 1 4)¹. Then

$\begin{eqnarray*} \sigma f(X_{1},X_{2},X_{3},X_{4}) & = & 4X_{4}+3X_{1}^{2}+2X_{3}^{3}+X_{2}^{4}\end{eqnarray*}$

Note: the only thing that changed are the subscripts.

We can show that permutations are linear operations on $\mathbb{Q}[X_{1},\ldots,X_{n}]$ .
Let $f,g\in\mathbb{Q}[X_{1},\ldots,X_{n}]$ , σ be a permutation, and α be a scalar. Then

$\begin{eqnarray*} \sigma[\alpha f(X_{1},\ldots,X_{n})+g(X_{1},\ldots,X_{n})] & = & \sigma[(\alpha f+g)(X_{1},\ldots,X_{n})]\\ & = & (\alpha f+g)(X_{\sigma(1)},\ldots,X_{\sigma(n)})\\ & = & \alpha f(X_{\sigma(1)},\ldots,X_{\sigma(n)})+g(X_{\sigma(1)},\ldots,X_{\sigma(n)})\\ & = & \alpha(\sigma f)+\sigma g\end{eqnarray*}$

which shows that σ is linear on $\mathbb{Q}[X_{1},\ldots,X_{n}]$ .

Also, $\sigma(f\cdot g)=(\sigma f)\cdot(\sigma g)$ (where $\cdot$ denotes multiplication of polynomials in the usual way):

$\begin{eqnarray*} \sigma[(f\cdot g)(X_{1},\ldots,X_{n})] & = & (f\cdot g)(X_{\sigma(1)},\ldots X_{\sigma(n)})\\ & = & f(X_{\sigma(1)},\ldots,X_{\sigma(n)})\cdot g(X_{\sigma(1)},\ldots,X_{\sigma(n)})\\ & = & (\sigma f)(X_{1},\ldots,X_{n})\cdot(\sigma g)(X_{1},\ldots,X_{n})\end{eqnarray*}$

That's nice, but what do these things have to do with parity?

Well, consider the function

$\begin{eqnarray*} p & = & \prod_{1\le i<j\le n}(X_{j}-X_{i})\end{eqnarray*}$

For example, if n = 3, then

$p=(X_{2}-X_{1})(X_{3}-X_{2})(X_{3}-X_{1})$

So each factor of p describes a 2-element subset of L_n (look at the subscripts) and p accounts for all 2-element subsets of L_n in this way. There are ${n \choose 2}$ such factors. Since a permutation σ is a bijection on L_n, it is a bijection on 2-element subsets of L_n. In other words, each factor of p will appear somewhere in σ p, possibly with a change in sign. This means that $\sigma p=\pm p$ , where the $\pm$ depends on the σ used. Example using n = 3, $\sigma=\left(\begin{array}{ccc} 2 & 1 & 3\end{array}\right)$ :

$\begin{eqnarray*} p & = & (X_{2}-X_{1})(X_{3}-X_{2})(X_{3}-X_{1})\\ \sigma p & = & (X_{1}-X_{3})(X_{2}-X_{1})(X_{2}-X_{3})\\ \sigma p & = & p\end{eqnarray*}$

To determine whether $\sigma p=p$ or -p, we need to find out the number of times where

$\begin{eqnarray*} \sigma(X_{j}-X_{i}) & = & X_{\sigma(j)}-X_{\sigma(i)}\end{eqnarray*}$

where $\sigma(j)<\sigma(i)$ but $i < j$ . Such a situation is called an inversion.

If σ gives an odd number of inversions, then σp = -p, and σ is called, well, odd. If σ gives an even number of inversions, then σp = p, and σ is said to be even. This gives us the parity ("oddness" or "even-ness"), or the sign, of σ.

We can define a function on the set of all permutations on L_n that gives us the sign of any permutation σ:

$\begin{eqnarray*} \mathrm{sgn}:S_{n} & \mapsto & \{-1,1\}\\ \mathrm{sgn}(\sigma) & = & \left\{ \begin{array}{rc} 1 & \textrm{if }\sigma\textrm{ even}\\ -1 & \textrm{if }\sigma\textrm{ odd }\end{array}\right.\end{eqnarray*}$

The function $\mathrm{sgn}$ has a simple but useful property: given $\sigma,\tau\in S_{n}$ , $\begin{eqnarray*} \mathrm{sgn}(\sigma\tau) & = & \mathrm{sgn}(\sigma)\cdot\mathrm{sgn}(\tau)\end{eqnarray*}$
The proof is basically "by exhaustion". I will give the proof for one of the four cases; the rest are similar.

If σ is odd and τ is even, p as defined previously on $\mathbb{Q}[X_{1},\ldots,X_{n}]$ , then

$\begin{eqnarray*} (\sigma\tau)p & = & \sigma(\tau p)=\sigma p=-p\\ \mathrm{\mathrm{sgn}(\sigma\tau)} & = & -1=(-1)1=\mathrm{sgn}(\sigma)\cdot\mathrm{sgn}(\tau)\end{eqnarray*}$

A few corollaries immediately follow:

Obviously, $\mathrm{sgn}(\sigma^{k})=[\mathrm{sgn}(\sigma)]^{k}$
Every transposition $\left(\begin{array}{rc} a & b\end{array}\right)$ is odd, since a transposition flips exactly two letters in $L_{n}$. That is, $\left(\begin{array}{rc} a & b\end{array}\right)$ implements exactly one inversion, so $\mathrm{sgn}\left(\begin{array}{rc} a & b\end{array}\right)=-1$
If $\sigma=\tau_{1}\circ\ldots\circ\tau_{k}$ is a product of k transpositions $\tau_{j}$ , then $\mathrm{sgn}(\sigma)=(-1)^{k}$ . If k is even, then any other factoring by σ into transpositions will involve an even number of them, and likewise if k is odd.
The number of even permutations on style="font-style: italic;">L_n equals the number of odd permutations, if $n\ge2$ . Proof:

Let A_n be the set of even permutations and B_n be the set of odd permutations. The mapping

$\begin{eqnarray*} A_{n} & \mapsto & B_{n}\\ \sigma & \mapsto & \sigma\circ\left(\begin{array}{rc} 1 & 2\end{array}\right)\end{eqnarray*}$

is a bijection with inverse

$\begin{eqnarray*} B_{n} & \mapsto & A_{n}\\ \tau & \mapsto & \tau\circ\left(\begin{array}{rc} 1 & 2\end{array}\right)\end{eqnarray*}$

Next up: defining determinants. Yay!

¹I use cycles as examples because I am lazy, not because permutations don't work.

[edited]
Shoot, the post width is shorter than my equation width, and I can't fix it. On the other hand, the borders are gone! Maybe I will switch to Wordpress...LaTeX looks nicer there. Or maybe not: laziness has a way of maintaining the status quo.

2 comments:

Felix said...: this looks nice
but i am wondering why you introduced those rational polynomials? i guess it's more applied than just doing permutations on {1,...,n} but what rational polynomials good for?; January 11, 2008 at 2:42 PM
Echiral said...: With respect to the polynomials, I can give two answers.

The cheap answer: when my professor covered the subject, he did it too.

My personal answer: it helps (me) further justify the terminology "odd" and "even" (what with the idea of odd/even functions in calculus), and gives a possible idea of where inversions come from.; January 14, 2008 at 9:00 PM

A Zephyr in Time

Monday, January 7, 2008

Parity and Sgn

2 comments:

About Me

Chemists

Equivalence Classes and/in Academia

Coffee-Theorem Operators

\int dq/T