Necessary and Sufficient Conditions for the Existence of Local Matrix Decompositions
Paul Gader · SIAM Journal on Matrix Analysis and Applications · 1988
Let $D = ( V,E )$ be a directed graph with n vertices. We define the notion of a local matrix with respect to D and we show that every $n \times n$ matrix, over the real or complex numbers, can be factored into a product of local matrices with respect to D if and only if D is strongly connected and contains all loops. We discuss the significance of this result with respect to parallel computation of linear transforms on SIMD processor arrays. We observe that the result can be used to associate with certain irreducible $n \times n$ matrices a generating set of the semigroup of all $n \times n$ matrices under matrix multiplication.