How to visually check the transitivity of a (large) relation matrix by hand?

Question

Let's say we're given a relatively large relation matrix like:

$$\begin{pmatrix} 0&1&0&1 \\ 1&0&0&1 \\ 1&1&0&1 \\ 0&0&0&0 \end{pmatrix}$$

Matrices can be as large as 10x10 or higher but only 2D. Checking reflexivity is simply checking for the $a_{ii} = 1$ diagonal. Symmetry can easily be checked by pairing elements one by one. I'd like to avoid having to draw out the arrowed graph since the matrix can get really complex. Calculators and computers are not allowed and this must be done by hand so iterative methods that tend to rely on computers are less desired.

Is there a way to visually check the transitivity of the matrix by hand? (Please include a visual representation of your method(s))

Answer 1

If $a_{ij} = 1$, you want to check that $a_{ik} \ge a_{jk}$ for all $k$, i.e. the $i$'th row is elementwise greater than or equal to the $j$'th row. In your example, $a_{12} = 1$ but row $1$ is not greater than or equal to row $2$ because $a_{11} = 0$ but $a_{21} = 1$, so this is not transitive.

Answer 2

For every entry $a_{ij} = 0$ that appears in the matrix, take the dot product of the column and row that intersect there. The matrix represents a transitive relation if and only if all these dot products are zero.

Alternatively, for an $n \times n$ matrix, compute $nA - A^2$. The relation represented by $A$ is transitive if and only if all the entries are nonnegative.