|
|
A070322
|
|
Number of primitive n X n real (0,1)-matrices.
|
|
12
|
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|