wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Det of sum of permutation matrices
        
(Message started by: Eigenray on Sep 3^rd, 2009, 4:04pm)

Title: Det of sum of permutation matrices
Post by Eigenray on Sep 3^rd, 2009, 4:04pm

Let P,Q be n x n permutation matrices, chosen uniformly at random.

What is the probability that det(P+Q) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0?

The expected value of det(P+Q) is 0, but what about |det(P+Q)|? det(P+Q)²?

Title: Re: Det of sum of permutation matrices
Post by Eigenray on Sep 9^th, 2009, 9:17pm

Maybe a good place to start: [hide]what is the characteristic polynomial of a permutation matrix[/hide]?

Title: Re: Det of sum of permutation matrices
Post by william wu on Sep 13^th, 2009, 3:48am

Some initial thoughts:

Suppose we have a permutation http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif in S_n that is a single cycle of length k. Then the permutation fixes n-k indices and rotates the rest. Let fix(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) denote the indices that are fixed, and let move(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) denote the rest.

Case I:
Now considering the permutation http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifin matrix form, each j http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.giffix(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) corresponds to an eigenvector with eigenvalue 1, where the eigenvector is a canonical basis vector containing all zeros except for a one in the jth slot.

Case II:
Each of the kth roots of unity are also eigenvalues for http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif, each corresponding to an eigenvector with complex roots of unity at the indices in move(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif), and zeroes at the indices in fix(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif).

Counting:
The eigenvectors we found in Case II are linearly independent since they each correspond to different (complex) eigenvalues.
The eigenvectors we found in Case I are clearly linearly independent since they have disjoint supports.
And any eigenvector from Case I is linearly independent of an eigenvector from Case II since they have disjoint supports as well.
Thus we have found a full set of n linearly independent eigenvectors. So the algebraic multiplicity for any eigenvalue must match its geometric multiplicity (which is generally just a lower bound).

Thus we have found all the eigenvalues:
- the kth roots of unity, and
- n-k extra copies of 1 (I say extra since 1 is also a kth root of unity)

Since the characteristic polynomial is the monic polynomial whose roots are the eigenvalues, it follows that the characteristic polynomial for a single k-cycle is: [hide]
(s^k-1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif(s-1)^(n-k).
[/hide]

Title: Re: Det of sum of permutation matrices
Post by william wu on Sep 13^th, 2009, 4:13am

Continuing this train of thought ...
[hideb]
We can write a permutation http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifas a product of disjoint cycles http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdots.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif_m, and apply the same arguments to each cycle, constructing eigenvectors with disjoint supports for each.
[/hideb]

So the characteristic polynomial for a general permutation should be of the form
[hideb]

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif_http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif (s^{L(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gif)} - 1)

where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sigma.gifruns through each of the disjoint cycles -- including cycles of length 1 which correspond to the fixed points -- and L(k) is the length of that cycle.
[/hideb]

Still haven't done anything random yet. Also P+Q isn't a permutation matrix. Hm .... ???

Title: Re: Det of sum of permutation matrices
Post by Michael Dagg on Sep 13^th, 2009, 10:05am

Here's another idea:

det(P+Q) = +- det( R - (-1)I ) where R = Q^(-1) P and the
+- sign is det(Q). I write it with the "(-1)I" to stress that
this det is the value of the characteristic polynomial of R
at -1 .

We can reorder the n basis elements of R^n (the ones that R
permutes) according to the cycle decomposition of R; this
makes it clear that R is a block sum of cyclic permutations,
and so the characteristic polynomial of R is a product
\prod (T^{n_i} - 1), where the n_i are the sizes of
the cycles. So det(R - (-1)I) is 0 unless all n_i
are odd, in which case it's (-2)^N, where N is the
number of cycles.

Thus we have a group-theoretic understanding of det(P+Q):
it's 0 if Q^{-1}P has an orbit of even length,
and otherwise is det(Q) * (-2)^N where N is the
number of orbits of Q^{-1}P.

Now, there is a one-to-one correspondence between the
pairs (P,Q) and (Q,R) (namely, P = Q R ) so in
the probability computations above, we can just select
R uniformly at random from S_n and assume det(Q)=-1
exactly half of the time. (That makes it clear that the
expected value of det(P+Q) will be zero!)

> What is the probability that det(P+Q) =/= 0 ?

It is the probability that R have all its cycles of
odd length. That must be some well-known partition
problem, but I don't know an elegant expression for it.
For example, when n=6, the cycles would have to be of
lengths 5+1, 3+3, 3+1+1+1, or 1^6. I get that there are
144 of the first type, 40 of the second, 40 of the next,
and 1 of the last: 225 of the 720 permutations qualify,
so the answer to this question when n=6 is 225/720.

> The expected value of det(P+Q) is 0, but what is the expected
> value of |det(P+Q)| ? ( det(P+Q) )^2 ?

This time instead of just counting the all-odd permutations,
we need to add 2^N resp 4^N for each. Taking again the
case n=6 I get the values 144*4 + 40*4 + 40*16 + 1*64 = 1440
and 144*4^2 + 40*4^2 + 40*16^2 + 1*64^2 = 17280 respectively,
making expected values of 2 and 24 respectively. I didn't
expect whole numbers. There must be a trick!

Title: Re: Det of sum of permutation matrices
Post by Eigenray on Sep 13^th, 2009, 12:01pm

All three problems have elegant answers (I was rather surprised myself), but I don't know elegant derivations for any of them. I solved each by finding the pattern and proving it satisfies the right recurrence. The first problem might be the hardest, but at the same time I suspect there must be a simple proof because it is a pretty basic question: how many elements of S_n have odd order?

We can also find recurrences for questions like:

What is the probability det(P+iQ) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0?

Given P,Q have no entries in common, what is the probability det(P+Q) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0?

But I don't think the answers to these have simple forms.

I was hoping for a simple form for E(|det(P+Q)|ⁿ), because it starts out simple enough, but it appears to be a polynomial of degree 2^n-1-1.

Anyway, as to the source of this problem, I was skimming through a linear algebra book (Gilbert Strang) and it had the problem: if P is even and Q is odd, then det(P+Q)=0. The suggested proof was to just use P+Q = [hide]P(P^t+Q^t)Q[/hide], but I started wondering about the converse, that is, exactly when is det(P+Q)=0?

Title: Re: Det of sum of permutation matrices
Post by Eigenray on Sep 13^th, 2009, 12:54pm

on 09/13/09 at 10:05:03, Michael Dagg wrote:

So det(R - (-1)I) is 0 unless all n_i
are odd, in which case it's (-2)^N, where N is the
number of cycles.

Actually you need to multiply by (-1)ⁿ to use the monic characteristic polynomial. And if all cycles are odd, then n = N mod 2, so the sign goes away: det(I + P) is either 0 or a power of 2.

Title: Re: Det of sum of permutation matrices
Post by Michael Dagg on Sep 13^th, 2009, 3:16pm

You're right.

> how many elements of S_n have odd order?

Yeah, it's a basic question, but it doesn't have an
answer that's described more easily than the question.

I did the computations for n up to 8, then searched the
OEIS, so I can give you as much information as is known
about those numbers:
http://research.att.com/~njas/sequences/A000246

In particular, one of their formulas presents the probability
that you asked about as
C(n-1, [(n-1)/2]) / 2^(n-1)
that is, it's the central binomial coefficient, divided by
the corresponding power of 2.

By Stirling's approximation, that probability then comes
out to something like 1/sqrt( pi/2 * n ) .

Title: Re: Det of sum of permutation matrices
Post by Eigenray on Sep 13^th, 2009, 5:14pm

Yes. I was able to show it using the recurrence:
p_n = 1/n (p_n-1 + p_n-3 + p_n-5 + ... ),
p₀ = p₁ = 1,
where p_n is the probability a permutation is odd.

But it was rather ugly: basically I used
(1-x)^-1/2 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif b_n xⁿ,
where b_n = C(2n,n)/4ⁿ, and then multiplied both sides by
(1-x)^-1 = 1 + x + x² + ...,
and used the fact that C(-1/2, n) = C(-3/2, n) / (2n+1) to get
b_n = 1/(2n) (b₀+b₁+...+b_n-1),
and from there concluded that p_n = b_m = C(2m,m)/4^m, where m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif n/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif.

But now I see that we can rewrite the recurrence as
np_n = p_n-1 + (n-2)p_n-2,
and from there the verification is simpler.

A bit of Googling turns up a nice [link=http://groups.google.com/group/sci.math/msg/3a8a540dd592b546?hl=en]proof[/link] using Joyal's theory of species.

Basically, for a given structure A, let a_n be the number of ways to put structure A on a set of n (labeled) points, and let A(x) be the exponential generating function A(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif a_n xⁿ/n!. Then there are combinatorial interpretations of, for example, the product and exponentiation (and more generally, composition) of e.g.f.s.

In the product C(x) = A(x)B(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif c_n xⁿ/n!, c_n counts the number of ways to split a set into two pieces, put structure A on the first piece, and B on the second. For example, let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cpi.gif be the structure of permutations: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cpi.gif(x) = 1/(1-x). Let S be the structure of set: S(x) = e^x. Let D be the structure of derangements. Any permutation can be considered as a set of fixed points together with a derangement on the rest: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cpi.gif(x) = S(x) D(x), so we get effortlessly: D(x) = e^-x/(1-x).

If we want to split a set into a set of pieces, and put structure A on each piece, the result is (assuming a₀=0, i.e., we use non-empty pieces):
1 + A(x) + A(x)²/2! + A(x)³/3! + ... = exp(A(x)).
For example, the structure C of cycles has c_n = (n-1)!, so C(x) = -log(1-x), and a permutation is the same as splitting a set into cycles : http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cpi.gif(x) = 1/(1-x) = exp(-log(1-x)) = exp(C(x)). Another example: partitioning a set is the same as breaking it up into non-empty sets. Non-empty sets has egf e^x-1, so partitions has egf exp(e^x-1).

To apply this to the current problem: let a_n be the number of permutations of odd order. Then A(x) = exp(C_o(x)), where C_o is the structure of odd length cycles. Clearly C_o is the 'odd part' of C:
C_o(x) = 1/2 [ C(x) - C(-x) ] = 1/2 log[ (1+x)/(1-x) ],
and so
A(x) = [(1-x)/(1+x)]^1/2 = (1+x) (1-x²)^-1/2,
so it follows a_n = C(2m,m)/4^m, the coefficient of x^m in (1-x)^-1/2, where m = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif n/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif.