login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307232 a(n) is the number of n X n {0,1}-matrices (over the reals) that contain no zeros when squared. 1
1, 1, 3, 73, 6003, 2318521, 4132876803 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

For every n, there are trivial solutions where an entire row is filled with 1's and an entire column is filled with 1's, and the column index is equal to the row index. This easily follows from the nature of matrix multiplication. Every matrix that has at least one of these row/column pairs along with any other 1's is also a solution because there are no negative numbers involved here. The number of trivial solutions is given by A307248.

LINKS

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

Wikipedia, Logical matrix.

EXAMPLE

For n = 2, the a(2) = 3 solutions are

  1 1    0 1    1 1

  1 0    1 1    1 1

MATHEMATICA

a[n_] := Module[{b, iter, cnt = 0}, iter = Sequence @@ Table[{b[k], 0, 1}, {k, 1, n^2}]; Do[If[FreeQ[MatrixPower[Partition[Array[b, n^2], n], 2], 0], cnt++], iter // Evaluate]; cnt]; a[0] = 1;

Do[Print[a[n]], {n, 0, 5}] (* Jean-Fran├žois Alcover, Jun 23 2019 *)

PROG

(MATLAB)

%Exhaustively searches all matrices

%from n = 1 to 5

result = zeros(1, 5);

for n = 1:5

for m = 0:2^(n^2)-1

    p = fliplr(dec2bin(m, n^2) - '0');

    M = reshape(p, [n n]);

    D = M^2;

    if(isempty(find(D==0, 1)))

        result(n) = result(n) + 1;

    end

end

end

CROSSREFS

Cf. A002720, A055601, A055602.

A002416 is the total number of possible square binary matrices.

A307248 gives a lower bound.

Sequence in context: A012810 A020517 A119017 * A002667 A145675 A336873

Adjacent sequences:  A307229 A307230 A307231 * A307233 A307234 A307235

KEYWORD

nonn,hard,more

AUTHOR

Christopher Cormier, Mar 29 2019

EXTENSIONS

a(6) from Giovanni Resta, May 29 2019

STATUS

approved

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 16:44 EDT 2021. Contains 345417 sequences. (Running on oeis4.)