login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A070322 Number of primitive n X n real (0,1)-matrices. 12
1, 1, 3, 139, 25575, 18077431, 47024942643 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
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.
FORMULA
For asymptotics see Sachkov and Tarakanov.
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} ]
CROSSREFS
Cf. A003030.
Sequence in context: A030247 A139956 A236193 * A053527 A195632 A152504
KEYWORD
nonn,hard,more
AUTHOR
N. J. A. Sloane, Aug 22 2003
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:21 EDT 2024. Contains 370952 sequences. (Running on oeis4.)