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!


Question and Answers Forum

All Questions Topic List
Others Questions
Previous in All Question Next in All Question
Previous in Others Next in Others
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 \to S where S is a finite set can be$ $written as a product of disjoint$ $cycle$ $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.$
	$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) i s o d d$ $\Rightarrow s g n (θ) = s g n (\underset{k = 1}{\prod^{7}} (k k + 1)) =$ $= \underset{k = 1}{\prod^{7}} s g n ((k k + 1)) = {(- 1)}^{7} = - 1 = s g n (θ)$ $\Rightarrow θ i s o d d$ $2) W e w i l l p r o v e t h a g f o r e v e r y s \in S_{n}, s c a n$ $b e r e p r e s e n t e d a s a p r o d u c t o f c y c l e s .$ $P r o o f b y i n d u c t i o n :$ $n = 1 : s = i d = (1)$ $n = 2 : s = {\begin{cases} i d = (1) (2) \\ (\begin{array}{c} 1 2 \\ 2 1 \end{array}) = (1 2) \end{cases}$ $n = m : l e t \forall s^{'} \in S_{m} c a n b e r e p r . a s a p r o d u c t$ $o f d i s j o i n t c y c l e s$ $n = m + 1 :$ $L e t s \in S_{n}$ $\underset{―}{1 s t c a s e} : s (n) = n \Rightarrow s = (\begin{matrix} 1 2 3 . . . n - 1 n \\ * * * . . . * n \end{matrix})$ $\Rightarrow s \equiv s^{'} = (\begin{matrix} 1 2 3 . . . n - 1 \\ * * * . . . * \end{matrix}) \in S_{m}$ $B y i n d . h y p . s^{'} = c_{1} . . . c_{r}, w h e r e c_{i} i s a c y c l e .$ $\Rightarrow s = c_{1} . . . c_{r} .$ $W e n o t e t h a t n \notin c_{1}, . . ., c_{r}$ $\underset{―}{2 n d c a s e} : s (n) = k \neq n, l e t s^{″} = (k n) s$ $\Rightarrow ((k n) s) (n) = (k n) (s (n)) = (k n) (k) = n$ $\Rightarrow s^{″} f a l l s u n d e r t h e 1 s t c a s e .$ $\Rightarrow s^{″} = (k n) s = c_{1} . . . c_{r}$ $\Rightarrow s = (k n) c_{1} c_{2} . . . c_{r}$ $I f k \notin c_{1}, . . ., c_{r}, t h e n (k n) i s d i s j o i n t w i t h$ $c_{1}, . . ., c_{r} a n d w e a r e d o n e .$ $E l s e, l e t k \in c_{p} . S i n c e c_{1}, . . ., c_{r} a r e d i s j o i n t$ $t h e y c o m m u t e .$ $\Rightarrow s = (n k) c_{p} c_{1} . . . c_{r}$ $c_{p} i s o f t h e f o r m (* . . . * k * . . . ) = (k . . . )$ $\Rightarrow s = (n k) (k . . . ) c_{1} . . . c_{r} =$ $= (n k . . . *) c_{1} . . . c_{r} = c_{p}^{'} c_{1} . . . c_{r}$ $O b v i o u s l y, c_{p}^{'}, c_{1}, . . ., c_{r} a r e d i s j o i n t .$ $W e a r e d o n e!$ $\Rightarrow B y o u r i n d u c t i o n h y p o t h e s i s,$ $w e p r o v e d t h a t e v e r y e l e m e n t o f a f i n i t e$ $s y m m e t r i c g r o u p c a n b e r e p r e s e n t e d a s$ $a p r o d u c t o f d i s j o i n t c y c l e s .$
	Commented by Mastermind last updated on 18/May/23

	$I do really appreciate$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum