ALGEBRAIC STRUCTURES OF TROPICAL MATHEMATICS

arXiv:1305.3906v1 [math.RA] 16 May 2013

ZUR IZHAKIAN, MANFRED KNEBUSCH, AND LOUIS ROWEN
Abstract. Tropical mathematics often is defined over an ordered cancellative monoid M, usually taken to
be (R, +) or (Q , +). Although a rich theory has arisen from this viewpoint, cf. [L1], idempotent semirings
possess a restricted algebraic structure theory, and also do not reflect certain valuation-theoretic properties,
thereby forcing researchers to rely often on combinatoric techniques.
In this paper we describe an alternative structure, more compatible with valuation theory, studied by
the authors over the past few years, that permits fuller use of algebraic theory especially in understanding
the underlying tropical geometry. The idempotent max-plus algebra A of an ordered monoid M is replaced
by R := L × M, where L is a given indexing semiring (not necessarily with 0). In this case we say R layered
by L. When L is trivial, i.e, L = {1}, R is the usual bipotent max-plus algebra. When L = {1, ∞} we
recover the “standard” supertropical structure with its “ghost” layer. When L = N we can describe multiple
roots of polynomials via a “layering function” s : R → L.
Likewise, one can define the layering s : R(n) → L(n) componentwise; vectorsPv1 , . . . , vm are called
tropically dependent if each component of some nontrivial linear combination
αi vi is a ghost, for
“tangible” αi ∈ R. Then an n × n matrix has tropically dependent rows iff its permanent is a ghost.
We explain how supertropical algebras, and more generally layered algebras, provide a robust algebraic
foundation for tropical linear algebra, in which many classical tools are available. In the process, we provide
some new results concerning the rank of d-independent sets (such as the fact that they are semi-additive),
put them in the context of supertropical bilinear forms, and lay the matrix theory in the framework of
identities of semirings.

1. Introduction
Tropical geometry, a rapidly growing area expounded for example in [Gat, ItMS, L1, MS, SS], has been
based on two main approaches. The most direct passage to tropical mathematics is via logarithms. But
valuation theory has richer algebraic applications (for example providing a quick proof of Kapranov’s theorem), and much of tropical geometry is based on valuations on Puiseux series. The structures listed above
are compatible with valuations, and in §2.4 we see how valuations fit in with this approach.
In his overview, Litvinov [L2] describes tropicalization as a process of dequantization. Thus, one is
motivated to develop the algebraic tools at the tropical level, in order to provide an intrinsic theory to
support tropical geometry and linear algebra. The main mathematical structure of tropical geometry is
the max-plus algebra, which is viewed algebraically as an ordered monoid. Considerable recent activity
[CHWW, W] concerns geometry over monoids, but the ordering provides extra structure which enables us
to draw on classical algebraic structure theory.
The max-plus algebra is fine for answering many combinatoric questions, but it turns out that a more
sophisticated structure is needed to understand the algebraic structure connected with valuations. Our
overlying objective is to translate ordered monoids into an algebraic theory supporting tropical linear algebra
and geometry, using the following approaches:
• Algebraic geometry as espoused by Zariski and Grothendieck, using varieties and commutative algebra in the context of category theory.
• Linear algebra via tropical dependence, the characteristic polynomial, and (generalized) eigenspaces.
• Algebraic formulations for more sophisticated concepts such as resultants, discriminants, and Jacobians.

Date: November 6, 2017.
2010 Mathematics Subject Classification. Primary 06F20, 11C08, 12K10, 14T05, 14T99, 16Y60; Secondary 06F25, 16D25.
Key words and phrases. tropical algebra, layered supertropical domains, polynomial semiring, d-base, s-base, bilinear form.
The research of the first and third authors was supported by the Israel Science Foundation (grant No. 448/09).
The research of the first author also was conducted under the auspices of the Oberwolfach Leibniz Fellows Programme
(OWLF), Mathematisches Forschungsinstitut Oberwolfach, Germany.
1

2

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

This approach leads to the use of polynomials and matrices, which requires two operations. Our task
has been to pinpoint the appropriate category of semirings in which to work, or equivalently, how far do we
dequantize in the process of tropicalization? In this survey we compare four structures, listed in increasing
level of refinement:
• The max-plus algebra,
• Supertropical algebra,

• Layered tropical algebras,

• Exploded supertropical algebras.

We review the layered algebra in §3, compare it to the max-plus algebra, and then in §4 survey its linear
algebraic theory, especially in terms of different notions of bases, proving a new result (Proposition 4.25)
about the semi-additivity of the rank of d-independent sets of a layered vector space. In §5 we see how these
considerations lead naturally to a theory of identities. Due to lack of space, we often refer the reader to
[IzKR4, IzKR5] for more details.
2. Algebraic Background
We start by reviewing some notions which may be familiar, but are needed extensively in our exposition.
The basic tropicalization, or dequantization, involves taking logarithms to (R, + ), which as explained in [L1]
replaces conventional multiplication by addition, and conventional addition by the maximum. This is called
the max-plus algebra of (R, + ).
2.1. Ordered groups and monoids. Recall that a monoid (M, · , 1) is a set with an associative operation ·
and a unit element 1. We usually work with Abelian monoids, in which the operation is commutative. The
passage to the max-plus algebra in tropical mathematics can be viewed algebraically via ordered groups
(such as (R, + )), and, more generally, ordered monoids.
An Abelian monoid M := (M, · , 1) is cancellative if ab = ac implies b = c. There is a well-known
localization procedure with respect to a submonoid S of a cancellative Abelian monoid M, obtained by
taking M × S/ ∼ , where ∼ is the equivalence relation given by (a, s) ∼ (a′ , s′ ) iff as′ = a′ s. Localizing
with respect to all of M yields its group of fractions, cf. [Bo, W]. We say that a monoid M is powercancellative (called torsion-free by [W]) if an = bn for some n ∈ N implies a = b. A monoid M is called
N-divisible (also called radicalizible in the tropical literature) if for each a ∈ M and m ∈ N there is b ∈ M
such that bm = a. For example, (Q, + ) is N-divisible.
Remark
√ 2.1. The customary way of embedding an Abelian monoid M into an N-divisible monoid, is to
adjoin m a for each a ∈ M and m ∈ N, and define
√
√ √
n
mn
m
a b :=
an b m .
This will be power-cancellative if M is power-cancellative.
An ordered Abelian monoid is an Abelian monoid endowed with a total order satisfying the property:
a ≤ b implies

ga ≤ gb,

(2.1)

for all elements a, b, g. Any ordered cancellative Abelian monoid is infinite.
One advantage of working with ordered monoids and groups is that their elementary theory is well-known
to model theorists. The theory of ordered N-divisible Abelian groups is model complete, cf. [M, p. 116]
and [Sa, pp. 35, 36], which essentially means that every N-divisible ordered cancellative Abelian monoid has
the same algebraic theory as the max-plus algebra (Q, + ), which is a much simpler structure than (R, + ).
From this point of view, the algebraic essence of tropical mathematics boils down to (Q, + ). Sometimes we
want to study its ordered submonoid (Z, + ), or even (N, + ), although they are not N-divisible.
Nevertheless, just as one often wants to study the arithmetic of Q by viewing finite homomorphic images
of Z, we want the option of studying finite homomorphic images of the ordered monoid (N, + ). Towards
this end, we define the q-truncated monoid M = [1, q] := {1, 2, . . . , q}, given with the obvious ordering;
the sum and product of two elements k, ℓ ∈ L are taken as usual, if not exceeding q − 1, and is q otherwise.
In other words, q could be considered as the infinite element of the finite monoid M.

ALGEBRAIC STRUCTURES

3

2.2. Semirings without zero. So far, dequantization has enabled us to pass from algebras to ordered
Abelian monoids, which come equipped with a rich model theory ready to implement, and as noted above,
there is a growing theory of algebraic geometry over monoids [CHWW]. But to utilize standard tools such as
polynomials and matrices, we need two operations (addition and multiplication), and return to the language
of semirings, using [Gol] as a general reference. We write † to indicate that we do not require the zero
element.
A semiring† (R, +, ·, 1) is a set R equipped with binary operations + and · such that:
• (R, +) is an Abelian semigroup;
• (R, · , 1R ) is a monoid with identity element 1R ;

• Multiplication distributes over addition.
A semifield† is a semiring† in which every element is (multiplicatively) invertible. In particular, the
max-plus algebras (Z, + ), (Q, + ), and (R, + ) are semifields† , since + now is the multiplication.
A semiring is a semiring† with a zero element 0R satisfying
a + 0R = a,
†

a · 0R = 0R = 0R · a,

∀a ∈ R.

We use semirings instead of semirings since the zero element can be adjoined formally, and often is
irrelevant. For example, the zero element of the max-plus algebra would be −∞, which requires special
attention.
A semifield is a semifield† with a zero element adjoined. Note that under this definition the customary
field Q with the usual operations is not a semifield, since Q \ {0} is not closed under addition.
Any ordered Abelian monoid gives rise to a max-plus semiring† , where the operations are written ⊙ and ⊕
and defined by:
a ⊕ b := max{a, b};
a ⊙ b := a + b.
Associativity and distributivity (of ⊙ over ⊕) hold, but NOT negation, since a ⊕ b 6= −∞ unless a = b =
−∞. Although the circle notation is standard in the tropical literature, we find it difficult to read when
dealing with algebraic formulae. (Compare x4 + 7x3 + 4x + 1 with
x ⊙ x ⊙ x ⊙ x ⊕ 7 ⊙ x ⊙ x ⊙ x ⊕ 4 ⊙ x ⊕ 1.)

Thus, when appealing to the abstract theory of semirings we use the usual algebraic notation of · (often
suppressed) and + respectively for multiplication and addition.
The max-plus algebra satisfies the property that a + b ∈ {a, b}; we call this property bipotence. In
particular, the max-plus algebra, viewed as a semiring† , is idempotent in the sense that a + a = a for all a.
Although idempotence pervades the theory, it turns out that what is really crucial for many applications is
the following fact:
Remark 2.2. In any idempotent semiring† , if a + b + c = a, then a + b = a. (Proof: a = a + b + c =
(a + b + c) + b = a + b.)
Let us call such a semiring† proper. Note that a proper semiring cannot have additive inverses other
than 0, since if c + a = 0, then a = a + 0 = a + c + a, implying a = a + c = 0.
Any proper semiring† R gives rise to a partial order, given by a ≤ b iff a + c = b for some c ∈ R. This
is a total order when the semiring† R is bipotent. Thus, the categories of bipotent semirings† and ordered
monoids are isomorphic, and each language has its particular advantages.
2.3. The function semiring† .
Definition 2.3. The function semiring† Fun(S, R) is the set of functions from a set S to a semiring† R.
Fun(S, R) becomes a semiring† under componentwise operations, and is proper when R is proper. Customarily one takes S = R(n) , the Cartesian product of n copies of R. This definition enables us to work
with proper subsets, but the geometric applications lie outside the scope of the present paper.
2.3.1. Polynomials and power series. Λ = {λ1 , . . . , λn } always denotes a finite set of indeterminates commuting with the semiring† R; often n = 1 and we have a single indeterminate λ. We have the polynomial
semiring† R[Λ]. As in [IzR1], we view polynomials in R[Λ] as functions, but perhaps viewed over some
extension R′ of R. More precisely, for any subset S ⊆ R(n) , there is a natural semiring† homomorphism
ψ : R[Λ] → Fun(S, R),

(2.2)

4

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

obtained by viewing a polynomial as a function on S.
When R is a semifield† , the same analysis is applicable to Laurent polynomials R[Λ, Λ−1 ], since the
homomorphism λi 7→ ai then sends λ−1
7→ a−1
i
i . Likewise, when R is power-cancellative and divisible, we
†
can also define the semiring of rational polynomials R[Λ]rat , where the powers of the λi are taken to be
arbitrary rational numbers. These can all be viewed as elementary formulas in the appropriate languages,
so the model theory alluded to earlier is applicable to the appropriate polynomials and their (tropical) roots
in each case.
Other functions over the bipotent semiring† R of an ordered monoid M can be defined in the same way.
For example, if M is an ordered submonoid of (R+ , ·), then we can define the formal exponential series
X ak
exp(a) :=
(2.3)
k!
k

am+1
(m+1)!

since a < m implies
is defined in Fun(R, R).

<

am
m! ,

and thus (2.3) becomes a finite sum. It follows at once that exp(λ) :=

P λk
k!

2.4. Puisuex series and valuations. Since logarithms often do not work well with algebraic structure ,
tropicalists have turned to the algebra of Puiseux series, denoted K, whose elements have the form
X
p(t) =
c τ tτ ,
τ ∈Q≥0 , cτ ∈K

where the powers of t are taken over well-ordered subsets of Q. Here K is any algebraically closed field of
characteristic 0, customarily C. Intuitively, we view t as a “generic element.” In the literature, the powers τ
are often taken in R rather than Q, but it is enough to work with Q, for which it much easier to compute
the powers of t. The algebra K is an algebraically closed field.
Now recall that a valuation from an integral domain W to an ordered monoid (G, + ) is a multiplicative
monoid homomorphism v : W \ {0} → G, i.e., with
v(ab) = v(a) + v(b),
and satisfying the property v(a + b) ≥ min{v(a), v(b)} for all a, b ∈ K. We formally put v(0) = ∞. For
example, the field of Puiseux series has the order valuation v given by
v(p(t)) := min{τ ∈ Q≥0 : cτ 6= 0}.

As t → 0, the dominant term in p(t) becomes cv(p(t)) tv(p(t)) .
The following basic observation in valuation theory shows why valuations are relevant to the tropical
theory.
Remark 2.4. If v(a) 6= v(b), then v(a + b) = min{v(a), v(b)}. Inductively, if v(a1 ), . . . , v(am ) are distinct,
then
v

X
m
i=1

ai



= min{v(ai ) : 1 ≤ i ≤ m} ∈ G.

P
Consequently, if
ai = 0, then at least two of the v(ai ) are the same. These considerations are taken much
more deeply in [BiG].
When W is a field, the value monoid G is a group. Much information about a valuation v : W → G ∪ {∞}
can be garnered from the target v(W ), but valuation theory provides some extra structure:
• The valuation ring Ov = {a ∈ W : v(a) ≥ 0},
• The valuation ideal Pv = {a ∈ W : v(a) > 0},

• The residue ring W̄ = Ov /Pv , a field if W is a field.
For example, the valuation ring of the order valuation on the field K of Puiseux series is {p(t) ∈ K : cτ = 0
for τ < 0}, and the residue field is K.
We replace v by −v to switch minimum to maximum, and ∞ by −∞. One can generalize the notion of
valuation to permit W to be a semiring† ; taking W = M, we see that the identity map is a valuation, which
provides one of our main examples.

ALGEBRAIC STRUCTURES

5

2.5. The standard supertropical semiring† . This construction, following [IzR1], refines the max-plus
algebra and picks up the essence of the value monoid. From now on, in the spirit of max-plus, we write the
operation of an ordered monoid M as multiplication.
We start with an Abelian monoid M := (M, · ), an ordered group G := (G, · ), and an onto monoid
homomorphism v : M → G. We write aν for v(a), for a ∈ M. Thus every element of G is some aν . We write
a∼
=ν b if aν = bν .
Our two main examples:
• M = G is the ordered monoid of the max-plus algebra (the original example in Izhakian’s dissertation);
• M is the multiplicative group of a field F , and v : F × → G is a valuation. Note that we forget the
original addition on the field F !
Our objective is to use the order on G to study M. Accordingly we want to define a structure on M ∪ G.
The standard supertropical semiring† R is the disjoint union M ∪ G, made into a monoid by starting
with the given multiplications on M and G, and defining a · bν and aν · b to be (ab)ν for a, b ∈ M. We
extend v to the ghost map ν : R → G by taking ν|M = v and ν|G to be the identity on G. Thus, ν is a
monoid projection.
We make R into a semiring† by defining


for aν > bν ;
a
a+b= b
for aν < bν ;

 ν
a
for aν = bν .

R is never additively cancellative (except for M = {1}).
M is called the tangible submonoid of R. G is called the ghost ideal.
R is called a supertropical domain† when the monoid M is (multiplicatively) cancellative.
Strictly speaking, a supertropical domain† will not be a semifield† since the ghost elements are not
invertible. Accordingly, we define a 1-semifield† to be a supertropical domain† for which M is a group.
Motivation: The ghost ideal G is to be treated much the same way that one treats the zero element in
commutative algebra. Towards this end, we write
a |= b

if

a=b

or a = b + ghost.

gs

(Accordingly, write a |= 0 if a is a ghost.) Note that for a tangible, a |= b iff a = b. If needed, we could
gs

gs

formally adjoin a zero element in a separate component; then the ghost ideal is G := G ∪ {0}. We may
think of the ghost elements as uncertainties in classical algebra arising from adding two Puiseux series whose
lowest order terms have the same degree.
R is a cover of the max-plus algebra of G, in which we “resolve” tangible idempotence, in the sense that
a + a = aν instead of a + a = a.
This modification in the structure permits us to detect corner roots of tropical polynomials in terms of
the algebraic structure, by means of ghosts. Namely, we say that a ∈ R(n) is a root of a polynomial f ∈ R[Λ]
when f (a) ∈ G. This concise formulation enables us to apply directly many standard mathematical concepts
from algebra, algebraic geometry, category theory, and model theory, as described in [IzKR1]–[IzKR5] and
[IzR1]–[IzR6].
The standard supertropical semiring works well with linear algebra, as we shall see.
2.6. Kapranov’s Theorem and the exploded supertropical structure. Given a polynomial f (Λ) =
P
i1
in
1 , . . . , in ), i.e., with each pi a Puiseux series, we define its tropicalizai pi (λ1 · · · λn ) ∈ K[Λ], where i = (i
P
tion f˜ to be the tropical polynomial i v(pi )λi11 · · · λinn . (In the tropical literature, this is customarily written
in the circle notation.) By Remark 2.4, if a ∈ K(n) is a root of f in the classical sense, then v(a) is a tropical
root of f˜. Kapranov showed, conversely, that any tropical root of f˜ has the form v(a) for suitable a ∈ K(n) ,
and valuation theory can be applied to give a rather quick proof of this fact, although we are not aware of
an explicit reference. (See [R1, Proposition 12.58] for an analogous proof of a related valuation-theoretic
result.)
To prove Kapranov’s theorem, one needs more than just the lowest powers of the Puiseux series appearing
as coefficients of f , but also their coefficients; i.e., we also must take into account the residue field of the

6

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

order valuation on Puiseux series. Thus, we need to enrich the supertropical structure to include this extra
information. This idea was first utilized by Parker [Par] in his “exploded” tropical mathematics. Likewise,
Kapranov’s Theorem has been extended by Payne [Pay1, Pay2], for which we need the following more refined
supertropical structure, initiated by Sheiner [ShSh]:
Definition 2.5. Given a valuation v : W → G, we define the exploded supertropical algebra R = W × G,
viewed naturally as a monoid. (Thus we are mixing the “usual” world with the tropical world.)
We make R into a semiring† by defining


when a > b;
(c, a)
(c, a) + (d, b) = (d, b)
when a < b;


(c + d, a) when a = b.

Sheiner’s theory parallels the standard supertropical theory, where now the ghost elements are taken to
be the 0-layer {0} × G.
3. The layered structure

The standard supertropical theory has several drawbacks. First, it fails to detect the multiplicity of a
root of a polynomial. For example we would want 3 to have multiplicity 5 as a tropical root of the tropical
polynomial (λ + 3)5 ; this is not indicated supertropically. Furthermore, serious difficulties are encountered
when attempting to establish a useful intrinsic differential calculus on the supertropical structure. Also,
some basic supertropical verifications require ad hoc arguments.
These drawbacks are resolved by refining the ghost ideal into different “layers,” following a construction
of [WW, Example 3.4] and [AkGG, Proposition 5.1]. Rather than a single ghost layer, we take an indexing
set L which itself is a partially ordered semiring† ; often L = N under classical addition and multiplication.
Ordered semirings† can be trickier than ordered groups, since, for example, a > b in (R, · ) does not imply
−a > −b, but rather −a < −b. To circumvent this issue, we require all elements in the indexing semiring†
to be non-negative.
Construction 3.1 ( [IzKR4, Construction 3.2]). Suppose we are given a cancellative ordered monoid G,
viewed as a semiring† as above. For any partially ordered semiring† L we define the semiring† R := R(L, G)
to be set-theoretically L × G, where we denote the “layer” {ℓ} × G as Rℓ and the element (ℓ, a) as [ℓ] a ; we
define multiplication componentwise, i.e., for k, ℓ ∈ L, a, b ∈ G,
[k]

a

[ℓ]

[kℓ]

b =

(ab) ,

(3.1)

and addition via the rules:

[k]

a+

The sort map s : R → L is given by s(

[k]

[ℓ]

b =







[k]
[ℓ]

a
b

[k+ℓ]

a

if a > b,
if a < b,
if a = b.

(3.2)

a ) = k.

R is indeed a semiring† . We identify a ∈ G with [1] a ∈ R1 .
In most applications the “sorting” semiring† L is ordered, and its smallest nonzero element is 1. In this
case, the monoid { [ℓ] a : 0 < ℓ ≤ 1} is called the tangible part of R. The ghosts are { [ℓ] a : ℓ > 1}, and
correspond to the ghosts in the standard supertropical theory. The ghosts together with R0 comprise an
ideal. If there is a zero element it would be [0] 0 .
One can view the various choices of the sorting semiring† L as different stages of degeneration of algebraic
geometry, where the crudest (for L = {1}) is obtained by passing directly to the familiar max-plus algebra.
The supertropical structure is obtained when L = {1, ∞}, where R1 and R∞ are two copies of G, with R1
the tangible submonoid of R and R∞ being the ghost copy. Other useful choices of L include {1, 2, ∞} (to
distinguish between simple roots and multiple roots) and N, which enables us to work with the multiplicity
of roots and with derivatives, as seen below. In order to deal with tropical integration as anti-differentiation,
one should consider the sorting semirings† Q>0 and R>0 , but this is outside our present scope.
By convention, [ℓ] λ denotes [ℓ] 1R λ. Thus, any monomial can be written in the form [ℓ] αi λi11 · · · λinn
where i = (i1 , . . . , in ). We say a polynomial f is tangible if each of its coefficients is tangible.

ALGEBRAIC STRUCTURES

7

L
Note that the customary decomposition R = ℓ∈L Rℓ in graded algebras has been strengthened to the
Ṡ
partition R = ℓ∈L Rℓ . The ghost layers now indicate the number of monomials defining a corner root of a
tangible polynomial. Thus, we can measure multiplicity of roots by means of layers. For example,
(λ + 3)5 =
and substituting 3 for λ gives

[1] 5

λ +

[32]

15 =

[5]
5

3 λ4 +

[10]

6 λ3 +

[10]

9 λ2 +

[5]

12 λ +

[1]

15 ,

[2 ] 5

3 .

3.1. Layered derivatives. Formal derivatives are not very enlightening over the max-plus algebra. For
example, if we take the polynomial f = λ2 + 5λ + 8, which has corner roots 3 and 5, we have f ′ = 2λ + 5,
having corner root 3, but the common corner root 3 of f and f ′ could hardly be considered a multiple root
of f . This difficulty arises from the fact that 1 + 1 6= 2 in the max-plus algebra. The layering permits us to
define a more useful version of the derivative (where now R contains a zero element 0R ):
′
Definition 3.2. The layered derivative flay
of f on R[λ] is given by:
X
′
n
n
X
[jℓj ]
[ℓj ]
αj λj−1 .
:=
αj λj
lay

j=0

In particular, for α =

[1]

(αλj )′lay

α ∈ R1 ,

:=

[j]

α λj−1

(j ≥ 2),

(3.3)

j=1

(αλ)′lay := α,

and α′lay := 0R .

Thus, we have the familiar formulas:
′
′
(1) (f + g)′lay = flay
+ glay
;
′
′
g + f glay
.
(2) (f g)′lay = flay

This is far more informative in the layered setting (say for L = N) than in the standard supertropical
setting, in which (αλj )′ is ghost for all j ≥ 2.
3.2. The tropical Laplace transform. The classical technique of Laplace transforms has a tropical analog
which enables us to compare the various notions of derivative. Suppose L is infinite, say L = N . Formally
permitting infinite vectors (aℓ )ℓ∈L permits us to define a homomorphism R[[Λ]] → R(L, R) given by
X

ak λk 7→ [k] k! ak .
1

(Strictly speaking, we would want the image to be ( [ k ] k! ak ), but this would complicate the notation and
require us to take L = Q+ .) For example, explay (a) 7→ ( [k] ak ) where each ak = a.
Now we define ( [ℓ] aℓ )′ = ( [ℓ−1] aℓ ). Then exp′lay = explay . This enables one to handle trigonometric
functions in the layered theory.
3.3. Layered domains† with symmetry, and patchworking. Akian, Gaubert, and Guterman [AkGG,
Definition 4.1] introduced an involutory operation on semirings, which they call a symmetry, to unify the
supertropical theory with classical ring theory. One can put their symmetry in the context of R(L, G).
Definition 3.3. A negation map on a semiring† L is a function τ : L → L satisfying the properties:
N1. τ (kℓ) = τ (k)ℓ = kτ (ℓ);
N2. τ 2 (k) = k;
N3. τ (k + ℓ) = τ (k) + τ (ℓ).
Suppose the semiring† L has a negation map τ of order ≤ 2. We say that R := R(L, G) has a symmetry σ
when R is endowed with a map
σ:R→R

and a negation map τ on L, together with the extra axiom:
S1. s(σ(a)) = τ (s(a)),

∀a ∈ R.

8

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

Example 3.4. Suppose L is an ordered semiring† . We mimic the well-known construction of Z from N.
Define the doubled semiring†
D(L) = L1 × L−1 ,

the direct product of two copies L1 and L−1 of L, where addition is defined componentwise, but multiplication
is given by
(k, ℓ) · (k ′ , ℓ′ ) = (kk ′ + ℓℓ′ , kℓ′ + ℓk ′ ).
In other words, D(L) is multiplicatively graded by {±1}.
D(L) is endowed with the product partial order, i.e., (k ′ , ℓ′ ) ≥ (k, ℓ) when k ′ ≥ k and ℓ′ ≥ ℓ.
Here is an example relating to “patchworking,” [ItMS].

Example 3.5. Suppose G is an ordered Abelian monoid, viewed as a semiring† as in Construction 3.1.
Define the doubled layered domain†
R = R(D(L), G) = {((k, ℓ), a) : (k, ℓ) 6= (0, 0), a ∈ G},
but with addition and multiplication given by the following rules:


((k, ℓ), a)
′ ′
((k, ℓ), a) + ((k , ℓ ), b) =
((k ′ , ℓ′ ), b)


((k + k ′ , ℓ + ℓ′ ), a)
((k, ℓ), a) · ((k ′ , ℓ′ ), b) =

if a > b,
if a < b,
if a = b.

((kk ′ + ℓℓ′ , kℓ′ + k ′ ℓ), ab).

Remark 3.6. In R = R(D(L), G), the symmetry σ : R → R given by σ : ((k, ℓ), a) 7→ ((ℓ, k), a) is analogous
to the one described in [AkGG], and behaves much like negation.
For example, when L = {1, ∞}, we note that D(L) = {(1, 1), (1, ∞), (∞, 1), (∞, ∞)}, which is applicable
to Viro’s theory of patchworking, where the “tangible” part could be viewed as those elements of layer
(1, 1), (1, ∞), or (∞, 1). Explicitly, comparing with Viro’s use of hyperfields in [Vi, § 3.5], we identify these
three layers respectively with 0, 1, and −1 in his terminology, and the element (∞, ∞) with the set {0, 1, −1}.
4. Matrices and linear algebra
As an application, the supertropical and layered structures provide many of the analogs to the classical
Hamilton-Cayley-Frobenius theory. Mn (R) denotes the semiring† of n × n matrices over a semiring R. (Note
that the familiar matrix operations do not require negation.)
Although one of the more popular and most applicable aspects of idempotent mathematics, idempotent
matrix theory is handicapped by the lack of an element −1 with which to construct the determinant. Many
ingenious methods have been devised to circumvent this difficulty, as surveyed in [AkBG]; also cf. [AkGG]
and many interesting papers in this volume. Unfortunately these give rise to many different notions of rank
of matrix, and often are difficult to understand. The layered (and more specifically, supertropical) theories
give a unified and relatively straightforward notion of rank of a matrix, eigenvalue, adjoint, etc.
4.1. The supertropical determinant. This discussion summarizes [IzR3]. We define the supertropical
determinant |A| of a matrix A = (ai,j ) to be the permanent:
X
|(ai,j )| =
a1,π(1) · · · an,π(n) .
(4.1)
π∈Sn

Defining the transpose matrix (ai,j )t to be (aj,i ), we have
(ai,j )t = |(ai,j )| .
|A| =
which in
We now
semiring

0R iff “enough” entries are 0R to force each summand in Formula 4.1 to be 0R . This property,
classical matrix theory provides a description of singular subspaces, is too strong for our purposes.
take the natural supertropical version. Write T for the tangible elements of our supertropical
R, and T = T ∪ {0}.

Definition 4.1. A matrix A is nonsingular if |A| ∈ T ; A is singular when |A| ∈ G .

ALGEBRAIC STRUCTURES

9

The standard supertropical structure often is sufficient for matrices, since it enables us to distinguish
between nonsingular matrices (in which the tropical n × n determinant is computed as the unique maximal
product of n elements in one track) and singular matrices.


0 0
The tropical determinant is not multiplicative, as seen by taking the nonsingular matrix A =
.
1 2


1 2
Then A2 =
is singular and A2 = 5ν 6= 2 · 2. But we do have:
3 4
Theorem 4.2. For any n × n matrices over a supertropical semiring R, we have
|AB| |= |A| |B| .
gs

In particular, |AB| = |A| |B| whenever |AB| is tangible.

We say a permutation σ ∈ Sn attains |A| if |A| ∼
=ν aσ(1),1 · · · aσ(n),n .
• By definition, some permutation always attains |A|.

• If there is a unique permutation σ which attains |A|, then |A| = a1,σ(1) · · · an,σ(n) .

• If at least two permutations attain |A|, then A must be singular. Note in this case that if we replaced
all nonzero entries of A by tangible entries of the same ν-value, then A would still be singular.
4.2. Quasi-identities and the adjoint.
Definition 4.3. A quasi-identity matrix IG is a nonsingular, multiplicatively idempotent matrix equal to
I + ZG , where ZG is 0R on the diagonal, and whose off-diagonal entries are ghosts or 0R .
|IG | = 1R by the nonsingularity of IG . Also, for any matrix A and any quasi-identity, IG , we have
AIG = A + AG , where AG = AZG ∈ Mn (G ).
There is another notion to help us out.
Definition 4.4. The (i, j)-minor A′i,j of a matrix A = (ai,j ) is obtained by deleting the i row and j column
of A. The adjoint matrix adj(A) of A is defined as the transpose of the matrix (a′i,j ), where a′i,j = A′i,j .
Remark 4.5.
(i) Suppose A = (ai,j ). An easy calculation using Formula (4.1) yields
|A| =

n
X

ai,j a′i,j ,

j=1

∀i.

(4.2)

Consequently, ai,j a′ i,j ≤ν |A| for each i, j.
(ii) If we take k 6= i, then replacing the i row by the k row in A yields a matrix with two identical rows;
thus, its determinant is a ghost, and we thereby obtain
n
X
ai,j a′k,j ∈ G ,
∀k 6= i;
(4.3)
j=1

Likewise

n
X
j=1

aj,i a′j,k ∈ G ,

∀k 6= i.

One easily checks that adj(B) adj(A) = adj(AB) for any 2 × 2 matrices A and B. However, this fails
for larger n, cf. [IzR3, Example 4.7]. We do have the following fact, which illustrates the subtleties of the
supertropical structure, cf. [IzR3, Proposition 5.6]:
Proposition 4.6. adj(AB) = adj(B) adj(A) + ghost.
Definition 4.7. For |A| invertible, define
IA = A

adj(A)
,
|A|

′
IA
=

adj(A)
A.
|A|

10

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

′
The matrices IA and IA
are quasi-identities, as seen in [IzR3, Theorem 4.13]. The main technique of proof
is to define a string (from the matrix A) to be a product ai1 ,j1 · · · aik ,jk of entries from A and, given such a
string, to define its digraph to be the graph whose edges are (i1 , j1 ), . . . , (ik , jk ), counting multiplicities. A
k-multicycle in a digraph is the union of disjoint simple cycles, the sum of whose lengths is k; thus every
vertex in an n-multicycle appears exactly once. A careful examination of the digraph in conjunction with
Hall’s Marriage Theorem yields the following major results from [IzR3, Theorem 4.9 and Theorem 4.12]:

Theorem 4.8.
n
(i) |A adj(A)| = |A| .

(ii) | adj(A)| = |A|n−1 .

In case A is a nonsingular, we define
adj(A)
.
|A|
′
′
Thus AA∇ = IA , and A∇ A = IA
. Note that IA
and IA may differ off the diagonal, although
A∇ =

′
IA A = AA∇ A = AIA
.

This result is refined in [IzR4, Theorem 2.18]. One might hope that A adj(A)A = |A| A, but this is false
in general! The difficulty is that one might not be able to extract an n-multicycle from
ai,j a′k,j ak,ℓ .

(4.4)

a1,1 a′2,1 a2,2

For example, when n = 3, the term a1,1 (a1,3 a3,2 )a2,2 =
have the following positive result from [IzR4, Theorem 4.18]:

does not contain an n-multicycle. We do

Theorem 4.9. adj(A) adj( adj(A)) adj(A) ∼
=ν |A|n−1 adj(A) for any n × n matrix A.
4.3. The supertropical Hamilton-Cayley theorem.
Definition 4.10. Define the characteristic polynomial fA of the matrix A to be
fA = |λI + A| ,

Pn
n
bi λn−i , where α̂i
and the tangible characteristic polynomial to
be a tangible polynomial fc
A = λ +
i=1 α
P
n
n−i
n
∼
are tangible and α
bi =ν αi , such that fA = λ + i=1 αi λ .

Under this notation, we see that αk ∈ R arises from the dominant k-multicycles in the digraph of A. We
say that a matrix A satisfies a polynomial f ∈ R[λ] if f (A) ∈ Mn (G ).

Theorem 4.11. (Supertropical Hamilton-Cayley, [IzR3, Theorem 5.2]) Any matrix A satisfies both its
characteristic polynomial fA and its tangible characteristic polynomial fc
A.

4.4. Tropical dependence. Now we apply supertropical matrix theory to vectors. As in classical mathematics, one defines a module (often called semi-module in the literature) analogously to module in
classical algebra, noting again that negation does not appear in the definition. It is convenient to stipulate
that the module V has a zero element 0V , and then we need the axiom:
a0V = 0V for all a ∈ R.

Also, if 0 ∈ R then we require that 0v = 0V for all v ∈ V .
In what follows, F always denotes a 1-semifield. In this case, a module over F is called a (supertropical)
vector space. The natural example is F (n) , with componentwise operations. As in the classical theory, there
is the usual familiar correspondence between the semiring Mn (F ) and the linear transformations of F (n) .
For v = (v1 , . . . , vn ), w = (w1 , . . . , wn ) ∈ F (n) , we write v |= w when vi |= wi for all 1 ≤ i ≤ n.
gs

gs

Here is an application of the adjoint matrix, used to solve equations.
Remark 4.12. Suppose A is nonsingular, and v ∈ F (n) . Then the equation Aw = v + ghost has the solution
w = A∇ v. Indeed, writing IA = I + ZG for a ghost matrix ZG , we have
Aw = AA∇ v = IA v = (I + ZG )v |= v.
gs

This leads to the supertropical analog of Cramer’s rule [IzR4, Theorem 3.5]:

ALGEBRAIC STRUCTURES

11

Theorem 4.13. If A is a nonsingular matrix and v is a tangible vector, then the equation Ax |= v has a
gs

solution over F which is the tangible vector having value A∇ v.
Our next task is to characterize singularity of a matrix A in terms of “tropical dependence” of its rows.
In some ways the standard supertropical theory works well with matrices, since we are interested mainly in
whether or not this matrix is nonsingular, i.e., if its determinant is tangible; at the outset, at least, we are
not concerned with the precise ghost layer of the determinant.
P
(n)
Definition 4.14. A subset W ⊂ F (n) is tropically dependent if there is a finite sum
αi wi ∈ G , with
(n)
each αi ∈ T , but not all of them 0R ; otherwise W ⊂ F
is called tropically independent. A vector
v ∈ F (n) is tropically dependent on W if W ∪ {v} is tropically dependent.
By [IzKR2, Proposition 4.5], we have:
Proposition 4.15. Any n + 1 vectors in F (n) are tropically dependent.
Theorem 4.16. ([IzR3, Theorem 6.5]) Vectors v1 , . . . , vn ∈ F (n) are tropically dependent, iff the matrix
whose rows are v1 , . . . , vn is singular.
Corollary 4.17. The matrix A ∈ Mn (F ) over a supertropical domain F is nonsingular iff the rows of A
are tropically independent, iff the columns of A are tropically independent.
Proof. Apply the theorem to |A| and |At |, which are the same.



There are two competing supertropical notions of base of a vector space, that of a maximal independent
set of vectors, and that of a minimal spanning set, but this is unavoidable since, unlike the classical theory,
these two definitions need not coincide.
4.5. Tropical bases and rank. The customary definition of tropical base, which we call s-base (for
spanning base), is a minimal spanning set (when it exists). However, this definition is rather restrictive,
and a competing notion provides a richer theory.
Definition 4.18. A d-base (for dependence base) of a vector space V is a maximal set of tropically
independent elements of V . A d,s-base is a d-base which is also an s-base. The rank of a set B ⊆ V ,
denoted rank(B), is the maximal number of d-independent vectors of B.
Our d-base corresponds to the “basis” in [MS, Definition 5.2.4]. In view of Proposition 4.15, all d-bases
of F (n) have precisely n elements.
This leads us to the following definition.
Definition 4.19. The rank of a vector space V is defined as:

rank(V ) := max rank(B) : B is a d-base of V .

We have just seen that rank(F (n) ) = n. Thus, if V ⊂ F (n) , then rank(V ) ≤ n.
We might have liked rank(V ) to be independent of the choice of d-base of V , for any vector space V . This is
proved in the classical theory of vector spaces by showing that dependence is transitive. However, transitivity
of dependence fails in the supertropical theory, and, in fact, different d-bases may contain different numbers
of elements, even when tangible. An example is given in [MS, Example 5.4.20], and reproduced in [IzKR2,
Example 4.9] as being a subspace of F (4) having d-bases both of ranks 2 and 3.


4 4 0
Example 4.20. The matrix A = 4 4 1 has rank 2, but is “ghost annihilated” by the tropically
4 4 2
independent vectors v1 = (1, 1, 0)t and v2 = (1, 1, 1)t ; i.e., Av1 = Av2 = (5ν , 5ν , 5ν )t , although 2 + 2 > 3.
We do have some consolations.
Proposition 4.21 ([IzKR2, Proposition 4.11]). For any tropical subspace V of F (n) and any tangible v ∈ V,
there is a tangible d-base of V containing v whose rank is that of V .
Proposition 4.22 ([IzKR2, Proposition 4.13]). Any n × n matrix of rank m has ghost annihilator of rank
≥ n − m.

12

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

4.5.1. Semi-additivity of rank.
Definition 4.23. A function rankS : S → N is monotone if for all S2 ⊆ S1 ⊆ S we have
rankS (S2 ∪ {s}) − rankS(S2 ) ≥ rankS (S1 ∪ {s}) − rankS (S1 )

for all s ∈ S.

(4.5)

Note that (4.5) says that rankS (S1 ) − rankS(S2 ) ≥ rankS (S1 ∪ {s}) − rankS(S2 ∪ {s}). Also, taking S2 = ∅
yields rankS (S1 ∪ {s}) − rankS (S1 ) ≤ 1.
Lemma 4.24. If rankS : S → N is monotone, then

rankS (S1 ) + rankS (S2 ) ≥ rankS (S1 ∪ S2 ) + rankS (S1 ∩ S2 )

for all S1 , S2 ⊂ S.

(4.6)

Proof. Induction on m = rankS (S2 \ S1 ). If m = 0, i.e., S2 ⊆ S1 , then the left side of (4.6) equals the right
side. Thus we may assume that m ≥ 1. Pick s in a d-base of S2 \ S1 . Let S2′ = S2 \ {s}. Noting that
rankS (S2′ \ S1 ) = m − 1, we see by induction that
or (taking S1 ∪

S2′

rankS (S1 ) + rankS(S2′ ) ≥ rankS (S1 ∪ S2′ ) + rankS (S1 ∩ S2′ ),

(4.7)

instead of S2 in (4.5)),

rankS(S1 ) − rankS(S1 ∩ S2 ) = rankS (S1 ) − rankS (S1 ∩ S2′ ) ≥ rankS (S1 ∪ S2′ ) − rankS (S2′ )

yielding (4.6).

≥ rankS(S1 ∪ S2 ) − rankS (S2 ),



Proposition 4.25. rank(S1 ) + rank(S2 ) ≥ rank(S1 ∪ S2 ) + rank(S1 ∩ S2 ) for all S1 , S2 ⊂ S.
Proof. rank is a monotone function, since each side of (4.5) is 0 or 1, depending on whether or not s is
independent of Si , and only decreases as we enlarge the set.

4.6. Supertropical eigenvectors. The standard definition of an eigenvector of a matrix A is a vector v,
with eigenvalue β, satisfying Av = βv. It is well known [BrR] that any (tangible) matrix has an eigenvector.
Example 4.26. The characteristic polynomial fA of

4
A=
0

0
1



is (λ + 4)(λ + 1) + 0 = (λ + 4)(λ + 1), and the vector (4, 0) is a eigenvector of A, with eigenvalue 4. However,
there is no eigenvector having eigenvalue 1.
In general, the lesser roots of the characteristic polynomial are “lost” as eigenvalues. We rectify this
deficiency by weakening the standard definition.
Definition 4.27. A tangible vector v is a generalized supertropical eigenvector of a (not necessarily
tangible) matrix A, with generalized supertropical eigenvalue β ∈ T , if Am v |= β m v for some m; the
gs

minimal such m is called the multiplicity of the eigenvalue (and also of the eigenvector). A supertropical
eigenvector is a generalized supertropical eigenvector of multiplicity 1.


4 0
Example 4.28. The matrix A =
of Example 4.26 also has the tangible supertropical eigenvector
0 1
v = (0, 4), corresponding to the supertropical eigenvalue 1, since
Av = (4ν , 5) = 1v + (4ν , −∞).
Proposition 4.29. If v is a tangible supertropical eigenvector of A with supertropical eigenvalue β, the
matrix A + βI is singular (and thus β must be a (tropical) root of the characteristic polynomial fA of A).
Conversely, we have:
Theorem 4.30 ([IzR3, Theorem 7.10]). Assume that ν|T : T → G is 1:1. For any matrix A, the dominant
tangible root of the characteristic polynomial of A is an eigenvalue of A, and has a tangible eigenvector. The
other tangible roots are precisely the supertropical eigenvalues of A.

ALGEBRAIC STRUCTURES

13



0 0
. Its characteristic polynomial is λ2 + 2λ + 2 = (λ + 0)(λ + 2),
1 2
whose roots are 2 and 0. The eigenvalue 2 has tangible eigenvector v = (0, 2) since Av = (2, 4) = 2v, but
there are no other tangible eigenvalues. A does have the tangible supertropical eigenvalue 0, with
 νtangible

0 0
ν
ν
supertropical eigenvector w = (2, 1), since Aw = (2, 3 ) = 0w + (−∞, 3 ). Note that A + 0I =
is
1 2
ν
singular, because |A +
0I| = 
2 .
1
2
Furthermore, A2 =
is a root of λ2 + 4A, and thus A is a root of g = λ4 + 4λ2 = (λ(λ + 2))2 , but 0
3 4
is not a root of g although it is a root of fA . This shows that the naive formulation of Frobenius’ theorem
fails in the supertropical theory, and is explained in the work of Adi Niv [N].
Let us return to our example A =

4.7. Bilinear forms and orthogonality. One can refine the study of bases by introducing angles, i.e.,
orthogonality, in terms of bilinear forms. Let us quote some results from [IzKR2].
Definition 4.31. A (supertropical) bilinear form B on a (supertropical) vector space V is a function
B : V × V → F satisfying
B(v1 + v2 , w1 + w2 ) |= B(v1 , w1 ) + B(v1 , w2 ) + B(v2 , w1 ) + B(v2 , w2 ),
gs

B(αv1 , w1 ) = αB(v1 , w1 ) = B(v1 , αw1 ),
for all α ∈ F and vi ∈ V, and wj ∈ V ′ .
We work with a fixed bilinear form B = h , i on a (supertropical) vector space V ⊆ F (n) . The Gram
matrix of vectors v1 , . . . , vk ∈ F (n) is defined as the k × k matrix


hv1 , v1 i hv1 , v2 i · · · hv1 , vk i
 hv , v i hv , v i · · · hv , v i 
2 2
2 k 
 2 1
e
.
G(v1 , . . . , vk ) = 
(4.8)
..
..
..


..
.


.
.
.
hvk , v1 i hvk , v2 i · · · hvk , vk i
The set {v1 , . . . , vk } is nonsingular (with respect to B) when its Gram matrix is nonsingular.
e = G(b
e 1 , . . . , bk ),
In particular, given a vector space V with s-base {b1 , . . . , bk }, we have the matrix G
e does not depend on the choice of
which can be written as (gi,j ) where gi,j = hbi , bj i. The singularity of G
s-base.
Definition 4.32. For vectors v, w in V , we write v⊥⊥w when hv, wi ∈ G , that is hv, wi |= 0F , and say
gs

that v is left ghost orthogonal to w. We write W ⊥⊥ for {v ∈ V : v⊥⊥w for all w ∈ W.}
Definition 4.33. A subspace W of V is called nondegenerate (with respect to B), if W ⊥⊥ ∩ W is ghost.
The bilinear form B is nondegenerate if the space V is nondegenerate.
Pm
Lemma 4.34. Suppose {w1 , . . . , wm } tropically spans a subspace W of V , and v ∈ V. If i=1 βi hv, wi i ∈ G
for all βi ∈ T , then v ∈ W ⊥⊥ .
Theorem 4.35. ([IzKR2, Theorem 6.7]) Assume that vectors w1 , . . . , wk ∈ V span a nondegenerate sube 1 , . . . , wk )| ∈ G , then w1 , . . . , wk are tropically dependent.
space W of V . If |G(w

Corollary 4.36. If the bilinear form B is nondegenerate on a vector space V , then the Gram matrix (with
respect to any given supertropical d,s-base of V ) is nonsingular.
Definition 4.37. The bilinear form B is supertropically alternate if hv, vi ∈ G for all v ∈ V. B is
supertropically symmetric if hv, wi + hw, vi ∈ G for all v, w ∈ V .

We aim for the supertropical version ([IzKR2, Theorem 6.19]) of a classical theorem of Artin, that any
bilinear form in which ghost-orthogonality is symmetric must be a supertropically symmetric bilinear form.
Definition 4.38. The (supertropical) bilinear form B is orthogonal-symmetric if it satisfies the following
property for any finite sum, with vi , w ∈ V :

14

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

X
i

hvi , wi ∈ G

iff

X
i

hw, vi i ∈ G ,

(4.9)

B is supertropically orthogonal-symmetric if B is orthogonal-symmetric and satisfies the additional
property that hv, wi ∼
=ν hw, vi for all v, w ∈ V satisfying hv, wi ∈ T .
The symmetry condition extends to sums, and after some easy lemmas we obtain ([IzKR2, Theorem 6.19]):
Theorem 4.39. Every orthogonal-symmetric bilinear form B on a vector space V is supertropically symmetric.
5. Identities of semirings, especially matrices
The word “identity” has several interpretations, according to its context. First of all, there are wellknown matrix identities such as the Hamilton-Cayley identity which says that any matrix is a root of its
characteristic polynomial.
Since the classical theory of polynomial identities is tied in with invariant theory, we also introduce layered
polynomial identities (PIs), to enrich our knowledge of layered matrices.
5.1. Polynomial identities of semirings† . We draw on basic concepts of polynomial identities, i.e., PI’s,
say from [R2, Chapter 23]. Since semirings† do not involve negatives, we modify the definition a bit.
Definition 5.1. The free N-semiring† N{x1 , x2 , . . . } is the monoid semiring† of the free (word) monoid
{x1 , x2 , . . . } over the commutative semiring† N.
Definition 5.2. A (semiring† ) polynomial identity (PI) of a semiring† R is a pair (f, g) of (noncommutative) polynomials f (x1 , . . . , xm ), g(x1 , . . . , xm ) ∈ N{x1 , . . . , xm } for which
f (r1 , . . . , rm ) = g(r1 , . . . , rm ),

∀r1 , . . . , rm ∈ R.

We write (f, g) ∈ id(R) when (f, g) is a PI of R.
Remark 5.3. A semigroup identity of a semigroup S is a pair (f, g) of (noncommutative) monomials
f (x1 , . . . , xm ), g(x1 , . . . , xm ) ∈ N{x1 , . . . , xm } for which f (s1 , . . . , sm ) = g(s1 , . . . , sm ), ∀s1 , . . . , sm ∈ S. If S
is contained in the multiplicative semigroup of a semiring† R, the semigroup identities of S are precisely the
semiring† PIs (f, g) where f and g are monomials.
Akian, Gaubert and Guterman [AkGG, Theorem 4.21] proved their strong transfer principle, which
immediately implies the following easy but important observation:
Theorem 5.4. If f, g ∈ N{x1 , . . . , xn } have disjoint supports and f − g is a PI of Mn (Z), then f = g is
also a semiring† PI of Mn (R) for any commutative semiring† R.
Proof. Since Z is an infinite integral domain, f − g is also a PI of Mn (C), where C = Z[ξ1 , ξ2 , . . . ]
denotes the free commutative ring in countably many indeterminates, implying (f, g) is a semiring† PI
of Mn (N[ξ1 , ξ2 , . . . ]). But the semiring† Mn (R) is a homomorphic image of Mn (N[ξ1 , ξ2 , . . . ]), implying
(f, g) ∈ id(Mn (R)).

Corollary 5.5. Any PI of Mn (Z) yields a corresponding semiring† PI of Mn (R) for all commutative
semirings† R.
Proof. Take f to be the sum of the terms having positive coefficient, and g to be the sum of the terms having
negative coefficient, and apply the theorem.

Many (but not all) matrix PIs can be viewed in terms of Theorem 5.4, although semiring versions of basic
results such as the Amitsur-Levitzki Theorem and Newton’s Formulas often are more transparent here.
We say that polynomials f (x1 , . . . , xm ) and g(x1 , . . . , xm ) are a t-alternating pair if f and g are interchanged whenever we interchange a pair xi and xj for some 1 ≤ i < j ≤ t. For example, x1 x2 and x2 x1 are a
2-alternating pair. Sometimes we write the non-alternating variables as y1 , y2 , . . . ; we write y as shorthand
for all the yj .

ALGEBRAIC STRUCTURES

15

Definition 5.6. We partition the symmetric group St of permutations in t letters into the even permutations St+ and the odd permutations St− . Given a t-linear polynomial h(x1 , . . . , xt ; y), we define the talternating pair
X
h+
h(xσ(1) , . . . , xσ(t) ; y)
alt (x1 , . . . , xt ; y) :=
σ∈St+

and
h−
alt (x1 , . . . , xt ; y) :=

X

h(xσ(1) , . . . , xσ(t) ; y).

σ∈St−
−
The standard pair is Stnt := (h+
alt , halt ), where h = x1 · · · xt . Explicitly,
 X

X
Stnt :=
xσ(1) · · · xσ(t) ,
xσ(1) · · · xσ(t) .
σ∈St+

σ∈St−

−
The Capelli pair is Capt := (h+
alt , halt ), where h = x1 y1 x2 y2 · · · xt yt . Explicitly,
 X

X
Capt :=
xσ(1) y1 xσ(2) y2 · · · yt−1 xσ(t) yt ,
xσ(1) y1 xσ(2) y2 · · · yt−1 xσ(t) yt .
σ∈St+

σ∈St−

Proposition 5.7. Any t-alternating pair (f, g) is a PI for every semiring† R spanned by fewer than t
elements over its center.
Proof. Suppose R is spanned by {b1 , b2 , . . . , bt−1 }. We need to verify
X

X

X
X
f
αi,t bit , . . . = g
αi,1 bi1 , . . . ,
αi,t bit , . . . .
αi,1 bi1 , . . . ,
Since f and g are linear in these entries, it suffices to verify
f (bi1 , . . . , bit , . . . ) = g(bi1 , . . . , bit , . . . )

(5.1)

for all i1 , . . . , it . But by hypothesis, two of these must be equal, say ik and ik′ , so switching these two
yields (5.1) by the alternating hypothesis.

Let ei,j denote the matrix units. The semiring† version of the Amitsur-Levitzki theorem [AmL], that
Stn2n ∈ id(Mn (N)), is an immediate consequence of Theorem 5.4, and its minimality follows from:
Lemma 5.8. Any pair of multilinear polynomials f (x1 , . . . , xm ) and g(x1 , . . . , xm ) having no common monomials do not comprise a PI of Mn (R) unless m ≥ 2n.
Proof. Rewriting
  indices we may assume that x1 · · · xm appears as a monomial of f, but not of g, and we
note (for ℓ = m
2 + 1) that
but

f (e1,1 , e1,2 , e2,2 , e2,3 , . . . , ek−1,k , ek,k , . . . ) = e1,ℓ 6= 0,
g(e1,1 , e1,2 , e2,2 , e2,3 , . . . , ek−1,k , ek,k , . . . ) = 0.


Likewise, the identical proof of [R2, Remark 23.14] shows that the Capelli pair Capn2 is not a PI of Mn (C),
and in fact (e1,1 , 0) ∈ Capn2 (Mn (R)) for any semiring† R.
5.2. Surpassing identities. The surpassing identity f |= g holds when f (a1 , . . . , am ) |= g(a1 , . . . , am )
gs

for all a1 , . . . , am ∈ R.

gs



a b
Example 5.9. Take the general 2 × 2 matrix A =
. Then tr(A) = a + d and |A| = ad + bc.
c d
 2

a + bc b(a + d)
A2 =
, so
c(a + d) bc + d2


a(a + d) + bc
b(a + d)
A2 + adI =
= tr(A)A + bcI,
c(a + d)
bc + d(a + d)
implying
A2 + |A| I = tr(A)A + bcν I,

16

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

yielding the surpassing identity A2 + |A| I |= tr(A)A for 2 × 2 matrices.
gs

We might hope for a surpassing identity involving alternating terms in the Hamilton-Cayley polynomial,
but a cursory examination of matrix cycles dashes our hopes.






− d a
cd ab −
abc cd2 acd
Example 5.10. Let A =  c − − . Then A2 =  − cd ac and A3 = c2 d abc −  , implying
− b −
bc − −
− bcd abc
A3 = αA + |A|
in this case, where α denotes the other coefficient in

−
A3 + αA + 2 −
−

−
abc
−



a −
fA . But for A = − b
− −

−
−  = tr(A)A2 + |A| ,
abc


−
− we have
c

so neither A3 + αA nor tr(A)A2 + |A| necessarily surpasses the other.
5.3. Layered surpassing identities. Since we want to deal with general layers, we write 2a (instead of aν )
for a + a, but note that s(2a) = 2s(a). When working with the layered structure, we can extend the notion
of PI from Definition 5.2 by making use of the following relations that arise naturally in the theory.
Definition 5.11. The L-surpassing relation |= is given by
L

a |= b

iff either

L



a = b + c
a = b,

 ∼
a =ν b

with

c

s(b)-ghost,

with

a

s(b)-ghost.

(5.2)

It follows that if a |= b, then a + b is s(b)-ghost. When a 6= b, this means a ≥ν b and a is s(b)-ghost.
L

Definition 5.12. The surpassing (L, ν)-relation |≡ν is given by
L

a |≡ν b

a |= b

iff

L

and

L

a∼
=ν b.

(5.3)

The surpassing L-identity f |= g holds for f, g ∈ Fun(R(n) , R) if f (a1 , . . . , an ) |= g(a1 , . . . , an ) for
L

L

all a1 , . . . , an ∈ R.
The surpassing (L, ν)-identity f |≡ν g holds for f, g ∈ Fun(R(n) , R) if f (a1 , . . . , an ) |≡ν g(a1 , . . . , an )
for all a1 , . . . , an ∈ R.

L

L

5.3.1. Layered surpassing identities of commutative layered semirings. Just as the Boolean algebra satisfies
the PI x2 = x, we have some surpassing identities for commutative layered domains† .
m
Proposition 5.13. (Frobenius identity) (x1 + x2 )m |≡ν xm
1 + x2 .
L

Proof. This is just a restatement of [IzKR5, Remark 5.2].



Proposition 5.14. (x1 + x2 + x3 )(x1 x3 + x2 x3 + x1 x2 ) |≡ν (x1 + x2 )(x1 + x3 )(x2 + x3 ). More generally, let
L
P Q
P
P
g1 = i xi , g2 = i<j xi xj , . . . , and gm−1 = i j6=i xj . Then
g1 · · · gm−1 |≡ν
L

Y
(xi + xj ).

(5.4)

i<j

Proof. This is just a restatement of [IzR1, Theorem 8.51].



ALGEBRAIC STRUCTURES

17

5.4. Layered surpassing identities of matrices.
We applied the strong transfer principle of Akian, Gaubert, and Guterman [AkGG, Theorem 4.21] to the
(standard) supertropical matrix semiring in [IzR4]. We would like to make a similar argument in the layered
case, but must avoid the following kind of counterexamples, pointed out by Adi Niv:
 [1]

 [1]

[2]
10
4
20 [2] 14
2
Example 5.15. Suppose A =
. Then A =
, so |A| = [10] 10 whereas
[2]
[10]
[2]
[4]
4
0
14
8
|A2 | = [8] 28 , which does not N-surpass |A|2 (and does not even N-surpass |A|).
The difficulty in the example was that some ν-small entry of A has a high layer which provides |A| a high
layer but does not affect the powers of A. There is a version of surpassing which is useful in this context.
Definition 5.16. An element c ∈ R is a strong ℓ-ghost (for ℓ ∈ L+ ) if s(c) ≥ 2ℓ.
The strong ℓ-surpassing relation a |= b holds in an L-layered domain† R, if either
Sℓ



a = b + c
or


a = b.

with

c

a strong ℓ-ghost
(5.5)

We often take ℓ = s(b). In this case b + b |= b (as well as b + b =
| b).
Sℓ

ℓ

The strong ℓ-surpassing relation (ai,j ) |= (bi,j ) holds for matrices (ai,j ) and (bi,j ), if ai,j |= bi,j for
Sℓ

each i, j.

Sℓ

We say that a matrix A is ℓ- layered if each entry has layer ≥ ℓ. We are ready for our other two versions
of layered identities.
Definition 5.17. The strong (ℓ, d)-surpassing identity f

|= g holds for f, g ∈ Fun(Mn (R)(m) , Mn (R))

Sℓ;d

if f (A1 , . . . , Am ) |= g(A1 , . . . , Am ) with ℓ̃ = ℓd , for all ℓ-layered matrices A1 , . . . , Am ∈ Mn (R).
S ℓ̃

In the standard supertropical theory we take ℓ = ℓ̃ = 1, but in the general layered theory we may need
to consider other ℓ. Formally set P (x1 , . . . , xℓ ) = P + − P − and Q(x1 , . . . , xℓ ) = Q+ − Q− . We say Q is
admissible if the monomials of Q+ and Q− are distinct, for each pair (i, j).
We then obtain the following metatheorem, along the lines of [AkGG] (just as in [IzR4, Theorem 2.4]):
Theorem 5.18. Suppose P = Q is a homogeneous matrix identity of Mn (Z) of degree d, with Q admissible.
Then the matrix semiring† Mn (R) satisfies the strong (ℓ, d)-surpassing identity
P + + P − |= Q+ + Q− .
Sℓ;d

Here are some applications.
Corollary 5.19. |AB| |= |A| |B| for L-layered n × n matrices A and B, where d = 2n.
Sℓ;d

Given an L-layered matrix A and the polynomial
fA := |λI + A| = αn λn + · · · + α1 λ + α0 ,

we define the polynomial ff
A to be
where s(b
αi ) = ℓn−i and α
bi ∼
=ν αi .

fc
bn λn−1 + · · · + α
b2 λ + α
b1 ,
A = α

Theorem 5.20. ff
A (A) |= adj(A), where d = n − 1, for any ℓ-layered matrix A.
Sℓ;d

Proof. This is an identity for Mn (Z), using the usual determinant.

Proposition 5.21. adj( adj(A)) |= |A|
Sℓ;d

Questions for further thought:

n−2

A, where d = n − 1, for any ℓ-layered matrix A.



18

Z. IZHAKIAN, M. KNEBUSCH, AND L. ROWEN

Q1. What are all the semiring† PIs of Mn (R)?
Specifically, we have the Specht-like question:
Q2. Are all semiring† PIs of Mn (R) a consequence of a given finite set?
Example 5.22. It is shown in [IzM] that the semiring of 2 × 2 matrices over the max-plus algebra satisfies
the semigroup identity
AB 2 A AB AB 2 A = AB 2 A BA AB 2 A.
(5.6)
The way of proving this identity is essentially based on showing that pairs of polynomials corresponding to
compatible entries in the right and the left product above define the same function. This identification is
performed by using the machinery of Newton polytopes, and thus is valid also for supertropical polynomials.
From the results of [IzM], we also conclude that this identity is minimal.
References
[AkBG]

M. Akian, R. Bapat, and S. Gaubert. Max-plus algebra, In: Hogben, L., Brualdi, R., Greenbaum, A., Mathias, R.
(eds.) Handbook of Linear Algebra. Chapman and Hall, London, 2006.
[AkGG] M. Akian, S. Gaubert, and A. Guterman. Linear independence over tropical semirings and beyond. In Tropical and
Idempotent Mathematics, G.L. Litvinov and S.N. Sergeev, (eds.), Contemp. Math. 495:1–38, 2009.
[AmL]
S.A¿ Amitsur and J. Levitzki. Minimal identities for algebras. Proc. American Mathematical Society 1, 449–463 1950.
[BiG]
R. Bieri and R. Groves, The geometry of the set of characters induced by valuations. J. für die Reine und angevandte
Mathematik, 374:168–195, 1984.
[Bo]
N. Bourbaki, Alg. Comm. VI, §3, No.1.
[BrR]
R. A. Brualdi and H. J. Ryser. Combinatorial matrix theory. Cambridge University Press, 1991.
[CHWW] G. Cortinas, C. Haesemeyer, M. Walker, and C. Weibel, Toric varieties, monoid schemes, and descent. Preprint, 2010.
[DeS]
M. Devlin and B. Sturmfels, Tropical convexity. Documenta Mathematica 9 (2004), 1–27, Erratum 205–6.
[Gat]
A. Gathmann, Tropical algebraic geometry. Jahresbericht der DMV 108:3–32, 2006.
[Gol]
J. Golan, The theory of semirings with applications in mathematics and theoretical computer science, Vol. 54,
Longman Sci & Tech., 1992.
[ItMS]
I. Itenberg, G. Mikhalkin and E. Shustin, Tropical Algebraic Geometry, Oberwolfach Seminars, 35, Birkhäuser Verlag,
Basel, 2007.
[Iz]
Z. Izhakian. Tropical arithmetic and matrix algebra. Commun. in Algebra 37(4),1445–1468, 2009.
[IzKR1] Z. Izhakian, M. Knebusch, and L. Rowen. A Glimpse at Supertropical Valuation theory An. St. Univ. Ovidius
Constanta 19, no. 2, 131–142, 2011.
[IzKR2] Z. Izhakian, M. Knebusch, and L. Rowen, Supertropical linear algebra, Pacific J. of Math., to appear. (Preprint at
arXiv:1008.0025.)
[IzKR3] Z. Izhakian, M. Knebusch, and L. Rowen, Dual spaces and bilinear forms in supertropical linear algebra, Linear and
Mult. Algebra, to appear. (Preprint at arXiv:1201.6481.)
[IzKR4] Z. Izhakian, M. Knebusch, and L. Rowen. Layered tropical mathematics, preprint at arXiv:0912.1398. (Submitted
May 2012)
[IzKR5] Z. Izhakian, M. Knebusch, and L. Rowen. Categorical layered mathematics. Contemporary Mathematics, proceedings
of the CIEM Workshop on Tropical Geometry, to appear. (Preprint at arXiv:1207.3487.)
[IzM]
Z. Izhakian and S. W. Margolis. Semigroup identities in the monoid of 2-by-2 tropical matrices. Semigroup Furom
80(2), 191–218, 2010.
[IzR1]
Z. Izhakian and L. Rowen, Supertropical algebra. Adv. in Math 225(4), 2222–2286, 2010.
[IzR2]
Z. Izhakian and L. Rowen, The tropical rank of a tropical matrix. Commun. in Algebra, 37(11), 3912–3927, 2009.
[IzR3]
Z. Izhakian and L. Rowen, Supertropical matrix algebra, Israel J. Math., 182(1), 383–424, 2011.
[IzR4]
Z. Izhakian and L. Rowen, Supertropical matrix algebra II: Solving tropical equations. Israel J. Math. 186(1), 69–97,
2011.
[IzR5]
Z. Izhakian and L. Rowen, Supertropical matrix algebra III: Powers of matrices and generalized eigenspaces. J. of
Algebra, 341(1), 125–149, 2011.
[IzR6]
Z. Izhakian and L. Rowen, Supertropical polynomials and resultants, J. Algebra 324, 1860–1886, 2010.
[J]
Jacobson, N., Basic Algebra, Freeman, 1980.
[Ko]
V.M. Kopytov, Lattice ordered groups (Russian), Nauka, Moscow (1984)
[L1]
G. Litvinov, The Maslov dequantization, idempotent and tropical mathematics: a very brief introduction. J. of Math.
Sciences, 140(3),426–444, 2007.
[L2]
G. Litvinov, Dequantization of mathematical structures and tropical idempotent mathematics: An introductory
lecture. (See next reference), 2012
[L3]
G. Litvinov and V.P. Maslov, Tropical and idempotent mathematics: International Workshop. Pncelet Laboratory
and Moscow Center for Continuous Mathematical Education, Independent University of Moscow, 2012.
[MS]
D. Maclagan and B. Sturmfels, Tropical Geometry, preprint, 2009.
[M]
D. Marker, Model theory: An introduction, Springer Graduate texts in mathematics; 217, 2002.
[N]
A. Niv, Characteric polynomials of supertropical matrices, Commun. in Algebra, to appear, 2012.
[Par]
B. Parker. Exploded fibrations, preprint at arXiv: 0705.2408v1, 2007.
[Pay1]
S. Payne. Fibers of tropicalizations, Arch. Math., 2010 Correction: preprint at arXiv: ?? [math.AG], 2012.

ALGEBRAIC STRUCTURES

[Pay2]
[R1]
[R2]
[Sa]
[ShSh]
[SS]
[Vi]
[W]
[WW]

19

S. Payne. Analytification is the limit of all tropicalizations, preprint at arXiv: 0806.1916v3 [math.AG], 2009.
L.H. Rowen. Graduate Algebra: Commutative View. Pure and Applied Mathematics 73, Amer. Math. Soc., 2006.
L.H. Rowen. Graduate algebra: A noncommutative view Amer. Math. Soc., 2008.
G.E. Sacks, Saturated Model Theory, Mathematical Lecture Noets 80 Benjamin, 1972.
E. Sheiner and S. Shnider, An exploded-layered version of Payne’s generalization of Kapranov’s theorem, preprint,
2012.
D. E. Speyer and B. Sturmfels, Tropical mathematics, Math. Mag., 82 (2009), 1631/2-173.
O. Viro, Hyperfields for tropical geometry I. Hyperfields and dequantization Preprint at arXiv:math.AG/1006.3034v2
C. Weibel, EGA for monoids. Preprint, 2010.
H.J. Weinert and R. Wiegandt, On the structure of semifields and lattice-ordered groups, Periodica Mathematica
Hungaria 32 (1-2) (1996), 129–147.

Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel
E-mail address: zzur@math.biu.ac.il
Department of Mathematics, NWF-I Mathematik, Universität Regensburg 93040 Regensburg, Germany
E-mail address: manfred.knebusch@mathematik.uni-regensburg.de
Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel
E-mail address: rowen@math.biu.ac.il

