Results 1 to 2 of 2

Math Help - Show any permutation of a finite set may be expressed as a product of transpositions

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    36

    Show any permutation of a finite set may be expressed as a product of transpositions

    Prove any permutation of a finite set may be expressed as a product of transpositions by using induction on |Supp(p)|.
    Here Supp(p) means the support of p, the elements which are moved by the map p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by kevinlightman View Post
    Prove any permutation of a finite set may be expressed as a product of transpositions by using induction on |Supp(p)|.
    Here Supp(p) means the support of p, the elements which are moved by the map p.
    Base case |Supp(p)|=2 is rather obvious. Suppose the result holds for |\text{Supp}(p)|\leqslant n, and let p be a permutation with |\text{Supp}(p)|=n+1. Suppose that p moves i to j: p (i)=j\ne i. Then the product of the transposition (i j) with p fixes i and therefore moves at most n elements. So apply the inductive hypothesis to it ... .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: February 19th 2011, 04:29 PM
  2. [SOLVED] Expressing as a product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 19th 2010, 01:33 AM
  3. Show that Y is a finite set
    Posted in the Differential Geometry Forum
    Replies: 12
    Last Post: March 31st 2010, 09:06 PM
  4. permutation and semidirect product
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 7th 2009, 11:09 AM
  5. product of transpositions
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2007, 07:03 AM

Search Tags


/mathhelpforum @mathhelpforum