Menu Close

1-Find-the-sign-of-odd-or-even-or-pality-of-permutation-1-2-3-4-5-6-7-8-2-prove-that-any-permutation-S-S-where-S-is-a-finite-set-can-be-written-as-a-product-of-disjoint-cycle-help-

Tinku Tara 0 Comments
Pin




Question Number 192341 by Mastermind last updated on 15/May/23
1) Find the sign of odd or even (or pality) of permutation θ=(1 2 3 4 5 6 7 8) 2) prove that any permutation θ:S→S where S is a finite set can be written as a product of disjoint cycle help!
$$\left.\mathrm{1}\right)\:\mathrm{Find}\:\mathrm{the}\:\mathrm{sign}\:\mathrm{of}\:\mathrm{odd}\:\mathrm{or}\:\mathrm{even}\:\left(\mathrm{or}\:\mathrm{pality}\right) \\ $$$$\mathrm{of}\:\mathrm{permutation}\:\theta=\left(\mathrm{1}\:\mathrm{2}\:\mathrm{3}\:\mathrm{4}\:\mathrm{5}\:\mathrm{6}\:\mathrm{7}\:\mathrm{8}\right) \\ $$$$ \\ $$$$\left.\mathrm{2}\right)\:\mathrm{prove}\:\mathrm{that}\:\mathrm{any}\:\mathrm{permutation} \\ $$$$\theta:\mathrm{S}\rightarrow\mathrm{S}\:\mathrm{where}\:\mathrm{S}\:\mathrm{is}\:\mathrm{a}\:\mathrm{finite}\:\mathrm{set}\:\mathrm{can}\:\mathrm{be} \\ $$$$\mathrm{written}\:\mathrm{as}\:\mathrm{a}\:\mathrm{product}\:\mathrm{of}\:\mathrm{disjoint} \\ $$$$\mathrm{cycle} \\ $$$$ \\ $$$$\mathrm{help}! \\ $$
Answered by aleks041103 last updated on 15/May/23
1) θ=(1 2 3 4 5 6 7 8)= =(1 2)(2 3)(3 4)(4 5)(5 6)(6 7)(7 8) (a b) is odd ⇒sgn(θ)=sgn(Π_(k=1) ^7 (k k+1))= =Π_(k=1) ^7 sgn((k k+1))=(−1)^7 =−1=sgn(θ) ⇒θ is odd 2)We will prove thag for every s∈S_n , s can be represented as a product of cycles. Proof by induction: n=1: s=id=(1) n=2: s= { ((id=(1)(2))),(( (((1 2)),((2 1)) )=(1 2))) :} n=m: let ∀s′∈S_m can be repr. as a product of disjoint cycles n=m+1: Let s∈S_n 1st case: s(n)=n ⇒ s= (((1 2 3 ... n−1 n)),((∗ ∗ ∗ ... ∗ n)) ) ⇒s≡s′= (((1 2 3 ... n−1)),((∗ ∗ ∗ ... ∗ )) ) ∈S_m By ind. hyp. s′=c_1 ...c_r , where c_i is a cycle. ⇒s=c_1 ...c_r . We note that n∉c_1 ,...,c_r 2nd case: s(n)=k≠n, let s′′=(k n)s ⇒((k n)s)(n)=(k n)(s(n))=(k n)(k)=n ⇒s′′ falls under the 1st case. ⇒s′′=(k n)s=c_1 ...c_r ⇒s=(k n)c_1 c_2 ...c_r If k∉c_1 ,...,c_r , then (k n) is disjoint with c_1 ,...,c_r and we are done. Else, let k∈c_p . Since c_1 ,...,c_r are disjoint they commute. ⇒s=(n k)c_p c_1 ...c_r c_p is of the form (∗ ... ∗ k ∗ ... ∗)=(k ∗ ... ∗) ⇒s=(n k)(k ∗ ... ∗)c_1 ...c_r = =(n k ∗ ... ∗)c_1 ...c_r =c_p ′c_1 ...c_r Obviously, c_p ′,c_1 ,...,c_r are disjoint. We are done! ⇒By our induction hypothesis, we proved that every element of a finite symmetric group can be represented as a product of disjoint cycles.
$$\left.\mathrm{1}\right)\:\theta=\left(\mathrm{1}\:\mathrm{2}\:\mathrm{3}\:\mathrm{4}\:\mathrm{5}\:\mathrm{6}\:\mathrm{7}\:\mathrm{8}\right)= \\ $$$$=\left(\mathrm{1}\:\mathrm{2}\right)\left(\mathrm{2}\:\mathrm{3}\right)\left(\mathrm{3}\:\mathrm{4}\right)\left(\mathrm{4}\:\mathrm{5}\right)\left(\mathrm{5}\:\mathrm{6}\right)\left(\mathrm{6}\:\mathrm{7}\right)\left(\mathrm{7}\:\mathrm{8}\right) \\ $$$$ \\ $$$$\left({a}\:{b}\right)\:{is}\:{odd} \\ $$$$\Rightarrow{sgn}\left(\theta\right)={sgn}\left(\underset{{k}=\mathrm{1}} {\overset{\mathrm{7}} {\prod}}\left({k}\:{k}+\mathrm{1}\right)\right)= \\ $$$$=\underset{{k}=\mathrm{1}} {\overset{\mathrm{7}} {\prod}}{sgn}\left(\left({k}\:{k}+\mathrm{1}\right)\right)=\left(−\mathrm{1}\right)^{\mathrm{7}} =−\mathrm{1}={sgn}\left(\theta\right) \\ $$$$\Rightarrow\theta\:{is}\:{odd} \\ $$$$ \\ $$$$\left.\mathrm{2}\right){We}\:{will}\:{prove}\:{thag}\:{for}\:{every}\:{s}\in{S}_{{n}} ,\:{s}\:{can} \\ $$$${be}\:{represented}\:{as}\:{a}\:{product}\:{of}\:{cycles}. \\ $$$${Proof}\:{by}\:{induction}: \\ $$$${n}=\mathrm{1}:\:{s}={id}=\left(\mathrm{1}\right) \\ $$$${n}=\mathrm{2}:\:{s}=\begin{cases}{{id}=\left(\mathrm{1}\right)\left(\mathrm{2}\right)}\\{\begin{pmatrix}{\mathrm{1}\:\mathrm{2}}\\{\mathrm{2}\:\mathrm{1}}\end{pmatrix}=\left(\mathrm{1}\:\mathrm{2}\right)}\end{cases} \\ $$$${n}={m}:\:{let}\:\forall{s}'\in{S}_{{m}} \:{can}\:{be}\:{repr}.\:{as}\:{a}\:{product} \\ $$$${of}\:\:{disjoint}\:{cycles} \\ $$$$\: \\ $$$${n}={m}+\mathrm{1}: \\ $$$${Let}\:{s}\in{S}_{{n}} \\ $$$$\underline{\mathrm{1}{st}\:{case}}:\:{s}\left({n}\right)={n}\:\Rightarrow\:{s}=\begin{pmatrix}{\mathrm{1}\:\mathrm{2}\:\mathrm{3}\:…\:{n}−\mathrm{1}\:{n}}\\{\ast\:\ast\:\ast\:…\:\:\:\:\:\ast\:\:\:\:{n}}\end{pmatrix} \\ $$$$\Rightarrow{s}\equiv{s}'=\begin{pmatrix}{\mathrm{1}\:\mathrm{2}\:\mathrm{3}\:…\:{n}−\mathrm{1}}\\{\ast\:\ast\:\ast\:…\:\:\:\:\:\ast\:}\end{pmatrix}\:\in{S}_{{m}} \\ $$$${By}\:{ind}.\:{hyp}.\:{s}'={c}_{\mathrm{1}} …{c}_{{r}} ,\:{where}\:{c}_{{i}} \:{is}\:{a}\:{cycle}. \\ $$$$\Rightarrow{s}={c}_{\mathrm{1}} …{c}_{{r}} . \\ $$$${We}\:{note}\:{that}\:{n}\notin{c}_{\mathrm{1}} ,…,{c}_{{r}} \\ $$$$\underline{\mathrm{2}{nd}\:{case}}:\:{s}\left({n}\right)={k}\neq{n},\:{let}\:{s}''=\left({k}\:{n}\right){s} \\ $$$$\Rightarrow\left(\left({k}\:{n}\right){s}\right)\left({n}\right)=\left({k}\:{n}\right)\left({s}\left({n}\right)\right)=\left({k}\:{n}\right)\left({k}\right)={n} \\ $$$$\Rightarrow{s}''\:{falls}\:{under}\:{the}\:\mathrm{1}{st}\:{case}. \\ $$$$\Rightarrow{s}''=\left({k}\:{n}\right){s}={c}_{\mathrm{1}} …{c}_{{r}} \\ $$$$\Rightarrow{s}=\left({k}\:{n}\right){c}_{\mathrm{1}} {c}_{\mathrm{2}} …{c}_{{r}} \\ $$$${If}\:{k}\notin{c}_{\mathrm{1}} ,…,{c}_{{r}} ,\:{then}\:\left({k}\:{n}\right)\:{is}\:{disjoint}\:{with} \\ $$$${c}_{\mathrm{1}} ,…,{c}_{{r}} \:{and}\:{we}\:{are}\:{done}. \\ $$$${Else},\:{let}\:{k}\in{c}_{{p}} .\:{Since}\:{c}_{\mathrm{1}} ,…,{c}_{{r}} \:{are}\:{disjoint} \\ $$$${they}\:{commute}. \\ $$$$\Rightarrow{s}=\left({n}\:{k}\right){c}_{{p}} {c}_{\mathrm{1}} …{c}_{{r}} \\ $$$${c}_{{p}} \:{is}\:{of}\:{the}\:{form}\:\left(\ast\:…\:\ast\:{k}\:\ast\:…\:\ast\right)=\left({k}\:\ast\:…\:\ast\right) \\ $$$$\Rightarrow{s}=\left({n}\:{k}\right)\left({k}\:\ast\:…\:\ast\right){c}_{\mathrm{1}} …{c}_{{r}} = \\ $$$$=\left({n}\:{k}\:\ast\:…\:\ast\right){c}_{\mathrm{1}} …{c}_{{r}} ={c}_{{p}} '{c}_{\mathrm{1}} …{c}_{{r}} \\ $$$${Obviously},\:{c}_{{p}} ',{c}_{\mathrm{1}} ,…,{c}_{{r}} \:{are}\:{disjoint}. \\ $$$${We}\:{are}\:{done}! \\ $$$$ \\ $$$$\Rightarrow{By}\:{our}\:{induction}\:{hypothesis}, \\ $$$${we}\:{proved}\:{that}\:{every}\:{element}\:{of}\:{a}\:{finite} \\ $$$${symmetric}\:{group}\:{can}\:{be}\:{represented}\:{as} \\ $$$${a}\:{product}\:{of}\:{disjoint}\:{cycles}. \\ $$
Commented by Mastermind last updated on 18/May/23
I do really appreciate
$$\mathrm{I}\:\mathrm{do}\:\mathrm{really}\:\mathrm{appreciate} \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *