Printer Friendly

Isotropical linear spaces and valuated Delta-matroids.

1 Introduction

Let n be a positive integer, and let V be a 2n-dimensional vector space over an algebraically closed field K of characteristic 0. Fix a basis [e.sub.1], [e.sub.2], ..., [e.sub.n], [e.sub.1]*, [e.sub.2]*, ..., [e.sub.n]* for V, and consider the symmetric bilinear form on V defined as

Q(x,y) = [n.summation over (i=1)][x.sub.i][y.sub.i]* + [n.summation over (i=1)][x.sub.i]*[y.sub.i],

for any x, y [member of] V with coordinates x = ([x.sub.i], ..., [x.sub.n],[x.sub.i]*, ..., [x.sub.n]*) and y = ([y.sub.1], ..., [y.sub.n],[y.sub.1]*, ..., [y.sub.n]*). An n-dimensional subspace U [subset or equal to] V is called (totally) isotropic if for all u, v [member of] U we have Q(u,v) = 0, or equivalently, for all u [member of] U we have Q(u, u) = 0. Denote by P(n) the collection of subsets of the set [n] := {1, 2, ..., n}. The space of pure spinors [Spin.sup.[+ or -]](n) is an algebraic set in projective space [P.sup.P(n)-i] that parametrizes totally isotropic subspaces of V. Its defining ideal is generated by very special quadratic equations, known as Wick relations. We will discuss these relations in Section 2. Since any linear subspace W [subset or equal to] [K.sup.n] defines an isotropic subspace U := W x [W.sup.[perpendicular to]] [subset or equal to] [K.sup.2n], all Grassmannians G(k, n) can be embedded naturally into the space of pure spinors, and in fact, Wick relations can be seen as a natural generalization of Pliicker relations.

In [Spe08], Speyer studied tropical Plucker relations, tropical Plucker vectors (or valuated matroids [DW92]), and their relation with tropical linear spaces. In his study he showed that these objects have a beautiful combinatorial structure, which is closely related to matroid polytope decompositions. In this paper we will study the tropical variety and prevariety defined by all Wick relations, the combinatorics satisfied by the vectors in these spaces (valuated [DELTA]-matroids [DW91]), and their connection with tropical linear spaces that are tropically isotropic (which we will call isotropical linear spaces). Much of our work can be seen as a generalization to type D of some of the results obtained by Speyer, or as a generalization of the theory of [DELTA]-matroids to the "valuated" setup.

We will say that a vector p [member of] [T.sup.P(n)] with coordinates in the tropical semiring T := R [union] {[infinity]} is a tropical Wick vector if it satisfies the tropical Wick relations. A central object for our study of tropical Wick vectors will be that of an even [DELTA]-matroid [Bou87]. Even [DELTA]-matroids are a natural generalization of classical matroids, and much of the theory of matroids can be extended to them. In particular, their associated polytopes are precisely those 0/1 polytopes whose edges have the form [+ or -][e.sub.i] [+ or -] [e.sub.j], with i [not equal to] j. In this sense, even [DELTA]-matroids can be seen as Coxeter matroids of type D, while classical matroids correspond to Coxeter matroids of type A. We will present all the necessary background on even [DELTA]-matroids in Section 3. Tropical Wick vectors will be valuated [DELTA]-matroids: real functions on the set of bases of an even [DELTA]-matroid satisfying certain "valuated exchange property" which is amenable to the greedy algorithm (see [DW91]).

In Section 4 we will be interested in determining for what values of n the Wick relations form a tropical basis, and we will provide an answer for all n [not equal to] 6. We will prove in Section 5 that in fact tropical Wick vectors can be characterized in terms of even [DELTA]-matroid polytope subdivisions. We give a complete list of all even [DELTA]-matroids up to isomorphism on a ground set of at most 5 elements, together with their corresponding spaces of valuations, in the website http://math.berkeley.edu/~felipe/delta/. In Section 6 we will extend some of the theory of even [DELTA]-matroids to the valuated setup. We will define duality, circuits, and cycles for a tropical Wick vector p, generalizing the corresponding definitions for even [DELTA]-matroids. We will be mostly interested in studying the cocycle space of a tropical Wick vector, which can be seen as an analog in type D to the tropical linear space associated to a tropical Plucker vector, and we will give a parametric description of it in terms of cocircuits. We will then specialize our results to tropical Plucker vectors, unifying in this way several results for tropical linear spaces given by Murota and Tamura [MT01], Speyer [Spe08], and Ardila and Klivans [AK06]. In Section 7 we will define isotropical linear spaces and study their relation with tropical Wick vectors. We will give an effective characterization for determining when a tropical linear space is isotropical, and we will show that the correspondence between isotropic linear spaces and points in the pure spinor space is lost after tropicalizing. Nonetheless, we will prove that this correspondence still holds when we restrict our attention only to vectors having "small support".

2 Isotropic Linear Spaces and Spinor Varieties

Let n be a positive integer, and let V be a 2n-dimensional vector space over an algebraically closed field K of characteristic 0, with a fixed basis [e.sub.1], [e.sub.2], ..., [e.sub.n], [e.sub.1]*, [e.sub.2]*, ..., [e.sub.n]*. Denote by P(n) the collection of subsets of the set [n] := {1,2, ..., n}. In order to simplify the notation, if S [member of] P(n) and a [member of] [n] we will write Sa, S - a, and S[DELTA]a instead of S [union] {a}, S \ {a}, and S[DELTA]{a}, respectively. Given an n- dimensional isotropic subspace U [subset or equal to] V, one can associate to it a vector w [member of] [P.sup.P(n)-1] of Wick coordinates as follows. Write U as the rowspace of some n x 2n matrix M with entries in K. If the first n columns of M are linearly independent, we can row reduce the matrix M and assume that it has the form M = [I|A], where I is the identity matrix of size n and A is an n x n matrix. The fact that U is isotropic is equivalent to the property that the matrix A is skew-symmetric. The vector w [member of] [P.sup.P(n)-1] is then defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

where S [member of] P(n) and Pf([A.sub.S]) denotes the Pfaffian of the principal submatrix [A.sub.S] of A whose rows and columns are indexed by the elements of S. If the first n columns of M are linearly dependent then we proceed in a similar way but working over a different affine chart of [P.sup.P(n)-1]. In this case, we can first reorder the elements of our basis (and thus the columns of M) using a permutation of 2n := {1, 2, ..., n, 1*, 2*, ..., n*} consisting of transpositions of the form (j, j*) for all j in some index set J [subset or equal to] [n], so that we get a new matrix that can be row-reduced to a matrix of the form M' = [I|A] (with A skew-symmetric). We then compute the Wick coordinates as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

where [(-1).sup.sg(S,J)] is some sign depending on S and J that will not be important for us. The vector w [member of] [P.sup.P(n)-1] of Wick coordinates depends only on the subspace U, and the subspace U can be recovered from its vector w of Wick coordinates.

The space of pure spinors is the set [Spin.sup.[+ or -]](n) [subset or equal to] [P.sup.P(n)-1] of Wick coordinates of all n-dimensional isotropic subspaces of V, and thus it is a parameter space for these subspaces. It is an algebraic set, and it decomposes into two isomorphic irreducible varieties as [Spin.sup.[+ or -]](n) = [Spin.sup.+](n) [??] [Spin.sup.-](n), where [Spin.sup.+](n) consists of all Wick coordinates w whose support supp(w) := {S [member of] P(n) : [w.sub.S] [not equal to] 0} is made of even-sized subsets, and [Spin.sup.-](n) consists of all Wick coordinates whose support is made of odd-sized subsets. The irreducible variety [Spin.sup.+](n) is called the spinor variety; it is the projective closure of the image of the map sending an n x n skew-symmetric matrix to its vector of Pfaffians. Its defining ideal consists of all polynomial relations among the Pfaffians of a skew-symmetric matrix, and it is generated by the following quadratic relations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)

where [sigma], [tau] [member of] P(n) have odd cardinalities r, s, respectively, and the variables [w.sub.[sigma]] are understood to be alternating with respect to a reordering of the indices, e.g. [w.sub.1234] = -[w.sub.1234] and [w.sub.1135] = 0. The ideal defining the space of pure spinors is generated by all quadratic relations having the form (1), but now with [sigma], [tau] [member of] P(n) having any cardinality. These relations are known as Wick relations. The shortest nontrivial Wick relations are obtained when [absolute value of [sigma][DELTA][tau]] = 4; they have the form [w.sub.Sabcd] x [w.sub.S] - [w.sub.Sab] x [w.sub.Scd] + [w.sub.Sac] x [w.sub.sbd] - [w.sub.Sad] x [w.sub.Sbc] and [w.sub.Sabc] x [w.sub.Sd] - [w.sub.Sabd] x [w.sub.Sc] + [w.sub.Sacd] x [w.sub.Sb] - [w.sub.Sbcd] x [P.sub.Sa], where S [subset or equal to] [n] and a, b, c, d [member of] [n] \ S are distinct. These relations will be of special importance for us; they will be called the 4-term Wick relations.

3 Delta-Matroids

In this section we review some of the basic theory of even [DELTA]-matroids.

3.1 Bases

Our first description of even [DELTA]-matroids is the following.

Definition 3.1 An even [DELTA]-matroid (or even Delta-matroid) is a pair M = (E, B), where E is a finite set and B is a nonempty collection of subsets of E satisfying the following symmetric exchange axiom: for all A, B [member of] B and for all a [member of] A[DELTA]B, there exists b [member of] A[DELTA]B such that b [not equal to] a and A[DELTA]{a, b} [member of] B. Here [DELTA] denotes symmetric difference: X[DELTA]Y = (X \ Y) [union] (Y \ X). The set E is called the ground set of M, and B is called the collection of bases of M. We also say that M is an even [DELTA]-matroid over the set E.

Even Delta-matroids are a natural generalization of classical matroids; in fact, it is easy to see that matroids are precisely those even [DELTA]-matroids whose bases have all the same cardinality (the reader not familiar with matroids can take this as a definition). The following proposition is easy to prove.

Proposition 3.2 Let M be an even [DELTA]-matroid. Then all the bases of M have the same parity.

It should be mentioned that the bases of an even [DELTA]-matroid can all have odd cardinality; unfortunately, the name used for even [DELTA]-matroids might be a little misleading.

The notion of duality for matroids generalizes naturally to even [DELTA]-matroids.

Definition 3.3 Let M = (E, B) be an even [DELTA]-matroid. Directly from the definition it follows that the collection [B.sup.*] := {E \ B : B [member of] B} is also the collection of bases of an even [DELTA]-matroid M* over E. We will refer to M* as the dual even [DELTA]-matroid to M.

3.2 Representability

Our interest in even [DELTA]-matroids comes from the study of the possible supports of Wick vectors.

Proposition 3.4 Let V be a 2n-dimensional vector space over the field K. If U [subset or equal to] V is an n-dimensional isotropic subspace with Wick coordinates w, then the subsets in supp(w) := {S [member of] P(n) : [w.sub.S] [not equal to] 0} form the collection of bases of an even [DELTA]-matroid M (U) over [n]. An even [DELTA]-matroid arising in this way is said to be a representable even [DELTA]-matroid (over the field K).

This notion of representability generalizes the classical notion of representability for classical matroids. For matroids, some work has succeeded in studying this property over fields of very small characteristic, but there is no simple and useful characterization of representable matroids over a field of characteristic zero. The study of representability for even [DELTA]-matroids shares the same difficulties, and there seems to be almost no research done in this direction so far.

3.3 Matroid Polytopes

Given any collection B of subsets of [n] one can associate to it the polytope [[GAMMA].sub.B] := convex{[e.sub.S] : S [member of] B}, where [e.sub.S] := [[summation].sub.i[member of]S] [e.sub.i] is the indicator vector of the subset S. The following theorem characterizes the polytopes associated to even [DELTA]-matroids; it is a special case of a more general and fundamental theorem characterizing the associated polytopes of Coxeter matroids (see [BGW03]).

Theorem 3.5 If B [subset or equal to] P(n) is nonempty then B is the collection of bases of an even [DELTA]-matroid if and only if all the edges of the polytope [[GAMMA].sub.B] have the form [+ or -][e.sub.i] [+ or -] [e.sub.j], where i, j [member of] [n] are distinct.

These results let us think of even [DELTA]-matroids as "matroids of type D" (while classical matroids are "matroids of type A").

3.4 Circuits and Symmetric Matroids

We will now describe a notion of circuits for even [DELTA]-matroids. We will present here only the basic properties needed for the rest of the paper; a much more detailed description can be found in [BGW03].

Consider the sets [n] := {1,2, ..., n} and [n]* := {1*, 2*, ..., n*}. Define the map * : [n] [right arrow] [n]* by i [??] i* and the map * : [n]* [right arrow] [n] by i* [??] i. We can think of * as an involution of the set 2n := [n] [union] [n]*, where for any j [member of] 2n we have j** = j. If J [subset or equal to] 2n we define J* := {j* : j [member of] J}. We say that the set J is admissible if J [intersection] J* = 0, and that it is a transversal if it is an admissible subset of size n. For any S [subset or equal to] [n], we define its extension [bar.S] [subset or equal to] 2n to be the transversal given by [bar.S] := S [union] ([n] \ S)*, and for any transversal J we will define its restriction to be the set J [intersection] [n]. Extending and restricting are clearly bijections (inverse to each other) between the set P(n) and the set of transversals V(n) of 2n.

Given an even [DELTA]-matroid M = ([n], B), the symmetric matroid associated to M is the collection [bar.B] of transversals defined as [bar.B] := {[bar.B] : B [member of] B}. There is of course no substantial difference between an even [DELTA]-matroid and its associated symmetric matroid; however, working with symmetric matroids will allow us to simplify the forthcoming definitions.

Definition 3.6 Let M = ([n], B) be an even [DELTA]-matroid over [n]. A subset S [subset or equal to] 2n is called independent in M if it is contained in some transversal [bar.B] [member of] [bar.B], and it is called dependent in M if it is not independent. A subset C [subset or equal to] 2n is called a circuit of M if [subset or equal to] is a minimal dependent subset which is admissible. A cocircuit of M is a circuit of the dual even [DELTA]-matroid M*. The set of circuits of M will be denoted by C(M), and the set of cocircuits by C*(M). An admissible union of circuits of M is called a cycle of M. A cocycle of M is a cycle of the dual even [DELTA]-matroid M*.

This definition of circuits for even [DELTA]-matroids generalizes the concept of circuits for matroids. In fact, if M = ([n], B) is a matroid, [subset or equal to] is its collection of (classical) circuits and K is its collection of (classical) cocircuits, then the collection of circuits of M, when considered as an even [DELTA]-matroid, is {C : C [member of] C}[union]{K* : K [member of] K}.

Example 3.7 Take n = 3, and let U be the isotropic subspace of [C.sup.6] defined as the rowspace of the matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The even [DELTA]-matroid M represented by U has bases B = {123,1,2,3}, corresponding to the support of its vector of Wick coordinates. Its associated polytope is the tetrahedron with vertices (1,1,1), (1,0,0), (0,1,0), and (0,0,1); whose edges are indeed of the form [+ or -][e.sub.i] [+ or -] [e.sub.j]. The circuits of M are the admissible subsets 1*23, 12*3, 123*, 1*2*3*. The dual even [DELTA]-matroid M* has bases B* = {0,12,13,23}. The cocircuits of M are the admissible subsets 123, 12*3*, 1*23*, 1*2*3.

4 Tropical Wick Relations

We now turn to the study of the tropical prevariety and tropical variety defined by the Wick relations. Due to space constraints, we will assume the reader is familiar with the basic notions of tropical geometry.

Definition 4.1 A vector p = ([p.sub.S]) [member of] [T.sup.P(n)] is called a tropical Wick vector if it satisfies the tropical Wick relations, that is, for all S, T [member of] P(n) the minimum

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

is achieved at least twice (or it is equal to [infinity]). The [DELTA]-Dressian [DELTA]Dr(n) [subset or equal to] [T.sup.P(n)] is the space of all tropical Wick vectors in [T.sup.P(n)], i.e., the tropical prevariety defined by the Wick relations.

Tropical Wick vectors have also been studied in the literature under the name of valuated [DELTA]-matroids (see [DW91]). The following definition will be central to our study, and it is the reason why working over R [union] [infinity] and not just R is fundamental for us.

Definition 4.2 The support of a vector p = ([p.sub.S]) [member of] [T.sup.P(n)] is supp(p) := {S [subset or equal to] [n] : [p.sub.S] [not equal to] [infinity]}.

We will later see (Theorem 5.1) that the support of any tropical Wick vector consists of subsets whose cardinalities have all the same parity, so the [DELTA]-Dressian decomposes as the disjoint union of two tropical prevarieties: the even [DELTA]-Dressian [DELTA][Dr.sup.+](n) [subset or equal to] [T.sup.P(n)] (consisting of all tropical Wick vectors whose support has only subsets of even cardinality) and the odd [DELTA]-Dressian [DELTA][Dr.sup.-](n) [subset or equal to] [T.sup.P(n)] (defined analogously).

One of the main advantages of allowing our vectors to have [infinity] entries is that tropical Wick vectors can be seen as a generalization of tropical Plucker vectors (or valuated matroids), as explained below.

Definition 4.3 A tropical Wick vector p = ([p.sub.S]) [member of] [T.sup.P(n)] is called a tropical Plucker vector (or a valuated matroid) if all the subsets in supp(p) have the same cardinality [r.sub.p], called the rank of p. The name is justified by noting that in this case, the tropical Wick relations become just the tropical Plucker relations: For all S, T [member of] P(n) such that [absolute value of S] = [r.sub.p] - 1 and [absolute value of T] = [r.sub.p] + 1, the minimum

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

is achieved at least twice (or it is equal to [infinity]). The space of tropical Plucker vectors of rank k is called the Dressian Dr(k, n); it is the tropical prevariety defined by the Plucker relations of rank k.

Tropical Plucker vectors play a central role in the combinatorial study of tropical linear spaces done by Speyer (see [Spe08]). In his paper he only deals with tropical Plucker vectors whose support is the collection of all subsets of [n] of some fixed size k; we will later see that our definition is the "correct" generalization to more general supports.

Definition 4.4 The tropical pure spinor space [TSpin.sup.[+ or -]](n) [subset or equal to] [T.sup.P(n)] is the tropicalization of the space of pure spinors, i.e., it is the tropical variety defined by all polynomials in the ideal generated by the Wick relations. A tropical Wick vector in the tropical pure spinor space is said to be realizable. The decomposition of the [DELTA]-Dressian into its even an odd parts induces a decomposition of the tropical pure spinor space as the disjoint union of two "isomorphic" tropical varieties [TSpin.sup.+](n) and [TSpin.sup.-](n), namely, the tropicalization of the spinor varieties [Spin.sup.+](n) and [Spin.sup.-](n) described in Section 2. The tropicalization [TSpin.sup.+](n) [subset or equal to] [T.sup.P(n)] of the even part [Spin.sup.+](n) will be called the tropical spinor variety.

By definition, we have that the tropical pure spinor space [TSpin.sup.[+ or -]](n) is contained in the [DELTA]-Dressian [DELTA]Dr(n). A first step in studying representability of tropical Wick vectors (i.e. valuated [DELTA]-matroids) is to determine when these two spaces are the same, or equivalently, when the Wick relations form a tropical basis. Our main result in this section answers this question for almost all values of n.

Theorem 4.5 If n [less than or equal to] 5 then the tropical pure spinor space [TSpin.sup.[+ or -]](n) is equal to the [DELTA]-Dressian [DELTA]Dr(n), i.e., the Wick relations form a tropical basis for the ideal they generate. If n [greater than or equal to] 7 then [TSpin.sup.[+ or -]](n) is strictly smaller than [DELTA]Dr(n); in fact, there is a vector in the even [DELTA]-Dressian [DELTA][Dr.sup.+](n) whose support consists of all even-sized subsets of [n] which is not in the tropical spinor variety [TSpin.sup.+](n).

To show that the tropical pure spinor space and the [DELTA]-Dressian agree when n [less than or equal to] 5 we used of Anders Jensen's software Gfan [Jen]. The results of our computations can be found at the website http:// math.berkeley.edu/~felipe/delta/. It is still unclear what happens when n = 6. In this case, the spinor variety is described by 76 nontrivial Wick relations (60 of which are 4-term Wick relations) on 32 variables, and a Gfan computation requires a long time to finish. We state the following conjecture.

Conjecture 4.6 The tropical pure spinor space [TSpin.sup.[+ or -]] (6) is equal to the [DELTA]-Dressian [DELTA]Dr(6).

Our equality between [TSpin.sup.[+ or -]](n) and [DELTA]Dr(n) for n [less than or equal to] 5 implies the following corollary about representability of even [DELTA]-matroids.

Corollary 4.7 Let M be an even [DELTA]-matroid on a ground set of at most 5 elements. Then M is a representable even [DELTA]-matroid over any algebraically closed field of characteristic 0.

5 Tropical Wick Vectors and Delta-Matroid Subdivisions

In this section we provide a description of tropical Wick vectors in terms of polytopal subdivisions. We start with a useful local characterization, which was basically proved by Murota in [Mur06].

Theorem 5.1 Suppose p = ([p.sub.S]) [member of] [T.sup.P(n)] has nonempty support. Then p is a tropical Wick vector if and only if supp(p) is the collection of bases of an even [DELTA]-matroid over [n] and the vector p satisfies the 4-term tropical Wick relations: For all S [member of] P(n) and all a, b, c, d [member of] [n] \ S distinct, the minima min([p.sub.Sabcd] + [p.sub.S], [p.sub.Sab] + [p.sub.Scd], [p.sub.Sac] + [p.sub.Sbd], [p.sub.Sad] + [p.sub.Sbc]) and min([px.sub.Sabc] + [p.sub.Sd], [p.sub.Sabd] + [p.sub.Sc], [p.sub.Sacd] + [p.sub.Sb], [p.sub.Sbcd] + [px.sub.Sa]) are achieved at least twice (or are equal to [infinity]).

Corollary 5.2 Suppose p = ([p.sub.S]) [member of] [T.sup.P(n)] has nonempty support. Then p is a tropical Plucker vector if and only if supp(p) is the collection of bases of matroid over [n] (of rank rp) and the vector p satisfies the 3-term tropical Plucker relations: For all S [member of] P(n) such that [absolute value of S] = [r.sub.p] - 2 and all a, b, c, d [member of] [n] \ S distinct, the minimum min([p.sub.Sab] + [p.sub.Scd], [p.sub.Sac] + [p.sub.Sbd], [p.sub.Sad] + [p.sub.Sbc]) is achieved at least twice (or it is equal to [infinity]).

Corollary 5.2 shows that our notion of tropical Plucker vector is indeed a generalization of the one given by Speyer in [Spe08] to the case where supp(p) is not necessarily the collection of bases of a uniform matroid.

Definition 5.3 Given a vector p = ([p.sub.s]) [member of] [T.sup.P(n)], denote by [[GAMMA].sub.p] [subset or equal to] [R.sup.n] its associated polytope [[GAMMA].sub.p] := convex{[e.sub.S] : S [member of] supp(p)}. The vector p induces naturally a regular subdivision [D.sub.p] of [[GAMMA].sub.p] in the following way. Consider the vector p as a height function on the vertices of [[GAMMA].sub.p], so "lift" vertex [e.sub.s] of [[GAMMA].sub.p] to height [p.sub.S] to obtain the lifted polytope [[GAMMA]'.sub.p] = convex{([e.sub.S], [p.sub.S]) : S [member of] supp(p)} [subset or equal to] [R.sup.n+1]. The lower faces of [[GAMMA]'.sub.p] are the faces of [[GAMMA]'.sub.p] minimizing a linear form (v, 1) [member of] [R.sup.n+1]; their projection back to [R.sup.n] form the polytopal subdivision [D.sub.p] of [[GAMMA].sub.p], called the regular subdivision induced by p.

We now come to the main result of this section. It describes tropical Wick vectors as the height vectors that induce "nice" polytopal subdivisions. After finishing this paper, it was pointed out to the author that an equivalent formulation of this result had already been proved by Murota in [Mur97], under the language of maximizers of an even [DELTA]-matroid.

Theorem 5.4 Let p = ([p.sub.S]) [member of] [T.sup.P(n)]. Then p is a tropical Wick vector if and only if the regular subdivision [D.sub.p] induced by p is an even [DELTA]-matroid subdivision, i.e., it is a subdivision of an even [DELTA]-matroid polytope into even [DELTA]-matroid polytopes.

If we restrict Theorem 5.4 to the case where all subsets in supp(p) have the same cardinality, we get the following corollary. It generalizes the results of Speyer in [Spe08] for subdivisions of a hypersimplex.

Corollary 5.5 Let p [member of] [T.sup.P(n)]. Then p is a tropical Plucker vector if and only if the regular subdivision [D.sub.p] induced by p is a matroid subdivision, i.e., it is a subdivision of a matroid polytope into matroid polytopes.

6 The Cocycle Space

In this section we define the notion of circuits, cocircuits and duality for tropical Wick vectors, and study the space of vectors which are "tropically orthogonal" to all circuits. The admissible part of this space will be called the cocycle space, for which we give a parametric representation. Most of our results can be seen as a generalization of results for matroids and even [DELTA]-matroids to the "valuated" setup. For this purpose it is useful to keep in mind that for any even [DELTA]-matroid M = ([n], B), by Theorem 5.4 there is a natural tropical Wick vector associated to it, namely, the vector [p.sub.M] [member of] [T.sup.P(n)] defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Definition 6.1 Suppose p = ([p.sub.S]) [member of] [T.sup.P(n)] is a tropical Wick vector. It follows easily from the definition that the vector p* = ([p*.sub.S]) [member of] [T.sup.P(n)] defined as [p*.sub.S] := [p.sub.[n]\S] is also a tropical Wick vector, called the dual tropical Wick vector to p. Note that the even [DELTA]-matroid associated to p* is the dual even [DELTA]-matroid to the one associated to p.

Definition 6.2 Recall that a subset J [subset or equal to] 2n is said to be admissible if J [intersection] J* = 0. An admissible subset of 2n of size n is called a transversal; the set of all transversals of 2n is denoted by V (n). For any subset S [member of] P(n) we defined its extension to be the transversal [bar.S] := S [union] ([n] \ S)* [subset or equal to] 2n. There is of course a bijection S [??] [bar.S] between P(n) and V(n).

Now, let p = ([p.sub.S]) [member of] [T.sup.P(n)] be a tropical Wick vector. It will be convenient for us to work with the natural extension [bar.p] [member of] [T.sup.V(n)] of p defined as [[bar.p].sub.S] := [p.sub.S]. For any T [member of] P(n) we define the vector [c.sub.T] [member of] [T.sup.2n] (also denoted [c.sub.[bar.T]]) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It can be checked that if supp([c.sub.T]) [not equal to] 0 then supp([c.sub.T]) is one of the circuits of the even [DELTA]-matroid [M.sub.p] whose collection of bases is supp(p). We will say that the vector c [member of] [T.sup.2n] is a circuit of the tropical Wick vector p if supp(c) [not equal to] 0 and there is some T [member of] P(n) and some [lambda] [member of] R such that c = [lambda] [dot encircle] [c.sub.T] (or in classical notation, c = [c.sub.T] + [lambda] x 1, where 1 denotes the vector in [T.sup.2n] whose coordinates are all equal to 1). It is not hard to see that C([M.sub.p]) = {supp(c) : c is a circuit of p}, so this notion of circuits indeed generalizes the notion of circuits for even [DELTA]-matroids to the "valuated" setup. The collection of circuits of p will be denoted by C(p) [subset or equal to] [T.sup.2n]. A cocircuit of the tropical Wick vector p is just a circuit of the dual vector [p.sup.*], i.e., a vector of the form [lambda] [dot encircle] [c*.sub.T], where [c*.sub.T] [member of] [T.sup.2n] (also denoted [c*.sub.[bar.T]],) is the vector

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now define the concept of "tropical orthogonality", which is just the tropicalization of the usual notion of orthogonality in terms of the dot product.

Definition 6.3 Two vectors x, y [member of] [T.sup.N] are said to be tropically orthogonal, denoted by x T y, if the minimum min([x.sub.1] + [y.sub.1], [x.sub.2] + [y.sub.2], ..., [x.sub.N] + [y.sub.N]) is achieved at least twice (or it is equal to [infinity]). If X [subset or equal to] [T.sup.N] then its tropically orthogonal set is [X.sup.T] := {y [member of] [T.sup.N] : yTx for all x [member of] X}.

We now turn to the study of the space of vectors which are tropically orthogonal to all circuits. Our motivation for this will be clear later, when we deal with tropical linear spaces.

Definition 6.4 A vector x [member of] [T.sup.2n] is said to be admissible if supp(x) is an admissible subset of 2n. Let p [member of] [T.sup.P(n)] be a tropical Wick vector. If x [member of] C[(p).sup.T] is admissible then x will be called a cocycle of p. The set of all cocycles of p will be called the cocycle space of p, and will be denoted by Q(p) [subset or equal to] [T.sup.2n].

We will now give a parametric description for the cocycle space Q(p) [subset or equal to] [T.sup.2n] of a tropical Wick vector p [member of] [T.sup.P(n)]. For this purpose we first introduce the concept of tropical convexity.

Definition 6.5 A set X [subset or equal to] [T.sup.N] is called tropically convex if it is closed under tropical linear combinations, i.e., for any [x.sub.1], ..., [x.sub.r] [member of] X and any [[lambda].sub.1], ..., [[lambda].sub.r] [member of] T we have that [[lambda].sub.1] [dot encircle] [x.sub.1] [direct sum] ... [direct sum] [[lambda].sub.r] [dot encircle] [x.sub.r] [member of] X. For any [a.sub.1], ..., [a.sub.r] [member of] [T.sup.N], their tropical convex hull is defined to be tconvex([a.sub.1], ..., [a.sub.r]) := {[[lambda].sub.1] [dot encircle] [a.sub.1] [direct sum] ... [direct sum] [[lambda].sub.r] [dot encircle] [a.sub.r] : [[lambda].sub.1], ..., [[lambda].sub.r] [member of] T}; it is the smallest tropically convex set containing the vectors [a.sub.1], ..., [a.sub.r]. A set of the form tconvex([a.sub.1], ..., [a.sub.r]) is usually called a tropical polytope.

Theorem 6.6 Let p [member of] [T.sup.P(n)] be a tropical Wick vector. Then the cocycle space Q(p) [subset or equal to] [T.sup.2n] of p is the set of admissible vectors in the tropical convex hull of the cocircuits of p.

Theorem 6.6 implies that if p is a tropical Wick vector and M is its associated even [DELTA]-matroid then the set of supports of all cocycles of p is precisely the set of cocycles of M (see Definition 3.6), so our definition of cocycles for tropical Wick vectors extends the usual definition of cocycles for even [DELTA]-matroids to the valuated setup. Theorem 6.6 implies the following corollary.

Corollary 6.7 Let p [member of] [T.sup.P(n)] be a tropical Wick vector. Then Q([p.sup.*]) [subset or equal to] [T.sup.2n] is the set of admissible vectors in Q[(p).sup.T].

6.1 Tropical Linear Spaces

We will now specialize some of the results presented above to tropical Plucker vectors (i.e. valuated matroids). In this way we will unify several results for tropical linear spaces given by Murota and Tamura in [MT01], Speyer in [Spe08], and Ardila and Klivans in [AK06]. Unless otherwise stated, all matroidal terminology in this section will refer to the classical matroidal notions and not to the [DELTA]-matroidal notions discussed above.

Definition 6.8 Let p = ([p.sub.S]) [member of] [T.sup.P(n)] be a tropical Plucker vector of rank [r.sub.p]. For T [member of] P(n) of size [r.sub.p] + 1, we define the vector [d.sub.T] [member of] [T.sup.n] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If supp([d.sub.T]) [not equal to] 0 then supp([d.sub.T]) is one of the circuits of the matroid [M.sub.p] whose collection of bases is supp(p). We will say that the vector d [member of] [T.sup.n] is a Plucker circuit of p if supp(d) [not equal to] 0 and there is some T [member of] P(n) of size [r.sub.p] + 1 and some [lambda] [member of] R such that d = [lambda] [dot encircle] [d.sub.T] (or in classical notation, d = [d.sub.T] + [lambda] x 1, where 1 denotes the vector in [T.sup.n] whose coordinates are all equal to 1). It is not hard to see that C([M.sub.p]) = {supp(d) : d is a Plucker circuit of p}, so this notion of Plucker circuits generalizes the notion of circuits for matroids to the "valuated" setup. The collection of Plucker circuits of p will be denoted by PC(p). A Plucker cocircuit of p is just a Plucker circuit of the dual vector [p.sup.*], i.e., a vector of the form [lambda] [dot encircle] [d.sub.T] where T [member of] P(n) has size n - [r.sub.p] - 1 and [d*.sub.T] [member of] [T.sub.n] denotes the vector

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The reason we are using the name "Plucker circuits" is just so that they are not confused with the circuits of p in the [DELTA]-matroidal sense; a more appropriate name (but not very practical for the purposes of this paper) would be "circuits in type A" (while the [DELTA]-matroidal circuits are "circuits in type D"). The following definition was introduced by Speyer in [Spe08].

Definition 6.9 Let p [member of] [T.sup.P(n)] be a tropical Plucker vector. The space [L.sub.p] := PC[(p).sup.T] [subset or equal to] [T.sup.n] is called the tropical linear space associated to p.

The tropical linear space [L.sub.p] should be thought of as the space of cocyles of p "in type A" (while Q(p) is the space of cocycles of p "in type D"). Tropical linear spaces have a very special geometric importance, for more information the reader is invited to consult [Spe08]. The following proposition will allow us to apply the "type D" results that we got in previous sections to the study of tropical linear spaces.

Proposition 6.10 Let p [member of] [T.sup.P(n)] be a tropical Plucker vector, and let [L.sub.p] [subset or equal to] [T.sup.n] be its associated linear space. Then, under the natural identification [T.sup.2n] [congruent to] [T.sup.n] x [T.sup.n], we have C[(p).sup.T] = [L.sub.p] x [L.sub.p]*.

The following theorem provides a parametric description of any tropical linear space. It was first proved by Murota and Tamura in [MT01]. In the case of realizable tropical linear spaces it also appears in work of Yu and Yuster [YY07]. It follows easily from the results in the previous section.

Theorem 6.11 Suppose p [member of] [T.sup.P(n)] is a tropical Plucker vector. Then the tropical linear space [L.sub.p] [subset or equal to] [T.sup.n] is the tropical convex hull of the Plucker cocircuits of p.

It is instructive to see what Theorem 6.11 is saying when applied to tropical Plucker vectors with only zero and infinity entries (what is sometimes called the "constant coefficient case" in tropical geometry). In this case, since the complements of unions of cocircuits of the associated matroid M are exactly the flats of M, we get precisely the description of the tropical linear space in terms of the flats of M that was given by Ardila and Klivans in [AK06].

Another useful application of our results to the study of tropical linear spaces is the following. It was also proved by Murota and Tamura in [MT01].

Theorem 6.12 If p [member of] [T.sup.P(n)] is a tropical Plucker vector then [L.sub.p]* = [L.sup.T.sub.p]. In particular, for any tropical linear space L, we have [([L.sup.T]).sup.T] = L.

7 Isotropical Linear Spaces

Definition 7.1 Let L [subset or equal to] [T.sup.2n] be an n-dimensional tropical linear space. We say that L is (totally) isotropic if for any two x, y [member of] L we have that the minimum min([x.sub.1] +[y.sub.1]*, ..., [x.sub.n] + [y.sub.n]*, [x.sub.1]* +[y.sub.1], ..., [x.sub.n]* +[y.sub.n]) is achieved at least twice (or it is equal to [infinity]). In this case, we also say that L is an isotropical linear space. Note that if K = C{{t}} and V = [K.sup.2n], the tropicalization of any n-dimensional isotropic subspace U of V (see Section 2) is an isotropical linear space L [subset or equal to] [T.sup.2n]. In this case we say that L is isotropically realizable by U.

We mentioned in Section 2 that if U is an isotropic linear subspace then its vector of Wick coordinates w carries all the information of U. One might expect something similar to hold tropically, that is, that the valuation of the Wick vector w still carries all the information of the tropicalization of U. This is not true, as the next example shows.

Example 7.2 We present two n-dimensional isotropic linear subspaces of [C{{t}}.sup.2n] whose corresponding tropicalizations are distinct tropical linear spaces, but whose Wick coordinates have the same valuation. Take n = 4. Let [U.sub.1] be the 4-dimensional isotropic linear subspace of [C{{t}}.sup.8] defined as the rowspace of the matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and [U.sub.2] be the 4-dimensional isotropic linear subspace of [C{{t}}.sup.8] defined as the rowspace of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Their corresponding tropical linear spaces [L.sub.1] and [L.sub.2] are distinct since, for example, the Plucker coordinate indexed by the subset 343* 4* is nonzero for [U.sub.1] but zero for [U.sub.2]. However, the Wick coordinates of [U.sub.1] and [U.sub.2] are all nonzero scalars (the ones indexed by even subsets), and thus their valuations give rise to the same tropical Wick vector.

It is important to have an effective way for deciding if a tropical linear space is isotropical or not. For this purpose, if v [member of] [T.sup.2n], we call its reflection to be the vector [v.sup.r] [member of] [T.sup.2n] defined as [v.sup.r.sub.i] := [v.sub.i]*. If X [subset or equal to] [T.sup.2n] then its reflection is the set [X.sup.r] := {[x.sup.r] : x [member of] X}. The following theorem gives us a simple criterion for identifying isotropical linear spaces.

Theorem 7.3 Let L [subset or equal to] [T.sup.2n] be a tropical linear space with associated tropical Plucker vector p (whose coordinates are indexed by subsets of 2n). Then the following are equivalent:

1. L is an n-dimensional isotropical linear space.

2. [L.sup.T] = [L.sup.r].

3. [p.sub.2n\T] = [p.sub.T]* for all T [subset or equal to] 2n of size n.

If L is an isotropical linear space which is isotropically realizable by U then we have seen that the valuation p of the Wick vector w associated to U does not determine L. Nonetheless, the following theorem shows that p does determine the admissible part of L.

Theorem 7.4 Let L [subset or equal to] [T.sup.2n] be an n-dimensional isotropical linear space which is isotropically realizable by the isotropic subspace U [subset or equal to] [C{{t}}.sup.2n]. Let p [member of] [T.sup.P(n)] be the tropical Wick vector obtained as the valuation of the Wick vector w associated to U. Then the set ofadmissible vectors in L is the cocycle space Q(p) [subset or equal to] [T.sup.2n].

References

[AK06] Federico Ardila and Caroline J. Klivans. The Bergman complex of a matroid and phylogenetic trees. J. Combin. Theory Ser. B, 96(1):38-49, 2006.

[BGW03] Alexandre V. Borovik, Israel M. Gelfand, and Neil White. Coxeter matroids, volume 216 of Progress in Mathematics. Birkhauser Boston Inc., Boston, MA, 2003.

[Bou87] Andre Bouchet. Greedy algorithm and symmetric matroids. Math. Programming, 38(2):147-159, 1987.

[DW91] Andreas W. M. Dress and Walter Wenzel. A greedy-algorithm characterization of valuated [DELTA]-matroids. Appl. Math. Lett., 4(6):55-58, 1991.

[DW92] Andreas W. M. Dress and Walter Wenzel. Valuated matroids. Adv. Math., 93(2):214-250, 1992.

[Jen] Anders N. Jensen. Gfan, a software system for Grobner fans and tropical varieties. Available at http://www.math.tu-berlin.de/~jensen/software/gfan/gfan.html.

[MT01] Kazuo Murota and Akihisa Tamura. On circuit valuation of matroids. Adv. in Appl. Math., 26(3):192-225, 2001.

[Mur97] Kazuo Murota. Characterizing a valuated delta-matroid as a family of delta-matroids. J. Oper. Res. Soc. Japan, 40(4):565-578, 1997.

[Mur06] Kazuo Murota. M-convex functions on jump systems: a general framework for minsquare graph factor problem. SIAM J. Discrete Math., 20(1):213-226 (electronic), 2006.

[Spe08] David E. Speyer. Tropical linear spaces. SIAM J. Discrete Math., 22(4):1527-1558, 2008.

[YY07] Josephine Yu and Debbie S. Yuster. Representing tropical linear spaces by circuits. In Proceedings of Formal Power Series and Algebraic Combinatorics (Tianjin, China), 2007.

Felipe Rincon (1) ([dagger])

(1) University of California, Berkeley, CA, USA

([dagger]) Supported as a Graduate Student Researcher through the U.S. National Science Foundation (DMS-0456960 and DMS0757207). felipe@math.berkeley.edu
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Rincon, Felipe
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2011
Words:7662
Previous Article:Cyclic sieving for two families of non-crossing graphs.
Next Article:Submaximal factorizations of a Coxeter element in complex reflection groups.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters