| Title:
|
On the coefficients of the max-algebraic characteristic polynomial and equation (English) |
| Author:
|
Butkovič, Peter |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
39 |
| Issue:
|
2 |
| Year:
|
2003 |
| Pages:
|
[129]-136 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
matrix |
| Keyword:
|
characteristicpolynomial |
| Keyword:
|
characteristic equation |
| MSC:
|
15A15 |
| MSC:
|
90C27 |
| MSC:
|
93C65 |
| idZBL:
|
Zbl 1249.90213 |
| idMR:
|
MR1996551 |
| . |
| Date available:
|
2009-09-24T19:51:59Z |
| Last updated:
|
2015-03-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135515 |
| . |
| Reference:
|
[1] Ahuja R. K., Magnanti, T., Orlin J. B.: Network Flows: Theory, Algorithms and Applications.Prentice Hall, Englewood Cliffs, N.J. 1993 Zbl 1201.90001, MR 1205775 |
| Reference:
|
[2] Baccelli F. L., Cohen G., Olsder G.-J., Quadrat J.-P.: Synchronization and Linearity.Wiley, Chichester 1992 Zbl 0824.93003, MR 1204266 |
| Reference:
|
[3] Butkovič P., Murfitt L.: Calculating essential terms of a characteristic maxpolynomial.Central European Journal of Operations Research 8 (2000), 237–246 Zbl 0982.90042, MR 1799201 |
| Reference:
|
[4] Cuninghame–Green R. A.: Minimax Algebra (Lecture Notes in Economics and Mathematical Systems 166).Springer, Berlin 1979 MR 0580321 |
| Reference:
|
[5] Cuninghame–Green R. A.: The characteristic maxpolynomial of a matrix.J. Math. Anal. Appl. 95 (1983), 110-116 Zbl 0526.90098, MR 0710423, 10.1016/0022-247X(83)90139-7 |
| Reference:
|
[6] Klinz B.: Private communication (2002. |
| Reference:
|
[7] (Ed.) J. van Leeuwen: Handbook of Theoretical Computer Science – Vol.A: Algorithms and Complexity. Elsevier, Amsterdam and MIT Press, Cambridge, MA 1990 Zbl 0714.68001, MR 1127166 |
| Reference:
|
[8] Murfitt L.: Discrete-Event Dynamic Systems in Max-Algebra: Realisation and Related Combinatorial Problems.Thesis. The University of Birmingham, 2000 |
| Reference:
|
[9] Zimmermann U.: Linear and Combinatorial Optimization in Ordered Algebraic Structures (Annals of Discrete Mathematics 10).North Holland, Amsterdam 1981 MR 0609751 |
| . |
