REACHABILITY OF FUZZY MATRIX PERIOD

MARTIN GAVALEC, GÜNTER ROTE

Abstract. The computational complexity of the matrix period reachability (MPR) problem in a fuzzy algebra B is studied. Given an n × n matrix A with elements in B, the problem is to decide whether there is an n-vector x such that the sequence of matrix powers A, A^{2}, A^{3}, … has the same period length as the sequence Ax, A^{2}x, A^{3}x, … of iterates of x. In general, the MPR problem is NP-complete. Two conditions are described, which both together imply that MPR can be solved in O(n^{2}) time. If only one of the conditions is satisfied, the problem remains NP-complete.

1. Introduction

Power sequences of matrices in fuzzy algebra were studied by R. A. Cuninghame-Green [2]. The convergence and periodicity of special classes of matrices were studied by M. G. Thomason [9], and subsequently by many other authors. Li Jian-Xin [7, 8] considered the periodicity of fuzzy matrices in the general case and gave an upper estimate for the period of a matrix. The convergence of the power sequence of a square matrix in fuzzy algebra was studied using digraphs by K. Cechlárová [1], and a necessary and sufficient condition was given for a matrix A to be stationary.

The computational complexity of several problems connected with finding the exact value of the matrix and orbit period in a fuzzy algebra B was considered in [3]. It was shown that the period of a matrix A is the least common multiple of the periods of at most n non-trivial strongly connected components in threshold digraphs G(A, h) for some threshold levels h and an algorithm was suggested which enables to compute the matrix period in O(n^{3}) time.

On the other hand, the matrix period per(A) is the least common multiple of the orbit periods per(A, x) for all vectors x ∈ B(n). In [4], the question of reaching the matrix period by some orbit period is discussed. The reaching matrix period (MPR) problem is shown to be NP-complete in [5].

The aim of this paper is to discuss some conditions under which the MPR problem can be solved in polynomial time. To illustrate the situations that can occur in this problem, we start with three examples. We refer the reader to Section 2 for the precise definition of all terms.

Example 1. Let B = {0, 1} and let A ∈ B(n, n) be the adjacency matrix of the digraph G in Figure 1. The digraph consists of n = 13 vertices 0, 1, …, 12 in 3 disjoint cycles, C_{0}, C_{1}, C_{2}, of lengths 3, 4 and 6.

The digraph G is the threshold digraph of matrix A for threshold level h = 1, and the cycles C_{0}, C_{1}, C_{2} are its only (non-trivial) strongly connected components. The components periods are 3, 4, 6. Therefore, the matrix period per(A) is equal to

Date: April 4, 1997.

Key words and phrases. period of a matrix, orbit of a vector, minimax algebra, fuzzy algebra, NP-completeness.

[figure: 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12] Figure 1

lcm(3, 4, 6) = 12. The components are non-comparable, in the sense of the ordering of components of the digraph G, i.e., they are not connected by any walk in G. As a consequence of the non-comparability, the vector x ∈ B(n) defined on the vertex set by putting x(i) = 1 for i = 0, 3 and x(i) = 0 otherwise, has its orbit period per(A, x) = lcm(3, 4) = 12. That means that this instance of the MPR problem has the positive answer.

Let us remark that the same result we can obtain by putting, e.g., x′(i) = 1 for i = 4, 7 and x′(i) = 0 otherwise. In this case, the orbit period is per(A, x′) = lcm(4, 6) = 12. In general, we can choose two vertices, i_{0} ∈ C_{0} (or i_{0} ∈ C_{2}) and i_{1} ∈ C_{1} and put x(i) = 1 for i = i_{0}, i_{1} and x(i) = 0 otherwise.

[figure: 0; 1; 2; 3; 4; 5; 6] Figure 2

Example 2. A is the adjacency matrix of the digraph G on Figure 2. The digraph consists of n = 7 vertices 0, 1, …, 6 in 2 disjoint cycles C_{0}, C_{1}, of lengths 3 and 4. The cycles are connected with an arc leading from the vertex 2 to 3, i.e., C_{0} < C_{1}, in the ordering of components.

The cycles C_{0}, C_{1} are the only non-trivial strongly connected components. The component periods are 3 and 4 and the matrix period is per(A) = lcm(3, 4) = 12. However, in this case there is no vector x ∈ B(n) with the property per(A, x) = per(A). The reason is that the periods of both cycles have the greatest common divisor equal to 1, which implies that every large enough integer can be expressed as a linear combination with positive coefficients, of component periods 3, 4. As a consequence, for any vertex i ∈ C_{0} and j ∈ C_{1}, there are walks beginning in i and ending in j, of any given length greater than some value. If x(j) = 1 for some j, then the i-th coordinate in the orbit of vector x has eventually constant value 1, see Lemma 2.1 below. That means that the number 3 will not occur as a coordinate-orbit period of x. Thus, the orbit period per(A, x) will not be a multiple of 3. On the other hand, if x(j) = 0 for every vertex j ∈ C_{1}, then 4 cannot occur as the coordinate period and the orbit period per(A, x) will not be a multiple of 4.

Example 3. In this example the digraph G on Figure 3 consists of n = 10 vertices 0, 1, …, 9 in 2 disjoint cycles C_{0}, C_{1}, of lengths 4 and 6. The cycles are connected with an arc leading from the vertex 2 to 4, i.e., C_{0} < C_{1}. The situation differs from the previous example by the fact that the lengths of the cycles have a non-trivial common divisor 2.

