Permanents, max algebra and optimal assignment

DOI10.1016/0024-3795(95)00304-AMaRDI QIDQ1899397zbMATH OpenFDO

Authors R. B. Bapat

Publication date 9 November 1995

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(95)00304-A

zbMATH Keywords

max algebranonnegative matrixoptimal assignmentpermanent

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Algebraic systems of matrices (15A30) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

The max algebra consists of the set \({\mathcal M}= \mathbb{R} \cup \{-\infty\}\) equipped with two binary operations, \(a \oplus b = \max (a,b)\) (addition in \(\mathcal M\)) and \(a \otimes b = a + b\) (multiplication in \(\mathcal M\)). For a square matrix, its permanent over \(({\mathcal M}, \oplus, \otimes)\) is simply the maximum diagonal sum of the matrix. Several results are proved for the permanent over the max algebra \(\mathcal M\), which are analogues of classical results for the permanent of a nonnegative matrix.

Recommendations

• Max algebra and the linear assignment problem
• MAX algebraic complementary basic matrices
• scientific article; zbMATH DE number 2221681
• Max-algebra: The linear algebra of combinatorics?

Cites work

• A Note on a Generalization of Boolean Matrix Theory
• Combinatorial matrix theory
• Cramer and Cayley-Hamilton in the max algebra
• Distance matrices and Lorentz space
• scientific article; zbMATH DE number 3887877 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 3185418 (Why is no real title available?)
• Inversion of matrices over a commutative semiring
• Minimax algebra
• Multinomial Probabilities, Permanents and a Conjecture of Karlin and Rinott
• Notes on Egoritsjev's proof of the van der Waerden conjecture
• On permanents and the zeros of rook polynomials
• On the evaluation of permanents
• Permanents
• Problems in algebraic combinatorics
• Study of the permanent conjecture and some of its generalizations

Cited in

(13)

• Cramer and Cayley-Hamilton in the max algebra
• A max version of the Perron-Frobenius theorem
• Finding all essential terms of a characteristic maxpolynomial.
• Max algebra and the linear assignment problem
• Max-algebra: The linear algebra of combinatorics?
• MAX algebraic complementary basic matrices
• On the coefficients of the max-algebraic characteristic polynomial and equation
• \(P_{\max}^1\) and \(S_{\max}\) properties and asymptotic stability in the max algebra
• Calculating essential terms of a characteristic maxpolynomial
• Dominant matrices and max algebra
• Characterization and algorithm for max-plus supereigenvector problem by parametric programming
• A note on Erdős matrices and Marcus-Ree inequality
• Properties of max-plus algebraic determinants derived from duality theorem

This page was built for publication: Permanents, max algebra and optimal assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899397)