# Tropical semirings, matrices, and polynomials

## Introduction

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.

## Constructor

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

tropical_semiringMethod
tropical_semiring(M::Union{typeof(min),typeof(max)}=min)

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

Warning
• +, *, /, 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,-∞)
(3)

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

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

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
(-1//2)

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)
(0)

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

## Properties

Objects of type TropicalSemiring have the following properties:

conventionMethod
convention(T::TropicalSemiring)

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.

Examples

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)
source

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

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

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

Examples

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
source
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].

Note

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.

Examples

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

julia> det(A)
(5)
source
tropical_polynomialMethod
tropical_polynomial(f::Union{<:MPolyRingElem,<:PolyRingElem},nu::TropicalSemiringMap)

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

Examples

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)
source