This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(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
1, 2, 11, 172, 6327, 474286, 67147431, 17080038508 (list; graph; refs; listen; history; text; internal format)



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

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.

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:

0 0 1 0 0

0 0 0 0 1

1 1 0 0 1

1 1 0 1 0

1 1 0 1 0.

The optimal values seem to match A070214, verified for n<=7.

Term (5,1) of n-th power of the 5x5 matrix shown = A001045(n), the Jacobsthal sequence. [From Gary W. Adamson, Oct 03 2008]

a(n) >= A226321(n).


Table of n, a(n) for n=0..7.

Eric Weisstein's World of Mathematics, Background information about adjacency matrices

E. W. Weisstein, (0,1)-Matrix, MathWorld. [P. Petsie, Aug 03 2008]

Wikipedia, Background information about adjacency matrices


Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.

Sequence in context: A120445 A003088 * A122527 A039747 A049531 A031508

Adjacent sequences:  A121228 A121229 A121230 * A121232 A121233 A121234




Dan Dima, Aug 21 2006


Edited by R. J. Mathar, Oct 01 2008

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

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 December 17 00:23 EST 2018. Contains 318191 sequences. (Running on oeis4.)