Wikipedia:Reference desk/Archives/Mathematics/2018 April 24
| Mathematics desk | ||
|---|---|---|
| < April 23 | << Mar | April | May >> | April 25 > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
April 24
[edit]A distance in the symmetric group?
[edit]Any permutation is a product of transpositions. That decomposition is not unique. Define the number of transpositions of a specific decomposition as the length of that decomposition. Define the minimum of all the lengths corresponding to all the various decompositions of that permutation as the length of that permutation. Take A and B to be two permutations of order n. Take C the permutation that turns A into B. Let L(C) be the length of C (as defined). Call that length the "distance" between A and B. Would that "distance" be a (metric) distance on the symmetric group of order n? I assume not (just because otherwise I suppose it would be one of the notable examples) but I haven't tried to find a counterexample. If there is a problem it's gotta be the inequality d(A,C) ≤ d(A,B) + d(B,C). Does anyone have a counterexample? Thanks. Basemetal 21:34, 24 April 2018 (UTC)
PS: Same question when you change "transposition" everywhere to "adjacent transposition". Thanks. Basemetal 21:46, 24 April 2018 (UTC)
- That would work okay - after all one can just put the transpositions of one after the other to get the group product. Dmcq (talk) 21:45, 24 April 2018 (UTC)
- I'm not sure I understand. Are you saying that it is a distance? If yes, could you slightly expand your proof? Basemetal 21:50, 24 April 2018 (UTC)
- Yes, it's certainly a metric: it's the graph distance on the Cayley graph of S_n generated by all transpositions. The same is true with adjacent transpositions, for the same reason. --JBL (talk) 21:54, 24 April 2018 (UTC)
- Thanks. Are there other (not trivial) metrics on the symmetric group worth noting? Basemetal 22:21, 24 April 2018 (UTC)
- Um. Possibly? It's hard to answer without knowing the context in which you decide whether things are worthwhile. Any generating set for S_n closed under inverses gives a metric like this. The two you mentioned are very important in certain parts of combinatorics (I have written papers in which both feature prominently). I do not know if there are other examples of generating sets that arise naturally and so make the associated metrics useful. There's a thing that Pak and Redlich called "abc-permutations" and there's obviously some associated metric there, but they don't study it from that point of view. --JBL (talk) 11:24, 25 April 2018 (UTC)
- Thanks again. Could you check another question of mine having to do with the symmetric group (A quotient of the symmetric group)? Thanks. Basemetal 17:03, 25 April 2018 (UTC)
- One can also generalize in another direction, to other groups. The symmetric group is a Weyl group which are Coxeter groups, generated by reflections. The length functions defined as above are useful in Lie theory etc. and you can get similar metrics. Came across Weyl distance function here too, tangential, but interesting.John Z (talk) 03:02, 1 May 2018 (UTC)
- Thanks. Basemetal 06:26, 1 May 2018 (UTC)
- One can also generalize in another direction, to other groups. The symmetric group is a Weyl group which are Coxeter groups, generated by reflections. The length functions defined as above are useful in Lie theory etc. and you can get similar metrics. Came across Weyl distance function here too, tangential, but interesting.John Z (talk) 03:02, 1 May 2018 (UTC)
- Thanks again. Could you check another question of mine having to do with the symmetric group (A quotient of the symmetric group)? Thanks. Basemetal 17:03, 25 April 2018 (UTC)
- Um. Possibly? It's hard to answer without knowing the context in which you decide whether things are worthwhile. Any generating set for S_n closed under inverses gives a metric like this. The two you mentioned are very important in certain parts of combinatorics (I have written papers in which both feature prominently). I do not know if there are other examples of generating sets that arise naturally and so make the associated metrics useful. There's a thing that Pak and Redlich called "abc-permutations" and there's obviously some associated metric there, but they don't study it from that point of view. --JBL (talk) 11:24, 25 April 2018 (UTC)
- Thanks. Are there other (not trivial) metrics on the symmetric group worth noting? Basemetal 22:21, 24 April 2018 (UTC)
- Yes, it's certainly a metric: it's the graph distance on the Cayley graph of S_n generated by all transpositions. The same is true with adjacent transpositions, for the same reason. --JBL (talk) 21:54, 24 April 2018 (UTC)