# On Generalized Transitive Matrices

Authors: Jing Jiang; Lan Shu; Xinan Tian
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

Transitivity of generalized fuzzy matrices over a special type of semiring is considered.
The semiring is called incline algebra which generalizes Boolean algebra, fuzzy algebra, and
distributive lattice. This paper studies the transitive incline matrices in detail. The transitive closure of an incline matrix is studied, and the convergence for powers of transitive
incline matrices is considered. Some properties of compositions of incline matrices are also
given, and a new transitive incline matrix is constructed from given incline matrices. Finally,
the issue of the canonical form of a transitive incline matrix is discussed. The results obtained here generalize the corresponding ones on fuzzy matrices and lattice matrices shown
in the references.


---

## Body

## 1. Introduction

Generalized transitive matrices [1] over a special type of semiring are introduced. The semiring is called incline algebra. Boolean algebra, fuzzy algebra, and distributive lattice are inclines. And the Boolean matrices, the fuzzy matrices, and the lattice matrices are the prototypical examples of the incline matrices. Inclines are useful tools in diverse areas such as design of switching circuits, automata theory, medical diagnosis, information systems, and clustering. Besides inclines are applied to nervous system, probable reasoning, dynamical programming, and decision theory.Transitive matrices are an important type of generalized matrices which represent transitive relation (see, e.g., [2–6]). Transitive relation plays an important role in clustering, information retrieval, preference, and so on [5, 7, 8]. The transitivity problems of matrices over some special semirings have been discussed by many authors (see, e.g., [9–17]). In 1982, Kim [18] introduced the concept of transitive binary Boolean matrices. Hashimoto [11] presented the concept of transitive fuzzy matrices and considered the convergence of powers of transitive fuzzy matrices. Kołodziejczyk [10] gave the concept of s-transitive fuzzy matrices and considered the convergence of powers of s-transitive fuzzy matrices. Tan [17, 19] discussed the convergence of powers of transitive lattice matrices. Han and Li [1] studied the convergence of powers of incline matrices. In [12, 13], the canonical form of a transitive matrix over fuzzy algebra was established, and, in [14, 15, 17], the canonical form of a transitive matrix over distributive lattice was characterized. In [9, 16, 20], some properties of compositions of generalized fuzzy matrices and lattice matrices were examined.In this paper, we continue to study transitive incline matrices. In Section3, the transitive closure of an incline matrix is discussed. In Section 4, the convergence of powers of transitive incline matrices is considered. In Section 5, some properties of compositions of incline matrices are given and a new transitive incline matrix is constructed from given incline matrices. In Section 6, the issue of the canonical form of an incline matrix is further discussed. Some results in this paper generalize the corresponding results in [14, 17, 20].


## 2. Definitions and Preliminary Lemmas

In this section, we give some definitions and lemmas.Definition 2.1 (see [1]).
A nonempty setL with two binary operations + and · is called an incline if it satisfies the following conditions:(1)
(L,+) is a semilattice;(2)
(L,·) is a commutative semigroup;(3)
x(y+z)=xy+xz for all x,y,z∈L;(4)
x+xy=x for all x,y∈L.In an inclineL, define a relation ≤ by x≤y⇔x+y=y. Obviously, xy≤x for all x,y∈L. It is easy to see that ≤ is a partial order relation over L and satisfies the following properties.Proposition 2.2 (see [21]).
LetL be an incline and a,b,c∈L. Then,(1)
0≤a≤1;(2)
ifa≤b, then a+c≤b+c, ac≤bc, ca≤cb;(3)
a≤a+b, and a+b is the least upper bound of a and b;(4)
ab≤a, ab≤b. In other words, ab is a lower bound of a and b;(5)
acb≤ab;(6)
a+b=0 if and only if a=b=0;(7)
ab=1 if and only if a=b=1.Boolean algebra ({0,1},∨,∧), fuzzy algebra ([0,1],∨,T) (T is a t-norm) and distributive lattice are inclines. Let (L,≤) be a poset and a,b∈L. If a≤b or b≤a, then a and b are called comparable. Otherwise, a and b are called incomparable, in notation, a∥b. If for any a,b∈L, a and b are comparable, then L is linear and L is called a chain. An unordered poset is a poset in which a∥b for all a≠b. A chain B in a poset L is a nonempty subset of L, which, as a subposet, is a chain. An antichain B in a poset L is nonempty subset which, as a subposet, is unordered. The width of a poset L, denoted by w(L), is n, where n is a natural number, iff there is an antichain in L of n elements and all antichains in L have ≤n elements. A poset (L,≤) is called an incline if L satisfies Definition 2.1. It is clear that any chain is an incline, which is called a linear incline.An elementa of an incline L is said to be idempotent if a2=a. The set of all idempotent elements in L is denoted by I(L), that is, I(L)={a∈L∣a2=a}.A matrix is called an incline matrix if its entries belong to an incline. In this paper, the incline(L,≤,+,·) is always supposed to be a commutative incline with the least and greatest elements 0 and 1, respectively. Let Mn(L) be the set of all n×n matrices over L. For any A in Mn(L), we will denote by aij or Aij the element of L which stands in the (i,j)th entry of A. For convenience, we will use N to denote the set {1,2,…,n}, and Z+ denotes the set of all positive integers.For anyA, B, C in Mn(L) and a in L, we defineA+B=C iff cij=aij+bij for all i, j in N;AB=C iff cij=∑k=1naikbkj for all i, j in N;AT= C iff cij=aji for all i, j in N;aA=C iff cij=aaij for all i, j in N;A≤B iff aij≤bij for all i, j in N and A≥B iff B≤A;In=(tij), where(2.1)tij={1,i=j,0,i≠j,fori,j∈N.For anyA in Mn(L), the powers of A are defined as follows:A0=In, Al=Al-1A, l∈Z+.The(i,j)th entry of Al is denoted by aijl(l∈Z+), and obviously
(2.2)aijl=∑1≤i1,i2,…,il-1≤naii1ai1i2⋯ail-1j.
The following properties will be used in this paper.(1)
Mn(L) is a semigroup with the identity element In with respect to the multiplication;(2)
(Mn(L),+,·) is a semiring.IfA2≤A, then A is called transitive; if A2=A, then A is called idempotent; if AT=A, then A is called symmetric; if A≤A2, then A is called increasing; if A≥In, then A is called reflexive; if aii=0 for all i∈N, then A is called irreflexive; if Am=0 (m∈Z+), then A is called nilpotent; if aij=0 for i,j=1,2,…,n, then A is called the zero matrix and denoted by 0n; A is called a permutation matrix if exactly one of the elements of its every row and every column is 1 and the others are 0.LetB∈Mn(L). The matrix B is called the transitive closure of A if B is transitive and A≤B, and, for any transitive matrix C in Mn(L) satisfying A≤C, we have B≤C. The transitive closure of A is denoted by A+. It is clear that if A has a transitive closure, then it is unique.For anyA∈Mn(L) with index, the sequence (2.3)A,A2,A3,…,Al,…
is of the form (2.4)A,A2,…,Ak-1∣Ak,…,Ak+d-1∣Ak,…,Ak+d-1∣⋯,
where k=k(A) is the least integer such that Ak=Ak+d for some d>0. The least integers k=k(A), d=d(A) are called the index and the period of A, respectively.The following definition will be used in this paper.Definition 2.3.
A matrixA=(aij)∈Mn(L)is said to be(1)
row diagonally dominant ifaij=aiiaij for all i,j∈N;(2)
column diagonally dominant ifaij=aijajj for all i,j∈N;(3)
weakly diagonally dominant if for anyi∈N, either aiiaij=aij for all j∈N or aiiaji=aji for all j∈N;(4)
strongly diagonally dominant ifaij=aiiaij=aijajj for all i,j∈N;(5)
nearly irreflexive ifaiiaij=aii for all i,j∈N.Lemma 2.4.
I(L) is a distributive lattice, where  I(L)={a∈L∣a2=a}.The proof can be seen in [1].


## 3. Transitive Closure of an Incline Matrix

In this section, some properties of the transitive closure of an incline matrix are given and an algorithm for computing the transitive closure of an incline matrix is posed.Lemma 3.1.
For anyA in Mn(L), we have A+=∑k=1nAk.The proof can be seen in [21].Lemma 3.2.
LetA∈Mn(L). Then,(1)
for anyi,j∈N with i≠j and any k≥n, there exists s(s∈{1,2,…,n-1}) such that aijs≥aijk;(2)
for anyi∈N and any k≥n, there exists t∈N such that aiit≥aiik.Proof.
(1) LetT=aii1ai1i2⋯aik-1j be any term of aijk, where k≥n and 1≤i,i1,i2,…,ik-1, j≤n. Since the number of indices in T is greater than n, a repetition among them must occur. Let us call the sequence of entries between two occurrences of one index a cycle. If we drop the cycle, a new expression T1 with m1≤k entries is obtained. If m1≥n, there must be a cycle in T1, then we delete the cycle and obtain a new expression T2 with m2≤m1 entries. The deleting method can be applied repeatedly until the new expression Ts contains ms<n entries. According to properties of the operation “·”, T≤T1≤⋯≤Ts, but Ts is a term of the (i,j)th entry aijs of As for some s<n, we have T≤T1≤⋯≤Ts≤aijs, and so aijk≤aijs. This completes the proof.
(2) LetT=aii1ai1i2⋯aik-1i be any term of aiik, where k≥n+1 and 1≤i,i1,i2,…,ik-1≤n. Since the number of indices in T is greater than n, there must be two indices iu and iv such that iu=iv for some u, v (u<v). Then, we delete aiuiu+1⋯aiv-1iv from T and obtain a new expression T1=aii1ai1i2⋯aiu-1iuaiviv+1⋯aik-1i with m1≤k entries. If m1≥n+1, there are still two identical numbers in the subscripts i,i1,…,iu-1,iu,iv+1,…,ik-1, then we apply the deleting method used in the above. The method can be applied repeatedly until the subscripts left are pairwise different. Finally, we can get a new term Tt with mt≤n entries. According to properties of the operation “·”, T≤T1≤⋯≤Tt, but Tt is a term of the (i,i)th entry aiit of At for some t≤n, we have T≤T1≤⋯≤Tt≤aiit, and so aiik≤aiit. This completes the proof.Lemma 3.3.
LetA∈Mn(L). Then,(1)
∑l=1nAl≥Ak for any k≥1;(2)
∑l=1nAl=∑l=1mAl for any m≥n.Proof.
From Lemma3.2, the proof is obvious.Proposition 3.4.
IfA+ is reflexive, then (A+)+=A+.Proof.
SinceA+≥In, we have A+≤(A+)2. On the other hand, by Lemmas 3.1 and 3.3, we see that (A+)2≤A+. Hence, (A+)+=A+.Proposition 3.5.
For anyA=(aij)∈Mn(L) with index, if A is column (or row) diagonally dominant, then A+=As, where As is transitive.Proof.
We only consider the caseA is column diagonally dominant.
For any integerl>0, we have Als≤As since As is transitive, and so aijls≤aijs, for all i,j∈N. Since A is column diagonally dominant, we have aijl=aijlajjajj⋯ajj≤aijls (because aijlajjajj⋯ajj is the sum of some term in aijls) ≤aijs. Hence, ∑l=1naijl≤aijs, then A+≤As. On the other hand, since A+=∑l=1nAl=∑l=1mAl for any m≥n, we have A+≥As. Therefore, A+=As.Corollary 3.6.
For anyA=(aij)∈Mn(L) with index, if A is strongly diagonally dominant, then A+=As, where As is transitive.Proof.
Obviously, any strongly diagonally dominant matrix is column (or row) diagonally dominant. Hence, the conclusion follows from Proposition3.5.Proposition 3.7.
For anyA=(aij)∈Mn(L) with index, if A is weakly diagonally dominant, then A+=As, where As is transitive.Proof.
SinceAs is transitive, we have As≥Als, and so aijs≥aijls, for any i,j∈N and any integer l>0. Since A is weakly diagonally dominant, we have for any i∈N, either aiiaij=aij for all j∈N or aiiaji=aji for all j∈N.
Let(3.1)aijl=∑1≤i1,…,il-1≤naii1ai1i2⋯ail-1j(∀i,j∈N).
Case 1.
Ifai1i1ai1j=ai1j for all j∈N, we have ai1i1ai1i2=ai1i2. Then,
(3.2)aijl=∑1≤i1,…,il-1≤naii1ai1i2⋯ail-1j=∑1≤i1,…,il-1≤naii1ai1i1⋯ai1i1ai1i2⋯ail-1j≤aijls(since∑1≤i1,…,il-1≤naii1ai1i1⋯ai1i1ai1i2⋯ail-1jisthesumofsometerminaijls)≤aijs.Case 2.
Ifaji1ai1i1=aji1 for all j∈N, we have aii1ai1i1=aii1. Then,
(3.3)aijl=∑1≤i1,…,il-1≤naii1ai1i2⋯ail-1j=∑1≤i1,…,il-1≤naii1ai1i1⋯ai1i1ai1i2⋯ail-1j≤aijls(since∑1≤i1,…,il-1≤naii1ai1i1⋯ai1i1ai1i2⋯ail-1jisthesumofsometerminaijls)≤aijs.
From above, we see thataijl≤aijls≤aijs for any i,j∈N. Hence, ∑l=1naijl≤aijs, then A+≤As. On the other hand, since A+=∑l=1nAl=∑l=1+∞A, we have A+≥As. Therefore, A+=As.Proposition 3.8.
LetA=(aij)∈Mn(L). If the entries of A satisfy aiiajk=ajk (1≤i,j,k≤n), then(1)
A2≤A3;(2)
aii=aii2=⋯=aiin  for all i∈N;(3)
A converges toAk(A) with k(A)≤n-1.Proof.
(1) Since any termT of the (i,j)th entry aij2 of A2 is of the form aii1ai1j, we have aij2=∑k=1naikakj (1≤i,j,k≤n). Because the hypothesis aiiajk=ajk, we can get aij2=∑k=1naikakkakj. Since aikakkakj is a term of aij3, we have aij2=∑k=1naikakkakj≤aij3.
Thus,A2≤A3.
(2) Because the hypothesisaiiajk=ajk, we have aiiaii⋯aii=aii. Hence,(3.4)aii≤aiis=∑1≤i1,…,is-1≤naii1ai1i2⋯ais-1i≤∑k∈Naik=∑k∈Naiiaik≤∑k∈Naii=aii,
then aii=aiis (for all s∈N).
(3) SinceA2≤A3, we have Ak-1≤Ak (for any integer k≥3), and so An-1≤An. Now we prove that An-1≥An. By (2), it is sufficient only to show that aijn-1≥aijn for i≠j. Let
(3.5)aijn=∑1≤i1,…,in-1≤naii1ai1i2⋯ain-1j(∀i,j∈N).
Since the number of indices in aii1ai1i2⋯ain-1j is n+1, there must be two indices iu and iv such that iu=iv for some u,v(u<v). Then, aii1ai1i2⋯ain-1j≤aii1ai1i2⋯aiu-1iuaiviv+1⋯ain-1j. Since aii1ai1i2⋯aiu-1iuaiviv+1⋯ain-1j is a term of aijn-(v-u), we have aii1ai1i2⋯ain-1j≤aii1ai1i2⋯aiu-1iuaiviv+1⋯ain-1j≤aijn-(v-u) and so aijn≤aijn-(v-u), that is, An≤Am(m=n-(v-u)<n)≤An-1 (because Ak-1≤Ak for any integer k≥3). Therefore, An-1=An. This proves the proposition.Lemma 3.9.
LetA=(aij)∈Mn(L). If the entries of A satisfy aiiajk=ajk (1≤i,j,k≤n), then adj(A)=An-1.The proof can be seen in [22].Proposition 3.10.
LetA=(aij)∈Mn(L). If the entries of A satisfy aiiajk=ajk (1≤i,j,k≤n), then (adjA)+=An-1.Proof.
By the Proposition3.8, we have An-1=An. By Lemma 3.9, we can get adj(A)=An-1. Thus, (adjA)+=(An-1)+=An-1.Corollary 3.11.
LetA=(aij)∈Mn(L). If A is reflexive, then(1)
A≤A2;(2)
aii=aii2=aii3=⋯=aiin=1  for all i∈N;(3)
A converges to Ak(A) with k(A)≤n-1;(4)
(adjA)+=An-1;(5)
((adjA)+)+=An-1.Proof.
From Propositions3.10 and 3.8, the proof is obvious.Proposition 3.12.
LetA=(aij)∈Mn(L). If L has no nilpotent elements and A is nilpotent, then(1)
(adjA)2=0;(2)
(adjA)+=adjA.Proof.
(1) The proof can be seen in [23].
(2) Form (1), the proof is obvious.Proposition 3.13.
LetA=(aij)∈Mn(L), A+=(tij)n×n, (In+A)+=(tij̃)n×n, then(1)
(In+A)+=(In+A)n=In+∑l=1nAl;(2)
(In+A)+=(In+A)n-1=In+∑l=1n-1Al;(3)
tij=∑l=1naijl=tij̃ (for all i,j∈N and i≠j).Proof.
(1) Since(In+A) is reflexive, we have (In+A) is increasing. By Lemma 3.1, we can get the conclusion.
(2) By Corollary3.11, (In+A) converges to (In+A)k(In+A) with k(In+A)≤n-1. Thus, the conclusion is obtained.
(3) From (1) and (2), the proof is obvious.At the end of this section, we may establish the following algorithm to find the(A+)ij (i≠j).LetA∈Mn(L), A+=(tij)n×n,(In+A)+=(tij̃)n×n, and B=In+A.Step 1.
Compute successively(3.6)B2,B22,…,B2p,…,(p∈Z+).
In (3.6), find p≤k-1 such that B2p-1≠B2p, but B2p=B2p+1. Then, (In+A)+=B2p. Go to Step 2.Step 2.
Find(A+)ij (i≠j).
Lettij=tij̃ (i≠j). Stop.


## 4. Convergence of Powers of Transitive Incline Matrices

In this section, the convergence of powers of transitive incline matrices inMn(L) will be discussed.Definition 4.1.
LetA=(aij)∈Mn(L). For any i,j∈N, if aijaik≠aik⇒aijakj=akj holds for all k∈N, then A is called a strongly transitive matrix.Theorem 4.2.
IfA=(aij)∈Mn(L) is a strongly transitive matrix, then A is transitive.Proof.
SinceA is strongly transitive, for any i,j∈N, we have aijaik=aik for all k∈N or aijaik≠aik and aijakj=akj for all k∈N.
Case 1.
For anyi,j∈N, suppose aijaik=aik for all k∈N, then we can get aij≥aijaik=aik≥aikakj, so aij≥∑k=1naikakj=aij2, which means that A is transitive.Case 2.
For anyi,j∈N, suppose aijaik≠aik and aijakj=akj for all k∈N, then we can get aij≥aijakj=akj≥aikakj, so aij≥∑k=1naikakj=aij2, which means that A≥A2. This completes the proof.Remark 4.3.
IfA is transitive, but A is not necessary to be a strongly transitive matrix.Example 4.4.
Consider the clineL={0,a,b,c,1} whose diagram is as Figure 1.
Let now(4.1)A=(cabc).
Then,A2≤A which means that A is transitive. But a11a12=ca≠a12=a (because ca<a)⇏a11a21=cb=a21=b (because cb<b), which means that A is not a strongly transitive matrix.Figure 1Theorem 4.5.
LetA=(aij)∈Mn(L). If A≥A2 and aii∈I(L) (for all i∈N), then(1)
aii=aii2=⋯=aiin  for all i∈N;(2)
A converges to Ak(A) with k(A)≤n.Proof.
(1) By the hypothesisA≥A2, it follows that Ak≥Ak+1 (for all k∈N). Hence, An≥An+1 and aii≥aiis (for all s∈N). Since aii∈I(L), we can get aii=aii⋯aii≤aiis (for all s∈N). Thus aii=aiis and aiis∈I(L).
(2) By (1), it is sufficient to verifyAn≤An+1.
Now, any termT of the (i,j)th entry aijn of An is of the form aii1ai1i2⋯ain-1j, where 1≤i1,i2,…,in-1≤n. Since the number of indices in T is greater than n, there must be two indices iu and iv such that iu=iv for some u,v (0≤u<v≤n, i0=i, in=j). Then, aii1ai1i2⋯ain-1j=aii1ai1i2⋯aiu-1iuaiuiu+1⋯aiv-1ivaiviv+1⋯ain-1j≤aii1ai1i2⋯aiu-1iuaiuiuv-uaiviv+1⋯ain-1j (because aiuiu+1⋯aiv-1iv is a term of aiuiuv-u) =aii1ai1i2⋯aiu-1iuaiuiuv-uaiuiuv-uaiviv+1⋯ain-1j (because (1) aii=aiis (for all i,s∈N) and aii∈I(L)) ≤aijn+(v-u)(v-u≥1) (because aii1ai1i2⋯aiu-1iuaiuiuv-uaiuiuv-uaiviv+1⋯ain-1j is the sum of some term in aijn+(v-u)) ≤aijn+1 (because Ak≥Ak+1 for any k∈N). Thus, T≤aijn+1, and so aijn≤aijn+1. Therefore, An≤An+1. This completes the proof.Corollary 4.6.
IfA=(aij)∈Mn(L) is strongly transitive, then A converges to Ak(A) with k(A)≤n.Proof.
SinceA is strongly transitive, by Theorem 4.2, we have  A≥A2 and aii∈I(L) (for all i∈N), the conclusion is obtained.Theorem 4.7.
LetA=(aij)∈Mn(L) be transitive. If B=(bij)∈Mn(I(L)) and diag(A)≤B≤A, where diag(A)=(cij) with cii=aii (for all i∈N) and cij=0(i≠j,i,j∈N). Then,(1)
B converges to Bk(B) with k(B)≤n;(2)
ifA satisfies akk≥∑i=1naki (or akk≥∑i=1naik) for some k in N, then B converges to Bk(B) with k(B)≤n-1;(3)
ifB satisfies bkk≥∑i=1nbki (or bkk≥∑i=1nbik) for some k in N, then B converges to Bk(B) with k(B)≤n-1.Proof.
(1) Firstly,bii=aii (for all i∈N) since diag(A)≤B≤A. Since bii∈I(L), we have aii∈I(L). By Theorem 4.5, we can get aii=aii2=⋯=aiin for all i∈N.
It follows that any termT of the (i,j)th entry bijn of Bn is of the form bii1bi1i2⋯bin-1j, where 1≤i1,i2,…,in-1≤n. Since {i,i1,i2,…,in-1,j}⊂{1,2,…,n} and n+1>n, there are u, v such that iu=iv (0≤u<v≤n, i0=i,in=j). Then, T≤biuiu+1⋯biv-1iv and T≤bii1bi1i2⋯biu-1iubiviv+1⋯bin-1j. Since A is transitive, we have A≥Ak for all k≥1, and so aij≥aijk for all i,j∈N. Thus, biuiuv-u-1≥biuiu (because B∈I(L)) =aiuiu=aiuiuv-u≥biuiuv-u (because A≥B) ≥biuiu+1⋯biv-1iv≥T. Since bii1bi1i2⋯biu-1iubiuiuv-u-1biviv+1⋯bin-1j is the sum of some term in bijn-1, we have bijn-1≥bii1bi1i2⋯biu-1iubiuiuv-u-1biviv+1⋯bin-1j≥T (because B∈In(L)), and so bijn-1≥bijn  (because T is any term of bijn). Thus, Bn-1≥Bn.
Certainly,Bn≥Bn+1≥Bn+2≥⋯.
On the other hand, for any termT=bii1⋯bin-1j of bijn, there must be two indices iu and iv such that iu=iv for some u,v (0≤u<v≤n, i0=i, in=j). Then, T=bii1bi1i2⋯bin-1j=bii1bi1i2⋯biu-1iubiuiu+1⋯biv-1ivbiviv+1⋯bin-1j≤bii1bi1i2⋯biu-1iubiuiuv-ubiviv+1⋯bin-1j  (because biuiu+1⋯biv-1iv is a term of biuiuv-u) =bii1bi1i2⋯biu-1iubiuiuv-ubiuiuv-ubiviv+1⋯bin-1j(because B∈Mn(I(L))) ≤bijn+(v-u) (because bii1bi1i2⋯biu-1iubiuiuv-ubiuiuv-ubiviv+1⋯bin-1j is the sum of some term in bijn+(v-u);v-u≥1) ≤bijn+1 (because Bk≥Bk+1 for any k≥n-1). Thus, T≤bijn+1, and so bijn≤bijn+1. Therefore, Bn≤Bn+1.
Consequently, we haveBn=Bn+1. This completes the proof.
(2) By the proof of (1), we haveBn≤Bn-1. Hence, Bn-1≥Bn≥Bn+1≥Bn+2≥⋯. In the following, we will show that Bn-1≤Bn. It is clear that any term T of the (i,j)th entry bijn-1 of Bn-1 is of the form bii1bi1i2⋯bin-2j, where 1≤i,ii,i2,…,in-2, j≤n. Let i0=i and in-1=j.
Case 1.
Ifiu=iv for some u and v (u<v,v-u≥1), then T=bii1bi1i2⋯bin-2j=bii1bi1i2⋯biu-1iubiuiu+1⋯biv-1ivbiviv+1⋯bin-2j≤bii1bi1i2⋯biu-1iubiuiuv-ubiviv+1⋯bin-2j (because biuiu+1⋯biv-1iv is a term of biuiuv-u) =bii1bi1i2⋯biu-1iubiuiuv-ubiuiuv-ubiviv+1⋯bin-2j (because B∈Mn(I(L))) ≤bijn-1+(v-u) (because bii1bi1i2⋯biu-1iubiuiuv-ubiuiuv-ubiviv+1⋯bin-2j is the sum of some term in bijn-1+(v-u)) ≤bijn (because Bn-1≥Bn≥Bn+1≥⋯). Thus, T≤bijn, and so bijn-1≤bijn. Therefore, Bn-1≤Bn.Case 2.
Suppose thatiu≠iv for all u≠v. By the hypothesis akk≥∑i=1naki for some k, we have biuiu=aiuiu≥∑i=1naiui≥∑i=1nbiui  (because A≥B) ≥biuiu+1. Then, T=bii1bi1i2⋯bin-2j=bii1bi1i2⋯biu-1iubiuiu+1biu+1iu+2⋯bin-2j=bii1bi1i2⋯biu-1iubiuiu+1biuiu+1biu+1iu+2⋯bin-2j  (because B∈Mn(I(L))) ≤bii1bi1i2⋯biu-1iubiuiu+1biuiubiu+1iu+2⋯bin-2j(because biuiu≥biuiu+1) ≤bijn  (because bii1bi1i2⋯biu-1iubiuiu+1biuiubiu+1iu+2⋯bin-2j is a term of bijn). Thus, T≤bijn, and so bijn-1≤bijn. Therefore, Bn-1≤Bn.
The case ofakk≥∑i=1naik is similar to that of the hypothesis akk≥∑i=1naki.
Consequently, we haveBn-1=Bn.
(3) The proof of (3) is similar to that of (2). This completes the proof.Theorem4.7 generalizes and develops Theorem  4.1 of Tan [17].


## 5. Compositions of Transitive Matrices

In this section, we construct a transitive matrix from given incline matrices and construct a new incline matrix with some special properties from transitive matrices. We know that any idempotent matrix is also a transitive matrix.Theorem 5.1.
LetA=(aij)∈Mn(L). If A is transitive and row diagonally dominant, then B=(bij) is idempotent, where bij=aijaji.Proof.
For anyi, j in N, bij2=∑k=1nbikbkj=∑k=1naikakiakjajk=∑k=1n(aikakj)(ajkaki)≤∑k=1n(aijaji) (because A≥A2) =∑k=1nbij=bij. Thus, B2≤B. On the other hand, since bij2=∑k=1nbikbkj≥biibij=aiiaiiaijaji=aijaji (because A is row diagonally dominant) =bij. Thus, B2≥B. Therefore, B2=B. This completes the proof.Definition 5.2.
A∘D=C iff cij=∏k=1n(aik+dkj) for any i,j∈N.Theorem 5.3.
LetA=(aij)∈Mn(L) be a symmetric and nearly irreflexive matrix. Then, the matrix M=C∘A is idempotent, where C=(cij) with cii=ci∈L, cij=0 (i≠j).Proof.
By the definitions of the matricesA, C, and M, we have
(5.1)mij=(∏l≠ialj)(ci+aij)=(∏l≠iajl)(ci+aij)={aii+∏l≠ialici,i=j,ajj,i≠j.
The (i,j)th entry of M2 is mij2=∑k=1nmikmkj.
Case 1 (i≠j).
In this case,mij2=∑k≠i,jmikmkj+miimij+mijmjj=∑k≠i,jakkajj+(aii+∏l≠ialici)ajj+ajj(ajj+∏l≠jaljcj)=ajj(∑k=1nakk+∏l≠ialici+∏l≠jaljcj)=ajj (because A is nearly irreflexive) =mij.Case 2 (i=j).
In this case,mii2=∑l≠imilmli+mii=∑l≠iallaii+aii+∏k≠iakici=aii+∏k≠iakici (because A is nearly irreflexive) =mii.
Consequently, we can getM2=M. Therefore, M=C∘A is idempotent.Theorem5.3 generalizes Theorem  3.5 of Tan [20].Lemma 5.4.
LetA,B∈Mm×n(L), C∈Mn×l(L) and D∈Mp×m(L). Then,(1)
(B∘C)T=CT∘BT;(2)
IfA≤B, then D∘A≤D∘B and A∘C≤B∘C.The proof is trivial.Lemma 5.5.
LetA=(aij)∈Mm×n(L) be a nearly irreflexive matrix, then A∘AT is nearly irreflexive and symmetric.Proof.
LetS=A∘AT. Then, sii=∏l=1m(ail+ail)=∏l=1mail=aii (because A is nearly irreflexive). Thus, siisij=aii(∏l=1m(ail+ajl))=aii=sii, that is, S=A∘AT is nearly irreflexive. By Lemma 5.4, we have (A∘AT)T=(AT)T∘AT=A∘AT.Lemma5.5 generalizes Theorem  3.3 of Tan [20].Corollary 5.6.
LetA=(aij)∈Mn(L) be a nearly irreflexive matrix. Then, C∘(A∘AT) is idempotent, where C=(cij) with cii=ci∈L, cij=0 (i≠j).Proof.
It follows from Theorem5.3 and Lemma 5.5.Proposition 5.7.
LetA=(aij)∈Mn(L) be a symmetric and nearly irreflexive matrix. Then,(1)
A∘A≤A;(2)
A∘A is symmetric and nearly irreflexive.Proof.
(1) LetR=A∘A. Then, rij=∏l=1n(ail+alj)≤aii+aij=aiiaij+aij (because A is nearly irreflexive) =aij, so that A∘A≤A.
(2) LetR=A∘A. Since rji=∏l=1n(ajl+ali)=∏l=1n(ail+alj)=rij, we have R is symmetric. Since rii=∏l=1n(ail+ali)=∏l=1nail=aii (because A is nearly irreflexive), we can get riirij=aii(∏l=1n(ail+alj))=aii=rii. Thus, R is nearly irreflexive.Proposition5.7 generalizes Proposition  3.1 of Tan [20].Corollary 5.8.
LetA=(aij)∈Mn(L) be a symmetric and nearly irreflexive matrix. Then, C∘(A∘A) is idempotent, where C=(cij) with cii=ci∈L, cij=0 (i≠j).Proof.
It follows from Theorem5.3 and Proposition 5.7.Corollary5.8 generalizes Corollary  3.7 (1) of Tan [20].Corollary 5.9.
LetA=(aij)∈Mn(L) be a nearly irreflexive matrix. Then, (A∘AT)∘C is idempotent, where C=(cij) with cii=ci∈L, cij=0 (i≠j).The proof is trivial.Corollary5.9 generalizes Corollary  3.8 of Tan [20].Proposition 5.10.
LetA∈Mn(L) be irreflexive and transitive. Then,(1)
A∘AT=0, 0∈Mn(L);(2)
AT∘A=0, 0∈Mn(L).Proof.
(1) LetR=A∘AT. Then, rij=∏l=1n(ail+ajl)≤(aii+aji)(aij+ajj) (because A is irreflexive) =aijaji≤aii (because A is transitive) = 0. Therefore, R=0.
The proof of (2) is similar to that of (1). This proves the Proposition.Proposition5.10 generalizes Proposition  3.9 of Tan [20].Definition 5.11.
An inclineL̃ is said to be a Brouwerian incline if for any a,b∈L, there exists an element b→a∈L̃ such that bx≤a⇔x≤b→a.Obviously,b→a is the largest element x∈L̃ satisfying bx≤a.Definition 5.12.
A←D=C iff cij=∏k=1n(dkj→aik) for any i,j∈N.Lemma 5.13.
LetL̃ be a Brouwerian incline. Then, for any a∈L̃,(1)
a→a=1;(2)
1→a=a.The proof is trivial.Theorem 5.14.
LetA∈Mm×n(L̃). Then, A←AT is reflexive and transitive.Proof.
LetR=A←AT. Then, rij=∏k=1n(ajk→aik). Obviously, rii=∏k=1n(aik→aik)=1 (by Lemma 5.13 (1)). Thus, R is reflexive. Furthermore, since ajk(alk→aik)(ajk→alk)=(alk→aik)(ajk(ajk→alk)≤(alk→aik)alk≤aik, we have (alk→aik)(ajk→alk)≤ajk→aik. Therefore, rilrlj=∏k=1n(alk→aik)(ajk→alk)≤∏k=1n(ajk→aik)=rij, and so R2≤R. This proves the Theorem.Theorem5.14 generalizes Lemma  4.1 of Tan [20].Theorem 5.15.
LetA∈Mn(I(L̃)). Then, the following conditions are equivalent.(1)
A is reflexive and transitive;(2)
A←AT=A.Proof.
(1)⇒ (2). Let R=A←AT. Then, rij=∏k=1n(ajk→aik)≤ajj→aij=1→aij=aij (by Lemma 5.13(2)), and so R≤A. On the other hand, since aik≥aijajk for all i,j,k∈N, we have aij≤ajk→aik, and so aij≤∏k=1n(ajk→aik) (because A∈Mn(I(L̃)))=rij, that is, A≤R. Consequently, we have R=A←AT=A.
(2)⇒ (1). It follows from Theorem 5.14.Theorem5.15 generalizes Proposition  4.2 of Tan [20].Theorem 5.16.
LetA∈Mm×n(L̃). Then, (A←AT)A=A.Proof.
LetR=(A←AT)A. Then, rij=∑k=1m∏l=1n(akl→ail)akj≤∑k=1makj(akj→aij)≤∑k=1maij=aij, so that R≤A. On the other hand, since A←AT is reflexive (by Theorem 5.14), we have R=(A←AT)A≥A. Therefore, (A←AT)A=A.Theorem5.16 generalizes Lemma  4.3 of Tan [20].


## 6. On Canonical Form of an Incline Matrix

In this section, we will discuss the canonical form of an incline matrix. LetA be an n×n incline matrix. If there exists an n×n permutation matrix P such that F=PAPT=(fij) satisfies fij≮fji for i>j then, F is called a canonical form of A. The main results obtained here generalize the previous results on canonical form of a lattice matrix (see, e.g., [17]) and a fuzzy matrix (see, e.g., [12]).Definition 6.1.
LetA=(aij)∈Mn(L). For any i,j,k∈N with i≠j, i≠k, j≠k, if aik>aki and akj>ajk, we have aij>aji. Then, A is called a especially strongly transitive matrix.Lemma 6.2.
IfA=(aij)∈Mn(L) is especially strongly transitive matrix and A is put in the block forms
(6.1)A=(a11α1α2A1)=(A2β1β2ann),
where α1,α2T,β1,β2T∈L1×(n-1) and A1,A2∈Mn-1(L), then A1, A2, and PAPT are especially strongly transitive matrices for any permutation matrix P.The proof is similar to that of Lemma  3.1 in [14].Lemma 6.3.
LetA=(aij)∈Mm×n(L) and B=(bij)∈Mn×m(L). If A≮BT, then APT≮BTPT holds for any n×n permutation matrix P.The proof is omitted.Theorem 6.4.
IfA=(aij)∈Mn(L) is especially strongly transitive, then A has a canonical form.The proof is similar to that of Theorem  3.1 in [14].Theorem 6.5.
LetL be an incline and n an integer with n≥4. Then, for any n×n transitive matrix A over L, there exists an n×n permutation matrix P such that F=PAPT satisfies fij≮fji for i>j only if L is a linear incline.Proof.
Suppose thatL is not a linear incline. Then, w(L)≥2, and so that there must be two elements a and c in L such that a∥c. Therefore, ac<a<a+c and ac<c<a+c. Now, let A=aE12+cE23+aE34+cE41+acJn∈Mn(L), where Jn=(1)n×n.
It is easy to see thatA2≤A. This means A is transitive. Let P be any n×n permutation matrix. Then, there exists a unique permutation τ of the set {1,2,…,n} such that P=∑i=1nEτ(i)i, and so PT=∑i=1nEiτ(i). Therefore, F=(fij)n×n=PAPT=aEτ(1)τ(2)+cEτ(2)τ(3)+aEτ(3)τ(4)+cEτ(4)τ(1)+acJn. Thus, fτ(1)τ(2)=fτ(3)τ(4)=a, fτ(2)τ(3)=fτ(4)τ(1)=c and fτ(2)τ(1)=fτ(4)τ(3)=fτ(3)τ(2)=fτ(1)τ(4)=ac. Since τ is a permutation, we have τ(i)≠τ(j)(i≠j). By the hypothesis F=PAPT satisfies fij≮fji for i>j, we have τ(1)>τ(2), τ(2)>τ(3), τ(3)>τ(4), and τ(4)>τ(1). This implies τ(1)>τ(1), which leads to a contradiction. This proves the Theorem.Theorem6.5 generalizes Theorem  5.2 of Tan [17].Remark 6.6.
It is easy to verify thatA always has a canonical form for any transitive matrix A∈M2(L).



---

*Source: 164371-2011-10-31.xml*