On Generalized Transitive Matrices

Definition 2.1 (see [1].)A nonempty set L 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.

Proposition 2.2 (see [21].)Let L be an incline and a, b, c ∈ L. Then,

• (1)

  0 ≤ a ≤ 1;

• (2)

  if a ≤ 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.

Definition 2.3. A matrix A = (a_ij) ∈ M_n(L) is said to be

• (1)

  row diagonally dominant if a_ij = a_iia_ij for all i, j ∈ N;

• (2)

  column diagonally dominant if a_ij = a_ija_jj for all i, j ∈ N;

• (3)

  weakly diagonally dominant if for any i ∈ N, either a_iia_ij = a_ij for all j ∈ N or a_iia_ji = a_ji for all j ∈ N;

• (4)

  strongly diagonally dominant if a_ij = a_iia_ij = a_ija_jj for all i, j ∈ N;

• (5)

  nearly irreflexive if a_iia_ij = a_ii for all i, j ∈ N.

Lemma 2.4. I(L) is a distributive lattice, where I(L) = {a ∈ L∣a² = a}.

Lemma 3.1. For any A in M_n(L), we have $$.

Lemma 3.2. Let A ∈ M_n(L). Then,

• (1)

  for any i, j ∈ N with i ≠ j and any k ≥ n, there exists s (s ∈ {1,2, …, n − 1}) such that $$;

• (2)

  for any i ∈ N and any k ≥ n, there exists t ∈ N such that $$.

Proof. (1) Let $$ be any term of $$, where k ≥ n and 1 ≤ i, i₁, i₂, …, i_k−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 T₁ with m₁ ≤ k entries is obtained. If m₁ ≥ n, there must be a cycle in T₁, then we delete the cycle and obtain a new expression T₂ with m₂ ≤ m₁ entries. The deleting method can be applied repeatedly until the new expression T_s contains m_s < n entries. According to properties of the operation “·”, T ≤ T₁ ≤ ⋯≤T_s, but T_s is a term of the (i, j)th entry $$ of A^s for some s < n, we have $$, and so $$. This completes the proof.

(2) Let $$ be any term of $$, where k ≥ n + 1 and 1 ≤ i, i₁, i₂, …, i_k−1 ≤ n. Since the number of indices in T is greater than n, there must be two indices i_u and i_v such that i_u = i_v for some u, v (u < v). Then, we delete $$ from T and obtain a new expression $$ with m₁ ≤ k entries. If m₁ ≥ n + 1, there are still two identical numbers in the subscripts i, i₁, …, i_u−1, i_u, i_v+1, …, i_k−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 T_t with m_t ≤ n entries. According to properties of the operation “·”, T ≤ T₁ ≤ ⋯≤T_t, but T_t is a term of the (i, i)th entry $$ of A^t for some t ≤ n, we have $$, and so $$. This completes the proof.

Lemma 3.3. Let A ∈ M_n(L). Then,

• (1)

  $$ for any k ≥ 1;

• (2)

  $$ for any m ≥ n.

Proof. From Lemma 3.2, the proof is obvious.

Proposition 3.4. If A⁺ is reflexive, then (A⁺) ⁺ = A⁺.

Proof. Since A⁺ ≥ I_n, we have A⁺ ≤ (A⁺) ². On the other hand, by Lemmas 3.1 and 3.3, we see that (A⁺) ² ≤ A⁺. Hence, (A⁺) ⁺ = A⁺.

Proposition 3.5. For any A = (a_ij) ∈ M_n(L) with index, if A is column (or row) diagonally dominant, then A⁺ = A^s, where A^s is transitive.

Proof. We only consider the case A is column diagonally dominant.

For any integer l > 0, we have A^ls ≤ A^s since A^s is transitive, and so $$, for all i, j ∈ N. Since A is column diagonally dominant, we have $$ (because $$ is the sum of some term in $$) $$. Hence, $$, then A⁺ ≤ A^s. On the other hand, since $$ for any m ≥ n, we have A⁺ ≥ A^s. Therefore, A⁺ = A^s.

Corollary 3.6. For any A = (a_ij) ∈ M_n(L) with index, if A is strongly diagonally dominant, then A⁺ = A^s, where A^s is transitive.

Proof. Obviously, any strongly diagonally dominant matrix is column (or row) diagonally dominant. Hence, the conclusion follows from Proposition 3.5.

Proposition 3.7. For any A = (a_ij) ∈ M_n(L) with index, if A is weakly diagonally dominant, then A⁺ = A^s, where A^s is transitive.

Proof. Since A^s is transitive, we have A^s ≥ A^ls, and so $$, for any i, j ∈ N and any integer l > 0. Since A is weakly diagonally dominant, we have for any i ∈ N, either a_iia_ij = a_ij for all j ∈ N or a_iia_ji = a_ji for all j ∈ N.

Let

From above, we see that $$ for any i, j ∈ N. Hence, $$, then A⁺ ≤ A^s. On the other hand, since $$, we have A⁺ ≥ A^s. Therefore, A⁺ = A^s.

Proposition 3.8. Let A = (a_ij) ∈ M_n(L). If the entries of A satisfy a_iia_jk = a_jk (1 ≤ i, j, k ≤ n), then

• (1)

  A² ≤ A³;

• (2)

  $$ for all i ∈ N;

• (3)

  A converges to A^k(A) with k(A) ≤ n − 1.

Proof. (1) Since any term T of the (i, j)th entry $$ of A² is of the form $$, we have $$ (1 ≤ i, j, k ≤ n). Because the hypothesis a_iia_jk = a_jk, we can get $$. Since a_ika_kka_kj is a term of $$, we have $$.

Thus, A² ≤ A³.

(2) Because the hypothesis a_iia_jk = a_jk, we have a_iia_ii ⋯ a_ii = a_ii. Hence,

(3) Since A² ≤ A³, we have A^k−1 ≤ A^k (for any integer k ≥ 3), and so Aⁿ⁻¹ ≤ Aⁿ. Now we prove that Aⁿ⁻¹ ≥ Aⁿ. By (2), it is sufficient only to show that $$ for i ≠ j. Let

Lemma 3.9. Let A = (a_ij) ∈ M_n(L). If the entries of A satisfy a_iia_jk = a_jk (1 ≤ i, j, k ≤ n), then adj(A) = Aⁿ⁻¹.

Proposition 3.10. Let A = (a_ij) ∈ M_n(L). If the entries of A satisfy a_iia_jk = a_jk (1 ≤ i, j, k ≤ n), then (adjA) ⁺ = Aⁿ⁻¹.

Proof. By the Proposition 3.8, we have Aⁿ⁻¹ = Aⁿ. By Lemma 3.9, we can get adj(A) = Aⁿ⁻¹. Thus, (adjA) ⁺ = (Aⁿ⁻¹) ⁺ = Aⁿ⁻¹.

Corollary 3.11. Let A = (a_ij) ∈ M_n(L). If A is reflexive, then

• (1)

  A ≤ A²;

• (2)

  $$ for all i ∈ N;

• (3)

  A converges to A^k(A) with k(A) ≤ n − 1;

• (4)

  (adjA) ⁺ = Aⁿ⁻¹;

• (5)

  ((adjA) ⁺) ⁺ = Aⁿ⁻¹.

Proof. From Propositions 3.10 and 3.8, the proof is obvious.

Proposition 3.12. Let A = (a_ij) ∈ M_n(L). If L has no nilpotent elements and A is nilpotent, then

• (1)

  (adjA) ² = 0;

• (2)

  (adjA) ⁺ = adjA.

Proof. (1) The proof can be seen in [23].

(2) Form (1), the proof is obvious.

Proposition 3.13. Let A = (a_ij) ∈ M_n(L), A⁺ = (t_ij) _n×n, $$, then

• (1)

  $$;

• (2)

  $$;

• (3)

  $$ (for all i, j ∈ N and i ≠ j).

Proof. (1) Since (I_n + A) is reflexive, we have (I_n + A) is increasing. By Lemma 3.1, we can get the conclusion.

(2) By Corollary 3.11, (I_n + A) converges to $$ with k(I_n + A) ≤ n − 1. Thus, the conclusion is obtained.

(3) From (1) and (2), the proof is obvious.

Step 1. Compute successively

Step 2. Find (A⁺) _ij (i ≠ j).

Let $$ (i ≠ j). Stop.

Definition 4.1. Let A = (a_ij) ∈ M_n(L). For any i, j ∈ N, if a_ija_ik ≠ a_ik⇒a_ija_kj = a_kj holds for all k ∈ N, then A is called a strongly transitive matrix.

Theorem 4.2. If A = (a_ij) ∈ M_n(L) is a strongly transitive matrix, then A is transitive.

Proof. Since A is strongly transitive, for any i, j ∈ N, we have a_ija_ik = a_ik for all k ∈ N or a_ija_ik ≠ a_ik and a_ija_kj = a_kj for all k ∈ N.

Remark 4.3. If A is transitive, but A is not necessary to be a strongly transitive matrix.

Example 4.4. Consider the cline L = {0, a, b, c, 1} whose diagram is as Figure 1.

Let now

Then, A² ≤ A which means that A is transitive. But a₁₁a₁₂ = ca ≠ a₁₂ = a (because ca < a)⇏a₁₁a₂₁ = cb = a₂₁ = b (because cb < b), which means that A is not a strongly transitive matrix.

Theorem 4.5. Let A = (a_ij) ∈ M_n(L). If A ≥ A² and a_ii ∈ I(L) (for all i ∈ N), then

• (1)

  $$ for all i ∈ N;

• (2)

  A converges to A^k(A) with k(A) ≤ n.

Proof. (1) By the hypothesis A ≥ A², it follows that A^k ≥ A^k+1 (for all k ∈ N). Hence, Aⁿ ≥ Aⁿ⁺¹ and $$ (for all s ∈ N). Since a_ii ∈ I(L), we can get $$ (for all s ∈ N). Thus $$ and $$.

(2) By (1), it is sufficient to verify Aⁿ ≤ Aⁿ⁺¹.

Now, any term T of the (i, j)th entry $$ of Aⁿ is of the form $$, where 1 ≤ i₁, i₂, …, i_n−1 ≤ n. Since the number of indices in T is greater than n, there must be two indices i_u and i_v such that i_u = i_v for some u, v (0 ≤ u < v ≤ n, i₀ = i, i_n = j). Then, $$ (because $$ is a term of $$) $$$$ (because (1) $$ (for all i, s ∈ N) and a_ii ∈ I(L)) $$ (because $$$$ is the sum of some term in $$) $$ (because A^k ≥ A^k+1 for any k ∈ N). Thus, $$, and so $$. Therefore, Aⁿ ≤ Aⁿ⁺¹. This completes the proof.

Corollary 4.6. If A = (a_ij) ∈ M_n(L) is strongly transitive, then A converges to A^k(A) with k(A) ≤ n.

Proof. Since A is strongly transitive, by Theorem 4.2, we have A ≥ A² and a_ii ∈ I(L) (for all i ∈ N), the conclusion is obtained.

Theorem 4.7. Let A = (a_ij) ∈ M_n(L) be transitive. If B = (b_ij) ∈ M_n(I(L)) and diag (A) ≤ B ≤ A, where diag (A) = (c_ij) with c_ii = a_ii (for all i ∈ N) and c_ij = 0 (i ≠ j, i, j ∈ N). Then,

• (1)

  B converges to B^k(B) with k(B) ≤ n;

• (2)

  if A satisfies $$ (or $$) for some k in N, then B converges to B^k(B) with k(B) ≤ n − 1;

• (3)

  if B satisfies $$ (or $$) for some k in N, then B converges to B^k(B) with k(B) ≤ n − 1.

Proof. (1) Firstly, b_ii = a_ii (for all i ∈ N) since diag (A) ≤ B ≤ A. Since b_ii ∈ I(L), we have a_ii ∈ I(L). By Theorem 4.5, we can get $$ for all i ∈ N.

It follows that any term T of the (i, j)th entry $$ of Bⁿ is of the form $$, where 1 ≤ i₁, i₂, …, i_n−1 ≤ n. Since {i, i₁, i₂, …, i_n−1, j}⊂{1,2, …, n} and n + 1 > n, there are u, v such that i_u = i_v (0 ≤ u < v ≤ n, i₀ = i, i_n = j). Then, $$ and $$. Since A is transitive, we have A ≥ A^k for all k ≥ 1, and so $$ for all i, j ∈ N. Thus, $$ (because B ∈ I(L)) $$ (because A ≥ B) $$. Since $$ is the sum of some term in $$, we have $$ (because B ∈ I_n(L)), and so $$ (because T is any term of $$). Thus, Bⁿ⁻¹ ≥ Bⁿ.

Certainly, Bⁿ ≥ Bⁿ⁺¹ ≥ Bⁿ⁺² ≥ ⋯.

On the other hand, for any term $$ of $$, there must be two indices i_u and i_v such that i_u = i_v for some u, v (0 ≤ u < v ≤ n, i₀ = i, i_n = j). Then, $$ (because $$ is a term of $$) $$(because B ∈ M_n(I(L))) $$ (because $$ is the sum of some term in $$) $$ (because B^k ≥ B^k+1 for any k ≥ n − 1). Thus, $$, and so $$. Therefore, Bⁿ ≤ Bⁿ⁺¹.

Consequently, we have Bⁿ = Bⁿ⁺¹. This completes the proof.

(2) By the proof of (1), we have Bⁿ ≤ Bⁿ⁻¹. Hence, Bⁿ⁻¹ ≥ Bⁿ ≥ Bⁿ⁺¹ ≥ Bⁿ⁺² ≥ ⋯. In the following, we will show that Bⁿ⁻¹ ≤ Bⁿ. It is clear that any term T of the (i, j)th entry $$ of Bⁿ⁻¹ is of the form $$, where 1 ≤ i, i_i, i₂, …, i_n−2, j ≤ n. Let i₀ = i and i_n−1 = j.

(3) The proof of (3) is similar to that of (2). This completes the proof.

Theorem 5.1. Let A = (a_ij) ∈ M_n(L). If A is transitive and row diagonally dominant, then B = (b_ij) is idempotent, where b_ij = a_ija_ji.

Proof. For any i, j in N, $$ (because A ≥ A²) $$. Thus, B² ≤ B. On the other hand, since $$ (because A is row diagonally dominant) = b_ij. Thus, B² ≥ B. Therefore, B² = B. This completes the proof.

Definition 5.2. A∘D = C iff $$ for any i, j ∈ N.

Theorem 5.3. Let A = (a_ij) ∈ M_n(L) be a symmetric and nearly irreflexive matrix. Then, the matrix M = C∘A is idempotent, where C = (c_ij) with c_ii = c_i ∈ L, c_ij = 0 (i ≠ j).

Proof. By the definitions of the matrices A, C, and M, we have

Consequently, we can get M² = M. Therefore, M = C∘A is idempotent.

Lemma 5.4. Let A, B ∈ M_m×n(L), C ∈ M_n×l(L) and D ∈ M_p×m(L). Then,

• (1)

  (B∘C) ^T = C^T∘B^T;

• (2)

  If A ≤ B, then D∘A ≤ D∘B and A∘C ≤ B∘C.

Lemma 5.5. Let A = (a_ij) ∈ M_m×n(L) be a nearly irreflexive matrix, then A∘A^T is nearly irreflexive and symmetric.

Proof. Let S = A∘A^T. Then, $$ (because A is nearly irreflexive). Thus, $$, that is, S = A∘A^T is nearly irreflexive. By Lemma 5.4, we have (A∘A^T) ^T = (A^T) ^T∘A^T = A∘A^T.

Corollary 5.6. Let A = (a_ij) ∈ M_n(L) be a nearly irreflexive matrix. Then, C∘(A∘A^T) is idempotent, where C = (c_ij) with c_ii = c_i ∈ L, c_ij = 0 (i ≠ j).

Proof. It follows from Theorem 5.3 and Lemma 5.5.

Proposition 5.7. Let A = (a_ij) ∈ M_n(L) be a symmetric and nearly irreflexive matrix. Then,

• (1)

  A∘A ≤ A;

• (2)

  A∘A is symmetric and nearly irreflexive.

Proof. (1) Let R = A∘A. Then, $$ (because A is nearly irreflexive) = a_ij, so that A∘A ≤ A.

(2) Let R = A∘A. Since $$, we have R is symmetric. Since $$ (because A is nearly irreflexive), we can get $$. Thus, R is nearly irreflexive.

Corollary 5.8. Let A = (a_ij) ∈ M_n(L) be a symmetric and nearly irreflexive matrix. Then, C∘(A∘A) is idempotent, where C = (c_ij) with c_ii = c_i ∈ L, c_ij = 0 (i ≠ j).

Proof. It follows from Theorem 5.3 and Proposition 5.7.

Corollary 5.9. Let A = (a_ij) ∈ M_n(L) be a nearly irreflexive matrix. Then, (A∘A^T) ∘ C is idempotent, where C = (c_ij) with c_ii = c_i ∈ L, c_ij = 0 (i ≠ j).

Proposition 5.10. Let A ∈ M_n(L) be irreflexive and transitive. Then,

• (1)

  A∘A^T = 0, 0 ∈ M_n(L);

• (2)

  A^T∘A = 0, 0 ∈ M_n(L).

Proof. (1) Let R = A∘A^T. Then, $$ (because A is irreflexive) = a_ija_ji ≤ a_ii (because A is transitive) = 0. Therefore, R = 0.

The proof of (2) is similar to that of (1). This proves the Proposition.

Definition 5.11. An incline $$ is said to be a Brouwerian incline if for any a, b ∈ L, there exists an element $$ such that bx ≤ a⇔x ≤ b → a.

Definition 5.12. A ← D = C iff $$ for any i, j ∈ N.

Lemma 5.13. Let $$ be a Brouwerian incline. Then, for any $$,

• (1)

  a → a = 1;

• (2)

  1 → a = a.

Theorem 5.14. Let $$. Then, A ← A^T is reflexive and transitive.

Proof. Let R = A ← A^T. Then, $$. Obviously, $$ (by Lemma 5.13 (1)). Thus, R is reflexive. Furthermore, since a_jk(a_lk → a_ik)(a_jk → a_lk) = (a_lk → a_ik)(a_jk(a_jk → a_lk)≤(a_lk → a_ik)a_lk ≤ a_ik, we have (a_lk → a_ik)(a_jk → a_lk) ≤ a_jk → a_ik. Therefore, $$, and so R² ≤ R. This proves the Theorem.

Theorem 5.15. Let $$. Then, the following conditions are equivalent.

• (1)

  A is reflexive and transitive;

• (2)

  A ← A^T = A.

Proof. (1) ⇒ (2). Let R = A ← A^T. Then, $$ (by Lemma 5.13(2)), and so R ≤ A. On the other hand, since a_ik ≥ a_ija_jk for all i, j, k ∈ N, we have a_ij ≤ a_jk → a_ik, and so $$ (because $$) = r_ij, that is, A ≤ R. Consequently, we have R = A ← A^T = A.

(2) ⇒ (1). It follows from Theorem 5.14.

Theorem 5.16. Let $$. Then, (A ← A^T)A = A.

Proof. Let R = (A ← A^T)A. Then, $$, so that R ≤ A. On the other hand, since A ← A^T is reflexive (by Theorem 5.14), we have R = (A ← A^T)A ≥ A. Therefore, (A ← A^T)A = A.

Definition 6.1. Let A = (a_ij) ∈ M_n(L). For any i, j, k ∈ N with i ≠ j, i ≠ k, j ≠ k, if a_ik > a_ki and a_kj > a_jk, we have a_ij > a_ji. Then, A is called a especially strongly transitive matrix.

Lemma 6.2. If A = (a_ij) ∈ M_n(L) is especially strongly transitive matrix and A is put in the block forms

Lemma 6.3. Let A = (a_ij) ∈ M_m×n(L) and B = (b_ij) ∈ M_n×m(L). If A≮≮B^T, then AP^T≮≮B^TP^T holds for any n × n permutation matrix P.

Theorem 6.4. If A = (a_ij) ∈ M_n(L) is especially strongly transitive, then A has a canonical form.

Theorem 6.5. Let L 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 = PAP^T satisfies f_ij≮≮f_ji for i > j only if L is a linear incline.

Proof. Suppose that L 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 = aE₁₂ + cE₂₃ + aE₃₄ + cE₄₁ + acJ_n ∈ M_n(L), where J_n = (1) _n×n.

It is easy to see that A² ≤ 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 $$, and so $$. Therefore, F = (f_ij) _n×n = PAP^T = aE_τ(1)τ(2) + cE_τ(2)τ(3) + aE_τ(3)τ(4) + cE_τ(4)τ(1) + acJ_n. 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 = PAP^T satisfies f_ij≮≮f_ji 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.

Remark 6.6. It is easy to verify that A always has a canonical form for any transitive matrix A ∈ M₂(L).