Max-Plus Algebra

In the previous chapter we described max-plus algebra in an informal way. The present chapter contains a more rigorous treatment of max-plus algebra. In Section 1.1 basic concepts are introduced, and algebraic properties of max-plus algebra are studied. Matrices and vectors over max-plus algebra are introduced in Section 1.2, and an important model, called heap of pieces or heap model, which can be described by means of max-plus algebra, is presented in Section 1.3. Finally, the projective space, a mathematical framework most convenient for studying limits, is introduced in Section 1.4.

1.1 BASIC CONCEPTS AND DEFINITIONS

Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and denote by Rmax the set R [intersection] {ε}, where R is the set of real numbers. For elements a, b [member of] Rmax we define operations [direct sum] and [cross product] by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1)

Clearly, max(a, -∞) = max(-∞, a) = a and a + (-∞) = -∞ + a = -∞, for any a [member of] Rmax, so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

for any a [member of] Rmax. The above definitions are illustrated with some numerical examples as follows:

5 [direct sum] 3 = max(5, 3) = 5,

5 [direct sum] ε = max(5, -∞) = 5,

5 [cross product] ε = 5 -∞ = -∞ = ε,

e [direct sum] 3 = max(0, 3) = 3,

5 [cross product] 3 = 5 + 3 = 8.

The set Rmax together with the operations [direct sum] and [cross product] is called max-plus algebra and is denoted by

Rmax = (Rmax, [direct sum], [cross product], ε,e).

As in conventional algebra, we simplify the notation by letting the operation [cross product] have priority over the operation [direct sum]. For example,

5 [cross product] -9 [direct sum] 7 [cross product] 1

has to be understood as

(5 [cross product] -9) [direct sum] (7 [cross product] 1).

Notice that (5 [cross product] -9) [direct sum] (7 [cross product] 1) = 8, whereas 5 [cross product] (-9 [direct sum] 7) [cross product] 1 = 13.

The operations [direct sum] and[cross product] defined in (1.1) have some interesting algebraic properties. For example, for x, y, z [member of] Rmax. it holds that

x [cross product] (y [direct sum] z) = x + max(y, z) = max(x + y,x + z) = (x [cross product] y) [direct sum] (x [cross product] z),

which in words means that [cross product] distributes over [direct sum]. Below we give a list of algebraic properties of max-plus algebra.

• Associativity:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Commutativity:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Distributivity of[cross product] over [direct sum]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Existence of a zero element:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Existence of a unit element:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• The zero is absorbing for [cross product]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

• Idempotency of [direct sum]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Powers are introduced in max-plus algebra in the natural way using the associative property. We denote the set of natural numbers including zero by N and define for x [member of] Rmax

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.3)

for all n [member of] N with n [not equal] 0, and for n = 0 we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Observe that x[cross product]n, for any n [member of] N, reads in conventional algebra as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For example,

5[cross product]3 = 3 × 5 = 15.

Inspired by this we similarly introduce negative powers of real numbers, as in

8[cross product]-2 = -2 x 8 = -16 = 16[cross product]-1,

for example. In the same vein, max-plus roots can be introduced as

x[cross product]α = α × x,

for α [member of] R. For example,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Continuing with the algebraic point of view, we show that max-plus algebra is an example of an algebraic structure, called a semiring, to be introduced next.

Definition 1.1A semiring is a nonempty set R endowed with two binary operations [direct sum]R and [cross product]R such that

• [direct sum]R is associative and commutative with zero element εR;

• [cross product]R is associative, distributes over [direct sum]R, and has unit element e R;

• εR is absorbing for [cross product]R.

Such a semiring is denoted by R = (R, [direct sum]R, [cross product]R, εR, eR). If [cross product]R is commutative, then R is called commutative, and if [direct sum]R is idempotent, then it is called idempotent.

Max-plus algebra is an example of a commutative and idempotent semiring. Are there other meaningful semirings? The answer is yes, and a few examples are listed below.

Example 1.1.1

• Identify [direct sum]R with conventional addition, denoted by +, and [cross product]R with conventional multiplication, denoted by x. Then the zero and unit element are εR = 0 and eR = 1, respectively. The object Rst = (R, +, ×, 0, 1) -the subscript st refers to "standard" -is an instance of a semiring over the real numbers. Since conventional multiplication is commutative, Rstis a commutative semiring. Note that Rstfails to be idempotent. However, as is well known, Rstis a ring and even a field with respect to the operations + and ×. See the notes section for some further remarks on semirings and rings.

• Min-plus algebra is defined as Rmin = (Rmin, [direct sum]', [cross product], ε', e), where Rmin = R [union] {+∞}, [cross product]' is the operation defined by a [cross product]' b [??] min(a,b) for all a, b [member of] Rmin, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that Rminis an idempotent, commutative semiring.

• Consider Rmin,max = ([??], [direct sum]', [direct sum], ε' ε), with [??] = R [union] {ε, ε'}, and set ε[direct sum]ε' = ε' [direct sum] ε = ε'. Then Rmin,maxis an idempotent, commutative semiring. In the same vein, Rmax,min = ([??], [direct sum], [direct sum]', ε, ε') is an idempotent, commutative semiring provided that one defines ε [direct sum]' ε' = ε' [direct sum]' ε = ε.

• As a last example of a semiring of a somewhat different nature, let S be a nonempty set. Denote the set of all subsets of S by R; then (R, [union], [intersection], Ø, S), with Ø the empty set, and [union] and [intersection] the set-theoretic union and intersection, respectively, is a commutative, idempotent semiring. The same applies to (R, [union], [intersection], S, Ø).

The above list of examples explains why we choose an algebraic approach. Any statement that is proved for a semiring will immediately hold in any of the above algebras. Apart from the structural insight this provides into the relationship between the different algebras, the algebraic approach also saves a lot of work.

To illustrate this, consider the following problem. Is it possible to define inverse elements (i.e., inverse with respect to the [direct sum]R operation) in an idempotent semiring? For example, consider an idempotent semiring R = (R, [direct sum]R, [cross product]R, εR, eR), with JR. included in R, such as the max-plus or min-plus semiring. For example, is it possible to find a solution of

5 [direct sum]R x = 3? (1.4)

As in conventional algebra, it is tempting to subtract 5 on both sides of the above equation in order to obtain

x = 3 [direct sum]R ( -5)

as a solution. However, is it possible to give meaning to -5 in the above equation? Take, for example, max-plus algebra. Then, equation (1.4) reads

max(5, x) = 3. (1.5)

Obviously, there exists no number that makes equation (1.5) true. On the other hand, in min-plus algebra, equation (1.5) reads

min(5,x) = 3

and has the solution x = 3. Now interchange the numbers 3 and 5 in equation (1.4), yielding 3 [direct sum]Rx = 5. This equation has no solution in min-plus algebra and has the obvious solution x = 5 in max-plus algebra.

Whether an equation has a solution may depend on the algebra. This raises the question whether a particular semiring (i.e., a particular interpretation of the symbols [direct sum]R, [cross product]R, eR, and εR) exists such that all equations of type (1.4) can be solved. The following lemma provides an answer.

For A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and α [member of] Rmax, the scalar multiple α [cross product] A is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.9)

for i [member of] [??]and j [member of] [??]. For example, let A be defined as in (1.8) and take α = 2; then [2 [cross product] A]11 = 2 [cross product] e = 2 + 0 = 2. Likewise, it follows that [2 [cross product] A]12 = ε, [2 [cross product] A]21 = 5, and [2 [cross product] A]22 = 4, yielding, in matrix notation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For matrices A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the matrix product A [cross product] B is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for i [member of] [??] and k [member of] [??]. This is just like in conventional algebra with + replaced by max and x by +. Notice that A [cross product] B [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], i.e., has n rows and m columns. For example, let A and B be defined as in (1.8); then the elements of A [cross product] B are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

yielding, in matrix notation,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Notice that the matrix product in general fails to be commutative. Indeed, for the above A and B

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let E (n, m) denote the n × m matrix with all elements equal to ε, and denote by E(n, m) the n × m matrix defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If n = m, then E(n, n) is called then n × n identity matrix. When their dimensions are clear from the context, ε(n, m) and E(n, m) will also be written as ε and E, respectively. It is easily checked (see exercise 5) that any matrix A [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].