Tropical Convexity

Mike Develin and Bernd Sturmfels

Received: August 28, 2003 Revised: January 21, 2004

Communicated by Günter Ziegler

Abstract. The notions of convexity and convex polytopes are introduced in the setting of tropical geometry. Combinatorial types of tropical polytopes are shown to be in bijection with regular triangulations of products of two simplices. Applications to phylogenetic trees are discussed.

2000 Mathematics Subject Classification: 52A30; 92B10

1 Introduction

The tropical semiring (ℝ, ⊕, ⊙) is the set of real numbers with the arithmetic operations of tropical addition, which is taking the minimum of two numbers, and tropical multiplication, which is ordinary addition. Thus the two arithmetic operations are defined as follows:

a ⊕ b := min(a, b)  and  a ⊙ b := a + b.

The n-dimensional space ℝ^{n} is a semimodule over the tropical semiring, with tropical addition

(x_{1}, …, x_{n}) ⊕ (y_{1}, …, y_{n}) = (x_{1} ⊕ y_{1}, …, x_{n} ⊕ y_{n}),

and tropical scalar multiplication

c ⊙ (x_{1}, x_{2}, …, x_{n}) = (c ⊙ x_{1}, c ⊙ x_{2}, …, c ⊙ x_{n}).

The semiring (ℝ, ⊕, ⊙) and its semimodule ℝ^{n} obey the usual distributive and associative laws. The purpose of this paper is to propose a tropical theory of convex polytopes. Convexity in arbitrary idempotent semimodules was introduced by Cohen, Gaubert and Quadrat [3] and Litvinov, Maslov and Shpiz [13]. Some of our results (such as Theorem 23 and Propositions 20 and 21) are known in a different guise in idempotent analysis. Our objective is to provide a combinatorial approach to convexity in the tropical semiring which is consistent with the recent developments in tropical algebraic geometry (see [15], [18], [20]). The connection to tropical methods in representation theory (see [12], [16]) is less clear and deserves further study. There are many notions of discrete convexity in the computational geometry literature, but none of them seems to be quite like tropical convexity. For instance, the notion of directional convexity studied by Matoušek [14] has similar features but it is different and much harder to compute with. A subset S of ℝ^{n} is called tropically convex if the set S contains the point a ⊙ x ⊕ b ⊙ y for all x, y ∈ S and all a, b ∈ ℝ. The tropical convex hull of a given subset V ⊂ ℝ^{n} is the smallest tropically convex subset of ℝ^{n} which contains V. We shall see in Proposition 4 that the tropical convex hull of V coincides with the set of all tropical linear combinations

a_{1}⊙v_{1} ⊕ a_{2}⊙v_{2} ⊕ ⋯ ⊕ a_{r}⊙v_{r} , where v_{1}, …, v_{r} ∈ V and a_{1}, …, a_{r} ∈ ℝ. (1)

Any tropically convex subset S of ℝ^{n} is closed under tropical scalar multiplication, ℝ ⊙ S ⊆ S. In other words, if x ∈ S then x + λ(1, …, 1) ∈ S for all λ ∈ ℝ. We will therefore identify the tropically convex set S with its image in the (n − 1)-dimensional tropical projective space

𝕋ℙ^{n−1} = ℝ^{n}/(1, …, 1)ℝ.

Basic properties of (tropically) convex subsets in 𝕋ℙ^{n−1} will be presented in Section 2. In Section 3 we introduce tropical polytopes and study their combinatorial structure. A tropical polytope is the tropical convex hull of a finite subset V in 𝕋ℙ^{n−1}. Every tropical polytope is a finite union of convex polytopes in the usual sense: given a set V = {v_{1}, …, v_{n}}, their convex hull has a natural decomposition as a polyhedral complex, which we call the tropical complex generated by V. The following main result will be proved in Section 4:

Theorem 1. The combinatorial types of tropical complexes generated by a set of r vertices in 𝕋ℙ^{n−1} are in natural bijection with the regular polyhedral subdivisions of the product of two simplices Δ_{n−1} × Δ_{r−1}.

This implies a remarkable duality between tropical (n − 1)-polytopes with r vertices and tropical (r − 1)-polytopes with n vertices. Another consequence of Theorem 1 is a formula for the f-vector of a generic tropical complex. In Section 5 we discuss applications of tropical convexity to phylogenetic analysis, extending known results on injective hulls of finite metric spaces (cf. [7], [8], [9] and [20]).

(0, 0, 0) (0, 0, −2)  (0, 3, 0) (0, \frac{3}{2}, −1)  (0, 0, 1) (0, −1, −2) (0, 0, −1)  (0, 0, 2)

Figure 1: Tropical convex sets and tropical line segments in 𝕋ℙ^{2}.

2 Tropically convex sets

We begin with two pictures of tropical convex sets in the tropical plane 𝕋ℙ^{2}. A point (x_{1}, x_{2}, x_{3}) ∈ 𝕋ℙ^{2} is represented by drawing the point with coordinates (x_{2}−x_{1}, x_{3}−x_{1}) in the plane of the paper. The triangle on the left hand side in Figure 1 is tropically convex, but it is not a tropical polytope because it is not the tropical convex hull of finitely many points. The thick edges indicate two tropical line segments. The picture on the right hand side is a tropical triangle, namely, it is the tropical convex hull of the three points (0, 0, 1), (0, 2, 0) and (0, −1, −2) in the tropical plane 𝕋ℙ^{2}. The thick edges represent the tropical segments connecting any two of these three points. We next show that tropical convex sets enjoy many of the features of ordinary convex sets.

Theorem 2. The intersection of two tropically convex sets in ℝ^{n} or in 𝕋ℙ^{n−1} is tropically convex. The projection of a tropically convex set onto a coordinate hyperplane is tropically convex. The ordinary hyperplane {x_{i} − x_{j} = l} is tropically convex, and the projection map from this hyperplane to ℝ^{n−1} given by eliminating x_{i} is an isomorphism of tropical semimodules. Tropically convex sets are contractible spaces. The Cartesian product of two tropically convex sets is tropically convex.

Proof. We prove the statements in the order given. If S and T are tropically convex, then for any two points x, y ∈ S ∩T, both S and T contain the tropical line segment between x and y, and consequently so does S ∩T. Therefore S ∩T is tropically convex by definition. Suppose S is a tropically convex set in ℝ^{n}. We wish to show that the image of S under the coordinate projection ϕ : ℝ^{n} → ℝ^{n−1}, (x_{1}, x_{2}, …, x_{n}) ↦ (x_{2}, …, x_{n}) is a tropically convex subset of ℝ^{n−1}. If x, y ∈ S then we have the obvious identity

ϕ(c ⊙ x ⊕ d ⊙ y) = c ⊙ ϕ(x) ⊕ d ⊙ ϕ(y).

This means that ϕ is a homomorphism of tropical semimodules. Therefore, if S contains the tropical line segment between x and y, then ϕ(S) contains the tropical line segment between ϕ(x) and ϕ(y) and hence is tropically convex. The same holds for the induced map ϕ : 𝕋ℙ^{n−1} → 𝕋ℙ^{n−2}. Most ordinary hyperplanes in ℝ^{n} are not tropically convex, but we are claiming that hyperplanes of the special form x_{i} − x_{j} = k are tropically convex. If x and y lie in that hyperplane then x_{i} − y_{i} = x_{j} − y_{j}. This last equation implies the following identity for any real numbers c, d ∈ ℝ:

(c ⊙ x ⊕ d ⊙ y)_{i} − (c ⊙ x ⊕ d ⊙ y)_{j} = min (x_{i}+c, y_{i}+d) − min (x_{j}+c, y_{j}+d) = k.

Hence the tropical line segment between x and y also lies in the hyperplane {x_{i} − x_{j} = k}. Consider the map from {x_{i} − x_{j} = k} to ℝ^{n−1} given by deleting the i-th coordinate. This map is injective: if two points differ in the x_{i} coordinate they must also differ in the x_{j} coordinate. It is clearly surjective because we can recover an i-th coordinate by setting x_{i} = x_{j} + k. Hence this map is an isomorphism of ℝ-vector spaces and it is also an isomorphism of (ℝ, ⊕, ⊙)- semimodules. Let S be a tropically convex set in ℝ^{n} or 𝕋ℙ^{n−1}. Consider the family of hyperplanes H_{l} = {x_{1} − x_{2} = l} for l ∈ ℝ. We know that the intersection S ∩ H_{l} is tropically convex, and isomorphic to its (convex) image under the map deleting the first coordinate. This image is contractible by induction on the dimension n of the ambient space. Therefore, S ∩ H_{l} is contractible. The result then follows from the topological result that if S is connected, which all tropically convex sets obviously are, and if S ∩ H_{l} is contractible for each l, then S itself is also contractible. Suppose that S ⊂ ℝ^{n} and T ⊂ ℝ^{m} are tropically convex. Our last assertion states that S × T is a tropically convex subset of ℝ^{n+m}. Take any (x, y) and (x′, y′) in S × T and c, d ∈ ℝ. Then

