EPSRC Reference: 
EP/J00829X/1 
Title: 
PerronFrobenius theory and maxalgebraic combinatorics of nonnegative matrices 
Principal Investigator: 
Butkovic, Professor P 
Other Investigators: 

Researcher CoInvestigators: 

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: 

Summary on Grant Application Form 
Maxalgebra is a rapidly evolving branch of mathematics with potential to solve a class of nonlinear 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 nonlinear problems as if they were linear, the techniques of maxalgebra 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 maxalgebra 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 nonlinear, discrete and stochastic optimisation and mathematical biology. The number of conferences, minisymposia, workshops and other events devoted partly or wholly to maxalgebra is increasing. A number of research monographs have been published, three of them since 2005. Applications are both theoretical (for instance in discreteevent dynamic systems, control theory and optimisation) and practical (analysis of the Dutch railway network).
Following the recent remarkable expansion of maxalgebra and latest research findings, it seems to be the right time to use the recently developed powerful combinatorial techniques of maxalgebra to strengthen the interplay between maxalgebra and conventional linear algebra. This means for instance to develop the PerronFrobenius theory in semirings, develop the theory of maxalgebraic tensors, solve the meanpayoff games and maxalgebraic 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 maxalgebraic equations, help to analyse complex systems of information technology by using a maxalgebraic rather than traditional model, find a steady regime in systems with maxlinear 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 maxalgebra 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 maxalgebraic PerronFrobenius 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 maxalgebraic 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 maxalgebraic analogues of equations involving Zmatrices and Mmatrices, with an outlook to a more general algebraic setting. We have shown that these equations can be solved using the Frobenius tracedown 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 maxalgebraic approach to the single criterion AHP, introduced previously by Elsner and van den Driessche, has been extended to the multicriteria AHP, by considering multiobjective generalisations of the single objective optimisation problem. The existence of minmax 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 maxplus linear system comprising four equations. Our starting point is to treat this system as a combination of two maxplus eigenproblems, with two additional constraints. Though of infinite dimensions, these two eigenproblems can be treated by means of the "standard" maxplus 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 Zequations (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 nonacademic contexts 
1. Most of the problems studied in this project may find immediate application in any multiprocessor interactive system, which is essentially any multistage 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 maxalgebraic 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 maxalgebra 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 