Properties of Max-Plus Algebraic Determinants Derived from Duality Theorem

Max-plus algebra is a semiring with two operations: addition ⊕:=max and multiplication ⊗:=+ . 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⊗Q)≥detP⊗detQ , and a known sufficient condition for the equality is given by the condition for det(P⊗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 detP and detQ but does not require to compute det(P⊗Q) beforehand.