Solution to "The Permutation Puzzles"

All the claims are true.

The complicated transformation which produces the result has a number of unnecessary features.

We don't have to start with permutations, and we don't have to subtract N/2.

The two key factors are a simple fact about the vectors P1 and P2, and the rotation by 45 degrees.

To see what is going on, let us write our steps as follows:

p1 = random permutation of 1 to n
p2 = random permutation of 1 to n

q1 = p1 - n / 2
q2 = p2 - n / 2

NOTE: the L2 norms of q1 and q2 are equal (the vectors have
the same entries, though in different orders).

r1 = c * q1 - s * q2
r2 = s * q1 + c * q2

dot = r1' * r2
= ( c * q1 - s * q2 )' * ( s * q1 + c * q2 )
=   c * s * q1' * q1 + c * c * q1' * q2
- s * s * q2' * q1 - s * c * q2' * q2

NOTE: angle = 45 degrees, so c = s, therefore...

= c * c * ( q1'*q1 + q1'*q2 - q2'*q1 - q2'*q2 )

NOTE: q1'*q2 = q2'*q1, by symmetry of dot products, therefore...

= c * c * ( q1'*q1                   - q2'*q2 )

NOTE: q1'*q1 is the square of the L2 norm of q1, and similarly for q2.

= c * c * ( 0 )

= 0

Thus, the crucial steps are that the translated vectors q1 and q2 have the same norm, which can easily be guaranteed if they have the same entries, though in different order; and that the sine and cosine of the rotation be equal (although this would also work for -45 degrees, for which c = -s, as well as 135 and 225 degrees.)

Last revised on 11 September 2009.