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 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