Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have graphs represented by matrices. For example,

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

Produces this graph:

enter image description here

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.

share|improve this question
4  
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

1 Answer 1

up vote 1 down vote accepted

To not leave this question unanswered, I repeat the correct solution given by Henning Makholm in the commentary:

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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