From: lrudolph@panix.com (Lee Rudolph) Subject: Re: Commutitive Matrices Date: 19 Feb 1999 07:53:50 -0500 Newsgroups: sci.math Keywords: What is the probability that two matrices will commute Bryce Bockman writes: >Does any one know what the probability that two matrices will commute >is. That is that: > >AB = BA In the 2n^2-dimensional vectorspace V of pairs (A,B) of n-by-n matrices over a field F, the subset X of pairs (A,B) with AB-BA = 0 is defined by a system of n^2 polynomial equations. They aren't independent equations (for instance, for all (A,B), the trace of AB-BA is 0, and that imposes one coherence condition on the system), but I think it's pretty clear that they are "almost independent" (specifically, that that one condition is *it*), and that therefore X is an algebraic subset of V of codimension n^2-1, which is greater than 0 except when n = 1. So if F is R or C, and you define "probability" in any usual way (using Lebesgue measure, say), unless n = 1, the probability that (A,B) is a commuting pair is 0 (and if n = 1, it's 1). If F is a finite field, you'd get a potentially interesting combinatorial problem (maybe Tal Kubo would know the answer? any other volunteers?). My uninformed guess is that, for fixed dimension > 1 and fixed characteristic, as the number of elements in the field grows the probability will go to zero. Lee Rudolph ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Commutitive Matrices Date: 19 Feb 1999 18:11:02 GMT Newsgroups: sci.math Lee Rudolph wrote: >Bryce Bockman writes: > >>Does any one know what the probability that two matrices will commute is. [...] >So if F is >R or C, and you define "probability" in any usual way (using >Lebesgue measure, say), unless n = 1, the probability that >(A,B) is a commuting pair is 0 (and if n = 1, it's 1). If F >is a finite field, you'd get a potentially interesting >combinatorial problem (maybe Tal Kubo would know the answer? >any other volunteers?). My uninformed guess is that, for >fixed dimension > 1 and fixed characteristic, as the number of >elements in the field grows the probability will go to zero. May I exclude the singular matrices? Then it's not so much combinatorics as group theory and linear algebra. You want, for each prime power p^m and matrix size n, the number Pr(p,m,n) = #{ (A,B) ; AB = BA } / |GL(n,p^m)|^2 Note that if A and A' are conjugate then their centralizers are, too, so that numerator is a Sum( |Cent(A)| ; A an element of GL(n, p^m) ) = Sum( |Cent(A)|*|C| ; C a conjugacy class in GL(n, p^m), A in C ) = |GL(n, p^m)| * (number of conjugacy classes) That is, after some cancellation, we see that the probability in question is just the ratio of the number k of conjugacy classes in GL(n, p^m) to the order of that group. How many conjugacy classes are there in GL(n,q)? I don't remember if there is a nice formula. At a minimum there are the companion matrices of the q^n monic polynomials of degree n in GF(q); these are mutually non-conjugate since conjugate matrices have the same characteristic polynomial. I'm pretty sure this number dominates the size of k. On the other hand there certainly is a formula for the size of GL(n,q): Think of constructing an invertible qxq matrix. You have q^n -1 vectors to put into the first column, then q^n - q to put in the second, and so on. So |GL(n,q)| = Prod( q^n - q^i, i=0..(n-1) ). Lee Rudolph wants to hold n fixed and let q=p^m increase. These arguments then show the probability is on the order of q^n / q^(n^2), which tends to zero as q increases to infinity; it is not necessary to assume the characteristic stays fixed. It's also clear that the probability drops to zero if q is fixed and n increases, which seems pretty true to experience anyway. I haven't thought through the details of non-invertible matrices and matrices with repeated eigenvalues, which will certainly change the tallies above, but not, I think, the limits. dave