A056990 -id:A056990 - cp's OEIS frontend

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

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

All eigenvalues are nonzero.

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

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

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.

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

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

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

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

A046747 Number of n X n rational {0,1}-matrices of determinant 0.

Original entry on oeis.org

1, 10, 338, 42976, 21040112, 39882864736, 292604283435872, 8286284310367538176

Offset: 1

Günter M. Ziegler (ziegler(AT)math.tu-berlin.de)

			a(2)=10: the matrix of all 0's, 4 matrices with 2 zeros in the same row or column, 4 matrices with 3 zeros and the all-1 matrix.

J. Bourgain, V. Vu and P. M. Wood, On the Singularity Probability of Discrete Random Matrices, Journal of Functional Analysis, 258 (2010), 559-603.
R. P. Brent and J. H. Osborn, Bounds on minors of binary matrices, arXiv preprint arXiv:1208.3330 [math.CO], 2012.
J. Kahn, J. Komlos and E. Szemeredi, On the probability that a random ±1-matrix is singular, J. AMS 8 (1995), 223-240.
J. Komlos, On the determinant of (0,1)-matrices, Studia Math. Hungarica 2 (1967), 7-21.
N. Metropolis and P. R. Stein, On a class of (0,1) matrices with vanishing determinants, J. Combin. Theory, 3 (1967), 191-198.
Eric Weisstein's World of Mathematics, Singular Matrix.
Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.
Miodrag Zivkovic, Classification of small (0,1) matrices, Linear Algebra and its Applications, 414 (2006), 310-346.
Index entries for sequences related to binary matrices

Cf. A000409, A000410, A002416, A002884, A046747, A055165, A056989, A056990.

Sum[KroneckerDelta[Det[Array[Mod[Floor[k/(2^(n*(#1-1)+#2-1))],2]&,{n,n}]],0],{k,0,(2^(n^2))-1}] (* John M. Campbell, Jun 24 2011 *)
Count[Det /@ Tuples[{0, 1}, {n, n}], 0] (* David Trimas, Sep 23 2024 *)

A046747(n) = m=matrix(n,n); ct=0; for(x=0,2^(n*n)-1,a=binary(x+2^(n*n)); for(i=1,n, for(j=1,n,m[i,j]=a[n*i+j+1-n])); if(matdet(m)==0,ct=ct+1,); ); ct \\ Randall L Rathbun

a(n)=sum(i=0,2^n^2-1,matdet(matrix(n,n,x,y,(i>>(n*x+y-n-1))%2))==0) \\ Charles R Greathouse IV, Feb 21 2015

a(n) = 2^(n^2) - n! * binomial(2^n -1, n) + n! * A000410(n).
a(n) + A055165(n) = 2^(n^2) = total number of n X n (0, 1) matrices.
The probability that a random n X n {0,1}-matrix is singular is conjectured to be asymptotic to C(n+1, 2)*(1/2)^(n-1). [Corrected by N. J. A. Sloane, Jan 02 2007]

a(8) from Vladeta Jovovic, Mar 28 2006

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Original entry on oeis.org

1, 2, 48, 11808, 27947520, 609653621760, 119288919620689920

Offset: 0

Eric W. Weisstein

It would be nice to have an estimate for the asymptotic rate of growth.

			a(1) = 2: [1], [ -1].
a(2) = 48: There are 8 choices for the first column, u (say) and then the 2nd column can be anything except 0, u, -u, so 6 choices, giving a total of 8*6 = 48.

Minfeng Wang, C++ program to calculate A056989
Eric Weisstein's World of Mathematics, Nonsingular Matrix
Index entries for sequences related to binary matrices

Cf. A055165, A053290, A056990, A055165, A002884, A046747, A057981, A060722.

(* A brute force solution up to n = 4 *) a[n_] := a[n] = (m = Array[x, {n, n}]; cnt = 0; iter = {#, -1, 1}& /@ Flatten[m]; Do[ If[ Det[m] != 0, cnt++], Evaluate[ Sequence @@ iter]]; cnt); Table[ Print[a[n]]; a[n], {n, 1, 4}] (* Jean-François Alcover, Oct 11 2012 *)

a(n) = A060722(n) - A057981(n). - Alois P. Heinz, Dec 02 2019

a(4) from Winston C. Yang (winston(AT)cs.wisc.edu), Aug 27 2000
Entry revised by N. J. A. Sloane, Jan 02 2007
a(5) from Giovanni Resta, Feb 20 2009
a(0)=1 prepended by Alois P. Heinz, Dec 02 2019
a(0)-a(5) confirmed and a(6) added by Minfeng Wang, May 01 2024

A118992 Number of real n X n invertible symmetric (+1,-1) matrices.

Original entry on oeis.org

2, 4, 32, 512, 16896, 1190144, 163899904, 46195853312, 25585116626944, 28281621931343872

Offset: 1

Giovanni Resta, May 08 2006

Cf. A056990, A086899, A056989, A118990, A118993, A118994, A118997.

a(n) = 2^(n*(n+1)/2) - A118990(n) = A118994(n) + A118997(n). - Max Alekseyev, Jun 12 2025

a(8)-a(10) from Max Alekseyev, Jun 17 2025

A057982 Number of singular n X n (-1,1)-matrices.

Original entry on oeis.org

0, 8, 320, 43264, 22003712, 43090149376, 326720427917312, 9588057159626653696, 1086099857128493963804672

Offset: 1

Eric W. Weisstein, Oct 23 2000

a(n) = 2^(2n-1)*A046747(n-1). - Kevin Costello, May 18 2005

R. P. Brent and J. H. Osborn, Bounds on minors of binary matrices, arXiv preprint arXiv:1208.3330 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 25 2012
Konstantin Tikhomirov, Singularity of random Bernoulli matrices, arXiv preprint arXiv:1812.09016 [math.PR], 2018-2019.
Eric Weisstein's World of Mathematics, Singular Matrix.

Complement of A056990.

Cf. A046747.

a(n)/2^(n^2) ~ (1/2 + o_n(1))^n (proved by Tikhomirov). - Timothy Y. Chow, Jan 17 2019

More terms from Kevin Costello, May 18 2005

a(6)-a(9) from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 18 2008

A364886 Number of n X n (-1, 1)-matrices which have only eigenvalues with strictly negative real part (which implies that the matrix has all nonzero eigenvalues).

Original entry on oeis.org

1, 2, 20, 640, 97824, 47545088

Offset: 1

Thomas Scheuerle, Aug 12 2023

As this problem is symmetric with sign we can get the same numbers for strictly positive real parts.
All values for n > 1 are even, because a transposed matrix has the same spectrum of eigenvalues.
Matrices with determinant 0 are not counted.
Let M be such a matrix then the limit of ||exp(t*M)*y|| if t goes to infinity will be zero.
n = 5 is the first case where not all entries on the main diagonal are -1. 93984 matrices with 5 times -1 on the main diagonal and 5*768 with 4 times -1 on the main diagonal have only eigenvalues with strictly negative real part.
In the case n = 6, 43586048 matrices with 6 times -1 on the main diagonal, 6*656000 matrices with 5 times -1 on the main diagonal and 15*1536  matrices with 5 times -1 on the main diagonal have only eigenvalues with strictly negative real part.

			For n = 2 the matrices are:
.
    -1,  1
    -1, -1
.
    -1, -1
     1, -1.

Index entries for sequences related to binary matrices

Cf. A056990.
Cf. A083058, A085506, A087488, A098148, A086510, A207259.
Cf. A219736, A346210, A271570, A271588, A296605, A306002.
Cf. A306791, A306792, A306793, A306794, A306795, A326928.
Cf. A346209.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A046747 Number of n X n rational {0,1}-matrices of determinant 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A056989 Number of nonsingular n X n (-1,0,1)-matrices (over the reals).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A118992 Number of real n X n invertible symmetric (+1,-1) matrices.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A057982 Number of singular n X n (-1,1)-matrices.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A364886 Number of n X n (-1, 1)-matrices which have only eigenvalues with strictly negative real part (which implies that the matrix has all nonzero eigenvalues).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs