The spectra of irreducible matrices over completed idempotent semifields

Abstract

Motivated by some spectral results in the characterization of concept lattices we investigate the spectra of reducible matrices over complete idempotent semifields in the framework of naturally-ordered semirings, or dioids. We find non-null eigenvectors for every non-null element in the semifield and conclude that the notion of spectrum has to be refined to encompass that of the incomplete semifield case so as to include only those eigenvalues with eigenvectors that have finite coordinates. Considering special sets of eigenvectors brings out finite complete lattices in the picture and we contend that such structure may be more important than standard eigenspaces for matrices over completed idempotent semifields.

Introduction

Several attempts have been made to generalise the basic framework of Formal Concept Analysis (FCA) [1] or Galois lattice theory [2] since it was conceived. Recall that this is a theory of concrete lattices arising from certain Galois connections between two sets induced by a binary incidence relation. It finds concrete applications in data mining and exploratory information retrieval, among others [3].

Perhaps the earliest and more developed generalisation is that of Formal Concept Analysis in a Fuzzy Setting, where incidences are allowed to have values in a fuzzy algebra which is also a complete lattice [4], [5]. Such fuzzy algebras can alternatively be described as fuzzy semirings [6]. Recall that a semiring is an algebra $\mathcal{S}=〈S,\oplus ,\otimes ,ϵ,e〉$ whose additive structure, $〈S,\oplus ,ϵ〉$, is a commutative monoid and whose multiplicative structure, $〈S\backslash \{ϵ\},\otimes ,e〉$, is a monoid with multiplication distributing over addition from right and left and with additive neutral element absorbing for ⊗, i.e. $\forall a\in S$, $ϵ\otimes a=ϵ$ [6].

An independently motivated generalisation of FCA, $\mathcal{K}$-Formal Concept Analysis, uses an idempotent semifield $\mathcal{K}$—a kind of semiring with a multiplicative group structure—as the range of the relation [7]. Whereas fuzzy semirings are mostly used to capture a “degree of truth”, semifields are used to capture the concept of “cost” or “utility”.

It is intriguing that these algebras induce Galois connections and Formal Concept Analysis inasmuch as idempotent semifields are as far as a naturally ordered semiring can be from prototypical fuzzy semirings like $〈[0,1],\max ,\min ,0,1〉$—in a sense made evident in this paper. In fact, idempotent semifields do not fulfil some of the more restrictive or technical conditions for an algebra L to define an L-fuzzy set [8]: in particular, in an idempotent semifield the identity is never an infinity element.

However, it has already been determined that the condition for an algebra to induce a flavour of FCA is that it be a complete residuated lattice [5]. Unsurprisingly, one of the notoriously overlooked abstractions of fuzzy semirings and idempotent semifields are dioids, or naturally-ordered semirings whose zero is the bottom in the order. Dioids are already residuated so complete dioids are already complete residuated lattices (see Fig. 1), hence Formal Concept Analysis-inducing. Furthermore, semiring $\mathbb{2}$ is embedded in both fuzzy semirings and idempotent semifields. Note that Ref. [9] already asked in this venue for a revisiting of idempotent semifields and the investigation of their relationship to fuzzy algebras.

On the other hand, concept lattices as issued from standard FCA show a remarkable relation to some eigenspaces of the incidence relation. For instance Ref. [10] found that the formal concepts in $\mathcal{K}$-Formal Concept Analysis  could be defined by means of the eigenequation of the unit eigenvalue. Building on earlier work, Ref. [11] demonstrated that binary formal concepts were optimal factors for decomposing a Boolean matrix, while Ref. [12] extended this to formal concepts over a residuated lattice. Both kind of results hint strongly that Formal Concept Analysis has some relationship with the Singular Value Decomposition (SVD) of the incidence relation and that formal concepts are pairs of left/right singular vectors. Despite the spectral theory of dioids having a long history of results [6], few general results for the cases of interest are known [13], [14] and a theorem of spectral decomposition is undiscovered, to the best of our knowledge.

This work tries to pave the way for an overarching theory of Formal Concept Analysis over complete dioids by trying to make explicit the relation from the other side of the picture: between complete lattices and some eigenspaces related to relations with entries in a complete (residuated) dioid. Unfortunately, idempotent semifields, except $\mathbb{2}$ are all incomplete, what seems to doom our efforts in this direction. However, it is well-known that idempotent semifields can easily be completed: the problem with the bottom being its lack of inverse, we can easily prescribe the top ⊤ to take this role.

This paper is dedicated to exploring the consequences of this decision in what respects the spectral theory of matrices over such top-completed idempotent semifields. We will prove that, far from harming our initial intentions, completing the semifield unveils lattice structures as scaffoldings of eigenspaces, and that such structures extend to more general semirings.

Also, we point out noticeable differences with the spectrum of incomplete idempotent semifields. To start with, since ⊤ may be a coordinate in eigenvectors, the spectrum is more extensive, to the point where, once a non-null eigenvalue is found, most of the values in the dioid are spectral, albeit their eigenvectors will have non-finite coordinates (Section 3.1). This necessitates the definition of the proper right (left) spectrum, ${\mathrm{P}}^{\mathrm{P}}(A)$ whose corresponding eigenvectors have some finite coordinate, which partially recovers the picture in the incomplete, irreducible case (Section 3.2).

Furthermore, once $\overline{\mathcal{K}}$ is a completed idempotent semifield, ⊤ may be an eigenvalue (Section 3.1.3), whence the structure of the eigenspaces is that of a complete lattice. Therefore, independency of eigenvectors plays a lesser role than heretofore expected. Rather, in our analysis, the order properties of such eigenvectors—induced from the order in the underlying semiring—are highlighted (Section 3.2.1).

This paper is organized as follows: Section 2 delimits the area of application of our findings by presenting a family picture of semirings (Section 2.1) followed by a discussion of completeness issues in idempotent semifields (Section 2.2). Then we state formally the eigenproblem on semirings as well as some techniques to solve it in dioids (Section 2.3). A review of the different cryptomorphisms or interpretations of matrices over semirings as number arrays, relations or networks with weights in a semiring, crucial for the spectral theory, can also be found in Section 2.4. Section 3 presents our results for the spectra of irreducible matrices over completed idempotent semifields beginning with a compilation and contextualization of previous results about the null eigenvalue and eigenspace (Section 3.1) also useful for the reducible case, tackled in [15]. The spectra are finally characterized in Section 3.2 including a discussion about the role of this eigenvectors for the representation of eigenspaces (Section 3.2.1). Then, we illustrate our findings with examples (Section 4), discuss the existent solutions for the incomplete case (Section 5), and draw some conclusions in Section 6.