From: ksbrown@seanet.com (Kevin Brown)
Newsgroups: sci.math
Subject: Re: Patterns in permutations
Date: Fri, 03 Jul 1998 22:50:31 GMT
On Fri, 03 Jul 1998 Nick Battle wrote:
> After once hearing the "ringing of the changes" at Wells Cathedral
> (where the N bells are rung in every N! permutation) I started
> thinking about the various orderings of the permutations of N
> numbers... Bell ringer friends told me of the various orderings
> used to ring the changes, most of them using a simple swap or shift
> of bell positions between adjacent peels so that they are simple to
> play... Consider the N! permutations of the numbers (1, 2,..., N).
> If you take each permutation as the coordinates of a point in N-space,
> then all the N! points are equi-distant from the origin... I have
> difficulty picturing what the N=4 "shape" made by joining the points
> to their nearest neighbours would look like, though trying to project
> it into 3-space I think the points form some sort of regular 4
> dimensional polyhedron (with 24 vertices).
Yes, I think the shape is what's called a "truncated octahedron",
one of the 13 Archimedian solids. It has six square faces and eight
hexagonal faces, making a total of 14 faces. The number of edges
is 36, as required by Euler's formula F + V - E = 2.
For a similar discussion, you could take a look at the notes called
"The Shape of Coincidence" and "Meeting Probabilities" at the web
page http://www.seanet.com/~ksbrown/.
To determine the 3D coordinates of the "4! solid" given in 4D space
by the permutations of [1,2,3,4] it might be easiest to subtract 5/2
from each coordinate so as to center the solid at the origin. Then
for each of the 4D verticies [W,X,Y,Z] we have W+X+Y+Z=0, which
of course is the condition that ensures us we are really dealing
with a 3D solid that happens to be rotated into 4D space. We know
the 4D coordinates of the verticies are the permutations of
V1 = [-3/2, -1/2, +1/2, +3/2]
so each vertex is a distance of d = sqrt(5) from the origin.
We want to find a rotation that brings all these points into the
form [x,y,z,0]. We're free to place the point V1 on the x axis
at [d, 0, 0, 0], and we can place the perpindicular point
V2 = [+1/2, -3/2, +3/2, -1/2]
on the y axis at [0, d, 0, 0]. (Note that V1 and V2 are
orthogonal, as can be seen by computing V1 dot V2 = 0.)
Then, for lack of any better ideas, let's consider the vertex
given by permuting the last two coordinates of V1, i.e.,
V3 = [-3/2, -1/2, +3/2, +1/2]
From the known distances of this vertex to V1, V2, and the origin,
we know the 3D coordinates of V3 satisfy the conditions
x^2 + y^2 + z^2 = 5
(x-d)^2 + y^2 + z^2 = 2
x^2 + (y-d)^2 + z^2 = 6
which implies that
x = 4/d y = 2/d z = +-1
so we can assign it the 3D coordinates [4/d, 2/d, 1, 0]. This is
our third independent vector in our 3D space, so we'll need something
in 4D to complete the conditions. Let's say the 4D vector
V4 = [0, 0, 0, 1]
goes to [x,y,z,w] when it is subjected to our rotation. To ensure
the determinant of our rotation matrix is 1 we need w=1/2, and then
preservation of the distances to V4 leads to the conditions
x^2 + y^2 + z^2 = 1 - (1/2)^2
(x-d)^2 + y^2 + z^2 = 3 - (1/2)^2
x^2 + (y-d)^2 + z^2 = 7 - (1/2)^2
which implies x = 3/(2d), y = -1/(2d), and z = +-1/2. Combining all
these conditions we can solve for the rotation matrix R using the
equation
_ _ _ _
| d 0 4/d 3/(2d) || -3/2 1/2 -3/2 0 |-1
R = | 0 d 2/d -1/(2d) || -1/2 -3/2 -1/2 0 |
| 0 0 1 1/2 || 1/2 3/2 3/2 0 |
|_ 0 0 0 1/2 _||_ 3/2 -1/2 1/2 1 _|
_ _
| -3/d -1/d 1/d 3/d |
= (1/2)| 1/d -3/d 3/d -1/d |
| 1 3 3 1 |
|_ 1 1 1 1 _|
Applying this transformation to the original 4D "permutation points"
(and noting that we need consider only 12 points because they come
in opposite pairs), we have the 3D coordinates
2W 2X 2Y 2Z x y z
--- --- --- --- ----- ----- -----
-3 -1 +1 +3 d 0 0
-3 -1 +3 +1 4/d 2/d 1
-3 +3 -1 +1 2/d -4/d 1
-3 +3 +1 -1 1/d -2/d 2
-3 +1 -1 +3 4/d -3/d 0
-3 +1 +3 -1 2/d 1/d 2
-1 -3 +1 +3 4/d 2/d -1
-1 -3 +3 +1 3/d 4/d 0
-1 +1 -3 +3 2/d -4/d -1
-1 +1 +3 -3 -1/d 2/d 2
-1 +3 +1 -3 -2/d -1/d 2
-1 +3 -3 +1 0 -d 0
The other 12 points are just the negatives of these (x,y,z) vectors.
As mentioned above, these 24 points constitute the verticies of a
truncated octahedron. A little Java applet that allows you to
examine this solid can be found at the web version of this note
at http://www.seanet.com/~ksbrown/kmath482.htm.
_________________________________________________________________
| MathPages /*\ http://www.seanet.com/~ksbrown/ |
| / \ |
|__________/"Angels alone, that soar above, enjoy such liberty." _|