March 2012 - March 2014

The principal objective of this research is to use the recently developed powerful combinatorial methodology in max-algebra to develop the interplay between linear algebra of nonnegative matrices and max-algebra. This may be useful for researchers working in max-algebra, in linear and numerical linear algebra as it will enable further progress by providing new max-algebraic and linear-algebraic methodologies. A key idea is that of developing Perron-Frobenius theory in max-algebra using the combinatorial concepts such as associated and critical graphs.

Principal Investigator: Professor Peter Butkovic (School of Mathematics, University of Birmingham)

Research Fellow: Dr Sergei Sergeev (School of Mathematics, University of Birmingham)

Visiting Researcher: Professor Hans Schneider (Department of Mathematics, University of Wisconsin, Madison)

1. P. Butkovic, H. Schneider and S. Sergeev, Recognizing weakly stable matrices, SIAM J. Control Optim. 2012, 50(5), 3029-3051. DOI: 10.1137/110837942.

2. P. Butkovic, H. Schneider and S. Sergeev, Z-matrix equations in max algebra,nonnegative linear algebra and other semirings, Linear and Multilinear Algebra (2012) 1-20. DOI:10.1080/03081087.2012.656107.

3. P. Butkovic, M. MacCaig, On integer eigenvectors and subeigenvectors in the max-plus algebra, Linear Algebra and its Applications 438 (2013) 3408-3424. DOI: 10.1016/j.laa.2012.12.017.

4. B. Benek Gursoy, O. Mason and S. Sergeev, The analytic hierarchy process, max algebra and multi-objective optimization, Linear Algebra and Its Applications, 438 (2013) 2911-2928. DOI:10.1016/j.laa.2012.11.020.

5. S. Sergeev, An application of the max-plus spectral theory to an ultradiscrete analogue of the Lax pair. In: C. Athorne, D. Maclagan, I. Strachan (Eds.), Tropical Geometry and Integrable Systems, vol. 580 of Contemporary Mathematics (2012) 117-133. DOI: 10.1090/conm/580/11501.

6. B. Benek Gursoy, S. Kirkland, O. Mason and S. Sergeev, On the Markov chain tree theorem in the max-algebra, Electronic J of Linear Algebra 26 (2013) 15-27.

7. V. Nitica, S. Sergeev, The structure of max-plus hemispaces, Proceedings of the Internat. Workshop "Tropical and Idempotent Mathematics" (Moscow, August 2012), Institute for Information Transmission Problems et.al., Moscow, 2012, pp. 199-207.

8. V. Nitica, S. Sergeev, Semispaces in the max-min convexity, Proceedings of the Internat. Workshop "Tropical and Idempotent Mathematics" (Moscow, August 2012), Institute for Information Transmission Problems et.al, Moscow, 2012, pp. 208-214.

9. O. Holtz, V. Mehrmann, H. Schneider, Matrices that commute with their derivative. On a letter from Schur to Wielandt, Linear Algebra and its Applications, Volume 438 (2013) 2574-2590. DOI: 10.1016/j.laa.2012.10.010.

10. G. L. Litvinov, A.Ya. Rodionov, S. N. Sergeev and A. N. Sobolevskii, Universal algorithms for solving the matrix Bellman equation over semirings, Soft Computing (2013). DOI: DOI 10.1007/s00500-013-1027-5

11. P. Butkovic, H. Schneider and S. Sergeev: Two cores of a nonnegative matrix, Linear Algebra and its Applications 439 (2013) 1929–1954

12. G. B. Shpiz, G. L. Litvinov and S. N. Sergeev, On common eigenvectors for semigroups of matrices in tropical and traditional mathematics, Linear Algebra and its Applications, 439 (2013) 1651-1656.

13. R. D. Katz, V. Nitica and S. Sergeev, Characterization of tropical hemispaces by (P,R)-decompositions, Linear Algebra and its Applications 440 (2014) 131-163.

14. V. Nitica and S. Sergeev, Tropical convexity over max-min
semiring, In: Litvinov and Sergeev (eds.), Tropical and Idempotent Mathematics
and Applications, Cont. Math. (AMS) vol. 616, 2014, pages 241-260.

15. P. Butkovic, M. MacCaig: The alternating method for finding integer solutions to two-sided systems, School of Mathematics, University of Birmingham, preprint 2012/8.

16. S. Gaubert and S. Sergeev, The level set method for the two-sided max-plus eigenproblem, Discrete Event Dyn Syst (2013) 23:105–134.DOI 10.1007/s10626-012-0137-z

17. P. Butkovic, M. MacCaig: On the integer max-linear programming problem, Discrete Applied Mathematics 162 (2014) 128–141.

18. P.Butkovic, M.MacCaig: A strongly polynomial method for solving integer max-linear programs in a generic case, Journal of Optimization Theory and Applications (2014).

19. G. Merlet, T. Nowak, H. Schneider and S. Sergeev, Generalizations
of bounds on the index of convergence to weighted digraphs. Discrete Applied
Mathematics 178 (2014) 121–134.

20. G. Merlet, T. Nowak and S. Sergeev, Weak CSR expansions and
transience bounds in max-plus algebra. Linear Algebra and Its Applications 461
(2014) 163–199.

21. B. Benek Gursoy, S. Kirkland, O. Mason and S. Sergeev, The
Markov Chain Tree Theorem in commutative semirings and the State Reduction
Algorithm in commutative semifields. Linear Algebra and Its Applications, In
press.

23. V.Nitica and S.Sergeev, On the dimension of max-min convex sets. Fuzzy Sets and Systems, in press, Available online 18 Oct. 2014. DOI:10.1016/j.fss.2014.10.008

24. M.Gavalec, Z.Nemcova and S.Sergeev, Tropical linear algebra with the Lukasiewicz T-norm. Fuzzy Sets and Systems, in press. DOI:10.1016/j.fss.2014.11.008

25. M. MacCaig: Exploring the complexity of the integer image problem
in the max-algebra (submitted).

27. P. Butkovic, H. Schneider and S. Sergeev: On the max-algebraic core of a nonnegative matrix. Electronic Journal of Linear Algebra 27 (2014).

28. P. Butkovic: Weakly and strongly stable max-plus matrices, 21st International Symposium on Mathematical Theory of Networks and Systems, July 7-11, 2014. Groningen, The Netherlands. Extended abstract.

29. S. Sergeev: Extremals of the supereigenvector cone in
max algebra: A combinatorial description, Linear Algebra and
its Applications 479 (2015) 106-117.