On special cases of the generalised max-plus eigenproblem

Add to your list(s) Download to your calendar using vCal

• Dan Jones (University of Birmingham, School of Mathematics)
• Thursday 27 October 2016, 12:00-13:00
• University House, room 108.

If you have a question about this talk, please contact Sergey Sergeev.

We study the generalised eigenproblem (GEP) Ax = \lambda Bx, where A and B are real, m x n matrices in the max-plus algebra. Efforts are usually concentrated on finding the spectrum – that is, the set of \lambda for which there exists a solution x. In general, there is no known polynomial method for finding the spectrum. It is known that if A and B are symmetric, then there is at most one generalised eigenvalue – but no description of this unique candidate is known in general.

We find solutions in polynomial time for three special cases of GEP . First, we prove that if C = A – B (in the conventional linear sense) is symmetric, then the common value of all saddle points of C (if any) is the unique candidate for \lambda. Next, we explicitly describe the whole spectrum in the case when B is an outer product. It follows that when A is symmetric and B is constant, then the smallest column maximum of A is the unique candidate for \lambda. We present an idea for a real world application (in car manufacturing) when the outer product case may be used. Finally, we provide a complete description of the spectrum when n = 2.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• Optimisation and Numerical Analysis Seminars
• School of Mathematics events
• University House, room 108

Note that ex-directory lists are not shown.