ECE 602 Fall 2010

Controllability and Observability of LTI Systems

by

Stanislaw H. Żak

October 21, 2010

In bear country, wear bells to avoid surprising bruins. Don’t approach a bear, but don’t run away from one either. Movement may incite a charge, and a bear can outrun you. If a bear approaches you, talk to it calmly in a low, firm voice. Slowly back away until the bear is out of sight. If you climb a tree, get at least 12 feet up. If a bear senses that its food may be stolen or that its cub is in danger, it may charge. If this happens, drop to the ground and assume a fetal position, protecting your head with your arms, and play dead. Keep your pack on; it may serve as armor. [4, pages 18–19]

We begin our discussion of linear system theory with a description of the concept of linearity by Mitchell J. Feigenbaum [3, page 3], who is a researcher of nonlinear systems. “Linearity means that the rule that determines what a piece of a system is going to do next is not influenced by what it is doing now. More precisely, this is intended in a differential or incremental sense: For a linear spring, the increase of its tension is proportional to the increment whereby it is stretched, with the ratio of these increments exactly independent of how much it has already been stretched. Such a spring can be stretched arbitrarily far, and in particular will never snap or break. Accordingly, no real spring is linear.” The real world is nonlinear. However, there is a number of reasons to investigate linear systems. Linear models are often used to approximate nonlinear systems. Many times, this approximation is sufficient for the controller design for the underlying nonlinear system. Knowledge of linear system theory helps to understand the intricate theory of nonlinear systems.

1 Reachability and Controllability

We first consider a linear, time-invariant, discrete-time system modeled by

x[k + 1] = Ax[k] + Bu[k], x[0] = x_{0},  (1)

where A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}. The solution to (1) is

x[i] = A^{i}x[0] + ∑_{k=0}^{i−1} A^{i−k−1}Bu[k],

which can be represented as

x[i] = A^{i}x[0] + [ B AB ⋯ A^{i−1}B ] [ u[i − 1] ; u[i − 2] ; ⋮ ; u[0] ] .  (2)

Let

U_{i} = [ B AB ⋯ A^{i−1}B ] , i = 1, 2, ….

Note that U_{i} ∈ ℝ^{n×mi}. If for some positive l,

rank U_{l} = rank U_{l+1},

then all the columns of A^{l}B are linearly dependent on those of U_{l}. This, in turn, implies that all the columns of A^{l+1}B, A^{l+2}B, … must also be linearly dependent on those of U_{l}. Hence,

rank U_{l} = rank U_{l+1} = rank U_{l+2} = …  (3)

The above implies that the rank of U_{i} increases by at least one when i is increased by one, until the maximum value of rank U_{i} is attained. The maximum value of the rank U_{i} is guaranteed to be achieved for i = n, which means that, we always have

rank U_{n} = rank U_{n+1} = rank U_{n+2} = …  (4)

It follows from (3) that if rank B = p, then

rank [ B AB ⋯ A^{n−1}B ] = rank [ B AB ⋯ A^{n−p}B ] .  (5)

We say that the system (1) is reachable if for any x_{f} there exists an integer q > 0 and a control sequence, {u[i] : i = 0, 1, …, q − 1}, that transfers x[0] = 0 to x[q] = x_{f}.

Theorem 1 The system (1) is reachable if and only if

rank [ B AB ⋯ A^{n−1}B ] = n.

Proof Using (2) where x[0] = 0 and x[q] = x_{f}, we obtain

x_{f} = ∑_{k=0}^{q−1} A^{q−k−1}Bu[k]

= [ B AB ⋯ A^{q−1}B ] [ u[q − 1] ; u[q − 2] ; ⋮ ; u[0] ] .  (6)

It follows from the above that for any x_{f} there exists a control sequence {u[i] : i = 0, 1, …, q − 1} that transfers x[0] = 0 to x[q] = x_{f} if and only if

rank [ B AB ⋯ A^{q−1}B ] = rank U_{q} = n.

By (4) the maximum value of the rank of U_{q} is guaranteed to be attained for q = n, which proves the theorem.

□

A closely related notion to reachability is the notion of controllability. The notion of controllability is related to the property of a controlled system being transferable from any given state to the origin 0 of the state space by means of an appropriately chosen control law.

Theorem 2 The system (1) is controllable if and only if

range (A^{n}) ⊂ range [ B AB ⋯ A^{n−1}B ] .

Proof Using the solution formula for the system (1), for the case when x[0] = x_{0} and x_{f} = x[q] = 0, we obtain

A^{q}x_{0} = − ∑_{k=0}^{q−1} A^{q−k−1}Bu[k]

= − [ B AB ⋯ A^{q−1}B ] [ u[q − 1] ; u[q − 2] ; ⋮ ; u[0] ] .  (7)

The system (1) is controllable if and only if for some q > 0 and arbitrary initial condition x_{0}, the vector A^{q}x_{0} is in the range of [ B AB ⋯ A^{q−1}B ] = U_{q}. Taking into account that the maximal range of U_{q} is guaranteed to be attained for q = n, the system (1) is controllable if and only if the condition of the theorem is satisfied.

□

Note that the condition of the above theorem can be equivalently represented as

rank [ B AB ⋯ A^{n−1}B ] = rank [ B AB ⋯ A^{n−1}B A^{n} ] .  (8)

We illustrate the above discussion with a simple example that we found in [2, page 482].

Example 1 Consider a discrete-time system modeled by

x[k + 1] = Ax[k] + bu[k]
= [ \begin{matrix}0 & a \\ 0 & 0 \end{matrix} ] x[k] + [ \begin{matrix}1 \\ 0 \end{matrix} ] u[k], a ∈ ℝ.  (9)

The above system model is not reachable because

rank [ b Ab ] = rank [ \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ] = 1 < 2.

