Finding transitive Boolean matrices

Question

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!

---

Answer 1

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

Answer 2

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.

Answer 3

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