login
Number of invertible n X n matrices with entries equal to 0 or 1.
20

%I #46 Jun 18 2022 09:49:11

%S 1,1,6,174,22560,12514320,28836612000,270345669985440,

%T 10160459763342013440

%N Number of invertible n X n matrices with entries equal to 0 or 1.

%C All eigenvalues are nonzero.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NonsingularMatrix.html">Nonsingular Matrix.</a>

%H Chai Wah Wu, <a href="https://arxiv.org/abs/1805.07431">Can machine learning identify interesting mathematics? An exploration using empirically observed laws</a>, arXiv:1805.07431 [cs.LG], 2018.

%H Miodrag Zivkovic, <a href="https://arxiv.org/abs/math/0511636">Classification of small (0,1) matrices</a>, arXiv:math/0511636 [math.CO], 2005; Linear Algebra and its Applications, 414 (2006), 310-346.

%H Miodrag Zivkovic, <a href="http://www.matf.bg.ac.rs/~ezivkovm/01matrices.htm">Classification of (0,1) matrices of order not exceeding 8</a>.

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F For an asymptotic estimate see A046747. A002884 is a lower bound. A002416 is an upper bound.

%F a(n) = n! * A088389(n). - _Gerald McGarvey_, Oct 20 2007

%e For n=2 the 6 matrices are {{{0, 1}, {1, 0}}, {{0, 1}, {1, 1}}, {{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}, {{1, 1}, {1, 0}}}.

%o (PARI) a(n)=sum(t=0,2^n^2-1,!!matdet(matrix(n,n,i,j,(t>>(i*n+j-n-1))%2))) \\ _Charles R Greathouse IV_, Feb 09 2016

%o (Python)

%o from itertools import product

%o from sympy import Matrix

%o def A055165(n): return sum(1 for s in product([0,1],repeat=n**2) if Matrix(n,n,s).det() != 0) # _Chai Wah Wu_, Sep 24 2021

%Y Cf. A056990, A056989, A046747, A055165, A002416, A003024 (positive definite matrices).

%Y A046747(n) + a(n) = 2^(n^2) = total number of n X n (0, 1) matrices = sequence A002416.

%Y Main diagonal of A064230.

%K nonn,nice,hard,more

%O 0,3

%A Ulrich Hermisson (uhermiss(AT)server1.rz.uni-leipzig.de), Jun 18 2000

%E More terms from Miodrag Zivkovic (ezivkovm(AT)matf.bg.ac.rs), Feb 28 2006

%E Description improved by _Jeffrey Shallit_, Feb 17 2016

%E a(0)=1 prepended by _Alois P. Heinz_, Jun 18 2022