On the coefficients of the max-algebraic characteristic polynomial and equation

Peter Butkovič

Kybernetika (2003)

  • Volume: 39, Issue: 2, page [129]-136
  • ISSN: 0023-5954

Abstract

top
No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and characteristic equation of a matrix in max- algebra. The following are proved: (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a { 0 , - ∞ } matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a { 0 , - ∞ } matrix can be converted to that of finding the conventional characteristic equation for a { 0 , 1 } matrix and thus it is solvable in polynomial time.

How to cite

top

Butkovič, Peter. "On the coefficients of the max-algebraic characteristic polynomial and equation." Kybernetika 39.2 (2003): [129]-136. <http://eudml.org/doc/33628>.

@article{Butkovič2003,
abstract = {No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and characteristic equation of a matrix in max- algebra. The following are proved: (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a $\lbrace 0,-\infty \rbrace $ matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a $\lbrace 0,-\infty \rbrace $ matrix can be converted to that of finding the conventional characteristic equation for a $\lbrace 0,1\rbrace $ matrix and thus it is solvable in polynomial time.},
author = {Butkovič, Peter},
journal = {Kybernetika},
keywords = {matrix; characteristicpolynomial; characteristic equation; matrix; characteristic polynomial; characteristic equation},
language = {eng},
number = {2},
pages = {[129]-136},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On the coefficients of the max-algebraic characteristic polynomial and equation},
url = {http://eudml.org/doc/33628},
volume = {39},
year = {2003},
}

TY - JOUR
AU - Butkovič, Peter
TI - On the coefficients of the max-algebraic characteristic polynomial and equation
JO - Kybernetika
PY - 2003
PB - Institute of Information Theory and Automation AS CR
VL - 39
IS - 2
SP - [129]
EP - 136
AB - No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and characteristic equation of a matrix in max- algebra. The following are proved: (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a $\lbrace 0,-\infty \rbrace $ matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a $\lbrace 0,-\infty \rbrace $ matrix can be converted to that of finding the conventional characteristic equation for a $\lbrace 0,1\rbrace $ matrix and thus it is solvable in polynomial time.
LA - eng
KW - matrix; characteristicpolynomial; characteristic equation; matrix; characteristic polynomial; characteristic equation
UR - http://eudml.org/doc/33628
ER -

References

top
  1. Ahuja R. K., Magnanti, T., Orlin J. B., Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, N.J. 1993 Zbl1201.90001MR1205775
  2. Baccelli F. L., Cohen G., Olsder G.-J., Quadrat J.-P., Synchronization and Linearity, Wiley, Chichester 1992 Zbl0824.93003MR1204266
  3. Butkovič P., Murfitt L., Calculating essential terms of a characteristic maxpolynomial, Central European Journal of Operations Research 8 (2000), 237–246 Zbl0982.90042MR1799201
  4. Cuninghame–Green R. A., Minimax Algebra (Lecture Notes in Economics and Mathematical Systems 166), Springer, Berlin 1979 MR0580321
  5. Cuninghame–Green R. A., 10.1016/0022-247X(83)90139-7, J. Math. Anal. Appl. 95 (1983), 110-116 (1983) Zbl0526.90098MR0710423DOI10.1016/0022-247X(83)90139-7
  6. Klinz B., Private communication (2002 
  7. (Ed.) J. van Leeuwen, Handbook of Theoretical Computer Science – Vol, A: Algorithms and Complexity. Elsevier, Amsterdam and MIT Press, Cambridge, MA 1990 Zbl0714.68001MR1127166
  8. Murfitt L., Discrete-Event Dynamic Systems in Max-Algebra: Realisation and Related Combinatorial Problems, Thesis. The University of Birmingham, 2000 
  9. Zimmermann U., Linear and Combinatorial Optimization in Ordered Algebraic Structures (Annals of Discrete Mathematics 10), North Holland, Amsterdam 1981 MR0609751

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.