PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] signature of a permutation (Definition)

Let $ X$ be a finite set, and let $ G$ be the group of permutations of $ X$ (see permutation group). There exists a unique homomorphism $ \chi$ from $ G$ to the multiplicative group $ \{-1,1\}$ such that $ \chi(t)=-1$ for any transposition (loc. sit.) $ t\in G$. The value $ \chi(g)$, for any $ g\in G$, is called the signature or sign of the permutation $ g$. If $ \chi(g)=1$, $ g$ is said to be of even parity; if $ \chi(g)=-1$, $ g$ is said to be of odd parity.

Proposition: If $ X$ is totally ordered by a relation $ <$, then for all $ g\in G$,

$\displaystyle \chi(g)=(-1)^{k(g)}$ (1)

where $ k(g)$ is the number of pairs $ (x,y)\in X\times X$ such that $ x<y$ and $ g(x)>g(y)$. (Such a pair is sometimes called an inversion of the permutation $ g$.)

Proof: This is clear if $ g$ is the identity map $ X\to X$. If $ g$ is any other permutation, then for some consecutive $ a,b\in X$ we have $ a<b$ and $ g(a)>g(b)$. Let $ h\in G$ be the transposition of $ a$ and $ b$. We have

$\displaystyle k(g \circ h)$ $\displaystyle =$ $\displaystyle k(g)-1$  
$\displaystyle \chi(g \circ h)$ $\displaystyle =$ $\displaystyle -\chi(g)$  

and the proposition follows by induction on $ k(g)$.



"signature of a permutation" is owned by rspuzio. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

See Also: transposition

Other names:  sign of a permutation
Also defines:  inversion, signature, parity, even permutation, odd permutation
Keywords:  permutation

This object's parent.

Attachments:
characterization of signature of a permutation (Theorem) by rm50
Log in to rate this entry.
(view current ratings)

Cross-references: induction, consecutive, identity map, clear, relation, totally ordered, odd, even, transposition, multiplicative group, homomorphism, permutation group, permutations, group, finite set
There are 51 references to this entry.

This is version 6 of signature of a permutation, born on 2003-02-26, modified 2004-10-31.
Object id is 4061, canonical name is SignatureOfAPermutation.
Accessed 14920 times total.

Classification:
AMS MSC: 03-00 (Mathematical logic and foundations :: General reference works )
 05A05 (Combinatorics :: Enumerative combinatorics :: Combinatorial choice problems )
 20B99 (Group theory and generalizations :: Permutation groups :: Miscellaneous)
Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)