Perron-Frobenius theory and max-algebraic combinatorics of nonnegative matrices
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
Max-algebra is a rapidly evolving branch of mathematics with potential to solve a class of non-linear problems in mathematics, science and engineering that can be given the form of linear problems, when arithmetical addition is replaced by the operation of maximum and arithmetical multiplication is replaced by addition. Besides the advantage of dealing with non-linear problems as if they were linear, the techniques of max-algebra enable us in many cases to efficiently describe the set of all solutions and thus to choose a best one with respect to a specified criterion. It also provides an algebraic encoding of a class of combinatorial or combinatorial optimisation problems.
Although the foundations of max-algebra were created in the first pioneering papers produced in the heart of England 50 years ago, it is mainly after 2000 that we see a remarkable expansion of this area in a number of research centres worldwide (e.g. Paris, Berkeley, San Diego, Delft, Madison and Moscow). Nowadays it penetrates a range of areas of mathematics from algebraic topology, functional analysis, linear algebra and geometry, to non-linear, discrete and stochastic optimisation and mathematical biology. The number of conferences, mini-symposia, workshops and other events devoted partly or wholly to max-algebra is increasing. A number of research monographs have been published, three of them since 2005. Applications are both theoretical (for instance in discrete-event dynamic systems, control theory and optimisation) and practical (analysis of the Dutch railway network).
Following the recent remarkable expansion of max-algebra and latest research findings, it seems to be the right time to use the recently developed powerful combinatorial techniques of max-algebra to strengthen the interplay between max-algebra and conventional linear algebra. This means for instance to develop the Perron-Frobenius theory in semirings, develop the theory of max-algebraic tensors, solve the mean-payoff games and max-algebraic matrix equations. This will have an immediate impact on the understanding of a range of properties of matrices which find applications in other areas of mathematics, in physics, computer science, engineering, biology and elsewhere in a way similar to that of conventional linear algebra. For instance it will enable researchers to solve systems of max-algebraic equations, help to analyse complex systems of information technology by using a max-algebraic rather than traditional model, find a steady regime in systems with max-linear dynamics, model and solve problems arising in solid state physics, or in certain types of scheduling problems.
To feed into this project and also to help to address the challenges, the PI will link this research with the work of the existing UK working group in tropical mathematics funded by the London Mathematical Society, which he chairs. Research meetings of this group are organised three times a year in Warwick, Manchester and Birmingham and are attended by more than 30 colleagues from a number of UK universities. The PI will form collaborative networks and strategic partnership with a number of internationally leading centres in max-algebra to further advance the field.
It is expected that as a consequence of this project the PI will obtain support to organise an international conference on tropical mathematics at Birmingham in 2014 or 2015 and in the future to create a centre for tropical mathematics (CTM), which will have several funded research projects. CTM will organise international research workshops and conferences, provide expertise for industrial partners and for specialised undergraduate and postgraduate courses. It will closely cooperate with the research group CICADA at the University of Manchester and with the existing similar centre at the Ecole Polytechnique in Paris.
Although the foundations of max-algebra were created in the first pioneering papers produced in the heart of England 50 years ago, it is mainly after 2000 that we see a remarkable expansion of this area in a number of research centres worldwide (e.g. Paris, Berkeley, San Diego, Delft, Madison and Moscow). Nowadays it penetrates a range of areas of mathematics from algebraic topology, functional analysis, linear algebra and geometry, to non-linear, discrete and stochastic optimisation and mathematical biology. The number of conferences, mini-symposia, workshops and other events devoted partly or wholly to max-algebra is increasing. A number of research monographs have been published, three of them since 2005. Applications are both theoretical (for instance in discrete-event dynamic systems, control theory and optimisation) and practical (analysis of the Dutch railway network).
Following the recent remarkable expansion of max-algebra and latest research findings, it seems to be the right time to use the recently developed powerful combinatorial techniques of max-algebra to strengthen the interplay between max-algebra and conventional linear algebra. This means for instance to develop the Perron-Frobenius theory in semirings, develop the theory of max-algebraic tensors, solve the mean-payoff games and max-algebraic matrix equations. This will have an immediate impact on the understanding of a range of properties of matrices which find applications in other areas of mathematics, in physics, computer science, engineering, biology and elsewhere in a way similar to that of conventional linear algebra. For instance it will enable researchers to solve systems of max-algebraic equations, help to analyse complex systems of information technology by using a max-algebraic rather than traditional model, find a steady regime in systems with max-linear dynamics, model and solve problems arising in solid state physics, or in certain types of scheduling problems.
To feed into this project and also to help to address the challenges, the PI will link this research with the work of the existing UK working group in tropical mathematics funded by the London Mathematical Society, which he chairs. Research meetings of this group are organised three times a year in Warwick, Manchester and Birmingham and are attended by more than 30 colleagues from a number of UK universities. The PI will form collaborative networks and strategic partnership with a number of internationally leading centres in max-algebra to further advance the field.
It is expected that as a consequence of this project the PI will obtain support to organise an international conference on tropical mathematics at Birmingham in 2014 or 2015 and in the future to create a centre for tropical mathematics (CTM), which will have several funded research projects. CTM will organise international research workshops and conferences, provide expertise for industrial partners and for specialised undergraduate and postgraduate courses. It will closely cooperate with the research group CICADA at the University of Manchester and with the existing similar centre at the Ecole Polytechnique in Paris.
Planned Impact
1. The principal objective of the proposed 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 will have an immediate impact on any researcher working in max-algebra and on many researchers in linear and numerical linear algebra as it will enable further research progress by providing new max-algebraic and linear-algebraic methodologies.
2. In the longer term the results of this project will be useful for researchers in other areas of mathematics and for researchers in physics, computer science, engineering, biology and elsewhere in a way similar to that of conventional linear algebra. For instance it will enable researchers to solve systems of max-algebraic equations, help to analyse complex systems of information technology by using a max-algebraic rather than traditional model, find a steady regime in systems with max-linear dynamics, model and solve problems arising in solid state physics, or in certain types of scheduling problems.
3. Network Rail has recently expressed interest in the use of max-algebraic methodology for the analysis of stability of the UK railway network and its possible use in railway scheduling. This follows a successful attempt for such an application in the Dutch railway network achieved in recent years. It is expected that this would eventually lead to a smoother and more reliable train service in selected areas. Consequently, it would not only have an impact on the quality of life of passengers but also on the efficiency of the use of resources and thus also on environmental sustainability.
4. In the longer term, it is also the intention to create a centre for tropical mathematics (CTM) at Birmingham, which will have several funded research projects. The results of the proposed research will be of fundamental importance for the creation of such a centre. The CTM will organise international research workshops and conferences, provide expertise for industrial partners and prepare specialised undergraduate and postgraduate courses. This will strengthen the dissemination of the max-algebraic expertise, prepare a number of highly skilled researchers in this field and enhance the research capacity of the host School.
5. Successful applications will attract attention to max-algebra as a new mathematical area that provides novel approaches to solving both theoretical and practical problems. It should therefore attract further funding not only by research councils but also by industrial partners. Hence among the beneficiaries should eventually also be the host university by receiving new sources of research funding.
6. It is expected that successful applications will increase public awareness and support of mathematics research. So a beneficiary will also be mathematics as a science.
2. In the longer term the results of this project will be useful for researchers in other areas of mathematics and for researchers in physics, computer science, engineering, biology and elsewhere in a way similar to that of conventional linear algebra. For instance it will enable researchers to solve systems of max-algebraic equations, help to analyse complex systems of information technology by using a max-algebraic rather than traditional model, find a steady regime in systems with max-linear dynamics, model and solve problems arising in solid state physics, or in certain types of scheduling problems.
3. Network Rail has recently expressed interest in the use of max-algebraic methodology for the analysis of stability of the UK railway network and its possible use in railway scheduling. This follows a successful attempt for such an application in the Dutch railway network achieved in recent years. It is expected that this would eventually lead to a smoother and more reliable train service in selected areas. Consequently, it would not only have an impact on the quality of life of passengers but also on the efficiency of the use of resources and thus also on environmental sustainability.
4. In the longer term, it is also the intention to create a centre for tropical mathematics (CTM) at Birmingham, which will have several funded research projects. The results of the proposed research will be of fundamental importance for the creation of such a centre. The CTM will organise international research workshops and conferences, provide expertise for industrial partners and prepare specialised undergraduate and postgraduate courses. This will strengthen the dissemination of the max-algebraic expertise, prepare a number of highly skilled researchers in this field and enhance the research capacity of the host School.
5. Successful applications will attract attention to max-algebra as a new mathematical area that provides novel approaches to solving both theoretical and practical problems. It should therefore attract further funding not only by research councils but also by industrial partners. Hence among the beneficiaries should eventually also be the host university by receiving new sources of research funding.
6. It is expected that successful applications will increase public awareness and support of mathematics research. So a beneficiary will also be mathematics as a science.
Organisations
People |
ORCID iD |
| Peter Butkovic (Principal Investigator) |
Publications
Benek Gursoy B
(2015)
The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields
in Linear Algebra and its Applications
Butkovic P
(2013)
Two cores of a nonnegative matrix
in Linear Algebra and its Applications
Butkovic P
(2014)
On the integer max-linear programming problem
in Discrete Applied Mathematics
Butkovic P
(2013)
On integer eigenvectors and subeigenvectors in the max-plus algebra
in Linear Algebra and its Applications
Butkovic P
(2016)
On Special Cases of the Generalized Max-Plus Eigenproblem
in SIAM Journal on Matrix Analysis and Applications
Butkovic P
(2014)
A Strongly Polynomial Method for Solving Integer Max-Linear Optimization Problems in a Generic Case
in Journal of Optimization Theory and Applications
Butkovic P
(2012)
Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings
in Linear and Multilinear Algebra
Butkovic P
(2018)
A Note on Tropical Linear and Integer Programs
in Journal of Optimization Theory and Applications
Butkovic P
(2016)
On tropical supereigenvectors
in Linear Algebra and its Applications
Butkovic P
(2012)
Recognizing Weakly Stable Matrices
in SIAM Journal on Control and Optimization
| Description | Among the main findings are: 1. Full characterisation of tropical weakly stable matrices in terms of Hamilton cycles. Orbits of these matrices by definition never reach an eigenvector unless they start in one. We proved that irreducible weakly stable matrices are exactly those whose critical graph is a Hamilton cycle in the associated graph. Using the Frobenius normal form of a matrix a necessary and sufficient condition was found for any (reducible) matrix. These criteria can be checked in polynomial time. This result enables us to efficiently characterise multiprocessor interactive processes which never reach stable regime unless they start from a stable state. This research was initiated before the start of the project but was finalised during the current project. 2. Proof that the sequence of eigencones (that is cones of nonnegative eigenvectors) of matrix powers is periodic both in max algebra and in nonnegative linear algebra. Using the max-algebraic Perron-Frobenius theory we have also shown that the Minkowski sum of the eigencones of matrix powers is equal to the core of the matrix defined as the intersection of nonnegative column spans of matrix powers, also in max algebra. Based on this, we describe the set of extremal rays of the core. The theory of the matrix core has been developed in max algebra and in nonnegative linear algebra simultaneously, in order to unify and compare both versions of the same theory. Further substantial results in this area are expected to be finalised soon. 3. (Joint research with M. MacCaig) Conditions for existence and description of max-algebraic integer subeigenvectors and eigenvectors of a given square matrix. We proved that the former can be solved as easily as the corresponding question without the integrality requirement (that is in polynomial time). An algorithm was presented for finding an integer point in the tropical column space of a matrix or deciding that no such vector exists. This algorithm was used to solve the problem of integer eigenvectors for any matrix. The algorithm was shown to be pseudopolynomial for finite matrices, which implies that this problem can be solved in pseudopolynomial time for any irreducible matrix. We have also identified classes of matrices for which it can be solved in polynomial time. A strongly polynomial algorithm has been developed to solve integer max-linear programs in a generic case. 4. We have studied the max-algebraic analogues of equations involving Z-matrices and M-matrices, with an outlook to a more general algebraic setting. We have shown that these equations can be solved using the Frobenius trace-down method in a way similar to that in nonnegative linear algebra that characterises the solvability in terms of supports and access relations. We proved a description of the solution set as a combination of the least solution and the eigenspace of the matrix, and provide a general algebraic setting in which this result holds. 5. (Joint research with O. Mason and B. Benek Gursoy) The Analytic Hierarchy Process (AHP) is widely used for decision making involving multiple criteria. A max-algebraic approach to the single criterion AHP, introduced previously by Elsner and van den Driessche, has been extended to the multi-criteria AHP, by considering multi-objective generalisations of the single objective optimisation problem. The existence of min-max optimal solutions is characterized by means of the spectral radius of the associated tropical matrix semigroup. The existence of globally optimal solutions is shown to be related to the commutativity properties of the associated matrices. 6. We have studied the ultradiscrete analogue of the Lax pair. This pair is a max-plus linear system comprising four equations. Our starting point is to treat this system as a combination of two max-plus eigenproblems, with two additional constraints. Though of infinite dimensions, these two eigenproblems can be treated by means of the standard max-plus spectral theory. In particular, any solution to the system can be described as a tropical combination of fundamental eigenvectors associated with each soliton. 7. Several types of semigroups of matrices (commutative, nilpotent and quasinilpotent) were considered in the joint work of Sergeev with Litvinov and Shpiz. The existence of a common eigenvector was proved for matrices with complex or real nonnegative entries both in the conventional and tropical linear algebra. 8. The joint paper of Sergeev with Litvinov, Rodionov and Sobolevskii is a survey on universal algorithms for solving Z-equations (also known as Bellman equations) over semirings and especially tropical and idempotent semirings. New algorithms for special types of matrices are also presented. 9. Tropical hemispaces, defined as tropically convex sets whose complements are tropicallly convex, were investigated in the joint paper of Sergeev with Katz and Nitica. The paper introduces the concept of (P,R)-decomposition yielding a new kind of representation of tropically convex sets extending the classical idea of representing convex sets by means of extreme points and rays. The tropical hemispaces are then characterized as tropically convex sets admitting a (P,R)-representation of a specific kind. This paper is currently one of the most downloaded papers from Linear Algebra and Its Applications. 10. In general, the transient of periodicity of matrix powers in max algebra depends both on the dimension of the matrix and on the magnitude of entries. However, it has been shown in this project that for the entries corresponding to critical nodes of the graph, the dependence on the magnitude of the entries is not crucial. More precisely, we proved that the bounds of Wielandt, Dulmage-Mendelsohn, Schwarz, Kim and Gregory-Kirkland-Pullman, previously known only for unweighted digraphs, also hold in this case. For arbitrary matrix entries, we have proposed a new method for deriving the bounds on periodicity. This method is based on the concept of the weak CSR expansion, being a new development of the CSR expansion idea of Sergeev-Schneider. A number of new bounds is established, using a combination of the new CSR concept with ideas taken from existing literature. The new bounds are essential improvements over the previously known ones. 11. The Markov chain tree theorem has been extended to general commutative semirings, and the state reduction algorithm computing the Markov chain tree vector has been extended to general commutative semifields. This leads to a new universal algorithm. 12. Some classes of nonnegative and complex matrices have been studied; in particular those defined by the row sums and associated digraphs. We have characterised the sets of Perron roots and eigenvalues of such matrices, also using the related methodology of max algebra. A new proof of the Camion-Hoffman theorem has been published. |
| Exploitation Route | 1. Most of the problems studied in this project may find immediate application in any multiprocessor interactive system, which is essentially any multi-stage system (mainly in industry but also for instance in biology) in which processes run in stages and the individual components of the system work interactively so that the work of a component cannot start before the work of some or all components in the previous stage is not finished. The use of the results in this project is likely to increase efficiency of the system and enable its smooth and stable run. 2. Network Rail has expressed interest in the use of max-algebraic methodology for the analysis of stability of the UK railway network and its possible use in railway scheduling. This follows a successful attempt for such an application in the Dutch railway network done in recent years. It is expected that this would eventually lead to a smoother and more reliable train service in selected areas. Consequently, it would have an impact on the efficiency of the use of resources and thus also on environmental sustainability. It is expected that the project will attract attention to max-algebra as a new mathematical area that provides novel approaches to timetabling in railways and other means of transport. Further funding for this research and its applications is being sought. 3. The results in this project are most likely to find their use by other researchers in tropical and classical linear algebra. All significant results are being published in international academic journals and have been/will be presented at national and international conferences and seminars (such as ILAS 2014 South Korea, SIAM Conference on applied linear algebra 2012, ILAS conference 2013, International Workshop on Tropical and Idempotent Mathematics in Moscow 2012, International Symposium on Positive Systems in Ireland 2012, Ames, Iowa, 2013 and the 2012 Haifa Matrix Theory Conference). The achieved results also appear on the PI's website. 4. The work of the research team is linked to the work of the joint research group in tropical mathematics funded by London Mathematical Society. Research meetings of the group are organized three times a year in Warwick, Manchester and Birmingham and are attended by colleagues from a number of UK universities and from abroad. Researchers from other disciplines (mainly computer science and physics) and industry (mainly railway operators but possibly also manufacturers) are encouraged to join the working group and the meetings provide a platform for cross-disciplinary collaboration. |
| Sectors | Digital/Communication/Information Technologies (including Software),Manufacturing, including Industrial Biotechology,Transport |
| URL | http://web.mat.bham.ac.uk/P.Butkovic/Grant_2011.html |