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.

Preview

Jones17PhD.pdf
PDF - Accepted Version
Download (680kB)

Abstract

The aim of this thesis is to present efficient (strongly polynomial) methods and algorithms for problems in maxalgebra 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.

Supervisor(s):