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!


  • $\begingroup$ Could you clarify what T3 means. It may be that your selection criterion for validity3 is not doing what you think it is. $\endgroup$
    – ubpdqn
    Jun 10 at 4:54

3 Answers 3


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];

So OP can check if expected results:

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

enter image description here

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.

  • $\begingroup$ Perfect! I really appreciate your patience. $\endgroup$
    – Jonathan
    Jun 11 at 7:47
  • $\begingroup$ Is this the correct way to find the square root? roots = MatrixPower[#, 1/2] & /@ r; $\endgroup$
    – Jonathan
    Jun 13 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]

graphic of matrices

If these are the intended T3 matrices then:

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

Note: all 21 of T3 matrices are transitive.

  • $\begingroup$ This suggests you code to select T3 is wrong and as expressed before Daniel Huber answer remains correct. $\endgroup$
    – ubpdqn
    Jun 10 at 6:18
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – ubpdqn
    Jun 10 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – ubpdqn
    Jun 10 at 8:47
  • $\begingroup$ You are right! you have guessed it correctly. This is what T3 means $\endgroup$
    – Jonathan
    Jun 10 at 11:43

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

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]

  • $\begingroup$ Thats perfect now. I get the same numbers with the code suggested in another answer. $\endgroup$
    – Jonathan
    Jun 20 at 4:12
  • $\begingroup$ Now How can we find the number of the square matrices of the these TBMs? $\endgroup$
    – Jonathan
    Jun 20 at 4:13
  • $\begingroup$ Why weakly transitive? $\endgroup$
    – Jonathan
    Jun 20 at 4:21
  • $\begingroup$ @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 $\endgroup$ Jun 20 at 4:24
  • $\begingroup$ My sincere apologies for my lose language. The actual defintion is "if and only if". $\endgroup$
    – Jonathan
    Jun 20 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.