ELT LINEAR ALGEBRA II

arXiv:1705.00266v1 [math.RA] 30 Apr 2017

GUY BLACHAR AND EREZ SHEINER
Abstract. This paper is a continuation of [4]. Exploded layered tropical (ELT) algebra is an
extension of tropical algebra with a structure of layers. These layers allow us to use classical
algebraic results in order to easily prove analogous tropical results. Specifically we prove and use
an ELT version of the transfer principal presented in [2].
In this paper we use the transfer principal to prove an ELT version of Cayley-Hamilton Theorem,
and study the multiplicity of the ELT determinant, ELT adjoint matrices and quasi-invertible
matrices.
We also define a new notion of trace – the essential trace – and study its properties.

Contents
0. Introduction
0.1. ELT Algebras
0.2. The Element −∞
0.3. Non-Archimedean Valuations and Puiseux Series
0.4. ELT Algebras and Puiseux Series
0.5. Semirings with a Negation Map and ELT Rings
1. ELT Transfer Principle
1.1. The Transfer Principle
1.2. Formulation and Proof of the ELT Transfer Principle
1.3. Multiplicity of the ELT Determinant
1.4. The ELT Adjoint Matrix and Quasi-Invertible Matrices
1.5. The ELT Characteristic Polynomial and ELT Eigenvalues
2. ELT Traces
2.1. Trace of ELT Matrices
2.2. ELT Nilpotent Matrices
2.3. The Essential Trace
References

Page
1
2
3
3
4
5
5
5
7
8
9
11
13
13
13
13
17

0. Introduction
Tropical linear algebra, also known as Max-Plus linear algebra, has been studied for more than
50 years (ref. [5]). While tropical geometry mainly deals with geometric combinatorial problems,
tropical linear algebra deals with algebraic non-linear combinatorial problems (for instance, the assignment problem [18]). Tropical linear algebra may also be used as a mean to study the tropical
algebraic geometry (for instance, the tropical resultant). Notable work in this field can be found at
Date: 19th February 2018.
2010 Mathematics Subject Classification. Primary: 15A03, 15A09, 15A15, 15A63; Secondary: 16Y60, 14T05.
Key words and phrases. Tropical algebra, ELT algebra, matrix theory, characteristic polynomial, trace, transfer
principle.
This article contains work from Erez Sheiner’s Ph.D. Thesis, which was accepted on 1.1.16, and from Guy Blachar’s
M.Sc. Thesis, both submitted to the Math Department at Bar-Ilan University. Both works were carried under the
supervision of Prof. Louis Rowen from Bar-Ilan University, to whom we thank deeply for his help and guidance.
1

2

GUY BLACHAR AND EREZ SHEINER

[5], [6], [13], [15] and [21].
In our previous paper ([4]) we introduced a new structure, which we call exploded layered tropical algebra (or ELT algebra for short). This structure is a generalization of the work of Izhakian
and Rowen ([14]), and is similar to Parker’s exploded structure ([19]). The layers enable us to use
“classical language” even when dealing with tropical questions.
Our work in this paper can be divided into two main parts. The first one uses the theory of
semirings with a negation map to study the ELT structure. We formulate and prove an ELT version
of the transfer principles written in [2], and use them to study ELT matrix theory, such as the ELT
adjoint matrix (Theorem 1.9 and Theorem 1.10).
The second part of our work deals with a new notion of trace. Whereas the trace can be defined
as in the classical theory, it lacks some important properties in the ELT theory. For example, the
trace of an ELT nilpotent matrix need not be of layer zero. We define the essential trace of an ELT
matrix (subsection 2.3) to deal with such cases.
0.1. ELT Algebras.
Definition 0.1. Let L be a semiring, and F a totally ordered semigroup. An ELT algebra is
the pair R = R (L , F ), whose elements are denoted [ℓ]a for a ∈ F and ℓ ∈ L , together with the
semiring (without zero) structure:

[ℓ ]

a1 > a2
 1 a1
[ℓ
]
[ℓ
]
[ℓ
]
1
2
2
(1)
a1 + a2 :=
a2
a1 < a2 .

[ℓ1 +L ℓ2 ]
a1 a1 = a2
(2) [ℓ1 ]a1 · [ℓ2 ]a2 := [ℓ1 ·L ℓ2 ] (a1 +F a2 ).
We write . For

[ℓ]a,

ℓ is called the layer, whereas a is called the tangible value.

ELT algebras originate from [19], and are also discussed in [22].
Let R be an ELT algebra. We write s : R → L for the projection on the first component (the
sorting map):

s [ℓ]a = ℓ
We also write τ : R → F for the projection on the second component:

τ [ℓ]a = a
We denote the zero-layer subset

[0]R

= {α ∈ R|s (α) = 0}

and
R× = {α ∈ R|s (α) 6= 0} = R \ [0]R

We note some special cases of ELT algebras.
Example 0.2. Let (G, ·) be a totally ordered group. We denote by Gmax the max-plus algebra
defined over G, i.e. the set G endowed with the operation
a ⊕ b = max {a, b} , a ⊙ b = a · b.
Then Gmax is equivalent to the trivial ELT algebra with F = G and L = {1}.
Example 0.3. Zur Izhakian’s supertropical algebra ([11]) is equivalent to an ELT algebra with a
layering set L = {1, ∞}, where
1 + 1 = ∞, 1 + ∞ = ∞ + 1 = ∞, ∞ + ∞ = ∞

ELT LINEAR ALGEBRA II

3

and
1 · 1 = 1, 1 · ∞ = ∞ · 1 = ∞, ∞ · ∞ = ∞.
The supertropical ”ghost” elements aν correspond to [∞]a in the ELT notation, whereas the
tangible elements a correspond to [1]a.
We define a partial order relation  on R in the following way:
x  y ⇐⇒ ∃z ∈ [0]R : x = y + z
Lemma 0.4 ([4, Lemma 0.4]).  is a partial order relation on R.
Let us point out some important elements in any ELT algebra R:
(1) [1]0, which is the multiplicative identity of R.
(2) [0]0, which is idempotent for both operations of R.
(3) [−1]0, which has the role of “−1” in our theory.
Note that

[0]0

· [ℓ]a = [0]a. Therefore,

[0]R

= [0]0 R. In particular,

[0]R

is an ideal of R.

Throughout this paper, unless otherwise noted, we work under more general assumptions than
in [4]. Out underlying ELT algebras R = R (L , F ) will be commutative ELT rings, meaning
that F is an abelian group, and L is a commutative ring.
0.2. The Element −∞. As in the tropical algebra, ELT algebras lack an additive identity. Therefore, we adjoin a formal element to the ELT algebra R, denoted by −∞, which satisfies ∀α ∈ R:
−∞ + α = α + −∞ = α
−∞ · α = α · −∞ = −∞
We also define s (−∞) = 0. We denote R = R ∪ {−∞}.
We note that R is now a semiring, with the following property:
α + β = −∞ =⇒ α = β = −∞
Such a semiring is called an antiring. Antirings are dealt with in [23] and [7].
0.3. Non-Archimedean Valuations and Puiseux Series. We recall the definition of a (nonArchimedean) valuation (see [8] and [24]).
Definition 0.5. Let K be a field, and let (Γ, +, ≥) be an abelian totally ordered group. Extend Γ
to Γ ∪ {∞} with γ < ∞ and γ + ∞ = ∞ + γ = ∞ for all γ ∈ Γ. A function v : K → Γ ∪ {∞} is
called a valuation, if the following properties hold:
(1) v (x) = ∞ ⇐⇒ x = 0.
(2) ∀x, y ∈ K : v (xy) = v (x) + v (y).
(3) ∀x, y ∈ K : v (x + y) ≥ min {v (x) , v (y)}.
Given a valuation v over a field K, we recall some basic properties:
(1) v (1) = 0.
(2) ∀x ∈ K : v (−x) = v (x).
(3) ∀x ∈ K × : v x−1 = −v (x).
(4) If v (x + y) > min {v (x) , v (y)}, then v (x) = v (y). (For this reason, the equality between
the valuation of two elements is central in out theory.)
One may associate with v the valuation ring
Ov = {x ∈ K|v (x) ≥ 0}
This is a local ring with the unique maximal ideal
mv = {x ∈ K|v (x) > 0}


The quotient kv = Ov mv is called the residue field of the valuation.

4

GUY BLACHAR AND EREZ SHEINER

Let us present another key construction related to valuations. For γ ∈ Γ, let D≥γ = {x ∈ K|v (x) ≥ γ}
and D>γ = {x ∈ K|v (x) > γ}. It is easily seen that D≥γ is an abelian additive group, and
. that
D
D>γ is a subgroup of D≥γ . Note that for γ = 0, D≥0 = Ov and D>0 = mv . Set Dγ = ≥γ D .
>γ

The associated graded ring of K with respect to v is
M
grv (K) =
Dγ
γ∈Γ

Given γ1 , γ2 ∈ Γ, the multiplication in K induces a well-defined multiplication Dγ1 × Dγ2 → Dγ1 +γ2
given by
(x1 + D>γ1 ) · (x2 + D>γ2 ) = x1 x2 + D>(γ1 +γ2 )
This multiplication can be extended to a multiplication map in grv (K), endowing it with a structure
of a graded ring.
We will now focus on Puiseux series, which is the central example for our theory. The field of
Puiseux series with coefficients in a field K and exponents in an abelian ordered group Γ is
(
)
X
i
K{{t}} =
αi t αi ∈ K, I ⊆ Γ is well-ordered
i∈I

The resulting set, equipped with the natural operations, is a field; in addition, if K is algebraically
closed and Γ is divisible, then K{{t}} is also algebraically closed.
Assuming Γ is also totally ordered, one may define a valuation on the field of Puiseux series
v : K{{t}} → Γ ∪ {∞} as follows: v (0) = ∞, and
!
X
i
v
αi t = min {i ∈ I|αi 6= 0}
i∈I

Let us examine the associated graded ring with respect to this valuation. For each γ ∈ Γ, we first
claim that Dγ ∼
= K. Indeed, the kernel of the homomorphism f : D≥γ → K defined by


X
f
αi ti  = αγ
γ≤i∈I

is precisely D>γ (since D>γ is the subgroup of D≥γ of Puiseux series whose minimal degree is bigger
than γ).
0.4. ELT Algebras and Puiseux Series. Let R = R (L , F ) be an ELT algebra. In [4] we introduced the EL tropicalization function ELTrop : L {{t}} → R, which is defined in the following
way: if x ∈ L {{t}}\ {0} has a leading monomial ℓta , then
ELTrop (x) = [ℓ] (−a) .
In addition, ELTrop (0) = −∞.
Lemma 0.6 ([4, Lemma 0.9]). The following properties hold:
(1) ∀x, y ∈ L {{t}} : ELTrop (x) + ELTrop (y)  ELTrop (x + y).
(2) ∀α ∈ L ∀x ∈ L {{t}} : ELTrop (αx) = [α]0 ELTrop (x).
(3) ∀x, y ∈ L {{t}} : ELTrop (x) ELTrop (y)  ELTrop (xy).
We remark that in the case in which R is an ELT integral domain, meaning L is an integral
domain, we have ELTrop (x) ELTrop (y) = ELTrop (xy) for all x, y ∈ L {{t}}.
Let us examine the relation x  ELTrop (y) a bit more deeply. If x = ELTrop (y), it means that
x can be lifted to a Puiseux series which has x as its leading monomial. Otherwise, we have that x
is of layer zero, and its tangible value is bigger than the tangible value of ELTrop (y); so one may
say that x can also be lifted to a Puisuex series with leading coefficient x, where we allow it to have
a zero coefficient in its leading monomial.

ELT LINEAR ALGEBRA II

5

0.5. Semirings with a Negation Map and ELT Rings. Semirings need not have additive
inverses to all of the elements. While some of the theory of rings can be copied “as-is” to semirings,
there are many facts about rings which use the additive inverses of the elements. The idea of negation
maps on semirings (sometimes called symmetrized semirings) is to imitate the additive inverse map.
Semirings with negation maps are discussed in [1], [9], [10], [2], [3], [20].
Definition 0.7. Let R be a semiring. A map (−) : R → R is a negation map (or a symmetry)
if the following properties hold:
(1) ∀a, b ∈ R : (−) (a + b) = (−)a + (−)b.
(2) (−)0R = 0R .
(3) ∀a, b ∈ R : (−) (a · b) = a · ((−)b) = ((−)a) · b.
(4) ∀a ∈ R : (−) ((−)a) = a.
We say that (R, (−)) is a semiring with a negation map (or a symmetrized semiring). If (−)
is clear from the context, we will not mention it.
We give several examples of semirings with negation maps:
• A trivial example of a negation map (over any semiring) is (−)a = a.
• If R is a ring, it has a negation map (−)a = −a.
• If R is an ELT algebra, we have a negation map given by (−)a = [−1]0a.
The last example is the central example for our theory, since it shows that any ELT algebra is
equipped with a natural negation map. Thus, the theory of semirings with negation maps can be
used when dealing with ELT algebras.
We now present several notations from this theory:
• a + (−)a is denoted a◦ .
• R◦ = {a◦ |a ∈ R}.
• We define two partial orders on R:
– The relation ◦ defined by
a ◦ b ⇔ ∃c ∈ R◦ : a = b + c
– The relation ∇ defined by
a∇b ⇔ a + (−)b ∈ R◦
If R is an ELT algebra, then some of these notations have already been defined. For example,
a◦ = [0]0a, R◦ = [0]R and the relation ◦ is the relation .
1. ELT Transfer Principle
The transfer principles are two theorems, presented in [2], which allows to conveniently transfer
equalities between polynomial expressions in the classical theory to theorems about semirings with
a negation map. We recall that any ELT algebra R has a negation map
(−) [ℓ]a = [−ℓ]a
and thus we may view each ELT algebra as a semiring with a negation map.
In this section, we use the transfer principles to prove two transfer principles for the ELT theory,
and use these transfer principles to study the ELT adjoint matrix.
1.1. The Transfer Principle. In this subsection, we briefly introduce the two classical transfer
principles given in [2].
Definition 1.1. A positive polynomial expression in the variables λ1 , . . . , λm is a formal expression produced by the context-free grammar E 7→ E +E, (E)×(E), where the symbols 0, 1, λ1 , . . . , λm
are thought of as terminal symbols of the grammar. A monomial in a positive polynomial expression is a sum of expressions of the form cI λi11 . . . λimm , where I = (i1 , . . . , in ) is fixed.

6

GUY BLACHAR AND EREZ SHEINER

That means that 0, 1, λ1 , . . . , λm are positive polynomial expressions. Also, λ1 + (λ2 ) × (λ1 + λ3 )
is a positive polynomial expression. Any positive polynomial expression E can be interpreted as a
polynomial in N [λ1 , . . . , λm ]. We say that a monomial λi11 . . . λimm appears in the expression E if
there exists a positive integer c such that cλi11 . . . λimm appears in the expansion of the polynomial
obtained by interpreting E in N [λ1 , . . . , λm ].
im
If R is a semiring with a negation map, and if cλi11 . . . λm
is a monomial, we define

i1
i1
im
(−) cλ1 . . . λm = ((−) c) λ1 . . . λimm
Definition 1.2. Let R be a semiring with a negation map. A polynomial expression is a
formal expression of the form P + − P − , where P + and P − are positive polynomial expressions. A
monomial in P is a sum of the monomials cI λi11 . . . λimm from P + and c′I λi11 . . . λimm from P − , where
I = (i1 , . . . , in ) is fixed. We say that a monomial appears in the polynomial expression P , if it
appears either in P + or in P − .
Definition 1.3. Let P and Q be polynomial expressions. We say that the identity P = Q is valid
in a semiring with a negation map R, if it holds for any semiring with a negation map R and for
any substitution λ1 = r1 , . . . , λm = rm of r1 , . . . , rm ∈ R.
Recall the relations ◦ and ∇ from subsection 0.5.
Definition 1.4. Let P and Q be polynomial expressions.
(1) We say that the identity P ∇Q holds in all commutative semirings with a negation map, if
for any semiring with a negation map R and for any substitution λ1 = r1 , . . . , λm = rm of
r1 , . . . , rm ∈ R,
P (r1 , . . . , rn ) ∇Q (r1 , . . . , rn )
(2) We say that the identity P ◦ Q holds in all commutative semirings with a negation map,
if for any semiring with a negation map R and for any substitution λ1 = r1 , . . . , λm = rm
of r1 , . . . , rm ∈ R,
P (r1 , . . . , rn ) ◦ Q (r1 , . . . , rn )
We recall the transfer principle ([2, Theorems 4.20 and 4.21]):
Theorem 1.5 (Transfer principle, weak form). Let P and Q be polynomial expressions. If the
identity P = Q holds in all commutative rings, then the identity P ∇Q holds in all commutative
semirings with negation map.
Theorem 1.6 (Transfer principle, strong form). Let P and Q be polynomial expressions. If the
identity P = Q holds in all commutative rings, and if Q = Q+ − Q− for some positive polynomial
expressions such that there is no monomial appearing simultaneously in Q+ and Q− , then the identity
P ◦ Q holds in all commutative semirings with negation map.
The transfer principle allows us to prove several important theorems in a rather convenient way.
Corollary 1.7 (Multiplicativity of determinant). Let R be a semiring with a negation map, and let
A ∈ Rn×n . We define:
X
a1,σ(1) . . . an,σ(n)
det (A)+ =
σ∈An

−

det (A)

=

X

a1,σ(1) . . . an,σ(n)

σ∈Sn \An

det (A) =

+

det (A) − det (A)

−

In [2, Corollary 4.8], it is proven that if R is a semiring with a negation map, then
∀A, B ∈ Rn×n : det (AB) ◦ det (A) det (B)
Corollary 1.8 (Cayley-Hamilton theorem). Let R be a semiring with a negation map, and let
A ∈ Rn×n . We know that over a commutative ring, fA (A) = 0. We can use the strong form of the
transfer principle componentwise, and thus
fA (A) ◦ 0

ELT LINEAR ALGEBRA II

7

In other words,
fA (A) ∈ (R◦ )

n×n

1.2. Formulation and Proof of the ELT Transfer Principle. We first recall that all of our
ELT algebras are commutative ELT rings, meaning R = R (L , F ) where F is an abelian group
and L is a commutative ring.
We would like to have a tool of proving polynomial identities over commutative ELT rings. Recall
that any ELT ring is a semiring with a negation map a 7→ [−1]0a (subsection 0.5), and thus we may
apply the transfer principle. In order to strengthen the general transfer principle, we will use results
from tropical linear algebra. This is formulated in the following theorems:
Theorem 1.9 (ELT Transfer Principle for equality). Let P and Q be polynomial expressions. Assume that the identity P = Q holds in all commutative rings. If the identity P = Q holds in all
commutative tropical algebras, then the identity P = Q holds in all commutative ELT rings.
Theorem 1.10 (ELT Transfer Principle for surpassing). Let P and Q be polynomial expressions.
Assume that the identity P = Q holds in all commutative rings. If the identity P ≥ Q holds in all
commutative tropical algebras, then the identity P  Q holds in all commutative ELT rings.
We prove two lemmas which will help us prove the theorems:

Lemma 1.11. Let R be an ELT algebra, and let α, β ∈ R. If s α + [−1]0β = 0, and if τ (α) ≥ τ (β),
then α  β.
Proof. Denote α = [ℓ]a, β = [k]b. τ (α) ≥ τ (β) means a ≥ b. We have two options:
(1) If a = b, then α + [−1]0β = [ℓ−k]a ∈ [0]R. Thus, ℓ = k, which implies α = β.
(2) If a > b, then α + [−1]0β = α ∈ [0]R. Thus, ℓ = 0, and α = α + β  β.
In any case α  β, and thus we are finished.



Lemma 1.12. Let R = R (L , F ) be an ELT algebra. Endow F with a max-plus algebra, Fmax .
Then the function τ : R → Fmax is a “homomorphism”, in the sense that:
(1) ∀x, y ∈ R : τ (x + y) = τ (x) ⊕ τ (y).
(2) ∀x, y ∈ R : τ (xy) = τ (x) ⊙ τ (y).
Proof. Take [ℓ1 ]a1 , [ℓ2 ]a2 ∈ R.
(1) If a1 = a2 , then
τ

[ℓ1 ]a

1


+ [ℓ2 ]a2 = τ

[ℓ1 +L ℓ2 ]a

1



= a1 = a1 ⊕ a2 = τ

[ℓ1 ]a

1



⊕τ

Otherwise, without loss of generality, a1 > a2 , and thus



τ [ℓ1 ]a1 + [ℓ2 ]a2 = τ [ℓ1 ]a1 = a1 = a1 ⊕ a2 = τ [ℓ1 ]a1 ⊕ τ


(2) τ [ℓ1 ]a1 · [ℓ2 ]a2 = τ [ℓ1 ·L ℓ2 ] (a1 +F a2 ) = a1 +F a2 = a1 ⊙ a2 = τ

[ℓ2 ]a

[ℓ2 ]a
[ℓ1 ]a

2

1





2



⊙τ

[ℓ2 ]a

2





We now prove these theorems. We note that since Theorem 1.9 follows from Theorem 1.10, we
will only prove the latter.

Proof of Theorem 1.10. By the weak form of the general transfer principle, s P + [−1]0Q = 0.
Let R = R (L , F ) be a commutative ELT ring. We will now prove that for any substitution
λ1 = r1 , . . . , λm = rm of r1 , . . . , rm ∈ R,
τ (P (r1 , . . . , rm )) ≥ τ (Q (r1 , . . . , rm ))
We endow F with the max-plus operations. By Lemma (Lemma 1.12) τ : R → Fmax is a homomorphism. Therefore, for any ELT polynomial p ∈ R [λ] and for any substitution λ1 = r1 , . . . , λm =
rm of r1 , . . . , rm ∈ R,
τ (p (r1 , . . . , rm )) = p (τ (r1 ) , . . . , τ (rm ))

8

GUY BLACHAR AND EREZ SHEINER

Thus, for any substitution λ1 = r1 , . . . , λm = rm of r1 , . . . , rm ∈ R,
τ (P (r1 , . . . , rm )) = P (τ (r1 ) , . . . , τ (rm )) ≥ Q (τ (r1 ) , . . . , τ (rm )) = τ (Q (r1 , . . . , rm ))

We have proven that s P + [−1]0Q = 0 and that τ (P ) ≥ τ (Q); by Lemma 1.11, we are finished.

Remark 1.13. Throughout the uses of the ELT transfer principle for equality, we need to check
the corresponding identity in commutative tropical algebras. However, since major work has been
done in the supertropical theory (see [15], [16] and [17]), we usually check that one of the following
conditions holds:
(1) The identity P = Q holds in all commutative supertropical algebras.
(2) The identity ν (P ) = ν (Q) holds in all commutative supertropical algebras.
Similarly, to prove a surpassing relation, we usually check that one of the following conditions holds:
(1) The identity P  Q holds in all commutative supertropical algebras.
gs

(2) The identity P ≥ν Q holds in all commutative supertropical algebras.
This tool allows us to prove many polynomial surpassing and equalities without effort. An example
is given in the next subsection.
1.3. Multiplicity of the ELT Determinant. We return to Corollary 1.7, which holds in particular
over commutative ELT rings. We first formulate this corollary in the “ELT language”:
Corollary 1.14 (Multiplicativity of the ELT determinant). Let R be a commutative ELT ring.
n×n
If A, B ∈ R
, then
det (AB)  det (A) · det (B)
We now present several corollaries from the multiplicativity of the ELT determinant, which are
two cases in which the ELT determinant is strictly multiplicative. First, we prove a lemma that will
be helpful for the first case:
Lemma 1.15. If x, y ∈ R satisfy x  y, and if s (x) 6= 0, then x = y.
Proof. Write x = [ℓ]a, y = [k]b. Since x  y, there is c ∈ F such that x = y + [0]c. In other words,
[ℓ]a

= [k]b + [0]c

By the definition of addition, a ≥ b, and a = max {b, c}. If a > b, then a = c > b, and thus
[ℓ]a

= [k]b + [0]c = [0]c

in contradiction to the fact that ℓ = s (x) 6= 0. Thus, x = y.



Corollary 1.16. If s (det (AB)) 6= 0, then
det (AB) = det (A) · det (B)
Proof. From Corollary 1.14,
det (AB)  det (A) · det (B)
By Lemma 1.15, we get equality.



Another case in which the determinant is multiplicative is when either A or B are invertible:
n×n
Theorem 1.17. If A, B ∈ R
, such that A or B are invertible. Then
det (AB) = det (A) · det (B)

Proof. Assume that B is invertible (the second direction is proved similarly). We note that by
Corollary 1.14,
det (AB)  det (A) · det (B)
but also


−1
det (A) = det (AB) B −1  det (AB) · det B −1 = det (AB) · (det (B)) .

ELT LINEAR ALGEBRA II

9

The latter surpassing implies that
det (A) · det (B)  det (AB) .
Since  is antisymmetric on R, the conclusion follows.



Although the determinant is not multiplicative, a natural question is: if AB is non-singular, is BA
also non-singular? The answer to this question is negative, as the following example demonstrates:
Example 1.18. In R = R (C, R), consider
A=





[1]1

[1]1

[1]2

[1]3

Then det (AAt ) = [1]8, yet det (At A) = [0]10.
1.4. The ELT Adjoint Matrix and Quasi-Invertible Matrices. As we have seen, the invertible
matrices in the ELT sense are limited. So, we shall try to generalize this. Our goal is to find an
equivalent condition to the fact that det (A) is invertible.
Definition 1.19. Let R be a commutative ELT ring. A quasi-identity matrix is a matrix
n×n
, which is idemopotent, nonsingular and defined by
I˜ ∈ R
(
 
[1]0
i=j
I˜
=
i,j
αi,j i 6= j
where αi,j ∈ R, s (αi,j ) = 0.
n×n
n×n
Definition 1.20. Let R be a commutative ELT ring, and let A ∈ R
. A matrix B ∈ R
is a quasi-inverse for A, if AB and BA are quasi-identity matrices. In this case, A is called
quasi-invertible. Note that AB and BA may differ.
n×n
. The (i, j)-minor A′i,j of
Definition 1.21. Let R be a commutative ELT ring, and let A ∈ R
a matrix A = (ai,j ) is obtained by deleting the i-th row and the j-th column. Its ELT determinant
is a′i,j = det A′i,j .
n×n
Definition 1.22. Let R be a commutative ELT ring, and let A ∈ R
. The adjoint matrix of
A is
(adj (A))i,j = [ε(i,j)]0 a′j,i
where ε (i, j) = (−1)i+j .
−1

We would like to prove that when det (A) is invertible in R, (det (A)) adj (A) is a quasi-inverse
of A. We present here some corollaries from the ELT transfer principle, which together will prove
the assertion (Theorem 1.26). We use the ELT transfer principles componentwise.
Corollary 1.23. A · adj (A) = det (A) IA , where IA  I.
Proof. We use the ELT transfer principle for surpassing. This result is known in ring theory, and is
proved in the supertropical theory (see [15, Remark 4.5]).

Corollary 1.24.
det (A · adj (A)) = det (A)

n

Proof. We use the ELT transfer principle for equalities. This result is known in ring theory, and is
proved in the supertropical theory (see [15, Theorem 4.9]).

Corollary 1.25.
2

(A · adj (A)) = det (A) · A · adj (A)
Proof. We use the ELT transfer principle for equalities. This result is known in ring theory, and is
proved in the supertropical theory (see [15, Theorem 4.12]).

Theorem 1.26. If det (A) is invertible in R, then A is quasi-invertible.

10

GUY BLACHAR AND EREZ SHEINER

Proof. By Corollary 1.23, A · adj (A) = det (A) · IA , where IA  I. It is left to prove that IA is
nonsingular and idempotent.
By Corollary 1.24, det (A · adj (A)) = det (A)n . But
n

n

det (A) = det (A · adj (A)) = det (det (A) IA ) = det (A) det (IA )
Since det (A) is invertible, det (IA ) = [1]0.
To prove that IA is idempotent, we use Corollary 1.25:

2 
−1
−1
2
2
2
=
(det (A)) A · adj (A) = det (A)
IA
(A · adj (A)) =
−1

=
det (A)2
det (A) · A · adj (A) = (det (A))−1 A · adj (A) = IA
as required.



Remark 1.27. Using the same arguments, one may show that adj (A) · A is det (A) times a quasiidentity matrix.
Corollary 1.28. Let R be a commutative ELT ring. Then A is quasi-invertible if and only if det (A)
is invertible.
We will now use the theory of the ELT adjoint matrix to study the connection between matrix
singularity and linear dependency. We recall the following theorem:
Theorem ([4, Theorem 1.6]). Let R = R (F, R) be an ELT algebra, where F is an algebraically
n×n
closed field. Consider A ∈ R
. Then the rows of A are linearly dependent, iff the columns of
A are linearly dependent, iff s (det A) = 0F .
This theorem was proved using the Fundamental Theorem, thus only in the case of R = R (F, R)
where F is an algebraically closed field. We will prove the following:
n×n
an ELT matrix. If det A
Theorem 1.29. Let R be a commutative ELT ring, and let A ∈ R
is invertible in R, then the columns (respectively, rows) of A are linearly independent.
Before proving this theorem, we recall the Hungarian algorithm ([18]):
n×n
Definition 1.30. An entry ai,j of a tropical matrix A ∈ Gmax
is called column-critical if it
is maximal within its columns, i.e., if ∀k : ai,j ≥ ak,j . A matrix A is called critical if there exists a
permutation σ ∈ Sn such that a1,σ(1) , . . . , an,σ(n) are column-critical.
n×n
be a tropical matrix. Then there
Theorem 1.31 (The Hungarian Algorithm). Let A ∈ Gmax
are scalars α1 , . . . , αn ∈ R× such that


α1 ⊙ R1 (A)


..


.
αn ⊙ Rn (A)

n×n
is critical. In other words, there exists a diagonal matrix D ∈ Gmax
, whose diagonal entries
are not −∞, such that A ⊙ D is critical.
n×n
n×n
is critical if τ (A) = (τ (ai,j )) ∈ Gmax
In the ELT case, we say that a matrix A ∈ R
is critical.
n×n
n×n
Corollary 1.32. Let A ∈ R
. Then there exists an invertible diagonal matrix D ∈ R
such that DA is critical.

n×n
Proof. Let D′ = d′i,j ∈ Gmax
be a diagonal matrix such that D′ ⊙ τ (A) is a critical tropical
n×n
matrix. We define D = (di,j ) ∈ R
as
 ′
[1]d , i = j
i,i
di,j =
−∞, i 6= j
Obviously, DA is critical (since τ (DA) = τ (D) ⊙ τ (A) = D′ ⊙ τ (A) is critical), as required.



ELT LINEAR ALGEBRA II

11

We are now ready to prove Theorem 1.29.
Proof of Theorem 1.29. We prove the assertion on the columns of A. The assertion that the rows
of A are linearly independent can be proven by replacing A with At .
n

t
Suppose that s (Av) = (0, . . . , 0) for some v ∈ R× . If
A∇ = (det A)

−1

adj (A) ,

′
there exists a quasi-identity matrix IA
such that
′
A∇ A = IA

Thus,


t
′
s (IA
v) = s A∇ A · v = (0, . . . , 0) .

n×n
′ t
We apply Corollary 1.32 for (IA
) to find a diagonal invertible matrix D ∈ R
such that
′ t
′
D (IA
) is critical. By transposing this matrix, we get a matrix IA
D such that there is a permutation
′
′
σ ∈ Sn for which (IA
D) i, j is row-critical in IA
D. By Theorem 1.17,
′
′
det (IA
D) = det IA
· det D = det D
′
′
is not of layer zero, i.e. IA
D is nonsingular. We note that the only non-zero layered track in IA
is
′
the diagonal track, since any entry of IA which is not on the diagonal is of layer zero; hence, we may
assume σ = Id, that is the diagonal entries are row-critical.
′
′
′
Returning to the original equation s (IA
v) = (0, . . . , 0)t , we replace IA
by B = IA
D and v
′
−1
by v = D v to get
s (Bv ′ ) = (0, . . . , 0)t
Let 1 ≤ k ≤ n such that
τ (vk′ ) = max τ (vi′ ) .
1≤i≤n

Then
(Bv ′ )k =

n
X
i=1

bk,i vi′ =

n
X

bk,i vi′ + bk,k vk′ .

i=1
i6=k

′
′
We recall that B = IA
D, where IA
is a quasi-identity matrix and D is an invertible diagonal matrix.
Thus, every entry of B which is not on its diagonal is of layer zero. Furthermore, for any i 6= k we
have τ (vi′ ) ≤ τ (vk′ ) and τ (bk,i ) ≤ τ (bk,k ). Therefore each summand bk,i vi′ cannot dominate bk,k vk′ ,
implying
(Bv ′ )k = bk,k vk′
′
which implies s (bk,k vk′ ) = 0. Since bk,k = (IA
)k,k dk,k = dk,k is not of layer zero (because D is
′
′
invertible), we must have s (vk ) = 0. Now, vk = d−1
k,k vk implies s (vk ) = 0.
n

But v ∈ R× , therefore s (vk ) = 0 implies vk = −∞. By the choice of k, we must have

v = (−∞, . . . , −∞), which proves that the columns of A are linearly independent.



1.5. The ELT Characteristic Polynomial and ELT Eigenvalues.
n×n
Definition 1.33. Let A ∈ R
be a matrix. The ELT characteristic polynomial of A is
defined to be

pA (λ) = det λIn + [−1]0A
n×n
be a matrix. A vector v ∈ (R× )n is called an eigenvector of A
Definition 1.34. Let A ∈ R
with an eigenvalue x ∈ R if v 6= (−∞, ..., −∞) and
Av = xv.
Proposition 1.35. Let A ∈ R

n×n

be a matrix with eigenvalue x. Then s (pA (x)) = 0L .

12

GUY BLACHAR AND EREZ SHEINER

Proof. Choose v to be an eigenvector of the eigenvalue v, then Av = xv. Therefore
Av + [−1]0 · xv = [0]0 · xv.
In other words,


s xv + [−1]0Av = (0L , ..., 0L ).

Thus


s (xIn + [−1]0A)v = (0L , ..., 0L ).

By Theorem 1.29, we conclude that s det xIn + [−1]0A = 0L , i.e., s (pA (x)) = 0L .



Note that the other direction is not necessarily true, i.e., there could be an ELT root of the
characteristic polynomial which is not an eigenvalue. Indeed, if one tried to prove that direction, he
would encounter the following difficulty:
Av 6= Av + [−1]0 · xv + xv.
2×2
Example 1.36. Consider the matrix A ∈ R
,


[1]1 [1]2
A = [1]
,
2 [1]3
Its ELT characteristic polynomial is
pA (λ)



[−1]0A



[−1]2
λ + [−1]1
= det
[−1]2
λ + [−1]3

=

det λI2 +

=

(λ + [−1]1)(λ + [−1]3) + [−1]4 = λ2 + [−1]3 · λ + [0]4.

If λ = [0]1, λ = [ℓ]α with α < 1 or λ = [1]3, then s (pA (λ)) = 0.
The only eigenvalue of A is λ = [1]3, with

   
 
[1]1 [1]2
[1]0
[1]3
[1]0
[1]3
=
=
.
[1]2 [1]3
[1]1
[1]4
[1]1
One may also define an ELT eigenvalue and an eigenvector in the following way:
n×n
be a matrix. A vector v ∈ (R× )n is called an ELT eigenvector
Definition 1.37. Let A ∈ R
of A with an ELT eigenvalue x ∈ R if v 6= (−∞, ..., −∞) and

s Av + [−1]0xv = (0L , ..., 0L ).

This definition is similar to the concept of ’ghost surpass’ given by Izhakian, Knebusch and Rowen
(ref. [12]).

Proposition 1.38. Let R = R (F, R) be an ELT algebra, where F is an algebraically closed field,
n×n
and let A ∈ R
be a matrix. Then x is an ELT eigenvalue of A if and only if s (pA (x)) = 0L .

Proof. By Definition 1.37, x is an eigenvalue of A if and only if there exists a vector v ∈ (R× )n such
that v 6= (−∞, ..., −∞) and

s xv + [−1]0Av = (0L , ..., 0L ),
if and only if the columns of pA (x) = x · In + [−1]0A are linearly dependent, if and only if pA (x) is
singular ([4, Theorem 1.7]).

We finish by reformulating Cayley-Hamilton theorem (Corollary 1.8) in the “ELT language”.
Corollary 1.39 (ELT Cayley-Hamilton theorem). Let R be a commutative ELT ring, and let
n×n
be an ELT matrix. Then
A∈ R
s (pA (A)) = 0

ELT LINEAR ALGEBRA II

13

2. ELT Traces
2.1. Trace of ELT Matrices.
n×n
Definition 2.1. Let R be a commutative ELT ring, and take A ∈ R
, A = (ai,j ). The trace
of A is
n
X
ai,i
tr (A) =
i=1

Lemma 2.2. The ELT trace satisfies the following relations:
n×n
: tr (A + B) = tr (A) + tr (B).
(1) ∀A, B ∈ R
n×n
(2) ∀α ∈ R ∀A ∈ R
: tr (αA) = αtr (A).
n×n
(3) ∀A, B ∈ R
: tr (AB) = tr (BA).

Proof. These properties can be proved just as the classical theory.



2.2. ELT Nilpotent Matrices.
Definition 2.3. Let R be a commutative ELT ring. A matrix A ∈ R
n×n
if there exists m ∈ N such that Am ∈ [0] R
.

n×n

is called ELT nilpotent,

Similarly to the classical theory, one would expect that the trace of a nilpotent matrix would
be of layer zero; however, this is wrong. For this reason, we define the essential trace in the next
subsubsection.


[1]0 [0]1
Example 2.4. Let R = R (C, R), and consider the following matrix: A = [0]
. Then
0 [1]0
tr (A) = [2]0, while


 

[1]0 [0]1
[1]0 [0]1
[0]1 [0]1
A2 = [0] [1]
=
.
[0]0 [1]0
[0]0 [0]1
0
0
Therefore, ELT nilpotent matrices don’t necessarily have zero-layered trace.
Another interesting example is an ELT nilpotent matrix, whose determinant is not of layer zero.
Example 2.5. Let R be a commutative ELT ring, and take a, b, c, d ∈ R such that


τ a2 < τ (bc) < τ d2


a b
and s (d) = 0. Consider the matrix A =
. We have
c d
 2
 

a + bc ab + bd
bc bd
2
A =
=
ac + cd bc + d2
cd d2
and


 

abc + bcd abd + bd2
bcd bd2
=
bc2 + cd2 bcd + d3
cd2 d3
which is of layer zero, since s (d) = 0.
But we may choose a, b, c, d such that τ (bc) > τ (ad) and s (bc) 6= 0; in that case, A is quasiinvertible and ELT nilpotent.
A3 =

2.3. The Essential Trace. Before defining the new notion of trace, we give an important definition,
which is significant in our construction of the new trace.
n
X

hi ∈ R [λ] be an ELT
X
polynomial, where each hi is a monomial. For a monomial h, define ph (λ) =
hi .

Definition 2.6. Let R be a commutative ELT ring, and let p (λ) =

i=1

hi 6=h

(1) The monomial h is called inessential at a point a ∈ R, if p (a) = ph (a) and τ (h (a)) <
τ (p (a)). If h is inessential at every point of R, it is called inessential.

14

GUY BLACHAR AND EREZ SHEINER

(2) The monomial h is called essential at a point a ∈ R, if p (a) = h (a) and τ (ph (a)) <
τ (p (a)). If h is essential at some point of R, it is called essential.
(3) The monomial h is called quasi-essential at a point a ∈ R, if it is neither inessential at
a nor essential at a. If h is quasi-essential at some point of R, it is called quasi-essential.
Throughout the rest of the section, we need a stronger assumption on our ELT algebras. We
require them to be divisible ELT fields, that is ELT algebras of the form R = R (L , F ), where
F is a divisible group and L is a field.
n×n
. We define
Definition 2.7. Let R be a divisible ELT field, and let A ∈ R


τ (cℓ )
τ (ck )
L (A) =
ℓ ≥ 1 ∀k ≤ n :
≥
ℓ
k
µ (A) = min (L (A))
We write µ for µ (A), if A is given.
n

Lemma 2.8. Let R be a divisible ELT field, and let p (λ) = λ +

n
X

αi λn−i ∈ R [λ] be an ELT

i=1

polynomial. Then the first monomial after λn that is not inessential is αµ λn−µ .
Proof. We need to find the monomial for which the intersection between λn and αℓ λn−ℓ is maximal
(in the sense that its tangible value is maximal).
First, we compute the tangible value of the intersection:
λn = αℓ λn−ℓ ⇒ τ (λ) =

τ (αℓ )
ℓ

ℓ)
The tangible value of the value of the polynomial at that point is nτ (α
.
ℓ
So, if
τ (αℓ )
τ (αk )
∀k ≤ n :
≥
ℓ
k
ℓ satisfies our conditions. Take such ℓ minimal, which is µ, and we are done.



Remark 2.9. If |L (A)| ≥ 2, then αµ λn−µ is only quasi-essential in pA (λ).
n×n
Definition 2.10. Let R be a divisible ELT field, and let A ∈ R
be a matrix. Assume
n
X
αi λn−i . αµ is called the dominant characteristic coefficient. The essential
pA (λ) = λn +
i=1

trace of A, denoted etr (A), is given by the formula
(
[−1]0tr (A) λn−1 is essential in p (λ)
tr (A)
A
etr (A) = [0]  τ (αµ ) 
Otherwise
µ

Lemma 2.11. If s (tr (A)) = 0, then s (etr (A)) = 0.

Proof. If [−1]0tr (A) λn−1 is essential in pA (λ), then etr (A) = tr (A). which is of layer zero. Otherwise, [−1]0tr (A) λn−1 is not essential in pA (λ), and thus, by the definition of essential trace,
s (etr (A)) = 0.

n×n
be a matrix over a commutative ELT ring R. A path from i
Definition 2.12. Let A ∈ R
to j is an expression of the form
s = ai,i2 ai2 ,i3 . . . aik ,j
where 1 ≤ i1 , . . . , ik+1 ≤ n. If i = j, we call it a multicycle. The length of s is |s| = k. The
τ (s)
tangible average value of s is
. A simple cycle is a multicycle from i to i, such that ij 6= ij ′
|s|
for j 6= j ′ (with i1 = i).
Fact 2.13. Every multicycle can be written as a product of simple cycles.

ELT LINEAR ALGEBRA II

15

Lemma 2.14. The (i, j) element in Ak is the sum of all paths from i to j. That is,
X

ai,i2 ai2 ,i3 . . . aik ,j
Ak i,j =
1≤i2 ,...,ik ≤n

Proof. By induction on k, where the case k = 1 is clear. If the assertion is true for some k, then
Ak+1



i,j

=

n
X
ℓ=1

ai,ℓ Akℓ,j =

n
X

X

ai,ℓ aℓ,i2 ai2 ,i3 . . . aik ,j =

j=1 1≤i2 ,...,ik ≤n

X

ai,i2 ai2 ,i3 . . . aik+1 ,j

1≤i2 ,...,ik+1 ≤n


Lemma 2.15. The coefficient of λn−k in pA (λ) is
X
X
k
[−1]0
[sgnσ]0 a
i1 ,iσ(1) ai2 ,iσ(2) . . . aik ,iσ(k)
1≤i1 ,...,ik ≤n σ∈Sk


Proof. We must choose n − k indices from which we “take” λ in the expansion of det λI + [−1]0A ;
we are left with a k × k submatrix, with rows i1 , . . . , ik from A. Its determinant is the inner sum. 
Lemma 2.16. Any multicycle contributing to the dominant characteristic coefficient must be a
simple cycle.
Proof. Otherwise, assume it is not a simple cycle. Since it can be written as a product of simple
(s)
≥ etr (A), and a shorter length. Thus, s would give
cycles, at least one of which, s, would have τ|s|
a dominant characteristic coefficient of lower degree, in contradiction to our assumption.

Lemma 2.17. If s (etr (A + B)) 6= 0, then etr (A + B) = etr (A) + etr (B).
Proof. The assumption can only happen if [−1]0tr (A + B) λn−1 is essential in pA+B (λ), and etr (A + B) =
tr (A + B).
The multicycles of A + B are products of sums of elements from A and from B. In particular,
every multicycle of A and of B is a part of a multicycle of A + B.
We know that tr (A + B) = tr (A) + tr (B); if τ (tr (A + B)) = τ (tr (A)), then τ (tr (A)) >every
average value of a multicycle of A; so etr (A) = tr (A). We are almost finished:
Case 1.

If τ (tr (A + B)) = τ (tr (A)) = τ (tr (B)), then etr (A) = tr (A), etr (B) = tr (B), and
etr (A + B) = tr (A + B) = tr (A) + tr (B) = etr (A) + etr (B)

Case 2.

If τ (tr (A + B)) = τ (tr (A)) > τ (tr (B)), then etr (A) = tr (A), and
etr (A + B) = tr (A + B) = tr (A) + tr (B) = tr (A) = etr (A)
In particular, τ (etr (A)) > τ (etr (B)); otherwise, there would have been a multicycle from
B with τ (average value) ≥ τ (etr (A)) = τ (etr (A + B)), and thus s (etr (A + B)) = 0,
which is a contradiction. So
etr (A + B) = etr (A) = etr (A) + etr (B)


Example 2.18. In general, it is not true that
 etr (A + B)
  etr (A) + etr (B). For example, take
[1]0
[1]0
in (R (C, R))2×2 the following matrices: A =
, B = At . Then etr (A) = etr (B) = [2]0.
−∞ [1]0


[2]0 [1]0
However, A + B = [1]
, and pA+B (λ) = λ2 + [−4]0λ + [3]0. The monomial [−4]0λ is quasi0 [2]0
essential, and thus etr (A + B) = [0]0.
Lemma 2.19. etr (AB) = etr (BA).

16

GUY BLACHAR AND EREZ SHEINER

Proof. By Lemma 2.16, it is enough to check only simple cycles. Assume
(AB)i1 ,i2 (AB)i2 ,i3 . . . (AB)ik ,i1
contributes to the dominant characteristic coefficient, where ij 6= ij ′ for j 6= j ′ . So there are ℓ1 , . . . , ℓk
such that
s = ai1 ,ℓ1 bℓ1 ,i2 ai2 ,ℓ2 bℓ2 ,i3 . . . aik ,ℓk bℓk ,i1
contributes to the dominant characteristic coefficient, i.e. τ (s) = etr (AB).
If ℓj = ℓj ′ for j < j ′ , write



s =
ai1 ,ℓ1 bℓ1 ,i2 . . . aij ,ℓj bℓj ,ij′ +1 . . . aik ,ℓk bℓk ,i1 bℓj ,ij+1 aij+1 ,ℓj+1 . . . aij′ ,ℓj′ =



=
ai1 ,ℓ1 bℓ1 ,i2 . . . aij ,ℓj bℓj ,ij′ +1 . . . aik ,ℓk bℓk ,i1 aij+1 ,ℓj+1 . . . aij′ ,ℓj′ bℓj ,ij+1
{z
}|
{z
}
|
s1

s2

Since τ (s) = τ (etr (AB)), τ (s1 ) ≥ τ (etr (AB)) or τ (s2 ) ≥ τ (etr (AB)). Since s1 and s2 are shorter,
we get a contradiction.
So ℓj 6= ℓj ′ for j 6= j ′ . So
s = bℓ1 ,i2 ai2 ,ℓ2 bℓ2 ,i3 . . . aik ,ℓk bℓk ,i1 ai1 ,ℓ1
is a part of the simple cycle
(BA)ℓ1 ,ℓ2 (BA)ℓ2 ,ℓ3 . . . (BA)ℓk ,ℓ1
in BA. So every simple cycle contributing to etr (AB) also contributes to etr (BA).
By symmetry, the opposite is true as well; so etr (AB) = etr (BA).



Lemma 2.20. If there is a multicycle s = ai1 ,i2 ai2 ,i3 . . . aik ,i1 of length k ≥ 2 such that


τ tr (A)k < τ (s)

then [−1]0tr (A) λn−1 is not essential in pA (λ) (meaning, it is either inessential or quasi-essential).
In other words, µ (A) ≥ 2.
Proof. Firstly, we may assume that k ≤ n; otherwise, write s as a product of multicycle, s = s1 . . . sj .
Since
j


X
τ tr (A)k < τ (s) =
τ (sℓ )


|sℓ |



ℓ=1

< τ (sℓ ), and we may replace k by ℓ.
n
X
αi λn−i . By Lemma 2.15,
Therefore, we assume k ≤ n. Write pA (λ) = λn +

At least one sℓ should satisfy τ tr (A)

i=1

ck = ai1 ,i2 ai2 ,i3 . . . aik ,i1 + · · · = s + · · ·

In particular, τ (ck ) ≥ τ (s). Also recall that c1 = [−1]0tr (A). Therefore,


k
τ tr (A)
τ (s)
τ (ck )
τ (c1 ) = τ (tr (A)) =
<
≤
k
k
k
An thus µ (A) ≥ k ≥ 2, as required.



[−1]0tr (A) λn−1

Lemma 2.21. If A is ELT nilpotent, and if s (tr (A)) 6= 0, then
is not essential in
pA (λ). In other words, [−1]0tr (A) λn−1 is either quasi-essential or inessential in pA (λ).
Proof. For this proof, write a ≤τ b if τ (a) ≤ τ (b), a <τ b if τ (a) < τ (b), and a ≡τ b if τ (a) = τ (b).
We take some ai,i such that ai,i ≡τ tr (A) and s (ai,i ) 6= 0; without loss of generality, let i = 1.
n
X
αi λn−i .
Write pA (λ) = λn +
i=1 

By Lemma 2.14, Ak 1,1 = ak1,1 + · · · . Take k minimal such that s Ak = 0. In particular,

 
s Ak 1,1 = 0, so we have two cases:

ELT LINEAR ALGEBRA II

Case 1.

17

There is a multicycle s = a1,i2 ai2 ,i3 . . . aik ,1 with ak1,1 <τ s. Firstly, we may assume that
k ≤ n; otherwise, write s as a product of multicycle, s = s1 . . . sj . Since


τ tr (A)

k



< τ (s) =

j
X

τ (sℓ )

ℓ=1



At least one sℓ should satisfy τ tr (A)|sℓ | < τ (sℓ ), and we may replace k by ℓ.
n
X
αi λn−i . By Lemma 2.15,
Therefore, we assume k ≤ n. Write pA (λ) = λn +
i=1

ck = ai1 ,i2 ai2 ,i3 . . . aik ,i1 + · · · = s + · · ·

Case 2.

In particular, τ (ck ) ≥ τ (s). Also recall that c1 = [−1]0tr (A). Therefore,


k
τ tr (A)
τ (s)
τ (ck )
τ (c1 ) = τ (tr (A)) =
<
≤
k
k
k
An thus µ (A) ≥ k ≥ 2, as required.
There is no multicycle with ak1,1 <τ a1,i2 ai2 ,i3 . . . aik ,1 . Then there has to be a multicycle

 
for which ak1,1 ≡τ a1,i2 ai2 ,i3 . . . aik ,1 = s (since s Ak 1,1 = 0, and ak1,1 is a summand in

the sum defining Ak 1,1 ).
By writing s as a product of simple cycles, we may assume that each simple cycle
aj1 ,j2 aj2 ,j3 . . . ajℓ ,j1 ≡τ aℓ1,1 (Otherwise, we are finished by the first case).
Since ℓ < n, we get that |L (A)| ≥ 2, meaning [−1]0tr (A) λn−1 is quasi-essential in
pA (λ).


Corollary 2.22. If A is ELT nilpotent, then s (etr (A)) = 0.
Proof. There are two cases:
(1) If s (tr (A)) = 0, then s (etr (A)) = 0 by Lemma 2.11.
(2) Otherwise, s (tr (A)) 6= 0; but then s (etr (A)) = 0 by Lemma 2.21.

References
[1] Marianne Akian, Guy Cohen, Stephane Gaubert, R Nikoukhah, and Jean Pierre Quadrat. Linear systems in
(max,+) algebra. In Decision and Control, 1990., Proceedings of the 29th IEEE Conference on, pages 151–156.
IEEE, 1990.
[2] Marianne Akian, Stéphane Gaubert, and Alexander Guterman. Linear independence over tropical semirings and
beyond. Contemporary Mathematics, 495:1, 2009.
[3] Marianne Akian, Stéphane Gaubert, and Alexander Guterman. Tropical cramer determinants revisited. Tropical
and Idempotent Mathematics and Applications, 616:45, 2014.
[4] Guy Blachar and Erez Sheiner. Elt linear algebra. arXiv preprint arXiv:1603.02204, 2016.
[5] Peter Butkovič. Max-algebra: the linear algebra of combinatorics? Linear Algebra and its applications, 367:313–
335, 2003.
[6] Mike Develin, Francisco Santos, and Bernd Sturmfels. On the rank of a tropical matrix. Combinatorial and
computational geometry, 52:213–242, 2005.
[7] David Dolžan and Polona Oblak. Invertible and nilpotent matrices over antirings. arXiv preprint arXiv:0806.2996,
2008.
[8] Ido Efrat. Valuations, orderings, and Milnor K-theory. Number 124. American Mathematical Soc., 2006.
[9] Stéphane Gaubert. Théorie des systèmes linéaires dans les dioı̈des. PhD thesis, 1992.
[10] Stephane Gaubert. Methods and applications of (max,+) linear algebra. In STACS 97, pages 261–282. Springer,
1997.
[11] Zur Izhakian. Tropical arithmetic and matrix algebra. Communications in Algebra R , 37(4):1445–1468, 2009.
[12] Zur Izhakian, Manfred Knebusch, and Louis Rowen. Dual spaces and bilinear forms in supertropical linear
algebra. Linear and Multilinear Algebra, 60(7):865–883, 2012.
[13] Zur Izhakian and Louis Rowen. The tropical rank of a tropical matrix. Communications in Algebra R ,
37(11):3912–3927, 2009.
[14] Zur Izhakian and Louis Rowen. Supertropical algebra. Advances in Mathematics, 225(4):2222–2286, 2010.

18

GUY BLACHAR AND EREZ SHEINER

[15] Zur Izhakian and Louis Rowen. Supertropical matrix algebra. Israel Journal of Mathematics, 182(1):383–424,
2011.
[16] Zur Izhakian and Louis Rowen. Supertropical matrix algebra II: Solving tropical equations. Israel Journal of
Mathematics, 186(1):69–96, 2011.
[17] Zur Izhakian and Louis Rowen. Supertropical matrix algebra III: Powers of matrices and their supertropical
eigenvalues. Journal of Algebra, 341(1):125–149, 2011.
[18] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(12):83–97, 1955.
[19] Brett Parker. Exploded manifolds. Advances in Mathematics, 229(6):3256–3319, 2012.
[20] Louis Halle Rowen. Algebras with a negation map. arXiv preprint arXiv:1602.00353, 2016.
[21] Sergei Sergeev. Max-plus definite matrix closures and their eigenspaces. Linear algebra and its applications,
421(2-3):182–201, 2007.
[22] Erez Sheiner. Exploded Layered Tropical Algebra. PhD thesis, Bar-Ilan University, 2015.
[23] Yijia Tan. On invertible matrices over antirings. Linear algebra and its applications, 423(2):428–444, 2007.
[24] Jean-Pierre Tignol and R Adrian. Value functions on simple algebras, and associated graded rings. Springer,
2015.
Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel.
E-mail address: blachag@biu.ac.il
Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel.
E-mail address: erez@math.biu.ac.il

