Samiksha Jaiswal (Editor)

Max plus algebra

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

A max-plus algebra is a semiring over the union of real numbers and ε = , equipped with maximum and addition as the two binary operations. It can be used appropriately to determine marking times within a given Petri net and a vector filled with marking state at the beginning.


Scalar operations

Let a and b be real scalars or ε. Then the operations maximum (implied by the max operator ) and addition (plus operator ) for these scalars are defined as

a b = max ( a , b ) a b = a + b

Watch: Max-operator can easily be confused with the addition operation. Similar to the conventional algebra, all - operations have a higher precedence than - operations.

Matrix operations

Max-plus algebra can be used for matrix operands A, B likewise, where the size of both matrices is the same. To perform the A B - operation, the elements of the resulting matrix at (row i, column j) have to be set up by the maximum operation of both corresponding elements of the matrices A and B:

[ A B ] i j = [ A ] i j [ B ] i j = max ( [ A ] i j , [ B ] i j )

The - operation is similar to the algorithm of Matrix multiplication, however, every "+" calculation has to be substituted by an - operation and every " " calculation by a - operation. More precisely, to perform the A B - operation, where A is a m×p matrix and B is a p×n matrix, the elements of the resulting matrix at (row i, column j) are determined by matrices A (row i) and B (column j):

[ A B ] i j = k = 1 p ( [ A ] i k [ B ] k j ) = max ( [ A ] i 1 + [ B ] 1 j , , [ A ] i p + [ B ] p j )

Useful enhancement elements

In order to handle marking times like which means "never before", the ε-element has been established by ε = . According to the idea of infinity, the following equations can be found:

ε a = a ε a = ε

To point the zero number out, the element e was defined by e = 0 . Therefore:

e a = a .

Obviously, ε is the neutral element for the -operation, as e is for the -operation

Algebra properties

  • associativity:
  • commutativity :
  • distributivity:
  • zero element :
  • unit element:
  • idempotency of  :
  • Additional reading

  • Butkovič, Peter (2010), Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag, doi:10.1007/978-1-84996-299-5 
  • References

    Max-plus algebra Wikipedia