Jordan Normal and Rational Normal Form Algorithms

-

Documents
15 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Nombre de lectures 16
Langue English
Signaler un problème
JordanNormalandRationalNormalFormAlgorithmsBernardParisse,MorganeVaughanInstitutFourierCNRS-UMR5582100ruedesMathsUniversitédeGrenobleI38402StMartind’HèresCédexRésuméInthispaper,wepresentadeterministJordannormalformalgorithmsbasedontheFadeevformula:(λIA)B(λ)=P(λ)IwhereB(λ)is(λIA)’scomatrixandP(λ)isA’scharacteristicpolynomial.ThisrationalJordannormalformalgorithmdiffersfromusualalgorithmssinceitisnotbasedontheFrobenius/SmithnormalformbutratherontheideaalreadyremarkedinGantmacherthatthenon-zerocolumnvectorsofB(λ0)areeigenvec-torsofAassociatedtoλ0foranyrootλ0ofthecharacteristicalpolynomial.The4complexityofthealgorithmisO(n)eldoperationsifweknowthefactoriza-tionofthecharacteristicpolynomial(orO(n5ln(n))operationsforamatrixofintegersofxedsize).ThisalgorithmhasbeenimplementedusingtheMapleandGiac/Xcascomputeralgebrasystems.1IntroductionLet’srememberthattheJordannormalformofamatrixis:λ100...00?λ20...000?λ3...0000?...00A=................000..?λn10000...?λnwherethereare1or0insteadofthe?.Itcorrespondstoafullfactorizationofthecha-racteristicalpolynomial.Iftheeldofcoefcientsisnotalgebraicallyclosed,thisJor-danformcanonlybeachievedbyaddingaeldextension.TheJordanrationalnormal1