# Validity of the number of transitive matrices

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.

Thanks

• Could you clarify what T3 means. It may be that your selection criterion for validity3 is not doing what you think it is. Commented Jun 10, 2023 at 4:54

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.

• Perfect! I really appreciate your patience. Commented Jun 11, 2023 at 7:47
• Is this the correct way to find the square root? roots = MatrixPower[#, 1/2] & /@ r; Commented Jun 13, 2023 at 23:55

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.

• This suggests you code to select T3 is wrong and as expressed before Daniel Huber answer remains correct. Commented Jun 10, 2023 at 6:18
• You are copying verbatim what you write. That is not a clarification. It is a verbatim restatement. Your first comment suggest the desired matrices to be tested were selected by func (my function). Applying checkTrans to this is correct with respect to your T3. This suggests your code is wrong. Finally, the reason larger cases will be problematic is size of space becomes intractable. I am not sure what your ultimate aim is but it is likely to need mathematical insights with or without clever algorithms to count cases. Good luck :) Commented Jun 10, 2023 at 8:36
• I just want to express it is ok to be wrong. My code to the original question was wrong. I deleted it to not mislead and I learned something. Where I think your error is occurs in validityMatrices3: where you try to select the T3 cases. The more you play with Mathematica you will gain insights into it and your problem. Commented Jun 10, 2023 at 8:47
• You are right! you have guessed it correctly. This is what T3 means Commented Jun 10, 2023 at 11:43

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]

`
• Thats perfect now. I get the same numbers with the code suggested in another answer. Commented Jun 20, 2023 at 4:12
• Now How can we find the number of the square matrices of the these TBMs? Commented Jun 20, 2023 at 4:13
• Why weakly transitive? Commented Jun 20, 2023 at 4:21
• @Jonathan I see people use "transitive" to mean if-and-only-if, in which case there are 11 such 2x2 matrices. Your definition only has the "if" part, so we get 13 such 2x2 matrices. Hence, I'm calling your definition "weakly transitive" to differentiate Commented Jun 20, 2023 at 4:24
• My sincere apologies for my lose language. The actual defintion is "if and only if". Commented Jun 20, 2023 at 4:27