Page 314 Exercise 20

The equation in the text is a simple application of boolean algebra.  Recall that A refers to the original matrix, and A^* to the matrix that places a 1 in position_i,j, if there is a simple path from i to j, and a 0 otherwise.  A + differs from A^* only in the treatment of the diagonals.  A⁺ will have a 1 in a diagonal only if there is a simple cycle for the diagonal. 

The equation states that a simple cycle exists, if there is a path from i back to itself through any intervening vertices.  The 'and' indicates that there must be a path from i back to itself.  The 'or' indicates that we only need to find one path.

For example, using Figure 6.354 (a) from the text, the following application of the equation determines if there is a simple cycle from <0,0>:

<0,0> ∧ <0,0> ∨ <0,1> ∧ <1,0> ∨ <0,2> ∧ <2,0> ∨ <0,3> ∧ <3,0> &or <0,4> ∧ <4,0>

→ (0 ∧ 1) ∨ (1 ∧ 0) ∨ (1 ∧ 0) ∨ (1 ∧ 0) ∨ (1 ∧ 0)

→  0 ∨ 0 ∨ 0 ∨ 0 ∨ 0

→  0

Since the result is zero, there is no simple cycle from 0 to 0.