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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.