What Metrics Can Be Defined on a Symmetric Group Beyond the Discrete Metric?

[Symmetryholic]

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.

 

[quasar987]

Maybe d(\sigma,\rho)=minimum number of permutations required to get from \sigma(1,...,n) to \rho(1,...,n), where \sigma and \rho are element of S_n.

 

[Symmetryholic]

Maybe d(\sigma,\rho)=minimum number of permutations required to get from \sigma(1,...,n) to \rho(1,...,n), where \sigma and \rho are element of S_n.

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

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

Thanks for your reply.

 

[quasar987]

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.

 

[dvs]

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.

 

[Hurkyl]

Finite metric spaces are necessarily discrete. (Points are closed, and every subset is a finite union of points)

 

[Bogaerts]

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 :)

 

[Office_Shredder]

Finite metric spaces are necessarily discrete. (Points are closed, and every subset is a finite union of points)

I think the discrete metric specifically refers to the metric d(x,y) = 1 if x =/= y