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(*n*^{3}) time whether a given two-sided homogeneous system belongs to this special case. Solvability can be decided in O(*n*^{3}) time and in the positive case a solution can be found in O(*n*^{3}).

### References

- 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).
- F. L. Bacelli, G. Cohen, G. J. Olsder, J. P. Quadrat, Synchronization and Linearity, An Algebra for Discrete Event Systems, Wiley, Chichester (1992).
- P. A. Binding, H. Volkmer, A generalized eigenvalue problem in the max algebra, Linear Algebra & Appl. 422 (2007) 360-371.
- P. Butković, Necessary solvability conditions of linear extremal equations, Discrete Applied Mathematics 10 (1985) 19-26, North-Holland.
- P. Butković, Max-algebra: the linear algebra of combinatorics?, Linear Algebra & Appl., 367 (2003) 313-335.
- P. Butković, Narrowing the search for eigenvalues in the generalized eigenproblem in max-algebra, University of Birmingham-Preprint 2008/25, 2007.
- P. Butković, A. Aminu, Introduction to Max-linear programming, IMA Journal of Management Mathematics (2008), DOI: 10.1093/imaman/dpn029.
- 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).
- 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.
- 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).
- R. A. Cuninghame-Green, Minimax Algebra, Lecture Notes in Economics and Mathematical Systems, vol.166, Springer, Berlin, (1979).
- R. A. Cuninghame-Green, Minimax Algebra and applications, in: Advances in Imaging and Electron Physics, vol. 90, Academic Press, New York (1995) 1-121.
- R. A. Cuninghame-Green, P. Butković, The equation A ⊗ x = B ⊗ y over (max,+), Theoret. Comput. Sci., 293 (1991) 3-12.
- R. A. Cuninghame-Green, P. Butković, generalized eigenproblem in max-algebra, IEEE explorer (2008).
- R. A. Cuninghame-Green, K. Zimmermann, Equation with residual functions, Comment. Math. Uni. Carolina. 42(2001) 729-740.
- L. Elsner, P. van den Driessche, On the power method in max algebra, Linear Algebra & Appl. 302-303 (1999) 17-32.
- L. Elsner, P. van den Driessche, Modifying the power method in max algebra, Linear Algebra & Appl. 332-334 (2001) 3-13.
- 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).
- R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math. 23 (1978) 309-311.
- P. D. Moral, G. Salut, Random particle methods in (max,+) Optimization problems in: Gunawardena (Ed.), Idempotency, Cambridge, (1988) 383-391.
- I. V. Romanovskil, Optimization of stationary control of discrete deterministic process in dynamic programming, Kibernetika 3(2): 66-78 (1967).
- C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization-Algorithms and Com- plexity, Dover, New York (1998).
- S. Sergeev, Alternating method for homogeneous systems of equations over max-algebra, School of Mathematics pre-print, University of Birmingham, 18, 2008.
- N. N. Vorobyov, Extremal algebra of positive matrices, Elektronische Datenverarbeitung und Kybernetik 3 (1967) 39-71 (in Russian).
- 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.