[math-fun] Distance matrix for symmetric group S_n
Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q. Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these: dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1 a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question). b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.) Dan
I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one? Daniel Asimov wrote:
Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q.
Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these:
dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1
a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question).
b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.)
Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck thane@best.com http://www.plambeck.org
At 11:51 PM 7/29/2004, Thane Plambeck wrote:
I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one?
Perhaps Dan means to limit the transpositions to transpositions of adjacent elements; at any rate, that definition results in the same numbers for S_4. In that case there is a simple way of computing the table which is exemplified by the fact that 1356531 = 1*11*111*1111, and is easily established by induction (tacking n+1 onto a permutation of 1...n yields n+1 possibilities with 0,1,... or n more transpositions needed to put n in the desired place). This distance between two permutations is also given by the number of pairs of elements which appear in one order in the first permutation and in the opposite order in the second.
Daniel Asimov wrote:
Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q. Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these: dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1 a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question). b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.)
-- Fred W. Helenius <fredh@ix.netcom.com>
On Fri, 30 Jul 2004, Fred W. Helenius wrote:
At 11:51 PM 7/29/2004, Thane Plambeck wrote:
I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one?
Perhaps Dan means to limit the transpositions to transpositions of adjacent elements; at any rate, that definition results in the same numbers for S_4.
In that case, this is the metric Diaconis calls "Kendall's tau" in the book I mentioned previously. Apparently this metric has a long history. See Diaconis' book for pointers. --Edwin
On Thu, 29 Jul 2004, Daniel Asimov wrote:
Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q.
Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these:
dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1
a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question).
b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.)
As you say the problem boils down to determining the distance from the identity to a permutation p. This is the minimum number of transpositions that it takes to write p. As I recall this minimum is obtained by computing the disjoint cycle decomposition and then decomposing each of the cycles into transpositions in the standard way so that a k-cycle is ap product of k-1 cycles. I think there was an article a few years ago in the Monthly proving this. I just looked this up in a little book I have by Persi Diaconis, Group Representations in Probablity and Statistics. He describes several metrics on S_n. The 5th one on page 112 is the one you describe. He attributes this to Cayley and mentions that Cayley proved that the distance from permutation f to permutation g in S_n is given by n - # cycles in the disjoint cycle decomposition of fg^(-1). The proof is essentially what I mentioned above, but Diaconis is skimpy on the details. Anyhow this should make it easy to find the formulas you seek. --Edwin PS This graph is clearly a "Cayley graph" and perhaps is the source of the term.
participants (4)
-
Daniel Asimov -
Edwin Clark -
Fred W. Helenius -
Thane Plambeck