Author 
Topic: Det of sum of permutation matrices (Read 6220 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Det of sum of permutation matrices
« on: Sep 3^{rd}, 2009, 4:04pm » 
Quote Modify

Let P,Q be n x n permutation matrices, chosen uniformly at random. What is the probability that det(P+Q) 0? The expected value of det(P+Q) is 0, but what about det(P+Q)? det(P+Q)^{2}?

« Last Edit: Sep 10^{th}, 2009, 5:37pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Det of sum of permutation matrices
« Reply #1 on: Sep 9^{th}, 2009, 9:17pm » 
Quote Modify

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


IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Det of sum of permutation matrices
« Reply #2 on: Sep 13^{th}, 2009, 3:48am » 
Quote Modify

Some initial thoughts: Suppose we have a permutation in S_n that is a single cycle of length k. Then the permutation fixes nk indices and rotates the rest. Let fix() denote the indices that are fixed, and let move() denote the rest. Case I: Now considering the permutation in matrix form, each j fix() 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 , each corresponding to an eigenvector with complex roots of unity at the indices in move(), and zeroes at the indices in fix(). 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  nk 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 kcycle is: (s^k1) (s1)^(nk).

« Last Edit: Sep 13^{th}, 2009, 3:49am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Det of sum of permutation matrices
« Reply #3 on: Sep 13^{th}, 2009, 4:13am » 
Quote Modify

Continuing this train of thought ... hidden:  We can write a permutation as a product of disjoint cycles = _1 _2 _m, and apply the same arguments to each cycle, constructing eigenvectors with disjoint supports for each.  So the characteristic polynomial for a general permutation should be of the form hidden:  _ (s^{L()}  1) where runs 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.  Still haven't done anything random yet. Also P+Q isn't a permutation matrix. Hm ....

« Last Edit: Sep 13^{th}, 2009, 2:49pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Det of sum of permutation matrices
« Reply #4 on: Sep 13^{th}, 2009, 10:05am » 
Quote Modify

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 grouptheoretic 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 onetoone 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 wellknown 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 allodd 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!

« Last Edit: Sep 13^{th}, 2009, 10:07am by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Det of sum of permutation matrices
« Reply #5 on: Sep 13^{th}, 2009, 12:01pm » 
Quote Modify

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) 0? Given P,Q have no entries in common, what is the probability det(P+Q) 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)^{n}), because it starts out simple enough, but it appears to be a polynomial of degree 2^{n1}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 = P(P^{t}+Q^{t})Q, but I started wondering about the converse, that is, exactly when is det(P+Q)=0?

« Last Edit: Sep 13^{th}, 2009, 12:41pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Det of sum of permutation matrices
« Reply #6 on: Sep 13^{th}, 2009, 12:54pm » 
Quote Modify

on Sep 13^{th}, 2009, 10:05am, 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)^{n} 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.


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Det of sum of permutation matrices
« Reply #7 on: Sep 13^{th}, 2009, 3:16pm » 
Quote Modify

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(n1, [(n1)/2]) / 2^(n1) 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 ) .


IP Logged 
Regards, Michael Dagg



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Det of sum of permutation matrices
« Reply #8 on: Sep 13^{th}, 2009, 5:14pm » 
Quote Modify

Yes. I was able to show it using the recurrence: p_{n} = 1/n (p_{n1} + p_{n3} + p_{n5} + ... ), p_{0} = p_{1} = 1, where p_{n} is the probability a permutation is odd. But it was rather ugly: basically I used (1x)^{1/2} = b_{n} x^{n}, where b_{n} = C(2n,n)/4^{n}, and then multiplied both sides by (1x)^{1} = 1 + x + x^{2} + ..., and used the fact that C(1/2, n) = C(3/2, n) / (2n+1) to get b_{n} = 1/(2n) (b_{0}+b_{1}+...+b_{n1}), and from there concluded that p_{n} = b_{m} = C(2m,m)/4^{m}, where m = n/2 . But now I see that we can rewrite the recurrence as np_{n} = p_{n1} + (n2)p_{n2}, and from there the verification is simpler. A bit of Googling turns up a nice proof 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) = a_{n} x^{n}/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) = c_{n} x^{n}/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 be the structure of permutations: (x) = 1/(1x). 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: (x) = S(x) D(x), so we get effortlessly: D(x) = e^{x}/(1x). 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}=0, i.e., we use nonempty pieces): 1 + A(x) + A(x)^{2}/2! + A(x)^{3}/3! + ... = exp(A(x)). For example, the structure C of cycles has c_{n} = (n1)!, so C(x) = log(1x), and a permutation is the same as splitting a set into cycles : (x) = 1/(1x) = exp(log(1x)) = exp(C(x)). Another example: partitioning a set is the same as breaking it up into nonempty sets. Nonempty 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)/(1x) ], and so A(x) = [(1x)/(1+x)]^{1/2} = (1+x) (1x^{2})^{1/2}, so it follows a_{n} = C(2m,m)/4^{m}, the coefficient of x^{m} in (1x)^{1/2}, where m = n/2 .

« Last Edit: Sep 13^{th}, 2009, 5:18pm by Eigenray » 
IP Logged 



