Boolean product

[standelds]

The question is:
Let R be the relation given by the matrix:

[ 0 0 1 ]
M = [ 0 1 1 ]
[ 1 0 0 ]

Find the matrix M(sub)R^2, i.e. compute the Boolean product of the matrix
with itself. Use the matrix to determine the number of paths of length 2 in
relation R.

So far I have:

[ 1 0 0 ]
M(sub)R^2 = [ 1 1 1 ]
[ 1 0 0 ]

and from what I think I understand of graph theory this means there are 5
paths of length 2 in relation R.

Is this correct? If not correct, please help me understand my errors.

Thank you for the time.
Dustin

[Brian M. Scott]

On Sun, 10 Sep 2006 03:35:00 GMT, standelds

Post by standelds
[ 0 0 1 ]
M = [ 0 1 1 ]
[ 1 0 0 ]
Find the matrix M(sub)R^2,

In the usual ASCII notation that's (M_R)^2.

Post by standelds
i.e. compute the Boolean product of the matrix with
itself. Use the matrix to determine the number of paths
of length 2 in relation R.
[ 1 0 0 ]
M(sub)R^2 = [ 1 1 1 ]
[ 1 0 0 ]

I believe that your last row is backwards: it should be
[0 0 1].

Post by standelds
and from what I think I understand of graph theory this
means there are 5 paths of length 2 in relation R.

Not quite. The ordinary product counts the paths; the
Boolean product merely tells you between which pairs of
vertices paths of length 2 exist, but not how many. In this
case the two happen to be the same, but suppose that the
second row of M had been [1 1 1]: then the ordinary
product would have had a 2 in the (2, 3) position, while the
Boolean product would still have had a 1. In that case
there are 2 paths of length 2 from the 2nd vertex to the
3rd, v_2 to v_1 to v_3, and v_2 to v_2 to v_3, but the
Boolean product merely tells you that one exists.

[...]

Brian