Tropical semirings, matrices, and polynomials


In OSCAR, the tropical semiring is either

  • the min-plus semiring $(\mathbb{Q}\cup\{+\infty\},\oplus,\odot)$ with $a\oplus b=\min(a,b)$ and $a\odot b=a+b$,
  • the max-plus semiring $(\mathbb{Q}\cup\{-\infty\},\oplus,\odot)$ with $a\oplus b=\max(a,b)$ and $a\odot b=a+b$.

Whereas tropical semirings in [MS15] and [Jos21] are extensions of the real numbers, tropical semirings in OSCAR are an extension of the rational numbers to avoid precision issues.


Objects of type TropicalSemiring, as well as matrices and polynomials thereover, can be constructed as follows:


Return the min-plus (default) or max-plus semiring.

  • +, *, /, and ^ are used for tropical addition, tropical multipliciation, tropical division, and tropical exponentiation, respectively.
  • There is no additive inverse or subtraction in the tropical semiring. Negating a tropical number or subtracting two tropical numbers will raise an error.
  • Zeroes of tropical semirings are printed as infty or -infty instead of their proper unicode characters. To enabled unicode in the current and future sessions, run allow_unicode(true).

Examples (basic arithmetic)

julia> T = tropical_semiring() # = tropical_semiring(min)
Min tropical semiring

julia> T = tropical_semiring(max)
Max tropical semiring

julia> 0*T(3) + 1*T(1)^2 + zero(T) # = max(0+3,1+2*1,-∞)

julia> T(0) == 0    # checks whether the tropical number is 0

julia> iszero(T(0)) # checks whether the tropical number is neutral element of addition

Examples (polynomials)

julia> T = tropical_semiring()
Min tropical semiring

julia> Tx,(x1,x2) = polynomial_ring(T,2)
(Multivariate polynomial ring in 2 variables over min tropical semiring, AbstractAlgebra.Generic.MPoly{TropicalSemiringElem{typeof(min)}}[x1, x2])

julia> f = x1 + -1*x2 + 0
x1 + (-1)*x2 + (0)

julia> evaluate(f,T.([-1//2,1//2])) # warning: omitting T() gives an error

Examples (matrices)

julia> T = tropical_semiring()
Min tropical semiring

julia> A = identity_matrix(T, 2) # = tropical identity matrix
[  (0)   infty]
[infty     (0)]

julia> 2*A
[  (2)   infty]
[infty     (2)]

julia> A*A
[  (0)   infty]
[infty     (0)]

julia> det(A)

julia> minors(A,1)
4-element Vector{TropicalSemiringElem{typeof(min)}}:


Objects of type TropicalSemiring have the following properties:


Return min if T is the min tropical semiring, return max if T is the max tropical semiring. Works similarly for tropical numbers, tropical vectors and matrices, and tropical polynomials.


julia> T = tropical_semiring(min)
Min tropical semiring

julia> convention(T)
min (generic function with 27 methods)

julia> T = tropical_semiring(max)
Max tropical semiring

julia> convention(T)
max (generic function with 27 methods)

Other functions related to TropicalSemiring, matrices, and polynomials thereover include:

det(M::MatrixElem{T}) where {T <: RingElement}

Return the determinant of the matrix $M$. We assume $M$ is square.


julia> R, x = polynomial_ring(QQ, "x")
(Univariate polynomial ring in x over rationals, x)

julia> A = R[x 1; 1 x^2];

julia> d = det(A)
x^3 - 1
det(A::MatrixElem{<: TropicalSemiringElem})

Return the tropical determinant of A. That is, this function evaluates the tropicalization of the ordinary determinant considered as a multivariate polynomial at A.

That computation is equivalent to solving a linear assignment problem from combinatorial optimization. The implementation employs the Hungarian method, which is polynomial time. See Chapter 3 in [Jos21].


This function effectively overwrites the det command for tropical matrices. This means that functions like minors will use the tropical determinant when used on a tropical matrix.


julia> A = matrix(tropical_semiring(),[1 2; 3 4])
[(1)   (2)]
[(3)   (4)]

julia> det(A)

Given a polynomial f and a tropical semiring map nu, return the tropicalization of f as a polynomial over the tropical semiring.


julia> R, (x,y) = polynomial_ring(QQ,["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])

julia> nu = tropical_semiring_map(QQ,7)
Map into Min tropical semiring encoding the 7-adic valuation on Rational field

julia> f = 7*x+y+49
7*x + y + 49

julia> tropical_polynomial(f,nu)
(1)*x + y + (2)