wu :: forums
« wu :: forums - Det of sum of permutation matrices »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 3:01pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: towr, william wu, SMQ, Grimbal, Icarus, Eigenray)
   Det of sum of permutation matrices
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Det of sum of permutation matrices  (Read 6237 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Det of sum of permutation matrices  
« on: Sep 3rd, 2009, 4:04pm »
Quote Quote Modify 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 10th, 2009, 5:37pm by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Det of sum of permutation matrices  
« Reply #1 on: Sep 9th, 2009, 9:17pm »
Quote Quote Modify Modify

Maybe a good place to start: what is the characteristic polynomial of a permutation matrix?
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Det of sum of permutation matrices  
« Reply #2 on: Sep 13th, 2009, 3:48am »
Quote Quote Modify Modify

Some initial thoughts:
 
 
Suppose we have a permutation in S_n that is a single cycle of length k. Then the permutation fixes n-k 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
- 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:  
(s^k-1) (s-1)^(n-k).
« Last Edit: Sep 13th, 2009, 3:49am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Det of sum of permutation matrices  
« Reply #3 on: Sep 13th, 2009, 4:13am »
Quote Quote Modify 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:


_ (sL() - 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 ....  Huh
« Last Edit: Sep 13th, 2009, 2:49pm by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Michael Dagg
Senior Riddler
****






   


Gender: male
Posts: 500
Re: Det of sum of permutation matrices  
« Reply #4 on: Sep 13th, 2009, 10:05am »
Quote Quote Modify 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 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!
« Last Edit: Sep 13th, 2009, 10:07am by Michael Dagg » IP Logged

Regards,
Michael Dagg
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Det of sum of permutation matrices  
« Reply #5 on: Sep 13th, 2009, 12:01pm »
Quote Quote Modify 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 Sn 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 2n-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 = P(Pt+Qt)Q, but I started wondering about the converse, that is, exactly when is det(P+Q)=0?
« Last Edit: Sep 13th, 2009, 12:41pm by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Det of sum of permutation matrices  
« Reply #6 on: Sep 13th, 2009, 12:54pm »
Quote Quote Modify Modify

on Sep 13th, 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: male
Posts: 500
Re: Det of sum of permutation matrices  
« Reply #7 on: Sep 13th, 2009, 3:16pm »
Quote Quote Modify 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(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 ) .
IP Logged

Regards,
Michael Dagg
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Det of sum of permutation matrices  
« Reply #8 on: Sep 13th, 2009, 5:14pm »
Quote Quote Modify Modify

Yes.  I was able to show it using the recurrence:
pn = 1/n (pn-1 + pn-3 + pn-5 + ... ),
p0 = p1 = 1,
where pn is the probability a permutation is odd.
 
But it was rather ugly: basically I used
(1-x)-1/2 = bn xn,
where bn = C(2n,n)/4n, and then multiplied both sides by
(1-x)-1 = 1 + x + x2 + ...,
and used the fact that C(-1/2, n) = C(-3/2, n) / (2n+1) to get
bn = 1/(2n) (b0+b1+...+bn-1),
and from there concluded that pn = bm = C(2m,m)/4m, where m = n/2 .
 
 
But now I see that we can rewrite the recurrence as
npn = pn-1 + (n-2)pn-2,
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 an 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) = an xn/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) = cn xn/n!, cn 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/(1-x).  Let S be the structure of set: S(x) = ex.  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/(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 a0=0, i.e., we use non-empty pieces):  
1 + A(x) + A(x)2/2! + A(x)3/3! + ... = exp(A(x)).
For example, the structure C of cycles has cn = (n-1)!, so C(x) = -log(1-x), and a permutation is the same as splitting a set into cycles : (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 ex-1, so partitions has egf exp(ex-1).
 
 
To apply this to the current problem: let an be the number of permutations of odd order.  Then A(x) = exp(Co(x)), where Co is the structure of odd length cycles.  Clearly Co is the 'odd part' of C:
Co(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-x2)-1/2,
so it follows an = C(2m,m)/4m, the coefficient of xm in (1-x)-1/2, where m = n/2 .
« Last Edit: Sep 13th, 2009, 5:18pm by Eigenray » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board