JOHANNES KEPLER JKU UNIVERSITA¨T LINZ Technisch-Naturwissenschaftliche Fakult¨at A computational view on normal forms of matrices of Ore polynomials DISSERTATION zur Erlangung des akademischen Grades Doktor im Doktoratsstudium der Naturwissenschaften Eingereicht von: Johannes Middeke Angefertigt am: Research Institute for Symbolic Computation (RISC) Beurteilung: Univ.-Prof. DI.Dr. Franz Winkler (Betreuung) Prof. Dr. George Labahn Mitwirkung: Dr. Gu¨nter Landsmann Linz, Juli, 2011 Normal forms of Ore polynomial matrices Kurzfassung/Abstract Kurzfassung Diese Doktorarbeit behandelt Normalformen von Matrizen über Ringen von Ore-Polynomen. Sie ist in drei Teile geteilt: Zunächst werden Ore-Polynome vorgestellt und ihre grundlegenden Eigen- schaften. Dieser Teil beinhaltet einen Exkurs über Integro-Differential-Operatoren. Zum zweiten werden im Hauptteil ein- und beidseitige Normalformen von Matrizen behandelt. Genauer legen wir unseren Fokus auf die Popov-, die Hermite- und die Jacobsonform. Der letzte Teil der Arbeit beschäftigtsichmiteinerAnwendungvonNormalformenaufeinProblemausderKontrolltheorie. ImfolgendensollaufalledieseTeilenocheinmalgenauereingegangenwerden. Ore-Polynome, die von einigen Autoren auch als Schiefpolynome bezeichnet werden, wurden zuerstvonØysteinOreuntersuchtin[Ore32a,Ore32b].SieverallgemeinerndiegewöhnlichenPoly- nome, wobei sie fast alle deren Eigenschaften erhalten mit der Ausnahme, dass die Multiplikation nicht kommutativ sein muss: Weder wird vorausgesetzt, dass die Koeffizienten miteinander kom- mutieren, noch muss die Unbestimmte mit diesen kommutieren. Ore-Polynome können verwendet werden,umRingevonDifferential-oderDifferenzoperatorenzumodellieren.Unteranderemistdie bekannteWeyl-AlgebraeinOre-Polynomring. AlseineArtausführlichesBeispielbenutzenwirOre-Polynome,umIntegro-Differential-Operatoren mit polynomiellen Koeffizienten darzustellen. Dieser Teil basiert auf unserem ISSAC 2009-Artikel [RRM09].WirerhalteneineKonstruktion,diegroßeÄhnlichkeitzurWeyl-Algebraimreindifferen- tiellenFallaufweist. Im Hauptteil der Doktorarbeit werden zunächst Normalformen von Matrizen betrachtet. Diese bieteneineMöglichkeit,SystemevonlinearenOperatorgleichungendarzustellenundaufLösbarkeit oder andere Eigenschaften hin zu untersuchen. Wir widmen uns zunächst Normalformen in Bezug aufZeilenoperationen.DieUntersuchungerstrecktsichdabeiaufZeilenreduktion,Hermite-,Popov- undverschobenePopovformen.WirstelleneineVerbindungdieserNormalformenzuGröbnerbasen über Moduln her. Als eine mögliche Anwendung dieser Verbindung wird ein modifizierter FGLM- Algorithmus vorgestellt, der es erlaubt, von einer Normalform in eine andere zu wechseln. Teile dieserArbeitwurdenaufderACA2010undin[Mid10]vorgestellt. WeiterhinbetrachtenwirdieJacobsonform,dieeineNormalforminBezugaufsimultaneZeilen- und Spaltenoperationen darstellt. In diesem Teil beschränken wir uns auf Differentialoperatoren mit kommutierenden Koeffizienten. Wir präsentieren einen modularen Algorithmus, der die Jacob- sonform mit Hilfe von zyklischen Vektoren berechnet und der zumindest bei Körpern der Charak- Frontmatter page i Normal forms of Ore polynomial matrices teristik Null immer ein Ergebnis liefert. Wir geben Bedingungen an, wann er auch bei positiver Charakteristikerfolgreichist. Der letzte Teil der Arbeit behandelt ein Thema aus der Kontrolltheorie. Wir untersuchen lin- eare,zeitvarianteSystememitTotzeitenaufdifferentielleundaufπ-Flachheit,wobeiwirIdeenaus [MCL10]aufgreifen.UnsereMethodebasiertaufdeneinseitigenNormalformenausdemHauptteil derDoktorarbeitanstellederursprünglichvorgeschlagenenJacobsonform.DieseArbeitwirdaufder AMMCS 2011 vorgestellt und ist bei der CDC 2011 eingereicht. Erste Resultate wurden in [AM10] präsentiert. Abstract ThisthesistreatsnormalformsofmatricesoverringsofOrepolynomials. Thewholethesisisdivided in three parts: First, Ore polynomials are described and basic facts about them are recalled. This part also includes integro-differential operators as an extended example. Second, in the main part we present one- and two-sided normal forms of matrices. More precisely, we deal with the Popov normal form, Hermite normal form and the Jacobson normal form. In the last part, we explore an applicationofmatrixnormalformstoaproblemincontroltheory. Below,wedescribeeachofthepartsinmoredetail. Ore polynomials, sometimes called skew polynomials, arise from the work of Øystein Ore in [Ore33]. Theyareageneralisationoftheusualpolynomialswithalmostalloftheirpropertieswith the main exception being that the multiplication in not necessarily commutative: Neither need the coefficientscommutewitheachother, nordoestheindeterminatehavetocommutewiththem. Ore polynomialscanbeusedtomodeldifferentialordifferenceoperators. Forexample,thefamousWeyl algebracanbeconsideredtobeanOrepolynomialring. As an example, we model integro-differential operators with polynomial coefficients using Ore polynomials. This part is based on our ISSAC 2009 paper [RRM09]. We arrive at a construction whichissimilartotheWeylalgebrainthepurelydifferentialcase. Inthemainpart,weconsidernormalformsofmatrices. Thesemakeitpossibletoexpresssystems oflinearequationsinvolvingoperatorsandtodeterminethepropertiesofthesesystemssuchas,for example, solvability. Wefirstconsidernormalformswithrespecttorow-operations. Thecoefficient domain here is a skew field. We treat row-reduction, the Hermite normal form, the Popov normal formandshiftedPopovnormalforms. WedrawaconnectionbetweenthesenormalformstoGröbner basesovermodules. Asanapplicationofthisconnection,wepresentamodifiedFGLMalgorithmfor converting matrices from one normal form into another. Parts of this were presented at ACA 2010 andin[Mid10]. WealsoconsidertheJacobsonnormalformwhichisanormalformwithrespecttosimultaneous row-andcolumn-operations. Here,werestrictourselvestodifferentialoperatorsoveracommutative coefficientdomain. WepresentamodularalgorithmforcomputingaJacobsonnormalformwhichis basedoncyclicvectorsandwhichisguaranteedtosucceedincharacteristiczero, butundercertain conditionsalsoyieldsaresultinpositivecharacteristic. Thelastpartdealswithatopicfromcontroltheory. Weexaminelineartime-varyingdifferential systems with delays for differential flatness and π-flatness where we use an idea from [MCL10]. Forthis,weapplytheone-sidednormalformsfromthemainpartinsteadoftheoriginallyproposed Frontmatter page ii Normal forms of Ore polynomial matrices Jacobsonnormalform. ThiswillbepresentedatAMMCS2011andisalsosubmittedtoCDC2011— initialresultswerepresentedat[AM10]. Frontmatter page iii Normal forms of Ore polynomial matrices Frontmatter page iv Normal forms of Ore polynomial matrices Curriculum vit(cid:230) Personal data FullName JohannesMiddeke DateofBirth 30thofNovember,1979 PlaceofBirth Oldenburg(Oldenburg),Germany Homeaddress Aubrunnerweg9,A-4040Linz,Austria Emailaddress [email protected] Citizenship German Career 2007–present Ph.D. studies in Natural Sciences at the Research Institute for Symbolic Computation(RISC)inHagenberg/Linz,Austria. 2000–2007 DiplomastudiesinMathematicsatCarlvonOssietzkyUniversityinOlden- burg (Oldenburg), Germany. Degree of Diplom-Mathematiker with distinc- tion. Career related activities • ResearchvisitatUniversityofInnsbruck(Austria,2009) • ContributedtalkatISSAC2009(Seoul,Korea) • ResearchvisitatUniversityofWaterloo(Canada,2009) • ContributedtalkatACA2010(Vlorë,Albania) • ContributedtalkatDEAM2(Linz,Austria) • OrganisingcommitteeofDEAM2(Linz,Austria) • ResearchvisitatUniversityofWaterloo(Canada,2011) • OrganisingcommitteeofCAI2011(Linz,Austria) • ContributedtalkatAMMCS2011(Waterloo,Canada) Frontmatter page v Normal forms of Ore polynomial matrices Published papers 1. J.Middeke, Apolynomial-timealgorithmfortheJacobsonformformatricesofdifferentialop- erators,Tech. Report08-13,RISCReportSeries,UniversityofLinz,Austria,July2008. 2. G. Regensburger, M. Rosenkranz, and J. Middeke, A skew polynomial approach to integro- differential operators, Proceedings of ISSAC 2009 (J. R. Johnson, H. Park, and E. Kaltofen, eds.),ACM,2009,pp. 287–294(English). 3. J.Middeke, ConvertingbetweenthePopovandtheHermiteformofmatricesofdifferentialop- erators using an FGLM-like algorithm, Tech. report, RISC Report Series, University of Linz, Austria,June2010. 4. J.Middeke,E.Shemyakova,F.Winkler. ProceedingsofDEAM(WorkshopforDifferentialEqua- tions by Algebraic Methods). Technical report no. 09-08 in RISC Report Series, University of Linz,Austria. 2009. Proceedings. 5. J. Middeke. Conversion between Hermite and Popov normal forms using an FGLM-like ap- proach, Albanian Journal of Mathematics, Vol. 4, No. 4 (2010), Special Issue, Applications of ComputerAlgebra2010. Frontmatter page vi Normal forms of Ore polynomial matrices Eidesstattliche Erkl(cid:228)rung/A(cid:30)davit IcherkläreanEidesstatt,dassichdievorliegendeDissertationselbstständigundohnefremdeHilfe verfasst, andere als die angegebenen Quellen und Hilfsmittel nicht benutzt bzw. die wörtlich oder sinngemäßentnommenenStellenalssolchekenntlichgemachthabe. Hereby I declare in lieu of oath that I wrote the present thesis by my own and without any assistancefromthirdpartiesandwithoutsourcesotherthanthoseindicatedinthethesisitself. JohannesMiddeke Frontmatter page vii Normal forms of Ore polynomial matrices Frontmatter page viii