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] = 1 iff (i, j) ∈ R .
Multiplication of boolean matrices is done in the same way as ordinary matrix multiplication, but using ∧ for · and ∨ for + .
|Identity, R0||In (identity matrix)|
|Inverse, R-1 or Γ-1||MT|
|Reflexive||I ⊆ M|
|Symmetric||M = MT|
|Transitive||M2 ⊆ M|
|Antisymmetric||M ∩ MT ⊆ In|
|Paths of length n||Mn|
|Transitive closure Γ+||∪i=1n Mi|
|Reflexive transitive closure Γ*||∪i=0n Mi|
Example: Let the set S be basic blocks of a program and Γ be transfers of control between blocks.