= Solution
Start with $P_1=I\lor E$ and repeatedly apply part (b), keeping a fresh output <matrix>. A simple implementation is
``
P := I OR E
repeat:
Q := P OR boolean_product(P, E)
if Q = P: return P
P := Q
``
At the start of each iteration, $P=P_k$ for the current length bound $k$. The update produces $P_{k+1}$, proving the <loop invariant> by <mathematical induction>. If $Q=P$, every <edge> extension of a known <graph path> is already known. Repeating the same update then makes no further change, so every longer <graph path> is represented as well.
Every reachable pair of distinct <vertices> has a <simple path> of at most $n-1$ <edges>: a repeated <vertex> allows the intervening part to be deleted. Thus the process stabilizes after finitely many updates and returns
$$
\boxed{R[i,j]=\text{true precisely when }j\text{ is reachable from }i,\text{ including }i=j.}
$$
This is the <reflexive transitive closure>. An alternative stopping rule is to stop once the length bound is at least $n-1$, avoiding a final equality-detection iteration. For $n=0$ or $1$, $P_1$ already suffices.
Back to article page
