|
%I #33 Jun 05 2021 04:38:50
%S 1,2,11,172,6327,474286,67147431,17080038508
%N Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.
%C Comments from _Brendan McKay_, Aug 21 2006: Equivalently, directed graphs (simple but loops allowed) without a few small forbidden subgraphs (those allowing 2 distinct paths of length 2 from vertex x to vertex y for some x,y; I think there are 6 possibilities). One can also consider isomorphism classes of those digraphs.
%C Comment from _Rob Pratt_, Aug 03 2008: A121294 provides a lower bound on the maximum number of 1's in such a matrix M. There are cases where a higher number is reached; the following 5 X 5 matrix has 11 ones and its square is binary:
%C 0 0 1 0 0
%C 0 0 0 0 1
%C 1 1 0 0 1
%C 1 1 0 1 0
%C 1 1 0 1 0.
%C The optimal values seem to match A070214, verified for n <= 7.
%C Term (5,1) of the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - _Gary W. Adamson_, Oct 03 2008
%C a(n) >= A226321(n).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphPower.html">Background information about adjacency matrices</a>
%H E. W. Weisstein, <a href="http://mathworld.wolfram.com/01-Matrix.html">(0,1)-Matrix</a>, MathWorld. [P. Petsie, Aug 03 2008]
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Adjacency_matrix">Background information about adjacency matrices</a>
%H <a href="/index/Mat#binmat">Index entries for matrices, binary, which are squares</a>
%Y Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.
%K nonn,more
%O 0,2
%A _Dan Dima_, Aug 21 2006
%E Edited by R. J. Mathar, Oct 01 2008
%E a(7) from _R. H. Hardin_, Jun 19 2012. This makes it clear that the old A122527 was really a badly-described version of this sequence, and that a(7) was earlier found by Balakrishnan (bvarada2(AT)jhu.edu), Sep 17 2006. - _N. J. A. Sloane_, Jun 19 2012
%E Entry revised by _N. J. A. Sloane_, Jun 19 2012
| 