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).
Previous Page Next Page