%I #46 Aug 09 2022 09:05:40
%S 1,1,3,139,25575,18077431,47024942643
%N Number of primitive n X n real (0,1)-matrices.
%C An n X n nonnegative matrix A is primitive iff every element of A^k is > 0 for some power k. If A is primitive then the power which should have all positive entries is <= n^2 - 2n + 2 (Wielandt).
%C Equivalently, a(n) is the number of n X n Boolean relation matrices that converge in their powers to U, the all 1's matrix. From the Rosenblatt reference we know that the relations that converge to U are precisely those that are strongly connected and whose cycle lengths have gcd equal to 1. In particular, if a strongly connected relation has at least one self loop then it converges to U. So A003030(n)*(2^n - 1) < a(n) < A003030(n)*2^n. Almost all (0,1)-matrices are primitive. - _Geoffrey Critzer_, Jul 20 2022
%D Sachkov, V. N. and Tarakanov, V. E., Combinatorics of Nonnegative Matrices. Translations of Mathematical Monographs, 213. American Mathematical Society, Providence, RI, 2002.
%H Nicholas R. Beaton, <a href="https://arxiv.org/abs/2010.06955">Walks obeying two-step rules on the square lattice: full, half and quarter planes</a>, arXiv:2010.06955 [math.CO], 2020.
%H S. J. Leon, <a href="https://web.archive.org/web/20171109083901/http://www.prenhall.com/divisions/esm/app/ph-linear/leon/html/perron.html">Linear Algebra with Applications: the Perron-Frobenius Theorem</a> [Cached copy at the Wayback Machine]
%H G. Markowsky, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN001251775">Bounds on the index and period of a binary relation on a finite set</a>, Semigroup Forum, Vol 13 (1977), 253-259.
%H D. Rosenblatt, <a href="https://nvlpubs.nist.gov/nistpubs/jres/67B/jresv67Bn4p249_A1b.pdf">On the graphs of finite Boolean relation matrices</a>, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
%H Helmut Wielandt, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002381516">Unzerlegbare, nicht negative Matrizen</a>, Math. Z. 52 (1950), 642-648.
%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F For asymptotics see Sachkov and Tarakanov.
%t Table[ it=Partition[ #, n ]&/@IntegerDigits[ Range[ 0, -1+2^n^2 ], 2, n^2 ]; Count [ it, (q_?MatrixQ) /; (Max@@Table[ Min@@Flatten[ MatrixPower[ q, k ] ], {k, 1, n^2-2n+2} ] )>0 ], {n, 1, 4} ]
%Y Cf. A003030.
%K nonn,hard,more
%O 0,3
%A _N. J. A. Sloane_, Aug 22 2003
%E _Wouter Meeussen_ computed a(0) through a(4), Aug 22 2003
%E _I. J. Kennedy_ computed a(0) through a(5), Aug 22 2003
%E a(6) from _Pontus von Brömssen_, Aug 09 2022