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