Decomposition has been studied in the context of linear algebra.
A matrix decomposition or matrix factorization is a factorization of a matrix
into a product of matrices. There are many different matrix factorizations.
Certain Boolean matrix-factorization problems are known to be NP-complete
[1]}. Our NP-completeness result for explicit relations can be
viewed as a special case of Boolean matrix-factorization. In addition, our formulation for the explicit case can be viewed as a reformulation of the combinatorial definition of the nondeterministic communication complexity (see Chapters 1-2 in [2]}). In that sense, this paper extends these works to more general representations of relations.
