Symmetric group to metric space

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 [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.

Symmetryholic

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.

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

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