# Transitive reduction: calculating “relation composition” of matrices?

I have graphs represented by matrices. For example,

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

Produces this graph:

The graphs are supposed to be transitive, i.e. the edge from A to C is redundant and should be removed.

From the Wikipedia Transitive Reduction page, the transitive reduction of a graph can be computed as follows:

$R^- = R - (R \circ R^+)$

Where $R^-$ is the transitive reduction, $R^+$ is the transitive closure of the matrix and $\circ$ denotes relation composition.

I have written algorithms to compute subtraction and the transitive closure of a matrix, but I'm having trouble understanding relation composition. My knowledge of set theory is pretty minimal and the notation on the Wikipedia page is beyond me.

All of the examples I've found seem to deal with sets of ordered pairs, and I'm wondering if anyone could recommend resources or give a brief outline of how to compute relation composition of two matrices.

-
That's easy: Just multiply the two matrices (I suppose you know matrix multiplication?), and then replace all nonzero elements of the result by $1$s. – Henning Makholm Feb 25 '12 at 21:45
@Henning Makholm Not quite. In the matrix above, the transitive closure of R is the same as R. so R-(R o R+) = R-R = zero matrix – waitinforatrain Feb 25 '12 at 22:18
Just because $R^+=R$ doesn't mean that $R\circ R=R$. The matrix product of $R$ by itself is different from $R$! – Henning Makholm Feb 25 '12 at 22:22
@Henning Makholm Ah yes, the issue was that my matrices have 1s across the diagonal. Thanks for your help. If you submit it as an answer I'll accept it. – waitinforatrain Feb 25 '12 at 22:43

If $A$ and $B$ are relation matrices, the matrix of the composed relation can be computed by matrix multiplication $A\cdot B$ and then setting all non-zero entries of the product to $1$.