The paper is a continuation of our previous paper on operators and spaces associated to matrices whose degrees are elements from a residuated lattice. The motivation for this study is to develop a calculus for such matrices which can be used in situations such as matrix decompositions. In this paper, we focus on row and column spaces, left and right ideals of matrices, and Green's relations. We prove basic results concerning these notions, show links to known structures, and put a new perspective on results known from Boolean matrices and their generalizations.
In this paper, we continue the study, started in [
The paper is organized as follows. Preliminaries are provided in Section 2. Section 3 presents the results, namely the results on rows and column spaces, and the results on Green’s relations for matrices with entries from residuated lattices. Section 4 presents conclusions and topics for future research.
This section provides preliminaries, mainly from [
Matrices We deal with matrices whose degrees are elements from residuated lattices. In particular, we deal with (de)compositions I = A ∗ B which involve an n × m matrix I, an n × k matrix A, and a k × m matrix B. The entries of matrices I, A, B, are elements of a residuated lattice (see below); for the composition operator ∗, we use three particular products (explained later in this section).
Recall that a (complete) residuated lattice [
We assume that Iij , Ail, Blj ∈ L. That is, all the matrix entries are elements of some complete residuated lattice L. Elements a ∈ L are also called grades (degrees). In particular Iij is interpreted as the degree to which object i has attribute j; Ail as the degree to which factor l applies to object i; Blj as the degree to which attribute j is a manifestation (one of possibly several manifestations) of factor l.
Therefore, examples of matrices I which are subject to our decomposition are 1.0 1.0 0.0 0.0 0.6 0.4 0 0 1 1 1 11..00 10..09 00..00 10..00 01..00 00..08 or 00 00 10 10 01 .
1.0 0.5 0.0 0.7 1.0 0.4 0 1 1 1 0 The second matrix demonstrates that binary matrices are a particular case of the matrices for L = {0, 1}.
Remark 1. Residuated lattices are heavily used in fuzzy logic [
k (A ◦ B)ij = Wl=1 Ail ⊗ Blj ,
k (A ⊳ B)ij = Vl=1 Ail → Blj ,
k (A ⊲ B)ij = Vl=1 Blj → Ail. for j ∈ {1, . . . , m} and i ∈ {1, . . . , n}. Third, a pair h∧, ∨i of operators ∧ : LX → LY and ∨ : LY → LX is defined by for j ∈ {1, . . . , m} and i ∈ {1, . . . , n}. h↑, ↓i forms an antitone Galois connection, h∩, ∪i and h∧, ∨i each form an isotone Galois connection. To emphasize that the operators are induced by I, we also denote the operators by
h↑I , ↓I i, h∩I , ∪I i, and h∧I , ∨I i.
Note that these operators were extensively studied by Bandler and Kohout,
see e.g. [
Decomposition Problem Given an n × m matrix I and a composition operator ∗
(i.e., ◦, ⊳, or ⊲), the decomposition problem consists in finding a decomposition
I = A ∗ B of I into an n × k matrix A and an k × m matrix B with the number
k (number of factors) as small as possible. The smallest k is called the Schein
rank of I and is denoted by ρs(I) (to make the type of product explicit, also
by ρs◦(I), ρs ⊳(I), and ρs ⊲(I)). Looking for decompositions I = A ∗ B can be
seen as looking for factors in data described by I. That is, decomposing I can
be regarded as factor analysis in which the data as well as the operations used
are different from the ordinary factor analysis [
Concept Lattices Associated to I Let X = {1, 2, . . . , n} and Y = {1, 2, . . . , m}. Recall that LU denotes the set of all L-sets in U , i.e. all mappings from U to L. Consider the following pairs of operators induced by matrix I. First, a pair h↑, ↓i of operators ↑ : LX → LY and ↓ : LY → LX is defined by for j ∈ {1, . . . , m} and i ∈ {1, . . . , n}. Second, a pair h∩, ∪i of operators ∩ : LX → LY and ∪ : LY → LX is defined by
n C↑(j) = Vi=1(C(i) → Iij ), D↓(i) = Vjm=1(D(j) → Iij ),
n C∩(j) = Wi=1(C(i) ⊗ Iij ), D∪(i) = Vjm=1(Iij → D(j)),
n C∧(j) = Vi=1(Iij → C(i)), D∨(i) = Wjm=1(D(j) ⊗ Iij ), (1) (2) (3) (4) (5) (6) (7) (8) (9) Furthermore, denote the corresponding sets of fixpoints by B(X↑, Y ↓, I), B(X∩, Y ∪, I), and B(X∧, Y ∨, I), i.e.
B(X↑, Y ↓, I) = {hC, Di | C↑ = D, D↓ = C}, B(X∩, Y ∪, I) = {hC, Di | C∩ = D, D∪ = C},
B(X∧, Y ∨, I) = {hC, Di | C∧ = D, D∨ = C}.
The sets of fixpoints are complete lattices, called concept lattices associated to
I, and their elements are called formal concepts. Note that these operators and
their sets of fixpoints have extensively been studied, see e.g. [
The concept lattices associated to I play a fundamental role for decompositions of I. Namely, given a set
F = {hC1, D1i, . . . , hCk, Dki} of L-sets Cl and Dl in {1, . . . , n} and {1, . . . , m}, respectively, define n × k and k × m matrices AF and BF by
(AF )il = (Cl)(i) and (BF )lj = (Dl)(i).
This says: the l-th column of AF is the transpose of the vector corresponding to
Cl and the l-th row of BF is the vector corresponding to Dl. Then, we have:
Theorem 1 (universality, [
(⊳) Let I = A ⊳ B for n × k and k × m matrices A and B. Then there exists F ⊆ B(X∩, Y ∪, I) with |F | ≤ k such that for the n × |F | and |F | × m matrices AF and BF we have I = AF ⊳ BF .
(⊲) Let I = A ⊲ B for n × k and k × m matrices A and B. Then there exists F ⊆ B(X∧, Y ∨, I) with |F | ≤ k such that for the n × |F | and |F | × m matrices AF and BF we have I = AF ⊲ BF . 3 3.1
Row and Column Spaces
In Boolean matrix theory [
By Ln and Ln×m, we denote the set of all vectors with n components (i.e., 1×n matrices) and the set of all n×m matrices with entries from L (or, the set of all fuzzy sets in an n-element universe and the set of all fuzzy relations between an n- and m-element universes). Using the terminology of Boolean matrices, we define the following notions, generalizing the notions known from Boolean matrices.
Definition 1. V ⊆ Ln is called an i-subspace (or just a subspace if there is no danger of confusion) if – V is closed under ⊗-multiplication, i.e. for every a ∈ L and C ∈ V , a⊗C ∈ V (here, a ⊗ C is defined by (a ⊗ C)(i) = a ⊗ C(i) for i = 1, . . . , n); – V is closed under W-union, i.e. for Cj ∈ V (j ∈ J ) we have Wj∈J Cj ∈ V (here, Wj∈J Cj is defined by (Wj∈J Cj )(i) = Wj∈J Cj (i)).
V ⊆ Ln is called a c-subspace (or just a subspace if there is no danger of confusion) if – V is closed under →-shift, i.e. for every a ∈ L and C ∈ V , a → C ∈ V (here, a → C is defined by (a → C)(i) = a → C(i) for i = 1, . . . , n); – V is closed under V-intersection, i.e. for Cj ∈ V (j ∈ J ) we have Vj∈J Cj ∈
V (here, Vj∈J Cj is defined by (Vj∈J Cj )(i) = Vj∈J Cj (i)).
Remark 2. (1) If V ∈ Ln are regarded as fuzzy sets, the concepts of an i-subspace
and a c-subspace coincide with the concept of a fuzzy interior operator and a
fuzzy closure operator as defined in [
(2) For L = {0, 1} the concept of an i-subspace coincides with the concept of
a subspace from the theory of Boolean matrices [
Definition 2. The i-span ( c-span) of V ⊆ Ln is the intersection of all isubspaces (c-subspaces) of Ln that contain V . The row i-space ( row c-space) of matrix I ∈ Ln×m is the i-span (c-span) of the set of all rows of I (considered as vectors from Ln). The column i-space ( column c-space) is defined analogously as the i-span (c-span) of the set of columns of I. The row i-space, row c-space, column i-space, and column c-space of matrix I is denoted by Ri(I), Rc(I), Ci(I), Cc(I). Remark 3. For L = {0, 1}, the row i-space of I coincides with the row space of I as defined in Boolean matrix theory.
For the concept lattices B(X↑, Y ↓, I), denote the corresponding sets of extents and intents by Ext(X↑, Y ↓, I) and Int(X↑, Y ↓, I). That is,
Ext(X↑, Y ↓, I) = {C ∈ LX | hC, Di ∈ B(X↑, Y ↓, I) for some D},
Int(X↑, Y ↓, I) = {D ∈ LY | hC, Di ∈ B(X↑, Y ↓, I) for some C}, and analogously for Ext(X∩, Y ∪, I), Int(X∩, Y ∪, I), Ext(X∧, Y ∨, I), and Int(X∧, Y ∨, I).
A fundamental connection between the row and column spaces on one hand, and the concept lattices on the other hand, is described in the following theorem (IT denotes the transpose of I).
Theorem 3. For a matrix I ∈ Ln×m, X = {1, . . . , n}, Y = {1, . . . , m}, we have
Ri(I) = Int(X∩, Y ∪, I) = Ext(Y ∧, X∨, IT ), Rc(I) = Int(X↑, Y ↓, I) = Ext(Y ↑, X↓, IT ), Ci(I) = Ext(X∧, Y ∨, I) = Int(Y ∩, X∪, IT ),
Cc(I) = Ext(X↑, Y ↓, I) = Int(Y ↑, X↓, IT ).
Proof. Ri(I) = Int(X∩, Y ∪, I) was established in [
Sketch of the proof of (11): The assertion follows from the fact that D ∈ Int(X↑, Y ↓, I) iff D = C↑ for some C, i.e. D(j) = Vi∈X (C(i) → Iij ), which means that D is the V-intersection of →-shifts C(i) → Ii of rows Ii of I. The set of all such intersections may be shown to form a c-space and it is the least c-space containing all rows of I. ¤
The following theorem provides us with the relationships generalizing the well-known relationship between the row (column) space of a Boolean product of two Boolean matrices and the row (column) spaces of the two matrices. Theorem 4. For A ∈ Ln×k and B ∈ Lk×m, In addition,
Ri(A ◦ B) ⊆ Ri(B), Ci(A ◦ B) ⊆ Ci(A), Rc(A ⊳ B) ⊆ Rc(B),
Cc(A ⊲ B) ⊆ Cc(A).
Cc(A ⊳ B) ⊆ Ext(X∩, {1, . . . , k}∪, A),
Rc(A ⊲ B) ⊆ Int({1, . . . , k}∧, Y ∨, B).
Proof. The assertions follow from Theorem 3 and [6, Theorem 4] describing relationships of concept lattices of compositions of fuzzy relations; the full proof is omitted. ¤ (10) (11) (12) (13) (14) (15) (16) (17) (18) (19)
Green’s Relations
Green’s relations [
Definition 3. For n × n matrices I and J , Green’s relations L, R, and D are defined as follows: – ILJ iff {M ◦ I | M ∈ Ln×n} = {M ◦ J | M ∈ Ln×n}, i.e. I and J generate the same left ideal (we say that I and J are L-equivalent). – IRJ iff {I ◦ M | M ∈ Ln×n} = {J ◦ M | M ∈ Ln×n}, i.e. I and J generate the same right ideal (we say that I and J are R-equivalent).
– IDJ iff there exists matrix K ∈ Ln×n such that ILK and KRJ .
Remark 4. (1) There exist several other ways to define Green’s relations. For example: – IRJ iff there exist A, B such that I ◦ A = J and J ◦ B = I. – IDJ iff there exists K such that IRK and KLJ ; D is the supremum of L and R in the lattice of equivalence relations.
(2) Due to lack of space, we omit the other two Green’s relations, denoted usually H and J .
Theorem 5. (1) ILJ iff Ri(I) = Ri(J ).
(2) IRJ iff Ci(I) = Ci(J ) Proof. (1) {M ◦ I | M ∈ Ln×n} = {M ◦ J | M ∈ Ln×n} iff {M ◦ I | M ∈ L1×n} = {M ◦ J | M ∈ L1×n}. Now, an immediate reflection shows that the latter condition is equivalent to Int(X∩, Y ∪, I) = Int(X∩, Y ∪, J )., i.e. by Theorem 3, I and J have the same row i-spaces.
(2) The proof is similar to that of (1). ¤ Theorem 6. Let B be a k × m matrix and I be an n × m matrix. Ri(I) ⊆ Ri(B) iff there exists an n × k matrix A such that I = A ◦ B.
Proof. “⇒”: Let Ri(I) ⊆ Ri(B), i.e. Int(X∩, Y ∪, I) ⊆ Int(X∩, Y ∪, B). Every H ∈ Int(X∩, Y ∪, B) can be expressed as W1≤l≤k cl ⊗ Bl . Thus every H ∈ Int(X∩, Y ∪, I) can be expressed as W1≤l≤k cl ⊗ Bl . Therefore, a row Ii of I can be expressed as W1≤li≤k clj ⊗ Bl . We get the required matrix A by putting Ail = clj .
“⇐”: This was established in Theorem 4. ¤ In a similar way, we can establish other theorems describing the inclusion of the row and column spaces of I in the corresponding spaces of B (we omit them due to lack of space).
Theorem 7. If ILJ and A ◦ B = I then there exists A′ such that A′ ◦ B = J . Proof. Follows from (1) of Theorem 5 and Theorem 6.
An analogous theorem holds true for the equivalence relation R. Using Theorem 7 and the analogous version for R, we get the following corollary regarding the Schein rank of D-equivalent matrices.
Theorem 8. If IDJ then ρs◦(I) = ρs(J ).
In the following theorem, B(X∩, Y ∪, I) ≈ B(X∩, Y ∪, J ) denotes that B(X∩, Y ∪, I) and B(X∩, Y ∪, J ) are isomorphic lattices.
Theorem 9. IDJ iff B(X∩, Y ∪, I) ≈ B(X∩, Y ∪, J ).
Proof. Sketch: “⇒”: Let IDJ . There there exists K such that ILK and KRJ . Hence, we have Int(X∩, Y ∪, I) = Int(X∩, Y ∪, K) by Theorem 5. Let now T and S be matrices for which K ◦ S = J and J ◦ T = K (they exists according to the above remark). Consider the mappings ¤ ∩S : Int(X∩, Y ∪, K) → Int(X∩, Y ∪, J ), ∩T : Int(X∩, Y ∪, J ) → Int(X∩, Y ∪, K).
One can show that ∩S∩T and ∩T ∩S are identities. Therefore, Int(X∩, Y ∪, K) and Int(X∩, Y ∪, J ) are isomorphic, establishing that B(X∩, Y ∪, I) and B(X∩, Y ∪, J ) are isomorphic lattices. The proof of “⇐”omitted due to lack of space. ¤
The above notions and results in this section have their counterparts for ⊳and ⊲-compositions of matrices. In the rest of this section, we present some of them without proofs.
Definition 4. For n × n matrices I and J , Green’s relations L⊳, R⊲, and D⊳ ⊲ are defined as follows: – IL⊳J iff {M ⊳ I | M ∈ Ln×n} = {M ⊳ J | M ∈ Ln×n}. – IR⊲J iff {I ⊲ M | M ∈ Ln×n} = {J ⊲ M | M ∈ Ln×n}.
– ID⊳ ⊲J iff there exists matrix K ∈ Ln×n such that IL⊳K and KR⊲J . Theorem 10. (1) IL⊳J iff Rc(I) = Rc(J ).
(2) IR⊲J iff Cc(I) = Cc(J ) Theorem 11. Let B be a k×m matrix and I be an n×m matrix. Rc(I) ⊆ Rc(B) iff there exists an n × k matrix A such that I = A ⊳ B.
Theorem 12. If IL⊳J and A ⊳ B = I then there exists A′ such that A′ ⊳ B = J . Theorem 13. If ID⊳ ⊲J then ρs ⊳(I) = ρs ⊳(J ).
We established properties of structures associated with matrices with entries
from residuated lattices. By doing so, we generalized the properties known from
Boolean matrix theory and provided links to structures known from formal
concept analysis. The line of research started in this paper and its predecessor is
to be continued to establish foundations for a calculus of matrices with entries
from residuated lattices. The usefulness of such calculus for data analysis is
demonstrated in [
Supported by grant No. 202/10/0262 of the Czech Science Foundation and by research plan MSM 6198959214.