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.

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:

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