login
a(n) is the number of n X n {0,1}-matrices (over the reals) that contain no zeros when squared.
1

%I #21 Jun 23 2019 17:00:40

%S 1,1,3,73,6003,2318521,4132876803

%N a(n) is the number of n X n {0,1}-matrices (over the reals) that contain no zeros when squared.

%C 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.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Logical_matrix">Logical matrix</a>.

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

%e 1 1 0 1 1 1

%e 1 0 1 1 1 1

%t 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;

%t Do[Print[a[n]], {n, 0, 5}] (* _Jean-François Alcover_, Jun 23 2019 *)

%o (MATLAB)

%o %Exhaustively searches all matrices

%o %from n = 1 to 5

%o result = zeros(1,5);

%o for n = 1:5

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

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

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

%o D = M^2;

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

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

%o end

%o end

%o end

%Y Cf. A002720, A055601, A055602.

%Y A002416 is the total number of possible square binary matrices.

%Y A307248 gives a lower bound.

%K nonn,hard,more

%O 0,3

%A _Christopher Cormier_, Mar 29 2019

%E a(6) from _Giovanni Resta_, May 29 2019