GitHub

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_semiring — Method
tropical_semiring(M::Union{typeof(min),typeof(max)}=min)

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

The operations +, *, /, and ^ are used for tropical addition, tropical multipliciation, tropical division, and tropical exponentiation, respectively. Zeroes of tropical semirings are printed as infty or -infty instead of their proper unicode characters. To enable unicode in the current and future sessions, run allow_unicode(true).

Warning
  • There is no additive inverse or subtraction in the tropical semiring. Negating a tropical number or subtracting two tropical numbers will raise an error.
  • Mixing normal and tropical numbers in larger arithmetic expressions can lead to unexpected results: Suppose T is the min-plus semiring. OSCAR will interpret 1*T(1) as T(1)*T(1) and return T(2). Due to how julia handles arithmetic expressions however, we have 1*1*T(1)=(1*1)*T(1)=1*T(1)= T(2) which is not T(1)*T(1)*T(1). The 1*1 is performed using integer multiplication, as the single multiplication does not know that a tropical number is involved in the overall arithmetic expression.

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:

convention — Method
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:

det — Method
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
roots — Method
roots(f::PolyRingElem{<:TropicalSemiringElem})

Return the tropical roots of a univariate tropical polynomial f, i.e., the variable values where the min or max is attained at least twice.

Examples

julia> R,x = polynomial_ring(tropical_semiring(min),:x)
(Univariate polynomial ring in x over min tropical semiring, x)

julia> f = 1*x^2+x+0
(1)*x^2 + x + (0)

julia> roots(f)
2-element Vector{QQFieldElem}:
 0
 -1

julia> R,x = polynomial_ring(tropical_semiring(max),:x)
(Univariate polynomial ring in x over max tropical semiring, x)

julia> f = 1*x^2+x+0
(1)*x^2 + x + (0)

julia> roots(f)
1-element Vector{QQFieldElem}:
 -1//2
source
tropical_polynomial — Method
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