Matrices over tropical semirings

AUTHORS:

  • Xavier Caruso (2025-11): initial version

class sage.rings.semirings.tropical_matrix.Matrix_tropical_dense[source]

Bases: Matrix_generic_dense

A class for dense matrices over a tropical semiring.

EXAMPLES:

sage: from sage.rings.semirings.tropical_matrix import Matrix_tropical_dense
sage: T = TropicalSemiring(QQ)
sage: M = matrix(T, [[1, 2], [3, 4]])
sage: isinstance(M, Matrix_tropical_dense)
True

>>> from sage.all import *
>>> from sage.rings.semirings.tropical_matrix import Matrix_tropical_dense
>>> T = TropicalSemiring(QQ)
>>> M = matrix(T, [[Integer(1), Integer(2)], [Integer(3), Integer(4)]])
>>> isinstance(M, Matrix_tropical_dense)
True
extremum_cycle_mean()[source]

Return the extremal (that is, minimal if the addition is max and maximal is the addition is min) mean weight of this matrix It is also the smallest/largest eigenvalue of this matrix.

ALGORITHM:

We implement Karp’s algorithm described in [But2010], Section 1.6.1.

EXAMPLES:

sage: T = TropicalSemiring(QQ, use_min=False)
sage: M = matrix(T, [[-2,  1, -3],
....:                [ 3,  0,  3],
....:                [ 5,  2,  1]])
sage: M.extremum_cycle_mean()
3

>>> from sage.all import *
>>> T = TropicalSemiring(QQ, use_min=False)
>>> M = matrix(T, [[-Integer(2),  Integer(1), -Integer(3)],
...                [ Integer(3),  Integer(0),  Integer(3)],
...                [ Integer(5),  Integer(2),  Integer(1)]])
>>> M.extremum_cycle_mean()
3


sage: T = TropicalSemiring(QQ)
sage: z = T.zero()
sage: M = matrix(T, [[z, 1, 10, z],
....:                [z, z,  3, z],
....:                [z, z,  z, 2],
....:                [8, 0,  z, z]])
sage: M.extremum_cycle_mean()
5/3
[Python] 
>>> from sage.all import *
>>> T = TropicalSemiring(QQ)
>>> z = T.zero()
>>> M = matrix(T, [[z, Integer(1), Integer(10), z],
...                [z, z,  Integer(3), z],
...                [z, z,  z, Integer(2)],
...                [Integer(8), Integer(0),  z, z]])
>>> M.extremum_cycle_mean()
5/3
kleene_star()[source]

alias of strong_transitive_closure().

strong_transitive_closure()[source]

Return the string transitive closure of this matrix \(M\), that is, by definition

\[I \oplus A \oplus A^2 \oplus A^3 \oplus A^4 \oplus \cdots\]

or raise an error if this sum does not converge.

ALGORITHM:

We implement the Floyd-Warshall algorithm described in [But2010], Algorithm 1.6.21.

See also

weak_transitive_closure()

EXAMPLES:

sage: T = TropicalSemiring(QQ, use_min=False)
sage: M = matrix(T, [[-5, -2, -6],
....:                [ 0, -3,  0],
....:                [ 2, -1, -2]])
sage: M.strong_transitive_closure()
[ 0 -2 -2]
[ 2  0  0]
[ 2  0  0]

>>> from sage.all import *
>>> T = TropicalSemiring(QQ, use_min=False)
>>> M = matrix(T, [[-Integer(5), -Integer(2), -Integer(6)],
...                [ Integer(0), -Integer(3),  Integer(0)],
...                [ Integer(2), -Integer(1), -Integer(2)]])
>>> M.strong_transitive_closure()
[ 0 -2 -2]
[ 2  0  0]
[ 2  0  0]


sage: T = TropicalSemiring(QQ)
sage: M = matrix(T, [[-5, -2, -6],
....:                [ 0, -3,  0],
....:                [ 2, -1, -2]])
sage: M.strong_transitive_closure()
Traceback (most recent call last):
...
ValueError: negative cycle exists
[Python] 
>>> from sage.all import *
>>> T = TropicalSemiring(QQ)
>>> M = matrix(T, [[-Integer(5), -Integer(2), -Integer(6)],
...                [ Integer(0), -Integer(3),  Integer(0)],
...                [ Integer(2), -Integer(1), -Integer(2)]])
>>> M.strong_transitive_closure()
Traceback (most recent call last):
...
ValueError: negative cycle exists
weak_transitive_closure()[source]

Return the weak transitive closure of this matrix \(M\), that is, by definition

\[A \oplus A^2 \oplus A^3 \oplus A^4 \oplus \cdots\]

or raise an error if this sum does not converge.

ALGORITHM:

We implement the Floyd-Warshall algorithm described in [But2010], Algorithm 1.6.21.

See also

strong_transitive_closure()

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: z = T.zero()
sage: M = matrix(T, [[z, 1, 10, z],
....:                [z, z,  3, z],
....:                [z, z,  z, 2],
....:                [8, 0,  z, z]])
sage: M.weak_transitive_closure()
[14  1  4  6]
[13  5  3  5]
[10  2  5  2]
[ 8  0  3  5]

>>> from sage.all import *
>>> T = TropicalSemiring(QQ)
>>> z = T.zero()
>>> M = matrix(T, [[z, Integer(1), Integer(10), z],
...                [z, z,  Integer(3), z],
...                [z, z,  z, Integer(2)],
...                [Integer(8), Integer(0),  z, z]])
>>> M.weak_transitive_closure()
[14  1  4  6]
[13  5  3  5]
[10  2  5  2]
[ 8  0  3  5]

We check that the minimal cycle mean of \(M\) is the largest value \(a\) such that \((-a) \otimes M\) has a weak transitive closure:

sage: M.extremum_cycle_mean()
5/3
sage: aM = T(-5/3) * M
sage: aM.weak_transitive_closure()
[22/3 -2/3  2/3    1]
[   8    0  4/3  5/3]
[20/3 -4/3    0  1/3]
[19/3 -5/3 -1/3    0]
sage: bM = T(-2) * M
sage: bM.weak_transitive_closure()
Traceback (most recent call last):
...
ValueError: negative cycle exists
[Python] 
>>> from sage.all import *
>>> M.extremum_cycle_mean()
5/3
>>> aM = T(-Integer(5)/Integer(3)) * M
>>> aM.weak_transitive_closure()
[22/3 -2/3  2/3    1]
[   8    0  4/3  5/3]
[20/3 -4/3    0  1/3]
[19/3 -5/3 -1/3    0]
>>> bM = T(-Integer(2)) * M
>>> bM.weak_transitive_closure()
Traceback (most recent call last):
...
ValueError: negative cycle exists