Max-Plus Algebra

A max-plus-algebra is a mathematical object that is comparable to an algebra over the real numbers , but with the body operations being replaced: addition by forming the maximum, multiplication by ordinary addition. Geometry above the Max-Plus-Algebra is called tropical geometry . Therefore the Max-Plus-Algebra is also called a tropical semiring . In planning theory, for example when dealing with Petri nets , the theory of max-plus algebras allows the use of suitable methods from linear algebra. The optimization of a timetable can, for example, be seen as an eigenvalue problem in this way .

Just as the term algebra describes both a mathematical structure and a mathematical sub-area, Max-Plus-Algebra is sometimes also understood as the mathematical sub-area that deals with said structures.

definition

A max-plus-algebra is a half-ring on which an idempotent commutative half-body with zero element operates by means of a multiplication . (For comparison: an algebra is a ring on which a body operates) ${\displaystyle (A,\oplus _{A},\otimes _{A})}$ ${\displaystyle (K,\oplus _{K},\otimes _{K},\varepsilon ,e)}$ ${\displaystyle \otimes }$

In detail, this means that the axioms listed below are fulfilled, each for all and . ${\displaystyle a,b,c\in K}$ ${\displaystyle u,v,w\in A}$

Half ring

1. ${\displaystyle u\oplus _{A}(v\oplus _{A}w)=(u\oplus _{A}v)\oplus _{A}w}$
2. ${\displaystyle u\oplus _{A}v=v\oplus _{A}u}$
3. ${\displaystyle u\otimes _{A}(v\otimes _{A}w)=(u\otimes _{A}v)\otimes _{A}w}$
4. ${\displaystyle u\otimes _{A}(v\oplus _{A}w)=(u\otimes _{A}v)\oplus _{A}(u\otimes _{A}w)}$
5. ${\displaystyle (u\oplus _{A}v)\otimes _{A}w=(u\otimes _{A}w)\oplus _{A}(v\otimes _{A}w)}$

According to 1. and 2. is a commutative semigroup, according to 3. is a semigroup, 4. and 5. are the distributive laws. ${\displaystyle (A,\oplus _{A})}$ ${\displaystyle (A,\otimes _{A})}$

Idempotent commutative half-body

1. ${\displaystyle a\oplus _{K}(b\oplus _{K}c)=(a\oplus _{K}b)\oplus _{K}c}$
2. ${\displaystyle a\oplus _{K}b=b\oplus _{K}a}$
3. ${\displaystyle a\otimes _{K}(b\otimes _{K}c)=(a\otimes _{K}b)\otimes _{K}c}$
4. ${\displaystyle a\otimes _{K}(b\oplus _{K}c)=(a\otimes _{K}b)\oplus _{K}(a\otimes _{K}c)}$
5. ${\displaystyle (a\oplus _{K}b)\otimes _{K}c=(a\otimes _{K}c)\oplus _{K}(b\otimes _{K}c)}$
6. ${\displaystyle \varepsilon \oplus _{K}a=a\oplus _{K}\varepsilon =a}$
7. ${\displaystyle e\otimes _{K}a=a\otimes _{K}e=a}$
8. If so, there is a with ${\displaystyle a\neq \varepsilon }$ ${\displaystyle a'\in K}$ ${\displaystyle a\otimes _{K}a'=a'\otimes _{K}a=e}$
9. ${\displaystyle a\otimes _{K}b=b\otimes _{K}a}$
10. ${\displaystyle a\oplus _{K}a=a}$

According to 1. – 5. is half-ring, according to 6th and 7th and are neutral elements of the links. Together with the existence of multiplicatively inverse elements according to 8, there is therefore a half-body which is commutative according to 9 (multiplicative) and idempotent according to 10 (additive). ${\displaystyle (K\oplus _{K},\otimes _{K})}$ ${\displaystyle \varepsilon }$ ${\displaystyle e}$ ${\displaystyle (K,\oplus _{K},\otimes _{K},\varepsilon ,e)}$

surgery

1. ${\displaystyle e\otimes v=v}$
2. ${\displaystyle (a\otimes _{K}b)\otimes v=a\otimes (b\otimes v)}$
3. ${\displaystyle a\otimes (v\otimes _{A}w)=(a\otimes v)\otimes _{A}w}$
4. ${\displaystyle (a\oplus _{K}b)\otimes v=(a\otimes v)\oplus _{A}(b\otimes v)}$
5. ${\displaystyle a\otimes (v\oplus _{A}w)=(a\otimes v)\oplus _{A}(a\otimes w)}$

The operation should therefore be compatible with the links on or in an obvious manner . ${\displaystyle \otimes }$ ${\displaystyle A}$ ${\displaystyle K}$

Examples

In the following, for the sake of readability, the indices on the links are omitted, since it is clear from the context which of the links must be meant. The circulations of the operators, however, are necessary to avoid confusion with the usual addition or multiplication.

The most important example for an idempotent commutative half body is denoted by and has the underlying set and the links ${\displaystyle \mathbb {R} _{\max }}$ ${\displaystyle \mathbb {R} \cup \{-\infty \}}$

• ${\displaystyle x\oplus y:=\max\{x,y\}}$(special ) ${\displaystyle (-\infty )\oplus x=x\oplus (-\infty )=x}$
• ${\displaystyle x\otimes y:=x+y}$(special ). ${\displaystyle (-\infty )\otimes x=x\otimes (-\infty )=-\infty }$

The neutral element with regard to is , the one with regard to is 0. This use of the operations maximum and addition also motivates the term Max-Plus-Algebra . Another important idempotent commutative half-body is , it is sometimes referred to as Min-Plus-Algebra . The following examples of max plus algebras are all max plus algebras over : ${\displaystyle \oplus }$ ${\displaystyle -\infty }$ ${\displaystyle \otimes }$ ${\displaystyle \mathbb {R} _{\min }:=(\mathbb {R} \cup \{+\infty \},\min ,+,+\infty ,0)}$ ${\displaystyle \mathbb {R} _{\max }}$

• ${\displaystyle \mathbb {R} _{\max }}$ itself is a max plus algebra.
• The set of all mappings from a fixed set to with pointwise maximum formation and addition and scalar operation. ${\displaystyle \mathbb {R} _{\max }^{M}}$ ${\displaystyle M}$ ${\displaystyle \mathbb {R} _{\max }}$
• The required operations can be defined on the set of all mappings as follows: ${\displaystyle \mathbb {R} _{\max }^{\mathbb {R} }}$ ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} _{\max }}$

  ${\displaystyle (f\oplus g)(x)=f(x)\oplus g(x)=\max\{f(x),g(x)\}}$ (point-wise maximum formation)

  ${\displaystyle (f\otimes g)(x)=\sup _{t\in \mathbb {R} }(f(t)+g(x-t))}$ (so-called supreme folding)

  ${\displaystyle (c\otimes f)(x)=c\otimes f(x)=c+f(x)}$

However, under the supremum fold is not complete. However, through the transition to suitable subsets thereof, for example to the set of mappings restricted upwards, one obtains a Max-Plus-Algebra. Note that this structure differs from the special case of the previous example. ${\displaystyle \mathbb {R} _{\max }^{\mathbb {R} }}$ ${\displaystyle M=\mathbb {R} }$

• The set of all matrices with entries in , whereby addition and multiplication of matrices are calculated according to the usual formulas in which and are replaced by and . Like normal matrix multiplication, it is not commutative either . ${\displaystyle \mathbb {R} _{\max }^{n\times n}}$ ${\displaystyle n\times n}$ ${\displaystyle \mathbb {R} _{\max }}$ ${\displaystyle +}$ ${\displaystyle \cdot }$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$ ${\displaystyle \otimes }$

literature

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

Web links

• amadeus.inria.fr