V x l I ’ WWW ON THE CONTRQLLABELETY OF DtSCRETE STATE SYSTEMS Thesis Ear fixer 9992‘“ a? M. S. MCHIGAN STA‘E'E UNWERS!‘?Y jaffrey 2.. Gwdnufi 26:23 THESIS This is to certify that the thesis entitled ON THE CONTROLLABILITY OF DISCRETE STATE SYSTEMS presented by Jeffrey L. Goodnuff has been accepted towards fulfillment of the requirements for M22;— degree in Elect. Engrg. Major professor Date August 9, 1963 0-169 LIBRARY Michigan State University ON THE CONTROLLABILITY OF DISCRETE STATE SYSTEMS BY 3 1" Lil» Jeffrey L: ‘Goodnuff AN ABSTRACT OF A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Electrical Engineering 1963 ABSTRACT ON THE CONTROLLABILITY OF DISCRETE STATE SYSTEMS by Jeffrey L. Goodnuff The idea of controllability was presented by R. E. Kalman in 1960. His definition was one which gave a specific mathematical meaning to an otherwise intuitive concept. This thesis develops, from that definition, necessary and sufficient conditions for a plant to be controllable. From these conditions it is shown that there is a certain minimum time in which a plant may be controlled. This time is a function of the dimension of the state vector. In addition it is shown that if a plant is- not controllable in the minimum time it is never controllable. In the last section observability is defined and the relationship between observability and controllability is shown. ON THE CONTROLLABILITY OF DISCRETE STATE SYSTEMS By Jeffrey L. Goodnuff A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Electrical Engineering 1963 ACKNOWLEDGEMENTS The author wishes to express his thanks to his committee members for their many helpful suggestibns throughout the preparation of this thesis. He wishes to thank his major professor, Dr. H. E. Koenig, whose encouragement and constructive suggestions were inval- uable, and Dr. J. 5. Frame whose superb mathematical ins‘ight saved many hours of work. The author also wishes to thank the National Science Foundation under whose sponsorship this research was done. ii TABLE OF C ONTENTS SECTION Page ' I. INTRODUCTION. . ............................... 1 II. CONTROLLABILITY WITH A SINGLE INPUT. . ..... . . . . ........... . ................... 3 III. C ON TROLLAB ILITY WITH MULTIPLE INPUTS ............... . .......... . ............. 25 IV. OBSERVABILITY. . . . ........................... 32 V. CONCLUSION .................................. 36 APPENDIX ..................................... 38 REFERENCES. . . . . ............................. 41 iii I INTRODUCTION In 1960 the concept of state controllability was introduced by Kalman. 1 He went on to state a necessary condition for state controll- ability in terms of the Jordan Canonical form of the transition matrix. He also required the inverse of the transition matrix to exist. In the same year the idea of output controllability was presented by Bertram and Sarachick. 2 They did not develop the concept beyond a mere definition. I This thesis develops a necessary condition for state controll- ability in terms of the minimal polynomial of the transition matrix. The transition matrix may be singular. A necessary and sufficient condition for both state and output controllability is also developed in terms of the Jordan Canonical form. From these conditions it is shown that there exists a certain minimal time in which a plant may be controlled, and that if the plant cannot be controlled in that minimal time it cannot be controlled in any finite time. Finally the concept of observability is considered, and necessary and sufficient conditions for it are established. These conditions are 1R. E. Kalman, On The General Theory of Control Systems, First International Congress On Automatic Control, Moscow, 1960- 2J. E. Bertram and P. E. Sarachik On Optimal Computer Control, First International Congress On Automatic Control, Moscow, TW— 1 related to the controllability conditions, and this relationship is shown. A brief discussion of the problem of non-zero compute time is presented in the conclusion . II CONTROLLABILITY WITH A SINGLE INPUT Consider a discrete state plant which is linear and has one input. The state model of the plant is then _x_[kT] = §_)_(_[(k-1)T] + 51d (k-1)T]; k = 1, z, T > o. (2.1) where X and A are n dimensional column vectors, u is a scalar, and <1 is an n by n square constant matrix. The outputs are given in the form gkr] = M_)_<_[k'r] (2. 2) where I is an m (m in) dimensional vector, and M is an m by n con- stant matrix. At this point it should be noted that (2. 2) is not the most general form for the outputs of a linear plant. In this discussion only the case where there are no direct transmission terms will be consi- dered. However, this is not as severe a restriction as it may at first seem, as output controllability is not affected by direct transmission terms. The two fundamental definitions pertaining to controllability are as follows: Definition 2. 1: A plant is said to be state controllable if and only if the state vector, _)_(_[ kTJ , can be brought to any desired state in a finite time. A plant is completely state controllable if and only if every state is controllable. Definition 2. 2: A plant is said to be output controllable if and only if the output vector, l[kT] , can be brought to any desired output in a finite time. A plant is completely output controllable if and only if every out- put vector is controllable. The input sequence u(nT), n = 0, 1, . . . , N-l, required to move the plant from an initial state at t = 0 to a given state at time t: NT is determined by the solution of the system of equations _DSINT]= s Nx[o] +[§NA 1 s__N'2£ . . . @£ {1] u[0] (2.3.1) u[T] u[ 2T] u((N-1)T] obtained as the recursive solution of (2. 1). In symbolic form (2. 3. 1) is represented as 3This same definition was used by Kalman. This same definition was used by Bertram and Sarachick. 9g NT] = §N_x_[o] + H (2.3.2) NEN ‘ In equations (2. 3) N is not to be confused with n, the order of the state vector. In equation (2. 3. 2) EN is the Nth order vector repre- senting the scalar inputs at the N time intervals, and HN is the n by N composite matrix composed of the column vectors §i_A_, i = 0, l, . . . , N-l. Substituting equation (2. 3. 2) into equation (2. 2) yields yNT] = MeNggo] + MH (2.4) NEN' The following three cases are of interest. Case I. N = n. That is, the number of iterations is equal to the num- ber of variables in the state vector. Since HN is square it is possible to solve (2. 3. Z) for EN if HN is nonsingular. _ -1 -1 N g-N-HN _)_{_[NT] -HN e 2‘10] (2.5) The square matrix H is nonsingular if and only if the columns of HN N are linearly independent. Therefore the following trivial lemma can be stated. LEMMA 2. l: A discrete state plant, with state model given in equation (Z. l), is completely controllable in N = n steps if and only if the vectors sn‘lé, en'zé, . . ., ii, .4.» are linearly independents A similar result arrived at in a much less direct manner and requiring the inverse of Q, is obtained by Kalman. It is at this point that this paper departs from Kalman's treatment of the subject. Case II. N <.n. That is, it is required to transfer a given state vector to some desired point in less than n steps. It can be seen that this is not possible in general. That is, it can be done only if )_(IO] is of a spe- cial form. This can be shown simply by writing equation (2. 3. 2) in par- titioned form. If we let [I = _13[ NT] - sNzgto]. (2. 6) then (2. 3. 2) becomes ._ .1 _ .. ‘11 H1 W = : )J. (2. 7.1) _. -N ‘12 H2 where H1 is a square, N by N matrix. If lHll ,! 0 then from the top equation in (2. 7. l) we have _ -1 EN-Hl V11, (2.7.2) and from the bottom equation W2 = HZE-N' (2. 7. 3) Therefore, v_v =HH'1W. (2.8) It can be seen from (2. 8) that any vector, _}5[ O] , can be transferred to lg NT] in N -< n steps if and only if W, as given in (2. 6), can be written in the form of equation (2. 8), and the following lemma follows. LEMMA 2. 2: A discrete state plant is never completely controllable with N < n iterations. Case III. N." > 11. That is, it is desired to transfer the state vector to a desired point in N time intervals, where N is greater than the number of \ variables in the state vector. Let equation (2. 3. 2.) be rewritten as (2. 9) Is I) II! :11 where W is defined in (Z. 6). Here H is a square, n by n matrix and H1 2 is n by N-n. If |H2| a! 0 we may write it =H w-H‘Hu. (2.10) It can immediately be seen that the N-n scalars in El can be chosen inde- pendently of the rest of the vector E. This corresponds to independent selection of the first N-ninputs. Since these inputs are arbitrary let £1 '3 0, so that (2.10) becomes ,. =H. 1:, (2.11) and E: is given by (2. 12) [1: n o The above establishes the following lemma. LEMMA 2. 3: A discrete state plant completely controllable in N = n time intervals is controllable in NT> n intervals. From the above three lemmas, and the fact that H2 in equation (2. 9) is exactly the same as H in equation (2. 5) the following theorem N may be stated. THEOREM 2. l: A general discrete state plant with state equations of the form in (2. l) is completely state controllable in N Z n intervals if and only if H is of maximum rank (i. e. , rank of H = n). N N By a careful examination of equation (2. 4) and through a develop- ment exactly analogous to that used to establish theorem 2. l we may draw the following conclusion. THEOREM 2. 2: A general discrete state plant with output equations of the form in (2. 2) is completely output controllable in N _>_ m intervals if is of maximum rank (i. e. , rank of MH = m). N and only if MHN With the above two theorems along with theorem A. l in the appendix, the following theorem relating output and state controllability may be proved. THEOREM 2. 3: If a discrete state plant is completely state controllable then the rank of M, in equation (2. 2), being equal to m is a necessary and sufficient condition for complete output controllability. PROOF: The hypothesis assures us that HN is of maximum rank. There- fore theorem A. l is applicable and we see that the rank of MH is equal N to the rank of M. Since the maximum rank of MH is m, the product N MHN is of maximum rank if and only if the rank of M is m. Therefore a necessary and sufficient condition for complete output controllability is that the rank of M equals m. Note, however, that complete output controllability does not always imply complete state controllability. Although theorems 2. l and 2. 2 are certainly necessary and sufficient conditions for complete controllability, they leave much to be desired. To say the least it is a tedious task to raise i to successive powers, postmultiply by the vector A, and then check the independence of the resulting vectors. Further, if this were done and the resulting vectors were found to be dependent it is not apparent what 'changes need to be made to i and A in order to achieve an independent set of vectors. It is this thought that motivates the following discussion. It will be useful to make the following change of variable. Let 10 _Z_[kT] = ngr], (2.13) where the square, non-singular, n by n matrix, P, is the matrix that transforms é, in equation (2. 1), into its upper triangular Jordan-Canon- ical form. Denote this form by J. That is, J=P§P'l . (2.14) Equation (2. 1) then becomes _Z_[k‘I‘J = Psp'l_z_[ (k-1)T] + PAu[(k-1)TJ (2.15.1) or, with e = PA, _Z_[kT] =J_Z_[(k-1)TJ +éu[(k-1)TJ. (2.15.2) It immediately follows then that equations (2. 3. l), (2. 3. 2), and (2. 4) become - _ T '7 £[NT] =JN£[O]+[JN12_} JN 29 . . . Jé é] u[o] u[ T] __u[(N—1)T_]_ (2.16) 11 or in the symbolic form, z[ NTJ = JNgjo] + sNgn. (2.17) and the output is given by, M NT] = KJNgo] + KS (2.18) NEN’ where, of course, W: P1, and K = MP-l. Since P is nonsingular the transformations between W and I and between éand _}_C are one to one, and an inverse exists. From this point on the properties of equations (2. 16), (Z. 17), and (2. 18) will be considered. The matrix SN is composed of N column vectors, each of which is of the form JIA. The Jordan form, J, is quasidiagonal, i. e. , of the form J = “ ' (2.19) L 1' where r is the number of distinct eigenvalues and block Li is of order si with si equal to the multiplicity of Ni in the characteristic polynomial, DR), of Q. Each Li has the following form. 12 L = 1 . (Z. 20) That is, the main diagonal has entries hi, and the upper diagonal con- tains ones and zeros. The remaining entries in Li are zero. The exact number of ones and zeros on the upper diagonal depends on the elementary divisors of the matrix (Lu - Q), and cannot be determined from knowledge of only the characteristic polynomial, D(A.), and the minimal polynomial, M0). However, knowledge of M0) andDM) does allow partial determination of the off diagonal entries. The upper diagonal in the ith block has all zeros if and only if the (K - ti) term in M(A) is linear. Also, the upper diagonal in the ith block has all ones if and only if the (k - ti) term in -M(k) is of the same degree as 6 the corresponding term in D(k). Examining the vector Jlé we see that 6V. N. Faddeeva, Computational Methods of Linear Algebra (New York: Dover Publications, Inc., T959). P752. where, rki (I) kl-l i “.2 j I J (2) j ° «.3 (w L; = L; with the convention that (3) If MM) 7! D(IL) then (2. 22) has the following form. (. i s.- .) i-s.+l (2.21) .J. (2.22) = O for j >—i, if and only if MM) '3 DUN). - 14 -T i1 (1)).1‘1 . . o o . o J 1 J . x1 o o . . . o (2.23) L}: J . x1 (1)X1 J 1 J L .. In general the Lj is itself quasidiagonal with the order of the xj factor in the minimal polynomial equal to the order of the largest sub-block in Lj' 7 Of course L; remains quasidiagonal. ' an: The product L; A. is 1 * i i. i-l LA = x. u +[ )x. u + o o o ' 2024 3—, J5Jk-1 1 )_ BJk ( ) i x- o J 5Jk r Ibid. 15 Since (2. 24) represents sj rows of the i + 1 column, it is apparent that in general the jk row of S is a multiple of the jsj row, and therefore N the rank is down by at least one. In fact it can be seen that the k-l row is a linear combination of the last two rows. The k- 2 row will be a linear combination of the last three rows, and so on. It can be verified that the number of dependent rows is exactly equal to the difference in degree between M0.) and D()~). Theorems 2. 4 and 2. 5 are then established. THEOREM 2. 4: A necessary condition for complete state controllability of a discrete state plant is that the minimal polynomial, M0), and characteristic polynomial, DR), of the matrix Q, in equation (2. 1), be identical. EEOEM 2. 5: Let the difference in degree between the minimal polynomial, MM), and the characteristic polynomial, DO), for the lj term be denoted by Bj. Then a necessary condition for complete output controllability of a discrete state plant is that 2‘. B. < n-m. j J Consider, now, the case where Q has distinct eigenvalues. It is immediately apparent that the necessary condition in theorem 2. 4 is satisfied, since each diagonal block, Li’ in the Jordan form is diagonal and of order one, i. e. , J is diagonal with diagonal elements equal to the distinct Xi. In this case the product Jlé is l6 and the composite matrix S N, N-l N-Z x1 61 x1 51 N-l N-Z x2 52 x2 62 SDI: tN‘la xN'za n n n n F. n-1 n-2 *1 51 N1 52 n-1 n-2 N > n, is given by, (2.25) ‘51 ‘52 (2. 26) 6 n N. ‘51 52 (2.27) 6 n 17 S n may be written as the product of two matrices, S = D V . (2.28) where D‘5 is the diagonal matrix with dii = 6i and Vn is the nth order Vandermonde matrix. It is a well known fact that the-Vandermonde determinant does not vanish for distinct Li. In fact the Vandermonde determinant is easy to compute and is given by n = “IT. (xi .. xj), (2.29) 1 >3 whichis obviously not zero for Ni 7‘ Kj, i 7! j. 8 Since the determinant of a product is equal to the product of determinants, ISn can be written as ' ' n n = = = k - k 0 sn Inévn lDéan F511 .||.(i j) . 1-J 1 > J (2. 30) Equation (2. 30) obviously implies 8n = 0 if and only if 6i = 0 for at least one i, i = l, 2, . . . , n. Now, noting the form of S in equation N (2. 26) itis seen that if any 6i = 0 there is an entire row of zeros in SN. The following lemma may therefore be stated. 8Edward T. Browne, Introduction to the TheorLof Determinants and Matrices (Chapel Hill, North Carolina: The University of North Carolina Press, 1958), P. 34. 18 LEMMA 2. 4: If a discrete state plant, with distinct eigenvalues and with state equations of the form shown in (2. l), is not completely state controllable in N = n intervals then it is not completely state controllable in N >- n intervals. Consider now the situation with output controllability and distinct eigenvalues. Again it is seen that the necessary condition for complete output controllability is satisfied (theorem 2. 5). Assume that the plant is not controllable in n steps. This implies the rank of KSn is less than m. This may occur in three ways. (1) The rank of K may be less than m, (2) the rank of Sn may be less than m, or (3) the rank of Sn is at least m, but the rank of the product, KSn, is less than m. Case (1): When the rank of K is less than m, the rank of KSN is always less than m, because the rank of the product of two matrices is never greater than the rank of either matrix. Case (2): The rank of Sn is less than m if and only if less than m rows are independent. It has been shown that Sn = D Vn’ and 6 an 3‘ 0. Therefore from theorem A. 1 it can be seen that the rank of Sn is equal to the rank of D Therefore the rank of D is 6' 6 a): less than m. However, from (2. 26) it is seen that SN = D6VN’ * where VN is the nth order Vandermonde matrix, Vn’ augmented with N-n columns. Since is always maxi- N mum (i. e. , equal to n) for all Nan. Again theorem A. l is appli- an" o the rank of v cable and it is seen that the rank of SN equals the rank of Sn which is les 5 than m. Case (3): Consider the product KSN = awhere l9 KS k11 12 kln 11 h12 th k21 22 k2n 21 h22 th kml m2 kmn n1 hn2 hnN__ an 12 alN a21 22 aZN = a (2.31) aml m2 amN __ _J Let the m, N dimensional row vectors of a, be denoted by 0.1, 0.2, . . . , am. Each of these m vectors is a linear combination of the n row vectors, Oi , of SN. It is known that there exists at least rn rows, (11, that are dependent. Since the combining vectors (i. e. , the rows of K) are all independent this implies that at least m of the row vectors, “ai, are partly composed of the dependent vectors in the set {93, Also note that the relationship of K to S is unaltered by N 20 the magnitude of N. It therefore follows that in order to increase the rank of a , the rank of S must be increased, i. e. , some dependent N rows must be made independent by adding another column. However in case (2) it was shown that the rank of SN equals the rank of D6 for all N. Therefore the rank of SN cannot be increased by increasing N. The above discussion together with lemma 2. 4 and theorems 2. l and 2. 2 imply the following. THEOREM 2. 6: A discrete state plant with state [output] equations as in (2. l) [ (2. 2)] and with distinct eigenvalues is completely state [output] controllable in N> n steps, if and only if it is completely controllable in N = n steps. And from the conclusion in case (2) of the above development, a necessary and sufficient condition for state controllability is apparent THEOREM 2. 7: A discrete state plant with state equations of the form of (2. l) and distinct eigenvalues, is completely state controllable in N = n steps if and only if 6i # 0 for all 6i as defined in (2. 30). Now consider the case where the transition matrix, Q, has multiple eigenvalues, and MM) =5 D(L). Each column vector of the matrix QN is of the form shown in (2. 21) and (2. 22). It can be seen that the matrix, S , may be factored into the product of two matrices, N ~~ S=D N 5 vn (2.32) 21 where Bl Ba N — D6 — with [—6. 6. is. 13,-1 1 1 6. is. 1 B. = 1 and A N V = n . il is.-l 1 is 9 f4 (2.33) (2. 34) (2.35) 22 where _/\., = ' . (2. 36) 1 (ml) 16"?” k. 1 0 l 1 1 h?'1 13"2 a 1 l. 1 _i Obviously the determinant of D5 is dependent only on each 61 s i and on nothing else. That is, ’13 = "IT (5. .1? (2.37) The determinant of the modified Vandermonde matrix can be shown to be 5N r 8.8. Ivn = (hi - a.) 1 .3 (2.38) i>j 3 Therefore ~ N r 3. r 3.5. _ _ 1 _ 1 J Is.| - |v.||v. - Tr <6...) IT. a. ’3)- 1=l 1 1 >3 23 N N Note that for distinct A, D6 = D6 and Vn = Vn. Then theorem 2. 8 immediately follows. THEOREM 2. 8: A discrete state plant with state equations of the form in (2. 1) is completely state controllable in N = 11 steps if and only if (a) M(k) = D(I\) and (b) all 6.1 s 35 O as defined in equation (2. 24). 1 The following theorem is also easy to prove. THEOREM 2. 9: A discrete state plant with state equations of the form in (2. l) is completely state [output] controllable in Nf> n steps if and only if it is completely state [output] controllable in N = n steps. PROOF: The "if" part is shown by lemma 2. 3. For the "only if" part it needs to be shown that a plant not controllable in N = n steps is not controllable in»N.‘> n steps. First consider state controllability. If the plant is not state controllable in N = n intervals then IsnI = o. This implies some 6i 3. = 0. Which, from (2. 24), implies that S 1 hence it cannot be of maximum rank. N has a row of zeros;’ Next consider output controllability. This development is parallel to the discussion in the case of distinct eigenvalues. Case (1) and Case (3) do not use the fact that the eigenvalues are distinct. Therefore it is only necessary to establish case (2). That is, it is necessary to show that the rank of S equals the rank of Sn for N N,‘> n, hence the rank of Sn: < n implies the rank of SN < n. It was shown above that (UN 5 =DV. (2.40) N It can be seen from (2. 38) that Vn 7! 0. Therefore theorem A. l N implies that the rank of S equals the rank of D . Note that S can n 6 N be written, ~N* S =DV N a N (2.41) a): where VN is the nth order modified Vandermonde matrix Vn augmented N :1: with N-n columns. Since 7‘ O the rank of VN is maximum and N theorem A. 1 again applies. Therefore the rank of SN = D6’ - from which N V n follows that the rank of SN equals the rank of Sn and the theorem is proved. III CONTROLLABILITY WITH MULTIPLE INPUTS Consider the discrete state plant with state equations of the following form. ng] = Q_)£[(k-1)TJ + Au[(k-1)T] (3.'l) Here, as before, X is an n dimensional vector and Q is an n by 11 square constant matrix. HoweverA is no longer a column vector, it is an n by q matrix. The column vector u is q dimensional. The outputs are given in the form l[kT] = Mgng] , (3. 2) where _Y_ is an m dimensional vector and M is an m by n constant matrix. Again, as in the single input case, (3. 1) can be solved recur- sively yielding 3] NT] = sijo] + [sN'lA QN'ZA . . . QA A] u[o] T U[ T] E[(N-1)Tl_ 3.3 25 ( ) 26 or in symbolic form 3:] NT] = sNgo] + H (3.4) NE-N' Each of the products QIA results in an n by q matrix, thus making HN an n by Nq matrix. Although I: is a vector, the elements, U, are N each q dimensional column vectors. Thus, )1- -N is an Nq dimensional vector. Let us again consider three cases. Case I. Nq : n. In this case H is a square matrix and if lHNl f 0, N _ -1 -1 N gN-HN _JgNT] -HN a _x_[o]. (3.5) Of course HNl )4 0 if and only if its columns are linearly independent. Case 11. Nq < n. In this case W is defined by N V_V=_)_(_[NT] -§ go]. (3.6) With this definition equation (3. 4) may be written as w ' * —1 H1 = s .7 E W H»: EN, (3 l -2 2 a): where H1 is a square Nq by Nq matrix. Solving for W2 from the bottom equation of (3. 7) and substituing it for I: in the top equation of (3. 7) #0. N H* 1 yields, for 27 at at -1 v12 = HzHl v11. .(3. 8) It can be seen that if Nq is no greater than the number of variables in the state vector, only certain special initial vectors, 2(_[ 0] , may be controlled. Case III. Nq > n. With the definition given in (3. 6), (3. 4) can be written as v_v-.-[nl e2] E1 . (3.9) .9 ZJ Here 02 18 .n by n, a1 15 n by Nq-n, and E2 is n by 1, while El 18 Nq-n by 1. If IezI go, se‘lw—a'le g (310) 92 — 2 1 1' ° It can be seen that the Nq-n constants in El are arbitrary. Therefore choose £1 = 0. Then (3 sez'lig, ' (3.11) whe re it = o . (3.12) 28 Note that for any given case, if q and n are such that n/q is an integer, E2 is identical with H in equation (3. 5). N Here, as in the case of a single input, the following theorem ‘ may be stated. THEOREM 3. 1: A discrete state, multiple input plant with state equations of the form in (3. l) is completely state controllable in N Z n/q time intervals if and only if HN, in equation (3. 4) is of maxi- mum rank (1. e. , of rank 11). Output controllability is concerned with the system _Y;[NT] = M §N_)_(_[o] + MH (3.13) NE-N ’ for which we have the following theorem. THEOREM 3. 2: A discrete state, multiple input plant with output equations as given in equation (3. 2) is completely output controllable in N 3.. m/q time intervals if and only if the product MHN. in equa- tion (3. 13), is of maximum rank (1. e. , of rank m). The similarity between the single input case and multiple input case terminates with the above theorems. ‘Recall now that the N groups of q columns which compose HN .are products of the form Qi A. As in the single input case, an equivalent system of equations may be consi- dered by using the Jordan Canonical form of Q. The Jordan Canonical form of (3. 3) is 29 N [o]+[JN'1A JN'ZA . . . JA A] Go] §_[NT] = J U[ T] URN-11'1"] (3.14) withé = P_}_(_, and A = PA. Here, of course, the terms JIA each repre- sent a band of q column vectors instead of a single column vector as in the single input case. It can be shown that theorem 2. 4 is not true under these conditions. For example, let T o o o— 1 o 1.1 o o J = (3.15) o 0 a2 0 _o o 0 kg and let bl o— o 1 A = . (3.16) 1 o .0 13 30 Obviously 2 2) (3.17) D(A) = (x - 1.1)2 (k - 1. and Mo.) = (A - 5.1) (:1 - a (3.18) 2" If k = O, k = 1, and N = 2 the matrix HN can be written 0] o H o H = [JA A] = (3'19) from which it is seen that IHN| = 1 g o. (3.20) Therefore Hfi'l exists and the plant is controllable. However it is seen from equation (3.17) and (3. 18) that MM) # D(A). It is also easy to show that theorem 2. 9 does not remain true in the multiple input case. For example, choose J with four distinct eigenvalues and let —1 1— 1 1 A = . (3.21) 1 1 1 1 Then, for N = n/q = 2, 2 2 H = . (3. 22) N k3 £3 1 1 k4 X4 1 1 Obviously lHNl = 0. However if N = 4 "—3 3 2 2 — kl k1 x1 kl k1 XI 1 1 3 3 2 2 L2 L2 k2 k2 k2 K2 1 1 HN = . (3. 23) with) .p. th .p. .p. .4; It is easily seen that the rank of H is maximum. Therefore by N theorem 3. l the plant is controllable in N > n/q time intervals. From the above discussion it can be seen that the results of the previous section do not trivially extend to the case of multiple inputs. Moreover, they are not true in general. IV OBLSERVABILITY In the previous two sections it was shown that there are certain necessary and sufficient conditions on the transition matrix, Q, and the coefficient matrix, 56:, for state and output controllability. However, examination of equations (2. 4) and (2. 5) reveals that for both state and output controllability the entire state vector evaluated at t = O, i. e. , 2(_[0], is required. In general it may be very difficult, inconvenient, or impossible to measure 2{_[0]. It is this thought that motivates the following discussion. DEFINITION 4. l : A discrete state plant is said to be observable if the exact value of the state vector at time zero can be determined, in a finite time, from the measurements of the output signal. If every 9 state is observable the plant is completely observable. In order that some definite conclusions may be drawn let the plant have a single input and single output. That is let M, in equation (2. 2), be a row matrix of dimension n. Equation (2. 4) with N = k becomes, Y[kT] = Mek3<_[01+ MHktk (4.1) 9 This same definition was used by Kalman. 32 33 where, of course, Y[0] is a scalar. Writing equation (4.1) for k: 0,1, . . . , n-l, one obtains ,. ._ _ .. Y[O] M Y[T] Mo = . £[0] + 1\(1Hn)_1__n , (4.42) Y[(n-1)T] Mon'l .. 4 .. 3 or in symbolic form, 3).: Yn = Gn_}_{_[0] + MHn 'in' (4. 3) If IG I 4 o n .. * _ 3(_[01= GnlY - G lMHn& . (4.4) The analog of lemma 2. 1 follows immediately. LEMMA 4. 1 : A discrete state plant with one input and one output is completely observable in N = n intervals if and only if the row vectors M_ n time intervals if and only if Gn is of maximum rank. A careful examination of Gn reveals that it is of the same form as the transpose of Hn. In fact (in is a row permutation of H: with At replaced by M and Qt replaced by 4?. Since the operation of transposition and row permutation does not affect the singularity of a matrix, all the theorems proved in section II will carry over, and theorems 2. 4 and 2. 5 become: THEOREM 4. 2 : A necessary condition for complete observability of a discrete state plant with one output is that the minimal polynomial, M(X ), and the characteristic polynomial, D().), of the matrix Q be identical . THEOREM 4. 3: A discrete state, single output, plant with distinct eigenvalues is completely observable in N > n intervals if and only if it is completely observable in “N = n steps. With 5i defined in equation (2. 30) and with _A_ : Mt, we may state the analog oftheorem 2. 7. (THEOREM 4. 4 : A discrete state plant with a single output and distinct eigenvalues .is completely observable in N = n time intervals if and only if ai¢0foralli:1, 2, . . . ,n. 35 In the case of repeated eigenvalues , theorem 2. 8 and theorem 2. 9 be come: THEOREM 4. 5 : A discrete state plant with a single output is completely observable in N = n time intervals if and only if (a) MO.) 3 DOK) and (b) all 51 3 qt 0 as defined in equation (2. 24) with i £=Mt. THEOREM 4. 6: A discrete state plant with a single output is completely observable in N >n steps if and only if it is completely observable in N = n steps. V C ONC LUSION In the previous four sections the concepts of output and state controllability as defined by Kalman have been given. It was found that for a linear, stationary, discrete state plant with one input and one output the minimal polynomial, M().), must be identically equalto the characteristic polynomial, D0. ), if we are to achieve state controllability. 10 In addition the input vector, _A_, must be such that when premultiplied by the Jordan transforming matrix, P, the result is free from zeros in certain positions. In addition to the above, the state-vector at t = 0 must be known. This last requirement motivates the development in Section IV where the concept of observability is given. It is shown that in order to compute _)_{_[O] (that is, the plant is observable) Gn must be non- singular. However the matrix Gn has properties very similar to Hn’ the inverse of which is required for controllability. It is therefore easy to check Gn from the information used to investigate the rank of Hn' To make a complete check of controllability the Jordan trans— forming matrix, P, must be found. In general this is a very laborious task to say the least. Even more serious is the fact that if the compu- tation is to be done on a digital computer the round-off errors, for large matrices may accumulate to such an extent that the result is useless. I 10This necessary condition was given in a different form by Kalman . 36 37 If an analysis is performed on the system, other factors,such as stability, will also be of interest. Much of the information required for a controllability investigation will also be required for these other purposes and therefore the increase in work to investigate controllability will not be as great as first may appear. As a further application to control systems it should be noted that in order to achieve controllability it is necessary to compute the solution to equation (2. 5) with £[O] given. Even if this is to be done on a high speed digital computer, it will require some non-zero compute time. Let this time be denoted by (3T, where T is".the sampling period. Since the solution to (2. 5) gives, among other things, the input at the next time interval it is impossible to control the plant, with zero error, in N = n time intervals. Also note from equation (2. 12) that the first N - n intervals are completely arbitrary, say zero. Therefore we are assured that we may control the plant in N = n + 5 intervals. If the state vector is not directly measureable, but the plant is completely controllable, we are assured that it can be controlled in at most ' N = 2n + (5 intervals. The question of controllability with multiple inputs and the prob- lem of observability with multiple outppts is essentially the same, but it is one that is not easily answered. Certainly it would appear that the answer lies in the relationship between Q and A in the controllability case and between ¢ and M in the observability case. Counter examples to the theorems in the single input-output case are easy to give for the multiple input-output case. As yet it has not been possible to draw any specific conclusions in the multiple input, multiple output plant. APPENDIX THEOREM A. l : Given the matrix product MH, where M is an m by n matrix, n: m; and H is an n by N matrix with N: n, if H is of maximum rank (i. e. , n) then the rank of MH equals the rank of M. PROOF: Let MH = 9. Then 511m12m13 ' ' ' m1; 1111’12' ° "’11: m21m22 m23 ' m2n h21 h22 ° ° ' th h31 h32 ° h3N = h__nl n2 ° ' hnli_ :11 “’12 “’13 “1N— “’21 “’22 “’23 ' “’2N = :2 . (A. 1) :ml mewm3' ° 'wmli It can be seen that (31 =m11W1+m12 \If2+. . . +mln\Ifn [32 =m21\IIl +m2‘2 \IIZ+. . . +1112an (A.2.) 6m = mmlq’l + mmZ \Ifz + . . . ~+ mman 39 Where [31: (cl)1 wiZ wiN) for 1 2 l, 2, . . . , m, and ‘Ifi=(hil hi2 . . . hiN) for1=l,2, . . .,n. It is clear that the vectors BI, (32, . . . , [3m are linear combinations of the vectors \Ifl, \Irz, . . maximum rank, and \Ili is the ith row of H, the vectors {iii} are linearly . , \Irn. Note that since H is of independent. Assume that the rank of S2 is less than the rank of M. Then any j rows of Q are dependent, where j is the rank of M. Then j Zaifiizo ; ai¢0forsomei=l,2,...,j, (A.3) i=1 or al(m11\1[r:l + leWZ + . . . + mlnwn) + a2(m21\lil + mZZWZ + . . . +m2nfl'fn) (A.4) + aj(mj1‘IIl + mjziliz + . . . + mjnwn) = 0 Rearranging and combining terms one obtains (alrn11 + a2m21+ . . . + ajmj1)\I’1 + (alm12 + azm22 + . . . + ajijHVZ (A. 5) + (alm1n + azm2n + . . . + ajmjnhlfn = 0 However, it has been shown that {Wig is a set of linearly inde- pendent vectors. Therefore equation (A. 5) implies that 4O alm11+ a2m21+. . . + ajmjl : 0 almlz+a2m22+ +ajm32 -O (A. 6) alm1n + azm2n + + aJmJn = 0 Let pi = (mi1 mi2 . . . min)° That 18, Hi 18 the 1th row of M. With this definition the equations in (A. 6) may be written a1)J.1+ azpz + . . . + ajllj = 0 . (A.7) Equation (A. 7) must hold for any set of j rows of M. Since the rank of M is j , there must exist j linearly independent rows of M. Therefore (A. 7) can only be true if ai=0 forall i=l,2,...,j. (A.7A) This is a contradiction to the original hypothesis that ai =# O _ for some i. It is therefore concluded that the rank of 9 is greater than or equal to the rank of M. However, since the rank of M equals j, j 3 mg n, and thelrank cf H is n, it is concluded that the rank of S2 is at most j. Hence the rank of (2 equals j. REFERENCES Bertram, J. E. and Sarachik, P. E. On Optimal Computer Control, Fir st International Congress On Automatic Control, Moscow, 1960. Browne, E. T. Introduction to the Theory of Determinants and Matrices, Chapel Hill, North Carolina: The University of North Carolina Press, 1958. Faddeeva, V. N. Computational Methods of Linear Algebra, New York: Dover Publications, Inc. , 1959. Hildebrand, F. B. Advanced Calculus For Applications, New York): Prentice Hall, 1963. Hohn, F. E. Elementary Matrix Algebra, New York: The Macmillian Co., 1958. Kalman, R. E. On The General Theory of ControlSJstems, First International Congress On Automatic Control, Moscow, 1960. 41 ’11’ H .1! 1111.24 1111' 13