Max-plus algebra

A max-plus algebra is a semiring over the union of real numbers and $\varepsilon = -\infty$, 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.

Operators

Scalar operations

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

$a \oplus b = \max(a,b)$

$a \otimes b = a + b$

Watch: Max-operator $\oplus$ can easily be confused with the addition operation. Similar to the conventional algebra, all $\otimes$ - operations have a higher precedence than $\oplus$ - 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 $\oplus$ 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 \oplus B]_{ij} = [A]_{ij} \oplus [B]_{ij} = \max([A]_{ij} , [B]_{ij})$

The $\otimes$ - operation is similar to the algorithm of Matrix multiplication, however, every "+" calculation has to be substituted by an $\oplus$ - operation and every "$\cdot$" calculation by a $\otimes$ - operation. More precisely, to perform the A $\otimes$ 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 \otimes B]_{ij} = \bigoplus_{k = 1}^p ( [A]_{ik} \otimes [B]_{kj} ) = \max([A]_{i1} + [B]_{1j}, \dots, [A]_{ip} + [B]_{pj})$

Useful enhancement elements

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

$\varepsilon \oplus a = a$

$\varepsilon \otimes a = \varepsilon$

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

$e \otimes a = a. \,$

Obviously, ε is the neutral element for the $\oplus$-operation, as e is for the $\otimes$-operation

Algebra properties

• associativity:

$(a \oplus b) \oplus c = a \oplus (b \oplus c)$

$(a\otimes b) \otimes c = a \otimes (b \otimes c)$

• commutativity :

$a \oplus b = b \oplus a$

$a \otimes b = b \otimes a$

• distributivity:

$(a \oplus b) \otimes c = a \otimes c \oplus b \otimes c$

• zero element :

$a \oplus \varepsilon = a$

• unit element:

$a \otimes e = a$

• idempotency of $\oplus$ :

$a \oplus a = a$

See also

• Tropical geometry

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

External links

• http://maxplus.org
• http://amadeus.inria.fr/gaubert/maxplus.html
• http://press.princeton.edu/titles/8120.html