cp's OEIS Frontend

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

%I A121231 #34 Feb 16 2025 08:33:02
%S A121231 1,2,11,172,6327,474286,67147431,17080038508
%N A121231 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 A121231 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 A121231 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 A121231 0 0 1 0 0
%C A121231 0 0 0 0 1
%C A121231 1 1 0 0 1
%C A121231 1 1 0 1 0
%C A121231 1 1 0 1 0.
%C A121231 The optimal values seem to match A070214, verified for n <= 7.
%C A121231 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 A121231 a(n) >= A226321(n).
%H A121231 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphPower.html">Background information about adjacency matrices</a>
%H A121231 E. W. Weisstein, <a href="https://mathworld.wolfram.com/01-Matrix.html">(0,1)-Matrix</a>, MathWorld. [P. Petsie, Aug 03 2008]
%H A121231 Wikipedia, <a href="http://en.wikipedia.org/wiki/Adjacency_matrix">Background information about adjacency matrices</a>
%H A121231 <a href="/index/Mat#binmat">Index entries for matrices, binary, which are squares</a>
%Y A121231 Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.
%K A121231 nonn,more
%O A121231 0,2
%A A121231 _Dan Dima_, Aug 21 2006
%E A121231 Edited by R. J. Mathar, Oct 01 2008
%E A121231 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 A121231 Entry revised by _N. J. A. Sloane_, Jun 19 2012