It is easy to check using (6) that, for example, the state x_{f} = [ 0 1 ]^{⊤} is not reachable from x[0] = 0 because x_{f} does not belong to the range of [ b Ab ]. In fact, nonreachable states form the set,

\{c [ \begin{matrix}0 \\ 1 \end{matrix} ] , c ∈ ℝ\} .

However, the system (9) is controllable because for any a ∈ ℝ,

rank [ b Ab ] = rank [ \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ] = rank [ b Ab A^{2} ] = rank [ \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ] .

That is,

range (A^{2}) = range (O) ⊂ range [ b Ab ] .

Using (7), we can easily see that arbitrary initial state x(0) ∈ ℝ^{2} of the system (9) can be transferred to the origin of ℝ^{2} using, for example, the zero control sequence, u[0] = u[1] = 0. This is because A^{2} = O and hence A^{2}x[0] = 0 for any x[0] ∈ ℝ^{2}.

In summary, for discrete-time linear systems, reachability implies controllability, and the two notions are equivalent if the matrix A of the given discrete system is nonsingular.

We next discuss the notions of reachability and controllability for continuous-time linear systems.

We say that the system ẋ(t) = Ax(t) + Bu(t), where A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, or equivalently, the pair (A, B), is reachable if for any x_{f} ∈ ℝ^{n} there is t_{1} and a control law u(t) that transfers x(t_{0}) = 0 to x(t_{1}) = x_{f}.

We say that the system ẋ(t) = Ax(t) + Bu(t), or equivalently, the pair (A, B), is controllable if there is a control law u(t) that transfers any initial state x_{0} = x(t_{0}) at any time t_{0} to the origin 0 of the state space at some time t_{1} > t_{0}.

It turns out that in the case of continuous, time invariant, systems the two notions are equivalent. Indeed, from the solution formula for the controlled system, for x(0) = 0 and x(t_{1}) = x_{f}, we obtain

x_{f} = ∫_{0}^{t_{1}} e^{A(t_{1}−t)}Bu(t)dt.

Pre-multiplying the above equation by e^{−At_{1}} and rearranging, we get

v = ∫_{0}^{t_{1}} e^{−At}Bu(t)dt,  (10)

where v = e^{−At_{1}}x_{f}. On the other hand, from the solution formula for the controlled system, for x(0) = x_{0} and x(t_{1}) = 0, we obtain

0 = e^{At_{1}}x_{0} + ∫_{0}^{t_{1}} e^{A(t_{1}−t)}Bu(t)dt.

Pre-multiplying the above equation by e^{−At_{1}} and rearranging yields

−x_{0} = ∫_{0}^{t_{1}} e^{−At}Bu(t)dt.  (11)

Comparing (10) and (11), we conclude that reachability of the system ẋ(t) = Ax(t)+Bu(t) is equivalent to its controllability. This is not true in the case of discrete-time systems, where reachability implies controllability, and the two notions are equivalent if the matrix A of the given discrete system is nonsingular.

There are many criteria for checking if a given system is reachable/controllable or not. We present a few of them in this section.

Theorem 3 The following are equivalent:

(1) The system ẋ(t) = Ax(t) + Bu(t) is reachable;

(2) rank [ B AB ⋯ A^{n−1}B ] = n;

(3) The matrix

W (t_{0}, t_{1}) = ∫_{t_{0}}^{t_{1}} e^{−At}BB^{T} e^{−A^{⊤}t}dt

is nonsingular for all t_{1} > t_{0};

Proof We first prove the implication (1) ⇒ (2), that is, if the pair (A, B) is reachable, then the so called controllability matrix

[ B AB ⋯ A^{n−1}B ] ∈ ℝ^{n×mn}

is of full rank n. We prove this statement by contraposition. Thus, we assume that

rank [ B AB ⋯ A^{n−1}B ] < n,

then, there is a constant n-vector q ≠ 0 so that

q^{⊤}B = 0^{⊤}, q^{⊤}AB = 0^{⊤}, …, q^{⊤}A^{n−1}B = 0^{⊤}.

By the Cayley-Hamilton theorem the matrix A satisfies its own characteristic equation. Hence

A^{n} = −a_{n−1}A^{n−1} − ⋯ − a_{1}A − a_{0}I_{n}.

Therefore

q^{⊤}A^{n}B = q^{⊤} (−a_{n−1}A^{n−1}B − ⋯ − a_{1}AB − a_{0}B) = 0^{⊤}.

By induction

q^{⊤}A^{i}B = 0^{⊤} for i = n + 1, n + 2, …

Let now x(0) = 0 and x(t_{1}) = q. We will now show that there is no control law that can transfer the system from x(0) = 0 to x(t_{1}) = q. From the solution formula for the controlled system, we obtain

q = ∫_{0}^{t_{1}} e^{A(t_{1}−t)}Bu(t)dt.

We now premultiply the resulting equation by q^{⊤} to get

0 ≠ ∥q∥^{2} = ∫_{0}^{t_{1}} q^{⊤}e^{A(t_{1}−t)}Bu(t)dt = 0

because

q^{⊤}e^{A(t_{1}−t)}B = q^{⊤} (B + (t_{1} − t)AB + \frac{(t_{1} − t)^{2}}{2!} A^{2}B − ⋯) = 0^{⊤}.

Thus the system cannot be transferred from x(0) = 0 to x(t_{1}) = q, and hence the pair (A, B) is not reachable.

We will now prove, by contraposition, the implication (2) ⇒ (3), that is, if the controllability matrix is of full rank, then det W (t_{0}, t_{1}) ≠ 0 for any t_{1} > t_{0}. So assume that det W (t_{0}, t_{1}) = 0. Then, there is a nonzero n-vector q ∈ ℝ^{n} such that

q^{⊤} ∫_{t_{0}}^{t_{1}} e^{−At}BB^{⊤}e^{−A^{⊤}t}dt = 0

for all t ∈ [t_{0}, t_{1}]. We postmultiply the above equation by q to get

∫_{t_{0}}^{t_{1}} (q^{⊤}e^{−At}B) (B^{⊤}e^{−A^{⊤}t}q) dt = 0.

Let v(t) = B^{⊤}e^{−A^{⊤}t}q, then the above equation can be written as

∫_{t_{0}}^{t_{1}} ∥v(t)∥^{2}dt = 0.

However, the above is true if and only if v(t) = 0, that is, if and only if the rows of e^{−At}B are linearly dependent over the set of real numbers for all t ∈ [t_{0}, t_{1}]. Now, evaluating

q^{⊤}e^{−At}B = 0^{⊤}

and its successive derivatives with respect to t at t = 0, we obtain

q^{⊤}B = 0^{⊤}, q^{⊤}AB = 0^{⊤}, …, q^{⊤}A^{n−1}B = 0^{⊤},

which means that rank [ B AB ⋯ A^{n−1}B ] < n.

We now prove, constructively, the implication (3) ⇒ (1). Let x(t_{0}) = x_{0} be an arbitrary initial state and x(t_{1}) = x_{f} an arbitrary final state. Then, we claim that the control law

u(t) = B^{⊤}e^{−A^{⊤}t}W^{−1}(t_{0}, t_{1}) (e^{−At_{1}}x(t_{1}) − e^{−At_{0}}x_{0})  (12)

will transfer the system from x_{0} to x_{f}. Note that to construct the above control law the matrix W (t_{0}, t_{1}) must be invertible. Substituting (12) into

x(t_{1}) = e^{A(t_{1}−t_{0})}x_{0} + ∫_{t_{0}}^{t_{1}} e^{A(t_{1}−τ)}Bu(τ)dτ

yields

x(t_{1}) = e^{A(t_{1}−t_{0})}x_{0}
+e^{At_{1}} ∫_{t_{0}}^{t_{1}} e^{−Aτ}BB^{T} e^{−A^{T} τ}dτW^{−1}(t_{0}, t_{1}) (e^{−At_{1}}x(t_{1}) − e^{−At_{0}}x_{0}) .

Performing easy manipulations gives x(t_{1}) = x(t_{1}), which means that indeed the proposed control law does the required job. Thus, we have established equivalence between the four statements of the theorem.

□

We now give a necessary and sufficient condition for the pair (A, B) to be nonreachable.

Theorem 4 The pair (A, B) is nonreachable if and only if there is a similarity transformation z = T x such that

Ã = T AT^{−1} = [ \begin{matrix}A_{1} & A_{2} \\ O & A_{4} \end{matrix} ] , B̃ = T B = [ \begin{matrix}B & 1 \\ O \end{matrix} ] ,

where the pair (A_{1}, B_{1}) is reachable, A_{1} ∈ ℝ^{r×r}, B_{1} ∈ ℝ^{r×m}, and the rank of the controllability matrix of the pair (A, B) equals r.

Proof We first prove necessity (⇒). After forming the controllability matrix of the pair (A, B), we use elementary row operations to get

T [ B AB ⋯ A^{n−1}B ] = [ T B (T AT^{−1}) (T B) ⋯ (T AT^{−1})^{n−1} (T B) ]

= [ \begin{matrix}x & x & x & ⋯ & x & x & x \\ 0 & x & x & ⋯ & x & x & x \\ ⋮ & & & ⋮ & & & ⋮ \\ 0 & 0 & 0 & ⋯ & x & x & x \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ ⋮ & & & ⋮ & & & ⋮ \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

= [ \begin{matrix}B_{1} & A_{1}B_{1} & A_{1}^{2}B_{1} & ⋯ & A_{1}^{n−1}B_{1} \\ O & O & O & ⋯ & O \end{matrix} ] ,  (13)

where the symbol x denotes a “don’t care”, that is, an unspecified scalar. We now show that indeed

Ã = T AT^{−1} = [ \begin{matrix}A_{1} & A_{2} \\ A_{3} & A_{4} \end{matrix} ] , B̃ = T B = [ \begin{matrix}B & 1 \\ O \end{matrix} ] ,

where A_{3} = O. It is clear that T B must have the above form. If A_{3} were not a zero matrix, then we would have

ÃB̃ = [ \begin{matrix}A & 1 & B & 1 \\ A & 3 & B & 1 \end{matrix} ] .

Comparing the above with (13), we conclude that A_{3}B_{1} = O. Thus,

ÃB̃ = [ \begin{matrix}A & 1 & B & 1 \\ O \end{matrix} ] .

Next we consider

Ã^{2}B̃ = [ \begin{matrix}A & {2 \atop 1} & B & 1 \\ A & 3 & A & 1 & B & 1 \end{matrix} ] .

Again, comparing the above with (13), we conclude that

A_{3}A_{1}B_{1} = O,

and thus

Ã^{2}B̃ = [ \begin{matrix}A & {2 \atop 1} & B & 1 \\ O \end{matrix} ] .

Continuing in this manner, we conclude that A_{3}A_{1}^{n−1}B_{1} = O. Thus it follows that

A_{3} [ B_{1} A_{1}B_{1} ⋯ A_{1}^{n−1}B_{1} ] = O.

Because rank[ B_{1} A_{1}B_{1} ⋯ A_{1}^{n−1}B_{1} ] = r, that is, the controllability matrix of the pair (A_{1}, B_{1}) is of full rank, we have to have A_{3} = O, and the proof of necessity is complete.

To prove sufficiency (⇐), note that if there is a similarity transformation such that

Ã = T AT^{−1} = [ \begin{matrix}A_{1} & A_{2} \\ O & A_{4} \end{matrix} ] , B̃ = T B = [ \begin{matrix}B & 1 \\ O \end{matrix} ] ,

then the controllability matrix of the pair (Ã, B̃) has the form

[ \begin{matrix}B_{1} & A_{1}B_{1} & A_{1}^{2}B_{1} & ⋯ & A_{1}^{n−1}B_{1} \\ O & O & O & ⋯ & O \end{matrix} ] .

Hence, the pair (Ã, B̃) is nonreachable. Because the similarity transformation preserves the reachability property, the pair (A, B) is nonreachable.

□

If the eigenvalues of the noncontrollable part of a given pair (A, B) are all in the open left-hand complex plane, that is, the nonreachable part is asymptotically stable, then the pair (A, B) is called stabilizable.

We now give yet another test for reachability. This test is also known as the Popov-Belevitch-Hautus (PBH) eigenvector test. We denote the set of eigenvalues of a matrix A as eig(A).

Theorem 5 The pair (A, B) is reachable if and only if

rank [ sI_{n} − A B ] = n for all s ∈ eig(A).

Proof We first prove the necessity part (⇒) by contraposition. If there is a vector q ≠ 0 such that for some s ∈ eig(A),

q^{⊤} [ sI_{n} − A B ] = 0^{⊤},

that is,

q^{⊤}A = sq^{⊤}, q^{⊤}B = 0^{⊤},

then

q^{⊤}AB = sq^{⊤}B = 0^{⊤},
q^{⊤}A^{2}B = sq^{⊤}AB = 0^{⊤},

and so on, until

q^{⊤}A^{n−1}B = sq^{⊤}A^{n−2}B = 0^{⊤}.

We write the above equations in the form

q^{⊤} [ B AB ⋯ A^{n−1}B ] = 0^{⊤},

which means that the pair (A, B) is nonreachable.

We now prove the sufficiency part (⇐) also by contraposition. So we assume that rank [ B AB ⋯ A^{n−1}B ] = r < n. By Theorem 4, there exists a state variable transformation such that in the new basis the pair (A, B) takes the form

Ã = T AT^{−1} = [ \begin{matrix}A_{1} & A_{2} \\ O & A_{4} \end{matrix} ] , B̃ = T B = [ \begin{matrix}B & 1 \\ O \end{matrix} ] .

We choose q of the form

q^{⊤} = [ 0 z ] ,

where z ≠ 0 is a left eigenvector of A_{4}, that is,

zA_{4} = sz,

where s ∈ eig(A_{4}). Thus

q^{⊤}Ã = [ 0 z ] Ã
= [ 0 sz ]
= sq^{⊤}.

Clearly

q^{⊤} [ sI_{n} − Ã B̃ ] = 0^{⊤},

which means that the rank of the matrix [ sI_{n} − Ã B̃ ] is less than n, and therefore the proof of the sufficiency part is complete.

□

2 Observability and Constructability

As we have seen in the previous section, system reachability implies the ability to completely control the entire state of the system. Suppose now that the system state is not directly accessible. Instead, we have the output of the system,

y = Cx + Du,

where C ∈ ℝ^{p×n}, p ≤ n, and D ∈ ℝ^{p×m}. However, we still want to know the behavior of the entire state.

We say that the system

\begin{matrix}ẋ & = & Ax + Bu \\ y & = & Cx + Du, \end{matrix} \}

or equivalently the pair (A, C), is observable if there is a finite t_{1} > t_{0} such that for arbitrary u(t) and resulting y(t) over [t_{0}, t_{1}], we can determine x(t_{0}) from complete knowledge of the system input u and output y.

Note that once x(t_{0}) is known, we can determine x(t) from knowledge of u(t) and y(t) over any finite time interval [t_{0}, t_{1}]. We now show how to constructively determine x(t_{0}), given u(t) and y(t). While doing so we will establish a sufficiency condition for the system to be observable. The condition is also necessary for the system observability as we show it next. To proceed with constructive determination of the state vector, we note that the solution y(t) is given by

y(t) = Ce^{A(t−t_{0})}x_{0} + ∫_{t_{0}}^{t} Ce^{A(t−τ)}Bu(τ)dτ + Du(t).

We subtract ∫_{t_{0}}^{t} Ce^{A(t−τ)}Bu(τ)dτ + Du(t) from both sides of the above equation. Let

g(t) = y(t) − ∫_{t_{0}}^{t} Ce^{A(t−τ)}Bu(τ)dτ − Du(t),

then we have

g(t) = Ce^{A(t−t_{0})}x(t_{0}),

where g is known to us. Our goal now is to determine x(t_{0}). Having x(t_{0}), we can determine the entire x(t) for all t ∈ [t_{0}, t_{1}] from the formula

x(t) = e^{A(t−t_{0})}x_{0} + ∫_{t_{0}}^{t} e^{A(t−τ)}Bu(τ)dτ.

Pre-multiplying both side of g(t) by e^{A^{⊤}(t−t_{0})}C^{⊤} and integrating the resulting expression between the limits t_{0} and t_{1}, we get

∫_{t_{0}}^{t_{1}} e^{A^{⊤}(t−t_{0})}C^{⊤}Ce^{A(t−t_{0})}dt x_{0} = ∫_{t_{0}}^{t_{1}} e^{A^{⊤}(t−t_{0})}C^{⊤}g(t)dt.

Let

V (t_{0}, t_{1}) = ∫_{t_{0}}^{t_{1}} e^{A^{⊤}t}C^{⊤}Ce^{At}dt.

Then, after performing some manipulations and assuming that the matrix V (t_{0}, t_{1}) is invertible, we obtain

x_{0} = e^{At_{0}}V^{−1}(t_{0}, t_{1})e^{A^{⊤}t_{0}} ∫_{t_{0}}^{t_{1}} e^{A^{⊤}(t−t_{0})}C^{⊤}g(t)dt.

Knowledge of x_{0} allows us to reconstruct the entire state x(t) over the interval [t_{0}, t_{1}]. We conclude that if the matrix V (t_{0}, t_{1}) is invertible, then the system is observable. We will now show that the invertibility of V (t_{0}, t_{1}) is also necessary for observability. We first note that one can use similar arguments to those in the previous section to show that V (t_{0}, t_{1}) is nonsingular if and only if the n columns of the matrix

Ce^{At} are linearly independent for all t ∈ [0, ∞) over the set of real numbers. Hence, if V (t_{0}, t_{1}) is singular, there exists a nonzero constant vector, say x_{a}, such that V (t_{0}, t_{1})x_{a} = 0. This implies that

g(t) = Ce^{At}x_{0} = Ce^{At} (x_{0} + x_{a}) .

Thus, x(0) = x_{0} + x_{a} yields the same response as x(0) = x_{0}, which means that we cannot determine the system state, or in other words, the state fails to be observable. In view of the above result, it follows that by repeating essentially the same arguments used in the previous section we can prove the following theorem:

Theorem 6 The following statements are equivalent:

(1) The pair (A, C) is observable;

(2) The matrix V (t_{0}, t_{1}) is nonsingular for all t_{1} > t_{0};

(3) The observability matrix

[ C ; CA ; ⋮ ; CA^{n−1} ] ∈ ℝ^{pn×n}

is of full rank n.

(4)

rank [ \begin{matrix}sI_{n} − A \\ C \end{matrix} ] = n for all s ∈ eig(A).

We can also prove analogous result to Theorem 4 for the given pair (A, C), that is, using a similarity transformation we can separate the observable part from the nonobservable. If the eigenvalues of the nonobservable part of a given pair (A, C) are all in the open left-hand complex plane, that is, the nonobservable part is asymptotically stable, then we say that the pair (A, C) is detectable.

A related notion to observability is the notion of constructability. We say that the system

\begin{matrix}ẋ & = & Ax + Bu \\ y & = & Cx + Du, \end{matrix} \}

or equivalently the pair (A, C), is constructable if there is a finite t_{1} > t_{0} such that for arbitrary u(t) and resulting y(t) over [t_{0}, t_{1}] we can determine x(t_{1}) from complete knowledge of the system input u and output y.

One can verify that in the case of continuous, time invariant systems, observability is equivalent to constructability. In the case of discrete-time systems observability implies constructability, and the two notions are equivalent if the matrix A of the given discrete system is nonsingular.

3 Companion Forms

In this section, we discuss two types of special forms of a given linear dynamic system model represented by the triple (A, B, C). These forms are obtained by a change of state variables, and reveal structural properties of the model. We will use the above mentioned forms to construct algorithms for pole placement. The pole placement algorithms will then be used to design state-feedback controllers, as well as state estimators. We begin by introducing the controller companion form, or for short, controller form.

3.1 Controller Form

We begin by considering a single-input, continuous-time, model represented by

ẋ(t) = Ax(t) + bu(t),

where the pair (A, b) is assumed to be reachable, or equivalently, controllable. This means that

rank [ b Ab ⋯ A^{n−1}b ] = n.

We select the last row of the inverse of the controllability matrix. Let q_{1} be that row. Next, we form the matrix

T = [ q_{1} ; q_{1}A ; ⋮ ; q_{1}A^{n−1} ] .

Note that T is invertible. Indeed, because

T [ b Ab ⋯ A^{n−1}b ] = [ \begin{matrix}0 & 0 & ⋯ & 0 & 1 \\ 0 & 0 & ⋯ & 1 & x \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ 1 & x & ⋯ & x & x \end{matrix} ] ,

this implies that T must be nonsingular. In the above, we used the symbol x to denote “don’t care”, unspecified, scalars in our present discussion. Consider now the state variable transformation, x̃ = T x. Then, in the new coordinates, the system model is

˙x̃(t) = T AT^{−1}x̃(t) + T bu(t)
= Ãx̃(t) + b̃u(t).

The matrices Ã and b̃ have particular structures that we now discuss. We first analyze the structure of b̃. Because q_{1} is the last row of the inverse of the controllability matrix, we have

q_{1}b = q_{1}Ab = ⋯ = q_{1}A^{n−2}b = 0,

and

q_{1}A^{n−1}b = 1.

Hence,

b̃ = T b = [ q_{1}b ; q_{1}Ab ; ⋮ ; q_{1}A^{n−2}b ; q_{1}A^{n−1}b ] = [ 0 0 ⋮ 0 1 ] .

The structure of Ã is revealed by considering the relation T AT^{−1} = Ã represented as

T A = ÃT .

The left-hand side of the above matrix equation is

T A = [ q_{1}A ; q_{1}A^{2} ; ⋮ ; q_{1}A^{n−1} ; q_{1}A^{n} ] .

By the Cayley-Hamilton theorem,

A^{n} = −a_{0}I_{n} − a_{1}A − ⋯ − a_{n−1}A^{n−1},

and hence

q_{1}A^{n} = −a_{0}q_{1} − a_{1}q_{1}A − ⋯ − a_{n−1}q_{1}A^{n−1}.

Comparing both sides of the equation T A = ÃT, and taking into account the Cayley-Hamilton theorem, we get

Ã = [ \begin{matrix}0 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 1 \\ −a_{0} & −a_{1} & −a_{2} & ⋯ & −a_{n−2} & −a_{n−1} \end{matrix} ] .

Note that the coefficients of the characteristic polynomial of A are immediately apparent by inspecting the last row of Ã. There are other benefits of the pair (A, b) being given in its controller form that we discuss in Section 4. We now illustrate the above algorithm for reducing a single-input system into the controller form with a numerical example. We now generalize the above method of transforming the given pair (A, B) into the controller form for multi-input systems. We consider a controllable pair (A, B) where A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, m ≤ n, and rank B = m. The last assumption we made is just for convenience to simplify further manipulations. This assumption implies that all inputs are mutually independent, which is usually the case in practical applications. We first form the controllability matrix of the pair (A, B) and represent it as

[ b_{1} b_{2} ⋯ b_{m} Ab_{1} Ab_{2} ⋯ Ab_{m} ⋯ A^{n−1}b_{1} ⋯ A^{n−1}b_{m} ] ,  (14)

where b_{i}, i = 1, 2, …, m, is the i-th column of B. The above controllability matrix is of full rank because we assumed that the pair (A, B) is controllable. Thus, we can select n linearly independent columns from (14). We select these columns proceeding from left to right. Then, we rearrange the selected columns to form a n × n nonsingular matrix L of the form

L = [ b_{1} Ab_{1} ⋯ A^{d_{1}−1}b_{1} b_{2} ⋯ A^{d_{2}−1}b_{2} ⋯ b_{m} ⋯ A^{d_{m}−1}b_{m} ] .

We call the m integers d_{i} the controllability indices of the pair (A, B). Note that

∑_{i=1}^{m} d_{i} = n.

We call the integer

d = max{d_{i} : i = 1, 2, …, m},

the controllability index of the pair (A, B). Observe that all m columns of B are present in L because we assumed that B is of full rank and the way we selected mutually independent columns from the controllability matrix (14) to construct the matrix L. Furthermore, if the column A^{k}b_{j} is present in L, then so is A^{k−1}b_{j}. To proceed further, we let

σ_{k} = ∑_{i=1}^{k} d_{i}, for k = 1, 2, …, m.

Note that σ_{1} = d_{1}, σ_{2} = d_{1} + d_{2}, …, σ_{m} = ∑_{i=1}^{m} d_{i} = n. We now select m rows from L^{−1}. We denote the selected rows by q_{k}, where q_{k} is the σ_{k}-th row of L^{−1}. Next, we form the n × n matrix

T = [ q_{1} ; q_{1}A ; ⋮ ; q_{1}A^{d_{1}−1} ; q_{2} ; ⋮ ; q_{2}A^{d_{2}−1} ; ⋮ ; q_{m} ; ⋮ ; q_{m}A^{d_{m}−1} ] .

We can show that T is nonsingular by computing the product T L and noticing that det(T L) = ±1. We define a state-variable transformation x̃ = T x, and then using similar arguments as in the single-input case, we arrive at the special structure of the pair

(Ã, B̃) = (T AT^{−1}, T B) ,

where

Ã = [ \begin{matrix}0 & 1 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & & 0 & 0 & ⋯ & 0 \\ & & & ... & & ⋮ & & & ⋮ & & ⋮ & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 0 & 0 & ⋯ & 0 & & 0 & 0 & ⋯ & 0 \\ x & x & x & ⋯ & x & x & x & ⋯ & x & ⋯ & x & x & ⋯ & x \\ 0 & 0 & 0 & ⋯ & 0 & 0 & 1 & ⋯ & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & & & & ⋮ & ⋮ & & ... & ⋮ & & ⋮ & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 1 & & 0 & 0 & ⋯ & 0 \\ x & x & x & ⋯ & x & x & x & ⋯ & x & ⋯ & x & x & ⋯ & x \\ ⋮ & & & & & & ⋮ & & & ... & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & ⋯ & 0 & 1 & ⋯ & 0 \\ ⋮ & & & & ⋮ & ⋮ & & & ⋮ & & ⋮ & & ... & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & 0 & & 0 & 0 & ⋯ & 1 \\ x & x & x & ⋯ & x & x & x & ⋯ & x & ⋯ & x & x & ⋯ & x \end{matrix} ] .

Note that the m diagonal blocks of Ã have the structure of the controller form as in the single-input case. The dimensions of the diagonal blocks are d_{i} × d_{i}, i = 1, 2, …, m. The off-diagonal blocks consist of zero elements except for their respective last rows. Thus, all information about Ã, as well as A, can be derived from knowledge of the controllability indices, and the m nonzero rows containing the elements marked using x, of the matrix Ã. The matrix B̃ has the form,

B̃ = [ \begin{matrix}0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 1 & x & x & x & x \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 1 & x & x & x \\ ⋮ & & & & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ] .

The nonzero rows of B̃ correspond to the rows of Ã containing the elements marked using x. We now illustrate the above algorithm for reducing a multi-input system model into the controller form with a numerical example.

3.2 Observer Form

In this subsection, we use duality and the algorithms for reducing reachable systems into controller forms to derive analogous results for observable systems. We consider an observable dynamic system model

\begin{matrix}ẋ(t) & = & Ax(t) \\ y(t) & = & Cx(t), \end{matrix} \}  (15)

or, equivalently, the observable pair (A, C), where A ∈ ℝ^{n×n}, C ∈ ℝ^{p×n}, p ≤ n, and rank C = p. We omitted the input variable u for convenience because it plays no role in the subsequent discussion. We next consider the dual system model associated with the system (15),

ż(t) = A^{⊤}z(t) + C^{⊤}v(t).

Because the pair (A, C) is observable, the dual pair (A^{⊤}, C^{⊤}) is reachable. Therefore, the pair (A^{⊤}, C^{⊤}) can be transformed into the controller form using the algorithm from the previous subsection. We then take the dual of the result to get

\begin{matrix}˙x̂(t) & = & Âx̂ \\ y(t) & = & Ĉx̂, \end{matrix} \}

where

Â = [ \begin{matrix}Â_{11} & Â_{12} & ⋯ & Â_{1p} \\ Â_{21} & Â_{22} & ⋯ & Â_{2p} \\ ⋮ & & & ⋮ \\ Â_{p1} & Â_{p2} & ⋯ & Â_{pp} \end{matrix} ] .

Each diagonal submatrix Â_{ii} ∈ ℝ^{d̂_{i}×d̂_{i}} of Â has the form

Â_{ii} = [ \begin{matrix}0 & 0 & ⋯ & 0 & x \\ 1 & 0 & ⋯ & 0 & x \\ ⋮ & & ... & & ⋮ \\ 0 & 0 & ⋯ & 1 & x \end{matrix} ] ,

which is just the transpose of the controller form for the single-input case. The integers d̂_{i}, i = 1, 2, …, p are the controllability indices of the controllable pair (A^{⊤}, C^{⊤}). The off-diagonal blocks, j ≠ i, have the form

Â_{ji} = [ \begin{matrix}0 & 0 & ⋯ & 0 & x \\ 0 & 0 & ⋯ & 0 & x \\ ⋮ & & & & ⋮ \\ 0 & 0 & ⋯ & 0 & x \end{matrix} ] ,

that is, they consist of zeros except for their last columns. The matrix Ĉ consists of p blocks and has the form

Ĉ = [ \begin{matrix}0 & 0 & ⋯ & 1 & 0 & 0 & ⋯ & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & x & 0 & 0 & ⋯ & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & & & ⋮ & ⋮ & & & ⋮ & & ⋮ & & & ⋮ \\ 0 & 0 & ⋯ & x & 0 & 0 & ⋯ & x & ⋯ & 0 & 0 & ⋯ & 1 \end{matrix} ] .

The p controllability indices of the pair (A^{⊤}, C^{⊤}) are called the observability indices of the pair (A, C). Note that

∑_{i=1}^{p} d̂_{i} = n.

Similarly as in the controller form, we define the observability index of the pair (A, C) to be the integer

d̂= max{d̂_{i} : i = 1, 2, …, p}.

4 Linear State-Feedback Control

In the following sections, we discuss methods for a feedback controller design for linear systems. The design process involves three steps. The first step is the design of a statefeedback control law. In this step, we assume that we have all states available to us for feedback purposes. In general, this may not be the case. The assumption that all the states are available allows us to proceed with the state-feedback control law design. We then proceed with the second step that involves the design of an estimator, also referred to as an observer of the state vector. The estimator should use only the input and output of the plant to be controlled to generate an estimate of the plant state. The last step is to combine the first two steps in that the control law, designed in the first step, uses the state estimate instead of the true state vector. The result of this step is a combined controllerestimator compensator. We first discuss the problem of designing a linear state-feedback control law. In the following sections, we present methods for constructing estimators and combined controller-estimator compensators.

The linear state-feedback control law, for a system modeled by ẋ = Ax + Bu, is the feedback of a linear combination of all the state variables, and has the form

u = −Kx,

where K ∈ ℝ^{m×n} is a constant matrix. The closed-loop system then is

ẋ = (A − BK) x.

The poles of the closed-loop system are the roots of the characteristic equation

det (sI_{n} − A + BK) = 0.

The linear state-feedback control law design consists of selecting the gains

k_{ij}, i = 1, 2, …, m, j = 1, 2, …, n,

so that the roots of the closed-loop characteristic equation

det (sI_{n} − A + BK) = 0

are in desirable locations in the complex plane. We assume that a designer has made the selection of the desired poles of the closed-loop system and they are:

s_{1}, s_{2}, …, s_{n}.

The desired closed-loop poles can be real or complex. If they are complex, then they must come in complex conjugate pairs. This is because we use only real gains k_{ij}. Having selected the desired closed-loop poles we can form the desired closed-loop characteristic polynomial,

α_{c}(s) = (s − s_{1})(s − s_{2}) ⋯ (s − s_{n})
= s^{n} + α_{n−1}s^{n−1} + ⋯ + α_{1}s + α_{0}.

Our goal is to select a feedback matrix K such that

det (sI_{n} − A + BK) = s^{n} + α_{n−1}s^{n−1} + ⋯ + α_{1}s + α_{0}.

The above problem is also referred to as the pole placement problem. We first discuss the pole placement problem for the single-input plants. In this case K = k ∈ ℝ^{1×n}. The solution to the problem is easily obtained if the pair (A, b) is already in the controller companion form. In such a case we have

A − bk = [ \begin{matrix}0 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & & & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 1 \\ −a_{0} − k_{1} & −a_{1} − k_{2} & −a_{2} − k_{3} & ⋯ & −a_{n−2} − k_{n−1} & −a_{n−1} − k_{n} \end{matrix} ] .

Hence, the desired gains are

k_{1} = α_{0} − a_{0},
k_{2} = α_{1} − a_{1},
⋮
k_{n} = α_{n−1} − a_{n−1}.

If the pair (A, b) is not in the controller companion form, we first transform it into the companion form, and then compute the gain vector k̃ such that

det (sI_{n} − Ã + b̃k̃) = s^{n} + α_{n−1}s^{n−1} + ⋯ + α_{1}s + α_{0}.

Thus,

k̃ = [ α_{0} − a_{0} α_{1} − a_{1} ⋯ α_{n−1} − a_{n−1} ] .

Then,

k = k̃T ,

where T is the transformation that brings the pair (A, b) into the controller companion form.

We can represent the above formula for the gain matrix in an alternative way. For this note that

k̃T = [ α_{0} − a_{0} α_{1} − a_{1} ⋯ α_{n−1} − a_{n−1} ] [ q_{1} ; q_{1}A ; ⋮ ; q_{1}A^{n−1} ]

= q_{1} (α_{0}I_{n} + α_{1}A + ⋯ + α_{n−1}A^{n−1}) − q_{1} (a_{0}I_{n} + a_{1}A + ⋯ + a_{n−1}A^{n−1}) .

By the Cayley-Hamilton theorem,

A^{n} = − (a_{0}I_{n} + a_{1}A + ⋯ + a_{n−1}A^{n−1}) .

Hence,

k = q_{1}α_{c} (A) .

The above expression for the gain row vector was proposed by Ackermann in 1972, and is now referred to as the Ackermann’s formula for pole placement.

We now present a pole placement algorithm for multi-input systems. If the pair (A, B) is already in the controller companion form, then we may proceed as follows. First, represent the matrix B as

B = [ \begin{matrix}0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 1 & x & x & x & x \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 1 & x & x & x \\ ⋮ & & & & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ] = [ \begin{matrix}0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 1 & 0 & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}1 & x & ⋯ & x & x \\ 0 & 1 & ⋯ & x & x \\ ⋮ & & ... & & ⋮ \\ 0 & 0 & ⋯ & 1 & x \\ 0 & 0 & ⋯ & 0 & 1 \end{matrix} ] = B̂Γ,

where the square and nonsingular matrix Γ consists of the nonzero rows of B. Next, let

K̂ = ΓK.

Notice that

B̂K̂ = [ \begin{matrix}0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ k̂_{11} & k̂_{12} & ⋯ & k̂_{1 n−1} & k̂_{1n} \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ k̂_{21} & k̂_{22} & ⋯ & k̂_{2 n−1} & k̂_{2n} \\ ⋮ & & & & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & & ⋮ \\ k̂_{m1} & k̂_{m2} & ⋯ & k̂_{m n−1} & k̂_{mn} \end{matrix} ] ,

that is, the nonzero rows in the product B̂K̂ match the nonzero rows of the matrix A in the controller companion form. We can then, for example, select the gains k_{ij}, i = 1, 2, …, m, j = 1, 2, …, n, so that

A − BK = A − B̂K̂ = [ \begin{matrix}0 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & & & & & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & 1 \\ −α_{0} & −α_{1} & −α_{2} & ⋯ & −α_{n−2} & −α_{n−1} \end{matrix} ] ,

where

K = Γ^{−1}K̂.

If the pair (A, B) is not in the controller companion form, we first transform it into this form, then compute the gain matrix that allocates the closed-loop poles into the desired locations for the pair (A, B) in the controller form. The gain matrix K that allocates the closed-loop poles into the prespecified locations for the pair (A, B) in the original coordinates is then given by

K = Γ^{−1}K̂T ,

where T is the transformation matrix that brings the pair (A, B) into the controller companion form. The above algorithm for pole placement for multi-input systems is more of theoretical value rather than practical. This algorithm is not well suited for numerical implementations because the transformation of a given pair (A, B) into the controller companion form suffers from poor numerical properties. For a discussion of pole placement numerically stable algorithms for multi-input systems, we refer the reader to Jamshidi, Tarokh, and Shafai [1].

Unlike in the single-input case, a solution to the pole placement problem for a multi-input system is not unique. Therefore, one can use the remaining degrees of freedom to achieve secondary goals.

Using the results preceding the above discussion, we can state and prove a fundamental theorem of linear systems.

Theorem 7 The pole placement problem is solvable for all choices of n desired closed-loop poles, symmetric with respect to the real axis, if and only if the given pair (A, B) is reachable.

Proof The pair (A, B) is reachable, if and only if it can be transformed into the controller canonical form. Once the transformation is performed, we can solve the pole placement problem for the given set of desired closed-loop poles, symmetric with respect to the real axis. We then transform the pair (A, B) and the gain matrix back into the original coordinates. Because the similarity transformation does not affect neither controllability nor the characteristic polynomial, the eigenvalues of A − BK are precisely the desired prespecified closed-loop poles. This completes the proof of the necessity part.

We use a proof by contraposition to prove the sufficiency part (⇒). Assume that the pair (A, B) is nonreachable. By Theorem 4, there is a similarity transformation z = T x such that the pair (A, B) in the new coordinates has the form

Ã = T AT^{−1} = [ \begin{matrix}A_{1} & A_{2} \\ O & A_{4} \end{matrix} ] , B̃ = T B = [ \begin{matrix}B & 1 \\ O \end{matrix} ] ,

where the pair (A_{1}, B_{1}) is reachable, A_{1} ∈ ℝ^{r×r}, and B_{1} ∈ ℝ^{r×m}. Let

u = −K̃z = − [ K_{1} K_{2} ] z,

where K_{1} ∈ ℝ^{m×r} and K_{2} ∈ ℝ^{m×(n−r)}. Then,

Ã − B̃K̃ = [ \begin{matrix}A_{1} − B_{1}K_{1} & A_{2} − B_{1}K_{2} \\ O & A_{4} \end{matrix} ] .  (16)

It follows from (16) that the nonreachable portion of the system is not affected by the statefeedback, that is, the eigenvalues of A_{4} cannot be allocated. Hence, the pole placement problem cannot be solved if the pair (Ã, B̃), or equivalently the pair (A, B), is nonreachable, which completes the proof of the sufficiency part.

□

For an alternative proof of this important result, the reader may consult Wonham [5].

References

[1] M. Jamshidi, M. Tarokh, and B. Shafai. Computer-Aided Analysis and Design of Linear Control Systems. Prentice Hall, Englewood Cliffs, New Jersey 07632, 1992.

[2] T. Kaczorek. Wektory i Macierze w Automatyce i Elektrotechnice. Wydawnictwa Naukowe-Techniczne—Scientific-Technical Publishers, Warszawa, second edition, 1998.

[3] H.-O. Peitgen, H. Jürgens, and D. Saupe, editors. Chaos and Fractals: New Frontiers of Science. Springer-Verlag, New York, 1992.

[4] Reader’s Digest Practical Problem Solver. Substitutes, Shortcuts, and Ingenious Solutions for Making Life Easier. The Reader’s Digest Association, Inc., Pleasantville, New York, 1991.

[5] W. M. Wonham. On pole assignment in multi-input controllable linear systems. IEEE Transactions on Automatic Control, AC-12(6):660–665, December 1967.