Special and structured matrices in max-plus algebra

[摘要] 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/minimallyactive 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 eigenproblemwhen 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.

[发布机构] University:University of Birmingham;Department:School of Mathematics

[关键词] Q Science;QA Mathematics