Motivation

The eigenvectors and eigenspaces over certain naturally ordered semirings called dioids seem to be intimately related to multi-valued extensions of Formal Concept 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 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 [0, 1] .

A possible way forward is to develop these theories under the common framework 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 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 spectral 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.

Dioids and their spectral theory

A semiring is an algebra S = S, ⊕, ⊗, , e whose additive structure, S, ⊕, , is a commutative monoid and whose multiplicative structure, S\{ }, ⊗, e , 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 M n (S) be the semiring of square matrices over a semiring S with the usual operations. Given A ∈ M n (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) = { n }} P(A) = {ρ ∈ S | V ρ (A) = { n }} U λ (A) = {u ∈ S 1×n | u ⊗ A = λ ⊗ u} V ρ (A) = {v ∈ S n×1 | A ⊗ v = v ⊗ ρ} U(A) = λ∈Λ(A) U λ (A) V(A) = ρ∈P(A) V ρ (A)(2)

Since Λ(A) = P(A t ) and U λ (A) = V λ (A t ) , from now on we will omit references 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 ⊗ µ ∈ V e (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 eigenspacesand, 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 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 selective semiring one where the arguments attaining the value of the additive operation can be identified.

R max,+ = R ∪ { −∞ }, max, +, −∞, 0

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 P p (A), and those associated with non-finite eigenvectors, the improper eigenvalues P(A)\P p (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 continuous and difficult to represent we introduce the more easily-represented eigenlattices L ρ (A) and L λ (A), complete finite sublattices of the eigenspaces to be used as scaffolding in visual representations.

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 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 [9] and we will not differentiate between complete or completed structures, Example 2. The maxplus R max,+ and minplus R min,+ semifields can be completed as,

1. the completed Minplus semifield, R min,+ = R ∪ {−∞, ∞}, min, +, −•, ∞, 0 . 2. the completed Maxplus semifield, R max,+ = R∪{−∞, ∞}, max, + , −•, −∞, 0 ,

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 R min,+ = R −1 max,+ , hence order-dual lattices. Indeed they are better jointly called the max-min-plus semiring R min, + max,+ .

In fact, idempotent semifields K = K, ⊕ , ⊕, ⊗ , ⊗, • −1 , ⊥, e, , 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 ∈ M n (S), the network (weighted digraph) induced by A, N A = (V A , E A , w A ), consists of a set of vertices V A = n, a set of arcs , E A = {(i, j) | A ij = S }, and a weight w A : V A × V A → S, (i, j) → w A (i, j) = a ij . This allows us to apply intuitively all notions from networks to matrices and vice versa, like the underlying graph G A = (V A , E A ), the set of paths Π + A (i, j) between nodes i and j or the set of cycles C + A . Matrix A is irreducible if every node of V A is connected to every other node in V A 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

C + A is the set of cycles of A then µ ⊕ (A) = ⊕{µ ⊕ (c) | c ∈ C + A } is their aggregate cycle mean. For finite µ ⊕ (A), let Ã+ = (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) = { Ã+ •i | Ã+ ii = e} , with left fundamental eigenvectors FEV ρ (A t ) = FEV ρ (A) t . Then,

Theorem 2 ((Right) spectral theory for irreducible matrices, [7]). Let A ∈ M n (K) be an irreducible matrix over a complete commutative selective radicable semifield. Then:

1. Λ(A) = K\{⊥} = P(A) . 2. Λ p (A) = {µ ⊕ (A)} = P p (A) . 3. If ρ ∈ P(A)\P p (A), then V ρ (A) = {⊥ n , n } = L ρ (A) . 4. If ρ = µ ⊕ (A) < , then V ρ (A) = FEV ρ (A) K ⊃ L ρ (A) = FEV ρ (A) 3 .

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.

Preliminaries

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, V, ≤ ∼ = n . When the relation is the empty order relation ∅ ∈ V × V , it is called an anti-chain of n elements, V, ∅ ∼ = n . Lattice 1 ∼ = 1 is the vacuously-ordered singleton. Lattice 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 P, ≤ be a finite poset. Then O(P ), ⊆ is a lattice obtained by the embedding ϕ :

P → O(P ), ϕ(x) =↓ x , with ∀A 1 , A 2 ∈ O(P ), A 1 ∨ A 2 = A 1 ∪ A 2 and A 1 ∧ A 2 = A 1 ∩ A 2 .

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 P, ≤ be a finite poset. Then 1. O(P ⊕ 1) ∼ = O(P ) ⊕ 1 and O(1 ⊕ P ) ∼ = 1 ⊕ O(P ) . 2. O(P 1 P 2 ) ∼ = O(P 1 ) × O(P 2 ) . 3. O(P d ) ∼ = F(P ) ∼ = O(P ) d . 4. O(n) ∼ = n ⊕ 1 ∼ = 1 ⊕ n . 5. O(n) ∼ = 2 n .

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 ∈ M n (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 j for such nodes, so it is not reflexive, in general. ( ∩I V ) 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 V G 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 subsets of vertices {V k } K k=1 and arcs

{E k } K k=1 of each disconnected component k V k = V , V k ∩ V l = ∅, k = l, k E k = E, E k ∩ E l = ∅, k = l and we may write G = K k=1 G k 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 symmetric, 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 G k , let R k be the number of its strongly connected components. If R k = 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, C ∈ V , (C, C ) ∈ E iff there exists one arc (i, j) ∈ E for some i ∈ C, j ∈ C and we say that component C has access to C , and write C C . It is well known that G = (V , E) is a partially ordered set called a directed acyclic graph (dag).

Given a matrix A ∈ M n (S), its condensation digraph is the partial order of strong connectivity classes G A = (V A , E A ), as in Figure 2b in Example 4, of its associated digraph G A = (V A , E A ) . 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 V x ⊆ n we write P (V x ) for a permutation of it, and E xy 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 ∈ M n (S) be a matrix over a semiring and G A its condensation digraph. Then, 1. (UFNF 3 ) If A has zero lines it can be transformed by a simultaneous row and column permutation of V A into the following form:

P t 3 ⊗ A ⊗ P 3 =     E ιι • • • • E αα A αβ A αω • • A ββ A βω • • • E ωω    (3)

where: either A αβ or A αω or both are non-zero, and either A αω or A βω or both are non-zero. Furthermore, P 3 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 P 3 = P (V ι )P (V α )P (V β )P (V ω ) . 2. (UFNF 2 ) If A has no zero lines it can be transformed by a simultaneous row and column permutation P 2 = P (A 1 ) . . . P (A k ) into block diagonal UFNF

P t 2 ⊗ A ⊗ P 2 =      A 1 • . . . • • A 2 . . . • . . . . . . . . . . . . • • . . . A K     (4)

where {A k } K k=1 , K ≥ 1 are the matrices of connected components of G A .

(UFNF 1 ) If

A is reducible with no zero lines and a single connected component it can be simultaneously row-and column-permuted by P 1 to

P t 1 ⊗ A ⊗ P 1 =      A 11 A 12 • • • A 1R • A 22 • • • A 2R . . . . . . . . . . . . • • • • • A RR     (5)

where A rr are the matrices associated to each of its R strongly connected components (sorted in a topological ordering), and P 1 = P (A 11 ) . . . P (A RR ) .

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 ∈ M n (S) be a matrix over an entire zerosumfree semiring and G A its condensation digraph. Then:

1. If A is irreducible then G A ∼ = 1 . 2. If A is in UFNF 2 then G A = G A k . 3. If A is in UFNF 3 then G A = G A ββ . 4. G A t = (G A ) d .

Note that for A in UFNF 1 , G A may be any connected ordered set.

Results

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. Let A ∈ M n (S) be a matrix and G A be its condensation digraph. Consider a class C r ∈ V A and call

V u = ( C ∈↓Cr C )\C r , V d = ( C ∈↑Cr C )\C r and V p = V A \(V u ∪ C r ∪ V d )

the sets of upstream, downstream and parallel vertices for C r , respectively. Using permutation P r = P (V u )P (C r )P (V p )P (V d ) we may suppose a blocked form of A(C r ) like the one in Fig. 1 without loss of generality. Notice that any of V u , V d or V p may be empty. However, if V u (resp. V d ) is not of null dimension, then A ur (resp. A rd ) cannot be empty. Proposition 3. Let A ∈ M n (K) be a matrix over a complete commutative selective radicable semifield with C + A = ∅. Then a scalar ρ > ⊥ is a proper eigenvalue of A if and only if there is at least one class in its condensation digraph C r ∈ G A such that ρ = µ ⊕ (A rr ) .

A(Cr) =     Auu Aur Aup A ud • Arr • A rd • • App A pd • • • A dd     (a) Blocked form of A(CR) Vu Vr Vp V d Aur Aup A ud A rd A pd (b) Digraph of A(CR)

Fig. 1: Matrix A focused on C r , A(C r ) = P r t ⊗ A ⊗ P r and associated digraph. The loops at each node, consisting of (possibly empty) A uu , A rr , A pp , A dd are not shown.

Proof. The proof, for instance, in [8] extends even to ρ = ,.

The proper spectrum is clarified by: Lemma 4. Let A ∈ M n (S) be a reducible matrix over a complete radicable selective semifield. Then, there are no other finite eigenvectors in V ρ (A) contributed by Ãρ than those selected by the critical circuits in

C r ∈ V A such that µ ⊕ (A rr ) = ρ , FEV f (A) = ∪ Cr∈V A {( Ãρ ) + •i | i ∈ V c r , µ ⊕ (A rr ) = ρ} .

Proof. If ρ = µ ⊕ (A rr ), from Proposition 3 we see that the finite eigenvectors mentioned really belong in V ρ (A). If ρ > µ ⊕ (A rr ) then ( Ãρ rr )

+

ii < e = ( Ãρ rr ) * ii hence the columns selected by C r do not generate eigenvectors. If ρ < µ ⊕ (A rr ) then ( Ãρ rr )

+ ij = and whether those classes with cycle mean ρ are upstream or downstream of C r the only value that is propagated is , hence the eigenvectors are all saturated.

Theorem 3 (Spectra of generic matrices). Let A ∈ M n (D) be a reducible matrix over an entire zerosumfree semiring. Then, Proof. If A is irreducible or in UFNF 1 or UFNF 2 it has no empty columns or rows. This can only happen in UFNF 3 in which case the result follows from Theorem 3.

1. If C + A = ∅ then P(A) = P p (A) = { } . 2. If C + A = ∅ and further D is a complete selective radicable semifield, (a) If zc(A) = ∅ then P(A) = K and P p (A) = {⊥}∪{µ ⊕ (A rr ) | C r ∈ V A } . (b) If zc(A) = ∅ then P(A) = K\{⊥} and P p (A) = {µ ⊕ (A rr ) | C r ∈ V A } . Proof.

Since this solves entirely the description of the spectrum, only the description of the eigenspaces is left pending.

Eigenspaces of matrices in UFNF 1

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 C p ⊆ V A in A(C r ) illustrated in C r of Fig. 1 A up = E up or A pd = E pd or both, then A is in UFNF 1 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 ∈ M n (S) be a matrix in UFNF 1 over a complete zerosumfree semiring. Then, for any class

C r ∈ V A , supp(C r ) = {C lr | C lr ∈ ↓ C r } .

Proof. Since A rr is irreducible, if ρ = µ ⊕ (A rr ) then for any v r ∈ V ρ (A rr ) we have that supp(v r ) = V r , hence V r ⊆ supp(C r ) . Also, since S is complete and zerosumfree ( Ãρ ) + rr exists and is full [7]. Since ( Ãρ )

+ uu

Ãρ

ur must have a full column for any C lr ∈↓ C r meaning precisely that C r is downstream from C lr , the product ( Ãρ )

+ uu Ãρ ur( Ãρ )

+ rr for the nodes in C lr is non-null and V lr ⊆ supp(C r ) .

Lemma 5 establishes a bijection between the supports of condensation classes and downsets in G A which is actually an isomorphism of orders, Proposition 4. Let A ∈ M n (K) be a matrix over a commutative complete selective radicable semifield admitting an UFNF 1 . Then

1. Each class C r ∈ V A generates a distinct saturated eigenvector, v r . 2. {v r | C r ∈ V A } ∼ = G A . Proof. Let v ∈ V ρ (A) where ρ = µ ⊕ (A rr ) then by Lemma 5 supp(v) =↓ C r , hence v r = 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.

We call FEV1, (A) = {v r | C r ∈ V A } the set of of saturated fundamental eigenvectors of A. Notice that V A t = V A but E A t = E d A , so FEV 1, (A t ) ∼ = G d A .

For every finite ρ ∈ P p (A) we define the critical nodes

V c ρ = {i ∈ n | ( Ãρ ) + ii = e} and FEV 1,f ρ (A) = {( Ãρ ) + •i | i ∈ V c ρ } the (maybe partially) finite fundamental eigenvectors of ρ. Next, let δ −1 ρ (ρ ) = e if ρ = ρ and δ −1 ρ (ρ ) = otherwise. for ρ ∈ P(A) the set of (right) fundamental eigenvectors of A in UFNF 1 for ρ as FEV 1 ρ (A) = ∪ ρ ∈P(A) {δ −1 ρ (ρ ) ⊗ FEV 1,f ρ (A)} .(6)

This definition absorbs two cases, actually, Lemma 6. Let A ∈ M n (K) be a matrix over a commutative complete selective radicable semifield admitting an UFNF 1 . Then, 1. for

ρ ∈ P(A)\P p (A) , FEV 1 ρ (A) = FEV 1, (A) . 2. for ρ ∈ P p (A), ρ = , FEV 1 ρ (A) = FEV 1,f ρ (A)∪FEV 1, (A) \( ⊗ FEV 1,f ρ (A)) . 3. for ρ ∈ P(A), ρ = , FEV 1, (A) = ⊗ FEV 1 ρ (A).

Proof. If ρ ∈ P(A)\P p (A), then for all ρ ∈ K, δ −1 ρ (ρ ) = . By Proposition 4 claim 1 follows as we range ρ ∈ P p (A) . Similarly, when ρ ∈ P p (A), those classes whose ρ = ρ supply a single saturated eigenvector. However, if ρ = ρ, then δ −1 ρ (ρ ) = e obtains the (partially) finite fundamental eigenvectors FEV 1,f ρ (A), the saturated eigenvectors of which cannot be considered fundamental, since they can be obtained from FEV 1,f ρ (A) linearly, and will not appear in FEV 1 ρ (A). Claim 3 is a corollary of the other two. Call V (A) = FEV 1, (A) K the saturated eigenspace of A , then Corollary 2. Let A ∈ M n (K) be a matrix over a commutative complete selective radicable semifield admitting an UFNF 1 . Then, 1. For ρ ∈ P(A), V (A) ⊆ V ρ (A) . 2. For ρ ∈ P(A)\P p (A), furthermore,V (A) = V ρ (A) .

Proof. Since we have FEV 1, (A) ⊆ V ρ (A), then V (A) ⊆ V ρ (A) . For ρ ∈ P(A)\P p (A), FEV 1 ρ (A) = FEV 1, (A) by Lemma 6, so claim 2 follows.

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, FEV 1, (A) ⊆ V (A) is actually a lattice embedding, Proposition 5. Let A ∈ M n (K) be a matrix over a commutative complete selective radicable semifield admitting an UFNF 1 . Then 1. For ρ ∈ P(A)\P p (A),

U (A) = FEV 1, (A t ) t 2. for all ρ ∈ P p (A), ρ < U λ (A) = FEV 1 λ (A t ) t K V ρ (A) = FEV 1 ρ (A) K . Proof. If v r ∈ FEV 1, (A) then λv r = λ( v r ) = v r , whence V (A) = FEV 1, (A) 3 .

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 = ⊥ . 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

meets. Recall that v r ∨v k = v r ⊕ v k and v r ∧v k = v r ⊕ v k = (v r ) −1 ⊕ (v k ) −1 −1 . Then supp(v r ⊕ v k ) = supp(v r ) ∪ supp(v k ) and also supp(v r ⊕ v k ) = supp c v r ∪ supp c v k c = supp(v r ) ∩ supp(v k )

for C r , C k ∈ V A and Proposition 1 gives the result. For ρ ∈ P p (A), FEV 1 ρ (A) ⊆ V ρ (A) implies that FEV 1 ρ (A) K ⊆ V ρ (A), and Corollary 4 ensures that no finite vectors are missing. And dually for left eigenspaces. This actually proves that FEV 1 ρ (A) is join-dense in V ρ (A). As already mentioned, V ρ (A) is a hard-to-visualize semimodule. An eigenspace schematics is a modified order diagram where the saturated eigenspace is represented in full but the rays generated by finite eigenvalues {κ ⊗ ( Ãρ )

+ •i | i ∈ V c

r , ρ = µ ⊕ (A rr )} 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

L λ (A) = FEV 1 ρ (A t ) t 3 L ρ (A) = FEV 1 ρ (A) 3 .

Example 3 (Spectral lattices of irreducible matrices). Since irreducible matrices are in UFNF 1 with a single class, FEV 0 µ⊕(A) (A) = FEV 1 µ⊕(A) (A). For ρ ∈ P(A)\P p (A) we have FEV 0, (A) = { n }, whence G A ∼ = 1 and V (A) = {⊥ n , n } ∼ = 2. For ρ ∈ P p (A), ρ < , as proven in [7], V ρ (A) is finitely generable from FEV 0 ρ (A), but the form of the eigenspace and eigenlattice for Λ p (A) = {µ ⊕ (A)} = P p (A) depends on the critical cycles and the eigenvectors they induce. Note that node 4 does not generate an eigenvector in either spectrum, since it does not belong to a critical cycle. Therefore Λ p (A 3 ) = P p (A 3 ) = {2, 1, 0, −3} each left eigenspace is the span of the set of eigenvectors chosen from distinct critical cycles for each class of 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(A 3 ) = ∪ ρ∈P p (A) V ρ (A 3 ) .

V A = {C 1 = {1}, C 2 = {2, 3, 4}, C 3 = {5, 6, 7}, C 4 = {8}} , so consider the strongly connected components G A kk = (C k , E ∩ C k × C k ), 1 ≤ k ≤ 4. Their maximal cycle means are µ k = µ ⊕ (A kk ) : µ 1 = 0, µ 2 = 2, µ 3 = 1 and µ 4 = −3 , respectively, corresponding to critical circuits: C c (G A11 ) = {1 } , C c (G A22 ) = {2 → 3 → 2} , C c (G A33 ) = {5 , 6 → 7 → 6} , C c (G A44 ) = {8 } . A3 =             0 • 0 • 7 • • • • • 3 0 • • • • • 1 • • • • • • • 2 • • • • • 10 • • • • 1 0 • • • • • • • • 0 • • • • • −1 2 • 23 • • • • • • • −3             (a) A reducible matrix in UFNF1          0 • 0 1 −2 • • • 6 • −1 0 −3 • • • 5 • • • • 0 −1 −2 20 • • • • −3 0 −1 21 • • • • −2 1 0 22 • • • • • • • 0           (c) Left fundamental eigenvectors 1 2 3 5 6 7 8             0 −3 −2 6 5 4 • 0 1 • • • • −1 0 • • • • 0 1 • • • • • • 0 −1 −2 • • • −3 0 −1 • • • −2 1 0 • • • • • • 0            (A: U µ1 (A) = ( Ã3 µ1 ) + 1• , U µ2 (A) = ( Ã3 µ2 ) + 2• , U µ3 (A) = ( Ã3 µ3 ) +{5

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 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.

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