Study of Polynomial and Matrix Fraction

1. INTRODUCTION

The first step when studying and designing a control strategy for a physical system is the development of mathematical equations that describe the system. These equations are obtained by applying various physical laws such as Kirchoff’s voltage and current laws (electrical systems) or Newton’s law (mechanical systems). The equations that describe the physical system may have different forms. They may be linear equations, nonlinear equations, integral equations, difference equations differential equations and so on. Depending on the problem being treated, one type of equation may prove more suitable than others. The linear equations used to describe linear systems are generally limited either to the input- output description, or external description in the frequency domain, where the equa- tions describe the relationship between the system input and system output in the Laplace trans- form domain (continuous-time systems) or in the z-transform domain (discrete-time systems), or the state- variable equation description, or internal description, a set of first-order linear differ- ential equations (continuous-time systems) or difference equations (discrete-time systems). Prior to 1960, the design of control systems had been mostly carried out by using transfer functions. However, the design had been limited to the single variable, or single-input-single- output (SISO) case. Its extension to the multivariable, or multi-input-multi-output (MIMO) case had not been successful. The state-variable approach was developed in the sixties, and a number of new results were established in the SISO and MIMO cases. At that time, these results were not available in the transfer-function, or polynomial approach, so the interest in this approach was renewed in the seventies. Now most of the results are available both in the state-space and polynomial settings. The essential difference between the state-space approach and the polynomial approach resides in the practical way control problems are solved. Roughly speaking, the state-space approach heavily relies on the theory of real and complex matrices, whereas the polynomial approach is based on the theory of polynomials and polynomial matrices. For historical reasons, the computer aided control system design packages have been mostly developed in the late eighties and nineties for solving control problems formulated in the state-space approach. Polynomial techniques generally simpler in concepts, were most notably favored by lecturers teaching the basics of control systems, and the numerical aspects have been left aside. Recent results tend however to counterbalance the trend, and several reliable and efficient numerical tools are now available to solve problems involving polynomials and polynomial matrices. In particular, the Polynomial Toolbox for Matlab is recommended for numerical computations with polynomials and polynomial matrices. Whereas the notion of the state variable of a linear systems may sometimes sounds somehow artificial, polynomials and polynomial matrices arise naturally when modeling dynamical systems. Polynomial matrices can be found in a variety of applications in science and engineering. Second degree poly- nominal matrices arise in the control of large flexible space structures, earthquake engineering, the control of mechanical multi-body systems, and stabilization of damped gyroscopic systems, robotics, and vibration control in structural dynamics. For illustration, natural modes and frequencies of a vibrating structure such as the Millennium footbridge over the river Thames in London are captured by the zeros of a quadratic polynomial matrix. Third degree polynomial matrices are sometimes used in aero-acoustics. In fluid mechanics the study of the spatial stability of the Orr-Somerfield equation yields a quadratic matrix polynomial. In this article, we will describe a series of concepts related to polynomial matrices. We will introduce them gradually, as they naturally arise when studying standard transformations to and from the state- space domain.

2.1. Rational transfer function Assuming that the knowledge of the internal structure of the system is not available, the transfer function description of a system gives a mathematical relation between the input and output signals of the system. Assuming zero initial conditions, the relationship between the input u and the output y of a system can be written as y s G s u s where s is the Laplace transform in continuous-time (for discrete-time systems, we use the z- transform and the variable z), and G s is the scalar transfer function of the system. G s is a rational function of the indeterminate s that can be written as a ratio of two polynomials n s G s d s where n s is a numerator polynomial and d s is a denominator polynomial in the indeterminate s. In the above description of a transfer function, it is assumed that polynomials n s and d s are relatively prime, or co-prime polynomials, i.e. they have no common factor, except possibly constants. The degree of denominator polynomial d s is the order of the linear system. When the denominator polynomial is monic, i.e. with leading coefficient equal to one, the transfer function is normalized or nominal. It is always possible to normalize a transfer function by dividing both numerator and denominator polynomials by the leading coefficient of the denominator polynomial.

Figure 1: Mechanical system

As an example, consider the mechanical system shown in Figure 1. For simplicity, we consider that the friction force between the floor and the mass consists of viscous friction only (we neglect the static friction and Coulomb friction). It is given by f k1dy dt , where k1 is the viscous friction coefficient. We also assume that the displacement of the spring is small, so that the spring force is equal to k 2y, where k2 is the spring constant. Applying Newton’s law, the input-output description of the system from the external force u (input) to the displacement y (output) is given by

d2y m dt 2 dy u k1 dt k2y

