# Number of bipartite graphs with full rank

Roland Bacher Roland.Bacher at ujf-grenoble.fr
Fri Nov 11 16:35:39 CET 2005

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