c ⊙ (x, y) ⊕ d ⊙ (x′, y′) = ( c ⊙ x ⊕ d ⊙ x′ , c ⊙ y ⊕ d ⊙ y′ )

lies in S × T since S and T are tropically convex.

We next give a more precise description of what tropical line segments look like.

Proposition 3. The tropical line segment between two points x and y in 𝕋ℙ^{n−1} is the concatenation of at most n − 1 ordinary line segments. The slope of each line segment is a zero-one vector.

Proof. After relabeling the coordinates of x = (x_{1}, , …, x_{n}) and y = (y_{1}, …, y_{n}), we may assume

y_{1} − x_{1} ≤ y_{2} − x_{2} ≤ ⋯ ≤ y_{n} − x_{n}.  (2)

The following points lie in the given order on the tropical segment between x and y:

x = (y_{1} − x_{1}) ⊙ x ⊕ y = (y_{1}, y_{1}−x_{1}+x_{2}, …, y_{1}−x_{1}+x_{n−1}, y_{1}−x_{1}+x_{n})
(y_{2} − x_{2}) ⊙ x ⊕ y = (y_{1}, y_{2}, y_{2}−x_{2}+x_{3}, …, y_{2}−x_{2}+x_{n−1}, y_{2}−x_{2}+x_{n})
(y_{3} − x_{3}) ⊙ x ⊕ y = (y_{1}, y_{2}, y_{3}, …, y_{3}−x_{3}+x_{n−1}, y_{3}−x_{3}+x_{n})
⋮  ⋮  ⋮
(y_{n−1}−x_{n−1}) ⊙ x ⊕ y = (y_{1}, y_{2}, y_{3}, …, y_{n−1}, y_{n−1}−x_{n−1}+x_{n})
y = (y_{n} − x_{n}) ⊙ x ⊕ y = (y_{1}, y_{2}, y_{3}, …, y_{n−1}, y_{n}).

Between any two consecutive points, the tropical line segment agrees with the ordinary line segment, which has slope (0, 0, …, 0, 1, 1, …, 1). Hence the tropical line segment between x and y is the concatenation of at most n − 1 ordinary line segments, one for each strict inequality in (2).

This description of tropical segments shows an important feature of tropical polytopes: their edges use a limited set of directions. The following result characterizes the tropical convex hull.

Proposition 4. The smallest tropically convex subset of 𝕋ℙ^{n−1} which contains a given set V coincides with the set of all tropical linear combinations (1). We denote this set by tconv(V).

Proof. Let x = ⨁_{i=1}^{r} a_{i}⊙v_{i} be the point in (1). If r ≤ 2 then x is clearly in the tropical convex hull of V. If r > 2 then we write x = a_{1} ⊙v_{1} ⊕ (⨁_{i=2}^{r} a_{i} ⊙v_{i}). The parenthesized vector lies the tropical convex hull, by induction on r, and hence so does x. For the converse, consider any two tropical linear combinations x = ⨁_{i=1}^{r} c_{i}⊙v_{i} and y = ⨁_{j=1}^{r} d_{i}⊙v_{i}. By the distributive law, a⊙x ⊕ b⊙y is also a tropical linear combination of v_{1}, …, v_{r} ∈ V. Hence the set of all tropical linear combinations of V is tropically convex, so it contains the tropical convex hull of V.

If V is a finite subset of 𝕋ℙ^{n−1} then tconv(V) is a tropical polytope. In Figure 2 we see three small examples of tropical polytopes. The first and second are tropical convex hulls of three points in 𝕋ℙ^{2}. The third tropical polytope lies in 𝕋ℙ^{3} and is the union of three squares. One of the basic results in the usual theory of convex polytopes is Carathéodory’s theorem. This theorem holds in the tropical setting.

Proposition 5 (Tropical Carathéodory’s Theorem). If x is in the tropical convex hull of a set of r points v_{i} in 𝕋ℙ^{n−1}, then x is in the tropical convex hull of at most n of them.

v_{2} = (0, 2, 0) v_{3} = (0, 1, −2) v_{2} = (0, 2, 0) v_{1} = (0, 0, 1) v_{3} = (0, −2, −2) v_{1} = (0, 0, 2)  v_{2} = (0, 1, 0, 1) v_{3} = (0, 1, 1, 0) v_{1} = (0, 0, 1, 1)

Figure 2: Three tropical polytopes. The first two live in 𝕋ℙ^{2}, the last in 𝕋ℙ^{3}.

Proof. Let x = ⨁_{i=1}^{r} a_{i} ⊙ v_{i} and suppose r > n. For each coordinate j ∈ {1, …, n}, there exists an index i ∈ {1, …, r} such that x_{j} = c_{i} + v_{ij}. Take a subset I of {1, …, r} composed of one such i for each j. Then we also have x = ⨁_{i∈I} a_{i} ⊙ v_{i}, where #(I) ≤ n.

The basic theory of tropical linear subspaces in 𝕋ℙ^{n−1} was developed in [18] and [20]. Recall that the tropical hyperplane defined by a tropical linear form a_{1} ⊙ x_{1} ⊕ a_{2} ⊙ x_{2} ⊕ ⋯ ⊕ a_{n} ⊙ x_{n} consists of all points x = (x_{1}, x_{2}, …, x_{n}) in 𝕋ℙ^{n−1} such that the following holds (in ordinary arithmetic):

a_{i} + x_{i} = a_{j} + x_{j} = min{a_{k} + x_{k} : k = 1, …, n} for some indices i ≠ j.

(3)

Just like in ordinary geometry, hyperplanes are convex sets:

Proposition 6. Tropical hyperplanes in 𝕋ℙ^{n−1} are tropically convex.

Proof. Let H be the hyperplane defined by (3). Suppose that x and y lie in H and consider any tropical linear combination z = c ⊙ x ⊕ d ⊙ y. Let i be an index which minimizes a_{i} +z_{i}. We need to show that this minimum is attained at least twice. By definition, z_{i} is equal to either c + x_{i} or d + y_{i}, and, after permuting x and y, we may assume z_{i} = c + x_{i} ≤ d + y_{i}. Since, for all k, a_{i} + z_{i} ≤ a_{k} + z_{k} and z_{k} ≤ c + x_{k}, it follows that a_{i} + x_{i} ≤ a_{k} + x_{k} for all k, so that a_{i} + x_{i} achieves the minimum of {a_{1} + x_{1}, …, a_{n} + x_{n}}. Since x is in H, there exists some index j ≠ i for which a_{i} + x_{i} = a_{j} + x_{j}. But now a_{j} + z_{j} ≤ a_{j} + c + x_{j} = c + a_{i} + x_{i} = a_{i} + z_{i}. Since a_{i} + z_{i} is the minimum of all a_{j} + z_{j}, the two must be equal, and this minimum is obtained at least twice as desired.

Proposition 6 implies that if V is a subset of 𝕋ℙ^{n−1} which happens to lie in a tropical hyperplane H, then its tropical convex hull tconv(V) will lie in H as well. The same holds for tropical planes of higher codimension. Recall that every tropical plane is an intersection of tropical hyperplanes [20]. But the converse does not hold: not every intersection of tropical hyperplanes qualifies as a tropical plane (see [18, §5]). Proposition 6 and the first statement in Theorem 2 imply:

Corollary 7. Tropical planes in 𝕋ℙ^{n−1} are tropically convex.

A theorem in classical geometry states that every point outside a closed convex set can be separated from the convex set by a hyperplane. The same statement holds in tropical geometry. This follows from the results in [3]. Some caution is needed, however, since the definition of hyperplane in [3] differs from our definition of hyperplane, as explained in [18]. In our definition, a tropical hyperplane is a fan which divides 𝕋ℙ^{n−1} into n convex cones, each of which is also tropically convex. Rather than stating the most general separation theorem, we will now focus our attention on tropical polytopes, in which case the separation theorem is the Farkas Lemma stated in the next section.

3 Tropical polytopes and cell complexes

Throughout this section we fix a finite subset V = {v_{1}, v_{2}, …, v_{r}} of tropical projective space 𝕋ℙ^{n−1}. Here v_{i} = (v_{i1}, v_{i2}, …, v_{in}). Our goal is to study the tropical polytope P = tconv(V). We begin by describing the natural cell decomposition of 𝕋ℙ^{n−1} induced by the fixed finite subset V. Let x be any point in 𝕋ℙ^{n−1}. The type of x relative to V is the ordered n-tuple (S_{1}, …, S_{n}) of subsets S_{j} ⊆ {1, 2, …, r} which is defined as follows: An index i is in S_{j} if

v_{ij} − x_{j} = min(v_{i1} − x_{1}, v_{i2} − x_{2}, …, v_{in} − x_{n}).

Equivalently, if we set λ_{i} = min{ λ ∈ ℝ : λ ⊙ v_{i} ⊕ x = x } then S_{j} is the set of all indices i such that λ_{i} ⊙ v_{i} and x have the same j-th coordinate. We say that an n-tuple of indices S = (S_{1}, …, S_{n}) is a type if it arises in this manner. Note that every i must be in some S_{j}.

Example 8. Let r = n = 3, v_{1} = (0, 0, 2), v_{2} = (0, 2, 0) and v_{3} = (0, 1, −2). There are 30 possible types as x ranges over the plane 𝕋ℙ^{2}. The corresponding cell decomposition has six convex regions (one bounded, five unbounded), 15 edges (6 bounded, 9 unbounded) and 6 vertices. For instance, the point x = (0, 1, −1) has type(x) = ({2}, {1}, {3}) and its cell is a bounded pentagon. The point x′ = (0, 0, 0) has type(x′) = ({1, 2}, {1}, {2, 3}) and its cell is one of the six vertices. The point x′′ = (0, 0, −3) has type(x′′) = {{1, 2, 3}, {1}, ∅) and its cell is an unbounded edge.

Our first application of types is the following separation theorem.

Proposition 9 (Tropical Farkas Lemma). For all x ∈ 𝕋ℙ^{n−1}, exactly one of the following is true.

(i) the point x is in the tropical polytope P = tconv(V), or (ii) there exists a tropical hyperplane which separates x from P.

The separation statement in part (ii) means the following: if the hyperplane is given by (3) and a_{k} + x_{k} = min(a_{1} + x_{1}, …, a_{n} + x_{n}) then a_{k} + y_{k} > min(a_{1} + y_{1}, …, a_{n} + y_{n}) for all y ∈ P.

Proof. Consider any point x ∈ 𝕋ℙ^{n−1}, with type(x) = (S_{1}, …, S_{n}), and let λ_{i} = min{ λ ∈ ℝ : λ ⊙ v_{i} ⊕ x = x } as before. We define

π_{V} (x) = λ_{1} ⊙ v_{1} ⊕ λ_{2} ⊙ v_{2} ⊕ ⋯ ⊕ λ_{r} ⊙ v_{r}.  (4)

There are two cases: either π_{V} (x) = x or π_{V} (x) ≠ x. The first case implies (i). Since (i) and (ii) clearly cannot occur at the same time, it suffices to prove that the second case implies (ii). Suppose that π_{V} (x) ≠ x. Then S_{k} is empty for some index k ∈ {1, …, n}. This means that v_{ik} +λ_{i} −x_{k} > 0 for i = 1, 2, …, r. Let ε > 0 be smaller than any of these r positive reals. We now choose our separating tropical hyperplane (3) as follows:

a_{k} := −x_{k} − ε  and  a_{j} := −x_{j} for j ∈ {1, …, n}\{k}. (5)

This certainly satisfies a_{k} + x_{k} = min(a_{1} + x_{1}…. , a_{n} + x_{n}). Now, consider any point y = ⨁_{i=1}^{r} c_{i} ⊙ v_{i} in tconv(V). Pick any m such that y_{k} = c_{m} + v_{mk}. By definition of the λ_{i}, we have x_{k} ≤ λ_{m} + v_{mk} for all k, and there exists some j with x_{j} = λ_{m} + v_{mj}. These equations and inequalities imply

a_{k} + y_{k} = a_{k} + c_{m} + v_{mk} = c_{m} + v_{mk} − x_{k} − ε > c_{m} − λ_{m}

= c_{m} + v_{mj} − x_{j} ≥ y_{j} − x_{j} = a_{j} + y_{j} ≥ min(a_{1} + y_{1}, …, a_{n} + y_{n}).

Therefore, the hyperplane defined by (5) separates x from P as desired.

The construction in (4) defines a map π_{V} : 𝕋ℙ^{n−1} → P whose restriction to P is the identity. This map is the tropical version of the nearest point map onto a closed convex set in ordinary geometry. Such maps were studied in [3] for convex subsets in arbitrary idempotent semimodules. If S = (S_{1}, …, S_{n}) and T = (T_{1}, …, T_{n}) are n-tuples of subsets of {1, 2, …, r}, then we write S ⊆ T if S_{j} ⊆ T_{j} for j = 1, …, n. We also consider the set of all points whose type contains S:

X_{S} := { x ∈ 𝕋ℙ^{n−1} : S ⊆ type(x)}.

Lemma 10. The set X_{S} is a closed convex polyhedron (in the usual sense). More precisely,

X_{S} = { x ∈ 𝕋ℙ^{n−1} : x_{k} −x_{j} ≤ v_{ik} −v_{ij} for all j, k ∈ {1, …, n} with i ∈ S_{j} }. (6)

v_{1} v_{3}  v_{2}

Figure 3: The region X_{(2,1,3)} in the tropical convex hull of v_{1}, v_{2} and v_{3}.

Proof. Let x ∈ 𝕋ℙ^{n−1} and T = type(x). First, suppose x is in X_{S}. Then S ⊆ T. For every i, j, k such that i ∈ S_{j}, we also have i ∈ T_{j}, and so by definition we have v_{ij} − x_{j} ≤ v_{ik} − x_{k}, or x_{k} − x_{j} ≤ v_{ik} − v_{ij}. Hence x lies in the set on the right hand side of (6). For the proof of the reverse inclusion, suppose that x lies in the right hand side of (6). Then, for all i, j with i ∈ S_{j}, and for all k, we have v_{ij} −x_{j} ≤ v_{ik} −x_{k}. This means that v_{ij} −x_{j} = min(v_{i1} −x_{1}, …, v_{in} −x_{n}) and hence i ∈ T_{j}. Consequently, for all j, we have S_{j} ⊂ T_{j}, and so x ∈ X_{S}.

As an example for Lemma 10, we consider the region X_{(2,1,3)} in the tropical convex hull of v_{1} = (0, 0, 2), v_{2} = (0, 2, 0), and v_{3} = (0, 1, −2). This region is defined by six linear inequalities, one of which is redundant, as depicted in Figure 3. Lemma 10 has the following immediate corollaries.

Corollary 11. The intersection X_{S} ∩ X_{T} is equal to the polyhedron X_{S∪T}.

Proof. The inequalities defining X_{S∪T} are precisely the union of the inequalities defining X_{S} and X_{T}, and points satisfying these inequalities are precisely those in X_{S} ∩ X_{T}.

Corollary 12. The polyhedron X_{S} is bounded if and only if S_{j} ≠ ∅ for all j = 1, 2, …, n.

Proof. Suppose that S_{j} ≠ ∅ for all j = 1, 2, …, n. Then for every j and k, we can find i ∈ S_{j} and m ∈ S_{k}, which via Lemma 10 yield the inequalities v_{mk} − v_{mj} ≤ x_{k} − x_{j} ≤ v_{ik} − v_{ij}. This implies that each x_{k} − x_{j} is bounded on X_{S}, which means that X_{S} is a bounded subset of 𝕋ℙ^{n−1}. Conversely, suppose some S_{j} is empty. Then the only inequalities involving x_{j} are of the form x_{j} − x_{k} ≤ c_{jk}. Consequently, if any point x is in S_{j}, so too is x − ke_{j} for k > 0, where e_{j} is the j-th basis vector. Therefore, in this case, X_{S} is unbounded.

Corollary 13. Suppose we have S = (S_{1}, …, S_{n}), with S_{1} ∪ ⋯ ∪ S_{n} = {1, …, r}. Then if S ⊆ T, X_{T} is a face of X_{S}, and furthermore all faces of X_{S} are of this form.

Proof. For the first part, it suffices to prove that the statement is true when T covers S in the poset of containment, i.e. when T_{j} = S_{j} ∪ {i} for some j ∈ {1, …, n} and i ∉ S_{j}, and T_{k} = S_{k} for k ≠ j. We have the inequality presentation of X_{S} given by Lemma 10. By the same lemma, the inequality presentation of X_{T} consists of the inequalities defining X_{S} together with the inequalities

{x_{k} − x_{j} ≤ v_{ik} − v_{ij} | k ∈ {1, …, n}}.  (7)

By assumption, i is in some S_{m}. We claim that X_{T} is the face of S defined by the equality

x_{m} − x_{j} = v_{im} − v_{ij}.  (8)

Since X_{S} satisfies the inequality x_{j} − x_{m} ≤ v_{ij} − v_{im}, (8) defines a face F of S. The inequality x_{m} − x_{j} ≤ v_{im} − v_{ij} is in the set (7), so (8) is valid on X_{T} and X_{T} ⊆ F. However, any point in F, being in X_{S}, satisfies x_{k}−x_{m} ≤ v_{ik}−v_{im} for all k ∈ {1, …, n}. Adding (8) to these inequalities proves that the inequalities (7) are valid on F, and hence F ⊆ X_{T}. So X_{T} = F as desired. By the discussion in the proof of the first part, prescribing equality in the facetdefining inequality x_{k} − x_{j} ≤ v_{ik} − v_{ij} yields X_{T}, where T_{k} = S_{k} ∪ {i} and T_{j} = S_{j} for j ≠ k. Therefore, all facets of X_{S} can be obtained as regions X_{T}, and it follows recursively that all faces of X_{S} are of this form.

Corollary 14. Suppose that S = (S_{1}, …, S_{n}) is an n-tuple of indices satisfying S_{1} ∪ ⋯ ∪ S_{n} = {1, …, r}. Then X_{S} is equal to X_{T} for some type T.

Proof. Let x be a point in the relative interior of X_{S}, and let T = type(x). Since x ∈ X_{S}, T contains S, and by Lemma 13, X_{T} is a face of X_{S}. However, since x is in the relative interior of X_{S}, the only face of X_{S} containing x is X_{S} itself, so we must have X_{S} = X_{T} as desired.

We are now prepared to state our main theorem in this section.

Theorem 15. The collection of convex polyhedra X_{S}, where S ranges over all types, defines a cell decomposition C_{V} of 𝕋ℙ^{n−1}. The tropical polytope P = tconv(V) equals the union of all bounded cells X_{S} in this decomposition.

Proof. Since each point has a type, it is clear that the union of the X_{S} is equal to 𝕋ℙ^{n−1}. By Corollary 13, the faces of X_{S} are equal to X_{U} for S ⊆ U, and by Corollary 14, X_{U} = X_{W} for some type W, and hence X_{U} is in our collection. The only thing remaining to check to show that this collection defines a cell decomposition is that X_{S} ∩ X_{T} is a face of both X_{S} and X_{T}, but X_{S} ∩ X_{T} = X_{S∪T} by Corollary 11, and X_{S∪T} is a face of X_{S} and X_{T} by Corollary 13. For the second assertion consider any point x ∈ 𝕋ℙ^{n−1} and let S = type(x). We have seen in the proof of the Tropical Farkas Lemma (Proposition 9) that x lies in P if and only if no S_{j} is empty. By Corollary 12, this is equivalent to the polyhedron X_{S} being bounded.

The collection of bounded cells X_{S} is referred to as the tropical complex generated by V; thus, Theorem 15 states that this provides a polyhedral decomposition of the polytope P = tconv(V). Different sets V may have the same tropical polytope as their convex hull, but generate different tropical complexes; the decomposition of a tropical polytope depends on the chosen generating set, although we will see later (Proposition 21) that there is a unique minimal generating set. Here is a nice geometric construction of the cell decomposition C_{V} of 𝕋ℙ^{n−1} induced by V = {v_{1}, …, v_{r}}. Let F be the fan in 𝕋ℙ^{n−1} defined by the tropical hyperplane (3) with a_{1} = ⋯ = a_{n} = 0. Two vectors x and y lie in the same relatively open cone of the fan F if and only if

{ j : x_{j} = min(x_{1}, …, x_{n}) } = { j : y_{j} = min(y_{1}, …, y_{n}) }.

If we translate the negative of F by the vector v_{i} then we get a new fan which we denote by v_{i} − F. Two vectors x and y lie in the same relatively open cone of the fan v_{i} − F if and only if

{ j : x_{j} − v_{ij} = max(x_{1} − v_{i1}, …, x_{n} − v_{in}) }
= { j : y_{j} − v_{ij} = max(y_{1} − v_{i1}, …, y_{n} − v_{in}) }.

Proposition 16. The cell decomposition C_{V} is the common refinement of the r fans v_{i} − F.

Proof. We need to show that the cells of this common refinement are precisely the convex polyhedra X_{S}. Take a point x, with T = type(x) and define S_{x} = (S_{x1}, …, S_{xn}) by letting i ∈ S_{xj} whenever

x_{j} − v_{ij} = max(x_{1} − v_{i1}, …, x_{n} − v_{in}).  (9)

Two points x and y are in the relative interior of the same cell of the common refinement if and only if they are in the same relatively open cone of each fan; this is tantamount to saying that S_{x} = S_{y}. However, we claim that S_{x} = T. Indeed, taking the negative of both sides of (9) yields exactly the condition for i being in T_{j}, by the definition of type. Consequently, the condition for two points having the same type is the same as the condition for the two points being in the relative interior of the same chamber of the common refinement of the fans v_{1} − F, v_{2} − F, …, v_{r} − F.

(2,123,3)^{(123, 1, 3)}^{(1, 1, 23)}^{(12, 1, 3)}  ^{(2, 13, 3)}^{(2, 1, 23)}^{(23, 1, 3)}^{(12, 1, 23)}  ^{(2, 12, 3)} (2, 1, 3) ^{(23, 13, 3)}^{(2, 12, 23)}^{(1, 1, 123)}

Figure 4: A tropical complex expressed as the bounded cells in the common refinement of the fans v_{1} − F, v_{2} − F and v_{3} − F. Cells are labeled with their types.

An example of this construction is shown for our usual example, where v_{1} = (0, 0, 2), v_{2} = (0, 2, 0), and v_{3} = (0, 1, −2), in Figure 4. The next few results provide additional information about the polyhedron X_{S}. Let G_{S} denote the undirected graph with vertices {1, …, n}, where {j, k} is an edge if and only if S_{j} ∩ S_{k} ≠ ∅.

Proposition 17. The dimension d of the polyhedron X_{S} is one less than the number of connected components of G_{S}, and X_{S} is affinely and tropically isomorphic to some polyhedron X_{T} in 𝕋ℙ^{d}.

Proof. The proof is by induction on n. Suppose we have i ∈ S_{j} ∩ S_{k}. Then X_{S} satisfies the linear equation x_{k} − x_{j} = c where c = v_{ik} − v_{ij}. Eliminating the variable x_{k} (projecting onto 𝕋ℙ^{n−2}), X_{S} is affinely and tropically isomorphic to X_{T} where the type T is defined by T_{r} = S_{r} for r ≠ j and T_{j} = S_{j} ∪ S_{k}. The region X_{T} exists in the cell decomposition of 𝕋ℙ^{n−2} induced by the vectors w_{1}, …, w_{n} with w_{ir} = v_{ir} for r ≠ j, and w_{ij} = max(v_{ij}, v_{ik} − c). The graph G_{T} is obtained from the graph G_{S} by contracting the edge {j, k}, and thus has the same number of connected components. This induction on n reduces us to the case where all of the S_{j} are pairwise disjoint. We must show that X_{S} has dimension n − 1. Suppose not. Then X_{S} lies in 𝕋ℙ^{n−1} but has dimension less than n − 1. Therefore, one of the inequalities in (6) holds with equality, say x_{k} − x_{j} = v_{ik} − v_{ij} for all x ∈ X_{S}. The inequality “≤” implies i ∈ S_{j} and the inequality “≥” implies i ∈ S_{k}. Hence S_{j} and S_{k} are not disjoint, a contradiction.

The following proposition can be regarded as a converse to Lemma 10.

Proposition 18. Let R be any polytope in 𝕋ℙ^{n−1} defined by inequalities of the form x_{k} − x_{j} ≤ c_{jk}. Then R arises as a cell X_{S} in the decomposition C_{V} of 𝕋ℙ^{n−1} defined by some set V = {v_{1}, …, v_{n}}.

Proof. Define the vectors v_{i} to have coordinates v_{ij} = c_{ij} for i ≠ j, and v_{ii} = 0. (If c_{ij} did not appear in the given inequality presentation then simply take it to be a very large positive number.) Then by Lemma 10, the polytope in 𝕋ℙ^{n−1} defined by the inequalities x_{k} − x_{j} ≤ c_{jk} is precisely the unique cell of type (1, 2, …, n) in the tropical convex hull of {v_{1}, …, v_{n}}.

The region X_{S} is a polytope both in the ordinary sense and in the tropical sense.

Proposition 19. Every bounded cell X_{S} in the tropical complex generated by V is itself a tropical polytope, equal to the tropical convex hull of its vertices. The number of vertices of the polytope X_{S} is at most \binom{2n−2}{n−1} , and this bound is tight for all positive integers n.

Proof. By Proposition 17, if X_{S} has dimension d, it is affinely and tropically isomorphic to a region in the convex hull of a set of points in 𝕋ℙ^{d}, so it suffices to consider the full-dimensional case. The inequality presentation of Lemma 10 demonstrates that X_{S} is tropically convex for all S, since if two points satisfy an inequality of that form, so does any tropical linear combination thereof. Therefore, it suffices to show that X_{S} is contained in the tropical convex hull of its vertices. The proof is by induction on the dimension of X_{S}. All proper faces of X_{S} are polytopes X_{T} of lower dimension, and by induction are contained in the tropical convex hull of their vertices. These vertices are a subset of the vertices of X_{S}, and so this face is in the tropical convex hull. Take any point x = (x_{1}, …, x_{n}) in the interior of X_{S}. Since X_{S} has dimension n, we can travel in any direction from x while remaining in X_{S}. Let us travel in the (1, 0, …, 0) direction until we hit the boundary, to obtain points y_{1} = (x_{1} + b, x_{2}, …, x_{n}) and y_{2} = (x_{1} − c, x_{2}, …, x_{n}) in the boundary of X_{S}. These points are contained in the tropical convex hull by the inductive hypothesis, which means that x = y_{1} ⊕ c ⊙ y_{2} is also, completing the proof of the first assertion. For the second assertion, we consider the convex hull of all differences of unit vectors, e_{i} − e_{j}. This is a lattice polytope of dimension n − 1 and normalized volume \binom{2n−2}{n−1}. To see this, we observe that this polytope is tiled by n copies of the convex hull of the origin and the \binom{n}{2} vectors e_{i} − e_{j} with i < j. The other n − 1 copies are gotten by cyclic permutation of the coordinates. This latter polytope was studied by Gel’fand, Graev and Postnikov, who showed in [4, Theorem 2.3 (2)] that the normalized volume of this polytope equals the Catalan number \frac{1}{n} \binom{2n−2}{n−1}. We conclude that every complete fan whose rays are among the vectors e_{i} − e_{j} has at most \binom{2n−2}{n−1} maximal cones. This applies in particular to the normal fan of X_{S}, hence X_{S} has at most \binom{2n−2}{n−1} vertices. Since the configuration {e_{i} − e_{j}} is unimodular, the bound is tight whenever the fan is simplicial and uses all the rays e_{i} − e_{j}.

We close this section with two more results about arbitrary tropical polytopes in 𝕋ℙ^{n−1}.

Proposition 20. If P and Q are tropical polytopes in 𝕋ℙ^{n−1} then P ∩ Q is also a tropical polytope.

Proof. Since P and Q are both tropically convex, P ∩ Q must also be. Consequently, if we can find a finite set of points in P ∩Q whose convex hull contains all of P ∩ Q, we will be done. By Theorem 15, P and Q are the finite unions of bounded cells {X_{S}} and {X_{T} } respectively, so P ∩ Q is the finite union of the cells X_{S} ∩ X_{T}. Consider any X_{S} ∩ X_{T}. Using Lemma 10 to obtain the inequality representations of X_{S} and X_{T}, we see that this region is of the form dictated by Proposition 18, and therefore obtainable as a cell X_{W} in some tropical complex. By Proposition 19, X_{W} is itself a tropical polytope, and we can therefore find a finite set whose convex hull is equal to X_{S} ∩ X_{T}. Taking the union of these sets over all choices of S and T then gives us the desired set of points whose convex hull contains all of P ∩ Q.

Proposition 21. Let P ⊂ 𝕋ℙ^{n−1} be a tropical polytope. Then there exists a unique minimal set V such that P = tconv(V).

Proof. Suppose that P has two minimal generating sets, V = {v_{1}, …, v_{m}} and W = {w_{1}, …, w_{r}}. Write each element of W as w_{i} = ⊕_{j=1}^{m}c_{ij} ⊙ v_{j}. We claim that V ⊆ W. Consider v_{1} ∈ V and write

v_{1} = ⨁_{i=1}^{r} d_{i} ⊙ w_{i} = ⨁_{j=1}^{m} f_{j} ⊙ v_{j}  where f_{j} = min_{i}(d_{i} + c_{ij}). (10)

If the term f_{1} ⊙ v_{1} does not minimize any coordinate in the right-hand side of (10), then v_{1} is a linear combination of v_{2}, …, v_{m}, contradicting the minimality of V. However, if f_{1} ⊙ v_{1} minimizes any coordinate in this expression, it must minimize all of them, since (v_{1})_{j} − (v_{1})_{k} = (f_{1} ⊙ v_{1})_{j} − (f_{1} ⊙ v_{1})_{k}. In this case we get v_{1} = f_{1} ⊙ v_{1}, or f_{1} = 0. Pick any i for which f_{1} = d_{i} + c_{i1}; we claim that w_{i} = c_{i1} ⊙ v_{1}. Indeed, if any other term in w_{i} = ⊕_{j=1}^{m}c_{ij} ⊙ v_{j} contributed nontrivially to w_{i}, that term would also contribute to the expression on the right-hand side of (10), which is a contradiction. Consequently, V ⊆ W, which means V = W since both sets are minimal by hypothesis.

Like many of the results presented in this section, Propositions 20 and 21 parallel results on ordinary polytopes. We have already mentioned the tropical analogues of the Farkas Lemma and of Carathéodory’s Theorem (Propositions 5 and 9); Proposition 17 is analogous to the result that a polytope P ⊂ ℝ^{n} of dimension d is affinely isomorphic to some Q ⊂ ℝ^{d}. Proposition 19 hints at a duality between an inequality representation and a vertex representation of a tropical polytope; this duality has been studied in greater detail by Michael Joswig [11].

4 Subdividing products of simplices

Every set V = {v_{1}, …, v_{r}} of r points in 𝕋ℙ^{n−1} begets a tropical polytope P = tconv(V) equipped with a cell decomposition into the tropical complex generated by V. Each cell of this tropical complex is labelled by its type, which is an n-vector of finite subsets of {1, …, r}. Two configurations (and their corresponding tropical complexes) V and W have the same combinatorial type if the types occurring in their tropical complexes are identical; note that by Lemma 13, this implies that the face posets of these polyhedral complexes are isomorphic. With the definition in the previous paragraph, the statement of Theorem 1 has now finally been made precise. We will prove this correspondence between tropical complexes and subdivisions of products of simplices by constructing the polyhedral complex C_{P} in a higher-dimensional space. Let W denote the (r + n − 1)-dimensional real vector space ℝ^{r+n}/(1, …, 1, −1, …, −1). The natural coordinates on W are denoted (y, z) = (y_{1}, …, y_{r}, z_{1}, …, z_{n}). As before, we fix an ordered subset V = {v_{1}, …, v_{r}} of 𝕋ℙ^{n−1} where v_{i} = (v_{i1}, …, v_{in}). This defines the unbounded polyhedron

P_{V} = { (y, z) ∈ W : y_{i} + z_{j} ≤ v_{ij} for all i ∈ {1, …, r} and j ∈ {1, …, n} }. (11)

Lemma 22. There is a piecewise-linear isomorphism between the tropical complex generated by V and the complex of bounded faces of the (r + n − 1)- dimensional polyhedron P_{V}. The image of a cell X_{S} of C_{P} under this isomorphism is the bounded face {y_{i} + z_{j} = v_{ij} : i ∈ S_{j}} of the polyhedron P_{V}. That bounded face maps isomorphically to X_{S} via projection onto the z-coordinates.

Proof. Let F be a bounded face of P_{V}, and define S_{j} via i ∈ S_{j} if y_{i} + z_{j} = v_{ij} is valid on all of F. If some y_{i} or z_{j} appears in no equality, then we can subtract arbitrary positive multiples of that basis vector to obtain elements of F, contradicting the assumption that F is bounded. Therefore, each i must appear in some S_{j}, and each S_{j} must be nonempty. Since every y_{i} appears in some equality, given a specific z in the projection of F onto the z-coordinates, there exists a unique y for which (y, z) ∈ F, so this projection is an affine isomorphism from F to its image. We need to show that this image is equal to X_{S}. Let z be a point in the image of this projection, coming from a point (y, z) in the relative interior of F. We claim that z ∈ X_{S}. Indeed, looking at the jth coordinate of z, we find

−y_{i} + v_{ij} ≥ z_{j} for all i,  (12)
−y_{i} + v_{ij} = z_{j} for i ∈ S_{j}.  (13)

The defining inequalities of X_{S} are x_{j} −x_{k} ≤ v_{ij} −v_{ik} with i ∈ S_{j}. Subtracting the inequality −y_{i}+v_{ik} ≥ z_{k} from the equality in (13) yields that this inequality is valid on z as well. Therefore, z ∈ X_{S}. Similar reasoning shows that S = type(z). We note that the relations (12) and (13) can be rewritten elegantly in terms of the tropical product of a row vector and a matrix:

z = (−y) ⊙ V = ⨁_{i=1}^{r}(−y_{i}) ⊙ v_{i}.  (14)

For the reverse inclusion, suppose that z ∈ X_{S}. We define y = V ⊙ (−z). This means that

y_{i} = min(v_{i1} − z_{1}, v_{i2} − z_{2}, …, v_{in} − z_{n}).  (15)

We claim that (y, z) ∈ F. Indeed, we certainly have y_{i} +z_{j} ≤ v_{ij} for all i and j, so (y, z) ∈ P_{V}. Furthermore, when i ∈ S_{j}, we know that v_{ij} − z_{j} achieves the minimum in the right-hand side of (15), so that v_{ij} − z_{j} = y_{i} and y_{i} + z_{j} = v_{ij} is satisfied. Consequently, (y, z) ∈ F as desired. It follows immediately that the two complexes are isomorphic: if F is a face corresponding to X_{S} and G is a face corresponding to X_{T}, where S and T are both types, then X_{S} is a face of X_{T} if and only if T ⊆ S. However, by the discussion above, this is equivalent to saying that the equalities G satisfies (which correspond to T) are a subset of the equalities F satisfies (which correspond to S); this is true if and only if F is a face of G. So X_{S} is a face of X_{T} if and only if F is a face of G, which implies the isomorphism of complexes.

The boundary complex of the polyhedron P_{V} is polar to the regular subdivision of the product of simplices Δ_{r−1} ×Δ_{n−1} defined by the weights v_{ij}. We denote this regular polyhedral subdivision by (∂P_{V})^{∗}. Explicitly, a subset of vertices (e_{i}, e_{j}) of Δ_{r−1} × Δ_{n−1} forms a cell of (∂P_{V})^{∗} if and only if the equations y_{i} +z_{j} = v_{ij} indexed by these vertices specify a face of the polyhedron P_{V}. We refer to the book of De Loera, Rambau and Santos [5] for basics on polyhedral subdivisions. We now present the proof of the result stated in the introduction. Proof of Theorem 1: The poset of bounded faces of P_{V} is antiisomorphic to the poset of interior cells of the subdivision (∂P_{V})^{∗} of Δ_{r−1} × Δ_{n−1}. Since every full-dimensional cell of (∂P_{V})^{∗} is interior, the subdivision is uniquely determined by its interior cells. In other words, the combinatorial type of P_{V} is uniquely determined by the lists of facets containing each bounded face of P_{V}. These lists are precisely the types of regions in C_{P} by Lemma 22. This completes the proof.

Theorem 1, which establishes a bijection between the tropical complexes generated by r points in 𝕋ℙ^{n−1} and the regular subdivisions of a product of simplices Δ_{r−1} × Δ_{n−1}, has many striking consequences. First of all, we can pick off the types present in a tropical complex simply by looking at the cells present in the corresponding regular subdivision. In particular, if we have an interior cell M, the corresponding type appearing in the tropical complex is defined via S_{j} = {i ∈ [n] | (j, i) ∈ M}. It is worth noting that via the Cayley Trick [19], Theorem 1 is equivalent to saying that tropical complexes generated by r points in 𝕋ℙ^{n−1} are in bijection with the regular mixed subdivisions of the dilated simplex rΔ^{n−1}. This connection is expanded upon and employed in a paper with Francisco Santos [6]. Another astonishing consequence of Theorem 1 is the identification of the row span and column span of a matrix. This result can also be derived from [3, Theorem 42].

Theorem 23. Given any matrix M ∈ ℝ^{r×n}, the tropical complex generated by its column vectors is isomorphic to the tropical complex generated by its row vectors. This isomorphism is gotten by restricting the piecewise linear maps ℝ^{n} → ℝ^{r}, z ↦ M ⊙ (−z) and ℝ^{r} → ℝ^{n}, y ↦ (−y) ⊙ M.

Proof. By Theorem 1, the matrix M corresponds via the polyhedron P_{M} to a regular subdivision of Δ_{r−1} × Δ_{n−1}, and the complex of interior faces of this regular subdivision is combinatorially isomorphic to both the tropical complex generated by its row vectors, which are r points in 𝕋ℙ^{n−1}, and the tropical complex generated by its column vectors, which are n points in 𝕋ℙ^{r−1}. Furthermore, Lemma 22 tells us that the cell in P_{M} is affinely isomorphic to its corresponding cell in both tropical complexes. Finally, in the proof of Lemma 22, we showed that the point (y, z) in a bounded face F of P_{M} satisfies y = M ⊙ (−z) and z = (−y) ⊙ M. This point projects to y and z, and so the piecewise-linear isomorphism mapping these two complexes to each other is defined by the stated maps.

The common tropical complex of these two tropical polytopes is given by the complex of bounded faces of the common polyhedron P_{M}, which lives in a space of dimension r + n − 1; the tropical polytopes are unfoldings of this complex into dimensions r − 1 and n − 1. Theorem 23 also gives a natural bijection between the combinatorial types of tropical convex hulls of r points in 𝕋ℙ^{n−1} and the combinatorial types of tropical convex hulls of n points in 𝕋ℙ^{r−1}, incidentally proving that there are the same number of each. This duality statement extends a similar statement in [3]. Figure 5 shows the dual of the convex hull of {(0, 0, 2), (0, 2, 0), (0, 1, −2)}, also

B D = (0, 0, 0) F  E  C  A F D  C  B A E = (0, 0, 0)

Figure 5: A demonstration of tropical polytope duality.

a tropical triangle (here r = n = 3). For instance, we compute:

( \begin{matrix}0 & 0 & 2 \\ 0 & 2 & 0 \\ 0 & 1 & −2 \end{matrix} ) ( \begin{matrix}0 \\ 0 \\ −2 \end{matrix} ) = ( \begin{matrix}0 \\ −2 \\ −4 \end{matrix} ) .

This point is the image of the point (0, 0, 2) under this duality map. Note that duality does not preserve the generating set; the polytope on the right is the convex hull of points {F, D, B}, while the polytope on the left is the convex hull of points {F, A, C}. This is necessary, of course, since in general a polytope with r vertices is mapped to a polytope with n vertices, and r need not equal n as it does in our example. We now discuss the generic case when the subdivision (∂P_{V})^{∗} is a regular triangulation of Δ_{r−1}×Δ_{n−1}. We refer to [18, §5] for the geometric interpretation of the tropical determinant.

Proposition 24. For a configuration V of r points in 𝕋ℙ^{n−1} with r ≥ n the following are equivalent:

1. The regular subdivision (∂P_{V})^{∗} is a triangulation of Δ_{r−1} × Δ_{n−1}.

2. No k of the points in V have projections onto a k-dimensional coordinate subspace which lie in a tropical hyperplane, for any 2 ≤ k ≤ n.

3. No k × k-submatrix of the r × n-matrix (v_{ij}) is tropically singular, i.e. has vanishing tropical determinant, for any 2 ≤ k ≤ n.

Proof. The last equivalence is proven in [18, Lemma 5.1]. We will prove that (1) and (3) are equivalent. The tropical determinant of a k by k matrix M is the tropical polynomial ⊕_{σ∈S_{k}}(⊙_{i=1}^{k}M_{iσ(i)}). The matrix M is tropically singular if the minimum min_{σ∈S_{k}} (∑_{i=1}^{k} M_{iσ(i)}) is achieved twice.

The regular subdivision (∂P_{V})^{∗} is a triangulation if and only if the polyhedron P_{V} is simple, which is to say if and only if no r + n of the facets y_{i} + z_{j} ≤ v_{ij} meet at a single vertex. For each vertex v, consider the bipartite graph G_{v} consisting of vertices y_{1}, …, y_{n} and z_{1}, …, z_{j} with an edge connecting y_{i} and z_{j} if v lies on the corresponding facet. This graph is connected, since each y_{i} and z_{j} appears in some such inequality, and thus it will have a cycle if and only if it has at least r + n edges. Consequently, P_{V} is not simple if and only there exists some G_{v} with a cycle. If there is a cycle, without loss of generality it reads y_{1}, z_{1}, y_{2}, z_{2}, …, y_{k}, z_{k}. Consider the submatrix M of (v_{ij}) given by 1 ≤ i ≤ k and 1 ≤ j ≤ k. We have y_{1} + z_{1} = M_{11}, y_{2} + z_{2} = M_{22}, and so on, and also z_{1} + y_{2} = M_{12}, …, z_{k} + y_{1} = M_{k1}. Adding up all of these equalities yields y_{1} + ⋯ + y_{k} + z_{1} + ⋯ + z_{k} = M_{11} + ⋯ + M_{kk} = M_{12} + ⋯ + M_{k1}. But consider any permutation σ in the symmetric group S_{k}. Since we have M_{iσ(i)} = v_{iσ(i)} ≥ y_{i} + z_{σ(i)}, we have ∑ M_{iσ(i)} ≥ x_{1} + ⋯ + x_{k} + y_{1} + ⋯ + y_{k}. Consequently, the permutations equal to the identity and to (12 ⋯ k) simultaneously minimize the determinant of the minor M. This logic is reversible, proving the equivalence of (1) and (3).

If the r points of V are in general position, the tropical complex they generate is called a generic tropical complex. These polyhedral complexes are then polar to the complexes of interior faces of regular triangulations of Δ_{r−1} × Δ_{n−1}.

Corollary 25. All tropical complexes generated by r points in general position in 𝕋ℙ^{n−1} have the same f-vector. Specifically, the number of faces of dimension k is equal to the multinomial coefficient

\binom{r + n − k − 2}{r − k − 1, n − k − 1, k} = \frac{(r + n − k − 2)!}{(r − k − 1)! · (n − k − 1)! · k!}.

Proof. By Proposition 24, these objects are in bijection with regular triangulations of P = Δ_{r−1} × Δ_{n−1}. The polytope P is equidecomposable [1], meaning that all of its triangulations have the same f-vector. The number of faces of dimension k of the tropical complex generated by given r points is equal to the number of interior faces of codimension k in the corresponding triangulation. Since all triangulations of all products of simplices have the same f-vector, they must also have the same interior f-vector, which can be computed by taking the f-vector and subtracting off the f-vectors of the induced triangulations on the proper faces of P. These proper faces are all products of simplices and hence equidecomposable, so all of these induced triangulations have f-vectors independent of the original triangulation as well. To compute this number, we therefore need only compute it for one tropical complex. Let the vectors v_{i}, 1 ≤ i ≤ r, be given by v_{i} = (i, 2i, ⋯, ni). By Theorem 10, to count the faces of dimension k in this tropical complex, we enumerate the existing types with k degrees of freedom. Consider any index i. We claim that for any x in the tropical convex hull of {v_{i}}, the set {j | i ∈ S_{j}} is an interval I_{i}, and that if i < m, the intervals I_{m} and I_{i} meet in at most one point, which in that case is the largest element of I_{m} and the smallest element of I_{i}. Suppose we have i ∈ S_{j} and m ∈ S_{l} with i < m. Then we have by definition v_{ij} − x_{j} ≤ v_{il} − x_{l} and v_{ml} − x_{l} ≤ v_{mj} − x_{j}. Adding these inequalities yields v_{ij} + v_{ml} ≤ v_{il} + v_{mj}, or ij + ml ≤ il + mj. Since i < m, it follows that we must have l ≤ j. Therefore, we can never have i ∈ S_{j} and m ∈ S_{l} with i < m and j < l. The claim follows immediately, since the I_{i} cover [1, n]. The number of degrees of freedom of an interval set (I_{1}, …, I_{r}) is easily seen to be the number of i for which I_{i} and I_{i+1} are disjoint. Given this, it follows from a simple combinatorial counting argument that the number of interval sets with k degrees of freedom is the multinomial coefficient given above. Finally, a representative for every interval set is given by x_{j} = x_{j+1} − c_{j}, where if S_{j} and S_{j+1} have an element i in common (they can have at most one), c_{j} = i, and if not then c_{j} = (min(S_{j}) + max(S_{j+1}))/2. Therefore, each interval set is in fact a valid type, and our enumeration is complete.

Corollary 26. The number of combinatorially distinct generic tropical complexes generated by r points in 𝕋ℙ^{n−1} equals the number of distinct regular triangulations of Δ_{r−1} × Δ_{n−1}. The number of respective symmetry classes under the natural action of the product of symmetric groups G = S_{r} × S_{n} on both spaces is also the same.

The symmetries in the group G correspond to a natural action on Δ_{r−1} ×Δ_{n−1} given by permuting the vertices of the two component simplices; the symmetries in the symmetric group S_{r} correspond to permuting the points in a tropical polytope, while those in the symmetric group S_{n} correspond to permuting the coordinates. (These are dual, as per Corollary 23.) The number of symmetry classes of regular triangulations of the polytope Δ_{r−1} × Δ_{n−1} is computable via Jörg Rambau’s TOPCOM [17] for small r and n:

2  3
2 5 35
3  35 7, 955
4  530
5 13, 631

For example, the (2, 3) entry of the table divulges that there are 35 symmetry classes of regular triangulations of Δ_{2} × Δ_{3}. These correspond to the 35 combinatorial types of four-point configurations in 𝕋ℙ^{2}, or to the 35 combinatorial types of three-point configurations in 𝕋ℙ^{3}. These 35 configurations (with the tropical complexes they generate) are shown in Figure 6; the labeling corresponds to Rambau’s labeling (see [17]) of the regular triangulations of Δ_{3} × Δ_{2}.

Tropical Convexity 21

Figure 6: The 35 symmetry classes of tropical complexes generated by four points in 𝕋ℙ^{2}.

Documenta Mathematica 9 (2004) 1–27

5 Phylogenetic analysis using tropical polytopes

A fundamental problem in bioinformatics is the reconstruction of phylogenetic trees from approximate distance data. In this section we show how tropical convexity might help provide new algorithmic tools for this problem. Our approach augments the results in [20, §4] and it provides a tropical interpretation of the work on T -theory by Andreas Dress and his collaborators [7], [8], [9]. Consider a symmetric n × n-matrix D = (d_{ij}) whose entries d_{ij} are nonnegative real numbers and whose diagonal entries d_{ii} are all zero. We say that D is a (finite) metric if the triangle inequality d_{ij} ≤ d_{ik} + d_{jk} holds for all indices i, j, k. Our starting point is the following easy observation:

Proposition 27. The symmetric matrix D is a metric if and only if all principal 3×3-minors of the negated symmetric matrix −D = (−d_{ij}) are tropically singular.

Proof. Both properties involve only three points, so we may assume n = 3, in which case

−D = (\begin{matrix}0 & −d_{12} & −d_{13} \\ −d_{12} & 0 & −d_{23} \\ −d_{13} & −d_{23} & 0 \end{matrix}) .

The tropical determinant of this matrix is the minimum of the six expressions

0, −2d_{12}, −2d_{13}, −2d_{23}, −d_{12} − d_{13} − d_{23} and − d_{12} − d_{13} − d_{23}.

This minimum is attained twice if and only if it is attained by the last two (identical) expressions, which occurs if and only if the three triangle inequalities are satisfied.

In what follows we assume that D = (d_{ij}) is a metric. Let P_{D} denote the tropical convex hull in 𝕋ℙ^{n−1} of the n row vectors (or column vectors) of the negated matrix −D = (−d_{ij}). Proposition 27 tells us that the tropical polytope P_{D} is always one-dimensional for n = 3. The finite metric D = (d_{ij}) is said to be a tree metric if there exists a weighted tree T with n leaves such that d_{ij} denotes the distance between the i-th leaf and the j-th leaf along the unique path between these leaves in T. The next theorem characterizes tree metrics among all metrics by the dimension of the tropical polytope P_{D}. It is the tropical interpretation of results that are quite classical and well-known in the phylogenetics literature.

Theorem 28. For a given finite metric D = (d_{ij}) the following conditions are equivalent:

1. D is a tree metric,

2. the tropical polytope P_{D} has dimension one,

3. all 4 × 4-minors of the matrix −D are tropically singular, 4. all principal 4 × 4-minors of the matrix −D are tropically singular,

5. For any choice of four indices i, j, k, l ∈ {1, 2, …, n}, the maximum of the three numbers d_{ij} + d_{kl}, d_{ik} + d_{jl} and d_{il} + d_{ik} is attained at least twice.

Proof. The condition (5) is the familiar Four Point Condition for tree metrics. The equivalence of (1) and (5) is a classical result due to various authors, including Buneman [2] and Zaretsky [21]. See equation (B3) on page 57 in [7]. Suppose that the condition (5) holds. By the discussion in [20, §4], this means that −D is a point in the tropical Grassmannian of lines, in symbols −D ∈ Gr(2, n) ⊂ 𝕋ℙ^{\binom{n}{2}}. By [20, Theorem 3.8], the point −D corresponds to a tropical line L_{D} in 𝕋ℙ^{n−1}. The n distinguished points whose coordinates are the rows of −D lie on the line L_{D}. By Corollary 7, it follows that their tropical convex hull P_{D} is contained in L_{D}. This means that P_{D} has dimension one, that is, (2) holds. Suppose that (2) holds. Then the tropical rank of the matrix −D is equal to two, by [6, Theorem 4.2]. This means that all r ×r-minors of −D are tropically singular for r ≥ 3. The case r = 4 is precisely the statement (3). Obviously, the condition (3) implies the condition (4). What remains is to prove the implication from (4) to (5). For this we note that the tropical determinant of the 4 × 4-matrix

(\begin{matrix}0 & −d_{12} & −d_{13} & −d_{14} \\ −d_{12} & 0 & −d_{23} & −d_{24} \\ −d_{13} & −d_{23} & 0 & −d_{34} \\ −d_{14} & −d_{24} & −d_{34} & 0 \end{matrix})

equals twice the minimum of −d_{12} − d_{34}, −d_{13} − d_{24} and −d_{14} − d_{23}. (It’s the tropicalization of a 4×4-Pfaffian). The matrix is tropically singular if and only if the minimum is attained twice.

If the five equivalent conditions of Theorem 28 are satisfied then the metric tree T coincides with the one-dimensional tropical polytope P_{D}. To make sense of this statement, we regard tropical projective space 𝕋ℙ^{n−1} as a metric space with respect to the infinity norm induced from ℝ^{n},

||x − y|| = max{ |x_{i} + y_{j} − x_{j} − y_{i}| : 1 ≤ i < j ≤ n },

and we note that the finite metric D embeds isometrically into P_{D} via the rows of −\frac{1}{2}D:

i ↦ \frac{1}{2} · (−d_{i1}, −d_{i2}, −d_{i3}, …, −d_{in}) for i = 1, 2, …, n

We learned from [8] that the tropical polytope P_{D} first appeared in the 1964 paper [10] by John Isbell. For the proof of the following result we assume familiarity with results from [7] and [8].

