Jordan Normal and Rational Normal Form Algorithms

pages

English

Documents

Écrit par
Jordan Normal

Publié par
pefav

Lire un extrait

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

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

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

Publié par

pefav

Nombre de lectures

Langue

English

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 ·

Voir

Publié par

pefav

Nombre de lectures

Langue

English

JordanNormalandRationalNormalFormAlgorithmsBernardParisse,MorganeVaughanInstitutFourierCNRS-UMR5582100ruedesMathsUniversitédeGrenobleI38402StMartind’HèresCédexRésuméInthispaper,wepresentadeterministJordannormalformalgorithmsbasedontheFadeevformula:(λ∙I−A)∙B(λ)=P(λ)∙IwhereB(λ)is(λ∙I−A)’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..?λn−10000...?λnwherethereare1or0insteadofthe?.Itcorrespondstoafullfactorizationofthecha-racteristicalpolynomial.Iftheeldofcoefcientsisnotalgebraicallyclosed,thisJor-danformcanonlybeachievedbyaddingaeldextension.TheJordanrationalnormal1

Voir