[seqfan] Re: Number of nxn (0,1)-matrices A with A^2 = J?

Richard J. Mathar mathar at mpia-hd.mpg.de
Fri Mar 10 10:13:57 CET 2017


In response to http://list.seqfan.eu/pipermail/seqfan/2017-March/017328.html :

The search space seems to grow proportional to the number of (0,1) matrices
with n rows and n columns, n=c^2, which have exactly c ones in each row.
According to A008300 this grows as
n=1, c=1: 1
n=4, c=2: 90
n=9, c=3: 315031400802720
n=16, c=4: 6892692735539278753058456514221737762215000

As a starter one could count by brute force the matrices that are circulant,
obtaining at least some well-defined lower estimates of the counts of
all solutions to A^2=J:

g-circulant solutions to the (0,1) matrix equation A^m=J_n
Lin Alg. Applic. 345 (1-3) (2002) 195-224
http://dx.doi.org/10.1016/S0024-3795(01)00491-8

Because the number of ones per row in the n*n matrices is only c,
giving binomial(c,c^2) choices to start with, defining a single top
line of the matrix generates the circulant versions that can
be more quickly scanned than some sort of examination of the
search space indicated above.

The only caveat is that one cannot add  the count of the circulant matrices
blindly because some periodic symmetries in the 1-0 pattern in the top row
may lead to over-counting if the shift-width interferes with the length of
that pattern.

RJM



More information about the SeqFan mailing list