{'fraction_non_alphanumeric': 0.050933193790336645, 'fraction_numerical': 0.01473922902494331, 'mean_word_length': 3.8443177017321504, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Geometry of deadbeat synchronization

The deadbeat synchronization of identical discrete-time nonlinear systems is studied from a geometric point of view. An array of deadbeat observers coupled via a deadbeat interconnection is shown to achieve synchronization in finite number of steps provided that a compatibility condition is satisfied between the observer and the interconnection. As an illustration to the theory, an example is provided where an array of third order observers achieves deadbeat synchronization.


Introduction
Two or more dynamical systems are said to synchronize when their solutions converge to a common trajectory. The generality of this definition allows many seemingly different cases to make examples of synchronization [1]. One such example is the following pair of discrete-time linear systems where y i = Cx i and all the eigenvalues of the matrix A − LC are on the open unit disc. The second system (1b) is the classic linear observer [2] and its construction readily yields x 1 (k) − x 2 (k) → 0 as k → ∞ regardless of the initial conditions. Another linear example to synchronization is the following array of systems with rather simple dynamics where [γ ij ] ∈ R q×q is a (connected) coupling matrix. That is, [γ ij ] satisfies: (i) the entries of each row sum up to unity, which implies that λ = 1 is an eigenvalue with the eigenvector [1 1 . . . 1] T , and (ii) all the remaining eigenvalues are on the open unit disc. In this case the solutions y i (k) converge to a fixed point in space and the systems are said to reach consensus [3,4]. At first sight the arrays (1) and (2) may not seem to be relevant, but they are in fact the two limiting cases of the following general structure Note that (3) boils down to (1) for [γ ij ] = 1 0 1 0 and to (2) for A = C = L = I. An effective way to study the synchronization behavior of an array is through understanding the smaller pieces that it is made of [5,6,7]. So if the array (3) is what we are trying to understand then it is worthwhile to focus on its two limiting cases: the array (1) and the array (2). In this line of thinking, the very first question that one is tempted to ask is the following. Given that the system (1b) is an observer for the system (1a) and that the array (2) reaches consensus, does the array (3) synchronize? However, a counterexample is easy to construct and this naive guess has to be abandoned.
Having dispensed with the first question, we point our attention, among a number of possibilities, to the following. Given that the system (1b) is a deadbeat observer [8,9,10] for the system (1a) and that the array (2) reaches consensus in finite number of steps [11,12], does the array (3) synchronize? This guess turns out to be more fruitful than the first one. In fact not only synchronization is achieved in this case, but it is achieved in deadbeat fashion, that is, in finite number of steps. Motivated by this simple observation on linear systems, we aim in this paper to establish sufficient conditions that guarantee deadbeat synchronization in an array of coupled identical discrete-time nonlinear systems. What we particularly study here is the synchronization behavior of an array of deadbeat observers that are coupled through a fixed interconnection scheme, which itself, if considered separately as the righthand side of an array, enjoys deadbeat synchronization. We show that deadbeat synchronization is achieved under a compatibility condition between the observer and the interconnection.
The literature accommodates few results on deadbeat synchronization. Motivated by possible applications in secure communications, one of the earliest results on the subject is presented in [13], where conditions for the synchronization of two systems of type Lur'e, coupled via a scalar output signal are given. Later, certain improvements to this work are reported, for instance, in [14,15,16], where synchronization still requires that the number of systems is two and the output is scalar. To the best of our knowledge, the problem of deadbeat synchronization has not yet been considered in a general setting where the number of (identical, nonlinear) individual systems are arbitrary and the output signals, through which the systems are coupled, are not necessarily scalar. The contribution of this paper is hence intended to be in understanding better the mechanism behind synchronization in discrete time from the deadbeat point of view.
The remainder of the paper is organized as follows. The next section contains some preliminary material. In Section 3 is the construction of the deadbeat observer, which is of geometric nature [17,18] and makes a special case of what is presented in [10]. The reader will find an illustrative example following this construction. As mentioned earlier, the observer together with the system being observed make a particular case of synchronization where there are only two systems. To reach a natural generalization of this scenario we take two mental steps. First, we remove the distinction between the two systems by allowing each to observe the other. In other words, we dispense with the drive system (leader)-response system (follower) hierarchy. Second, having removed the distinction between the observer and the observee, we allow the number of systems involved to be arbitrary. At that point a method is required to couple this array of observers. Therefore we introduce in Section 4 what we call deadbeat interconnection, which basically is a nonlinear generalization of the time-invariant map (coupling matrix) that appears in linear deadbeat consensus. Then in Section 5 we bring together the observer construction of Section 3 and the interconnection scheme of Section 4 to define the array of coupled observers. There we establish the deadbeat synchronization of this array under a compatibility condition that concerns both the observer and the interconnection. In Section 6 we provide a nonlinear example where an array of third order deadbeat observers are shown to achieve deadbeat synchronization. Certain issues are discussed in Section 7.

Preliminaries
The set of nonnegative integers is denoted by N, the set of rational numbers by Q. A vector of all ones is denoted by 1. The m × m identity matrix is denoted by I m , or sometimes simply by I when what m should be is either obvious or immaterial. The symbol ⊗ denotes Kronecker product. The null space of a matrix M ∈ R m×n is denoted by N (M ) and M ⊥ denotes some real matrix, whose columns form a basis for N (M ). For square M we let M 0 = I. Given a map h : X → Y, h −1 denotes the inverse map in the general sense that, for y ∈ Y, h −1 (y) is the set of all x ∈ X satisfying h(x) = y. That is, we will not need h be bijective when talking about its inverse. For f : . . x T q ] T ∈ R qn . We sometimes use " * " as a placeholder for "don't care."

Deadbeat observer
This section is dedicated to the description of the nonlinear deadbeat observer. Later, in Section 5, when we establish the conditions for deadbeat synchronization of an array of coupled observers, the construction presented here will be of key importance. Unlike linear systems, there is not a standard deadbeat observer construction for nonlinear systems. Even the definition of a deadbeat observer may not be unique. The definition and the construction that we present in this section are adopted from [10]. The section ends with an illustration of the construction.

Definition
Consider the following discrete-time system where x ∈ X ⊂ R n is the state, x + is the state at the next time instant, and y ∈ h(X ) =: Y ⊂ R m is the output or the measurement. The solution of the system (4) at time k ∈ N, starting at the initial condition x(0) ∈ X is denoted by x(k). Now consider the following array The solution of the system (5b) at time k ∈ N, starting at the initial condition x(0) ∈ X is denoted byx(k). Note thatx(k) depends also on x(0). We now use (5) to define deadbeat observer.
Definition 1 Given g : X × Y → X , the system is said to be a deadbeat observer for the system (4) if there exists an integer p ≥ 1 such that, for all initial conditions, the solutions of the array (5) satisfŷ x(k) = x(k) for all k ≥ p. The integer p then is called a deadbeat horizon.

Construction
To be used in the construction of the observer we define certain sets associated with the system (4). For x ∈ X we let We finally let We make the following two assumptions to guarantee that the observer construction will work. We note that these conditions are only sufficient. For less restrictive assumptions see [10].
Assumption 1 The map f : X → X is bijective.
The following result tells us how to design a deadbeat observer under these assumptions.

Theorem 1 Suppose Assumptions 1-2 hold. Then the system
is a deadbeat observer for the system (4) with deadbeat horizon p.
Theorem 1 will later become a corollary of our main result (Theorem 4). Hence we omit the proof. Let us now give an example to this construction (6).

Illustration
Consider the system (4) with . This map appears in [19] where it is reported to exhibit chaotic behavior for certain values of real numbers a and b. Let us now construct a deadbeat observer taking h(x) = ξ 3 . Note first that f is bijective (for b nonzero) and its inverse is Since h(x) = ξ 3 we can write Then by (7) [ The intersection of the sets (8) and (9) yields which means that Assumption 2 is satisfied with p = 3. The dynamics of the deadbeat observer then read For the parameter choice a = 1 and b = 1/3, Fig. 1 shows the simulation results for the initial conditions x(0) = (1, −1, 1) andx(0) = (0, 2, 1). The description of the deadbeat observer is now complete. As mentioned earlier, we are headed towards understanding the collective behavior of an arbitrary number of identical observers that are interacting. To be able to proceed, we therefore first need to be precise with what we mean by interacting. To this end, we introduce in the next section the so called deadbeat interconnection. This interconnection scheme will be evoked in Section 5 to characterize the coupling of the array whose synchronization we will study.

Deadbeat interconnection
Here we provide a generalization of the case where the linear array (2) reaches consensus in finite number of steps, which happens when the characteristic polynomial of the q × q coupling matrix [γ ij ] is d(s) = s q−1 (s − 1). When referring to such [γ ij ] we will use the term deadbeat coupling matrix. A primitive example for q = 4 is given as for all k ≥ 3. This means that the solutions of the array (2) should satisfy That is, convergence is exact. Now we give the generalization.
if the following conditions simultaneously hold.
• There exists an integer r ≥ 1 such that, for all initial conditions, the solutions of the array The integer r then is called a deadbeat horizon.
Some examples are in order. Let G ∈ R q×q be a deadbeat coupling matrix and Y = R m . Then the linear map with y = (y 1 , y 2 , . . . , y q ) is a deadbeat interconnection for any Q ∈ R m×m . Note for Q = I that the array (2) makes a special case of this construction. Not all linear deadbeat interconnections must have this structure (11) though. For instance, for Y = R 2 and q = 2, the map y → Γy with can be shown to be a deadbeat interconnection for which no G, Q ∈ R 2×2 exist that yield G ⊗ Q = Γ. Our last example is nonlinear. Let [γ ij ] ∈ R q×q be a deadbeat coupling matrix and Y = R. Then the map γ = (γ 1 , γ 2 , . . . , γ q ) with is a deadbeat interconnection.
Recall that in the standard observer setting, where there are only two systems in the array, i.e., the response system (the observer) and the drive system (the system being observed); the driving signal for the observer is the output of the system being observed. When one considers the general setting, where the array contains an arbitrary number of systems, the driving signal of each system (observer) is a function of the outputs of all the systems in the array. An array with q many systems means there will be q such functions. The deadbeat interconnection (γ 1 , γ 2 , . . . , γ q ) we defined in this section is nothing but a particular collection of those coupling functions. Having defined deadbeat observer and deadbeat interconnection, now we proceed to study the array that we form by bringing the two together.

Deadbeat synchronization
This section is where we finally gather the conditions that yield deadbeat synchronization of an array of coupled identical observers. Let us begin with defining the phenomenon under investigation. Definition 3 Given the maps g : X ×Y → X , h : X → Y, and (γ 1 , γ 2 , . . . , γ q ) = γ : Y q → Y q , the following array is said to achieve deadbeat synchronization if there exists an integer τ ≥ 1 such that, for all initial conditions, the solutions satisfy x i (k) = x j (k) for all k ≥ τ and all i, j. The integer τ then is called a deadbeat horizon.
This definition lets us write the formal statement of the problem to which we propose a solution in this paper: Under what conditions on the triple (g, h, γ) does the array (14) achieve deadbeat synchronization? Now, instead of directly listing the assumptions and establishing the main result, we prefer first to present the linear case, which we mentioned in the introduction in a slightly less general form (3), that motivated all the analysis in this paper. The conditions on which this linear result is founded we take as a justification for some of the assumptions we will have made.
Theorem 2 Let A ∈ R n×n , C ∈ R m×n , and L ∈ R n×m be such that A − LC is nilpotent. Let [γ ij ] ∈ R q×q be a deadbeat coupling matrix. Then the array  (15) can be written as Since G is a deadbeat coupling matrix we have G r = 1ℓ T where ℓ ∈ R q is the left eigenvector of G for the eigenvalue λ = 1 satisfying ℓ T 1 = 1. That all the remaining eigenvalues are at the origin allows us to find a transformation matrix V ∈ R q×q satisfying as well as that is strictly upper triangular. Without loss of generality we assume that J is in Jordan form. That is, J = diag(J 1 , J 2 , . . . , J σ ) where each (Jordan) block J α , α ∈ {1, 2, . . . , σ}, is strictly upper triangular. Then the size of the largest Jordan block is no greater than r × r. Employing the coordinate change z := (V −1 ⊗ I n )x we can write where Since J is block diagonal with blocks strictly upper triangular, N is also block diagonal N = diag(N 1 , N 2 , . . . , N σ ) with the structure for all α ∈ {1, 2, . . . , σ}. Note that the size of the largest of the blocks N α is no greater than rn × rn. And this largest block must vanish in rp steps because (A − LC) p = 0. By the time the largest block has vanished the other blocks must have also vanished. We deduce therefore Equations (16) and (17) yield for all k ≥ rp. In other words, all the solutions x i (·) converge (in deadbeat fashion) to the trajectorȳ Let us go through the conditions required for Theorem 2 in order to generate their nonlinear counterparts. One condition is that the matrix A − LC is nilpotent. This is equivalent to that the system (1b) is a deadbeat observer for the system (1a), which suggests for the nonlinear case that each individual system of the array is a deadbeat observer. Recall that, under Assumptions 1-2, we know how to construct a deadbeat observer, see Theorem 1. Another condition in Theorem 2 is that [γ ij ] is a deadbeat coupling matrix. This translates into that the map y → ([γ ij ] ⊗ Q)y is a deadbeat interconnection. Hence the following assumption, which we will later need for the main theorem.
Consider now, in the light of Theorem 1 and under Assumptions 1-3, the following array Does the array (18) achieve deadbeat synchronization? The answer to this question is negative and that is why we will eventually need to make a fourth assumption. A counterexample, which is indeed linear, is as follows.
We take X = R 4 and Y = R 2 . Let f (x) = Ax and h(x) = Cx with Assumption 1 is satisfied since A is nonsingular. Assumption 2 is also satisfied (with p = 2) because where H can be computed as Note that (A − AHC) 2 = 0. As for the deadbeat interconnection, we take γ(y) = Γy where Γ ∈ R 4×4 is as in (12), which is known to satisfy Assumption 3 without admitting matrices G, Q ∈ R 2×2 to realize G ⊗ Q = Γ. (We especially want to emphasize here that the special structure (11) of the interconnection assumed in Theorem 2 is not merely for demonstrational convenience. The structure (11) does indeed play a role in achieving synchronization.) Hence the triple (f, h, γ) = (A, C, Γ) satisfies Assumptions 1-3. Under our parameter choice the array (18) enjoys the following form which does not achieve deadbeat synchronization. Because if it did then it would necessarily require that the matrix Φ ∈ R 8×8 has at least (q − 1)n = 4 of its eigenvalues at the origin. However, the characteristic polynomial of Φ turns out to be d(s) = s 8 − 3.5s 7 − 1.5s 6 + 11.5s 5 − 2.5s 4 − 8s 3 − 2s 2 .
This example justifies that Assumptions 1-3 are not sufficient and additional conditions are needed for the deadbeat synchronization of the array (18). Let us now provide (in Definition 4) one such condition. First, however, we need to introduce some notation associated with the triple (f, h, γ).

Definition 4
The triple (f, h, γ) is said to be compatible if, for all σ ≥ 1 and where p is as in Assumption 2.
Here is our last assumption.
We need some sort of justification for this assumption. When studying nonlinear systems, a first step towards forming an opinion on whether an assumption is too restrictive or not for the goal to be achieved is to see what it boils down to for linear systems. For this purpose we want to point out that, for the linear array (15), compatibility is implied by Assumptions 1-3 whenever the matrix Q is nonsingular. The next theorem formalizes this.
Theorem 3 Let A ∈ R n×n be nonsingular and C ∈ R m×n be such that there exists L ∈ R n×m satisfying (A− LC) p = 0. Then, given Q ∈ R m×m nonsingular and a deadbeat coupling matrix G ∈ R q×q , the triple (A, C, G⊗Q) is compatible.
Proof. Since G is a deadbeat coupling matrix, for some integer r ≤ q − 1, we have G r = G r+1 = 1ℓ T where ℓ ∈ R q is the left eigenvector of G for the eigenvalue λ = 1 satisfying ℓ T 1 = 1. That Q is nonsingular allows us to write Y σ = N ((G σ − 1ℓ T ) ⊗ I m ). Given σ, let {v 1 , v 2 , . . . , v α } be a basis for N (G σ −1ℓ T ) and {e 1 , e 2 , . . . , e m } be a basis for R m . Then the set i, j {v i ⊗e j } makes a basis for Y σ . Now, given x ∈ R qn , suppose (I q ⊗ CA k )x ∈ Y σ for all k = 0, 1, . . . , p − 1. Note that we can find scalars α kij such that Since A is nonsingular, that we can find some L satisfying (A−LC) p = 0 implies [C T A T C T . . . A (p−1)T C T ] is full row rank. Hence, for each k = 0, 1, . . . , p−1, we can find M k ∈ R m×m such that We can then write The next theorem is our main result, which says that if a number of identical deadbeat observers are coupled through a deadbeat interconnection, the array achieves synchronization in finite number of steps provided that the observer and the interconnection satisfy the compatibility condition of Definition 4.
To prove our claim we suppose that it holds for some k. Let x, z be such that Then we can write for all k and α. Note that it is enough to establish this for α = 1. Again we employ induction. Suppose (20) holds with α = 1 for some k. Then Now, by (19) and (20) which completes the demonstration of Lemma 1.
Note that the array (18) leads to the following system in X q where . The next two results concern the system (21). Lemma 2 Consider the system (21). For all k ≥ p − 1 the solution x(k) =: x k satisfies for all α ∈ {1, 2, . . . , p}.
Proof of Theorem 4. Consider the system (21). Given some k ≥ p and σ ≥ 1, suppose hx k−α ∈ Y σ for all α ∈ {1, 2, . . . , p}. Then by Lemma 3 we have for all α ∈ {1, 2, . . . , p}. By compatibility therefore hx k ∈ Y σ−1 . Hence we established Now note that Y σ−1 ⊂ Y σ by definition and Y r = Y q , where r ≥ 1 satisfies γ r Y q = Y 0 because γ is a deadbeat interconnection. In the light of these facts, (23) implies hx τ −α ∈ Y 1 for all α ∈ {1, 2, . . . , p}, where τ := rp. Evoking Lemma 3 once again we have The interpretation of this for the array (18) is for all α ∈ {1, 2, . . . , p}. Note that Assumption 2 and the first property listed in Lemma 1 imply x = h −1 hx ∩ [x] + p−2 for all x ∈ X . Then we can write where for the last step we used the property [x] + −1 = X . By (24) we can then write Recall that f is bijective. Hence x i (τ ) = x j (τ ). This equality emerges from arbitrary initial conditions. The time-invariance of the array (18) therefore implies that x i (k) = x j (k) for all k ≥ τ and all i, j.
is itself a deadbeat interconnection (over X q ) under the assumptions of Theorem 4.

Remark 5
Observe that Theorem 1 directly follows from Theorem 4 by letting the interconnection γ : Y 2 → Y 2 be such that γ 1 y = γ 2 y = y 1 .

An example
As an illustration of Theorem 4, we now provide an example where an array of nonlinear observers achieves deadbeat synchronization. The below pair (f, h) is borrowed from [10].
with (a, b, c) = x ∈ X = R 3 and Y = R. The map f is bijective, hence Assumption 1 holds, and we have which is singleton. (We refer the reader to [10] for derivations.) Therefore Assumption 2 is satisfied with deadbeat horizon p = 3. Regarding the deadbeat interconnection γ, our choice is the one given in (13) with [γ ij ] ∈ R q×q a deadbeat coupling matrix. Hence Assumption 3 also holds. The question now is whether the triple (f, h, γ) is compatible or not.
Then by (26) we can write Hence the result.

Notes
The deadbeat interconnection considered in this paper is fixed. A possible relaxation is suggested by the proof of Theorem 4. Namely, deadbeat synchronization would still be achieved with time-varying interconnection γ(k, y) provided that the sets Y σ stayed fixed and the relation γ(k, Y σ ) ⊂ Y σ−1 was satisfied at all times k. This is very closely related to what we mentioned in Remark 2 regarding the linear array (15). Further generalization in this direction seems nevertheless not to be an easy task.
A practical design problem is how to construct a deadbeat interconnection compatible with a given (f, h) pair. A primitive solution to this problem is to select an interconnection that admits a connected graph that is a (directed) tree. In that case, in an array of q systems, q − 1 of the systems would each be driven by exactly one other system, i.e., for each i ∈ {1, 2, . . . , q − 1} we would have γ i (y) = y j for some j = i, and one system (the root) would be driven by no one, i.e., γ q (y) = y q . However, when one starts considering interconnection schemes that include cycles in their graphs, the problem seems to lack an obvious systematic solution.