On the solvability of homogeneous two-sided systems in max-algebra

A. Aminu
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 16, 2010, Number 2, Pages 5–15
Full paper (PDF, 247 Kb)

Details

Authors and affiliations

A. Aminu
Department of Mathematical Sciences
Kano University of Science and Technology, Wudil
P.M.B 3244, Kano, Nigeria

Abstract

Let a⊕b = max(a, b) and a⊗b = a+b for a, b ∈ ℝ and extend the pair of operations to matrices and vectors in the same way as in linear algebra. The homogeneous twosided system in max-algebra is of the form A ⊗ x = B ⊗ x. No polynomial method for solving homogeneous system is known. In this paper, we consider homogeneous twosided linear systems in max-algebra in a special case. We show that it can be checked in O(n3) time whether a given two-sided homogeneous system belongs to this special case. Solvability can be decided in O(n3) time and in the positive case a solution can be found in O(n3).

References

  1. M. Akian, R. Bapat, S. Gaubert, Max-plus algebra, in: L. Hogben (Ed.), Handbook of Linear algebra: Discrete Mathematics and its Application, Chapman & Hall/CRC, Baton Rouge, L.A (2007).
  2. F. L. Bacelli, G. Cohen, G. J. Olsder, J. P. Quadrat, Synchronization and Linearity, An Algebra for Discrete Event Systems, Wiley, Chichester (1992).
  3. P. A. Binding, H. Volkmer, A generalized eigenvalue problem in the max algebra, Linear Algebra & Appl. 422 (2007) 360-371.
  4. P. Butković, Necessary solvability conditions of linear extremal equations, Discrete Applied Mathematics 10 (1985) 19-26, North-Holland.
  5. P. Butković, Max-algebra: the linear algebra of combinatorics?, Linear Algebra & Appl., 367 (2003) 313-335.
  6. P. Butković, Narrowing the search for eigenvalues in the generalized eigenproblem in max-algebra, University of Birmingham-Preprint 2008/25, 2007.
  7. P. Butković, A. Aminu, Introduction to Max-linear programming, IMA Journal of Management Mathematics (2008), DOI: 10.1093/imaman/dpn029.
  8. P. Butković, S.Gaubert and R. A. Cuninghame-Green,, Reducible spectral theory with applications to the robustness of matrices in max-algebra., The University of Birming- ham, preprint 2007/16 (2007).
  9. P. Butković, G. Hegedus, An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonom. mat. Obzor 20 (1984) 2003-215.
  10. J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. McGettrick, J.-P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: IFAC Conference on System Structure and Control (1998).
  11. R. A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol.166, Springer, Berlin, (1979).
  12. R. A. Cuninghame-Green, Minimax Algebra and applications, in: Advances in Imaging and Electron Physics, vol. 90, Academic Press, New York (1995) 1-121.
  13. R. A. Cuninghame-Green, P. Butković, The equation A ⊗ x = B ⊗ y over (max,+), Theoret. Comput. Sci., 293 (1991) 3-12.
  14. R. A. Cuninghame-Green, P. Butković, generalized eigenproblem in max-algebra, IEEE explorer (2008).
  15. R. A. Cuninghame-Green, K. Zimmermann, Equation with residual functions, Comment. Math. Uni. Carolina. 42(2001) 729-740.
  16. L. Elsner, P. van den Driessche, On the power method in max algebra, Linear Algebra & Appl. 302-303 (1999) 17-32.
  17. L. Elsner, P. van den Driessche, Modifying the power method in max algebra, Linear Algebra & Appl. 332-334 (2001) 3-13.
  18. B. Heidergott, G. J. Olsder, J. van der Woude, Max-plus at work, Modelling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications, Princeton University Press, New Jersey (2006).
  19. R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math. 23 (1978) 309-311.
  20. P. D. Moral, G. Salut, Random particle methods in (max,+) Optimization problems in: Gunawardena (Ed.), Idempotency, Cambridge, (1988) 383-391.
  21. I. V. Romanovskil, Optimization of stationary control of discrete deterministic process in dynamic programming, Kibernetika 3(2): 66-78 (1967).
  22. C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization-Algorithms and Com- plexity, Dover, New York (1998).
  23. S. Sergeev, Alternating method for homogeneous systems of equations over max-algebra, School of Mathematics pre-print, University of Birmingham, 18, 2008.
  24. N. N. Vorobyov, Extremal algebra of positive matrices, Elektronische Datenverarbeitung und Kybernetik 3 (1967) 39-71 (in Russian).
  25. E. A. Walkup, G. Boriello, A general linear max-plus solution technique, in: Gunawardena( Ed.), Idempotency, Cambridge, (1988) 406-415.

Related papers

Cite this paper

Aminu, A. (2010). On the solvability of homogeneous two-sided systems in max-algebra, 16(2), 5-15.

Comments are closed.