[figure: 0; 1; 5; 6; 2; 4; 7; 3; 9; 8] Figure 3

Again, the cycles C_{0}, C_{1} are the only non-trivial strongly connected components. The component periods are 4 and 6 and the matrix period is per(A) = lcm(4, 6) = 12. In this case, we can find a vector x ∈ B(n) with the property per(A, x) = per(A). We choose two vertices, i ∈ C_{0} and j ∈ C_{1} and put x(i) = x(j) = 1 and x(k) = 0 otherwise. If there is a walk of odd length from i to j, then all walks from i to j have odd lengths and, by Lemma 2.1(ii), the i-th coordinate in the orbit sequence of x on odd positions eventually has constant value 1, while on even positions it oscillates between values 0 and 1. Thus, the i-th coordinate-orbit period is per(A, x, i) = 4. On the other hand, per(A, x, j) = 6 and, by Theorem 2.2(ii), the orbit period is per(A, x) = 12.

We may notice that, if we choose the vertices i ∈ C_{0} and j ∈ C_{1} in such a way that the walks from i to j have even lengths, then by a similar argument as above, the i-th coordinate in the orbit of vector x eventually has constant value 1 on even positions and 0 on odd positions, therefore per(A, x, i) = 2. Thus, the number 4 does not occur as a coordinate-orbit period of x and the orbit period is per(A, x) = 6.

Our three examples indicate that in searching for a vector solution of the equation per(A, x) = per(A), we have to find a system of strongly connected components with suitable periods and to choose a suitable system of vertices, one in each of these components. The exact formulation of this idea can be found in Theorem 3.5.

It can be easily seen that if the components can be found in such a way that they are pairwise non-comparable, then any choice of vertices (one vertex in each component) induces a solution of the MPR problem. If there exist comparable components in the theshold graph G(A, h), then the solvability of the problem depends on the greatest common divisors of the periods for comparable pairs of components.

In the paper, two conditions are described which together imply that MPR problem is polynomially solvable (Theorem 4.1). We show that if only one of the conditions is fulfilled, then MPR is NP-complete (Theorems 4.2 and 4.3).

4 MARTIN GAVALEC, GÜNTER ROTE

2. Matrix and orbit periods

In this section we define the notions mentioned informally in the introduction. For simpler notation of index sets we shall use the convention by which any natural number n is considered as the set of all smaller natural numbers, i.e., n = {0, 1, …, n−1}. By ℕ we denote the set of all non-negative integers. The greatest common divisor and the least common multiple of a set S ⊆ ℕ are denoted by the abbreviations gcd S and lcm S, respectively.

If G = (V, E) is a digraph (directed graph), then by a strongly connected component of G we mean a subdigraph K = (K, E ∩ K^{2}) generated by a non-empty subset K ⊆ V such that every vertex x ∈ K is reachable from every other vertex y ∈ K, and K is a maximal subset with this property. The vertex sets K of the strongly connected components form a partition of V. For i ∈ V, we denote by K[i] the unique strongly connected component to which i belongs. A strongly connected component K is called non-trivial if there is a cycle of positive length in K; otherwise, is is called trivial. By SCC^{∗}(G) we denote the set of all non-trivial strongly connected components of G. For any K ∈ SCC^{∗}(G), the period per(K) is defined as gcd of the lengths of all cycles in K. If K is trivial, then per(K) = 0.

Definition 2.1. The fuzzy algebra B is a triple (B, ⊕, ⊗), where B is a linearly ordered set and ⊕, ⊗ are the binary operations of maximum and minimum, respectively, on B. For any natural n > 0, B(n) denotes the set of all n-dimensional column vectors over B, and B(n, n) denotes the set of all square matrices of order n over B. For x ∈ B(n), A = (a_{ij}) ∈ B(n, n), we denote by x̄ and Ā the input sets { x_{i}; i ∈ n } and { a_{ij}; i, j ∈ n }, respectively. The matrix operations over B are defined formally in the same manner (with respect to ⊕, ⊗) as the matrix operations over a ring. For any A ∈ B(n, n), x ∈ B(n), the orbit of x generated by A is the sequence x^{(0)}, x^{(1)}, x^{(2)}, …, where x^{(r)} := A^{r}x.

Definition 2.2. Let A ∈ B(n, n), h ∈ B. Then the threshold digraph G(A, h) is the digraph G = (n, E), with the vertex set n = {0, 1, …, n − 1} and with the arc set E = { (i, j) : i, j ∈ n, a_{ij} ≥ h }. For any natural r and for any two vertices i, j of a graph G, we write i ⟶_{G}^{r} j if there is a walk of length r in G, beginning in vertex i and ending in j. If the graph G is understood from the context, we will simply write

i ⟶^{r} j.

The following lemma, which is due to Cechlárová [1], gives a connection between the existence of walks in threshold graphs and values of matrix powers A^{r} and orbit vectors x^{(r)}.

Lemma 2.1. Let A ∈ B(n, n), x ∈ B(n), h ∈ B, r ∈ ℕ, r ≥ 1, i, j ∈ n. Then

(i) (A^{r})_{ij} ≥ h ⇔ i ⟶_{G(A,h)}^{r} j

(ii) (A^{r}x)_{i} ≥ h ⇔ (∃j ∈ n)[ x_{j} ≥ h ∧ i ⟶_{G(A,h)}^{r} j ]

Proof. By induction on r.

Definition 2.3. Let A ∈ B(n, n), x ∈ B(n). The period of an infinite sequence a_{1}, a_{2}, … is the smallest positive number p for which there is an R such that for all r > R we have a_{r} = a_{r+p}, if such a number exists. The matrix period, the orbit period and the i-th coordinate-orbit period of x with respect to A, in notation: per(A), per(A, x) and per(A, x, i), are defined as the periods of the sequences A^{r}, x^{(r)}, or x_{i}^{(r)} (r = 1, 2, …), respectively.

The period of a set R ⊆ ℕ is the period of its characteristic sequence

a_{r} := \begin{cases}1 & if r ∈ R \\ 0 & otherwise. \end{cases}

Remark 2.1. By linearity of B, any element of any power of the matrix A is equal to some element of A. Therefore, the sequence of powers of A contains only finitely many different matrices. As a consequence, the periods per(A), per(A, x), per(A, x, i) are always well-defined.

The connection between matrix periods, orbit periods and coordinate-orbit periods is described by the following theorem.

Theorem 2.2. Let A ∈ B(n, n), x ∈ B(n). Then

(i) per(A) = lcm_{x∈B(n)} per(A, x)

(ii) per(A, x) = lcm_{i∈n} per(A, x, i)

Proof. It is easy to see that per(A) is a multiple of per(A, x) for any x ∈ B(n) and therefore, per(A) is a multiple of lcm_{x∈B(n)} per(A, x).

For the converse relation, let us assume that p is a common multiple of per(A, x) for all x ∈ B(n), i.e., for any x ∈ B(n) there is a number R_{x} such that (∀r > R_{x}) x^{(r)} = x^{(r+p)}. In general, there are infinitely many vectors x ∈ B(n), but we can restrict our consideration to only finitely many of R_{x}, because the orbit period of a given vector x ∈ B(n) depends only on the way in which the elements of x̄ are comparable with all elements of Ā and there are only finitely many possibilities for placing the elements of x̄ between the elements of Ā. Therefore, there are only finitely many equivalence classes in B(n) with respect to the comparability with elements of Ā (in the sense that x, x′ ∈ B(n) are equivalent if and only if (∀i, j, k ∈ n)[ a_{ij} ≤ x_{k} ⇔ a_{ij} ≤ x′_{k}] ). Thus, we may conclude that

(∃R ∈ ℕ)(∀r > R)(∀x ∈ B(n)) x^{(r)} = x^{(r+p)}.

By the simple fact that A = B ⇔ (∀x ∈ B(n)) Ax = Bx, we get

(∃R ∈ ℕ)(∀r ∈ R) A^{(r)} = A^{(r+p)}

i.e., p is a multiple of per(A).

The assertion (ii) is proved analogously.

Definition 2.4. Let A ∈ B(n, n), h ∈ B, let G(A, h) be a threshold digraph of A. Recall that SCC^{∗} G(A, h) denotes the set of all non-trivial strongly connected components of G(A, h).

(i) SCC^{∗}(A) := ⋃ { SCC^{∗} G(A, h) : h ∈ Ā } (ii) SCC^{min}(A) := { K ∈ SCC^{∗}(A) : K is minimal in (SCC^{∗}(A), ⊆) }

The period of a matrix in max-min (fuzzy) algebra is characterized by the periods of the non-trivial strongly connected components in the threshold graphs of the matrix:

Theorem 2.3. [3] Let A ∈ B(n, n). Then

(i) per(A) = lcm { per(K); K ∈ SCC^{∗}(A) } (ii) per(A) = lcm { per(K); K ∈ SCC^{min}(A) }

6 MARTIN GAVALEC, GÜNTER ROTE

3. Reachability of the matrix period

In view of Theorem 2.2(i), a natural question arises: under which conditions is the value of the matrix period achieved by some orbit period [5]?

Definition 3.1. Matrix Period Reachability Problem (MPR)

Given a matrix A ∈ B(n, n), is there x ∈ B(n) such that per(A) = per(A, x)?

In this section we show that if an instance of MPR problem has a solution, then the solution can be represented in a standard form, which will be described in Theorem 3.5. This result is in accordance with our observations made by the examples described in the introduction.

The following definition and lemma are crucial for investigating the periodicity of the orbit sequence ( x^{(r)}; r = 1, 2, …), since they establish a connection with the periods of paths and components in a digraph.

Definition 3.2. For vertices i and j in a digraph G, we denote by W (i, j) the set of all elementary paths from i to j (i.e., walks with distinct vertices) in a digraph. For any walk w we define

per(w) = gcd{ per(K) : K ∈ SCC^{∗}(G) ∧ K ∩ w ≠ ∅ }

and we denote

R(i, j, w) := { r ∈ ℕ : there is a walk w′ from i to j with r arcs and w ⊆ w′ }.

Remark 3.1. If the walk w meets no non-trivial component K ∈ SCC^{∗}(G), then by Definition 3.2, per(w) = 0 holds true and R(i, j, w) contains the only element |w|.

The notation of per(w) as the period of the walk w is justified by part (ii) of the following lemma.

Lemma 3.1. For any digraph G, there are numbers R_{1} and R_{2} for which the following holds.

(i) If a vertex i is contained in a component K, then

(∀r > R_{1})[ r ≡ 0 mod per(K) ⇔ i ⟶^{r} i ]  (3.1)

(ii) For any two vertices i and j and for any w ∈ W (i, j), we have

(∀r > R_{2})[ r ≡ |w| mod per(w) ⇔ r ∈ R(i, j, w) ]

(iii) For any two vertices i and j and for any walk w from i to j, we have

(∀r > R_{2})[ r ≡ |w| mod per(w) ⇒ i ⟶^{r} j ]

Proof. In part (i), the existence of R_{1} for any specific vertex i follows from the definition of per(K). As the number of vertices is finite, we can take R_{1} large enough such that (3.1) holds for all vertices i in G.

For part (ii), we first note that if w does not meet any K ∈ SCC^{∗}(G), then, by remark 3.1, per(w) = 0 and the statement of the lemma is trivially fulfilled. Now, we show that whenever K ∈ SCC^{∗}(G) is a non-trivial component with K ∩ w ≠ ∅, then

r ∈ R(i, j, w) ∧ c ∈ ℕ ∧ c · per(K) ≥ R_{1} ⇒ r + c · per(K) ∈ R(i, j, w).

If k ∈ K ∩ w for some K ∈ SCC^{∗}(G), then, by part (i) of the lemma, there is a cycle C through k with c · per(K) arcs whenever c · per(K) ≥ R_{1}. This cycle may be added to w to obtain a walk of length r + c · per(K) from i to j. Since per(w) is the greatest common divisor of per(K) for all non-trivial components K ∈ SCC^{∗}(G) which meet w, then, by a well-known theorem of number theory, any big enough multiple of per(w) can be expressed as a linear combination, with positive coefficients, of the corresponding compoment periods per(K). Therefore, if the set R(i, j, w) contains an element r in some congruence class modulo per(w), then all larger elements in that congruence class are also contained in R(i, j, w). Thus, R(i, j, w) contains either all elements of any give congruence class except a finite number, or none at all. Since there are only finitely many congruence classes, finitely many vertices i and j, and finitely many elementary paths w, R_{2} can be selected large enough so that the statement of the lemma is fulfilled.

For part (iii), note first that we may assume w.l.o.g. that w is an elementary path. If w contains a vertex k twice, the cycle C that w forms between the first and last visit to k has a length which is a multiple of per(K[k]). Thus, if we clip C out of w, the length r mod per(w) remains unchanged. Furthermore, C does not touch any additional components, by the definition of strongly connected components. Thus, the set of components K in the definition of per(w) is also unchanged. By repeatedly deleting cycles out of w, we eventually arrive at an elementary path with less that n arcs that has the same period per(w) and the same length modulo per(w) as the original walk. The statement of the lemma is now a simple consequence of part (ii).

The following sequence of lemmas will allow us to convert a given vector x into another vector that has the same orbit period per(A, x) and satisfies additional contraints. For a given vector x ∈ B(n) and for given h ∈ B, we denote

S(x, h) := { i ∈ n : x(i) ≥ h }.

For i ∈ n, we denote by K[i, h] the uniquely determined strongly connected component in G(A, h) containing the vertex i.

Lemma 3.2. Let A ∈ B(n, n), x ∈ B(n). Then there is vector x′ ∈ B(n) with per(A, x′) = per(A, x), such that any vertex i ∈ S(x′, h) is contained in a non-trivial component of the threshold digraph G(A, h), for any h ∈ B.

Proof. Let H = { h_{k}; k ∈ s } = Ā ∪ x̄ be the union of the input sets of A and x, in descending order. We shall proceed by recursion through H. We take h = h_{k} ∈ H and we assume that for any h_{l} > h, the assertion of lemma holds true. Then we modify x to x′ by the following two rules (all walks mentioned in the proof are in digraph G(A, h)).

1. For any j ∈ S(x, h) with K[j, h] trivial, we define x′(j) = h_{k+1} (i.e., j is left out of S(x, h), but it remains in S(x, h_{l}) for any h_{l} ∈ H, h_{l} < h).

2. For any j ∈ S(x, h) with K[j, h] trivial and for any w : i ⟶^{s} j such that i is the only vertex in w with non-trivial component K[i, h], we choose a vertex j_{w} ∈ K = K[i, h] such that i ⟶^{s} j_{w}. As K is non-trivial, such a vertex j_{w} can always be found in K. Then we set x′(j_{w}) = max(h, x(j_{w})), (i.e., j_{w} is added to S(x, h) but not to S(x, h_{l}) for h_{l} ∈ H, h_{l} > h), if it has not already been there).

All remaining values x(j) are unchanged at this stage of recursion. We may notice that the rules 1, 2 apply only to vertices j with x(j) = h. Namely, if x(j) < h, then j ∉ S(x, h) and if x(j) > h, then, by recursion assumption, K[j, h] is non-trivial. In view of Lemma 2.1(ii) and Theorem 2.2, it is sufficient to verify that for any i ∈ n and for any big enough r, the equality (A^{r}x)_{i} = (A^{r}x′)_{i} holds true, i.e., the following two formulas are equivalent:

(∃j ∈ n)[ x(j) ≥ h ∧ i ⟶^{r} j ], (∃j′ ∈ n)[ x′(j′) ≥ h ∧ i ⟶^{r} j′ ].

Let the first formula be fulfilled, in other words, let there be j ∈ n such that x(j) ≥ h and w : i ⟶^{r} j. If r is big enough, then the walk w cannot be an elementary path, i.e., w must meet some non-trivial component in G(A, h). If the component K[j, h] is non-trivial, then we have x′(j) = x(j) and the second formula holds true. If the component K[j, h] is trivial, then we denote by i_{1} the last vertex in w with non-trivial K[i_{1}, h] = K and we denote w_{1} := w(i_{1}, j) (the subwalk of w from i_{1} to j). By the rule 2 of the definition of x′, there is a vertex j′ = j_{w_{1}} ∈ K and a walk w′_{1} : i_{1} ⟶^{s} j′ such that s = |w_{1}| and x′(j′) ≥ h. If we denote w_{0} := w(i, i_{1}), then the walks w = w_{0}w_{1} and w′ = w_{0}w′_{1} are of the same length r and, therefore, the second formula holds true.

Conversely, let the second formula be fulfilled, i.e. let j′ ∈ n such that x′(j′) ≥ h and w : i ⟶^{r} j′. By the definition of x′, the component K := K[j′, h] is non-trivial. If x(j′) ≥ h, then the first formula holds true. If x(j′) < h, then there are vertices i_{1} ∈ K, j ∉ K and walks w_{1} : i_{1} ⟶^{s} j, w′_{1} :⟶^{s} j′ such that x(j) ≥ h and i_{1} is the only vertex in w_{1} with non-trivial component K[i, h] = K. We choose a walk u : j′ ⟶^{t} i_{1}, u ⊆ K. The concatenation c = uw′_{1} is a cycle in K and, therefore, the length s + t of c is a multiple of per(K) and r − s ≡ r + t mod per(K). As r is big enough, we can assume that r − s > R_{2}, and as per(K) is a multiple of per(w) = per(wu), we have r − s ≡ r + t mod per(wu). By Lemma 3.1(iii) applied to the concatenation wu of length r + t we get a walk w_{0} : i ⟶^{r−s} i_{1}. Then w_{0}w_{1} : i ⟶^{r} j and the first formula holds true.

The key notions in Theorem 3.5 are the notion of dominance of vertices in a digraph G and the notion of deciding components in SCC^{∗}(G).

Definition 3.3. Let i, j ∈ n, h ∈ B. We say that j dominates i at level h (in notation: i ⪯_{h} j), if

(∃R ∈ ℕ)(∀r > R)(∀k ∈ n) [ k ⟶_{G(A,h)}^{r} i ⇒ k ⟶_{G(A,h)}^{r} j ] .

Remark 3.2. For fixed h, the relation ⪯_{h} is reflexive and transitive (i.e., ⪯_{h} is a quasi-order on n). Note that the threshold R := R_{ijh} in Definition 3.3 may depend on i, j and h. By taking the maximum R of the finitely many numbers R_{ij}, (for i, j ∈ n, h ∈ Ā) we have a global constant R with the property:

i ⪯_{h} j ⇒ (∀r > R)(∀k ∈ n) [ k ⟶_{G(A,h)}^{r} i ⇒ k ⟶_{G(A,h)}^{r} j ] .  (3.2)

Remark 3.3. If the component K = K[i, h] is non-trivial, then, in view of Lemma 3.1, i ⪯_{h} j holds true if and only if

(∀r > R) [ i ⟶_{G(A,h)}^{r} i ⇒ i ⟶_{G(A,h)}^{r} j ]

which can be equivalently expressed as

(∀r > R) [ r ≡ 0 mod per(K) ⇒ i ⟶_{G(A,h)}^{r} j ] or,

(∃r > R) [ r ≡ 0 mod per(K) ∧ i ⟶_{G(A,h)}^{r} j ]  (3.3)

Lemma 3.3. Let A ∈ B(n, n), x ∈ B(n). Then there is vector x′ ∈ B(n) such that per(A, x′) = per(A, x) and any vertex i ∈ n with x′(i) = h > min(Ā) is not dominated at level h by any vertex j ≠ i with x′(j) ≥ x′(i).

Proof. If there are vertices i ≠ j such that min(Ā) < h = x(i) ≤ x(j) and i ⪯_{h} j, then we denote by h′ the precedessor of h in Ā ∪ x̄ and define

x′(k) := \begin{cases}h′ & if k = i \\ x(k) & otherwise. \end{cases}

In view of Lemma 2.1(ii), the vectors x, x′ have the same orbits and, therefore, per(A, x) = per(A, x′). The procedure is repeated finitely many times, until x′ has the desired property.

Remark 3.4. As K[i, h] ⊆ K[i, h′] holds true for h ≥ h′, the procedure in the above proof preserves the property of vector x′, formulated in Lemma 3.2.

The following lemma provides a lower bound for the period of a sequence, if the period of some subsequence is known.

Lemma 3.4. If a sequence a_{1}, a_{2}, … has period p, then the period of the subsequence a_{d}, a_{2d}, a_{3d}, … formed by taking every d-th element divides p/ gcd(p, d).

Proof. Since p divides lcm(p, d) = pd/ gcd(p, d), we have

a_{id} = a_{id+pd/ gcd(p,d)} = a_{(i+p/ gcd(p,d))d},

for large enough i, and hence p/ gcd(p, d) is a multiple of the period of the subsequence.

Definition 3.4. Let per(A) = p_{0}^{α_{0}}p_{1}^{α_{1}} … p_{k−1}^{α_{k−1}} be a decomposition of the matrix period per(A) into powers of distinct primes. Then a subset D ⊆ SCC^{∗}(A) which contains a component K with p_{t}^{α_{t}} | per(K), for all t = 0, …, k −1, is called a deciding set of components.

Theorem 3.5. For any A ∈ B(n, n), the following statements are equivalent.

(i) There is x ∈ B(n) such that per(A, x) = per(A). (ii) There is a deciding set D of pairwise disjoint components at levels H = { h_{K}; K ∈

D ∧ K ∈ SCC^{∗}(G(A, h_{K})) } and a set I = { i_{K} ∈ K : K ∈ D } of vertices, with one vertex chosen from each component in D, such that, if h_{K} ≤ h_{L}, K ≠ L, then the vertex i_{L} does not dominate i_{K} at level h_{K}.

Proof. (ii) ⇒ (i): We define a vector x ∈ B(n) in the following way: we put

x(i) := \begin{cases}h_{K} & if i = i_{K} for some K ∈ D \\ min(Ā) & otherwise. \end{cases}

By Theorem 2.2(ii), it is sufficient to prove that

(∀t ∈ k)(∃i ∈ n) p_{t}^{α_{t}} | per(A, x, i).

Let t ∈ k be fixed and let K ∈ D be a maximal component with the property p_{t}^{α_{t}} | per(K) (maximal in the sense of the ordering induced by G(A, h_{K})). We denote by i := i_{K} the vertex chosen by the system I. All the walks in this part of the proof are understood in the theshold digraph G := G(A, h_{K}). We will first show that

(∃R ∈ ℕ)(∀r > R) [( r ≡ 0 mod per(K)/p_{t}) ⇒ ( x^{(r)}(i) = h_{K} ⇔ r ≡ 0 mod per(K) )] .

By Lemma 2.1 and by Lemma 3.1(i) we can conclude that per(K) | r implies x^{(r)}(i) ≥ h_{K}, for big enough r. By the non-dominance assupmtion and by (3.3) we get x^{(r)}(i) = h_{K}. Now, if we had x^{(r)}(i) = h_{K} for some r with (per(K)/p_{t}) | r and per(K) /| r, this can only happen if i ⟶^{r} j for some j ∈ I which was selected from another component K′. By the maximality of K we know that p_{t}^{α_{t}} /| per(K′), and hence, applying Lemma 3.1(iii), we conclude that i ⟶^{r′} j for all large enough r′ with r′ ≡ r mod per(w). Since p_{t}^{α_{t}} /| per(w), we have gcd(p_{t}^{α_{t}}, per(w)) | p_{t}^{α_{t}−1} | (per(K)/p_{t}), and the two equations r′ ≡ r mod per(w), r′ ≡ 0 mod per(K) have infinitely many solutions. So we have i ⟶^{r′} j for some r′ ≡ 0 mod per(K). This means that i ⪯_{h_{K}} j, contradicting the assumption of non-dominance of vertices in I.

We have seen that the subsequence (x^{(r)}(i)) of all elements with r ≡ 0 mod per(K)/p_{t} has period p_{t}. Applying Lemma 3.4 with increment d = per(K)/p_{t}, we obtain that p_{t} · gcd(per(K)/p_{t}, per(A, x, i)) = gcd(per(K), p_{t} · per(A, x, i)) divides per(A, x, i), and hence gcd(p_{t}^{α_{t}}, p_{t} · per(A, x, i)) | per(A, x, i), from which it follows that p_{t}^{α_{t}} | per(A, x, i).

(i) ⇒ (ii): Let x ∈ B(n), per(A) = per(A, x). By Lemma 3.3, we may assume that x fulfills the non-dominance requirement: any vertex i ∈ n with x(i) = h > min(Ā) is not dominated at level h by any vertex j ≠ i with x(j) ≥ x(i). By Lemma 3.2 and Remark 3.4, we may assume that any vertex i ∈ S(x, h) is contained in a non-trivial component of G(A, h).

We only have to ensure that, for every t ∈ k, there is a level h ∈ Ā ∪ x̄ such that S(x, h) contains a vertex j in a component K ∈ SCC^{∗}(G(A, h)) with p_{t}^{α_{t}} | per(K). We prove this by contradiction. Suppose that there is a t such that, for all h ∈ Ā ∪ x̄ and for all j ∈ S(x, h), we have p_{t}^{α_{t}} /| per K[j, h]. By Lemma 2.1, for any h ∈ Ā ∪ x̄ and i ∈ n we have (the notation W (i, j, h), R(i, j, w, h) per(w, h) is used for objects W (i, j), R(i, j, w) per(w) defined with respect to the threshold digraph G = G(A, h)):

x^{(r)}(i) ≥ h ⇔ (∃j ∈ S(x, h)) i ⟶^{r} j

⇔ (∃j ∈ S(x, h))(∃w ∈ W (i, j, h)) r ∈ R(i, j, w, h)

⇔ r ∈ R(i, h) := ⋃_{j∈S(x,h)} ⋃_{w∈W (i,j,h)} R(i, j, w, h)

Under the above assumption, we have p_{t}^{α_{t}} /| per(w, h), for all possible paths w in this statement, since per(w, h) is defined as the gcd of the periods of certain components which include the component K[j, h], whose period is not a multiple of p_{t}^{α_{t}}. By Lemma 3.1(ii), the set R(i, j, w, h) is periodic with period per(w, h). It follows that the set R(i, h), being a finite union of sets R(i, j, w, h), is also periodic, and its period divides

lcm{ per(w, h) : j ∈ S(x, h), w ∈ W (i, j, h) },

which is not a multiple of p_{t}^{α_{t}}. It is easy to see that per(A, x, i) divides the lcm of the periods of sets R(i, h) for h ∈ Ā ∪ x̄ and, therefore, it is not a multiple of p_{t}^{α_{t}}, for arbitrary i. Then, by Theorem 2.2(ii), the orbit period per(A, x) = lcm_{i∈n} per(A, x, i) is not a multiple of p_{t}^{α_{t}}. Hence, per(A, x) is different from per(A), which contradicts to our assumption (i).

Now, in view of the facts that two components K, L ∈ SCC^{∗}(A) are either disjoint or comparable, and if K ⊆ L, then per(L) | per(K), we can easily choose a deciding system D of pairwise disjoint components and the sets H, I satisfying the statement (ii).

4. The computational complexity of the MPR problem

It was shown in [5] that, in general, the MPR problem is NP-complete. We describe here two conditions under which the problem is polynomially solvable.

By Theorem 3.5, the solving of the problem MPR is equivalent to performing two choices: we have to choose a suitable deciding set of components in such a way that it is possible to choose a set of pairwise non-dominating vertices, by one from each component. In spite of the fact that the problem of performing these two choices is NP-complete, we may hope that under some restrictive conditions it can be solved in polynomial time.

Similar situation occurs with the classical satisfiability problem (SAT) for disjunctive boolean formulas. If the number of variables in each disjunctive clause is restricted to 2, the problem 2-SAT is polynomially solvable. However, it is a wellknown fact, that the restriction to 3-disjunctive formulas is not sufficient: the problem 3-SAT remains NP-complete.

Theorem 4.1. MPR problem with two restrictive conditions

(i) the matrix A has a unique minimal deciding set of components, (ii) there is a deciding set D of components such that for any components K, L ∈ D

at levels h ≤ h′ with K < L in G(A, h), gcd(per(K), per(L)) ≤ 2 holds true, is solvable in time O(n^{2}) for a given matrix A ∈ B(n, n).

Proof. It is easy to show using Theorem 2.3, that there is always at least one minimal deciding set D of components, which is necessarily disjoint. Thus, condition (i) reduces the problem to the choice of pairwise non-dominating vertices in D. Condition (ii) implies that, for any comparable components K, L ∈ D, we have gcd(per(K), per(L)) = 1, or gcd(per(K), per(L)) = 2.

If the first case occurs for some h ≤ h′ and for K, L ∈ D, K ∈ SCC^{∗}(G(A, h)), L ∈ SCC^{∗}(G(A, h′)), with K < L in G(A, h), then for any i ∈ K, j ∈ L, the vertex i is dominated by j at level h and the instance of MPR has no solution.

If the second case takes place for all comparable pairs K, L ∈ D, then the dominancy i ⪯_{h} j for i ∈ K ∈ SCC^{∗}(G(A, h)), j ∈ L ∈ SCC^{∗}(G(A, h′)), h ≤ h′ depends only on the parity of the positions of the vertices i, j and on the existence or nonexistence of a walk w in digraph G(A, h), of even length and connecting points of the same parity in components K, L, or of odd length and connecting points of different parities in K and L. Therefore, the choice of pairwise non-dominating vertices in D is equivalent to the choice of pairwise compatible representatives from a system of n two-element sets. It is shown in [6] that such a choice can be performed in time O(n^{2}).

The conditions (i), (ii) in Theorem 4.1 may seem rather restrictive. However, the next two theorems show that each of the conditions alone is too weak to make the MPR problem polynomially solvable.

Theorem 4.2. The MPR problem with the restrictive condition (i) from Theorem 4.1 is NP-complete.

12 MARTIN GAVALEC, GÜNTER ROTE

Proof. As a special case of MPR, the problem belongs to NP. We show that the well-known NP-complete problem of 3-colouring for graphs (3-COL) polynomially transforms to MPR(i) problem (i.e., MPR with the restrictive condition (i)). We describe a polynomial algorithm which assigns, to any instance of 3-COL, such an instance of MPR(i) that both instances are equivalent, i.e., they have the same answer yes or no.

Let G′ = (V′, E′) be an instance of 3-COL, let us denote m′ = |V′|, n′ = |E′|. We choose m′ + n′ distinct primes

(p_{v}; v ∈ V′), (q_{e}; e ∈ E′)

and we define a digraph G = (V, E) consisting of m′ + n′ disjoint oriented cycles

(C_{v}; v ∈ V′), (D_{e}; e ∈ E′)

of lengths

|C_{v}| = 3p_{v}, |D_{e}| = 3q_{e} for any v ∈ V′, e ∈ E′.

The vertices in each cycle are numbered beginning with 0, in the sense of the orientation. The vertices will be referred to by the notation C_{v}(i), D_{e}(j). Besides the arcs contained in the cycles, there are additional arcs between cycles in G, defined as follows: we fix a linear ordering ≤ of vertices in V′ and for any edge e = (u, v) ∈ E′, u ≤ v we add the arcs (D_{e}(0), C_{u}(0)), (D_{e}(0), C_{u}(2)), (D_{e}(0), C_{v}(1)) to E.

[figure: C_{u}; 0; 1; 2; 2; C_{v}; 0; 1; 2; D_{e}; 0; 1; 2] Figure 4

The additional arcs are schematically drawn on Figure 4. For the sake of simplicity, the cycles C_{u}, C_{v}, D_{e}, are depicted with 3 vertices only. This simplification is based on the fact that the greatest common divisor of the periods of the cycles is equal to 3.

The matrix A is defined as the adjacency matrix of the digraph G. Denoting B = {0, 1} and n = 3(m′ + n′), we have A ∈ B(n, n). Clearly, A has exactly one deciding set of components, namely the set of all cycles { C_{v} : v ∈ V′ } and { D_{e} : e ∈ E′ }. Therefore, A is an instance of MPR(i). By the well-known properties of prime numbers, the construction of A is polynomial with respect to the size of G′. In the following we show that the instances A and G′ are equivalent.

Let A be a yes instance of MPR(i). By Theorem 3.5, there is a set

I = { i_{u} ∈ C_{u} : u ∈ V′ } ∪ { j_{e} ∈ D_{e} : e ∈ E′ }

of pairwise non-dominating vertices in G (at level 1).

We shall show that the graph G′ is a yes-instance of 3-COL, i.e., there is a colouring F: V′ → {0, 1, 2} with F (u) ≠ F (v) for every e = (u, v) ∈ E′. The colouring F is defined for any u ∈ V′, k ∈ ℕ by the formula

F (u) := \begin{cases}0 & if i_{u} = C_{u}(3k) \\ 1 & if i_{u} = C_{u}(3k + 1) \\ 2 & if i_{u} = C_{u}(3k + 2) \end{cases}

Let us suppose that F (u) = F (v) for some e = (u, v) ∈ E′, u ≤ v. If F (u) = F (v) = 0, then the vertex i_{u} = C_{u}(3k) dominates all the vertices of the form D_{e}(3l + 1), D_{e}(3l + 2) and the vertex i_{v} = C_{v}(3k) dominates all the vertices D_{e}(3l). As a consequence, the vertex j_{e} is dominated either by i_{u} or by i_{v}. The assumption F (u) = F (v) = 1, or F (u) = F (v) = 2 leads to contradiction in a similar way. Therefore, F (u) ≠ F (v) holds true for any adjacent vertices of the graph G′.

Conversely, let G′ be a yes-instance of 3-COL with the colouring F: V′ → {0, 1, 2}. Then we define i_{u} = C_{u}(F (u)) for any u ∈ V′ and j_{e} = D_{e}(F (u)) for any e = (u, v) ∈ E′, u ≤ v. By the above reasoning, the vertex i_{u} does not dominate j_{e}. The adjacency property of F implies that the vertex i_{v} does not dominate j_{e}, as well. Therefore by Theorem 3.5, the matrix A is a yes-instance of MPR(i).

Remark 4.1. To underline the analogy with 2-SAT and 3-SAT, we may notice that Theorem 4.2 holds true even if the modified condition (ii), with 3 instead of 2, is added.

Theorem 4.3. The MPR problem with the restrictive condition (ii) from Theorem 4.1 is NP-complete.

Proof. It is shown in [5] that the NP-complete problem of satisfiability for 3-disjunctive boolean formulas (3-SAT) polynomially transforms to MPR problem. It is easy to verify that the construction described in [5] satisfies the condition (ii) of Theorem 4.1.

References

[1] K. Cechlárová, On the powers of matrices in bottleneck/fuzzy algebra, Preprint 21/93, University of Birmingham.

[2] R. A. Cuninghame-Green, Minimax algebra, Lecture Notes in Econom. and Math. Systems 166, Springer-Verlag, Berlin, 1979.

[3] M. Gavalec, Computing matrix period in max-min algebra, Discr. Appl. Math. (to appear).

[4] M. Gavalec, Periodicity of matrices and orbits in fuzzy algebra, Tatra Mountains Math. Publ. 6 (1995), 35–46.

[5] M. Gavalec, Reaching matrix period is NP-complete, Tatra Mountains Math. Publ. (to appear).

[6] D. E. Knuth, A. Raghunathan, The Problem of Compatible Representatives, SIAM J. Disc. Math. 5 (1992), 422-427.

[7] Li Jian-Xin, Periodicity of powers of fuzzy matrices (finite fuzzy relations), Fuzzy Sets and Systems 48 (1992), 365-369.

[8] Li Jian-Xin, An upper bound on indices of finite fuzzy relations, Fuzzy Sets and Systems 49 (1992), 317-321.

[9] M. G. Thomason, Convergence of powers of a fuzzy matrix, J. Math. Anal. Appl. 57 (1977), 476–480.

Department of Mathematics, Faculty of Electrical Engineering and Informatics, Technical University, Hlavná 6, 04201 Košice, Slovakia

E-mail address: gavalec@ccsun.tuke.sk

Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, Graz, Austria

E-mail address: rote@opt.math.tu-graz.ac.at