A286331 -id:A286331 - cp's OEIS frontend

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.

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.

A322556 The number of eigenvectors with eigenvalue 1 summed over all linear operators on the vector space GF(2)^n.

Original entry on oeis.org

0, 1, 12, 448, 61440, 32505856, 67645734912, 558551906910208, 18374686479671623680, 2413129272746388704198656, 1266412660188944021221804081152, 2657157917355198038900481496478384128, 22295300680659888126120304278929453214597120

Offset: 0

Geoffrey Critzer, Aug 28 2019

nonn

Generally, for any prime power q, the total number of eigenvectors corresponding to any element lambda in the field GF(q) summed over all operators on GF(q)^n is equal to (q^n-1)*q^(n^2-n).

Cf. A286331.

Map[Total,Table[Table[(q^(n - k) - 1) Product[(q^n - q^i)^2/(q^k - q^i), {i, 0,k - 1}] /. q -> 2, {k, 0, n}], {n, 0, 11}]]

a(n) = (2^n-1)*2^(n^2-n).

A333329 Number of winnable configurations in Lights Out game (played on a digraph) summed over every labeled digraph on n nodes.

Original entry on oeis.org

1, 3, 43, 2619, 654811, 662827803, 2699483026843, 44102911693372059, 2886238576935227688091, 756075355087132847491422363, 792522435884210281153847457333403, 3323493099535510709729189614466101940379, 55754039618636998102358059592995073452269940891

Offset: 0

Geoffrey Critzer, Mar 15 2020

nonn

Here a digraph may have at most one self loop (cf. A002416). A winnable configuration is a subset of lit vertices that can be turned off by some toggling sequence. In this version of the game, the digraph D is not necessarily symmetric so that the number of winnable configurations is 2^rank(A^t) where A^t is the transpose of the adjacency matrix of D.

In the limit as n goes to infinity, the probability that a random configuration on a random digraph is winnable is: Sum_{j>=0} (1/2^j) * (Product_{i>=j+1} (1-2^i))/(Product_{i>=1} (2^i - 2^(j-i))) = 0.610321...

A. Giffen and D. Parker, On Generalizing the Lights Out Game and a Generalization of Parity Domination, 2009.
L. Keough and D. Parker, An Extremal Problem for the Neighborhood Lights Out Game, arXiv:1908.03649 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Lights Out Puzzle

Table[Table[2^k*Product[(2^n - 2^i)^2 /(2^k - 2^i), {i, 0, k - 1}], {k, 0, n}] // Total, {n, 0, 12}]

a(n) = Sum_{k=0..n} A286331(n,k)*2^k.

a(n) ~ c * 2^(n*(n+1)), where c = 0.610321518048266425924048782090628564983520109965690835927574616905934... - Vaclav Kotesovec, Apr 07 2020

A379105 Triangular array read by rows. T(n,k) is the number of n X n matrices T over GF(2) such that there are exactly 2^k vectors v in GF(2)^n with Tv=v, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 6, 9, 1, 168, 294, 49, 1, 20160, 37800, 7350, 225, 1, 9999360, 19373760, 4036200, 144150, 961, 1, 20158709760, 39687459840, 8543828160, 326932200, 2542806, 3969, 1, 163849992929280, 325139829719040, 71124337751040, 2812314375360, 23435953128, 42677334, 16129, 1

Offset: 0

Geoffrey Critzer, Dec 15 2024

Sum_{k=0..n} T(n,k)*2^k = (2^(n+1)-1)*2^(n^2-n) so that as n->oo the average number of fixed points is 2.

T(n,k) is also the number of n X n matrices over GF(2) with nullity k. As n->oo, the probability that a random n X n matrix over GF(q) has nullity k is 1/|GL_k(F_q)|*Product_{i>=k+1} (1 - 1/q^i). - Geoffrey Critzer, Dec 31 2024

			Triangle T(n,k) begins:
        1;
        1,        1;
        6,        9,       1;
      168,      294,      49,      1;
    20160,    37800,    7350,    225,   1;
  9999360, 19373760, 4036200, 144150, 961, 1;
  ...

Cf. A060867 (T(n,n-1)), A002884 (column k=0), A086699 (column k=1), A346381, A286331.

Row sums give A002416.

nn = 5; b[p_, i_] := Count[p, i];d[p_, i_] := Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}];aut[deg_, p_] :=Product[Product[q^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}]; \[Nu] = Table[1/n Sum[MoebiusMu[n/d] q^d, {d, Divisors[n]}], {n, 1, nn}]; L=Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]; g[u_, v_, deg_] :=  Total[Map[v^Length[#] u^(deg Total[#])/aut[deg, #] &, L]]; Map[Select[#, # > 0 &] &,  Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0,nn}] CoefficientList[Series[g[u, 1, 1] g[u, v, 1] Product[g[u, 1, deg]^\[Nu][[deg]], {deg, 2, nn}], {u, 0, nn}], {u,v}]] // Grid

T(n,k)=Product_{j=0..n-k-1} (2^n - 2^j)^2/(2^(n-k)-2^j). - Geoffrey Critzer, Dec 31 2024

cp's OEIS Frontend

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

A322556 The number of eigenvectors with eigenvalue 1 summed over all linear operators on the vector space GF(2)^n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A333329 Number of winnable configurations in Lights Out game (played on a digraph) summed over every labeled digraph on n nodes.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A379105 Triangular array read by rows. T(n,k) is the number of n X n matrices T over GF(2) such that there are exactly 2^k vectors v in GF(2)^n with Tv=v, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula