1.5 You name it—we have it 13

This crucial observation is emphasized by renaming the two basic

operations into new “multiplication” and “addition”:

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

The previous identity takes the more familiar shape of the dis-

tributive law:

a (b ⊕ c) = a b ⊕ a c.

Of course, operations and ⊕ are commutative and associative.

After recycling the traditional shorthand

xn

= x · · · x (n times),

we can introduce polynomials as well as matrix multiplication,

determinants, etc. For example, the tropical determinant of the

matrix A = (aij ) is defined by evaluating the expansion formula

(see page 9) tropically and ignoring the signs of permutations σ

involved in the classical formula for determinant [396,

408]:8

dettrA =

σ∈Symn

(a1,σ(1) · · · an,σ(n))

= max

σ∈Symn

(a1,σ(1) + · · · + an,σ(n)).

Here the “sum” is taken over the set Symn of all permutations of

indices 1, . . . , n; for example,

dettr

a b

c d

= max(a + d, b + c).

Therefore the “sum” involves n! “monomials”—exactly as in the

case of ordinary determinants. Let us return for a second to our

discussion of the complexity of the evaluation of determinants in

two models of computation: choice-based and choiceless. It is not

obvious at all that a tropical determinant can be evaluated us-

ing O(n3) elementary operations—but it is true. The evaluation

of the tropical determinant is the classical assignment problem in

discrete optimization and the bounds for its complexity are well

known [400, Corollary 17.4b]. Indeed, finding the value of the trop-

ical determinant amounts to finding a permutation i → σ(i) which

maximizes the sum

a1,σ(1) + · · · + an,σ(n).

This is an old problem of applied discrete optimization: a company

has bought n machines M1,. . . , Mn which have to be assigned to

n factories F1,.. . , Fn; the expected profit from assigning machine

Mi to factory Fj is aij ; find the assignment

Mi → Fσ(i)

which maximizes the expected profit

a1,σ(1) + · · · + an,σ(n).