wu :: forums « wu :: forums - Det of sum of permutation matrices » Welcome, Guest. Please Login or Register. Jun 8th, 2023, 11:08am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, Grimbal, Icarus, william wu, SMQ, Eigenray)    Det of sum of permutation matrices « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 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 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

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

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
http://research.att.com/~njas/sequences/A000246

In particular, one of their formulas presents the probability
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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »