Algebraic Combinatorics (ALCO)

Mével, Gurvan

Combinatorial Göttsche-Schroeter invariants in any genus

Dennin, Hugh

Pattern bounds for principal specializations of $\beta $-Grothendieck polynomials

Oba, Ryoshun

Multigraded strong Lefschetz property for balanced simplicial complexes

Abe, Takuro

Kühne, Lukas

Mücksch, Paul

Mühlherr, Leonie

Projective dimension of weakly chordal graphic arrangements

Chindris, Calin

Collins, Brett

Kline, Daniel

Hive-type polytopes for quiver multiplicities and the membership problem for quiver moment cones

Marberg, Eric

Tong, Kam Hung

Crystals for set-valued decomposition tableaux

Aval, Jean-Christophe

Samuele, Giraudo

Karaboghossian, Théo

Tanasa, Adrian

Operads on graphs: extending the pre-Lie operad and general construction

Davis, James A.

Polhill, John

Smith, Ken

Swartz, Eric

Nonabelian partial difference sets constructed using abelian techniques

Shitov, Yaroslav

ALGEBRAIC
 COMBINATORICS
Yaroslav Shitov
Positive tropicalizations of determinantal varieties and the Gondran–Minoux rank
Volume 8, issue 5 (2025), p. 1349-1352.
https://doi.org/10.5802/alco.440
© The author(s), 2025.
This article is licensed under the
CREATIVE COMMONS ATTRIBUTION (CC-BY) 4.0 LICENSE.
http://creativecommons.org/licenses/by/4.0/
Algebraic Combinatorics is published by The Combinatorics Consortium
and is a member of the Centre Mersenne for Open Scientific Publishing
www.tccpublishing.org www.centre-mersenne.org
e-ISSN: 2589-5486
Algebraic Combinatorics
Volume 8, issue 5 (2025), p. 1349–1352
https://doi.org/10.5802/alco.440
Positive tropicalizations of determinantal
varieties and the Gondran–Minoux rank
Yaroslav Shitov
Abstract We point out to a connection of an old approach of Gondran and Minoux to ranks
of matrices over the algebra (R, max, +) and a recent work of Brandenburg, Loho, and Sinn
on positive tropicalizations of algebraic varieties. This leads to examples of tropical varieties
and their tropical bases which are not the corresponding positive tropical generating sets. In
particular, we show that the d × d minors of a d × n matrix of variables form a positive tropical
generating set if and only if either (1) d = n or (2) d ⩽ 4.
1. Positive tropicalizations
A common object of tropical geometry is the field C{{t}} of Puiseux series with the
corresponding valuation, which takes the formal sum
p =
∑
α∈Q
pαt
α with pα ∈ C
to the minimal a for which pa ̸= 0, that is, a = val p, and such an a exists because,
by the definition, all exponents α with pα ̸= 0 have a common denominator and
minimal element. The positive part C+ is the set of all series p ∈ C{{t}} for which
the coefficient pa in the leading term pata is real and positive [1, 3]. The mapping
(1.1) tropC+(X) = {val x : x ∈ X ∩ (C+)
n} ⊆ Rn
sending any algebraic variety X ⊂ (C{{t}})n to a subset of Rn is called the positive
tropicalization, where the overline denotes the Euclidean closure [1, 3].
Definition 1.1 ([3, Definition 2.3]). A set of polynomials F ⊂ R[x1, . . . , xn] is called
a positive tropical generating set of an ideal I ⊂ R[x1, . . . , xn] if
tropC+V (I) =
⋂
f∈F
tropC+V (f),
where V (I) ⊆ (C{{t}})n is the intersection of the zero loci of all polynomials in I.
As an alternative in [3, Definition 2.3], one replaces C+ by (C+) ∩ R{{t}} in (1.1),
but our results and arguments are valid in both settings. Instead, one can replace C+
with the set of all nonzero series in C{{t}}, and the resulting version of Definition 1.1
gives the concept of tropical bases, see [6]. Indeed, there has been a known problem
that asked one to describe the triples (d, n, r) for which the (r + 1) × (r + 1) minors of
a d×n matrix of variables form a tropical basis of the variety that they generate, that
Manuscript received 23rd November 2024, revised 12th March 2025, accepted 13th May 2025.
Keywords. Gondran–Minoux rank, tropical varieties.
ISSN: 2589-5486 http://algebraic-combinatorics.org/
Yaroslav Shitov
is, the set of all d×n matrices of the rank at most r, see [5]. The study of this question
begins in the work of Develin, Santos, Sturmfels [6], and its resolution culminates in
the article of the present author, see [9] and references therein. The authors of [3]
discuss a similar question in the case of positive generating sets.
Question 1.2 ([3, Question 2.8]). Is there a tropical variety T and a tropical basis B
of T such that B is not a positive tropical generating set of T ?
We answer this question in the positive, and we correct a statement in Table 1
in [3]. Indeed, with a reference to [3, Theorem 2.4], it is said that the (r + 1) × (r + 1)
minors of a d × n matrix of variables form a positive tropical generating set, provided
that r + 1 = d ⩽ n, see [3, Table 1]. Of course, this reasoning is true if the additional
condition d = n is imposed. However, if one has d < n, the variety of rank-deficient
matrices is not anymore cut by a single minor, and Theorem 2.4 in [3] may not be
applicable. This issue was not addressed in the correction either [4], and, in fact, it
turns out that, in the case d < n, the answer depends on (d, n).
Theorem 1.3. Assume d ⩽ n. The d × d minors of a d × n matrix of variables form
a positive tropical generating set if and only if either (1) d = n or (2) d ⩽ 4.
In particular, the set of all d×d minors is not a positive tropical generating set, for
a d × n matrix of variables with 5 ⩽ d < n. However, the d × d minors give tropical
bases for d × n matrices, for all possible values with d ⩽ n, as explained in [6, 9], and
hence we get a positive answer to Question 1.2.
2. Gondran–Minoux rank
As it turns out, the description of the set tropC+V (f) is quite well known in the case
when f is the determinant of an m × m matrix, and the corresponding results, stated
in different notation, arise to the works of Gondran and Minoux [7].
Definition 2.1 ([2, Definition 3.5]). The tropical bideterminant of a real m×m matrix
A is the pair (|A+|, |A−|) defined as follows, where Am and Bm are the sets of all
even and odd permutations of {1, . . . , m}, respectively:
|A+| = min
σ∈Am
{a1σ1 + . . . + amσm}, |A−| = min
τ∈Bm
{a1τ1 + . . . + amτm}.
Definition 2.2 ([2, Definition 2.11]). The rows of an m × n real matrix A are called
linearly dependent in the sense of Gondran-Minoux (or just GM-dependent) if there is
a partition of {1, . . . , m} into two disjoint subsets I and J , and there are real numbers
(λ1, . . . , λn) such that, for any k ∈ {1, . . . , n}, one has
min
i∈I
{λi + aik} = min
j∈J
{λj + ajk}.
The old result relating the bideterminant to GM-dependence is as follows.
Theorem 2.3 (Gondran–Minoux theorem [2, 7]). For an m × m real matrix A, one
has |A+| = |A−| if and only if the rows of A are GM-dependent.
The Gondran–Minoux theorem is equivalent to the description of the positive trop-
icalizations of the varieties of singular matrices, which can appear in Section 8 of [6],
Proposition 3.1 in [3], Theorem 4.1 in [1], and Lemma 2.6 in [10].
Theorem 2.4. If X is an m × m matrix of variables, then tropC+V (det X) coincides
with the set of all m × m matrices A such that |A+| = |A−|.
In fact, Definition 2.2 gives a deeper description of the positive tropicalization of
the variety of rank deficient matrices.
Algebraic Combinatorics, Vol. 8 #5 (2025) 1350
Positive tropicalizations of determinantal varieties and GM-rank
Theorem 2.5. Let d and n be integers with 1 ⩽ d ⩽ n, and let Vdn be the variety
of all d × n matrices which have the ranks less than d over C{{t}}. For a d × n real
matrix A, if the rows of A are GM-dependent, then A ∈ tropC+(Vdn).
Proof. We apply Definition 2.2. Indeed, up to scaling and permutations of rows, we
can assume that there is an index s ∈ {2, . . . , d − 1} such that the condition
(2.1) min{a1k, . . . , ask} = min{as+1 k, . . . , adk}
holds for all k ∈ {1, . . . , n}, and we write ı̂(k) to denote one of the indices that deliver
the minimum to the left-hand side of (2.1). We proceed with the definition of the
d × n matrix B with entries in C+ as follows. Indeed, for any k ∈ {1, . . . , n}, for any
i ∈ {1, . . . , s} with i ̸= ı̂(k), and, for any j ∈ {s + 1, . . . , d}, we define
(bjk = tajk ) & (bik = ε · taik ) & (bı̂k =
∑
j bjk −
∑
i bik)
with ε ∈ (0, 1/d). For all q ∈ {1, . . . , d}, we get val bqk = aqk with positive leading
terms, and the row sums over {1, . . . , s} and {s + 1, . . . , d} coincide, so rk B < d. □
The part (2) of Theorem 1.3 is clear from the following result. Here, we use
• the bideterminantal Gondran–Minoux rank δ(A), which is the largest order
of a square submatrix M of a real matrix A with |M+| ≠ |M−|, and
• the Gondran–Minoux row rank GMr(A), which is the largest cardinality of a
GM-independent family of the rows of A, see [2, 8].
Theorem 2.6 ([8, Theorem 4.6]). If δ(A) ⩽ 3, then GMr(A) = δ(A).
Theorem 2.7. Let d, n be integers with d ∈ {1, 2, 3, 4} and d ⩽ n. Then the d × d
minors of a d × n matrix of variables form a positive tropical generating set.
Proof. Let A be a d × n real matrix. If δ(A) = d, then some d × d submatrix M of A
has |M+| ̸= |M−|, and its determinant polynomial f satisfies A /∈ tropC+ V (f), due
to Theorem 2.4. If δ(A) < d, then we have A ∈ tropC+ Vdn by Theorems 2.5 and 2.6.
Therefore, the family tropC+ Vdn is the intersection of all tropicalizations tropC+ V (f)
in which f runs over all determinants of the d × d minors, as desired. □
We complete the proof of Theorem 1.3 with a study of the matrix in [8, Exam-
ple 3.1]. Namely, we present a 5 × 6 matrix A each of whose 5 × 5 submatrices can
be lifted to singular matrices over C+ with the degrees of the entries equal to the
corresponding entries of A, but A cannot be lifted to a rank-four matrix itself.
Example 2.8. The matrix
A =

0 1 0 0 1 1
0 1 1 1 0 0
1 1 0 0 0 0
1 0 0 1 0 1
1 0 1 0 1 0

satisfies δ(A) = 4, but the positive tropicalization tropC+ V56 does not contain A.
Proof. The property δ(A) = 4 can be checked straightforwardly, and, due to the
symmetry of the construction, it is sufficient to check the property |M+| = |M−| for
the matrices M obtained from A by removing either the first column or last column.
Also, the full details of the corresponding checking appear in [8, Example 3.1].
Algebraic Combinatorics, Vol. 8 #5 (2025) 1351
Yaroslav Shitov
As to the second assertion, we argue by absurdum and take a 5 × 6 lifting Bε with
entries in C+ such that rk Bε ⩽ 4 and val bij → aij as ε → 0. Up to scaling, we get
Bε =

1 0 z1 z3 0 0
1 0 0 0 x5 x7
0 0 y1 y2 y3 y4
0 1 x2 0 x6 0
0 1 0 x4 0 x8
 + C
with real xk > 0, ys > 0, zt ⩾ 0 and val cij > 0. If λ1B1 + λ2B2 + . . . + λ5B5 = 0 is
a linear combination of the rows of Bε with λi ∈ C{{t}} that certifies the inequality
rk Bε ⩽ 4, then we use the scaling again and assume
(2.2) min{val λ1, val λ2, val λ3, val λ4, val λ5} = 0,
and the constant terms of λi are denoted as µi ∈ C. We have µ1 + µ2 = µ4 + µ5 = 0
and µ1 z1 + µ4 x2 = −y1 µ3, µ1 z3 + µ5 x4 = −y2 µ3, µ2 x5 + µ4 x6 = −y3 µ3, and also
µ2 x7 + µ5 x8 = −y4 µ3. Using the further notation (α, β, γ) = (µ1, µ4, −µ3), we get
z1α + x2β = y1γ, z3α − x4β = y2γ, −x5α + x6β = y3γ, −x7α − x8β = y4γ and
(2.3) (x2 x5 + z1 x6) β = (x5 y1 + z1 y3) γ, −(x4 x7 + z3 x8) β = (x7 y2 + z3 y4) γ
or ((x4 x7 + z3 x8) · (x5 y1 + z1 y3) + (x2 x5 + z1 x6) · (x7 y2 + z3 y4)) · γ = 0, and this
gives γ = 0. Using (2.3), we get β = 0 and hence α = 0, which implies that all
coefficients (µ1, µ2, µ3, µ4, µ5) are zero, and this is a contradiction to (2.2). □
Therefore, the d × d minors of a d × n matrix are not a positive tropical generating
set if n > d ⩾ 5, which completes the proof of Theorem 1.3.
Acknowledgements. I thank David Speyer for careful reading of a draft and discussion,
and editors and reviewers for processing the article and a detailed review report.
References
[1] Abeer Al Ahmadieh, May Cai, and Josephine Yu, Real and Positive Tropicalizations of Sym-
metric Determinantal Varieties, 2024, https://arxiv.org/abs/2409.17462.
[2] Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Linear independence over trop-
ical semirings and beyond, in Tropical and idempotent mathematics, Contemp. Math., vol. 495,
Amer. Math. Soc., Providence, RI, 2009, pp. 1–38.
[3] Marie-Charlotte Brandenburg, Georg Loho, and Rainer Sinn, Tropical positivity and determi-
nantal varieties, Algebr. Comb. 6 (2023), no. 4, 999–1040.
[4] Marie-Charlotte Brandenburg, Georg Loho, and Rainer Sinn, Corrigendum to “Tropical Posi-
tivity and Determinantal Varieties”, Algebraic Combinatorics 7 (2024), no. 3, 749–751.
[5] Melody Chan, Anders Jensen, and Elena Rubei, The 4 × 4 minors of a 5 × n matrix are a
tropical basis, Linear Algebra Appl. 435 (2011), no. 7, 1598–1611.
[6] Mike Develin, Francisco Santos, and Bernd Sturmfels, On the rank of a tropical matrix, in
Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge
Univ. Press, Cambridge, 2005, pp. 213–242.
[7] M. Gondran and M. Minoux, Linear Algebra in Dioids: A Survey of Recent Results, in Algebraic
and Combinatorial Methods in Operations Research (R. E. Burkard, R. A. Cuninghame-Green,
and U. Zimmermann, eds.), North-Holland Mathematics Studies, vol. 95, North-Holland, 1984,
pp. 147–163.
[8] Ya. N. Shitov, Matrices with different Gondran–Minoux and determinantal ranks over max-
algebras, Journal of Mathematical Sciences 163 (2009), no. 5, 598–624.
[9] Yaroslav Shitov, When do the r-by-r minors of a matrix form a tropical basis?, J. Combin.
Theory Ser. A 120 (2013), no. 6, 1166–1201.
[10] Cynthia Vinzant, Real radical initial ideals, J. Algebra 352 (2012), 392–407.
Yaroslav Shitov, Izumrudnaya ulitsa, dom 65, kvartira 4, 129346 Moscow, Russia
E-mail : yaroslav-shitov@yandex.ru
Algebraic Combinatorics, Vol. 8 #5 (2025) 1352


Positive tropicalizations of determinantal varieties and the Gondran–Minoux rank

Not a member yet