Explicit solution formulas are presented for systems of the formExk+1=Axk+fk withk∈K, w hereK⊂Zis a discrete interval and the pencil λE−Ais regular

EXPLICIT SOLUTIONS OF REGULAR LINEAR DISCRETE-TIME DESCRIPTOR SYSTEMS WITH CONSTANT COEFFICIENTS^∗

TOBIAS BR ¨ULL^†

Abstract. Explicit solution formulas are presented for systems of the formEx^k+1=Ax^k+f^k withk∈K, w hereK⊂Zis a discrete interval and the pencil λE−Ais regular. Different results are obtained when one starts with an initial condition at the point k= 0 and calculates into the future (i.e.,Ex^k+1 =Ax^k+f^k withk∈N) and when one wants to get a complete solution (i.e., Ex^k+1=Ax^k+f^kwithk∈Z).

Key words. Descriptor system, Strangeness index, Linear discrete descriptor system, Explicit solution, Backward Leslie model.

AMS subject classifications.39A05, 15A06.

1. Introduction. We denote sequences of vectors by{x^k}_k∈Dfor arbitrary dis- crete intervals D⊂Z. Thek-th vector of such a sequencex^k is also called thek-th element of{x^k}_k∈Dand further x^k_i denotes thei-th (block-)row of the vectorx^k. To introduce the notion of a discrete-time descriptor system let us first define two discrete intervals in the following way.

K:={k∈Z:k_b≤k≤k_f}, k_b ∈Z∪ {−∞}, k_f ∈Z∪ {∞}, K⁺:=

K ifk_f =∞, K∪ {k_f+ 1} ifk_f <∞. With this definition we call

Ex^k+1=Ax^k+f^k, x^k0 =x₀, k∈K (1.1) alinear discrete-time descriptor system with constant coefficients, whereE, A∈C^n,n, x^k ∈Cⁿfork∈K⁺are the state vectors,f^k∈C^n,nfork∈Kare the inhomogeneities and x₀ ∈ Cⁿ is an initial condition given at the point k₀ ∈ K⁺. Other names for systems of the form (1.1) includelinear time-invariant discrete-time descriptor system, linear singular system (e.g., [12]), linear semi-state system, and linear generalized state-space system. The sequence{x^k}_k∈K⁺is called a solution of (1.1) if its elements fulfill all the equations. The continuous-time counterpart to (1.1) is called linear continuous-time descriptor system with constant coefficientsand given by

Ex(t) =˙ Ax(t) +f(t), x(t₀) =x₀, t∈R, (1.2) whereE, A∈C^n,n,x(t)∈Cⁿ is the state vector,f(t)∈Cⁿis the inhomogeneity, ˙x(t) is the derivative ofx(t) with respect tot, andx₀∈Rⁿ is an initial condition given at

∗ Received by the editors January 23, 2009. Accepted for publication July 3, 2009. Handling Editor: Peter Lancaster. This research is supported by the DFG Research Center MATHEONin Berlin.

†Institut f¨ur Mathematik, TU Berlin, Straße des 17. Juni 136, D-10623 Berlin, Germany (bruell@math.tu-berlin.de).

317

the point t₀ ∈R. Assuming that the pencil λE−A is regular, i.e., detλE−A = 0 for someλ∈C, one can explicitly write down the unique solution of (1.2) with the help of the Drazin inverse, as shown in [8]. The purpose of this paper is to obtain corresponding results for the discrete-time case (1.1).

Equations of the form (1.1) arise naturally by approximating ˙x(t) in (1.2) via an explicit finite difference method. Equation (1.1) is also a special form of a singular Leontief model in economics, see [5, 9]. Another application of (1.1) is the backward Leslie model [3]. The Leslie model is used to describe the evolution of the age distri- bution of a population at discrete time points. Therefore the population is divided into ndistinct equidistant age classes, e.g., 0-1 years, 1-2 years, ... Then the vector x^k ∈ Rⁿ in the Leslie model describes the number of individuals in each of the age classes at the discrete time pointk. It is further assumed that all successive discrete time points k and k+ 1 correspond to two time points in real time that are as far apart as the extent of one age classes is. With these assumptions, the Leslie model is given by

x^k+1 =











b₁ b₂ · · · b_n−1 b_n s₁ 0 · · · · · · 0

0 s₂ . .. ... ... . .. ... . .. ... 0 · · · 0 s_n−1 0











=:L

x^k,

with L∈R^n,n where b_i ≥0 fori= 1, . . . , nare the birth rates of the i-th age class in one period of time ands_i ∈[0,1] fori= 1, . . . , n−1 are the survival rates of the i-th age class in one period of time. Since in most cases elderly individuals are not likely to produce offsprings we can assume thatb_n=0 and thusLis singular. Given an age distribution we can use the Leslie model to estimate the age distribution in the future. If, however, we want to determine an age distribution in the past, given a present age distribution ˆx, we have to solve the Leslie Model backwards, i.e., we have to solve a system of the form

Lx^l+1 =x^l, withx⁰= ˆx, (1.3) withLsingular. System (1.3) is a special case of system (1.1).

Throughout the paper we will assume thatλE−A is a regular pencil. As shown in [6], any regular pencil can be reduced to theKronecker/Weierstraß canonical form

P(λE−A)Q=λ

I_nf 0

0 N

−

J 0 0 I_n∞

, (1.4)

where P, Q ∈ C^n,n are invertible, I_k ∈ C^k,k is the identity matrix of dimension k, J ∈C^nf,nf is in Jordan canonical form,N ∈C^n∞,n∞ is a nilpotent matrix in Jordan canonical form andn_f, n_∞∈Nwithn_f+n_∞=n. We see thatn_f is the number of finite eigenvalues andn_∞is the number of infinite eigenvalues. The form (1.4) allows

to determine the solution of (1.1) in changed coordinates, i.e., by transforming system (1.1) through

P⁻¹EQ⁻¹Qx^k+1=P⁻¹AQ⁻¹Qx^k+P⁻¹f^k, (1.5) we do not change the set of solutions. Adapting the state and the inhomogeneity to the new coordinates we define

x^k₁ x^k₂

:=Qx^k and f₁^k

f₂^k

:=P⁻¹f^k,

with partitioning analog to (1.5), i.e., x^k₁, f₁^k ∈ C^nf and x^k₂, f₂^k ∈ C^n∞. Then from (1.5) we see that in the new coordinates (1.1) can be decomposed into the two sub- problems

x^k+1₁ =Jx^k₁+f₁^k, (1.6a) Nx^k+1₂ =x^k₂+f₂^k, (1.6b) of which we can compute the solutions separately, see [2]. In this paper, however, we will determine representations of the solution in the original coordinates.

2. The Drazin inverse. The Drazin inverse is a generalization of the inverse of a matrix to potentially singular square matrices. The properties of the Drazin inverse make it very useful for finding solutions of systems of the form (1.1).

Definition 2.1. [8] Let E, A∈C^n,n, let the matrix pencilλE−A be regular and let the Kronecker canonical form ofλE−Abe given by (1.4). Then the quantity ν defined byN^ν =0,N^ν−1 =0, i.e., by the index of nilpotency of N in (1.4), if the nilpotent block in (1.4) is present and byν =0 if it is absent, is called the index of the matrix pencilλE−A, and denoted by ind(λE−A) =ν.

Definition 2.2. LetE∈C^n,n. Further, letν be the index of the matrix pencil λE−I_n. Thenν is also called theindexof E and denoted by ind(E) =ν.

Definition 2.3. LetE∈C^n,n have the indexν. A matrixX ∈C^n,n satisfying EX=XE,

XEX=X, (2.1)

XE^ν+1=E^ν, is called aDrazin inverseofE and denoted byE^D.

As shown in [8] the Drazin inverse of a matrix is uniquely determined. Several properties of the Drazin inverse will be used frequently in section 3, which is why we review them here.

Lemma 2.4. Consider matrices E, A∈C^n,n withEA=AE.Then EA^D =A^DE,

E^DA =AE^D, (2.2)

E^DA^D =A^DE^D.

Proof. See [8, Lemma 2.21].

Also, the following Theorem will be necessary in the next section. It represents a decomposition of a general square matrix into a part belonging to the non-zero eigenvalues and a part belonging to the zero eigenvalues.

Theorem 2.5. Let E∈C^n,n withν =ind(E).Then there is one and only one decomposition

E= ˜C+ ˜N (2.3)

with the properties

C˜N˜ = ˜NC˜= 0, N˜^ν = 0, N˜^ν−1= 0, ind( ˜C)≤1. (2.4) For this decomposition the following statements hold:

C˜^DN˜ = ˜NC˜^D= 0, E^D= ˜C^D,

C˜C˜^DC˜= ˜C, (2.5)

C˜^DC˜=E^DE,

C˜ =EE^DE, N˜ =E

I−E^DE .

Proof. See [8, Theorem 2.22].

Note, that the Drazin inverse and the decomposition (2.3) can easily be computed via the Jordan canonical form ofE. To see this, assume thatE∈C^n,nhas the Jordan canonical form

E=S

J 0

0 N

S⁻¹, (2.6)

where S ∈ C^n,n is invertible, J is invertible, and N only has zero as an eigenvalue.

Then, the Drazin inverse ofE is given by E^D=S

J⁻¹ 0

0 0

S⁻¹,

which can be shown by proving the properties (2.1) through basic computations. The matrices of decomposition (2.3) in this case can be written as

C˜ =S J 0

0 0

S⁻¹and ˜N =S 0 0

0 N

S⁻¹, (2.7)

which shows that ˜N only has zero as an eigenvalue and ˜C has all the non-zero eigen- values ofE. However, ˜C may also have the eigenvalue zero although in this case the eigenvalue zero is non-defective. We also remark that

P_E:=E^DE (2.8)

is a projector which follows from the properties of the Drazin inverse (2.1). Again, using the Jordan canonical form (2.6) we can write this projector as

P_E =E^DE=S I 0

0 0

S⁻¹,

which shows thatP_Eis, in functional analytic terms, the Riesz projection correspond- ing to the non-zero eigenvalues ofE. Analogously, (I−P_E) = (I−E^DE) is the Riesz projection corresponding to the zero eigenvalues ofE.

3. Basic theorems. Assume thatλE−A is a regular pencil and that E and Ado not commute. Using a nice trick, which is due to Campbell (see [4]), we can in this case rewrite system (1.1) as a system with commuting coefficient matrices.

Lemma 3.1. [4] LetE, A∈C^n,n with λE−Aregular.Letλ˜∈Cbe chosen such that the matrixλE˜ −A is nonsingular.Then the matrices

E˜:=

λE˜ −A₋₁

E, A˜:=

λE˜ −A₋₁ A

commute.

Thus, by multiplying (1.1) from the left with the invertible matrix

˜λE−A₋₁ and using the notation of Lemma 3.1 as well as ˜f^k:=(˜λE−A)⁻¹f^k we see that we obtain the equivalent system

Ex˜ ^k+1= ˜Ax^k+ ˜f^k, (3.1) with commuting coefficient matrices ˜Eand ˜A. Note, that this transformation does not change the state space/the coordinates of the system (1.1), since the multiplication is only executed from the left. Thus, the set of solutions is not changed. Because of Lemma 3.1 we will assume in the following that E and A already commute. Using (2.2) together with the definition (2.8) we see that in the case thatEandAcommute we also have

P_EP_A=P_AP_E,

which means that P_AP_E is again a projector. Also P_A(I −P_E), (I−P_A)P_E, and (I−P_A)(I−P_E) are projectors.

Remark 3.2. In the following we are going to decompose the complete problem (1.1) into four subproblems by projecting (1.1) through the following projectors:

P_AP_E corresponds to the non-zero, finite eigenvalues ofλE−A, P_A(I−P_E) corresponds to the infinite eigenvalues ofλE−A,

(I−P_A)P_E corresponds to the zero eigenvalues ofλE−A,

(I−P_A)(I−P_E) corresponds to the remaining (singular) part ofλE−A.

Assuming thatλE−Ais regular we are going to see that the singular part belonging to the projector (I−P_A)(I−P_E) vanishes.

Like [8, Lemma 2.24] we start by splitting system (1.1) into the two subsystems which occur by projecting (1.1) throughP_E and (I−P_E). The subsystem projected through P_E corresponds to (1.6a) and thus to the matrix ˜C as in 2.3 whereas the subsystem projected through (I−P_E) corresponds to (1.6b) and thus the matrix ˜N as in 2.3.

Lemma 3.3. Let E, A∈C^n,n with EA=AE and E = ˜C+ ˜N be the decompo- sition (2.3). Then system (1.1) is equivalent (in the sense that there is a one-to-one correspondence of solutions) to the system

Cx˜ ^k+1₁ =Ax^k₁+f₁^k, (3.2a) Nx˜ ^k+1₂ =Ax^k₂+f₂^k, (3.2b) for k∈K, where

x^k₁ :=E^DEx^k, x^k₂:=

I−E^DE x^k, f₁^k:=E^DEf^k, f₂^k :=

I−E^DE

f^k, (3.3)

for all k∈K⁺. With (3.3) subsystem (3.2a) is equivalent to the standard difference equation

x^k+1₁ =E^DAx^k₁+E^Df₁^k, for k∈K, (3.4)

Proof. Sincex^k =E^DEx^k+(I−E^DE)x^k=x^k₁+x^k₂we find that (1.1) is equivalent

to

C˜+ ˜N x^k+1₁ +x^k+1₂

=A

x^k₁+x^k₂

+f^k. (3.5)

Using (2.5), (2.2) we see that ˜Nx^k+1₁ =0, ˜Cx^k+1₂ =0, ˜Nf₁^k+1=0, and ˜Cf₂^k+1 =0.

Projecting (3.5) withP_E=E^DE= ˜C^DC, i.e., multiplying (3.5) with ˜˜ C^DC˜ from the left first leads to (3.2a) and then to (3.2b). Multiplying (3.2a) by ˜C^D = E^D and adding (I−C˜^DC)x˜ ^k+1₁ =0 finally gives the equivalence of (3.2a) and (3.4). A more detailed proof of Lemma 3.3 can be found in [1, Lemma 6].

System (3.2a) corresponds to the system projected byP_E and thus to the finite eigenvalues ofλE−Awhereas system (3.2b) corresponds to the system projected by (I−P_E) and thus to the infinite eigenvalues ofλE−A. Because of the linearity of (1.1) we first consider the homogeneous case.

Analogous to [8, Lemma 2.25] we obtain the following Lemma.

Lemma 3.4. Let E, A ∈C^n,n with EA =AE, k₀ ∈ Z and v ∈ Cⁿ.Then the following statements hold.

1.Let ˆv=E^DEv.Then

x^k :=(E^DA)^k−k0ˆv, k=k₀, k₀+ 1, . . . (3.6) solves the homogeneous linear discrete-time descriptor system

Ex^k+1 =Ax^k, k=k₀, k₀+ 1, . . . (3.7)

2.Let ˆv=A^DAv.Then

x^k :=(A^DE)^k0−kˆv, k=k₀, k₀−1, . . . (3.8) solves the homogeneous linear discrete-time descriptor system

Ex^k+1=Ax^k, k=k₀−1, k₀−2, . . . (3.9) 3.Let ˆv∈range

A^DA

∩range E^DE

.Then x^k :=

(E^DA)^k−k0ˆv, k=k₀, k₀−1, . . .

(A^DE)^k0−kˆv, k=k₀−1, k₀−2, . . . (3.10) solves the homogeneous linear discrete-time descriptor system

Ex^k+1=Ax^k, k∈Z. (3.11)

Proof.

1. With (2.1) and (2.2) we get

Ex^k+1=E(E^DA)(E^DA)^k−k0E^DEv

=A(E^DA)^k−k0E^DEE^DEv

=A(E^DA)^k−k0E^DEv

=Ax^k, for allk=k₀, k₀+ 1, . . .

2. In this case we obtain

Ax^k=A(A^DE)^k0−kA^DAv

=A(A^DE)(A^DE)^k0−k−1A^DAv

=E(A^DE)^k0−k−1A^DAA^DAv

=E(A^DE)^k0−k−1A^DAv

=Ex^k+1, for allk=k₀−1, k₀−2, . . .

3. This follows from 1. and 2., since the definitions of x^k0 from 1. and 2.

coincide.

Since by (2.2)

(E^DA)^k−k0E^DEv=E^DE(E^DA)^k−k0v, it is clear, that the solutionx^k stays in the subspace range

E^DE

for allk≥k₀. An analogous conclusion is possible for the case 2. in Lemma 3.4. In case 3. of Lemma 3.4 the solution even stays in range

A^DA

∩range E^DE

all the time. To verify that all solutions of the homogeneous discrete-time descriptor system are in the form given by Lemma 3.4 we make the following observation.

Theorem 3.5. Let E, A ∈ C^n,n with EA = AE and suppose that the pencil λE−Ais regular.Then,

(I−E^DE)A^DA= (I−E^DE). (3.12)

Proof. See [8, Lemma 2.26] as well as [1, Lemma 20].

Remark 3.6. Using (3.12) and (2.8) we see that under the assumption that E andAcommute we have

(I−P_A)(I−P_E) = (I−E^DE)−(I−E^DE)A^DA= 0, P_A(I−P_E) = (I−P_E)P_A= (I−P_E), and (I−P_A)P_E = (I−P_A).

Looking back at Remark 3.2 this proves that under the assumptions of Theorem 3.5 the part belonging to the projector (I−P_A)(I−P_E) indeed vanishes and thus the complete problem (1.1) really splits up into only three subproblems: one on P_AP_E, one on (I−P_E), and one on (I−P_A).

According to [8, Theorem 2.27] we obtain the following Theorem.

Theorem 3.7. Let E, A∈C^n,n withEA=AE be such thatλE−A is regular.

Also, letk₀∈Z.Then the following statements hold.

1.Let{x^k}k≥k0 be any solution of (3.7). Then{x^k}k≥k0 has the form (3.6) for somevˆ∈range

E^DE .

2.Let{x^k}k≤k0 be any solution of (3.9). Then{x^k}k≤k0 has the form (3.8) for somevˆ∈range

A^DA .

3.Let{x^k}_k∈Zbe any solution of (3.11). Then {x^k}_k∈Z has the form (3.10) for somevˆ∈range

A^DA

∩range E^DE

.

Proof. Using the decomposition (2.3), (2.5), and (2.2) we have

AN˜ =AE(I−E^DE) =E(I−E^DE)A= ˜NA. (3.13) Furthermore, we see that for anyx∈Cⁿ withANx˜ = 0 we also have

(I−E^DE)A^DANx˜ = 0.

Using (3.12) this implies

(I−E^DE) ˜Nx= 0.

Thus, using (2.5) we have shown that for anyx∈Cⁿ withANx˜ = 0 we have

Nx˜ = 0. (3.14)

Let {x^k}k∈Z be any solution of (3.7). From Lemma 3.3 we get{x^k₁}k≥k0, {x^k₂}k≥k0

withx^k=x^k₁+x^k₂ which solve (3.2), respectively. Withν=ind(E), using (2.4), (3.2), and (3.13) one then obtains

0 = ˜N^νx^k+1₂ = ˜N^ν−1Ax^k₂=AN˜^ν−1x^k₂,

for all k≥k₀. From this and from (3.14) we see that we also have ˜N^ν−1x^k₂ = 0 for allk≥k₀. Discarding the identity for k=k₀then yields

N˜^ν−1x^k₂ = 0, k≥k₀+ 1.

Shifting the indexk, i.e., replacing kbyk+ 1 shows that N˜^ν−1x^k+1₂ = 0, k+ 1≥k₀+ 1, which is the same as

N˜^ν−1x^k+1₂ = 0, k≥k₀. By repeating this procedureν−2 times we finally get

Nx˜ ^k₂= 0, k≥k₀. Using (3.2) once again, this implies

Ax^k₂= 0, and thus with (3.3) and (3.12) we have

x^k₂ = (I−E^DE)x^k₂ = (I−E^DE)A^DAx^k₂= 0,

which means that x^k =x^k₁ for allk≥k₀. Therefore, from Lemma 3.3 we know that {x^k₁} solves

x^k+1₁ = (E^DA)x^k₁,

for allk≥k₀. Applying this formula recursively shows that x^k₁= (E^DA)^k−k0x^k₁⁰,

for everyk≥k₀. Summing up those implications we have that for allk≥k₀

x^k=x^k₁= (E^DA)^k−k0x^k₁⁰ = (E^DA)^k−k0E^DEx^k0, (3.15) which shows part 1. To prove part 2., let {x^k}k≤k0 be any solution of (3.9). Set l₀:=−k₀andy^l:=x^−lforl≥l₀. By replacingk=−l in (3.9) one obtains

Ex^−l+1=Ax^−l, −l=−l₀−1,−l₀−2, . . . , which is equivalent to

Ex^−(l−1)=Ax^−l, l=l₀+ 1, l₀+ 2, . . . By definition we can see that{y^l}_l≥l0 is a solution of

Ey^l−1=Ay^l, l≥l₀+ 1,

and also a solution of

Ay^l+1=Ey^l, l≥l₀. Using identity (3.15) for this reversed system means that

y^l= (A^DE)^l−l0A^DAy^l0, for alll≥l₀. Undoing the replacements then yields

x^−l= (A^DE)^l−l0A^DAx^−l0, for alll≥l₀and thus

x^k= (A^DE)^−k+k0A^DAx^k0, for all−k≥ −k₀. Again, summing up these results shows that

x^k = (A^DE)^k0−kA^DAx^k0, (3.16) for allk≤k₀. Finally, to prove part 3., let {x^k}_k∈Z be any solution of (3.11). Then from (3.15) we have

x^k= (E^DA)^k−k0E^DEx^k0, for allk≥k₀and especially for k=k₀ we see that

x^k0=E^DEx^k0 ∈range E^DE

. Also we know from (3.16) that

x^k = (A^DE)^k0−kA^DAx^k0, for allk≤k₀and especially for k=k₀ we see that

x^k0 =A^DAx^k0 ∈range A^DA

. Thus, the claim of the Theorem follows with ˆv=x^k0.

One may think that it is not meaningful to look at case 3. of Theorem 3.7, since in most cases one starts at some time point and then calculates into the future.

But as shown by the following Lemma 3.8, also those solutions (where one starts at k₀ ∈Z and calculates a solution for k≥k₀) are almost completely in the subspace range

A^DA

∩range E^DE

.

Lemma 3.8. Let E, A ∈C^n,n with EA =AE be such that λE−A is regular.

Also, let k₀ ∈ Z and let ν_E =ind(E), ν_A =ind(A).Then the following statements hold.

1.Let {x^k}_k≥k0 be any solution of (3.7). Then for allk≥k₀+ν_A it holds that x^k ∈range

A^DA

∩range E^DE

.

2.Let {x^k}_k≤k0 be any solution of (3.9). Then for allk≤k₀−ν_E it holds that x^k ∈range

E^DE

∩range A^DA

.

Proof. Sincek≥k₀+ν_Ait follows that there exists ˆk≥0 such thatk= ˆk+k₀+ν_A. From Theorem 3.7 using (3.6) and (2.1) we then know that for somev∈Cⁿwe have

A^DAx^k =A^DA(E^DA)^k−k0E^DEv

=A^DA(E^D)^k−k0A^k−k0E^DEv

=A^DA(E^D)^k−k0A^νAA^kˆE^DEv

=A^DA(E^D)^k−k0A^DA^νA+1A^ˆkE^DEv

= (E^D)^k−k0A^DAA^DA^νA+1A^ˆkE^DEv

= (E^D)^k−k0A^DA^νA+1A^kˆE^DEv

= (E^DA)^k−k0E^DEv

=x^k. Also, we naturally get

E^DEx^k = E^DE(E^DA)^k−k0E^DEv

= (E^DA)^k−k0E^DEv=x^k, (3.17) and thus the assertion of part 1. follows. As in (3.17) one gets that A^DAx^k =x^k. Letk=−ˆk+k₀−ν_E with ˆk≥0. Then again for somev∈Cⁿ it follows that

E^DEx^k =E^DE(A^DE)^k0−kA^DAv

=E^DE(A^D)^k0−kE^k0−kA^DAv

=E^DE(A^D)^k0−kE^νEE^ˆkA^DAv

=E^DE(A^D)^k0−kE^DE^νE+1E^ˆkA^DAv

= (A^D)^k0−kE^DEE^DE^νE+1E^ˆkA^DAv

= (A^D)^k0−kE^DE^νE+1E^ˆkA^DAv

= (A^DE)^k0−kA^DAv

=x^k, which proves part 2.

To understand the relevance of Lemma 3.8, consider a homogeneous forward system, i.e., a system of the type (3.7), and assume that a consistent initial condition x^k0 ∈range

E^DE

is given. Assuming that EA=AE we can apply the projector A^DAto x^k0 obtaining a new consistent initial condition

x˜^k0 =A^DAx^k0 ∈range E^DE

∩range A^DA

.

Lemma 3.8 and the proof of Lemma 3.8 then show that for allk ≥k₀+ ind(A) we have

x˜^k =x^k.

Thus, it seems reasonable to demand x^k0 ∈range

A^DA

∩range E^DE

(3.18) in the first place.

Also, only in case that (3.18) holds, we get something like an invertibility of the operator that calculatesx^k+1 from x^k. To understand this, imagine that a fixedx^k0 is given. From this we calculate a finite number of stepsκinto the future. Thus, we havex^k0+κ. From this state we then calculateκ steps back into the past to obtain x˜^k0. We then havex^k0 = ˜x^k0 if condition (3.18) holds. Otherwise we cannot be sure thatx^k0 = ˜x^k0 holds, as shown in the following example.

Example 3.9. Consider the homogeneous linear discrete-time descriptor system defined by



 1 0 0 0 1 0 0 0 0





:=E

x^k+1=



 0 0 0 0 1 0 0 0 1





:=A

x^k, k≥0, x⁰=



 1 1 0



. (3.19)

Clearly, we have EA =AE, E^D = E, A^D =A and λE−A is regular. Thus, the pencil (E, A), corresponding to system (3.19), satisfies all assumptions of Lemma 3.8.

Since the index of the matrixA is ind(A) =1 this means that the iterate x¹ has to be in range

A^DA

. Indeed,

Ax⁰=



 0 1 0



, x¹=



 0 1 0



∈range A^DA

. (3.20)

Now let us calculate back one step from (3.20), i.e., let us consider the reversed system A˜x^l+1=E˜x^l, l≤0,x˜⁻¹=



 0 1 0



.

We see that

Ex˜⁻¹=



 0 1 0



, x˜⁰=



 0 1 0



,

and thus

x˜⁰=



 0 1 0



 =x⁰.

So far, we have characterized all the solutions of the homogeneous descriptor system. Thus, what we still need to characterize all solutions of (1.1) is one particular

solution of the inhomogeneous system. Using [8, Theorem 2.28] we can prove the following.

Theorem 3.10. Let E, A∈C^n,n with EA=AE be such thatλE−Ais regular.

Also, let ν_E =ind(E), ν_A =ind(A), {f^k}_k∈Z with f^k ∈Cⁿ and k₀ ∈Z.Then the following statements hold.

1.The linear discrete-time descriptor system

Ex^k+1=Ax^k+f^k, k≥k₀, has the particular solution{x^k₁+x^k₂}_k≥k0, where

x^k₁ :=

k−1

j=k0

(E^DA)^k−j−1E^Df^j,

x^k₂ := −(I−E^DE)^νE−1

i=0

(A^DE)ⁱA^Df^k+i,

for k ≥k₀.For the construction of the iterate x^k only the f_k with k ≥k₀ have to be employed.

2.The linear discrete-time descriptor system

Ex^k+1=Ax^k+f^k, k≤k₀−1, (3.21) has the particular solution{x^k₁+x^k₂}_k≤k0, where

x^k₁ :=(I−A^DA)

νA−1 i=0

(E^DA)ⁱE^Df^k−i−1, x^k₂ := − ^k0

j=k+1

(A^DE)^j−k−1A^Df^j−1,

for k≤k₀.For the construction of the iterate x^k only thef_k withk≤k₀−1 have to be employed.

Proof. LetE = ˜C+ ˜N be the decomposition (2.3). Then, using (2.2) we have the identities

E^DEx^k₁=

k−1

j=k0

(E^DA)^k−j−1E^DEE^Df^j =x^k₁,

(I−E^DE)x^k₂=−(I−E^DE)(I−E^DE)

νE−1 i=0

(A^DE)ⁱA^Df^k+i=x^k₂.

Using (2.5) and (2.1) one can also conclude, that for allk≥k₀ it follows that Cx˜ ^k+1₁ = ˜C ^k

j=k0

(E^DA)^k+1−j−1E^Df^j

= ˜C



^k−1

j=k0

(E^DA)^k−jE^Df^j+E^Df^k





= ˜C



(E^DA)

k−1

j=k0

(E^DA)^k−j−1E^Df^j+E^Df^k





=AE^DEx^k₁+E^DEf^k

=Ax^k₁+E^DEf^k, and with

(I−E^DE)E^νE=

(I−E^DE)E^DE^νE−1= 0, ifν_E≥1,

(I−E^DE) = (I−I) = 0, ifν_E= 0, (3.22) we obtain

Nx˜ ^k+1₂ =E(I−E^DE)x^k+1₂

=−(I−E^DE)

νE−1 i=0

(A^DE)ⁱ⁺¹f^k+i+1

=−(I−E^DE)^νE−2

i=0

(A^DE)ⁱ⁺¹f^k+i+1

=−(I−E^DE)A^DA^νE−1

i=1

(A^DE)ⁱf^k+i

=−A(I−E^DE)

νE−1 i=0

(A^DE)ⁱA^Df^k+i+ (I−E^DE)f^k

=Ax^k₂+ (I−E^DE)f^k,

by using (3.12). With these results and Lemma 3.3 one immediately gets that {x^k}_k≥k0 with

x^k=E^DEx^k₁+ (I−E^DE)x^k₂ =x^k₁+x^k₂

is a solution and thus part 1. of the assertion follows. To prove part 2. we perform a variable substitution. By replacingl :=−k and l₀ :=−k₀ in (3.21) one gets the system

Ex^−l+1=Ax^−l+f^−l, −l≤ −l₀−1, which is equivalent to the system

Ex^−(l−1)=Ax^−l+f^−l, l≥l₀+ 1.

By further replacingy^l:=x^−l forl≥l₀one gets

Ey^l−1=Ay^l+f^−l, l≥l₀+ 1.

Shifting the indexl, i.e., replacingl byl+ 1 shows that Ey^l=Ay^l+1+f^−l−1, l+ 1≥l₀+ 1, which in turn is equivalent to

Ay^l+1=Ey^l−f^−l−1, l≥l₀. Settingg^l:=−f^−l−1 we can finally write this equation as

Ay^l+1=Ey^l+g^l, l≥l₀.

From the results of the first part we then get a solution of this last system as y^l=

l−1 j=l0

(A^DE)^l−j−1A^Dg^j−(I−A^DA)^νA−1

i=0

(E^DA)ⁱE^Dg^l+i.

Undoing the replacementy^l=x^−lin this equations then leads to x^−l=−^l−1

j=l0

(A^DE)^l−j−1A^Df^−j−1+ (I−A^DA)

νA−1 i=0

(E^DA)ⁱE^Df^−(l+i)−1,

and undoing the replacementk=−l finally gives us x^k= (I−A^DA)^νA−1

i=0

(E^DA)ⁱE^Df^k−i−1−^−k−1

j=−k0

(A^DE)^−k−j−1A^Df^−j−1

= (I−A^DA)

νA−1 i=0

(E^DA)ⁱE^Df^k−i−1−

k0

j=k+1

(A^DE)^j−k−1A^Df^j−1.

The parts x^k₁ and x^k₂ of the solution in Theorem 3.10 part 1. and Lemma 3.3 correspond to each other. With (2.8) we see thatx^k₁ =P_Ex^k₁ corresponds to the finite eigenvalues of λE−A and x^k₂ = (I−P_E)x^k₂ corresponds to the infinite eigenvalues of λE−A. Theorem 3.10 shows that the problem (1.1) only decomposes into two subproblems if we only want to compute the solution into one direction, i.e.,k ≥0.

With the notation of Remark 3.2 we can say that in case 1. of Theorem 3.10 the projectorsP_EP_A andP_E(I−P_A) can be treated as one. If, however, we move to the case where we want to get a solution for allk∈Z, then we need all three projectors introduced in Remark 3.6. Similar to Lemma 3.3 we obtain the following result.

Lemma 3.11. Let E, A∈C^n,n with EA=AE be such that λE−A is regular.

Further, letE = ˜C+ ˜N and analogously A= ˜D+ ˜M be decompositions as in (2.3).

Let {x^k₁}_k∈Z,{x^k₂}_k∈Z,{x^k₃}_k∈Z be solutions of

Cx˜ ^k+1₁ = ˜Mx^k₁+ (I−A^DA)f^k, Cx˜ ^k+1₂ = ˜Dx^k₂+A^DAE^DEf^k, Nx˜ ^k+1₃ = ˜Dx^k₃+ (I−E^DE)f^k,