Taking the Laplace transform and assuming zero initial conditions, we obtain Transfer function G s has numerator polynomial n s 1 of degree zero and denominator poly- nomial d s ms2 k1s k2 of degree two. The corresponding linear system has therefore order two. Dividing both n s and d s by the leading coefficient of d s we obtain the normalized transfer function 2.2. From transfer function to state-space Similarly to network synthesis where the objective is to build a network that has a prescribed impedance or transfer function, it is very useful in control system design to determine a dynamical equation that has a described rational transfer matrix G s . Such an equation is called a realization of G s . The most common ones for linear systems are state-space realizations of the form

where x t is the state vector, u t is the input, y t is the output and A B C are matrices of appropriate dimensions. Such realizations correspond to strictly proper transfer functions. In the case of proper transfer function, one must add a direct transmission term Du t to the output variable y t . For simplicity we shall assume that D 0 in the sequel. For every transfer function G s , there is an unlimited number of state-space realizations. So it is relevant to introduce some commonly used, or canonical realizations. We shall present two of them in the sequel: the controllable form and the observable form. However, note there are other canonical forms such as the controllability, observability, parallel, cascade or Jordan form, that we will not describe here for conciseness. For notational simplicity, we will consider a system of third order, with normalized strictly proper transfer function

The observable canonical realization corresponding to G s has state-space matrices Note that this realization is dual to the controllable canonical realization in the sense that matrix A is transposed, and vectors B and C are interchanged. Obviously, this form is always observable. If n s and d s are coprime, it is also controllable. 2.3. From state-space to transfer function Assuming zero initial conditions and taking the Laplace transform of the state-space equations we obtain that where I denotes the identity matrix of the same dimension as matrix A. Recalling the formula of the inverse of a matrix, the above equation can be written as Polynomial d¯ s is generally referred to as the characteristic polynomial of matrix A. It may happen that polynomials n¯ s and d¯ s have some common factors captured by a common polynomial term f s , so that we can write where n s and d s are coprime. The ratio of n s over d s as defined above is a representation of

It turns out that G s is irreducible if and only if pair A B is controllable and pair C A is observable. Checking the relative primeness of two polynomials n s and d s can be viewed as a special case of finding the greatest common divisor (gcd) of two polynomials. This can be done either with the Euclidean division algorithm, or with the help of Sylvester matrices. 2.4. Minimality A state-space realization A B C of a transfer function G s is minimal if it has the smallest number of state variables, i.e. matrix A has the smallest dimension. It can be proven that A B C is minimal if and only if the two polynomials defined above n¯ s CAdj sI A B and d¯ s det sI A are coprime, or equivalently, if and only if A B is controllable and C A is observable.

3. MULTIVARIABLE SYSTEMS

When trying to extend the results on scalar systems presented in the previous section, several difficulties must be overcome. Multivariable systems are more involved because, unlike the scalar case, there does not seem to be a single unique canonical choice of realizations. Moreover, the connection with irreducible transfer functions is not obvious. The closest analogy with the scalar results can be achieved by using the so-called matrix fraction descriptions (MFDs) of rational matrices as the ratio of two relatively-prime polynomial matrices. To handle these objects, several properties of polynomial matrices must be introduced.

With analogy to the scalar case, a given rational matrix G s can be written as a fraction of two polynomial matrices. As the product of matrices is not commutative, there exist two different ways to proceed.

We can define a right matrix fraction description, or right MFD for short, G s NR s DR 1 s

where non-singular polynomial matrix DR s enters G s from the right. Here non-singularity of a polynomial matrix means that its determinant is not identically zero, or equivalently that the matrix is non-singular for almost all values of the indeterminate. For example, the matrix 1 s s 1 s2 1 is non-singular, whereas the matrix 1 s s 1 s2 s is singular.

G s DL 1 s NL s

As an example of a left MFD, we consider the RCL network depicted on Figure 2, where the system outputs are the voltage and current through the inductor, and the input is the voltage Applying Kirchoff’s laws, the Laplace transform and assuming zero initial conditions, we obtain the relation

In the scalar case, given a transfer function n s G s

