Jordan Normal and Rational Normal Form Algorithms

Jordan Normal

Description

Jordan Normal and Rational Normal Form Algorithms Bernard Parisse, Morgane Vaughan Institut Fourier CNRS-UMR 5582 100 rue des Maths Université de Grenoble I 38402 St Martin d'Hères Cédex Résumé In this paper, we present a determinist Jordan normal form algorithms based on the Fadeev formula : (? · I ?A) ·B(?) = P (?) · I where B(?) is (? · I ? A)'s comatrix and P (?) is A's characteristic polynomial. This rational Jordan normal form algorithm differs from usual algorithms since it is not based on the Frobenius/Smith normal form but rather on the idea already remarked in Gantmacher that the non-zero column vectors of B(?0) are eigenvec- tors of A associated to ?0 for any root ?0 of the characteristical polynomial. The complexity of the algorithm is O(n4) field operations if we know the factoriza- tion of the characteristic polynomial (or O(n5 ln(n)) operations for a matrix of integers of fixed size). This algorithm has been implemented using the Maple and Giac/Xcas computer algebra systems. 1 Introduction Let's remember that the Jordan normal form of a matrix is : A = ? ? ? ? ? ? ? ? ? ? ? ? ?1 0 0 . . .

• a? ?i


• bk can


• matrice polynomiale


• adding any field


• adding


• space associated


• field has


• a? ?i ·

Sujets

• Vaughan
• Université Grenoble-I
• Normal
• Parisse

Informations

• Publié par: pefav
• Nombre de lectures: 16
• Langue: English

Extrait

JordanNormalandRationalNormalForm Algorithms BernardParisse,MorganeVaughan InstitutFourier CNRS-UMR5582 100ruedesMaths UniversitédeGrenobleI 38402StMartind’HèresCédex Résumé Inthispaper,wepresentadeterministJordannormalformalgorithmsbased ontheFadeevformula: (λ ∙ I − A) ∙ B(λ)=P(λ) ∙ I where B(λ) is (λ ∙ I − A) ’scomatrixand P(λ) is A ’scharacteristicpolynomial. ThisrationalJordannormalformalgorithmdiffersfromusualalgorithmssinceit isnotbasedontheFrobenius/Smithnormalformbutratherontheideaalready remarkedinGantmacherthatthenon-zerocolumnvectorsof B(λ 0 ) areeigenvec- torsof A associatedto λ 0 foranyroot λ 0 ofthecharacteristicalpolynomial.The 4complexityofthealgorithmis O(n) eldoperationsifweknowthefactoriza- tionofthecharacteristicpolynomial(or O(n 5 ln(n)) operationsforamatrixof integersofxedsize).ThisalgorithmhasbeenimplementedusingtheMapleand Giac/Xcascomputeralgebrasystems. 1Introduction Let’srememberthattheJordannormalformofamatrixis: λ 1 00...00  ?λ 2 0...00 0?λ 3 ...00 00?...00 A= ........  ........   000..?λ n − 1 0  000...?λ n wherethereare1or0insteadofthe?.Itcorrespondstoafullfactorizationofthecha- racteristicalpolynomial.Iftheeldofcoefcientsisnotalgebraicallyclosed,thisJor- danformcanonlybeachievedbyaddingaeldextension.TheJordanrationalnormal 1