EPSRC logo

Details of Grant 

EPSRC Reference: EP/J00829X/1
Title: Perron-Frobenius theory and max-algebraic combinatorics of nonnegative matrices
Principal Investigator: Butkovic, Professor P
Other Investigators:
Researcher Co-investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Birmingham
Scheme: Standard Research
Starts: 12 March 2012 Ends: 11 March 2014 Value (£): 175,775
EPSRC Research Topic Classifications:
Algebra & Geometry Numerical Analysis
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Sep 2011 Mathematics Prioritisation Panel Meeting September 2011 Announced
Summary on Grant Application Form
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.

Key Findings
Among the main findings so far 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.

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.

Some 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.
Potential use in non-academic contexts
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.
Impacts
No information has been submitted for this grant.
Sectors submitted by the Researcher
Information & Communication Technologies; Manufacturing; Transport
Project URL: http://web.mat.bham.ac.uk/P.Butkovic/Grant_2011.html
Further Information:  
Organisation Website: http://www.bham.ac.uk