A070322 Number of primitive n X n real (0,1)-matrices.

1, 1, 3, 139, 25575, 18077431, 47024942643

Offset: 0

Author

N. J. A. Sloane, Aug 22 2003

Keywords

• nonn
• hard
• more

Comments

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).

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

References

• Sachkov, V. N. and Tarakanov, V. E., Combinatorics of Nonnegative Matrices. Translations of Mathematical Monographs, 213. American Mathematical Society, Providence, RI, 2002.

Links

• Nicholas R. Beaton, Walks obeying two-step rules on the square lattice: full, half and quarter planes, arXiv:2010.06955 [math.CO], 2020.
• S. J. Leon, Linear Algebra with Applications: the Perron-Frobenius Theorem [Cached copy at the Wayback Machine]
• G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
• D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
• Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-648.
• Index entries for sequences related to binary matrices

Crossrefs

Cf. A003030.

Programs

Mathematica

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} ]

Formula

For asymptotics see Sachkov and Tarakanov.

Extensions

Wouter Meeussen computed a(0) through a(4), Aug 22 2003

I. J. Kennedy computed a(0) through a(5), Aug 22 2003

a(6) from Pontus von Brömssen, Aug 09 2022