# Controllability Analysis of Linear Discrete Time Systems with Time Delay in State

Authors: Hong Shi; Guangming Xie; Wenguang Luo
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

The controllability issues for linear discrete-time systems with delay in state are addressed. By introducing a new concept, the minimum controllability realization index (MinCRI), the characteristic of controllability is revealed. It is proved that the MinCRI of a system with state delay exists and is finite. Based on this result, a necessary and sufficient condition for the controllability of discrete-time linear systems with state delay is established.


---

## Body

## 1. Introduction

The concept of controllability of dynamical systems was first proposed by Kalman in 1960s [1]. Since then, controllability of dynamical systems has been studied by many authors in various contexts [2–11], because controllability turns out to be a fundamental concept in modern control theory and has dose connections with pole assignment, structure decomposition, quadratic control, and so forth [12, 13]. On the other hand, time delay phenomena are very common in practical systems, for instance, in economic, biological, and physiological systems. Studying the time delay phenomena in control systems has become an important topic in control theory. Chyung studied the controllability for linear time-invariant systems with constant time delay in the control functions. Simple algebraic-type necessary and sufficient criteria are established [3, 4]. However, once the time delay appears in state, the problem becomes much more complex. There are some preliminary results in [5, 6]. However, all these results are not suitable for verification and application.In this paper, we consider the discrete-time case, the system model described as follows:(1.1)x(k+1)=Ax(k)+Dx(k-h)+Bu(k),
where x(k)∈ℝn is the state, u(k)∈ℝp is the input, A, D∈ℝn×n, B∈ℝn×p are constant matrices, and positive integer h is the length of the steps of time delay. The initial states x(-h),x(-h+1),…,x(0) are given arbitrarily.The controllability discussed here refers to the unconstrained controllability, or say completely controllability.Definition 1.1 (controllability).
System (1.1) is said to be (completely) controllable, if for any initial state x(-h),x(-h+1),…,x(0) and any final state xf, there exist a positive integer k and input u(0),…,u(k-1) such that x(k)=xf.Definition 1.2 (controllability realization index, (CRI)).
For system (1.1), if there exists a positive integer K such that for any initial state x(-h),x(1-h),…,x(0) and any terminal state xf, there exist input u(0),…,u(K-1) such that x(K)=xf; then one calls K the controllability realization index (CRI) of system (1.1). Obviously, if exists, such K is not unique, so one calls the smallest K among them the minimum controllability realization index (MinCRI).In this paper, our main concern is the following.Can the controllability of system (1.1) be realized completely in finite steps, or say can the MinCRI of the system be finite?Here we demonstrate that the answer to this question isyes. And in the case of planar systems, the exact value of the controllability realization index is obtained, and we will prove it is independent of the choices of A and D.This paper is organized as follows. In Section2 some concepts are introduced, which will be used in the later discussion. Section 3 contains the main results. Finally, the conclusion is provided in Section 4.


## 2.  Preliminaries

Denote byℕ the nonnegative integer set, ℝ the real number set, respectively. The matrices A1,…,AN∈ℝn×n are said to be linearly dependent in ℝn×n, if there exist scalars c1,…,cN∈ℝ, not all zero, such that ∑i=1NciAi=0. In what follows, span{A1,…,AN} will be used to denote the linear subspace constructed by the linear combinations of matrices {A1,…,AN}.Definition 2.1 (symmetrical subspace).
Given matricesA,D∈ℝn×n, one defines a subset of ℝn×n as follows:
(2.1)P[A,D]:={f(A,D)∣f(A,D)=∑m=1M‍cmAim,1Djm,1⋯Aim,nmDjm,nm,nm∈ℕ,im,1,jm,1,…,im,nm,jm,nm∈ℕ,0≤im,1,jm,1,…,im,nm,jm,nm≤n,cm∈ℝ,m=1,…,M;M∈ℕ{∑m=1M‍}}.
Then a one-to-one mapping Θ:P[A,D]→P[A,D] is constructed as follows:give anyf(A,D)∈P[A,D], supposing f(A,D)=∑m=1McmAim,1Djm,1,…,Aim,nmDjm,nm, one defines
(2.2)Θ(f(A,D)):=∑m=1M‍cm(Aim,1Djm,1⋯Aim,nmDjm,nm+Djm,nmAim,nm⋯Djm,1Aim,1).
Then we get a subspace of P[A,D] by
(2.3)PSym[A,D]:={Θ(f(A,D))∣∀f(A,D)∈P[A,D]}.
We call PSym[A,D] the symmetrical subspace of P[A,D].By Definition2.1, it is easy to verify that I,A,D,AD+DA,ADA,DAD∈PSym[A,D], where I is the identity matrix in ℝn×n.Now, we introduce a matrix sequence{Gk}k=0∞∈ℝn×n as follows:
(2.4)Gk={Ak,ifk=0,1,…,h,Gk-1A+Gk-1-hD,ifk=h+1,h+2,…Then the solution of system (1.1) can be expressed as
(2.5)x(k+1)=Ψk(x(0),…,x(-h))+∑i=0k‍Gk-iBu(i),k>0,
where Ψk(x(0),…,x(-h)) is the part of the solution with zero input.Lemma 2.2.
Given the matrix sequence{Gk}k=0∞ in (2.3), the following statements hold:(a)
there are no similar terms betweenGkA and Gk-hD;(b)
for anyGk, it can be expressed as
(2.6)Gk=∑∀f(A,D)∈Qk[A,D]‍f(A,D),whereQk[A,D] is a subset of ℝn×n defined as follows:
(2.7)Qk[A,D]={{∑m=1k‍}f(A,D)∣f(A,D)=Ai1Dj1⋯AikDjk,∀i1,j1,…,ik,jk∈ℕ,∑m=1k‍im+(h+1)∑m=1k‍jm=k};(c)
for allk∈ℕ,Gk∈PSym[A,D].Proof.
Statement (a) is nearly self-evident because any term fromGkA is ended by A, whereas any term from Gk-hD is ended by D.
To prove the result of statement (b), mathematical induction is invoked.(I)
The firsth+1 terms of {Gk}k=0∞ are I,A,…,Ah, and it is obvious that Qk[A,D]={Ak}, for k=0,1,…,h. Thus, for k=0,1,…,h, (2.5) holds.(II)
Assume that, forl=k,k+1,…,k+h, Gl is expressed in form (2.5). We will prove that Gk+h+1 can be expressed in form (2.5) as well.
First, we prove that, for anyk, we have
(2.8)Qk+1[A,D]=Qk[A,D]A⋃Qk-h[A,D]D,
where the sets Qk[A,D]A, Qk-h[A,D]D are defined as
(2.9)Qk[A,D]A={f(A,D)A∣f(A,D)∈Qk[A,D]},Qk-h[A,D]D={f(A,D)D∣f(A,D)∈Qk-h[A,D]}.
By the assumption, we have
(2.10)Qk[A,D]A={f(A,D)A∣f(A,D)∈Qk[A,D]}={{∑m=1k‍}f(A,D)A∣f(A,D)=Ai1Dj1⋯AikDjk,i1,j1,…,ik,jk∈ℕ,∑m=1k‍im+(h+1)∑m=1k‍jm=k},={{∑m=1k‍}g(A,D)∣g(A,D)=Ai1Dj1⋯Aik+1Djk+1,i1,j1,…,ik,jk∈ℕ,ik+1=1,jk+1=0,∑m=1k+1‍im+(h+1)∑m=1k+1‍jm=k+1}⊆Qk+1[A,D],Qk-h[A,D]D,={f(A,D)D∣f(A,D)∈Qk-h[A,D]}={{∑m=1k‍}f(A,D)D∣f(A,D)=Ai1Dj1⋯Aik-hDjk-h,i1,j1,…,ik-h,jk-h∈ℕ,∑m=1k-h‍im+(h+1)∑m=1k-h‍jm=k-h}={{∑m=1k+1‍}g(A,D)∣g(A,D)=Ai1Dj1⋯Aik+1Djk+1,i1,j1,…,ik-h,jk-h∈ℕ,ik-h+1=⋯=ik+1=0,jk-h+1=⋯=jk=0,jk+1=1,∑m=1k+1‍im+(h+1)∑m=1k+1‍jm=k+1}⊆Qk+1[A,D].
Thus, we have Qk[A,D]A⋃‍Qk-h[A,D]D⊆Qk+1[A,D].
On the contrary, given anyf(A,D)∈Qk+1[A,D], suppose that
(2.11)f(A,D)=Ai1Di1⋯Aik+1Djk+1,
where i1,j1,…,ik+1,jk+1∈ℕ, ∑m=1k+1im+(h+1)∑m=1k+1jm=k+1.
There are two cases: (i) the final term off(A,D) is Aim, im>0, 1≤m≤k+1, then there exists a matrix polynomial g(A,D) such that f(A,D)=g(A,D)A, then it is easy to verify that g(A,D)∈Qk[A,D], and it follows that f(A,D)∈Qk[A,D]A; (ii) the final term of f(A,D) is Djm, jm>0, 1≤m≤k+1, then there exists a matrix polynomial g(A,D) such that f(A,D)=g(A,D)D, then it is easy to verify that g(A,D)∈Qk-h[A,D], and it follows that f(A,D)∈Qk-h[A,D]D.
Thus, we haveQk[A,D]A⋃‍Qk-h[A,D]D⊇Qk+1[A,D]. Hence, we know that (2.7) holds.
Secondly, sinceGk+h+1=Gk+hA+GkD, we have
(2.12)Gk+1+h=∑f(A,D)∈Qk+h[A,D]‍f(A,D)A+∑f(A,D)∈Qk[A,D]‍f(A,D)D=∑g(A,D)∈Qk+h[A,D]A⋃‍Qk[A,D]D‍g(A,D)=∑g(A,D)∈Qk+h+1[A,D]‍g(A,D).
Thus, (2.5) holds for k+h+1. Hence, statement (b) holds.
As for statement (c), it can be deduced naturally from statement (b). Note that ifAi1Dj1⋯AikDjk∈Qk[A,D], then Ai1Dj1⋯AikDjk∈Qk[A,D] as well. So they must appear in Gk. By Definition 2.1, Gk∈PSym[A,D].


## 3. Main Results

First, we consider the general case.Theorem 3.1.
System (1.1) is controllable if and only if rank[G0B,G1B,…,GkB,…]=n.Proof.
From (2.4) and Definition 1.1, this theorem holds naturally.Theorem 3.2.
For system (1.1), there exists K∈ℕ such that
(3.1)rank[G0B,G1B,…,GkB,…]=rank[G0B,G1B,…,GKB].Proof.
It is obvious thatrank[G0B,G1B,…,GKB]=dim(span{G0B,G1B,…,GKB}). Consider an auxiliary scalar sequence {dk}k=0∞, where dk=dim(Span{G0B,G1B,…,GkB}). By definition, dk≤dk+1≤n2 for any k. Hence, there exists a constant d* such that, limk→∞dk=d*. Then for ε=0.5, there exists K>0 such that for all k>K, we have d*-0.5<dk<d*+0.5. It implies that dk=d*.Remark 3.3.
From Theorem3.2, it is clear that the controllability of the system (1.1) can be realized completely within first K steps during the evolving process, which means K is just a CRI of system (1.1), so the existence of MinCRI of linear discrete-time delay systems is ensured and the value of MinCRI is finite. Moreover, K is dependent on A, D, and h.Now we consider the second-order case, that is,n=2.Theorem 3.4.
Ifn=2, then 2h+4 is a CRI of system (1.1).Before giving the proof of Theorem3.4, we first give some lemmas.Lemma 3.5.
GivenA,D∈ℝ2×2, for any k∈ℕ, one has (AD)kA,(DA)kD,(AD)k+(DA)k∈span{I,A,D,DA+AD,ADA,DAD}.Proof.
According to the different cases, we formulate the proof into two cases.
(a)I,A,D are linearly dependent. Without loss of generality, suppose that
(3.2)A=λ1I+λ2D.
Then we have
(3.3)(AD)kA=[(λ1I+λ2D)D]k(λ1I+λ2D)(DA)kD=[D(λ1I+λ2D)]kD(AD)k+(DA)k=[D(λ1I+λ2D)D]k+[D(λ1I+λ2D)]k.
It is obvious that (AD)kA,(DA)kD,(AD)k+(DA)k∈span{I,D}.
(b)I,A,D are linearly independent. If span{I,A,D,DA+AD,ADA,DAD}=ℝ2×2, the proof is completed. Otherwise, suppose that DA+AD,ADA,DAD∈span{I,A,D}. We use mathematical induction.(i)
Fork=1, by the assumption, (AD)1A,(DA)1D,AD+DA∈span{I,A,D}.(ii)
Suppose that fork, (AD)kA,(DA)kD∈span{I,A,D}. Assume
(3.4)(AD)kA=λ1+λ2A+λ3D(DA)kD=λ4+λ5A+λ6D.For k+1, we have
(3.5)(AD)k+1A=A[(DA)kD]A=A(λ4+λ5A+λ6D)A=λ4A2+λ5A3+λ6ADA(DA)k+1D=D(λ1+λ2A+λ3D)D=λ1D2+λ2DAD+λ3D3(AD)k+1+(DA)k+1=(AD)k-1ADAD+(DA)k-1DADA=(AD)k-1A(λ4+λ5A+λ6D)+(DA)k-1(λ4+λ5A+λ6D)A=λ6(AD)k+λ6(DA)k+(AD)k-1A(λ4+λ5A)+(DA)k-1(λ4+λ5A)A.
It is obvious that (AD)k+1A,(DA)k+1D,(AD)k+1+(DA)k+1∈span{I,A,D}.Lemma 3.6.
GivenA,D∈ℝ2×2, one has span{I,A,D,DA+AD,ADA,DAD}=PSym[A,D].Proof.
First, it is obvious that(3.6)span{I,A,D,DA+AD,ADA,DAD}⊆PSym[A,D].
Now we prove that span{I,A,D,DA+AD,ADA,DAD}⊇PSym[A,D].
For anyf(A,D)∈PSym[A,D], assume that
(3.7)f(A,D)=∑m=1M‍cm(Aim,1Djm,1⋯Aim,nmDjm,nm+Djm,nmAim,nm⋯Djm,1Aim,1),
where nm∈ℕ,im,1,jm,1,…,im,nm,jm,nm∈{0,1},cm∈ℝ,m=1,…,M; M∈ℕ.
It is easy to see that if we could prove that each(3.8)Aim,1Djm,1⋯Aim,nmDjm,nm+Djm,nmAim,nm⋯Djm,1Aim,1∈span{I,A,D,DA+AD,ADA,DAD},
then we would have proved that
(3.9)f(A,D)∈span{I,A,D,DA+AD,ADA,DAD}.
It is easy to verify that
(3.10)Aim,1Djm,1⋯Aim,nmDjm,nm+Djm,nmAim,nm⋯Djm,1
can only be rewritten in three different forms:(a)
(AD)kA, where k∈ℕ;(b)
(DA)kD, where k∈ℕ;(c)
(AD)k+(DA)k, where k∈ℕ.
By Lemma3.5, we know that (3.8) holds. Thus, we have
(3.11)f(A,D)∈span{I,A,D,DA+AD,ADA,DAD}.
It follows that
(3.12)PSym[A,D]⊆span{I,A,D,DA+AD,ADA,DAD}.Now we are in a position to prove Theorem3.4.Proof of Theorem3.4.
By the definition of CRI, we only need to prove that(3.13)span{G0B,G1B,…,GkB,…}=span{G0B,G1B,…,G2h+3B}.
By Lemmas 2.2 and 3.6, we have
(3.14)span{G0,G1,…,Gk,…}⊆span{I,A,D,AD+DA,ADA,DAD}.
Now we prove that
(3.15)span{G0,G1,…,G2h+3}=span{I,A,D,AD+DA,ADA,DAD}.
By the definition of Gk, we have Gk=Ak, k=0,1,…,h, Gh+1=Ah+1+D, Gh+2=Ah+2+DA+AD, Gh+3=Ah+3+DA2+ADA+A2D. Note that DA2+A2D can be linearly expressed by I,A,D,AD+DA; then, we have
(3.16)span{G0,G1,…,Gh+3}=span{I,A,D,AD+DA,ADA}.
Consider the term DAD; it first appears in G2h+3. It is easy to verify that all other terms in G2h+3 can be linearly expressed by I,A,D,AD+DA,ADA. Thus, we know that (3.14) holds. This implies that (3.8) holds.Without proof, we can get the following corollaries directly.Corollary 3.7.
Assumingn=2, system (1.1) is controllable if and only if
(3.17)rank[B,AB,DB,(AD+DA)B,ADAB,DADB]=2.Corollary 3.8.
Assumingn=2, if system (1.1) is controllable, then the controllability can be realized in 2h+4 steps; that is, one can select appropriate u(0),u(1),…,u(2h+3) such that system (1.1) can be driven from any initial state to any terminal state.Remark 3.9.
Note that the parameterh does not appear in Corollary 3.7. This implies that the specific number of the delay steps has nothing to do with the controllability of the system.Remark 3.10.
Lemma3.6 plays a key role in the proof of Theorem 3.4. When n>2, it is difficult to build up a similar result like Lemma 3.6 for n>2. Thus the CRI problem for more general case is still open.


## 4. Examples

In this section, we present some numerical examples to illustrate the validity of our theoretic results.Example 4.1.
Consider the system (1.1) with n=2, h=2, and
(4.1)A=[0000],D=[0010],B=[10].
By simple calculation, we have rank[B,AB,DB,(AD+DA)B,ADAB,DADB]=2. By Corollary 3.7, the system should be controllable. In fact, we have
(4.2)x(4)=Φ(x(0),x(-1),x(-2))+[I,A,A2,D][u(3)u(2)u(1)u(0)].
Leting u(2)=u(1)=0, we can select suitable u(3) and u(0) such that x(4) be any state in ℝ2. Thus, the system is controllable indeed.Example 4.2.
Consider the system (1.1) with n=2, h=2, and
(4.3)A=[1001],D=A,B=[10].
By simple calculation, we have rank[B,AB,DB,(AD+DA)B,ADAB,DADB]=1. By Corollary 3.7, the system should not be controllable. In fact, it is easy to see that the second element of the state x(k) is not affected by any input u(k). Thus, the system is not controllable indeed.


## 5. Conclusion

This paper discussed the controllability of linear discrete-time systems with delay in state. After introducing a new concept called MinCRI to describe the controllability feature of delay systems, we proved the existence and finiteness of MinCRI. Based on this, a necessary and sufficient condition for the controllability of linear delay systems has been derived.



---

*Source: 490903-2012-10-31.xml*