Number of bipartite graphs with full rank

[Roland Bacher]

On Fri, Nov 11, 2005 at 12:48:22PM -0000, simone at cs.york.ac.uk wrote:
> Dear seqfans,
> 
> I have the following question:
> 
> What is the number of nonisomorphic bipartite graphs on n vertices whose
> adjacency matrix has n nonzero eigenvalues?
> 
> Thanks a lot for your time,
> Simone
> 
> --
> Simone Severini
> Department of Mathematics and Department of Computer Science
> University of York, YO10 5DD York, U.K.
> Tel: +44 (0)1904 433072
> Web: www-users.york.ac.uk/~ss54
> 
> 
A necessary condition is that $n$ is an even integer $n=2m$ 
and each class of vertices has exactly $n$ elements. Indeed,
the adjacency matrix of such a graph with suitably ordered
vertices is given by

(  0     A )

( A^t    0 )

and such a matrix is non-degenerate if and only if 
$A$ is a non-degenerate square matrix.

The total number of such graphs with $2m$
vertices equals thus the number of orbits of
non-degenerate {0,1} matrices of square-size m\times m
under the action of the direct product $S_m \times S_m$ 
of two symmetric groups, the first acting by left-multiplication
of permutation-matrices and the second acting by 
right-multiplication of permutation-matrices.

Asymptotically, the correct answer should thus be 
$2^{m^2}/(m!)^2$ since a random {0,1} matrix of 
huge square-size is almost surely invertible and 
has almost surely a trivial stabilizer under the 
above action of $S_m\times S_m$.

To compute the generating function of the associated
integer sequences is another (and probably more difficult)
story.

Best whishes,   Roland Bacher