Tropical semirings, matrices, and polynomials

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

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

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)

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)

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

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

Examples

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

julia> det(A)
(5)

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

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)