Special and structured matrices in max-plus algebra

Jones, Daniel Lewis (2017). Special and structured matrices in max-plus algebra. University of Birmingham. Ph.D.

PDF - Accepted Version

Download (680kB)


The aim of this thesis is to present efficient (strongly polynomial) methods and algorithms for problems in max­algebra when certain matrices have special entries or are structured.
First, we describe all solutions to a one-sided parametrised system. Next, we consider special cases of two-sided systems of equations/inequalities. Usually, we describe a set of generators of all solutions but sometimes we are satisfied with finding a non-trivial solution or being able to say something meaningful about a non-trivial solution should it exist. We look at special cases of the generalised eigenproblem, describing the full spectrum usually. Finally, we prove some results on 2x2 matrix roots and generalise these results to a class of nxn matrices.
Main results include: a description of all solutions to the two-dimensional generalised eigenproblem; observations about a non-trivial solution (should it exist) to essential/minimally active two-sided systems of equations; the full spectrum of the generalised eigenproblem when one of the matrices is an outer-product; the unique candidate for the generalised eigenproblem when the difference of two matrices is symmetric and has a saddle point and finally we explicitly say when a 2x2 matrix has a kth root for a fixed positive integer k.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Mathematics
Funders: Engineering and Physical Sciences Research Council
Subjects: Q Science > QA Mathematics
URI: http://etheses.bham.ac.uk/id/eprint/7527


Request a Correction Request a Correction
View Item View Item


Downloads per month over past year