Abstract Nonsense

Crushing one theorem at a time

Permutations (Pt. VI Alternate Definitions of the Sign of a Permutation cont.)


Point of post: This is a literal continuation of this post. I just hate when that dark grey to light grey thing happens. Just pretend that there was no lapse in the posts

And so we continue…


So, from this we may finally verify that the definition of \text{sgn}(\pi) given in terms of \Delta(x_1,\cdots,x_n) is the same as the on given by us.

Theorem Let

\displaystyle \text{sgn}'(\pi)=\frac{\Delta(x_{\pi(1)},\cdots,x_{\pi(n)})}{\Delta(x_1,\cdots,x_n)}

Then, \text{sgn}=\text{sgn}'

Proof: For the sake of notational convenience let

\begin{bmatrix}1 & \cdots & x_1^{n-1}\\ \vdots & \ddots & \vdots\\ 1 & \cdots & x_n^{n-1}\end{bmatrix}

be denoted by V(x_1,\cdots,x_n). Then, with this in mind we see from our previous theorems that for any \pi\in S_n

\displaystyle \begin{aligned}\text{sgn}'(\pi) &=\frac{\Delta(x_{\pi(1)},\cdots,x_{\pi(n)})}{\Delta(x_1,\cdots,x_n)}\\ &= \frac{(-1)^{n\choose 2}\det V(x_{\pi(1)},\cdots,x_{\pi(n)})}{(-1)^{n\choose 2}\det V(x_1,\cdots,x_n)}\\ &= \frac{\det V(x_{\pi(1)},\cdots,x_{\pi(n)})}{\det V(x_1,\cdots,x_n)}\\ &= \frac{\det\left(P_{\pi}^T V(x_1,\cdots,x_n)\right)}{\det V(x_1,\cdots,x_n)}\\ &= \frac{\det\left(P_{\pi}^T\right)\det\left(V(x_1,\cdots,x_n)\right)}{\det V(x_1,\cdots,x_n)}\\ &= \det \left(P_{\pi}^T\right)\\ &= \det P_\pi \\ &= \text{sgn}(\pi)\end{aligned}

and since \pi was arbitrary it follows that \text{sgn}'=\text{sgn}. \blacksquare

Conclusion

So, now that we have proven that the two definitions are the same we ask “Why would someone want to define it this way?” Well, any kid off the street having read the motivation given in terms of the alternating function will spit out this definition. In other words, depending how the subject is motivated this definition is most natural. Also, arithmetic with the sign function is reduced to arithmetic of polynomials, which is always a plus.

Ok, so how is it not good? There is no obvious reason why the above definition of \text{sgn}(\pi) gives negative one for odd permutations and one for even permutations, and considering this was really the point of the sign function, this is a pretty big minus.

 

Inversions

Because of the similarity between this definition and the usual one, we merely mention it.

Now we can talk about the, admittedly simpler, topic of inversions as discussed in Shilov (viz. ref. 1 pg. 5-6). Intuitively an inversion is just a transposition in a different guise. Namely, we call an inversion induced on [n] by some \pi\in S_n a rearrangement such that  x<y and \pi(x)>\pi(y). Then, if N(\pi) is the number of inversions induced by \pi then we define \text{sgn}(\pi)=(-1)^{N(\pi)}.

This one is barely different from the definition we know of the sign of a permutation. It is just a relabeling of the idea of a transposition.

 

References:

1. Lang, Serge. Undergraduate Algebra. New York: Springer, 1998. Print.

2. Shilov, G. E. Linear Algebra. Englewood Cliffs, NJ: Prentice-Hall, 1971. Print.

Advertisements

November 8, 2010 - Posted by | Algebra, Halmos, Linear Algebra | , , , , ,

1 Comment »

  1. […] and is the number of inversions of a permutation. In doing so we find an interesting way to prove that […]

    Pingback by Interesting Combinatorial Sum Involving Inversions « Abstract Nonsense | December 27, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: