# Finding transitive Boolean matrices

I am fairly new here and with Mathematica too. I have a question regarding Boolean matrices but before this I did a random search and got this Defining an arbitrary binary relation

But I am unable to modify the code to get the desired results.

I am hoping to generate 3 × 3 Boolean matrices, there are 2^9 of them, and I need to know how many of those 2 ^ 9 Boolean matrices are transitive.

Can someone please put me in the right direction?

Thanks

Edit:

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.

Futhermore

A is transitive if and only if A^2≤A.

We can set a check on the validity by using the following

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


This works for only those 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.

Edit 2.

I got quick and very positive responses here, which I really appreciate. I have tried to adopt the answers but due to my lack of basic understanding of Mathematica, I am unable to get the desired results. here is what I am looking for

1. How to manange a code which can easily work for higher orders such is 3X3, 4X4, 5X5, 6X6?
2. I would like to incorporate all the matrices which satisfies the above two definitions more specificly A^2<=A
3. I would like to see the complete list of the transitive matrices that I can verify them manually If I had to.
4. It would be more helpful if the code includes verfication test as I have mentioned above.

I know I am asking for too much but this work if done manually is beyond my abilities.

Looking forward to your kind replies!

• Do you have a test for transitivity? Use it on ArrayReshape[#, {3, 3}] & /@ Tuples[{0, 1}, 9];.
– Syed
Commented Jun 6, 2023 at 7:37
• A relevant post from MathSE.
– Syed
Commented Jun 6, 2023 at 7:49
• trQ[k_?MatrixQ] := Unitize@MatrixPower[k, 2] == k and (res = Select[ArrayReshape[#, {3, 3}] & /@ Tuples[{0, 1}, 9], trQ]) // Length gives me 123. Am I wrong in using MatrixPower instead of Dot?
– Syed
Commented Jun 6, 2023 at 11:12
• @Syed some non zero base matrix have square that is zero matrix. Further, some with 1 in base matrix can have zero in same position in square and still be counted as transitive. The condition is if two step path then there is edge in base matrix . If there is no two step path there may or may not be an edge in base matrix. Daniel Huber answer deals with this. Commented Jun 6, 2023 at 21:25
• @Syed I have updated the question and included the transitivity test. Please have a look. Commented Jun 7, 2023 at 7:01

A matrix m1 can be check for transitivity by:

• Dot multiply m1 with itself and set every element >1 to 1. This can be achieved by:

m2= m1.m1 /. x_ /; x > 1 -> 1

• Check if for each element of m2 that is 1, the corresponding element of m1 is also 1. This can be achieved by element wise multiplication of m1 and m2:

m1 m2 == m2

Here is an example:

SeedRandom[1];
m1 = RandomInteger[{0, 1}, {3, 3}]
m2 = m1 . m1 /. x_ /; x > 1 -> 1
m1 m2 == m2

False


Or:

SeedRandom[5];
m1 = RandomInteger[{0, 1}, {3, 3}]
m2 = m1 . m1 /. x_ /; x > 1 -> 1
m1 m2 == m2

True


If you now want to count which 3x3 boolean matrices are transitive, you may first create these 512 matrices. That can be done by noting that the flatten matrices are the numbers from 0..511 in binary notation. Then, having a list of digits, you can reshape them into a matrix and finally check the matrix. For the check we define a small function:

checkTrans[m1_] := Module[{m2},
m2 = m1 . m1;
m1 m2 == m2
]
ms = IntegerDigits[#, 2, 9] & /@ Range[0, 511];
ms = ArrayReshape[#, {3, 3}] & /@ ms;
Count[checkTrans /@ ms, True]

171

• Thanks for your input. But the problem is that I have to check it for all 512 matrices...here is all 512 matrices and how can I call them at once to check its transitivity. Clear[boolmat] boolmat[n_Integer /; n > 0] := Tuples[{0, 1}, {n, n}] MatrixForm /@ boolmat[3] Commented Jun 6, 2023 at 7:46
• Knowing how to check for transitivity, it is not difficult to count the 3x3 boolean transitive matrices. I added this to my answer. Commented Jun 6, 2023 at 10:35
• How to see all those 63 of them, just to verify? Commented Jun 6, 2023 at 10:37
• Use Select[ms, checkTrans] @Jonathan Commented Jun 6, 2023 at 10:38
• @DanielHuber in your update answer you don’t Unitise the squared matrix (as you did in original). Any >1 two step paths in your component wise multiplication will not pass your test though from link they should, eg one of examples in link. Commented Jun 6, 2023 at 10:42

The easiest way to generate random boolean matrices, is like this:

(* Generate 1 random 3x3 matrix *)
RandomChoice[{True, False}, {3, 3}]

(* Generate 10 of them *)
RandomChoice[{True, False}, {10, 3, 3}]


Use {0, 1} instead of {True, False} if you want numbers instead of boolean values.

This answer is based on the updated question. Selecting only matrices with 3 non-zero entries and looking for transitivity.

I use the test of Daniel Huber (who I have voted for).

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


Testing for 3x3 to 7x7 matrices:

  TableForm[Table[{Row[{j, "x", j}], num3[j]}, {j, 3, 7}]]


• Once again thanks for your efforts. I think you misunderstood me. I am looking for all the transitive matrices out of 512. The 3 nonzero elements matrices are just a validity test. Commented Jun 7, 2023 at 7:44
• I have corrected my error Commented Jun 7, 2023 at 7:44
• Daniel Huber answer works (IMHO) and passes your vailidiity check with 3 non-zero entries. My reply was too long for a comment. Commented Jun 7, 2023 at 7:46
• How can I display the full list and the total number of the transitive matrices? Commented Jun 7, 2023 at 7:49
• Does this includes all the matrices which satisfies the condition A^2<=A? Commented Jun 7, 2023 at 7:50