Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Symmetric group to metric space

  1. Jan 12, 2009 #1
    If I convert a symmetric group of degree n into a metric space, what metrics can be defined except a discrete metric?

    If a metric can be defined, I am wondering if the metric can describe some characteristics of a symmetric group.
     
  2. jcsd
  3. Jan 15, 2009 #2

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Maybe [itex]d(\sigma,\rho)[/itex]=minimum number of permutations required to get from [itex]\sigma(1,...,n)[/itex] to [itex]\rho(1,...,n)[/itex], where [itex]\sigma[/itex] and [itex]\rho[/itex] are element of S_n.
     
  4. Jan 15, 2009 #3

    If [itex]\sigma, \rho \in S_{n}[/itex], then [itex]\sigma x = \rho[/itex] for [itex]x \in S_{n}[/itex]. I mean, is it just a single time of permuation between elements of [itex]S_{n}[/itex]?

    If you happen to have a reference or web link of the above argument, plz post it. I will appreciate on it.

    Thanks for your reply.
     
  5. Jan 16, 2009 #4

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Excuse me, I meant "transposition" instead of "permutation".

    I have no reference to the above argument. It was just an idea for you to explore. I thought it had the ring of truth.
     
  6. Jan 19, 2009 #5

    dvs

    User Avatar

    Perhaps you can try embedding S_n into the general linear group of some complex vector space. This way you can pull back the Euclidean metric onto S_n. There are a few ways you can get such embeddings; some keywords: (complex) faithful representations of S_n.
     
  7. Jan 19, 2009 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Finite metric spaces are necessarily discrete. (Points are closed, and every subset is a finite union of points)
     
  8. Feb 25, 2009 #7
    You can define a Hamming distance on permutations:
    d( a, b)= n-fix(a-1b)

    The distance defined by quasar987 is the Cayley distance in Sym(n):
    d( a, b)= n-number of cycles of a-1b

    A paper of Deza ("Metrics on Permutations, a Survey",1998) says that if you have a bi-invariant metric, that is, for all a,b,c: d(a,b)=d(ac,bc)=d(ca,cb), then there is a weight function defined by w(a)=d(Id,a). The weight function have the same value for all permutations in the same conjugacy class. So the weight w can be expressed as a linear comb. of the irreducible characters of Sym(n).
    Note that Hamming and Cayley distances are both bi-invariant.

    There are also not bi-invariant metrics such as the Lee distance. Ask if you want to know more about it, I'm finishing a PhD thesis on this subject :)
     
  9. Feb 25, 2009 #8

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think the discrete metric specifically refers to the metric d(x,y) = 1 if x =/= y
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Symmetric group to metric space
  1. Metric space (Replies: 2)

Loading...