A226321 -id:A226321 - 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.

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

Offset: 0

Dan Dima, Aug 21 2006

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 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:
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 the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - Gary W. Adamson, Oct 03 2008
a(n) >= A226321(n).

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
Index entries for matrices, binary, which are squares

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

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

A225371 a(n) = number of squares in M(n,2), the ring of n X n matrices over GF(2).

Original entry on oeis.org

1, 2, 10, 260, 31096, 13711952, 28275659056, 224402782202048, 7293836994286696576, 952002419516769475035392, 497678654312172407869125822976, 1044660329769242614113093804053562368, 8745525723307044762290950664928498588583936

Offset: 0

N. J. A. Sloane, May 07 2013

a(0)-a(4) computed by W. Edwin Clark, May 07 2013.

A226321 is a similar sequence which counts the real {0,1} matrices which are the square of a {0,1} matrix. - Giovanni Resta, Jun 03 2013

Victor S. Miller, Table of n, a(n) for n = 0..30
Victor S. Miller, Counting Matrices that are Squares, arXiv:1606.09299 [math.GR], 2016.
Giovanni Resta, C program for a(k), with k <= 6.
Index entries for matrices, binary, which are squares

Cf. A226321, A121231, A266462, A274313.

a(n)=#vecsort(lift(vector(2^n^2,k,matrix(n,n,i,j,bittest(k,(i-1)*n+j-1))^2*Mod(1,2))),,8) \\ Charles R Greathouse IV, May 07 2013

ZM(k)=matrix(n,n,i,j,bittest(k,(i-1)*n+j-1))*Mod(1,2)
MZ(M)=my(n=matsize(M)[1]);sum(i=1,n,sum(j=1,n,M[i,j]<<((i-1)*n+j-1)))
a(n)=#vecsort(vector(2^n^2,i,MZ(lift(ZM(i,n)^2))),,8) \\ Charles R Greathouse IV, May 07 2013

a(5)-a(6) from Giovanni Resta, May 08 2013

a(7)-a(30) from Victor S. Miller, May 24 2013

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions