Max-algebra: the linear algebra of combinatorics? Original Research Article

Let acircled plusb=max(a,b), acircle times operatorb=a+b for image. By max-algebra we understand the analogue of linear algebra developed for the pair of operations (circled plus,circle times operator) extended to matrices and vectors. Max-algebra, which has been studied for more than 40 years, is an attractive way of describing a class of nonlinear problems appearing for instance in machine-scheduling, information technology and discrete-event dynamic systems. This paper focuses on presenting a number of links between basic max-algebraic problems like systems of linear equations, eigenvalue–eigenvector problem, linear independence, regularity and characteristic polynomial on one hand and combinatorial or combinatorial optimisation problems on the other hand. This indicates that max-algebra may be regarded as a linear-algebraic encoding of a class of combinatorial problems. The paper is intended for wider readership including researchers not familiar with max-algebra.