** Boolean Matrix Representation of Graph**

A relation * R * or graph on a finite set can be expressed as a boolean
matrix * M * where:

M[i, j] = 1iff(i, j) &isin R.

Multiplication of boolean matrices is done in the same way as ordinary
matrix multiplication, but using * &and * for * · * and
* &or * for * + * .

Property: | Matrix: |

Identity, R ^{0} | I (identity matrix) _{n} |

Inverse, R or ^{-1} &Gamma ^{-1} | M ^{T} |

Reflexive | I &sube M |

Symmetric | M = M ^{T} |

Transitive | M ^{2} &sube M |

Antisymmetric | M &cap M ^{T} &sube I_{n} |

Paths of length n | M ^{n} |

Transitive closure &Gamma ^{+} | &cup _{i=1}^{n} M^{i} |

Reflexive transitive closure &Gamma ^{*} | &cup _{i=0}^{n} M^{i} |

Example: Let the set * S * be basic blocks of a program and * &Gamma *
be transfers of control between blocks.