From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: matrix equation AB = 0
Date: 8 Apr 1997 22:40:55 GMT

In article <334117C8.3E8@univ-tln.fr>,
Philippe Langevin  <langevin@univ-tln.fr> wrote:
>Hi,
>
>Let a,b,c three positive integers.
>
>Let q the cardinality of a finite field K
>
>I denote N(a,b,c,q) the number of couples of matrices (A,B) satisfying
>the conditions :
>
>	(1) AB = 0
>	(2) A is an axc matrix with coefficients in K
>	(3) B is an cxb matrix with coefficient in K
>
>Have you a (nice) formula to get N(a,b,c,q) ?

Come, come; all those linear algebra students out there writing in with
questions and none so bold as to try this? The following is at least 
right in spirit and may even have all the details correct :-).

The multiplications by  A  and  B  are the linear mappings
K^c -> K^a  and  K^b -> K^c  respectively. We need only ask for the
number of pairs of linear transformations with ker(A) containing im(B).
Count these by considering what this subspace  V=ker(A) of  K^c  is.

For each fixed  V, choose a basis of  K^c  which contains a basis of  V.
Then we may count the linear maps  K^c -> K^a whose kernel is exactly  V
as follows: if the elements of the basis which are not in  V  are
{v1, v2, ..., vd}  [so that  d=c-dim(V)] then we may send  v1  to any of the
(q^a-1) nonzero vectors of  K^a; we may then send  v2  to any of the
(q^a-q) vectors linearly independent of that first choice; likewise v3
may be sent to any of (q^a-q^2) vectors independent of the first two, and
so on. Since a linear map is determined by its action on a basis, the
number of linear maps  K^c -> K^a  whose kernel is precisely  V  is
Prod(  (q^a-q^i), i=0 .. d-1 ). Note in particular that if d>a then this
number is zero.

Meanwhile, what are the mappings sending  K^b  into  V? That's easier:
simply send each basis vector in  K^b  to any of the  |V|=q^dim(V)
elements of  V. Thus there are  |V|^b=q^(b*(c-d))  such maps.

Finally we ask how many of these subspaces  V  there are. One way to 
examine these is as follows. To find an  e-dimensional subspace of
K^c, simply take the image of any one-to-one linear map  K^e -> K^c.
As above, there are  Prod( (q^c-q^i), i=0.. e-1 ) of these. Of course, not
all these linear transformations will have the same image; two of them
do iff each can be written as a composite of the other with an
isomorphism of  K^e, of which there are  |GL(e,q)|=Prod( (q^e-q^i), i=0..e-1).
So there are
	Prod( (q^c-q^i)/(q^e-q^i), i=0..e-1 )
subspaces of dimension  e  in  K^c.

So we can sum over all those intermediate subspaces  V  by summing over 
all possible  e=0..a: the number of such pairs  (A,B)  seems to be
(using  d = c-e):

Sum, e=0 .. a  of:
	Prod( (q^c-q^i)/(q^e-q^i), i=0..e-1 ) * 
	Prod( (q^a-q^i), i=0 .. c-e-1 ) * q^(b*e)  

This simplifies at least a little (and maybe more than I see right now):
letting r_n = q^n-1 we have
	Prod( r_(c-i) / r_(e-i), i=0..e-1 ) * Prod( r_(a-i), i=0 .. c-e-1 )
	*q^( b*e + (c-e)*(c-e-1)/2 )
Since  r_0=0, this product is zero unless  c-a <= e <= c. 

Well, OK, maybe that's a little too much for introductory linear
algebra students but finite group theorists do this all the time.
Look up "finite groups of Lie type".

dave