A064230 -id:A064230 - 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

A000410 Number of singular n X n rational (0,1)-matrices.

Original entry on oeis.org

0, 0, 6, 425, 65625, 27894671, 35716401889, 144866174953833

Offset: 1

N. J. A. Sloane

Number of all n X n (0,1)-matrices having distinct, nonzero ordered rows and determinant 0 - compare A000409.

a(n) is the number of singular n X n rational {0,1}-matrices with no zero rows and with all rows distinct, up to permutation of rows and so a(n) = binomial(2^n-1,n) - A088389(n). Cf. A116506, A116507, A116527, A116532. - Vladeta Jovovic, Apr 03 2006

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. Metropolis and P. R. Stein, On a class of (0,1) matrices with vanishing determinants, J. Combin. Theory, 3 (1967), 191-198.
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, A046747, A064230, A064231.

n! * a(n) = A046747(n) - 2^(n^2) + n! * binomial(2^n -1, n).

n=7 term from Guenter M. Ziegler (ziegler(AT)math.TU-Berlin.DE)

a(8) from Vladeta Jovovic, Mar 28 2006

A064231 Triangle read by rows: T(n,k) = number of rational (+1,-1) matrices of rank k (n >= 1, 1 <= k <= n).

Original entry on oeis.org

2, 8, 8, 32, 288, 192, 128, 6272, 36864, 22272, 512, 115200, 3456000, 18432000, 11550720, 2048, 1968128, 243302400, 6471168000, 36373708800, 25629327360, 8192, 32514048, 14809546752, 1557061632000, 43378316083200, 281770208133120

Offset: 1

N. J. A. Sloane, Sep 23 2001

Rows add to 2^(n^2) = A002416. - Jonathan Vos Post, Feb 27 2011

Komlos and later Kahn, Komlos and Szemeredi show that almost all such matrices are invertible.

			2; 8,8; 32,288,192; 128,6272,36864,22272; ...

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 determinants of random matrices, Studia Sci. Math. Hungar., 3 (1968), 387-399.

Cf. A064230, A000409, A000410, A046747.

T=matrix(4,4); { for(n=1,4, mm=matrix(n,n); for(k=1,n, T[n,k]=0); forvec(x=vector(n*n,i,[0,1]), for(i=1,n, for(j=1,n,mm[i,j]=(-1)^x[i+n*(j-1)])); T[n,matrank(mm)]++); for(k=1,n,print1(T[n,k], if(k

More terms and PARI code from Michael Somos, Sep 25 2001
More terms from Vladeta Jovovic, Apr 02 2006
Offset changed to 1 by T. D. Noe, Mar 02 2011

A086875 Sum of rank(M) over all n X n matrices over Z with all entries zero or one.

Original entry on oeis.org

1, 21, 1147, 211965, 143331811, 366753209781

Offset: 1

Tom Womack (tom(AT)womack.net), Aug 21 2003

The unlikely-looking symbol "+:=" in the MAGMA code is in fact correct. - N. J. A. Sloane, Feb 02 2009

Cf. A064230.

for a in [1..5] do b := 0; for c in CartesianPower([0,1], a^2) do b +:= Rank(Matrix(a, a, [aa : aa in c])); end for; print b; end for;

a(n) = Sum_{k=1..n} k * A064230(n,k). - Alois P. Heinz, Jun 18 2022

a(6) from Alois P. Heinz, Jun 18 2022

A354741 Triangular array read by rows. T(n,k) is the number of n X n Boolean matrices with row rank k, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 37488, 19272, 1, 961, 194850, 4811700, 17551800, 10995120

Offset: 0

Geoffrey Critzer, Jun 12 2022

Compare to A286331 which counts n X n matrices over the field GF(2). Note that the limit when n->oo of the probability that a matrix over GF(2) has rank n is equal to Product_{i>=1} (1-1/2^i) = 0.288... (see A048651). Here, it appears (from some empirical computations) that the limiting probability that a Boolean matrix has rank n is 1.

			Table begins:
  1;
  1,   1;
  1,   9,    6;
  1,  49,  306,   156;
  1, 225, 8550, 37488, 19272;
  ...

Wikipedia, Boolean matrix

Columns k = 0 and 1 give A000012, A060867.
Row sums give A002416.
Cf. A048651, A064230, A286331, A355333.

Table[B = Tuples[Tuples[{0, 1}, nn],nn]; bospan[matrix_]:= Sort[DeleteDuplicates[
     Map[Clip[Total[#]] &, Drop[Subsets[matrix], 1]]]]; rowrank[matrix_] :=
   If[Total[Map[Total, matrix]] == 0, 0, Length[Select[Drop[Subsets[DeleteCases[matrix, Table[0, {nn}]]], 1],
       bospan[#] == bospan[DeleteCases[matrix, Table[0, {nn}]]] &][[ 1]]]]; Tally[
    Table[rowrank[B[[i]]], {i, 1, 2^(nn^2)}]][[All,2]], {nn, 0, 4}] // Grid

T(n,0) = 1.
T(n,1) = (2^n-1)^2.
T(n,2) = (3^n - 2*2^n + 1)^2 + (1/2)*(4^n - 2*3^n + 2^n)^2.

Row n=5 from Pontus von Brömssen, Jul 14 2022

A355333 Triangle read by rows: T(n,k) is the number of n X n Boolean matrices with Schein rank k, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 9, 6, 1, 49, 306, 156, 1, 225, 8550, 40656, 16104, 1, 961, 194850, 5771100, 21165720, 6421800

Offset: 0

Pontus von Brömssen, Jun 29 2022

Also, T(n,k) is the number of spanning subgraphs of the complete bipartite graph K_{n,n} that have bipartite dimension (or biclique covering number) k.

			Triangle begins:
  n\k | 0   1      2       3        4       5
  ----+--------------------------------------
   0  | 1
   1  | 1   1
   2  | 1   9      6
   3  | 1  49    306     156
   4  | 1 225   8550   40656    16104
   5  | 1 961 194850 5771100 21165720 6421800

Mathematics Stack Exchange, Calculating the rank of a Boolean matrix and Boolean matrix factorization
Wikipedia, Bipartite dimension
Wikipedia, Boolean matrix

Cf. A002416 (row sums), A064230, A286331, A354741, A355334.

A173760 Partials sums of A000410.

Original entry on oeis.org

0, 0, 6, 431, 66056, 27960727, 35744362616, 144901919316449

Offset: 1

Jonathan Vos Post, Feb 23 2010

Partials sums of number of singular n X n rational (0,1)-matrices. The subsequence of primes in this partial sum begins: 431.

			a(8) = 0 + 0 + 6 + 425 + 65625 + 27894671 + 35716401889 + 144866174953833.

Cf. A000409, A000410, A046747, A064230, A064231.

a(n) = SUM[i=0..n] A000410(i).

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

A000410 Number of singular n X n rational (0,1)-matrices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A064231 Triangle read by rows: T(n,k) = number of rational (+1,-1) matrices of rank k (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI

Extensions

A086875 Sum of rank(M) over all n X n matrices over Z with all entries zero or one.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Formula

Extensions

A354741 Triangular array read by rows. T(n,k) is the number of n X n Boolean matrices with row rank k, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A355333 Triangle read by rows: T(n,k) is the number of n X n Boolean matrices with Schein rank k, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A173760 Partials sums of A000410.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula