Theorem 1 from section 43 states MR MR MR2 so that MR MR sh

Theorem 1 from section 4.3 states M_R M_R = M_R^2, so that M_R M_R shows whore there are paths of length 2 in the digraph of R. Describe and show what M_R M_R would produce. Use your finding to explain (M_R)^n. Look over your fellow classmates work and discuss differences in your approaches.

Solution

Suppose that R is a relation on a set A.

A path of length n in R from a to b is a finite sequence : a, x1, x2, ....., xn1, b, beginning with a and ending b, such that aRx1, x1Rx2, ......., xn1Rb. A path that begins and ends at the same vertex is called a cycle.

If we have aRb and bRc then there exists a path of length two from a to b and it is represented by aR2 b.

We have MR² = MR MR where MR is the matrix for relation R and MR² for R2 .

We have the following relations: Rⁿ means a path of length n exists in R

R means there is some path in R. R = R R² R³ .......Rⁿ¹

MR = MR MR² MR³ ........ The reachability relation R of a relation R on a set A that has n elements is

defined as follows: xRy means that x = y or x Ry. It is seen that

MR = MR I_n, where I_n is the identity matrix.