login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A121231 Number of n X n binary matrices M such that M^2 is also a binary matrix. 6

%I

%S 1,2,11,172,6327,474286,67147431,17080038508

%N Number of n X n binary matrices M such that M^2 is also a binary matrix.

%C A binary matrix is a real matrix with entries 0 and 1.

%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 _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 n-th power of the 5x5 matrix shown = A001045(n), the Jacobsthal sequence. [From _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>

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 18:25 EDT 2019. Contains 324330 sequences. (Running on oeis4.)