SQU Journal for Science, 2016, 21(1), 64-68 © 2016 Sultan Qaboos University 64 Reduction of Linear Functional Systems using Fuhrmann's Equivalence Mohamed S. Boudellioua Department of Mathematics and Statistics, College of Science, Sultan Qaboos University, P.O. Box: 36, PC 123, Al-Khod, Muscat, Sultanate of Oman. *Email: boudell@squ.edu.om Abstract: Functional systems arise in the treatment of systems of partial differential equations, delay-differential equations, multidimensional equations, etc. The problem of reducing a linear functional system to a system containing fewer equations and unknowns was first studied by Serre. Finding an equivalent presentation of a linear functional system containing fewer equations and fewer unknowns can generally simplify both the study of the structural properties of the linear functional system and of different numerical analysis issues, and it can sometimes help in solving the linear functional system. In this paper, Fuhrmann's equivalence is used to present a constructive result on the reduction of under-determined linear functional systems to a single equation involving a single unknown. This equivalence transformation has been studied by a number of authors and has been shown to play an important role in the theory of linear functional systems. Keywords: Linear functional systems; Reduction; Fuhrmann's equivalence; Quillen-Suslin Theorem; Lin-Bose conjecture. (Fuhrmann) اختصار األنظمة الذالية الخطية باستخذام تكافؤ فورمان محمذ الصالح بودليوة ة األبعاد. حسخخذو األَظًت انذانٍت فً دساست أَظًت انًعادالث انخفاضهٍت انجضئٍت ٔاألَظًت انخفاضهٍت راث اإلعالاث انضيٍُت ٔكزنك األَظًت يخعذد :الملخص نشٌاضً انفشَسً ٔلذ حًج دساست اخخصاس األَظًت انذانٍت انخطٍت إنى أَظًت ححخٕي عهى عذد ألم يٍ انًعادالث ٔانًجاٍْم ألٔل يشة يٍ طشف انعانى ا . ٔانٓذف األساسً يٍ عًهٍت االخخصاس ْزِ ْٕ حسٍٓم دساست ْزِ األَظًت يٍ حٍث حهٓا أٔ حطبٍك طشق عذدٌت عهٍٓا َسخخذو فً ْزا انبحث (Serre)ساس نخمذٌى َخٍجت بُاءة الخخصاس بعض األَظًت انذانٍت انخطٍت َالصت انخعٍٍٍ حٍث أٌ انُظاو انًخخصش ٌحخٕي عهى يعادة ٔاحذة (Fuhrmann)حكافؤ فٕسياٌ ًت انذانٍت انخطٍت.راث دانت يجٕٓنت ٔاحذة. ْزا انخكافؤ حى دساسخّ يٍ طشف عذد يٍ انباحثٍٍ ٔحبٍٍ يٍ رنك أٌ ْزا انخكافؤ ٌهعب دٔسا يًٓا فً َظشٌت األَظ بٕص.-َظشٌت نٍٍٔ سٕسهٍ-حكافؤ فٕسياٌ، َظشٌت كٌٕهٍ ،خخصاسانخطٍت انذانٍت، اال تاألَظً: الكلمات المفتاحية 1. Introduction olynomial matrices play an important role in the theory of linear systems described by ordinary differential equations (see for example Rosembrock [1] and Kailath [2]). In this case, the polynomial matrices involve a single indeterminate with coefficients in the field of real or complex numbers. The study of linear systems of ordinary differential equations is thus reduced to the study of matrices over the ring [ ]s or [ ]s . These rings have the Euclidean division property which makes it possible to establish canonical forms such as the Smith normal form. In fact, the polynomial theory of such systems can be regarded as more or less complete. In the case of linear functional systems, arising for example from partial differential equations or delay-differential equations, the resulting system matrices involve polynomials in more than one indeterminate. Since multivariate polynomial rings do not have the Euclidean division property, it is no longer possible to extend most of the results obtained for the single indeterminate case. Throughout this paper unless specified otherwise, [ ] denotes the polynomial ring in the indeterminates with coefficients in an arbitrary but fixed field K. First we present a few definitions that will be needed later in the paper. P REDUCTION OF LINEAR FUNCTIONAL SYSTEMS 65 Definition 1.1 Given a matrix q p T D   , the i th order invariant polynomial i  of T is defined by : 1 ; 1 = 0; min( , ) i ii i r r i p q            (1) where r is the normal rank of T , 0 = 1 and i  is the greatest common divisor of all the i i minors of .T As in the single variable case, the zero structure of a multivariate polynomial matrix is a crucial indicator of its properties. However, unlike the single variable case, the zero structure of a multivariate polynomial matrix is not completely captured by the invariant polynomials but by the invariant zeros as defined by the following. Definition 1.2 [3, 4, 5] Let 1 = [ , , ] n D x x , q p R D   , ( > )p q be a full row rank matrix and i the ideal generated by the i i minors of R and ( ) i V the algebraic variety defined by: ( ) = { | ( ) = 0, }. n i V P P    The i th order invariant zeros of R are the elements of the variety ( ) i V . Definition 1.3 Let 1 = [ , , ] n D K x x . The general linear group ( )pGL D is defined by:  ( ) = | : = =p p p pp pGL D M D N D MN NM I      An element ( ) p M GL D is called a unimodular matrix. It follows that M is unimodular if and only if the determinant of M is invertible in D , i.e., is a non-zero element of .K Definition 1.4 Two polynomial matrices 1 T and 1 S of appropriate dimensions, are said to be zero-left-coprime ( ZLC ) if the matrix  1 1T S admits a right-inverse in D . Similarly, 2T and 2S , of appropriate dimensions, are said to be zero-right-coprime ( ZRC ) if the matrix  2 2 T T T T S has left-inverse in D . One of standard tasks carried out in systems theory is to transform a given system representation into a simpler form. An equivalence transformation used in the context of multidimensional systems is Fuhrmann's equivalence [6] and is defined by the following. Definition 1.5 (Fuhrmann's Equivalence) Let ( , )T m n denote the class of ( ) ( )r m r n   matrices with elements in D where ,m n are fixed positive integers and > min( , )r m n . 1 T and 2 T are said to be Fuhrmann-equivalent (F-E) if there exist matrices 1 S , 2 S of appropriate dimensions with elements in D such that 2 1 2 1 =S T T S (2) where 1 1 ,T S are ZLC and 2 2 ,T S are ZRC. In the case when 1 T and 2 T have the same size and 1 S and 2 S are square, the transformation in (2) reduces to the classical unimodular equivalence. F-E has been studied by a number of authors. For instance, Pugh et al. [7, 8] have shown that it exhibits fundamental algebraic properties amongst its invariants. In particular, they have shown that it preserves the invariant polynomials as well as the the invariant ideals. Lemma 1.1 [7] Suppose that two matrices 1 T and 2 ( , )T m n are related by F-E and let [ ] [ ] [ ] 1 1 1 1 2 , , , T T T h    where [ ] [ ] 1 1= min( , ), T T h r m r n  denote the invariant polynomials of 1 T and [ ] [ ] [ ] 2 2 2 1 2 , , , , T T T k    where [ ] [ ] 2 2= min( , ), T T k r m r n  denote the invariant polynomials of 2 T , then [ ] [ ] 1 2= for = 0,1, , max( 1, 1) T T h i i k i c i k h       (3) where [ ] [ ] 1 2= 1, = 1 for any < 1, \ {0}. T T j j i j c   Lemma 1.2 [8] Suppose that two matrices 1 T and 2 T ( , )m n are related by F-E and let [ ] 1 T j for [ ] [ ] 1 1= 1, , = min( , ) T T j h r m r n  denote the ideal generated by the j j minors of 1 T and [ ] 2 T i , for [ ] [ ] 2 2= 1, , = min( , ) T T i k r m r n  denote the ideal generated by the i i minors of 2 T . Then [ ] [ ] 1 2= , = 0, , T T h i k i i h   (4) MOHAMED S. BOUDELLIOUA 66 where = min( 1, 1)h h k  and for any >i h , [ ] [ ] 1 2= 1 or = 1 in case < or < . T T h i k i i h i k       The problem of reducing a linear functional system to a system containing fewer equations and unknowns was first studied by Serre [9]. Such a process is based on the application of the well known Quillen-Suslin Theorem. Theorem 1.1 [10, 11] Let K be a principal ideal domain and  1= , , nD K x x and let q p R D   be a matrix which admits a right-inverse p q R D   , i.e., = qRR I . Then there exists a unimodular matrix ( )pN GL D such that  = 0 .qRN I (5) 2. Reduction using Fuhrmann's Equivalence The reduction of a multivariate polynomial matrix in the context of multidimensional systems theory was first studied by Frost and Boudellioua [12]. They obtained necessary and sufficient conditions under which a square multivariate polynomial matrix is unimodular equivalent to a simpler form. This corresponds to the reduction of a determined linear functional system into a single equation in one unknown function. Boudellioua and Quadrat [13] generalized this result to underdetermined systems using a module theoretic approach. Their result gives necessary and sufficient conditions for the reduction of a linear system to a system containing a single equation with several unknown functions. Boudellioua [14] generalized the earlier result to under-determined systems thereby giving necessary and sufficient conditions for the unimodular equivalence of an under-determined linear system to one containing a single equation involving only one unknown function. The results mentioned so far are based mainly on unimodular equivalence. This transformation has the disadvantage of establishing a connection between matrices and hence systems which have the same size. Boudellioua [15] used Fuhrmann's equivalence to reduce a class of determined linear functional systems to a system containing a single equation in one unknown. In this paper, we extend this latter result to the under-determined case. Before presenting the main result of this paper, we first state the following result which is a statement of the positive answer of the Lin-Bose conjecture [16]. This theorem which will be used later is given by Fabianska and Quadrat [17]. Theorem 2.1 [Section 5 of [17] ] Let =D 1 [ , , ] n K x x be a commutative polynomial ring over a field K and q p R D   a full row rank matrix. Then the following two assertions are equivalent: 1. The ideal ( ) q I R generated by the q q minors of R is principal, i.e. can be generated by the greatest common divisor  of these minors. 2. There exist , ' q p '' q q R D R D     , and ( )pN GL D such that:  = , det( ) = , = 0 .'' ' '' ' qR R R R R N I (6) Theorem 2.2 Let 1 = [ , , ] n D K z z and q p T D   , >p q with full row rank, then T is Fuhrmann- equivalent to the row vector 1 ( 1)p q T D     :  = 0 .T  (7) where D is the gcd of the q q minors of T , if and only if there exist a vector qU D which admits a left inverse in D such that the matrix  T U has a right inverse over D and the ideal generated by the q q minors of T is principal. Proof. Let q p T D   and suppose that there exist a vector q U D satisfying the given condition. Then by the Quillen-Suslin theorem there will exist a square ( 1) ( 1)p p   matrix 1( )pK GL D such that    1 1 = 0 q K M N T U I X T       (8) where 1 ( 1) 1 p q T D     . It follows from (8) that: 1 1 =TN UT (9) REDUCTION OF LINEAR FUNCTIONAL SYSTEMS 67 where ,T U are, by assumption, ZLC and 1 1 ,T N are ZRC (since 1( )pK GL D ). By virtue of Lemma 1.1 and Lemma 1.2, Fuhrmann's equivalence preserves the determinantal ideals and the invariant polynomials of the matrices. Hence the ideal generated by the elements of 1 T is also principal and generated by the single polynomial  . Hence by virtue of the Lin-Bose Theorem 2.1, there exists a matrix 2 1 ( ) p q N GL D    such that  1 2 = 0 .T N T   (10) From which 1 2 =TN N UT (11) where again ,T U are by assumption ZLC and 1 2,T N N are ZRC, since 11 2 2 1 = . NN N N TT           (12) Now suppose that q p T D   is F-E with 1 ( 1)p q T D     , then there exist matrices 1 p N D   and ( 1)p q p Q D     such that =NT TQ , where ,N T are ZLC and ,T Q are ZRC. By the Quillen-Suslin theorem, there exist ZRC matrices q U D and ( 1) 1p q Y D     such that 1 ( ) p T U GL D Q Y         (13) where the matrices T and U must be ZLC. It is worth mentioning at this stage that finding a vector ,U D when it exists, such that the condition in Theorem 2.2 is satisfied is not a straight forward task. On simple examples over a commutative polynomial ring 1 = [ , , ] n D K x x with coefficients in a computable field K (e.g., =K ), one may take a generic vector q U D with a fixed total degree in the i x 's and compute the D -module  1 1 ( 1)/ ( )q p TD D T U   by means of a Gröbner basis computation and check whether or not this D -module vanishes on certain branches of the corresponding tree of integrability conditions (see Pommaret and Quadrat [18]) or on certain obstructions to genericity ( see Levandoskyy and Zerz [19]). 3. Conclusion We have presented a constructive result for the simplification of a class of linear functional systems. More specifically, we have given necessary and sufficient conditions under which a rectangular multivariate polynomial matrix can be reduced by Fuhrmann's equivalence to a form that corresponds to the reduction of a linear functional system to a single equation with only one unknown function. The result can be easily implemented on a computer algebra system such as Maple using the OreModules package (see Chyzak et al. [20]). 4. Acknowledgment The author wishes to express his thanks to Sultan Qaboos University (Oman) for supporting this research (Grant No. IG/SCI/DOMS/15/01). References 1. Rosenbrock, H.H. State space and multivariable theory, 1970, Nelson-Wiley, London, New York. 2. Kailath, T. Linear Systems, 1980, Prentice-Hall. 3. Youla, D.C. and Gnavi, G. Notes on n -dimensional system theory. IEEE Trans. Circuits and Systems, 1979, 26(2), 105–111. 4. Youla, D.C. and Pickel, P.F. The Quillen-Suslin theorem and the structure of n-dimensional elementary polynomial matrices. IEEE Trans. Circuits and Systems, 1984, 31, 513–517. 5. Zerz, E. Topics in Multidimensional Linear Systems Theory, 2000, Springer, London. 6. Fuhrmann, P.A. On strict system equivalence and similarity. Int. J. Control, 1977, 25(1), 5-10. 7. Pugh, A.C., McInerney, S.J., Hou, M. and Hayton, G.E. 1996. A transformation for 2-D systems and its invariants. In Proceedings of the 35th IEEE conference on decision and control, pages 2157–2158, Kobe (Japan). 8. Pugh, A.C., McInerney, S.J. and El-Nabrawy, E.M.O. Zero structures of n -D systems. Int. J. Control, 2005,78(4), 277–285. 9. Serre, J.P. Sur les modules projectifs. Séminaire Dubreil-Pisot, 1960/61, 2, 23-34, In Jean-Pierre Serre, Oeuvres, MOHAMED S. BOUDELLIOUA 68 Collected Papers, 1960-1971, 2, 23-34. 10. Quillen, D. Projective modules over polynomial rings. Invent. Math., 1976, 36, 167-171. 11. Suslin, A.A. Projective modules over polynomial rings are free. Soviet Math Dokl., 1976, 17(4), 1160–1164. 12. Frost, M.G. and Boudellioua, M.S. Some further results concerning matrices with elements in a polynomial ring. Int. J. Control, 1986, 43(5), 1543-1555. 13. Boudellioua, M.S. and Quadrat, A. Serre's reduction of linear functional systems. Mathematics in Computer Science, 2010, 4(2), 289–312. 14. Boudellioua, M.S., Further results on the equivalence to Smith form of multivariate polynomial matrices. Control and Cybernetics, 2013, 42(2), 543–551. 15. Boudellioua, M.S., On the simplification of systems of linear multidimensional equations. In The Sage Days 24 Workshop on Symbolic Computation in Differential Algebra and Special Functions, 2010, Hagenberg (Austria). 16. Lin, Z. and Bose, N.K., A generalization of Serre's conjecture and related issues. Linear Algebra and its Applications, 2001, 338, 125–138. 17. Fabianska, A. and Quadrat, A. Applications of the Quillen-Suslin theorem in multidimensional systems theory. In H. Park and G. Regensburger, editors, Gröbner Bases in Control Theory and Signal Processing, Radon Series on Computation and Applied Mathematics 3, 2007, pages 23–106. de Gruyter publisher. 18. Pommaret, J.F. and Quadrat, A. Formal elimination for multidimensional systems and applications to control theory. Mathematics of Control, Signal and Systems, 2000, 13, 193–215. 19. Levandovskyy, V. and Zerz, E. Obstructions to genericity in the study of parametric problems in control theory. In H. Park and G. Regensburger, editors, Gröbner Bases in Control Theory and Signal Processing, Radon Series on Computation and Applied Mathematics 3, 2007, pages 127–149. de Gruyter publisher. 20. Chyzak, F., Quadrat, A. and Robertz, D. OreModules: A symbolic package for the study of multidimensional linear systems. In J. Chiasson and J.J. Loiseau, editors, Applications of Time-Delay Systems, LNCIS 352, 2007, pages 233–264. Springer, http://wwwb.math.rwth-aachen.de/OreModules/. Received 7 April 2015 Accepted 13 September 2015