Malaysian Journal of Mathematical Sciences, March 2026, Vol. 20, No. 1
Properties of Max-Plus Algebraic Determinants Derived from Duality Theorem
Nishida, Y., Watanabe, S., and Watanabe, Y.
Corresponding Email: y-nishida@kpu.ac.jp
Received date: 7 May 2025
Accepted date: 9 July 2025
Abstract:
Max-plus algebra is a semiring with two operations: addition $\oplus:= \max$ and multiplication $\otimes:= +$.
The definition of the max-plus algebraic determinant is equivalent to the assignment problem on a bipartite graph.
%This study presents a new expression of the max-plus algebraic determinant.
Since the assignment problem has a formulation as linear programming, the duality theorem induces the minimization problem that attains the same optimal value as the assignment problem. We translate this dual problem in terms of max-plus algebraic operation and obtain another expression for the max-plus algebraic determinant.
For the determinant of the product of max-plus square matrices, we have only the inequality $\det (P \otimes Q) \geq \det P \otimes \det Q$, and a known sufficient condition for the equality is given by the condition for $\det (P \otimes Q)$. Exploiting the duality theorem for the determinant, we derive a necessary and sufficient condition for the equality. Our criterion only needs the optimal assignments corresponding to $\det P$ and $\det Q$ but does not require to compute $\det (P \otimes Q)$ beforehand.
Keywords: max-plus algebra; duality theorem; tropical semiring; determinant.