Theorem 29. The tropical polytope P_{D} equals Isbell’s injective hull of the metric D.

Proof. According to Lemma 22, the tropical polytope P_{D} is the bounded complex of the following unbounded polyhedron in the (2n − 1)-dimensional space W = ℝ^{2n}/ℝ(1, …, 1, −1, …, −1):

P_{−D} = { (y, z) ∈ W : y_{i} + z_{j} ≤ −d_{ij} for all 1 ≤ i, j ≤ n }.

Dress et al. [7] showed that the injective hull T (D) of the finite metric D coincides with the complex of bounded faces of the following n-dimensional unbounded polyhedron:

Q_{−D} = { x ∈ ℝ^{n} : x_{i} + x_{j} ≥ d_{ij} for all 1 ≤ i, j ≤ n }.

What we need to show is that the two polyhedra have the same bounded complex. The metric D satisfies the tropical matrix identity −D = D ⊙ (−D), because −d_{ij} = min_{k}(d_{ik} −d_{kj}). This implies that any column vector y of −D satisfies y = (−y) ⊙ (−D). Consider any vertex (y, z) of P_{−D}. Then y is a column vector of −D. Equation (14) implies z = (−y) ⊙ (−D) = y. Hence every vertex of P_{−D} lies in the subspace defined by y = z, and so does the complex of bounded faces of P_{−D}. Therefore the linear map (y, z) ↦ −y induces an isomorphism between the bounded complex of P_{−D} and the bounded complex of Q_{−D}.

Theorem 23 specifies an involution on the set of all tropical complexes. We are interested in the fixed points of this canonical involution. A necessary condition is that r = n and V is a symmetric matrix. The previous result and its proof can be reinterpreted as follows:

Corollary 30. A tropical complex P is pointwise fixed under the canonical involution (on the set of all tropical complexes) if and only if P is the injective hull of a metric on {1, 2, …, n}.

Proof. In order for P to be fixed under the canonical involution, it is necessary that n = d. Hence we can write P = tconv(−D) for some non-negative square matrix D. Now, P is fixed under the involution if and only if the identity −D = D ⊙ (−D) holds. This identity is equivalent to D being a metric.

Dress, Huber and Moulton [7] emphasize that the tropical polytope P_{D} records many important invariants of a given finite metric D. For instance, the dimension of P_{D} gives information about how far the metric is from being a tree metric. In practical biological applications of phylogenetic reconstruction, the distances d_{ij} are not known exactly, and P_{D} appears to contain many of the various trees which are found by existing software for phylogenetic reconstruction.

The dimension of the tropical complex P_{D} = tconv(−D) can be characterized combinatorially by tropicalizing the sub-Pfaffians of a skew-symmetric n × nmatrix. The tropical Pfaffians of format 4 × 4 specify the four point condition (5) in Theorem 28, while the tropical sub-Pfaffians of format 6 × 6 specify the six-point condition which is discussed in [7, page 25]. The combinatorial study of k-compatible split systems can be interpreted in the setting of tropical algebraic geometry (cf. [15], [18], [20]) as the study of the k-th secant variety in the Grassmannian Gr(2, n) ⊂ 𝕋ℙ^{\binom{n}{2}}. Tropical convexity provides a convenient language to study numerous extensions of the classical problem of tree reconstruction. As an example, imagine the following scenario, which would correspond to the Grassmannian of planes in 𝕋ℙ^{n−1}, denoted Gr(3, n). Suppose there are n taxa, labeled 1, 2, …, n, and rather than having a distance for any pair i, j, we are now given a proximity measure d_{ijk} for any triple i, j, k ∈ {1, 2, …, n}. We can then construct a tropical polytope by taking the tropical convex hull of \binom{n}{2} points as follows:

P = tconv { (−d_{ij1}, −d_{ij2}, −d_{ij3}, … − d_{ijn}) ∈ 𝕋ℙ^{n−1} : 1 ≤ i < j ≤ n }.

Under certain hypotheses, the tropical polytope P can be realized as the complex of bounded faces of the polyhedron in ℝ^{n} defined by the inequalities x_{i} + x_{j} + x_{k} ≥ d_{ijk}. It provides a polyhedral model for the tree-like nature of the data (d_{ijk}). The case of most interest is when P is two-dimensional in which case it plays the role of a two-dimensional phylogenetic tree. The construction of this particular tropical polytope P was pioneered by Dress and Terhalle in the important paper [9]. There they discuss valuated matroids, which are essentially the points on the tropical Grassmannian of [20], and they call P the tight span of a valuated matroid. We share their view that these tropical polytopes constitute a promising tool for phylogenetic analysis.

Acknowledgements

This work was conducted while Mike Develin held the AIM Postdoctoral Fellowship 2003-2008 and Bernd Sturmfels held the MSRI-Hewlett Packard Professorship 2003/2004. Sturmfels also acknowledges partial support from the National Science Foundation (DMS-0200729).

References

[1] L.J. Billera, R. Cushman, and J.A. Sanders: The Stanley decomposition of the harmonic oscillator, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), 375–393.

[2] P. Buneman: A note on metric properties of trees, Journal of Combinatorial Theory, Ser. B 17 (1974) 48–50.

[3] G. Cohen, S. Gaubert, and J.-P. Quadrat: Duality and separation theorems in idempotent semimodules, arXiv:math.FA/0212294.

[4] I.M. Gel’fand, M.I. Graev and A. Postnikov: Combinatorics of hypergeometric functions associated with positive roots, in Arnold-Gel’fand Mathematical Seminars, Geometry and Singularity Theory, (Eds. V.I. Arnold, I.M. Gel’fand, M. Smirnov and V.S. Retakh), Birkhäuser, Boston, 1997, pp. 205–221.

[5] J. De Loera, J. Rambau and F. Santos: Triangulations of Point Configurations, Algorithms and Computation in Mathematics, Springer Verlag, Heidelberg, to appear.

[6] M. Develin, F. Santos and B. Sturmfels: On the rank of a tropical matrix,

arXiv:math.CO/0312114.

[7] A. Dress, K.T. Huber and V. Moulton: An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex, Advances in Mathematics 168 (2002) 1–28.

[8] A. Dress, V. Moulton and W. Terhalle: T-Theory – an overview, European Journal of Combinatorics 17 (1996) 161–175.

[9] A. Dress and W. Terhalle: The tree of life and other affine buildings. Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), Documenta Mathematica, Extra Vol. III, 1998, 565–574.

[10] J. Isbell: Six theorems about metric spaces, Comment. Math. Helv. 39 (1964) 65–74.

[11] M. Joswig: Tropical halfspaces, arXiv:math.CO/0312068.

[12] A.N. Kirillov: Introduction to tropical combinatorics, in Physics and Combinatorics 2000, Proceedings of the Nagoya 2000 International Workshop, (Eds. A.N. Kirillov and N. Liskova), pp. 82–150, World Scientific, 2001.

[13] G. Litvinov, V. Maslov, and G. Shpiz: Idempotent functional analysis: an algebraic approach, Mathematical Notes 69 (2001) 696–729,

arXiv:math.FA/0009128.

[14] J. Matoušek, On directional convexity, Discrete and Computational Geometry 25 (2001) 389–403.

[15] G. Mikhalkin: Counting curves via lattice paths in polygons, C. R. Acad. Sci. Paris 336 (2003), no. 8, 629–634.

[16] M. Noumi and Y. Yamada: Tropical Robinson-Schensted-Knuth correspondence and birational Weyl group actions, arXiv:math-ph/0203030.

[17] J. Rambau: TOPCOM (Triangulations of Point Configurations and Oriented Matroids), software available at

http://www.zib.de/rambau/TOPCOM/. The numbers cited for reg-

ular triangulations of products of simplices can be found at

http://www.zib.de/rambau/TOPCOM/TOPCOM-examples/.

[18] J. Richter-Gebert, B. Sturmfels, and T. Theobald: First steps in tropical geometry, arXiv:math.AG/0306366, to appear in Idempotent Mathematics and Mathematical Physics, Proceedings Vienna 2003, (editors G.L. Litvinov and V.P. Maslov), American Mathematical Society, 2004.

[19] F. Santos: The Cayley Trick and triangulations of products of simplices,

arXiv:math.CO/0312069.

[20] D. Speyer and B. Sturmfels: The tropical Grassmannian, arXiv:math.AG/0304218, to appear in Advances in Geometry.

[21] K.A. Zaretsky: Reconstruction of a tree from the distances between its pendant vertices, Uspekhi Math. Nauk. Russian Mathematical Surveys 20 (1965) 90–92.

Mike Develin

American Inst. of Math 360 Portage Ave. Palo Alto, CA 94306-2244 USA develin@post.harvard.edu Bernd Sturmfels Dept. of Mathematics UC-Berkeley Berkeley, CA 94720 USA bernd@math.berkeley.edu 28

Documenta Mathematica 9 (2004)