Author |
Topic: Det of sum of permutation matrices (Read 6272 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Det of sum of permutation matrices
« on: Sep 3rd, 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 10th, 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 9th, 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 13th, 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 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
Gender:
Posts: 1291
|
|
Re: Det of sum of permutation matrices
« Reply #3 on: Sep 13th, 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: |
 _ (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 .... 
|
| « 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:
Posts: 500
|
|
Re: Det of sum of permutation matrices
« Reply #4 on: Sep 13th, 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 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:
Posts: 1948
|
|
Re: Det of sum of permutation matrices
« Reply #5 on: Sep 13th, 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 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:
Posts: 1948
|
|
Re: Det of sum of permutation matrices
« Reply #6 on: Sep 13th, 2009, 12:54pm » |
Quote 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:
Posts: 500
|
|
Re: Det of sum of permutation matrices
« Reply #7 on: Sep 13th, 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(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:
Posts: 1948
|
|
Re: Det of sum of permutation matrices
« Reply #8 on: Sep 13th, 2009, 5:14pm » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print