=Paper=
{{Paper
|id=None
|storemode=property
|title=Spectral Lattices of Reducible Matrices over Completed Idempotent
Semifields
|pdfUrl=https://ceur-ws.org/Vol-1062/paper18.pdf
|volume=Vol-1062
|dblpUrl=https://dblp.org/rec/conf/cla/Valverde-AlbaceteP13
}}
==Spectral Lattices of Reducible Matrices over Completed Idempotent
Semifields==
https://ceur-ws.org/Vol-1062/paper18.pdf
Spectral Lattices of reducible matrices over
completed idempotent semifields
Francisco J. Valverde-Albacete1 and Carmen Peláez-Moreno2?
1
Departamento de Lenguajes y Sistemas Informáticos
Univ. Nacional de Educación a Distancia, c/ Juan del Rosal, 16. 28040 Madrid, Spain
fva@lsi.uned.es
2
Departamento de Teorı́a de la Señal y de las Comunicaciones
Universidad Carlos III de Madrid, 28911 Leganés, Spain
carmen@tsc.uc3m.es
Abstract. Previous work has shown a relation between L-valued ex-
tensions of FCA and the spectra of some matrices related to L-valued
contexts. We investigate the spectra of reducible matrices over completed
idempotent semifields in the framework of dioids, naturally-ordered semi-
rings, that encompass several of those extensions. Considering special
sets of eigenvectors also brings out complete lattices in the picture and
we argue that such structure may be more important than standard
eigenspace structure for matrices over completed idempotent semifields.
1 Motivation
The eigenvectors and eigenspaces over certain naturally ordered semirings called
dioids seem to be intimately related to multi-valued extensions of Formal Con-
cept Analysis [1]. For instance [2, 3] prove that formal concepts are optimal
factors for decomposing a matrix with entries in complete residuated semirings.
Notice the strong analogy to the SVD, with formal concepts taking the role of
pairs of left and right eigenvectors.
Indeed, [4] prove that, at least on a particular kind of dioids, the idempotent
semifields, formal concepts are related to the eigenvectors of the unit in the semi-
ring. This result, however, cannot be unified with the former both for theoretical
reasons, since idempotent semifields are incomplete (see below), as well as for
practical reasons, since the carrier set of idempotent semifields is almost never
included in [0, 1] .
A possible way forward is to develop these theories under the common frame-
work of the L-fuzzy sets, where L is any complete lattice [5]. Such an endeavour
has already been called for [6], although it remains unfulfilled, hence this paper
has a two-fold aim:
1. to clarify the spectral theory over completed idempotent semifields, and
?
FJVA is supported by EU FP7 project LiMoSINe (contract 288024). CPM has been
partially supported by the Spanish Government-Comisión Interministerial de Ciencia
y Tecnologı́a project TEC2011-26807 for this paper.
c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA
2013, pp. 211–224, ISBN 978–2–7466–6566–8, Laboratory L3i, University of La
Rochelle, 2013. Copying permitted only for private and academic purposes.
212 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
2. to take steps towards a common framework for the interpretation of L-
Formal Concept Analysis as a spectral construction.
First steps have been taken in this direction with the development of a spec-
tral theory of irreducible matrices [7] over complete idempotent semifields, whose
summary we include below, but the general case, here presented, shows a more
intimate relation to lattice theory.
1.1 Dioids and their spectral theory
A semiring is an algebra S = hS, ⊕, ⊗, , ei whose additive structure, hS, ⊕, i,
is a commutative monoid and whose multiplicative structure, hS\{}, ⊗, ei, is a
monoid with multiplication distributing over addition from right and left and
with additive neutral element absorbing for ⊗, i.e. ∀a ∈ S, ⊗ a = .
Let Mn (S) be the semiring of square matrices over a semiring S with the
usual operations. Given A ∈ Mn (S) the right (left) eigenproblem is the task of
finding the right eigenvectors v ∈ S n×1 and right eigenvalues ρ ∈ S (respectively
left eigenvectors u ∈ S 1×n and left eigenvalues λ ∈ S) satisfying:
u⊗A=λ⊗u A⊗v =v⊗ρ (1)
The left and right eigenspaces and spectra are the sets of these solutions:
Λ(A) = {λ ∈ S | Uλ (A) 6= {n }} P(A) = {ρ ∈ S | Vρ (A) 6= {n }}
Uλ (A) = {u ∈ S 1×n | u ⊗ A = λ ⊗ u} Vρ (A) = {v ∈ S n×1 | A ⊗ v = v ⊗ ρ}
[ [
U(A) = Uλ (A) V(A) = Vρ (A) (2)
λ∈Λ(A) ρ∈P(A)
Since Λ(A) = P(At ) and Uλ (A) = Vλ (At ) , from now on we will omit refer-
ences to left eigenvalues, eigenvectors and spectra, unless we want to emphasize
differences.
With so little structure it might seem hard to solve (1), but a very generic
solution based in the concept of transitive closure A+ and transitive-reflexive
closure A∗ of a matrix is given by the following theorem:
Theorem 1 (Gondran and Minoux, [8, Theorem 1]). Let A ∈ S n×n . If
A∗ exists, the following two conditions are equivalent:
1. A+ ∗
.i ⊗ µ = A.i ⊗ µ for some i ∈ {1 . . . n}, and µ ∈ S.
2. A.i ⊗ µ (and A∗.i ⊗ µ) is an eigenvector of A for e , A+
+
.i ⊗ µ ∈ Ve (A) .
In [7] this result was made more specific in two directions: on the one hand, by
focusing on particular types of completed idempotent semirings—semirings with
a natural order where infinite additions of elements exist so transitive closures
are guaranteed to exist and sets of generators can be found for the eigenspaces—
and, on the other hand, by considering more easily visualizable subsemimodules
than the whole eigenspace—a better choice for exploratory data analysis.
Specifically, every commutative semiring accepts a canonical preorder, a ≤ b
if and only if there exists c ∈ D with a ⊕ c = b . A dioid is a semiring D
Spectral Lattices of reducible matrices over completed idempotent semifields 213
where this relation is actually an order. Dioids are zerosumfree and entire, that
is they have no non-null additive or multiplicative factors of zero. Commutative
complete dioids are already complete residuated lattices. Similarly, semimodules
over complete commutative dioids are also complete lattices.
An idempotent semiring is a dioid whose addition is idempotent, and a se-
lective semiring one where the arguments attaining the value of the additive
operation can be identified.
Example 1. Examples of idempotent dioids are
1. The Boolean lattice B = h {0, 1}, ∨, ∧, 0, 1 i
2. All fuzzy semirings, e.g. h [0, 1], max, min, 0, 1 i
3. The min-plus algebra Rmin,+ = h R ∪ {∞}, min, +, ∞, 0 i
4. The max-plus algebra Rmax,+ = h R ∪ { −∞ }, max, +, −∞, 0 i u
t
Of the semirings above, only the boolean lattice and the fuzzy semirings are
complete dioids, since the rest lack the top element > as an adequate inverse for
the bottom in the order.
The second important feature of spectra over complete dioids, as proven in
[7], is that the set of eigenvalues on complete dioids is extended with respect to
the incomplete case, and it makes sense to distinguish those which are associated
to finite eigenvectors, the proper eigenvalues Pp(A), and those associated with
non-finite eigenvectors, the improper eigenvalues P(A)\Pp(A).
Moreover, as said above, the eigenspaces of matrices over complete dioids
have the structure of a complete lattice. But since these lattices may be contin-
uous and difficult to represent we introduce the more easily-represented eigen-
lattices Lρ (A) and Lλ (A), complete finite sublattices of the eigenspaces to be
used as scaffolding in visual representations.
1.2 Completed idempotent semifields and their spectral theory
A semiring is a semifield if there exists a multiplicative inverse for every element
a ∈ S, notated as a−1 , and radicable if the equation ab = c can be solved for
a. As exemplified above, idempotent semifields are incomplete in their natural
order. Luckily, there are procedures for completing such structures [9] and we
will not differentiate between complete or completed structures,
Example 2. The maxplus Rmax,+ and minplus Rmin,+ semifields can be com-
pleted as,
1. the completed Minplus semifield, Rmin,+ = hR ∪ {−∞, ∞}, min, +, −·, ∞, 0i .
2. the completed Maxplus semifield, Rmax,+ = hR∪{−∞, ∞}, max, +, −·, −∞, 0i ,
In this notation we have ∀c, −∞ + c = −∞ and ∞ + c = ∞, which solves several
issues in dealing with the separately completed dioids. These two completions
−1
are inverses Rmin,+ = Rmax,+ , hence order-dual lattices. Indeed they are better
min,+
jointly called the max-min-plus semiring Rmax,+ . t
u
214 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
In fact, idempotent semifields K = hK, ⊕, ⊕, ⊗, ⊗, ·−1 , ⊥, e, >i , appear as
enriched structures, the advantage of working with them being that meets can
be expressed by means of joins and inversion as a ∧ b = (a−1 ⊕ b−1 )−1 . On a
practical note, residuation in complete commutative idempotent semifields can
be expressed in terms of inverses, and this extends to eigenspaces.
Given A ∈ Mn (S), the network (weighted digraph) induced by A, NA =
(VA , EA , wA ), consists of a set of vertices VA = n̄, a set of arcs , EA = {(i, j) |
Aij 6= S }, and a weight wA : VA × VA → S, (i, j) 7→ wA (i, j) = aij . This allows
us to apply intuitively all notions from networks to matrices and vice versa, like
+
the underlying graph GA = (VA , EA ), the set of paths ΠA (i, j) between nodes
+
i and j or the set of cycles CA . Matrix A is irreducible if every node of VA is
connected to every other node in VA though a path, otherwise it is reducible.
We will use the spectra of irreducible matrices as a basic block for that of re-
+ +
ducible matrices: if CA is the set of cycles of A then µ⊕ (A) = ⊕{µ⊕ (c) | c ∈ CA }
+
+ −1
is their aggregate cycle mean. For finite µ⊕ (A), let à = (A ⊗ µ⊕ (A) ) be
the normalized transitive closure of A, and define the set of (right) fundamental
+ +
eigenvectors of irreducible A for ρ as FEVρ(A) = {Ã ·i | Ã ii = e} , with left
t
fundamental eigenvectors FEVρ(At ) = FEVρ(A) . Then,
Theorem 2 ((Right) spectral theory for irreducible matrices, [7]). Let
A ∈ Mn (K) be an irreducible matrix over a complete commutative selective
radicable semifield. Then:
1. Λ(A) = K\{⊥} = P(A) .
2. Λp(A) = {µ⊕ (A)} = Pp(A) .
3. If ρ ∈ P(A)\Pp(A), then Vρ (A) = {⊥n , >n } = Lρ (A) .
4. If ρ = µ⊕ (A) < >, then Vρ (A) = hFEVρ(A)iK ⊃ Lρ (A) = hFEVρ(A)i3 .
In this paper we try and find analogue results to Theorem 2 for the reducible
case. First, we completely describe the spectra with Theorem 3 in Section 3.1.
Then, we provide in Section 3.2 a bottom-up construction of the eigenspaces
of certain reducible matrices from that of their irreducible blocks, using from
Section 2.2 a recursive scheme to render matrices over idempotent semifields
into specialised Upper Frobenius Normal Forms (UFNF). Finally, we discuss
our findings in Section 4 and relate them to previous approaches.
2 Preliminaries
2.1 Some partial orders and lattices
In this paper we assume familiarity with basic order notions as described in
[1, 10]. We only introduce notation when departing from there.
Recall that every set V with |V | = n elements and a total order ≤ ⊆ V × V
is isomorphic to a lattice called the chain of n elements, hV, ≤i ∼
= n . When the
relation is the empty order relation ∅ ∈ V × V , it is called an anti-chain of n
elements, hV, ∅i ∼= n . Lattice 1 ∼= 1 is the vacuously-ordered singleton. Lattice
Spectral Lattices of reducible matrices over completed idempotent semifields 215
2 is the boolean lattice isomorphic to chain 2. Lattice 3 is a lattice lying at the
heart of completed semifields, the 3-bounded lattice-ordered group ⊥ < e < >,
isomorphic to chain 3.
If set of order ideals of a poset P is O(P ), then
Proposition 1 ( [10, Chap. 1]). Let hP, ≤i be a finite poset. Then hO(P ), ⊆i
is a lattice obtained by the embedding ϕ : P → O(P ), ϕ(x) =↓ x , with ∀A1 , A2 ∈
O(P ), A1 ∨ A2 = A1 ∪ A2 and A1 ∧ A2 = A1 ∩ A2 .
Note that x ≤ y in P if and only if ↓ x ⊆↓ y in O(P ). Furthermore, O(P ) can be
obtained systematically from the ordered set in a number of cases:
Proposition 2 ( [10, Chap. 1]). Let hP, ≤i be a finite poset. Then
1. O(P ⊕ 1) ∼= O(P ) ⊕ 1 and O(1 ⊕ P ) ∼
= 1 ⊕ O(P ) .
2. O(P1 ] P2 ) ∼
= O(P1 ) × O(P2 ) .
3. O(P d ) ∼
= F(P ) ∼
= O(P )d .
∼ ∼
4. O(n) = n ⊕ 1 = 1 ⊕ n .
5. O(n) ∼= 2n .
2.2 An inductive structure for reducible matrices
Recall that a digraph (or directed graph), is a pair G = (V, E) with V a set of
vertices and E ⊆ V × V a set of arcs (directed edges), ordered pairs of vertices,
such that for every i, j ∈ V there is at most one arc (i, j) ∈ E . If (i, j) ∈ E then
we say that “i is a predecessor of j” or “j is a successor of i”, and E ∈ Mn (B)
is the associated relation of G. If there is a walk from a vertex i to a vertex j
in G we say that “i has access to j” or j is reachable from i, i j . Hence,
reachability is the transitive closure of the associated relation, = E + [11].
However, vertices j ∈ V with no incoming or outgoing arcs cannot be part of
any cycle, hence j 6 j for such nodes, so it is not reflexive, in general. ( ∩IV )
is the reflexive restriction of , that is, the biggest reflexive relation included
in it.
If there is a walk from a vertex i to vertex j in G or viceversa we say that
i and j are connected, i j∨j i. Connectivity is the symmetric closure
of the reachability relation: its transitive, reflexive restriction is an equivalence
relation on VG whose classes are called the (dis)connected components of G .
Note that each of the (outwards) disconnected components is actually (inwards)
connected. Let K ≥ 1 be the number of disconnected components of G. Then
V and E are partitioned into the S subsets of vertices {Vk }K K
S {Ek }k=1
k=1 and arcs
of each disconnected component k Vk = V , Vk ∩ Vl = ∅, k 6= l, k Ek = E,
Ek ∩ El = ∅, k 6= l and we may write G = ]K k=1 Gk is a disjoint union of graphs.
G is called connected itself if K = 1 .
On the other hand, since reachability is transitive by construction, its sym-
metric, reflexive restriction i ! j ⇔ i j ∧j i is a refinement of connectiv-
ity called strong connectivity. Its equivalence classes are the strongly connected
components of G . For each disconnected component Gk , let Rk be the number of
its strongly connected components. If Rk = 1 then the k-th component is strongly
216 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
connected, otherwise just connected and composed of a number of strongly con-
nected components itself. G is strongly connected itself if K = R = 1 .
Given a digraph G = (V, E), the reduced or condensation digraph, G = (V , E)
is induced by the set V = V / ! of strongly connected components, and C, C 0 ∈
V , (C, C 0 ) ∈ E iff there exists one arc (i, j) ∈ E for some i ∈ C, j ∈ C 0 and we
say that component C has access to C 0 , and write C 4 C 0 . It is well known
that G = (V , E) is a partially ordered set called a directed acyclic graph (dag).
Given a matrix A ∈ Mn (S), its condensation digraph is the partial order of
strong connectivity classes GA = (V A , E A ), as in Figure 2b in Example 4, of its
associated digraph GA = (VA , EA ) . This can be proven by means of an Upper
Frobenius Normal Form (UFNF) [12], a structure for matrices that we intend to
specialise and use as a scheme for structural induction over reducible matrices.
In the following, for a set of indices Vx ⊆ n we write P (Vx ) for a permutation
of it, and Exy is an empty matrix of conformal dimension most of the times
represented on matrix patterns as elliptical dots.
Lemma 1 (Recursive Upper Frobenius Normal Form, UFNF). Let A ∈
Mn (S) be a matrix over a semiring and GA its condensation digraph. Then,
1. (UFNF3 ) If A has zero lines it can be transformed by a simultaneous row
and column permutation of VA into the following form:
Eιι · · ·
· Eαα Aαβ Aαω
P3t ⊗ A ⊗ P3 = · · Aββ Aβω
(3)
· · · Eωω
where: either Aαβ or Aαω or both are non-zero, and either Aαω or Aβω or
both are non-zero. Furthermore, P3 is obtained concatenating permutations
for the indices of simultaneously zero columns and rows Vι , the indices of
zero columns but non-zero rows Vα , the indices of zero rows but non-zero
columns Vω and the rest Vβ as P3 = P (Vι )P (Vα )P (Vβ )P (Vω ) .
2. (UFNF2 ) If A has no zero lines it can be transformed by a simultaneous row
and column permutation P2 = P (A1 ) . . . P (Ak ) into block diagonal UFNF
A1 · . . . ·
· A2 . . . ·
P2t ⊗ A ⊗ P2 = . . . . (4)
.. .. . . ..
· · . . . AK
where {Ak }Kk=1 , K ≥ 1 are the matrices of connected components of GA .
3. (UFNF1 ) If A is reducible with no zero lines and a single connected compo-
nent it can be simultaneously row- and column-permuted by P1 to
A11 A12 · · · A1R
· A22 · · · A2R
P1t ⊗ A ⊗ P1 = . .. . . . (5)
.. . . ..
· · · · · ARR
Spectral Lattices of reducible matrices over completed idempotent semifields 217
where Arr are the matrices associated to each of its R strongly connected
components (sorted in a topological ordering), and P1 = P (A11 ) . . . P (ARR ) .
The particular choice of UFNF is clarified by the following Lemma, since the
condensation digraph will prove important later on:
Lemma 2 (Scheme for structural induction over reducible matrices).
Let A ∈ Mn (S) be a matrix over an entire zerosumfree semiring and GA its
condensation digraph. Then:
1. If A is irreducible then GA ∼
=U1 .
2. If A is in UFNF2 then GA = GAk .
3. If A is in UFNF3 then GA = GAββ .
4. GAt = (GA )d .
Note that for A in UFNF1 , GA may be any connected ordered set.
3 Results
3.1 Generic results for reducible matrices
The following lemma clarifies the order relation between eigenvectors in ordered
semimodules,
Lemma 3. Let X be a naturally-ordered semimodule.
1. Vectors with incomparable supports are incomparable.
2. If X is further complete, vectors with incomparable saturated supports are
incomparable.
Proof. Let v and w be two vectors in X . Comparability of supports lies in the ⊆
relation: if supp(v) k supp(w) then supp(v) 6⊆ supp(w) and supp(w) 6⊆ supp(v) .
C C
Therefore from supp(v) ∩ supp(w) 6= ∅ we have v(supp(v) ∩ supp(w) ) 6= ⊥
C
and w(supp(v) ∩ supp(w) ) = ⊥ , hence v 6≤ w . Similarly, from supp(w) ∩
C
supp(v) 6= ∅ we have w 6≤ v , therefore v k w . Claim 2 is likewise argued on
the support taking the role of n, and the saturated support taking the role of
the original support. t
u
Let A ∈ Mn (S) be a matrix andS GA be its condensation S digraph. Consider
a class Cr ∈ V A and call Vu = ( C 0 ∈↓Cr C 0 )\Cr , Vd = ( C 0 ∈↑Cr C 0 )\Cr and
Vp = VA \(Vu ∪ Cr ∪ Vd ) the sets of upstream, downstream and parallel vertices
for Cr , respectively. Using permutation Pr = P (Vu )P (Cr )P (Vp )P (Vd ) we may
suppose a blocked form of A(Cr ) like the one in Fig. 1 without loss of generality.
Notice that any of Vu , Vd or Vp may be empty. However, if Vu (resp. Vd ) is not
of null dimension, then Aur (resp. Ard ) cannot be empty.
Proposition 3. Let A ∈ Mn (K) be a matrix over a complete commutative
+
selective radicable semifield with CA 6= ∅. Then a scalar ρ > ⊥ is a proper
eigenvalue of A if and only if there is at least one class in its condensation
digraph Cr ∈ GA such that ρ = µ⊕ (Arr ) .
218 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
Vd
Ard Apd
Vr Aud Vp
Auu Aur Aup Aud
· Arr · Ard
A(Cr ) =
·
· App Apd
· · · Add Aur Aup
Vu
(a) Blocked form of A(CR ) (b) Digraph of A(CR )
Fig. 1: Matrix A focused on Cr , A(Cr ) = Pr t ⊗ A ⊗ Pr and associated digraph.
The loops at each node, consisting of (possibly empty) Auu , Arr , App , Add are
not shown.
Proof. The proof, for instance, in [8] extends even to ρ = >,. t
u
The proper spectrum is clarified by:
Lemma 4. Let A ∈ Mn (S) be a reducible matrix over a complete radicable
selective semifield. Then, there are no other finite eigenvectors in Vρ (A) con-
tributed by Ãρ than those selected by the critical circuits in Cr ∈ V A such that
µ⊕ (Arr ) = ρ ,
+
FEVf(A) = ∪Cr ∈V A {(Ãρ )·i | i ∈ Vrc , µ⊕ (Arr ) = ρ} .
Proof. If ρ = µ⊕ (Arr ), from Proposition 3 we see that the finite eigenvectors
+ ∗
mentioned really belong in Vρ (A). If ρ > µ⊕ (Arr ) then (Ãρrr )ii < e = (Ãρrr )ii
hence the columns selected by Cr do not generate eigenvectors. If ρ < µ⊕ (Arr )
+
then (Ãρrr )ij = > and whether those classes with cycle mean ρ are upstream or
downstream of Cr the only value that is propagated is >, hence the eigenvectors
are all saturated. t
u
Theorem 3 (Spectra of generic matrices). Let A ∈ Mn (D) be a reducible
matrix over an entire zerosumfree semiring. Then,
1. If CA+
= ∅ then P(A) = Pp(A) = {} .
+
2. If CA 6= ∅ and further D is a complete selective radicable semifield,
(a) If zc(A) 6= ∅ then P(A) = K and Pp(A) = {⊥}∪{µ⊕ (Arr ) | Cr ∈ V A } .
(b) If zc(A) = ∅ then P(A) = K\{⊥} and Pp(A) = {µ⊕ (Arr ) | Cr ∈ V A } .
Proof. First, call zc(A) the set of empty columns of A. If GA has no cycles
+ +
CA = ∅, claim 1 follows from a result in [7] . But if CA 6= ∅ then by Proposition
p
3, P (A) ⊇ {µ⊕ (Arr ) | Cr ∈ V A } and no other non-null proper eigenvalues may
exist by Lemma 4. ⊥ is only proper when zc(A) 6= ∅ hence claims 2a and 2b
follow. t
u
Spectral Lattices of reducible matrices over completed idempotent semifields 219
Translating to UFNF terms:
Corollary 1. Let A ∈ Mn (K) be a matrix over a complete selective radicable
semifield with CA +
6= ∅. Then P(A) = K\{⊥} and Pp(A) = {µ⊕ (Arr ) | Cr ∈
V A }, unless A is in UFNF3 and zc(A) 6= ∅ whence ⊥ ∈ Pp(A) ⊆ P(A) too.
Proof. If A is irreducible or in UFNF1 or UFNF2 it has no empty columns or
rows. This can only happen in UFNF3 in which case the result follows from
Theorem 3. t
u
Since this solves entirely the description of the spectrum, only the description
of the eigenspaces is left pending.
3.2 Eigenspaces of matrices in UFNF1
In this section we offer an instance of how the UFNF can be used to obtain,
inductively, the spectrum of reducible matrices.
If for every parallel condensation class Cp ⊆ VA in A(Cr ) illustrated in Cr
of Fig. 1 Aup 6= Eup or Apd 6= Epd or both, then A is in UFNF1 with a single
connected block. In this case, we can relate the order of the eigenvectors to the
condensation digraph: define the support of a class supp(C) as the support of
any of the non-null eigenvectors it induces in A.
Lemma 5. Let A ∈ Mn (S) be a matrix in UFNF1 over S a complete zerosumfree
semiring. Then, for any class Cr ∈ V A , supp(Cr ) = {Clr | Clr ∈ ↓ Cr } .
Proof. Since Arr is irreducible, if ρ = µ⊕ (Arr ) then for any vr ∈ Vρ (Arr ) we
have that supp(vr ) = Vr , hence Vr ⊆ supp(Cr ) . Also, since S is complete and
+ +
zerosumfree (Ãρ )rr exists and is full [7]. Since (Ãρ )uu Ãρur must have a full column
for any Clr ∈↓ Cr meaning precisely that Cr is downstream from Clr , the product
+ +
(Ãρ )uu Ãρur (Ãρ )rr for the nodes in Clr is non-null and Vlr ⊆ supp(Cr ) . t
u
Lemma 5 establishes a bijection between the supports of condensation classes
and downsets in GA which is actually an isomorphism of orders,
Proposition 4. Let A ∈ Mn (K) be a matrix over a commutative complete
selective radicable semifield admitting an UFNF1 . Then
1. Each class Cr ∈ V A generates a distinct saturated eigenvector, vr> .
2. {vr> | Cr ∈ V A } ∼
= GA .
Proof. Let v ∈ Vρ (A) where ρ = µ⊕ (Arr ) then by Lemma 5 supp(v) =↓ Cr , hence
vr> = >v ∈ Vρ (A) is the unique saturated eigenvector, since sat-supp (>v) =
supp(>v) = supp(C), and the bijection follows. By Lemma 3, claim 2 the order
relation between classes is maintained between eigenvectors, whence the order
isomorphism in claim 2. tu
220 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
We call FEV1,>(A) = {vr> | Cr ∈ V A } the set of of saturated fundamental
d
eigenvectors of A. Notice that V At = V A but E At = E A , so FEV1,>(At ) ∼ =
d
GA .
+
For every finite ρ ∈ Pp(A) we define the critical nodes Vρc = {i ∈ n | (Ãρ )ii =
+
e} and FEV1,f ρ c
ρ (A) = {(Ã )·i | i ∈ Vρ } the (maybe partially) finite fundamental
eigenvectors of ρ. Next, let δρ (ρ ) = e if ρ0 = ρ and δρ−1 (ρ0 ) = > otherwise. for
−1 0
ρ ∈ P(A) the set of (right) fundamental eigenvectors of A in UFNF1 for ρ as
FEV1ρ (A) = ∪ρ0 ∈P(A) {δρ−1 (ρ0 ) ⊗ FEV1,f
ρ0 (A)} . (6)
This definition absorbs two cases, actually,
Lemma 6. Let A ∈ Mn (K) be a matrix over a commutative complete selective
radicable semifield admitting an UFNF1 . Then,
1. for ρ ∈ P(A)\Pp(A) , FEV1ρ (A) = FEV1,>(A) .
2. for ρ ∈ Pp(A), ρ 6= >, FEV1ρ (A) = FEV1,f
ρ (A)∪FEV
1,>
(A) \(> ⊗ FEV1,f
ρ (A)) .
3. for ρ ∈ P(A), ρ 6= >, FEV1,>(A) = > ⊗ FEV1ρ (A).
p 0
Proof. If ρ ∈ P(A)\P (A), then for all ρ ∈ K, δρ−1 (ρ0 ) = >. By Proposition 4
claim 1 follows as we range ρ0 ∈ Pp(A) . Similarly, when ρ ∈ Pp(A), those classes
whose ρ0 6= ρ supply a single saturated eigenvector. However, if ρ0 = ρ, then
δρ−1 (ρ0 ) = e obtains the (partially) finite fundamental eigenvectors FEV1,f
ρ (A),
the saturated eigenvectors of which cannot be considered fundamental, since
they can be obtained from FEV1,f 1
ρ0 (A) linearly, and will not appear in FEVρ (A).
Claim 3 is a corollary of the other two. t
u
Call V >(A) = hFEV1,>(A)iK the saturated eigenspace of A , then
Corollary 2. Let A ∈ Mn (K) be a matrix over a commutative complete selec-
tive radicable semifield admitting an UFNF1 . Then,
1. For ρ ∈ P(A), V >(A) ⊆ Vρ (A) .
2. For ρ ∈ P(A)\Pp(A), furthermore,V >(A) = Vρ (A) .
Proof. Since we have FEV1,>(A) ⊆ Vρ (A), then V >(A) ⊆ Vρ (A) . For ρ ∈
P(A)\Pp(A), FEV1ρ (A) = FEV1,>(A) by Lemma 6, so claim 2 follows. t
u
Hence, V >(A) provides a common “scaffolding” for every eigenspace, while the
peculiarities for proper eigenvalues are due to the finite eigenvectors. Also, since
V >(A) is a complete lattice, FEV1,>(A) ⊆ V >(A) is actually a lattice embedding,
Proposition 5. Let A ∈ Mn (K) be a matrix over a commutative complete
selective radicable semifield admitting an UFNF1 . Then
1. For ρ ∈ P(A)\Pp(A),
t
U >(A) = hFEV1,>(At ) i3 ∼
= F(GA ) V >(A) = hFEV1,>(A)i3 ∼
= O(GA ) .
(7)
Spectral Lattices of reducible matrices over completed idempotent semifields 221
2. for all ρ ∈ Pp(A), ρ < >
t
Uλ (A) = hFEV1λ (At ) iK Vρ (A) = hFEV1ρ (A)iK .
Proof. If vr> ∈ FEV1,>(A) then λvr> = λ(>vr> ) = vr> , whence V >(A) = hFEV1,>(A)i3 .
In fact, the generation process may proceed on only a subsemiring of K which
need not even be complete. For instance, we may use any of the isomorphic
copies of 2 embedded in K, for instance {⊥, k} ∼= 2, with k 6= ⊥ .
Since the number of saturated eigenvectors is finite, being identical to the
number of condensation classes, we only have to worry about binary joins and
−1
> > > > > > > > > −1 > −1
meets. Recall that vr ∨vk = vr ⊕ vk and vr ∧vk = vr ⊕ vk = (vr ) ⊕(vk ) .
Then supp(vr> ⊕ vk> ) = supp(vr> ) ∪ supp(vk> ) and also
c
supp(vr> ⊕ vk> ) = suppc vr> ∪ suppc vk> = supp(vr> ) ∩ supp(vk> )
for Cr , Ck ∈ V A and Proposition 1 gives the result. For ρ ∈ Pp(A), FEV1ρ (A) ⊆
Vρ (A) implies that hFEV1ρ (A)iK ⊆ Vρ (A), and Corollary 4 ensures that no finite
vectors are missing. And dually for left eigenspaces. t
u
This actually proves that FEV1ρ (A) is join-dense in Vρ (A).
As already mentioned, Vρ (A) is a hard-to-visualize semimodule. An eigen-
space schematics is a modified order diagram where the saturated eigenspace is
+
represented in full but the rays generated by finite eigenvalues {κ ⊗ (Ãρ )·i | i ∈
Vrc , ρ = µ⊕ (Arr )} are drawn with discontinuous lines, as in the examples below.
We are now introducing another representation inspired by (7): we define the
(left) right eigenlattices of A for (λ ∈ Λ(A)) ρ ∈ P(A) as
t
Lλ (A) = hFEV1ρ (At ) i3 Lρ (A) = hFEV1ρ (A)i3 .
Example 3 (Spectral lattices of irreducible matrices). Since irreducible matri-
ces are in UFNF1 with a single class, FEV0µ⊕(A) (A) = FEV1µ⊕(A) (A). For ρ ∈
P(A)\Pp(A) we have FEV0,>(A) = {>n }, whence GA ∼ = 1 and V >(A) = {⊥n , >n } ∼
=
p
2. For ρ ∈ P (A), ρ < >, as proven in [7], Vρ (A) is finitely generable from
FEV0ρ (A), but the form of the eigenspace and eigenlattice for Λp(A) = {µ⊕ (A)} =
Pp(A) depends on the critical cycles and the eigenvectors they induce. t
u
Example 4. Consider the matrix A ∈ Mn (Rmax,+ ) from [13, p. 25.7, example
2] in UFNF1 depicted in Fig. 2.(a). The condensed graph GA in Fig. 2.(b) has
for vertex set V A = {C1 = {1}, C2 = {2, 3, 4}, C3 = {5, 6, 7}, C4 = {8}} , so
consider the strongly connected components GAkk = (Ck , E ∩ Ck × Ck ), 1 ≤ k ≤
4. Their maximal cycle means are µk = µ⊕ (Akk ) : µ1 = 0, µ2 = 2, µ3 = 1 and
µ4 = −3 , respectively, corresponding to critical circuits: C c (GA11 ) = {1 } ,
C c (GA22 ) = {2 → 3 → 2} , C c (GA33 ) = {5 , 6 → 7 → 6} , C c (GA44 ) = {8 } .
222 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
C4
8
10
C2 −3 23
0
4 C3
0 · 0 · 7 · · · 0
· · 3 0 · · · ·
2
2
6 7
· 1 · · · · · · 3 2
· 2 · · · · · 10 1
A3 =
· · · · 1 0 · ·
1
3
0
5
−1
· · · · · · 0 · C1
0 7
· · · · −1 2 · 23 1
· · · · · · · −3 0
(a) A reducible matrix in UFNF1 (b) Class diagram (rectangles) overlaid on
GA3
1 2 3 5 6 7 8
0 −3 −2 6 5 4 >
1 0 > > > > > > > · 0 1 · · · >
2 · >
· 0 1 −2 · · · 6 −1 0 · · ·
3 · −1 0 −3 · · · 5 · 0 1 · · · >
5 · · · · 0 −1 −2 20 · · · 0 −1 −2 >
6 · · · · −3 0 −1 21
· · · −3 0 −1 >
7 · · · · −2 1 0 22 · · · −2 1 0 >
8 · · · · · · · 0 · · · · · · 0
(c) Left fundamental eigenvectors (d) Right fundamental eigenvectors
>v8 ≡ >8 >v8 ≡ >8 >v8 ≡ >8
v8
>v2 ⊕ >v5 >v2 ⊕ >v5 >v2 ⊕ >v5
>v2 >v5 >v2 >v5 >v2 >v5
v3 v3 >v1 v6
>v1 >v1 v5
v2 v2 v7
v1
⊥8 ⊥8 ⊥8
(e) V >(A3 ) (f) Schematics of V2 (A3 ) (g) Schematics of V(A3 )
Fig. 2: Matrix A3 (a), its associated digraph and class diagram (b), its left (c)
and right (d) fundamental eigenvectors annotated with their eigennodes to the
left and above, respectively; the eigenspace of improper eigenvectors V >(A3 ) in
(e), a schematic of the right eigenspace of proper eigenvalue ρ = 2, V2 (A3 ) in (f)
and the schematics of the whole right eigenspace V(A3 ) in (g).
Spectral Lattices of reducible matrices over completed idempotent semifields 223
Note that node 4 does not generate an eigenvector in either spectrum, since it
does not belong to a critical cycle.
Therefore Λp(A3 ) = Pp(A3 ) = {2, 1, 0, −3} each left eigenspace is the span
of the set of eigenvectors chosen from distinct critical cycles for each class of
+ + +
A: Uµ1 (A) = h(Ã3 µ1 )1· i , Uµ2 (A) = h(Ã3 µ2 )2· i , Uµ3 (A) = h(Ã3 µ3 ){5,6}· i , and
+
Uµ4 (A) = h(Ã3 µ4 )8· i –as described by the row vectors of Fig. 2.(c)–and the
+ +
right eigenspaces are Vµ1 (A) = h(Ã3 µ1 )·1 i , Vµ2 (A) = h(Ã3 µ2 )·2 i , Vµ3 (A) =
+ +
h(Ã3 µ3 )·{5,6} i , and Vµ4 (A) = h(Ã3 µ4 )·8 i –as described by the column vectors of
Fig. 2.(d).
The saturated eigenspace is easily represented by means of an order diagram–
Hasse diagram–as that of Fig. 2.(e). Note how it is embedded in that of any
proper eigenvalue like ρ = 2 in Fig. 2.(f). Since the representation of continuous
eigenspaces is problematic, we draw schematics of them, as in Fig. 2.(f). Fig. 2.(g)
shows a schematic view of the union of the eigenspaces for proper eigenvalues
V(A3 ) = ∪ρ∈Pp(A) Vρ (A3 ) . t
u
4 Discussion
In this paper, we have discussed the spectrum of reducible matrices with entries
in completed idempotent semifields. To the extent of our knowledge, this was
pioneered in [14] and both [7] and this paper can be understood as systematic
explorations to try and understand what was stated in there. For this purpose,
the consideration of particular UFNF forms for the matrices has been crucial:
while the description in [14] is combinatorial ours is constructive.
The usual notion of spectrum as the set of eigenvectors with more than one
(null) eigenvector appears in this context as too weak: when a matrix has at
least one cycle then all the values in the semifield (except the bottom ⊥) belong
to the spectrum. If the matrix has at least one empty column (resp. empty row)
and a cycle then all of the semifield is the spectrum. Rather than redefine the
notion of spectrum we have decided to introduce the proper spectrum as the set
of eigenvalues with at least one vector with finite support.
Regarding the eigenspaces, we found not only that they are complete con-
tinuous lattices for proper eigenvalues, but also that they are finite (complete)
lattices for improper eigenvalues. Looking for a device to represent the informa-
tion within each proper eigenspace we focus on the fundamental eigenvectors of
an irreducible matrix for each eigenvalue: those with unit values in certain of
their coordinates. The span of those eigenvectors by the action of the 3-bounded
lattice-ordered group generates the finite eigenlattices. Interestingly, since im-
proper eigenvectors only have non-finite coordinates, their span by the 3-blog is
exactly the same finite lattice as their span by the whole semifield itself.
With these building blocks it is easy to build finite lattices for reducible
matrices of any UFNF description, as exemplified above. We believe this will
224 Francisco José Valverde-Albacete and Carmen Peláez-Moreno
be a useful technique to understand and visualize the concept lattices of formal
contexts with entries in an idempotent semifield and other dioids.
Bibliography
[1] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer, Berlin, Heidelberg (1999)
[2] Belohlavek, R., Vychodil, V.: Discovery of optimal factors in binary data
via a novel method of matrix decomposition. Journal Of Computer And
System Sciences 76(1) (2010) 3–20
[3] Belohlavek, R.: Optimal decompositions of matrices with entries from resid-
uated lattices. Journal Of Logic And Computation 22(6) (November 2012)
1405–1425
[4] Valverde-Albacete, F.J., Pelaez-Moreno, C.: Spectral lattices of (Rmax,+ )-
formal contexts. In: Formal Concept Analysis. Volume LCNS 4933. (2008)
124–139
[5] Goguen, J.A.: L-fuzzy sets. J. Math. Anal. Appl 18(1) (1967) 145–174
[6] Gondran, M., Minoux, M.: Dioids and semirings: links to fuzzy set and
other applications. Fuzzy Sets And Systems 158(1273–1294) (April 2007)
[7] Valverde-Albacete, F.J., Peláez-Moreno, C.: The spectra of irreducible ma-
trices over completed commutative idempotent semifields. In preparation
(2013)
[8] Gondran, M., Minoux, M.: Valeurs propres et vecteurs propres dans les
dioı̈des et leur interprétation en théorie des graphes. EDF, Bulletin de la
Direction des Etudes et Recherches, Serie C, Mathématiques Informatique
2 (1977) 25–41
[9] Valverde-Albacete, F.J., Pelaez-Moreno, C.: Extending conceptualisation
modes for generalised Formal Concept Analysis. Information Sciences 181
(May 2011) 1888–1909
[10] Davey, B., Priestley, H.: Introduction to lattices and order. 2nd edn. Cam-
bridge University Press, Cambridge, UK (2002)
[11] Schmidt, G., Ströhlein, T.: Relations and Graphs. Discrete Mathematics
for Computer Scientists. Springer (1993)
[12] Brualdi, R.A., Ryser, H.J.: Combinatorial Matrix Theory. Volume 39 of
Encyclopedia of Mathematics and its Applications. Cambridge University
Press (1991)
[13] Akian, M., Bapat, R., Gaubert, S.: 25. [15] 25–1–25–17
[14] Jun, M., Yan, G., zhi Yong, D.: The eigen-problem in the completely max-
algebra. In: Proceedings of the Sixth International Conference on Parallel
and Distributed Computing. (2005)
[15] Hogben, L., ed.: Handbook of Linear Algebra. Discrete Mathematics and
Its Applications. Chapman & Hall/CRC (2007)