Question #156043

 Prove that the product of an even permutation and an odd permutation is odd.


1
Expert's answer
2021-01-19T02:06:33-0500

Solution:Now, Our first claim is, every permutation can be expressed as the product of one and only one of the following:                    an odd number of transpositions   odd permutation                    an even number of transpositions  even permutationSolution: Now, ~Our~ first ~claim~ is, ~every ~permutation~ can ~be ~expressed ~as ~\\the ~product ~of ~one ~and~ only~ one~ of~ the ~following: \\~~~~~~~~~~~~~~~~~~~~an~ odd ~number ~of ~transpositions    ⟺ odd~ permutation \\~~~~~~~~~~~~~~~~~~~~an~ even ~number ~of ~transpositions   ⟺ even~ permutation

There are many ways to write a permutation as the product of transpositions, and they can vary in length, but those products will have either an odd or an even number of factors, never both.We know that the number of transpositions in a product corresponding to a permutation that is a cycle of length n can be expressed as the product of(n1) transpositions.There ~are ~many ~ways~ to ~write~ a~ permutation~ as ~the ~product~ of~ transpositions, \\~and ~they~ can ~vary~ in ~length,~ but~ those~ products~ will ~have~ either ~an~ odd~ or ~an \\~even~ number~ of~ factors, ~never~ both. \\We ~know ~that~ the ~number ~of~ transpositions~ in~ a~ product ~corresponding ~to~ a \\~permutation ~that~ is ~a ~cycle ~of ~length ~n ~can ~be ~expressed ~as ~the~ product ~of\\ (n−1)~ transpositions.

One ~can~ always ~resort ~to~ following ~the~ pattern:~ Without ~loss~ of ~generality~ \\suppose ~n ~is ~odd ~then~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~(a_1,a_2,...,a_n)=(a_1,a_n)(a_1,a_{n-1})...(a_1,a_2)\\which~is~even~because ~there ~are~ (n-1)~ transpositions.~\\ [we~ can~ also ~write ~ (a_1,a_2,...,a_n)=(a_1,a_2)(a_2,a_3)...(a_{n-1},a_n)]

Again, an even number of transpositions  the permutation is even. A similar approach can be drawn for even number n.Again, ~an ~even ~number~ of~ transpositions   ⟺ the~ permutation~ is~ even.~\\ A~ similar~approach~ can ~be~ drawn~ for~ even~ number~ n.

So a cycle with a length that is even (has an even number of elements) is ODD,and a cycle with a length that is odd (has an odd number of elements) is EVEN.So~ a ~cycle ~with~ a ~length~ that~ is~ even~ (has~ an ~even~ number~ of~ elements) ~is~ ODD, \\and~ a~ cycle~ with~ a~ length~ that ~is ~odd~ (has~ an ~odd~ number ~of ~elements)~ is~ EVEN. If you have a permutation that is the product of disjoint cycles: say three cycles, corresponding to lengths n1,n2,n3, then the number of transpositions representing this permutation can be computed by the parity of (n11)+(n21)+(n31) or simply the parity (oddness/evenness) of n1+n2+n31.If ~you~ have~ a~ permutation ~that~ is~ the ~product~ of~ disjoint ~cycles: ~say~ three~ cycles, ~\\corresponding ~to ~lengths~n_1,n_2,n_3,~then~ the~ number~ of ~transpositions~ \\representing~ this~ permutation ~can ~be~ computed ~by~ the ~parity~ of ~\\(n_1-1)+(n_2-1)+(n_3-1)~or ~simply~ the ~parity~(oddness/evenness) ~of~\\n_1+n_2+n_3-1. Now Let E be the set of even permutations in G (which is presumably a group of permutations).Our second aim is to show that E forms a subgroup of G.Now ~Let ~E ~be~ the~ set ~of ~even~ permutations~ in~ G~ (which~ is~ presumably ~a ~group ~of ~\\permutations). Our ~second~ aim~ is ~to ~show~ that ~E ~forms~ a ~subgroup~ of ~G. Let p and q be elements of E. Now we need to check if pq1 is also an element of E.We know that a permutation is called an even permutation if it can be written as a product of an even number of transpositions.Let ~p~ and~ q~ be ~elements~ of~ E.~ Now~ we~ need ~to~ check ~if ~pq^{-1}~ is~ also~ an~ element ~\\of ~E. We~ know ~that ~a~ permutation ~is ~called~ an ~even ~permutation~ if ~it ~can ~be~\\ written ~as ~a~ product~ of~ an~ even~ number ~of~ transpositions.


So,let p=p1p2...p2k and q=q1q2...q2j be a representation of p and q as a product of transpositions.We have that q1=q2jq2j1...q2q1 since transpositions are self inverses.So, let ~p=p_1p_2...p_{2k}~and~q=q_1q_2...q_{2j} ~ be ~a~ representation ~of~ p~ and ~q ~as ~a ~\\product ~of~ transpositions. \\We ~have~ that~q^{-1}=q_{2j}q_{2j-1}...q_2q_1~since ~transpositions~ are ~self ~inverses.


Thus,pq1=p1p2p2kq2jq2q1 is indeed a product of an even number of transpositions.Furthermore, pq1 is an element of G since p and q (and thus q1) are elements of G and G is closed under products and inverses.Thus, pq^{−1}=p_1p_2⋯p_{2k}q_{2j}⋯q_2q_1 ~is ~indeed~ a ~product ~of ~an ~even ~number ~of ~\\transpositions. Furthermore,~ pq^{−1}~is~ an ~element~ of ~G~ since~ p~ and ~q~ (and ~thus~ q^{−1})\\~ are ~elements~ of~ G~ and~ G ~is ~closed ~under~ products ~and ~inverses.


Thus,pq1E,implying that the identity is an element of E (by taking p=q),that it is closed under inverse (by taking p=id), and that it is closed under products (by taking q1 instead ofq) and E is a subgroup of G.Thus, pq^{-1} \in E, implying~ that ~the~ identity ~is~ an~ element ~of~ E~ (by~ taking ~p=q), \\that~ it~ is~ closed~ under~ inverse ~(by~ taking~ p=id),~ and ~that ~it ~is~ closed~ under~\\ products ~(by ~taking ~q^{−1}~instead ~of q) ~and~ E~ is ~a~ subgroup ~of ~G.


Now suppose, if possible, there exist an even permutation p and an odd permutationq such that there product r=pq is even that is rE. Then q=p1rE since p,rE and E is a subgroup of G.Therefore,q is a even permutation but by assumption q is an odd permutation, contradiction.Therefore, product of an even permutation and an odd permutation is an odd permutation.Now~ suppose, ~if ~possible, ~there ~exist ~an ~even ~permutation ~p ~and~ an~ odd ~\\permutation q~ such ~that~ there~ product~r=pq~is~even~that~is~r \in E.~Then~\\q=p^{-1}r \in E~since ~p,r \in E~and ~E ~is~a~subgroup~of~G.Therefore, q ~is ~a ~even~ \\permutation~ but ~by~ assumption ~q ~is ~an~ odd~ permutation, ~contradiction.\\Therefore, ~product ~of~ an~ even~ permutation~ and~ an~ odd~ permutation~ is~ an~ odd ~\\permutation.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS