Validity of the number of transitive matrices

Question

I am trying to generate all possible transitive boolean matrices of order nxn which satisfies the following definition of transitivity

Let A=(a_ij)∈M_n(B) be a non-zero matrix. If for any i,j,k in I_n, where I_n={1,2,⋯,n}, when a_ij=a_jk=1 ，we have a_ik=1, then A is said to be transitive. and A is transitive if and only if A^2≤A.

The code I am adopting from here to extend it to nxn,

checkTrans[m1_] := Module[{m2}, m2 = m1 . m1; m1 m2 == m2]

To check the validity I am using the following

 T1[n_] := n*(n - 1)^3 + 1/6*n*(n - 1)^4*(n - 2) + 
  1/6*n*(n - 1)*(n - 2)*(4*n - 1)
T2[n_] := 1/2*n*(n - 1)*(n^2 - n + 3)
T3[n_] := n*(2^n - 1)

T1 validity test works for only those transitive boolean matrices which has 3 nonzero elements. For example in 3x3 there are 43 transitive matrices, for 4x4 there are 276 having only 3 nonzero elements.

T2 test works for the number of n × n transitive Boolean matrices with two nonzero elements.

T3 denotes the number of transitive Boolean matrices with 1 non-0 columns in the Boolean matrices of nxn

     n = 3; (*martix order*)
    
    ms = IntegerDigits[#, 2, n^2] & /@ Range[0, 2^(n^2) - 1];
    ms = ArrayReshape[#, {n, n}] & /@ ms;
    
    validMatrices = 
      Select[ms, Count[Flatten[#], 1] == 3 && checkTrans[#] &];
    validity = Length[validMatrices] == T1[n];
    
    validMatrices2 = 
      Select[ms, Count[Flatten[#], 1] == 2 && checkTrans[#] &];
    validity2 = Length[validMatrices2] == T2[n];
    func[x_] := 
 Length[Union[SparseArray[x]["NonzeroPositions"][[All, 2]]]] == 1
    validMatrices3 = Select[ms, func];
    validity3 = Length[Select[validMatrices3, checkTrans]] == T3[n];
    
    {validity, validity2, validity3}

{True, True, True}

(validity3 fails. I am trying to make sure, that the number of all the possible transitive matrices generated by checkTrans are accurate.) @ubpdqn helped to solve this issue.

The remaining issues are

Is this the correct way to find the numbers of transitive Boolean matrices in nxn boolean matrices with 4 non-zero elements in each transitive Boolean matrix?

Select[ms, Total[Flatten[#]] == 4 && checkTrans[#] &];

Finally, this code takes ages for 5x5.

Please have a look!

Thanks

Answer 1

This answer relates to the second part regarding 4 non-zero entries in n xn matrix.

Select[ms, Total[Flatten[#]] == 4 && checkTrans[#] &];

does do this but falters as n increases (size 2^(n^2)).

A first approach would be to just deal with the matrices of interest. For example (this is some code I had written earlier):

tst[m_] := With[{s = m . m}, s m == s]
numz[n_, nz_] := 
 Module[{sel = 
    ArrayReshape[#, {n, n}] & /@ (Permutations[
       ArrayPad[ConstantArray[1, nz], {0, n^2 - nz}]]), r},
  r = Select[sel, tst];
  Length[r]]

So OP can check if expected results:

TableForm[
 Table[{Row[{j, "x", j}], numz[j, 4], Multinomial[j^2 - 4, 4]}, {j, 3,
    7}]]

The first column is matrix dimensions, the second column the number of transitive matrices, the last column the number of matrices with 4 non-zero entries.

Answer 2

This is a long comment seeking to clarify the meaning of T3.

A criterion to select T3 (an interpretation):

 func[x_] := 
 Length[Union[SparseArray[x]["NonzeroPositions"][[All, 2]]]]== 1 

Selecting T3 matrices:

  a = Select[ms, func]

Showing these matrices for OP to see if this is what T3 means:

Grid[Partition[MatrixForm /@ a, 3]

If these are the intended T3 matrices then:

Length[Select[a, checkTrans]] == T3[3] yields True.

Note: all 21 of T3 matrices are transitive.

Answer 3

You can use SatisfiabilityCount for this task, the counts are $\{2, 13, 171, 3994, 154303, 9415189,878222530\}$, appearing to follow A006905

Clear["Global`*"];
booleanMatmul[mat1_, mat2_] := 
  Array[Inner[And, mat1[[#1, ;;]], mat2[[;; , #2]], Or] &, {Length[
     mat1], Length[mat2]}];
booleanEquals[mat1_, mat2_] := 
  And @@ Flatten@MapThread[Xnor, {mat1, mat2}, 2];
booleanGreaterEqual[mat1_, mat2_] := 
  And @@ Flatten@MapThread[Or[#1, Not[#2]] &, {mat1, mat2}, 2];

countWeaklyTransitive[d_] := (
   mat = Array[x, {d, d}];
   mat2 = booleanMatmul[mat, mat];
   SatisfiabilityCount[booleanGreaterEqual[mat2, mat], Flatten[mat]]
   );
countWeaklyTransitive /@ Range[5]