A Graph Adjacency Matrix's Necessary Condition for Representing Transitive Closure

Abstract

This work derives the necessary requirement for an adjacency matrix of a directed graph to represent its transitive closure. Hence, it allows computationally very efficient determination of whether a given graph may already represent its transitive closure. The requirement is derived from a new recursive matrix relation which leads to the determination of transitive closure for any directed graph. The transitive closure condition derived from it has the added benefit of creating a measure for how close an adjacency matrix is to its transitive closure. The proximity criterion allows estimating how many iterative steps of the recursive matrix relations are needed to find the transitive closure for a given graph. The current method provides a computational path to calculate the transitive closure that is substantially faster than the existing approaches when the number of repetitions is modest.