we could easily derive a variety of state-space realizations A B C of G s , with nice controllability and observability properties and order always equal to the degree of denominator polynomial d s . It is not hard to write down state-space realizations in the multivariable case but some of the nice properties will be lost if we are not careful. As an example, we consider the two-input two-output system with strictly proper transfer function matrix First we try to make realizations of each entry of this rational matrix and connect them appropriately. For example, with the controllable canonical realizations, we obtain the state-space realization Here zero entries are left empty for clarity. This realization has order twelve, which is the sum of the degrees of the denominators of the different entries. Now if we denote G s as and define the degree of the denominator matrix as deg DR s deg det DR s which is here the degree of d s times the number of inputs. The degree of the denominator matrix actually corresponds to the order of the realization. The above example raises the question of what the minimal order of a realization can be. Moreover, we may also wonder whether a realization is controllable and observable. It turns out that, as in the scalar case, a realization of a multivariable system is minimal if and only if it is controllable and observable. There can be many right and left matrix fraction description (MFDs) of G s . Indeed, given a right

such that which means that the degree of a MFD can be reduced by removing right divisors of the numerator and denominator matrices. Obviously, we will get a minimum-degree right MFD by extracting a greatest common right divisor (gcrd) of NR s and DR s . In other words, we have extracted a gcrd from NR s and DR s if and only if deg det DR s deg det D¯ R s

s have the property that det U s is a non-zero constant independent of s. Such matrices are called unimodular matrices. For example, we can check easily that

U s 1 s 1 0 1

Checking relatively primeness of two polynomial matrices can be performed in various ways. The most useful ones are the rank criterion, the Sylvester matrix criterion or the reduction to some tri- angular matrix form. Basically, these are matrix extensions of the procedures available for scalar polynomials. 3.3. Properness In the scalar case, properness or strict properness of a transfer function is directly related to the degrees of the numerator and denominator polynomials. In the matrix case things are more complicated.

then every column of NR s has degree strictly less than (resp. less than or equal to) that of the corresponding column of DR s . However, the converse is not always true. For example, if

but the transfer function Inequality may hold because of possible cancellations. However if DR s is such that the equality holds, then we say that DR s is column-reduced. Let us define the highest column degree coefficient matrix, or leading coefficient matrix for short, as the matrix whose ith column consists of coefficients of ski in the ith column of DR s . It turns out that a non-singular polynomial matrix is column- reduced if and only if its leading coefficient matrix is nonsingular. The leading coefficient matrix of the polynomial matrix DR s given above is

1 1 0 0

which is a singular matrix, so DR s is not column-reduced. With the help of this notion we can prove that, provided DR s is column-reduced, the transfer

A dual statement holds with left MFDs and row-reduced column matrices. Note that, if a polynomial matrix DR s is not column-reduced, then it is always possible to find a unimodular matrix U s such that

is column-reduced. One way to proceed is to use the so-called elementary column operations, that is to say multiplication of a column by a non-zero number, interchange of two columns, addition of the product of one column and a polynomial to another column. One can check that all of these operations can be performed by post-multiplication by a unimodular matrix. When combined, these operations result in a product of unimodular matrices, which is also a unimodular matrix. For the above non-column-reduced matrix DR s we find for example which is column-reduced. 3.4. Non-canonical realizations With the help of the concepts introduced above, we will now extend the scalar controllable and ob- servable canonical forms to the multivariable case for a given MFD. The order of these realizations is always equal to the degree of the determinant of the denominator polynomial matrix of the MFD.

Given a strictly proper right MFD G s NR s DR 1 s where denominator matrix DR s is column-reduced with column degrees ki i 1 n. Let Dh denote the leading coefficient matrix in DR s , and Dl denote the remaining coefficient matrix such that DR s DhH s Dl L s NR s Nl L s Where Then the system matrices of a controllable form realization of G s are given by The order of the realization is deg det DR s i ki. The nice feature of this realization is its con- trollability, no matter whether NR s and DR s are right coprime or not. However, observability is guaranteed only if NR s and DR s are right coprime. To illustrate this with an example, let

3.4.2. Observable form The dual form can be obtained starting from the left MFD Then we define and the state-space matrices are given by A A0 Dl Dh 1C0 B Nl C Dh 1C0 This realization is always observable, but controllability is lost when NL s and DL s are not left coprime. As an example, we consider the left MFD 3.5. Canonical realizations We have seen in the previous section that we can associate with a scalar transfer function a unique state-space realization in controllable canonical form. The (minimal) order of the realization was the degree of the denominator polynomial. for any unimodular matrix U . Proceeding this way, we do not affect the degree of the determinant DR s , hence we do not affect the order of the realization. However, we modify the coefficients of NR s and DR s , hence we modify the coefficients entering the state-space matrices of the realization. In order to define a unique, canonical multivariable realization, we must define a canonical transfor- mation of a polynomial matrix. The most commonly used transformations are the Hermite form and the Popov form. 3.5.1. Hermite form Given a non-singular polynomial matrix DR s , we can always convert it to a unique so-called Hermite form DH s DR s U s Where U s is unimodular, and DH s has the following properties it is lower triangular Each diagonal element is monic each diagonal element has higher degree than any other element in the same row. The standard approach to convert a polynomial matrix into Hermite form consists in applying elemen- tary operations on the columns of DR s . The main drawback in applying elementary operations is that generally numerical stability of the algorithm is not guaranteed. However, note that numerically stable versions of the triangularization procedure have recently been proposed. They are not based on elementary operations. One can check that the Hermite form DH s is row reduced, so that given a transfer matrix right MFD G s NR s DR 1 s we can associate a unique right MFD corresponding to the Hermite form DH s of DR s . Associated with this MFD, we can build a unique, or canonical state-space realization such as the controllable form introduced above. An example of reduction to Hermite form is as follows

Given a non-singular polynomial matrix DR s , we can always convert it to a unique so-called Popov form or polynomial echelon form DP s DR s U s where U s is unimodular, and DP s has the following properties it is column reduced with its column degrees arranged in ascending order k1 k2 for column j there is a pivot index p j such that entry p j j in DP s has degree k j , entry p j j in DP s is monic, entries i j with i p j have degree less than k j ,

have degree less than k j if i j. Here too, the Popov form can be obtained via elementary column operations, but more reliable trans- formation algorithms based on numerical linear algebra are recommended. 3.6. From right MFD to left MFD Now we mention the conversion from a not necessarily coprime right MFD to a coprime left MFD, and vice versa. The equality which means that matrices NL s and DL s of the left MFD belong to the left null space of the compound polynomial matrix built from right MFD matrices NR s and DR s . It turns out that among all candidate matrices NL s DL s living in this null space, there exists a so-called minimal polynomial basis that has the smallest possible row degrees. A numerically stable algorithm can be devised to build the minimal polynomial basis. Obviously, conversion from left MFD to right MFD can be performed the same way. The conversion from right MFD to left MFD of the transfer function studied in this section reads

3.7. From state-space to MFD Given a state-space representation x˙ t Ax t Bu t y t Cx t we can obtain a left MFD of the matrix transfer function G s C sI A 1B by converting first Conversely, we can obtain a right MFD of G s if we first convert the right MFD sI A1B to a coprime left MFD EL s DL 1 s and then G s NL s DL 1 s with NL s CEL s . The obtained right MFD will be coprime only if C A is observable.

4. CONCLUSION

We have described the use of matrix fraction descriptions (MFDs) to model scalar and multivariable linear systems. The transformation from MFDs to state-space representation motivated the introduc- tion of several concepts and several properties specific to polynomial matrices. There exist several extensions to the results described in this chapter. MFDs can be transformed to the so-called descriptor state-space representation E x˙ t Ax t Bu t y t Cx t with transfer function G s C sE A 1B Matrix E may be singular, so the above representation is a generalization of the state-space form that captures impulsive dynamics and the structure at infinity. One can also mention here polynomial matrix descriptions (PMDs) G s R s P 1 s Q s W s with the associated system polynomial matrix P s Q s R s W s as a generalization of MFDs. There exists a whole theory of state-space realizations of PMDs based on properties of the system polynomial matrix. For practical computation with polynomials and polynomial matrices, modern software packages are available. In particular, the Polynomial Toolbox for Matlab is recommended for numerical computations with polynomials and polynomial matrices.

BIBLIOGRAPHY

Chen C.T. (1984). Linear system theory and design. New York: Holt, Rinehart and Winston [Text- book that presents most of the aspects of the theory of multivariable linear systems. Matrix fraction descriptions are fully covered. Appendix G is devoted to the theory of polynomial matrices, with a focus on numerical computation.] Kailath T. (1980). Linear systems. Englewood Cliffs, New Jersey: Prentice Hall. [Textbook that cov- ers a very large spectrum of topics on linear system theory of multivariable linear systems, including matrix fraction descriptions. Section 6.3 collects in a comprehensive ways several results on polyno- mial matrices.] Kucˇera V. (1979). Discrete linear control: the polynomial equation approach. London: Wiley [This is a pioneering textbook that paved the way for the use of polynomials, polynomial matrices and polynomial equations to solve linear control problems.] Kucˇera V. (1991). Analysis and design of discrete linear control systems. London: Prentice Hall [Textbook that investigates connections between the state-space approach and the polynomial ap- proach to several standard linear control problems.] Kwakernaak H. and Sˇ ebek M. (1998)). The Polynomial Toolbox for Matlab, Prague, CZ: PolyX Ltd., Web site at