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
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL: http://web.mat.bham.ac.uk/P.Butkovic/Grant_2011.html
Further Information:  
Organisation Website: http://www.bham.ac.uk