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

1, 1, 6, 174, 22560, 12514320, 28836612000, 270345669985440, 10160459763342013440

Offset: 0

Author

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

Keywords

• nonn
• nice
• hard
• more

Comments

All eigenvalues are nonzero.

Examples

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

Links

• Eric Weisstein's World of Mathematics, Nonsingular Matrix.
• Chai Wah Wu, Can machine learning identify interesting mathematics? An exploration using empirically observed laws, arXiv:1805.07431 [cs.LG], 2018.
• Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005; Linear Algebra and its Applications, 414 (2006), 310-346.
• Miodrag Zivkovic, Classification of (0,1) matrices of order not exceeding 8.
• Index entries for sequences related to binary matrices

Crossrefs

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

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

Main diagonal of A064230.

Programs

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

Python

from itertools import product
from sympy import Matrix
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

Formula

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

a(n) = n! * A088389(n). - Gerald McGarvey, Oct 20 2007

Extensions

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

Description improved by Jeffrey Shallit, Feb 17 2016

a(0)=1 prepended by Alois P. Heinz, Jun 18 2022