> A
B@!"#$%&'()*+,-./0123456789:;<=>?CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeRoot EntrydO)0U]PowerPoint Document(<~SummaryInformation( >DocumentSummaryInformation8<"(
4/0DTimes New RomanTTܖ0ܖDSymbolew RomanTTܖ0ܖ DWingdingsRomanTTܖ0ܖ@.
@n?" dd@ @@``p
m+
0AA@g4KdKd0vppp@<4BdBd x0Tʚ;Sk8ʚ;<4!d!d x0 <4dddd x0 60___PPT10
___PPT9/0GH4 K?%GGOdd and Even Permutations$Proposition 11: Let p Sn and suppose p is decomposed into transpositions as: p = t1" t2 " & .. " ta and p = s1" s2 " & .. " sb. Then a and b have the same parity; i.e. either both are odd or both are even.
Definition: Let p Sn and let i,j {1,2,3,& ,n} with i < j. The pair (i,j) is called an inversion in p if p(i) > p(j).
Lemma 1: Let (cd) be a transposition in Sn with c < d. Then the number of inversions in (cd) is 2(d c 1) + 1.
Lemma 2: If the identity permutation is written as a composition of transpositions, then the number of transpositions must be even.
Definition: Let p Sn. Then p is said to be even provided it can be written as a composition of an even number of transpositions. Otherwise, p can be written as a composition of an odd number of transpositions and it is then said to be odd.
Remark: This definition makes sense in view of Proposition 11. <" " 4"
: $$((((f((((D(( ((@((((((((((((((((D((tr0HHInversions in a Permutation$Notation: For a permutation p Sn, let Ip denote the set of inversions of p, i.e. Ip = {(i,j): 1 i < j n and p(i) > p(j)}, and let n(p) = | Ip | denote the number of inversions of p.
Proposition 12 (More powerful version of Proposition 10 and its corollary): For a permutation p Sn,
p can be expressed as a product of n(p) simple transpositions.
n(p) is the minimal number of simple transpositions required in writing p as the product of simple transpositions.
Remark 1: Proposition 12 can be proved using PMI but is not easy.
Remark 2: For those who have studied sorting: you may have noticed that bubble sort is essentially equivalent to expressing a permutation as a product of simple transpositions. ^#" " " !*=*% : , KKThe Alternating Group$Definition: For a permutation p Sn, its sign or signature is defined by sgn(p) = ( 1 ) n(p); more simply, sgn(p) = 1 if and only if p is even and sgn(p) = 1 if and only if p is odd.
Remark: the sign of a transposition is ( 1); for a k-cycle p = (x1x2..xk), sgn(p) = ( 1 ) k 1.
Proposition 13: For s, p Sn, sgn(s p) = sgn(s) sgn(p) .
Definition: in view of Proposition 13, the even permutations form a subgroup of Sn called the Alternating Group on n elements, notation An. " # AE n "&"%p2V; 0` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>f(
6L P
T Click to edit Master title style!
!
08
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0 ``
>*
0 `
@*
0L `
@*H
0h ? ̙33 Default DesignP8(
0` P
>*
0,
@*
6G `P
>*
6 e `
@*H
0h ? ̙3380___PPT10.V`
2
0\r(
\x
\ c$N
\ c$p<$
0
"p`PpH
\0h ? ̙332
0`r(
`x
` c$'
` c$H<$
0
"p`PpH
`0h ? ̙332
0lr(
lx
l c$
l c$|<$
0
"p`PpH
l0h ? ̙33r( "4T+G t/1K3H"6U1"(
4/0DTimes New RomanTTܖ0ܖDSymbolew RomanTTܖ0ܖ DWingdingsRomanTTܖ0ܖ@.
@n?" ՜.+,0
On-screen ShowRTL<~Times New RomanSymbol
WingdingsDefault DesignOdd and Even PermutationsInversions in a PermutationThe Alternating GroupFonts UsedOh+'0>`h|
CALCULUSSrinavas200191002102Microsoft PowerPoint@@Ҟ@PPz]lG=g gy--$xx--'@Times New Roman-. -2
Odd and Even Permutations."System-@Times New Roman-. 2
.-@Times New Roman-. 2
Proposition 11:.-@Times New Roman-.
2
1Let .-@Symbol-. 2
9p .-@Symbol-. 2
= .-@Times New Roman-. 2
BS .-@Times New Roman-. 2
En .-@Times New Roman-. 2
Hand suppose .-@Symbol-. 2
dp .-@Times New Roman-. $2
his decomposed into .-@Times New Roman-. $2
transpositions as: .-@Symbol-. 2
2p .-@Times New Roman-.
2
6= .-@Symbol-. 2
;t .-@Times New Roman-. 2
=1 .-@Times New Roman-. 2
? .-@Symbol-. 2
Bt .-@Times New Roman-. 2
D2 .-@Times New Roman-. 2
H .-@Times New Roman-. 2
K .-@Times New Roman-. 2
P.. .-@Times New Roman-. 2
T .-@Symbol-. 2
Xt .-@Times New Roman-. 2
Za .-@Times New Roman-.
2
]and .-@Symbol-. 2
fp .-@Times New Roman-.
2
j= .-@Symbol-. 2
ns .-@Times New Roman-. 2
q1 .-@Times New Roman-. 2
s .-@Symbol-. 2
ws .-@Times New Roman-. 2
z2 .-@Times New Roman-. 2
} .-@Times New Roman-. 2
.-@Times New Roman-. 2
.. .-@Times New Roman-. 2
.-@Symbol-. 2
s .-@Times New Roman-. 2
b .-@Times New Roman-.
2
. .-@Times New Roman-. g2
@Then a and b have the same parity; i.e. either both are odd or b.-@Times New Roman-.
2
oth .-@Times New Roman-. 2
'
are even. .-@Times New Roman-. 2
. .-@Times New Roman-. 2
.
Definition: Let .-@Symbol-. 2
.-p .-@Symbol-. 2
.1 .-@Times New Roman-. 2
.6S .-@Times New Roman-. 2
/9n .-@Times New Roman-. 2
.=and let i,j .-@Symbol-. 2
.R .-@Times New Roman-. 2
.X{1,2,3,.-@Times New Roman-. 2
.f .-@Times New Roman-. .2
.k,n} with i < j. The pair .-@Times New Roman-. $2
5
(i,j) is called an .-@Times New Roman-. 2
5/ inversion.-@Times New Roman-. 2
5Ein .-@Symbol-. 2
5Jp .-@Times New Roman-. 2
5Oif .-@Symbol-. 2
5Sp .-@Times New Roman-. 2
5V(i) > .-@Symbol-. 2
5ap .-@Times New Roman-. 2
5d(j). .-@Times New Roman-. 2
< .-@Times New Roman-. 2
<
Lemma 1: Let (.-@Times New Roman-.
2
<.cd.-@Times New Roman-. +2
<3) be a transposition in .-@Times New Roman-. 2
<bS .-@Times New Roman-. 2
=en .-@Times New Roman-. (2
<hwith c < d. Then the .-@Times New Roman-. -2
C
number of inversions in (.-@Times New Roman-.
2
CCcd.-@Times New Roman-. 2
CH ) is 2(d .-@Times New Roman-. 2
CX .-@Times New Roman-.
2
C\c .-@Times New Roman-. 2
C_ .-@Times New Roman-. 2
Cc1) + 1..-@Times New Roman-. [2
J8Lemma 2: If the identity permutation is written as a com.-@Times New Roman-. 2
Jposition of .-@Times New Roman-. g2
Q
@transpositions, then the number of transpositions must be even. .-@Times New Roman-. 2
Y .-@Times New Roman-. 2
Y
Definition: Let .-@Symbol-. 2
Y-p .-@Symbol-. 2
Y1 .-@Times New Roman-. 2
Y6S .-@Times New Roman-. 2
Z9n .-@Times New Roman-. 2
Y<. Then .-@Symbol-. 2
YJp .-@Times New Roman-. 2
YOis said to be .-@Times New Roman-.
2
Yieven.-@Times New Roman-. $2
Yuprovided it can be .-@Times New Roman-. d2
_
>written as a composition of an even number of transpositions. .-@Times New Roman-. 2
e
Otherwise, b.-@Symbol-. 2
e%p .-@Times New Roman-. U2
e)4can be written as a composition of an odd number of .-@Times New Roman-. E2
l
)transpositions and it is then said to be .-@Times New Roman-. 2
l]odd.-@Times New Roman-.
2
lf. .-@Times New Roman-. 2
s .-@Times New Roman-. f2
s?Remark: This definition makes sense in view of Proposition 11. .-Design Template
Slide Titles!_~ 0200191002200191002Current User ;dd@ @@``p
m+
0AA@g4KdKd0vppp@<4BdBd x0Tʚ;Sk8ʚ;<4!d!d x0 <4dddd x0 60___PPT10
___PPT9/0GH4 K?%GGOdd and Even Permutations$Proposition 11: Let p Sn and suppose p is decomposed into transpositions as: p = t1" t2 " & .. " ta and p = s1" s2 " & .. " sb. Then a and b have the same parity; i.e. either both are odd or both are even.
Definition: Let p Sn and let i,j {1,2,3,& ,n} with i < j. The pair (i,j) is called an inversion in p if p(i) > p(j).
Lemma 1: Let (cd) be a transposition in Sn with c < d. Then the number of inversions in (cd) is 2(d c 1) + 1.
Lemma 2: If the identity permutation is written as a composition of transpositions, then the number of transpositions must be even.
Definition: Let p Sn. Then p is said to be even provided it can be written as a composition of an even number of transpositions. Otherwise, p can be written as a composition of an odd number of transpositions and it is then said to be odd.
Remark: This definition makes sense in view of Proposition 11. <" " 4"
: $$((((f((((D(( ((@((((((((((((((((D((tr0HHInversions in a Permutation$Notation: For a permutation p Sn, let Ip denote the set of inversions of p, i.e. Ip = {(i,j): 1 i < j n and p(i) > p(j)}, and let n(p) = | Ip | denote the number of inversions of p.
Proposition 12 (More powerful version of Proposition 10 and its corollary): For a permutation p Sn,
p can be expressed as a product of n(p) simple transpositions.
n(p) is the minimal number of simple transpositions required in writing p as the product of simple transpositions.
Remark 1: Proposition 12 can be proved using PMI but is not easy.
Remark 2: For those who have studied sorting: you may have noticed that bubble sort is essentially equivalent to expressing a permutation as a product of simple transpositions. ^#" " " !*=*% : , KKThe Alternating Group$Definition: For a permutation p Sn, its sign or signature is defined by sgn(p) = ( 1 ) n(p); more simply, sgn(p) = 1 if and only if p is even and sgn(p) = 1 if and only if p is odd.
Remark: the sign of a transposition is ( 1); for a k-cycle p = (x1x2..xk), sgn(p) = ( 1 ) k 1.
Proposition 13: For s, p Sn, sgn(s p) = sgn(s) sgn(p) .
Definition: in view of Proposition 13, the even permutations form a subgroup of Sn called the Alternating Group on n elements, notation An. " # AE n "&"%p2V;rv6KR6YU1"(
4/0DTimes New RomanTTܖ0ܖDSymbolew RomanTTܖ0ܖ DWingdingsRomanTTܖ0ܖ@.
@n?" dd@ @@``p
m+
0AA@g4KdKdS0vppp@<4BdBd x0Tʚ;Sk8ʚ;<4!d!d x0 <4dddd x0 60___PPT10
___PPT9/0GH4 K?%GGOdd and Even Permutations$Proposition 11: Let p Sn and suppose p is decomposed into transpositions as: p = t1" t2 " & .. " ta and p = s1" s2 " & .. " sb. Then a and b have the same parity; i.e. either both are odd or both are even.
Definition: Let p Sn and let i,j {1,2,3,& ,n} with i < j. The pair (i,j) is called an inversion in p if p(i) > p(j).
Lemma 1: Let (cd) be a transposition in Sn with c < d. Then the number of inversions in (cd) is 2(d c 1) + 1.
Lemma 2: If the identity permutation is written as a composition of transpositions, then the number of transpositions must be even.
Definition: Let p Sn. Then p is said to be even provided it can be written as a composition of an even number of transpositions. Otherwise, p can be written as a composition of an odd number of transpositions and it is then said to be odd.
Remark: This definition makes sense in view of Proposition 11. <" " 4"
: $$((((f((((D(( ((@((((((((((((((((D((tr0HHInversions in a Permutation$Notation: For a permutation p Sn, let Ip denote the set of inversions of p, i.e. Ip = {(i,j): 1 i < j n and p(i) > p(j)}, and let n(p) = | Ip | denote the number of inversions of p.
Proposition 12 (More powerful version of Proposition 10 and its corollary): For a permutation p Sn,
p can be expressed as a product of n(p) simple transpositions.
n(p) is the minimal number of simple transpositions required in writing p as the product of simple transpositions.
Remark 1: Proposition 12 can be proved using PMI but is not easy.
Remark 2: For those who have studied sorting: you may have noticed that bubble sort is essentially equivalent to expressing a permutation as a product of simple transpositions. ^#" " " !*=*% : , KKThe Alternating Group$Definition: For a permutation p Sn, its sign or signature is defined by sgn(p) = ( 1 ) n(p); more simply, sgn(p) = 1 if and only if p is even and sgn(p) = 1 if and only if p is odd.
Remark: the sign of a transposition is ( 1); for a k-cycle p = (a1a2..ak), sgn(p) = ( 1 ) k 1.
Proposition 13: For s, p Sn, sgn(s p) = sgn(s) sgn(p) .
Definition: in view of Proposition 13, the even permutations form a subgroup of Sn called the Alternating Group on n elements, notation An. " # AE n "&"%p2V;2
0lr(
lx
l c$p
l c$ă<$
0
"p`PpH
l0h ? ̙33r8YK{KY~U1