Let $\alpha$ be a binary relation from $\gamma$ to $\chi$ and $\beta$ a binary relation from $\chi$ to $\rho$. If both $\alpha$ and $\beta$ are rectangular, i.e., they satisfy $\alpha \alpha^{-1} \alpha = \alpha$ and $\beta \beta^{-1} \beta = \beta$, then the composite relation $\gamma = \alpha \beta$ is also rectangular. On the other hand, if a relation is rectangular, then by Theorems 2 and 4 of Ref. 1, it admits a decomposition $\gamma = \alpha' \beta'$. Note that it is possible that $\alpha'\not=\alpha$ and $\beta'\not=\beta$. This decomposition can be obtained via the corresponding relation matrices via, e.g., the algorithm of Ref. 2.

Question: If $\alpha$ and $\beta$ are rectangular and $\gamma = \alpha \beta$, then is it true that, for any decomposition $\gamma = \alpha' \beta'$, $\alpha'$ and $\beta'$ are also rectangular?

I have the feeling that the answer should be affirmative, as I think it is implied by Theorem 7 in Ref. 3. I think it should hold for $n$-ary rectangular relations as well. Is there a way to (dis)prove this?


  1. A. Berman and R. J. Plemmons, Inverses of nonnegative matrices, Linear and Multilinear Algebra 2, 161-172 (1974) [link]

  2. S. L. Campbell and G. D. Poole, Computing nonnegative rank factorizations, Linear Algebra Applied 35, 175–182 (1981) [link]

  3. A. A. Bulatov and V. Dalmau, Information and Computation 205, 651-678 (2007) [link]



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.