1. Introduction
In the field of applications, lattice matrices play major role in various areas such as automata theory, design of switching circuits, logic of binary relations, medical diagnosis, markov chains, computer network, traffic control (see e.g. [1]). Since several classical lattice matrices, for example transitive matrix, monotone increasing matrix, nilpotent matrix, have special applications, many authors have studied these types of matrices. In fact, a transitive matrix can be used in clustering, information retrieval, preference, and so on (see e.g. [2,3]); a nilpotent matrix represents an acyclic graph that is used to represent consistent systems and is important in the representation of precedence relations (see e.g. [4]). Recently, the transitive closure of lattice matrix has been used to analyze the maximum road of network. In this paper, we continue to study transitive lattice matrices and monotone increasing matrices. The main results obtained in this paper develop the previous results on transitive lattice matrices [5] and monotone increasing matrices [6].
2. Definitions and Preliminaries
At this section, we shall give some definitions and lemmas. Let be a partially ordered set (simply denoted by poset) and. If or then and are called comparable. Otherwise, and are called incomparable, noted by. If for any, and are comparable, then P is called a chain. An unordered poset is a poset in which for all. A chain c in a poset P is a nonempty subset of P, which, as a subposet, is a chain. An antichain C in a poset P is a nonempty subset which, as a subposet, is unordered. A lattice is a poset in which every two elements have a unique least upper bound and a unique greatest lower bound. For any x and y in L, the least upper bound and the greatest lower bound will be denoted by and, respectively. It is clear that any chain is a lattice, which is called a linear lattice. It is obvious that if is a linear lattice (especially, the fuzzy algebra [0,1] or the binary Boolean algebra) then and for all x and y in L. Let be a lattice and. X is called a sublattice of L if for any and A lattice is said to be distributive if the operations and are distributive with respect to each other. A matrix is called a lattice matrix if its entries belong to a distributive lattice. In this paper, the lattice is always supposed to be a distributive lattice with the least and greatest elements 0 and 1, respectively. Let be all matrices over L. For any A in, we shall denote by or the element of L which stands in the entry of A. For convenience, we shall use the set N to denote the set
For any A, B, C in, we define:
iff for in N;
iff for in N;
iff for in N;
iff for in N and iff;
where if and if for
For any A in the powers of A are defined as follows: where Z+ denotes the set of all positive integers. The entry of is denoted by and
Let A is called transitive if
A is called monotone increasing if A is called reflexive if In this paper, A lattice matrix A is called monotone if A is transitive or A is monotone increasing.
For any, A is said to be almost periodic if there exist positive integers k and d such that The least positive integers k and d are called the index and the period of A, and denoted by and respectively. In particular, if then A is said to converges in a finite number of steps.
3. Convergence of Monotone Lattice Matrices
In this section, we shall discuss the convergence of Monotone Lattice Matrices. In [5,6], Tan studied the convergence index of transitive matrices and monotone increasing matrices. In the following, we continue to study the convergence index of these matrices which discussed by Tan [5,6], and the convergence index of these discussed matrices is smaller than previous considered index.
Theorem 3.1. Let if
holds for all then 1)
2)
3) converges to with
Proof. 1) Let
By the hypothesis it follows that
Since is the sum of some term in we have
Thus
2) By we have
Then
Therefore,
3) By, it follows that. Hence, In the following, we shall prove that
By the result of 2), we only need to show that for Let
Since the number of indices in is, there must be two indices and such that. Then
Since is a term of we have
Thus then
(since for).
From above, we can get This completes the proof.
Corollary 3.1. Let if then 1)
2) for all
3) A converges to with
Proof. It follows from Theorem 3.1.
Theorem 3.2. Let If and
holds for all, then A converges towith
Proof. Sincewe have
Then
Let be any term of
Since the number of indices in T is greater than, there must be two indices and such that . Then
Now delete the term in, thus we can get a new term
Since is a term of we have. But by the property of the operation, we have
Thus On the other hand, by the hypothesis we have
From above, we can get
Since, we have
and so
This completes the proof.
Theorem 3.3. Let. If for any
, or, then 1);
2);
3) A converges to with.
Proof. 1) Let
.
If, then
If, then
Thus, and so. Therefore
2) for any, ,
On the other hand, by the result in 1), we have.
3) It follows from Theorem 3.2. This completes the proof.
Corollary 3.2. Let. If for any and, then 1);
2) A converges to with.
Proof. 1) By, we can get
Since
We have. On the other hand, since, we have. Therefore
2) It follows from Theorem 3.2. This completes the proof.
Theorem 3.4. If A is transitive and. Where, with and
, then 1) converges to with;
2) If A satisfies (or) for some
, then B converges to with;
3) If B satisfies (or) for some
, then B converges to with.
Proof. First by, we have .
1) Let
Now, we consider any term T of. Since the number of indices in T is greater than n, there must be two indices and such that. Then
And
Since is transitive, we have for all, and so. Thus
Since is a term of, we have
Then, and so. Therefore . On the other hand, since
We have, then. From above, we can get, and so.
2) By the proof of 1), we have. In the following we shall prove that.
Let
Now consider any term of.
a) If for some and, then
And so
Then
b) Suppose that for all. By the hypothesis, (or) for some and
, we can get Thus
From above, we have, and so. Therefore.
3) The proof of 3) is similar to that of 2). This completes the proof.
Theorem 3.4 is an improvement of Theorem 4.1 [6].
As a special of Theorem 3.4, we obtain the following Corollary.
Corollary 3.3. If is transitive, then 1) converges to with;
2) If A satisfies (or) for some
, then A converges to with.
Corollary 3.3 is an improvement of Corollary 4.1 [6].
NOTES