Previous work has shown a relation between L-valued extensions 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 semirings, 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.
dioids seem to be intimately related to multi-valued extensions of Formal
Concept Analysis [
semifields, formal concepts are related to the eigenvectors of the unit in the
semiring. 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 [
A possible way forward is to develop these theories under the common
framework of the L-fuzzy sets, where L is any complete lattice [
? FJVA is supported by EU FP7 project LiMoSINe (contract 288024). CPM has been partially supported by the Spanish Government-Comisi´on 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.
Formal Concept Analysis as a spectral construction.
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 = .
usual operations. Given A ∈ Mn(S) the right (left) eigenproblem is the task of finding the right eigenvectors v ∈ Sn×1 and right eigenvalues ρ ∈ S (respectively left eigenvectors u ∈ S1×n and left eigenvalues λ ∈ S) satisfying: u ⊗ A = λ ⊗ u
A ⊗ v = v ⊗ ρ
Λ(A) = {λ ∈ S | Uλ(A) 6= { n}} Uλ(A) = {u ∈ S1×n | u ⊗ A = λ ⊗ u} U (A) =
[ λ∈Λ(A)
Uλ(A)
V(A) = P(A) = {ρ ∈ S | Vρ(A) 6= { n}} Vρ(A) = {v ∈ Sn×1 | A ⊗ v = v ⊗ ρ} [
Vρ(A) ρ∈P(A) Since Λ(A) = P(At) and Uλ(A) = Vλ(At) , from now on we will omit references to left eigenvalues, eigenvectors and spectra, unless we want to emphasize differences.
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 ∈ Sn×n. If A∗ exists, the following two conditions are equivalent: 12.. AA..++ii ⊗⊗ μμ =(anAd.∗i A⊗.∗iμ⊗foμr) siosmaen iei∈ge{n1v.e.c.tonr},oafnAd fμor∈eS,. A.+i ⊗ μ ∈ Ve(A) .
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.
if and only if there exists c ∈ D with a ⊕ c = b . A dioid is a semiring D (1) (2) 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.
1. The Boolean lattice B = h {0, 1}, ∨, ∧, 0, 1 i
2. All fuzzy semirings, e.g. h [
complete dioids, since the rest lack the top element > as an adequate inverse for
non-finite eigenvectors, the improper eigenvalues P(A)\Pp(A).
[
have the structure of a complete lattice. But since these lattices may be continuous and difficult to represent we introduce the more easily-represented eigenused as scaffolding in visual representations. lattices Lρ(A) and Lλ(A), complete finite sublattices of the eigenspaces to be 1.2
Completed idempotent semifields and their spectral theory tu tu
a ∈ S, notated as a−1, and radicable if the equation a
b = 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 [
pleted as, 1. the completed Minplus semifield, Rmin,+ = hR ∪ {−∞, ∞}, min, +, −·, ∞, 0i . 2. the completed Maxplus semifield, Rmax,+ = hR∪{−∞, ∞}, max, +, −·, −∞, 0i , −1 In this notation we have ∀c, −∞ + c = −∞ and ∞ + c = ∞, which solves several issues in dealing with the separately completed dioids. These two completions are inverses Rmin,+ = Rmax,+, hence order-dual lattices. Indeed they are better jointly called the max-min-plus semiring Rmax,+ . min,+
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
reducible matrices: if CA+ is the set of cycles of A then μ⊕(A) = ⊕{μ⊕(c) | c ∈ CA+}
+
is their aggregate cycle mean. For finite μ⊕(A), let A˜ = (A ⊗ μ⊕(A)−1)+ be
the normalized transitive closure of A, and define the set of (right) fundamental
˜+ +
eigenvectors of irreducible A for ρ as FEVρ(A) = {A·i | A˜ii = e} , with left
fundamental eigenvectors FEVρ(At) = FEVρ(A)t . Then,
Theorem 2 ((Right) spectral theory for irreducible matrices, [
case. First, we completely describe the spectra with Theorem 3 in Section 3.1.
of certain reducible matrices from that of their irreducible blocks, using from
2 2.1
Some partial orders and lattices
[
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
heart of completed semifields, the 3-bounded lattice-ordered group ⊥ < e < >, isomorphic to chain 3.
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 .
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+ [
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.
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 .
connected. Let K ≥ 1 be the number of disconnected components of G. Then K K V and E are partitioned into the subsets of vertices {Vk}k=1 and arcs {Ek}k=1 of each disconnected component Sk Vk = V , Vk ∩ Vl = ∅, k 6= l, Sk Ek = E, K Ek ∩ El = ∅, k 6= l and we may write G = ]k=1Gk is a disjoint union of graphs. G is called connected itself if K = 1 .
metric, reflexive restriction i ! j ⇔ i j ∧ j i is a refinement of connectivity 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 connected, otherwise just connected and composed of a number of strongly connected 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, C0 ∈
say that component C has access to C0, and write C 4 C0 . It is well known that G = (V , E) is a partially ordered set called a directed acyclic graph (dag).
strong connectivity classes GA = (V A, EA), as in Figure 2b in Example 4, of its associated digraph GA = (VA, EA) . This can be proven by means of an Upper
specialise and use as a scheme for structural induction over reducible matrices.
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: 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 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 component it can be simultaneously row- and column-permuted by P1 to A1 · . . . · P t · A2 . . . · 2 ⊗ A ⊗ P2 = ... ... . . . ... 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) .
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 =∼ 1 . 2. If A is in UFNF2 then GA = U GAk . 3. If A is in UFNF3 then GA = GAββ . 4. GAt = (GA)d .
3 3.1
Generic results for reducible matrices
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.
relation: if supp(v) k supp(w) then supp(v) 6⊆ supp(w) and supp(w) 6⊆ supp(v) . Therefore from supp(v) ∩ supp(w)C 6= ∅ we have v(supp(v) ∩ supp(w)C ) 6= ⊥ and w(supp(v) ∩ supp(w)C ) = ⊥ , hence v 6≤ w . Similarly, from supp(w) ∩ supp(v)C 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. tu
a class Cr ∈ V A and call Vu = (SC0∈↓Cr C0)\Cr , Vd = (SC0∈↑Cr C0)\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.
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) . Auu Aur Aup Aud
Arr · Ard · App Apd · · Add (a) Blocked form of A(CR) Ard Vr Aur
Vd Aud
Vu (b) Digraph of A(CR)
Apd
Vp Aup Fig. 1: Matrix A focused on Cr, A(Cr) = Prt ⊗ A ⊗ Pr and associated digraph.
not shown.
Proof. The proof, for instance, in [
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) contributed by A˜ρ than those selected by the critical circuits in Cr ∈ V A such that μ⊕(Arr) = ρ ,
FEVf(A) = ∪Cr∈V A {(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 (A˜rρr)ii < e = (A˜rρr)ii hence the c+olumns selected by Cr do not generate eigenvectors. If ρ < μ⊕(Arr) then (A˜rρr)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. tu 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} .
3C,A+P=p(A∅), ⊇cla{iμm⊕1(Aforlrl)ow|Csrfr∈omVaAr}esaunldt inno[7o]th.eBruntoinf-CnAu+l l6=pr∅opthereneibgyenPvraolupeossimtioany exist by Lemma 4. ⊥ is only proper when zc(A) 6= ∅ hence claims 2a and 2b follow. tu
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.
rows. This can only happen in UFNF3 in which case the result follows from
tu
3.2
Eigenspaces of matrices in UFNF1
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 a complete zerosumfree
semiring. Then, for any class Cr ∈ V A, supp(Cr) = S{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 (A˜ρ)r+r exists and is full [
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 v> = >v ∈ Vρ(A) is the unique saturated eigenvector, since sat-supp (>v) = r 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. GdA .
We call FEV1,>(A) = {vr> | Cr ∈ V A} the set of of saturated fundamental eigenvectors of A. Notice that V At = V A but EAt = EdA , so FEV1,>(At) ∼= For every finite ρ ∈ Pp(A) we define the critical nodes Vρc = {i ∈ n | (A˜ρ)+ ii = e} and FEV1ρ,f(A) = {(A˜ρ)+
·i | i ∈ Vρc} the (maybe partially) finite fundamental eigenvectors of ρ. Next, let δ−1(ρ0) = e if ρ0 = ρ and δρ−1(ρ0) = > otherwise. for ρ ρ ∈ P(A) the set of (right) fundamental eigenvectors of A in UFNF1 for ρ as
FEV1ρ(A) = ∪ρ0∈P(A){δρ−1(ρ0) ⊗ FEV1ρ,0f(A)} .
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)∪FEV1,>(A) \(> ⊗ FEV1ρ,f(A)) . 3. for ρ ∈ P(A), ρ 6= >, FEV1,>(A) = > ⊗ FEV1ρ(A). (6) tu cPlraoimof.1Iffoρllo∈wsPa(sAw)\ePrap(nAg)e, ρt0h∈enPfpo(rAa)ll. ρS0im∈ilKar,lyδ,ρ−w1h(ρe0n) ρ=∈>Pp(A), those classes . By Proposition 4 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ρ,0f(A) linearly, and will not appear in FEV1ρ(A).
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 selective 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. tu
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),
U >(A) = hFEV1,>(At)ti3 =∼ F (GA)
V>(A) = hFEV1,>(A)i3 =∼ O(GA) .
(7) 2. for all ρ ∈ Pp(A), ρ < >
Uλ(A) = hFEV1λ(At)tiK
Vρ(A) = hFEV1ρ(A)iK .
Proof. If vr> ∈ FEV1,>(A) then λvr> = λ(>vr>) = vr>, whence V>(A) = hFEV1,>(A)i3.
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= ⊥ .
number of condensation classes, we only have to worry about binary joins and meets. Recall that vr>∨vk> = vr> ⊕ vk> and vr>∧vk> = vr> ⊕ vk> = (vr>)−1 ⊕(vk>)−1 Then supp(vr> ⊕ vk>) = supp(vr>) ∪ supp(vk>) and also −1 . supp(vr> ⊕ vk>) = suppc v> r ∪ suppc v> k c = 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. tu This actually proves that FEV1ρ(A) is join-dense in Vρ(A).
space schematics is a modified order diagram where the saturated eigenspace is represented in full but the rays generated by finite eigenvalues {κ ⊗ (A˜ρ)·+i | i ∈ Vrc, ρ = μ⊕(Arr)} are drawn with discontinuous lines, as in the examples below.
(left) right eigenlattices of A for (λ ∈ Λ(A)) ρ ∈ P(A) as
Lλ(A) = hFEV1ρ(At)ti3
Lρ(A) = hFEV1ρ(A)i3 .
Example 3 (Spectral lattices of irreducible matrices). Since irreducible
matri0 1
ces are in UFNF1 with a single class, FEVμ⊕(A)(A) = FEVμ⊕(A)(A). For ρ ∈
P(A)\Pp(A) we have FEV0,>(A) = {>n}, whence GA =∼ 1 and V>(A) = {⊥n, >n} =∼
2. For ρ ∈ Pp(A), ρ < >, as proven in [
tu
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: Cc(GA11 ) = {1 } , Cc(GA22 ) = {2 → 3 → 2} , Cc(GA33 ) = {5 , 6 → 7 → 6} , Cc(GA44 ) = {8 } . 0 · 0 · 7 · · · · · 3 0 · · · · · 1 · · · · · · A3 = · 2 · · · · · 10
· · · · 1 0 · · ·· ·· ·· ·· −·1 2· 0· 2·3
· · · · · · · −3 (a) A reducible matrix in UFNF1 1 0 > > > > > > > 2 · 0 1 −2 · · · 6 3 · −1 0 −3 · · · 5 5 · · · · 0 −1 −2 20 6 · · · · −3 0 −1 21 7 · · · · −2 1 0 22 8 · · · · · · · 0 (c) Left fundamental eigenvectors 2 0 1
C2 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).
V(A3) = ∪ρ∈Pp(A)Vρ(A3) . 4
tu
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(A˜3μ1 )1+i , Uμ2 (A) = h(A˜3μ2 )2+i , Uμ3 (A) = h(A˜3μ3 ){+5,6}·i , and · · Uμ4 (A) = h(A˜3μ4 )8+i –as described by the row vectors of Fig. 2.(c)–and the · right eig·{e5n,6s}piac,easnadreVμV4 μ(A1()A=) h=(A˜h3(μA˜43)μ·+81i)·+–1ais,dVesμc2r(iAbe)d=byh(tAh˜e3μc2o)l·+u2imn, Vvμec3t(oAr)s o=f h(A˜3μ3 )+ Fig. 2.(d).
in completed idempotent semifields. To the extent of our knowledge, this was
pioneered in [
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 continuous lattices for proper eigenvalues, but also that they are finite (complete) lattices for improper eigenvalues. Looking for a device to represent the information 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 improper 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.
be a useful technique to understand and visualize the concept lattices of formal contexts with entries in an idempotent semifield and other dioids.
Bibliography