a matrix K ∈ F m×n
2
such that A + B K has the desired invariant polynomials ci, K if and only if the
inequalities
k
k
∑ deg( ci, K) ≥ ∑ μi, k = 1,2,. . ., m
(22)
i=1
i=1
are satisfied.
Remark 22. The sum of the invariant polynomial degrees and the n-controllability condition guarantee
that equality holds for k = m. However, the choice of formulation also includes the case of systems with
single input m. In this case, Rosenbrock’s theorem requires n-controllablity when a desired closed-loop
characteristic polynomial is to be assigned by state feedback. Furthermore, the theorem indicates that at
most m different invariant polynomials may be assigned in an LMS with m inputs.
Assigning invariant polynomials is equivalent to assigning the non-unity polynomials of the
Smith canonical form of the closed-loop characteristic matrix λI − ( A + B K). It has to be
noted that although meeting the assumptions of the control structure theorem with the desired
460
Discrete Time Systems
closed-loop Smith form, the extraction of the corresponding feedback matrix K is not a trivial
task. The reason for this is that, in general, the structure of the Smith form of λI − ( A + B K)
does not necessarily agree with the controllability indices of the LMS, which are preserved
under linear state feedback. However, there is a useful reduction of the LMS representation
based on the closed loop characteristic matrix in the controller companion form as shown in
[Theorem 5.8 in (Reger, 2004)].
Theorem 23. Given is an n-dimensional n-controllable LMS in controller companion form (21) with
m inputs and controllability indices μ 1, . . . , μm. Let D ˆ ∈ F
K
2[ λ] m×m denote the polynomial matrix
D ˆ ( λ) := Λ( λ) − ˆ
K
A ˆ K,nonzero P( λ) ,
where ˆ
A ˆ
∈ F m×n
K,nonzero
2
contains the m non-zero rows of the controllable part of the closed-loop
system matrix ˆ
A
ˆ
c + ˆ
Bc K in controller companion form, and P ∈ F2[ λ] n×m, Λ ∈ F2[ λ] m×m are
⎛
⎞
1
0
· · ·
0
⎜
⎜ λ
0
· · ·
0
⎟
⎜ .
.
.
.
⎟
⎜ .
.
.
⎟
.
.
⎜ .
.
.
⎟
⎜ λμ
⎟
1 − 1
0
· · ·
0
⎛
⎞
⎜
⎟
λμ 1 0 · · · 0
⎜ 0
1
· · ·
0
⎟
⎜ .
.
⎟
.
.
⎟
⎜ 0 λμ 2 · · · 0 ⎟
P( λ) = ⎜
.
.
.
.
⎜
⎟
⎜ .
.
.
.
⎟ , Λ( λ) = ⎝ .. .. .. .. ⎠ .
(23)
⎜
⎟
0
λμ 2 − 1 · · ·
0
.
.
.
.
⎜
⎟
⎜ .
.
.
.
⎟
0
0 · · · λμm
⎜ ..
..
. .
.. ⎟
⎜
⎟
⎜ 0
0
· · ·
1
⎟
⎝ .
⎟
.
.
.
.
⎠
.
..
. .
..
0
0
· · · λμm− 1
Then the non-unity invariant polynomials of λI − ( ˆ
A
ˆ
c + ˆ
BcK) , λI − ( ˆ
A nonzero + ˆ
K) and D ˆ ( λ)
K
coincide, whereby ˆ
A nonzero contains the nonzero rows of the controllable part ˆ
Ac of the original system
matrix.
Theorem 23 points out a direct way of realizing the closed-loop LMS y( k + 1) = ( ˆ
Ac +
ˆ
B ˆ
cK) y( k) with desired invariant polynomials by means of specifying D ˆ ( λ).
That is, if
K
an appropriate D ˆ can be found, then a linear state feedback matrix ˆ
K
K in the transformed
coordinates can be directly constructed. Simple manipulations first lead to
ˆ
A ˆ
( λ) − Λ( λ)
(24)
K,nonzero P( λ) = D ˆ
K
from which ˆ
A ˆ K,nonzero can be determined by comparison of coefficients. Then, by Theorem
23, the feedback matrix
ˆ
K = A nonzero − ˆ
A ˆ K,nonzero
(25)
is obtained. Finally, the inverse coordinate transformation from the controller companion
form to the original coordinates yields
K = ˆ
K ˜
T .
(26)
Hence, it remains to find an appropriate matrix D ˆ . To this end, the following definitions are
K
employed.
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
461
Definition 24. Let M ∈ F2[ λ] n×m be arbitrary. The degree of the highest degree monomial in λ
within the i-th column of M( λ) is denoted as the i-th column degree of M and denoted by col i( M) .
Definition 25. Let M ∈ F2[ λ] n×m be arbitrary. The highest column degree coefficient matrix
Γ( M) ∈ F n×m
2
is the matrix whose elements result from the coefficients of the highest monomial
degree in the respective elements of M( λ) .
Then, the following procedure leads to an appropriate D ˆ . Starting with a desired cycle
K
sum for the closed-loop LMS, an appropriate set of invariant polynomials – as discussed
in Section 2.1 – has to be specified. Next, it has to be verified if the realizability condition
of Rosenbrock’s control structure theorem for the given choice of invariant polynomials is
fulfilled. If the polynomials are realizable then D ˆ ( λ) is chosen as the Smith canonical form
K
that corresponds to the specified closed-loop invariant polynomials. In case the column
degrees of D ˆ ( λ) coincide with the respective controllability indices of the underlying LMS,
K
that is, col i( D ˆ ) = μ
K
i for i = 1, . . . , m, it is possible to directly calculate the feedback matrix ˆ
K
according to (26). Otherwise, it is required to modify the column degrees of D ˆ ( λ) by means
K
of unimodular left and right transformations while leaving the invariant polynomials of D ˆ K
untouched. This procedure is summarized in the following algorithm.
Algorithm 26. Input: Pair ( ˆ
Ac, ˆ Bc) in controller companion form 8 controllability indices μ 1 ≥
· · · ≥ μm, polynomials ci, K ∈ F2[ λ] , i = 1, . . . , m with cj+1, K|cj, K, j = 1, . . . , m − 1 and
∑ mi=1 deg( ci, K) = n.
1. Verify Rosenbrock’s structure theorem
if the inequalities in Theorem 21 are fulfilled
go to step 2.
else
return “Rosenbrock’s structure theorem is violated.”
2. Define D ( λ) := diag( c 1, K, . . . , cm, K)
3. Verify if the column degrees of D ( λ) and the controllability indices coincide
if col i( D ) = μi, i = 1, . . . , m
go to step 6.
else
Detect the first column of D ( λ) which differs from the ordered list of controllability indices,
starting with column 1 . Denote this column col u( D ) ( deg(col u( D )) > μu)
Detect the first column of D ( λ) which differs from the controllability indices, starting with
column m. Denote this column col d( D ) ( deg(col d( D )) < μd)
4. Adapt the column degrees of D ( λ) by unimodular transformations
Multiply row d( D ) by λ and add the result to row u( D ) → new matrix D+( λ)
if deg(col u( D+)) = deg(col u( D )) − 1
D+( λ) → new matrix D++( λ) and go to step 5.
else
Define r := deg(col u( D )) − deg(col d( D )) − 1
Multiply col d( D+) by λr and subtract result from col u( D+) → new matrix D++( λ) .
8 If the LMS is not given in controller companion form, this form can be computed as in [p. 86 in
(Wolovich, 1974)].
462
Discrete Time Systems
5. Set D ( λ) = (Γ( D++)) − 1 D++( λ) and go to step 3.
6. D ˆ ( λ) :=
( λ)
K
D ( λ) and return D ˆ K
It is important to note that the above algorithm is guaranteed to terminate with a suitable
matrix D îf Rosenbrock’s structure theorem is fulfilled. For illustration, the feedback matrix
K
computation is applied to the following example that also appears in (Reger, 2004; Reger &
Schmidt, 2004). Given is an LMS over F2 of dimension n = 5 with m = 2 inputs in controller
companion form (that is, ˜
T = I),
⎛
⎞
⎛
⎞
0 1 0 0 0
0 0
⎜
⎜0 0 1 0 0⎟
⎟
⎜
⎜1 0⎟
⎟
y( k + 1) = ˆ
Ac y( k) + ˆ Bc u( k),
ˆ
Ac = ⎜
⎝0 0 0 0 0⎟
⎠ , ˆ Bc = ⎜
⎝0 0⎟
⎠
0 0 0 0 1
0 0
1 0 0 1 0
0 1
from which the matrix ˆ
A nonzero = 0 0 0 0 0 can be extracted.
1 0 0 1 0
As a control objective, we want to assign the invariant polynomials9 c 1, K( a) = ( a 2 + a +
1)( a + 1)2 and c 2, K( a) = a + 1, that is, according to the example in Subsection 2.1.2 this goal
is equivalent to specifing that the closed-loop LMS shall have 4 cycles of length 1, 2 cycles of
length 2, 4 cycles of length 3 and 2 cycles of length 6. An appropriate state feedback matrix K
is now determined by using (26) and Algorithm 26.
1.
−→
1
1
2
2
√
∑ deg( ci, K( λ)) = 4 ≥ ∑ ci = 3 and ∑ deg( ci, K( λ)) = 5 ≥ ∑ ci = 5
i=1
i=1
i=1
i=1
2.
−→
D ( λ) =
( λ 2 + λ + 1)( λ + 1)2
0
= λ 4 + λ 3 + λ + 1
0
0
λ + 1
0
λ + 1
3., 4.
−→
D+( λ) =
λ 4 + λ 3 + λ + 1 λ 2 + λ
= ⇒ D++( λ) =
λ + 1 λ 2 + λ
0
λ + 1
λ 3 + λ 2 λ + 1
5.
−→
Γ( D++) =
0 1
= ⇒ D ( λ) = (Γ( D++)) − 1 D++( λ) = λ 3 + λ 2 λ + 1
1 0
λ + 1 λ 2 + λ
3., 4., 6.
−→ D ˆ( λ) = λ 3 + λ 2 λ + 1
K
λ + 1 λ 2 + λ
With D ˆ ( λ) the feedback matrix
K
K can be computed. First, employing equation (24) yields
⎛
⎞
1 0
⎜ λ 0⎟
ˆ
⎜
⎟
A ˆ
⎜ λ 2 ⎟ = λ 3 0 + λ 3 + λ 2 λ + 1
=
λ 2 λ + 1
K,nonzero ⎝
0⎠
0 λ 2
λ + 1 λ 2 + λ
λ + 1 λ
0 1
0 λ
Λ( λ)
D ˆ ( λ)
K
9 Constructing the appropriate invariant polynomials based on the cycle structure desired is not always
solvable and, if solvable, not necessarily a straightforward task (Reger & Schmidt (2004)).
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
463
and by comparison of coefficients results in ˆ
A ˆ
= 0 0 1 1 1 . This implies that
K,nonzero
1 1 0 0 1
K = ˆ
K ˜
T = ( ˆ
A ˆ
+ ˆ
.
K,nonzero
A nonzero) I = 0 0 1 1 1
0 1 0 1 1
3. Properties of Boolean monomial systems10
3.1 Dynamic properties, cycle structure and the loop number
The aim of this section is that the reader becomes acquainted with the main theorems
that characterize the dynamical properties of Boolean monomial dynamical systems without
deepening into the technicalities of their proofs. We briefly introduce terminology and
notation and present the main results. Proofs can be found in Delgado-Eckert (2008), and
partially in Delgado-Eckert (2009a) or Colón-Reyes et al. (2004).
Let G = ( VG, EG, πG) be a directed graph (also known as digraph). Two vertices a, b ∈ VG are
called connected if there is a t ∈ N0 and (not necessarily different) vertices v 1, ..., vt ∈ VG such
that
a → v 1 → v 2 → ... → vt → b,
where the arrows represent directed edges in the graph. In this situation we write a
s b,
where s is the number of directed edges involved in the sequence from a to b (in this case
s = t + 1). Two sequences a
s b of the same length are considered different if the directed
edges involved are different or the order at which they appear is different, even if the visited
vertices are the same. As a convention, a single vertex