Comparison of the quasi-inverses of the Kronecker sum and product of matrices over complete commutative dioids with applications

We compare the quasi-inverses of the Kronecker sum ⊞ and product ⊠ of two given square matrices A and B  , with entries from an idempotent, complete and commutative dioid. We prove that (A⊞B)⁎(A⊞B)⁎ is greater than or equal to (A⊠B)⁎(A⊠B)⁎ in the sense of the canonical order, where ⁎⁎ denotes the quasi-inverse. We also show how to reduce the computational complexity of computing (A⊞B)⁎(A⊞B)⁎ from sixtic to quartic order. Moreover, we propose three applications of our results. First, we compare solutions to fixed-point type matrix equations X=A⊗X⊗B⊕CX=A⊗X⊗B⊕C and X=A⊗X⊕X⊗B⊕CX=A⊗X⊕X⊗B⊕C over any complete commutative dioid. It is also possible to compare the connections between vertices in the corresponding graphs G(A⊞B)G(A⊞B) and G(A⊠B)G(A⊠B) over the Boolean dioid. Finally, we show that the lengths of the shortest paths in the aforementioned graphs are equal using the tropical dioid.