Structure of the eigenspace of a Monge matrix in max-plus algebra
Matrix computations using maximum and minimum operations have been considered by many authors in optimization problems. The steady states of discrete events processes correspond to eigenvectors of max-plus matrices, so the characterization of the eigenspace structure is important for the applications purposes. Let \(G=\mathbb R\cup\left\{-\infty\right\}\), where \(\mathbb R\) is the set of real numbers. Let \(\oplus\) be the maximum binary operation on \(G\) and \(\otimes\) be the usual addition operation on \(G\). (The infinite element is neutral with respect to the maximum operation and absorbing with respect to the addition). Then \(\left(G,\oplus,\otimes\right)\) is a max-plus algebra. For any natural number \({n}>{0}\) let \(N=\left\{1,2,3,\dots,n\right\}\), and Let \(G_{n}\) be the set of all \({n}\times{n}\) matrices over \(G\). A matrix \(A=(a_{ij})\in{G_{n}}\) is called a Monge matrix if \[ a_{ij}+a_{kl}\leq a_{il}+a_{kj},\quad\text{for all}\;{i}<{k}, {j}<{l}. \] The authors describe the structure of the eigenspace of a Monge matrix in detail. They use some well known techniques to compute the equivalence classes connected with cycles of the zero weight in the associated digraph of the given Monge matrix. They present an algorithm, which can be done in \(O(n^{2})\) time, or with some additional conditions in \(O(n)\) time, to compute and describe completely the structure of the eigenspace and the eigenspace dimension. The paper contains some research ideas for interested researchers.
- Structure and dimension of the eigenspace of a concave Monge matrix
- Special properties of Monge matrices in max-plus algebra
- Controllable and tolerable generalized eigenvectors of interval max-plus matrices.
- Computing an eigenvector of a Monge matrix in max-plus algebra
- An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
- A characterization of the minimum cycle mean in a digraph
- A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
- An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
- Combinatorial matrix theory
- Computing an eigenvector of a Monge matrix in max-plus algebra
- Eigenvalues of dynamic max-min systems
- scientific article; zbMATH DE number 3708436 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 5018129 (Why is no real title available?)
- Linear and combinatorial optimization in ordered algebraic structures
- Minimax algebra
- Perspectives of Monge properties in optimization
- Structure and dimension of the eigenspace of a concave Monge matrix
- Monotone eigenspace structure in max-min algebra
- An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
- On integer eigenvectors and subeigenvectors in the max-plus algebra
- Computing an eigenvector of a Monge matrix in max-plus algebra
- Special properties of Monge matrices in max-plus algebra
- Eigenproblem for optimal-node matrices in max-plus algebra
- Eigenproblems of Latin squares in bipartite \((\min, \max,+)\)-systems
- Eigenspace of a max-drast matrix over ${I^2}$
- A min-plus analogue of the Jordan canonical form associated with the basis of the generalized eigenspace
- Computing an eigenvector of an inverse Monge matrix in max-plus algebra
- Dominant matrices and max algebra
- Max-plus definite matrix closures and their eigenspaces
This page was built for publication: Structure of the eigenspace of a Monge matrix in max-plus algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476248)
