Wie berechne ich das Minimalpolynom?
Benjamin B.
weiter, leider konnte ich auch nirgends praktische Beispiele finden.
Kann mir jemand am Beispiel
( 0 1 0 1 )
( 0 1 0 0 )
( -1 1 1 1 ) e R(4x4)
( -1 1 0 2 )
zeigen, wie ich das Minimalpolynom berechne oder mit Links zu anderen
(nicht trivialen) Beispielen geben? Bin für jeden Hilfe dankbar.
Benjamin
Thomas Blum
> Wie berechne ich das Minimalpolynom? Die Definition hilft mir nicht
> weiter, leider konnte ich auch nirgends praktische Beispiele finden.
> Kann mir jemand am Beispiel
> ( 0 1 0 1 )
> ( 0 1 0 0 )
> ( -1 1 1 1 ) e R(4x4)
> ( -1 1 0 2 )
Hi,
also, zunächst mußt Du das charakteristische Polynom bilden, das ist das
Produkt der (T-a_ii), also in diesem Fall:
T(T-1)(T-1)(T-2)=T((T-1)^2)(T-2).
Da das charakteristische Polynom und das Minimalpolynom dieselben
Nullstellen und dieselben irreduziblen Faktoren haben, ist das
Minimalpolynom demnach
T(T-1)(T-2).
Gruß
Thomas Blum
Christian Ohn
> gmb...@gmx.de (Benjamin B.) schrieb:
>
>> Wie berechne ich das Minimalpolynom? Die Definition hilft mir nicht
>> weiter, leider konnte ich auch nirgends praktische Beispiele finden.
>> Kann mir jemand am Beispiel
>> ( 0 1 0 1 )
>> ( 0 1 0 0 )
>> ( -1 1 1 1 ) e R(4x4)
>> ( -1 1 0 2 )
>
>
> Hi,
> also, zunächst mußt Du das charakteristische Polynom bilden, das ist das
> Produkt der (T-a_ii), also in diesem Fall:
>
> T(T-1)(T-1)(T-2)=T((T-1)^2)(T-2).
Nein!!!
Das charakteristische Polynom einer Matrix A ist die Determinante von A-xI,
wo I für die Einheitsmatrix steht. Das ist nur dann das Produkt der
(x-a_ii), wenn die Matrix triangulär ist (d.h. nur Nullen unterhalb [oder
oberhalb] der Diagonale). Im Allgemeinen ist das char. Polynom (bis auf ein
Vorzeichen) das Produkt der (x-\lambda_i), wo die \lambda_i die Eigenwerte
sind.
> Da das charakteristische Polynom und das Minimalpolynom dieselben
> Nullstellen und dieselben irreduziblen Faktoren haben, ist das
> Minimalpolynom demnach
>
> T(T-1)(T-2).
Selbst, wenn man vom obenstehenden char. Polynom ausgeht, stimmt das auch
nicht unbedingt: das einzige, das man vorab sagen kann, ist daß das char.
Polynom durch das min. Polynom teilbar ist, und daß jeder irreduzible
Faktor des char. Polynoms mindestens einmal im min. Polynom vorkommt. Es
können aber ggf. noch Exponenten >1 geben.
--
Christian Ohn
email: fr.rei...@ohn.christian (Reihenfolge umdrehen)
Web: http://christian.ohn.free.fr/math/
Philipp Zumstein
Christian Ohn <si...@unten.am.ende>
> > also, zunächst mußt Du das charakteristische Polynom bilden, das
ist das
> > Produkt der (T-a_ii), also in diesem Fall:
> >
> > T(T-1)(T-1)(T-2)=T((T-1)^2)(T-2).
>
> Nein!!!
Puh. Da bin ich aber froh, dass das nicht stimmt. Ich habe schon
gedacht alles was ich gelernt habe ich falsch oder man habe hier
wieder mal Magie betrieben:-)
> > Da das charakteristische Polynom und das Minimalpolynom dieselben
> > Nullstellen und dieselben irreduziblen Faktoren haben, ist das
> > Minimalpolynom demnach
> >
> > T(T-1)(T-2).
>
> Selbst, wenn man vom obenstehenden char. Polynom ausgeht, stimmt das
auch
> nicht unbedingt: das einzige, das man vorab sagen kann, ist daß das
char.
> Polynom durch das min. Polynom teilbar ist, und daß jeder
irreduzible
> Faktor des char. Polynoms mindestens einmal im min. Polynom
vorkommt. Es
> können aber ggf. noch Exponenten >1 geben.
Die Faktoren des Minimalpolynoms sind also die gleichen wie die des
char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
Exponenten heraus?
Gruss
Philipp
Boudewijn Moonen
>
> Die Faktoren des Minimalpolynoms sind also die gleichen wie die des
> char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> Exponenten heraus?
>
Ich zitiere jetzt dazu mal einiges aus Buechern ueber Lineare Algebra,
in denen *wirklich* was drin steht, nicht diese hier so oft
zitierte inhaltsleere Laberliteratur.
Als erstes haben wir da das gefuerchtete
E. Brieskorn: Lineare Algebra und Analytische Geometrie II
Dort finden wir auf Seite 75 ff.:
>
> DEFINITION. A in M(nxn,K) sei irgendeine Matrix. Dann sind dieser
> Matrix wie folgt Polynome d_k(x) in K[x], k=0,...,n zugeordnet:
>
> d_k(x) ist der normierte groesste gemeinsame Teiler aller
> Determinanten von kxk Untermatrizen von xE-A. d_0(x) = 1.
>
> Die d_k heissen die *Dererminantenfaktoren* von A.
>
> PROPOSITION 11.28
>
> d_{k-1}(x) teilt d_k(x) , k=1,...,n .
>
> DEFINITION Fuer A in M(nxn,K) seien d_1,...,d_n in K[x] die
> Determinantenfaktoren. Dann ist der Quotient
>
> e_k = d_k/d_{k-1} k = 1,...,n
>
> ein Polynom e_k in K[x]. Die e_k heissen die *Elementarteiler*
> von A.
>
> PROPOSITION 11.29 Konjugierte Matrizen haben die gleichen
> Elementarteiler.
>
> DEFINITION phi sei ein Endomorphismus eines n-dimensionalen
> K-Vektorraumes V . Dann sind die Elementarteiler e_1,...,e_n
> in K[x] die Elementarteiler der Matrix, durch die phi bezueglich
> einer Basis von V beschrieben wird.
>
> PROPOSITION 11.36 phi sei ein Endomorphismus eines n-dimensionalen
> Vektorraumes und e_1,...,e_n die Elementarteiler. Dann gilt:
>
> (i) Der groesste Elementarteiler e_n ist das Minimalpolynom
> von phi .
>
> (ii) Das Produkt der Elementarteiler e_1...e_n ist das
> charakteristische Polynom von phi .
>
Als naechstes haben wir
W. Greub: Lineare Algebra (erste Auflage)
Da findet sich in den Aufgaben zu 11.10:
>
> 4. Man zeige, dass man das Minimalpolynom einer linearen
> Selbstabbildung (sigma) auf folgende Art erhalten kann: Man waehle
> einen Vektor x_1 und bestimme die kleinste Zahl m_1, so dass
> die Vektoren sigma^{nu} (nu=0...m_1) linear abhaengig sind,
>
> sum_{nu=0}^{m_1} lambda_{nu} sigma^{nu} x_1 = 0 .
>
> Dann definiert man das Polynom f_1(u) durch
>
> f_1(u) = sum_{nu=0}^{m_1} lambda_{nu} u^{nu} .
>
> Spannen die Vektoren sigma^{nu} x_1 (nu=0...m_1) noch nicht den
> ganzen Raum A auf, so waele man einen Vektor x_2, der nicht in dem
> von diesen Vektoren erzeugten Unterraum liegt und wende auf diesen
> dasselbe Verfahren an. So erhaelt man ein Polynom f_2(x).
> Dieses Verfahren setze man fort, bis der ganze Raum A erschoepft
> ist. Das kleinste gemeinsame Vielfache der Polynome f_{rho} ist
> dann das Minimalpolynom von sigma.
>
Dann haben wir noch
W. Groebner: Matrizenrechnung
und finden dort in Kapitel V, Paragraph 3:
>
> (III) SATZ Eine quadratische n-zeilige Matrix A ueber dem
> Grundkoerper K besitzt ein charakteristisches Polynom
>
> (5.14) phi(sigma) = |sigma E-A| = sigma^n + ......
>
> und ein Minimalpolynom
>
> (5.2) m(sigma) = sigma^d + ...
>
> und zwar ist
>
> (5.16) phi(sigma) = m(sigma) mu(sigma) ,
>
> wo mu(sigma) der (n-1)-te *Determinantenteiler* der
> *charakteristischen Matrix* (sigma E-A), d.h. der (normierte)
> groesste gemeinsdame Teiler aller (n-1)-zeiligen
> Unterdeterminanten von (sigma E-A) oder derjenige aller
> Elemente von (sigma E-A)_ad ist.
>
Und schliesslich haben wir noch das (ziemlich aetzende)
H.-J. Kowalsky: Lineare Algebra (6. Auflage)
mit
>
> 35.6 Das Minimalpolynom f eines Endomorphismus phi von X
> ist ein Teiler seines charakteristischen Polynoms g. Ist
>
> g = +-p_1^{k_1}...p_l{k_l}
>
> die eindeutig bestimmte Produktdarstellung von g als
> Produkt von Potenzen normierter irreduzibler Polynome, so gilt
>
> f = +-p_1^{s_1}...p_l{s_l}
>
> wobei die Exponenten s_lambda durch den zweiten Teil von 35.5 bestimmt
> sind.
>
Schaut man sich den zweiten Teil von 35.5 an, so findet sich dort
>
> Es ist s_lambda die kleinste natuerliche Zahl k, fuer die
> Rg(p_lambda(phi)}^k = Rg(p_lambda(phi)}^{k+1} gilt.
>
Noch Fragen, Shaft?
MfG
--
Boudewijn Moonen
Institut fuer Photogrammetrie der Universitaet Bonn
Nussallee 15
D-53115 Bonn
Boudewijn Moonen
>
> Die Faktoren des Minimalpolynoms sind also die gleichen wie die des
> char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> Exponenten heraus?
>
Ich zitiere jetzt dazu mal einiges aus Buechern ueber Lineare Algebra,
Als naechstes haben wir
> ganzen Raum A auf, so waehle man einen Vektor x_2, der nicht in dem
Boudewijn Moonen
>
> Die Faktoren des Minimalpolynoms sind also die gleichen wie die des
> char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> Exponenten heraus?
>
Ich zitiere jetzt dazu mal einiges aus Buechern ueber Lineare Algebra,
in denen *wirklich* was drin steht, nicht diese hier so oft
zitierte inhaltsleere Laberliteratur.
Als erstes haben wir da das gefuerchtete
E. Brieskorn: Lineare Algebra und Analytische Geometrie II
Dort finden wir auf Seite 75 ff.:
>
> DEFINITION. A in M(nxn,K) sei irgendeine Matrix. Dann sind dieser
> Matrix wie folgt Polynome d_k(x) in K[x], k=0,...,n zugeordnet:
>
> d_k(x) ist der normierte groesste gemeinsame Teiler aller
> Determinanten von kxk Untermatrizen von xE-A. d_0(x) = 1.
>
> Die d_k heissen die *Determinantenfaktoren* von A.
Christian Wahle
>
> Die Faktoren des Minimalpolynoms sind also die gleichen wie die des
> char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> Exponenten heraus?
>
Eine ziemlich stupide Methode:
Nimm dir alle Faktoren des Charpols, setzte deren Exponenten auf 1, dann
setzt du die Matrix ein und schaust, ob null rauskommt. Wenn nicht, erhöhst
du etwa den Exponenten des ersten Faktors, der im Charpol auch mit
Vielfachheit >1 vorkommt und setzt wieder die Matrix ein und so weiter. Die
Exponenten erhöst du dabei natürlich nur bis zu der Vielfachheit, mit der
die Faktoren im Charpol auftauchen.
Das erste Polynom, bei dem 0 rauskommt, ist dann das MiPo.
mfg ChriWa
Christian Ohn
> Nimm dir alle Faktoren des Charpols, setzte deren Exponenten auf 1, dann
> setzt du die Matrix ein und schaust, ob null rauskommt. Wenn nicht,
> erhöhst du etwa den Exponenten des ersten Faktors, der im Charpol auch mit
> Vielfachheit >1 vorkommt und setzt wieder die Matrix ein und so weiter.
> Die Exponenten erhöst du dabei natürlich nur bis zu der Vielfachheit, mit
> der die Faktoren im Charpol auftauchen.
> Das erste Polynom, bei dem 0 rauskommt, ist dann das MiPo.
Beispiel: Charpol=(x-1)^5(x-2)^4, Minpol=(x-1)^3(x-2)^2. Wenn ich Deinen
Algorithmus richtig verstehe, kommt allerdings (x-1)^5(x-2)^2 dabei heraus.
Außerdem benötigst Du zuerst einmal eine Faktorisierung des Charpol's, was
nicht immer einfach zu ermitteln ist. Die von Boudewijn zitierte Methode in
Greub's "Lineare Algebra" umgeht dieses Problem.
Philipp Zumstein
Boudewijn Moonen <Boudewij...@ipb.uni-bonn.de> schrieb:
> Philipp Zumstein wrote:
>
> > Die Faktoren des Minimalpolynoms sind also die gleichen wie die
des
> > char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> > Exponenten heraus?
>
>
> E. Brieskorn: Lineare Algebra und Analytische Geometrie II
>
> Dort finden wir auf Seite 75 ff.:
>
> >
> > DEFINITION. A in M(nxn,K) sei irgendeine Matrix. Dann sind dieser
> > Matrix wie folgt Polynome d_k(x) in K[x], k=0,...,n zugeordnet:
> >
> > d_k(x) ist der normierte groesste gemeinsame Teiler aller
> > Determinanten von kxk Untermatrizen von xE-A. d_0(x) = 1.
> >
> > Die d_k heissen die *Dererminantenfaktoren* von A.
Diese Methode ist für - von Hand auszurechnen - doch recht mühsam.
Wenn ich dich richtig verstehe muss ich z.B. bei einer 3x3-Matrix für
d_2(x) zu berechnen zuerst die 9 2x2 Untermatrizen bilden und von
diesen die Determinante berechnen.
> Als naechstes haben wir
>
> W. Greub: Lineare Algebra (erste Auflage)
>
> Da findet sich in den Aufgaben zu 11.10:
>
> >
> > 4. Man zeige, dass man das Minimalpolynom einer linearen
> > Selbstabbildung (sigma) auf folgende Art erhalten kann: Man waehle
> > einen Vektor x_1 und bestimme die kleinste Zahl m_1, so dass
> > die Vektoren sigma^{nu} (nu=0...m_1) linear abhaengig sind,
> >
> > sum_{nu=0}^{m_1} lambda_{nu} sigma^{nu} x_1 = 0 .
> >
> > Dann definiert man das Polynom f_1(u) durch
> >
> > f_1(u) = sum_{nu=0}^{m_1} lambda_{nu} u^{nu} .
> >
> > Spannen die Vektoren sigma^{nu} x_1 (nu=0...m_1) noch nicht den
> > ganzen Raum A auf, so waele man einen Vektor x_2, der nicht in dem
> > von diesen Vektoren erzeugten Unterraum liegt und wende auf diesen
> > dasselbe Verfahren an. So erhaelt man ein Polynom f_2(x).
> > Dieses Verfahren setze man fort, bis der ganze Raum A erschoepft
> > ist. Das kleinste gemeinsame Vielfache der Polynome f_{rho} ist
> > dann das Minimalpolynom von sigma.
Ich hätte lieber etwas mit Matrizen. Tja... Und kann man nicht
ausnutzen, dass man das charakteristische Polynom kennt? Ich weiss
nicht ob die obige Methode mühsam ist zum ausrechnen.
> Dann haben wir noch
>
> W. Groebner: Matrizenrechnung
>
> und finden dort in Kapitel V, Paragraph 3:
>
> >
> > (III) SATZ Eine quadratische n-zeilige Matrix A ueber dem
> > Grundkoerper K besitzt ein charakteristisches Polynom
> >
> > (5.14) phi(sigma) = |sigma E-A| = sigma^n + ......
> >
> > und ein Minimalpolynom
> >
> > (5.2) m(sigma) = sigma^d + ...
> >
> > und zwar ist
> >
> > (5.16) phi(sigma) = m(sigma) mu(sigma) ,
> >
> > wo mu(sigma) der (n-1)-te *Determinantenteiler* der
> > *charakteristischen Matrix* (sigma E-A), d.h. der (normierte)
> > groesste gemeinsdame Teiler aller (n-1)-zeiligen
> > Unterdeterminanten von (sigma E-A) oder derjenige aller
> > Elemente von (sigma E-A)_ad ist.
Dies erscheint mir ähnlich wie die erste Methode, wobei man nicht mehr
alle Determinantenteiler auszurechnen braucht. Aber auch nur schon ein
Determinantenteiler auszurechnen erscheint mir sehr mühsam.
> Und schliesslich haben wir noch das (ziemlich aetzende)
>
> H.-J. Kowalsky: Lineare Algebra (6. Auflage)
>
> mit
>
> >
> > 35.6 Das Minimalpolynom f eines Endomorphismus phi von X
> > ist ein Teiler seines charakteristischen Polynoms g. Ist
> >
> > g = +-p_1^{k_1}...p_l{k_l}
> >
> > die eindeutig bestimmte Produktdarstellung von g als
> > Produkt von Potenzen normierter irreduzibler Polynome, so gilt
> >
> > f = +-p_1^{s_1}...p_l{s_l}
> >
> > wobei die Exponenten s_lambda durch den zweiten Teil von 35.5
bestimmt
> > sind.
> >
>
> Schaut man sich den zweiten Teil von 35.5 an, so findet sich dort
>
> >
> > Es ist s_lambda die kleinste natuerliche Zahl k, fuer die
> > Rg(p_lambda(phi)}^k = Rg(p_lambda(phi)}^{k+1} gilt.
Diese Methode gefällt mir am besten aber ich verstehe sie nicht ganz.
Also Mühe bekunde ich bei den lambda's. Bei dieser obigen Formel > >
Rg(p_lambda(phi)}^k = Rg(p_lambda(phi)}^{k+1}.
p_lambda(phi) ist doch ein Polynom in der Variablen phi. Dann rechne
ich dieses Polynom hoch k; dies ergibt wiederum ein Polynom. Was ist
dann aber der Rang eines Polynoms? Der Rang macht doch eigentlich nur
bei einem System von Vektoren Sinn. Klar kann ich Polynome als
Vektoren betrachten, aber der Rang eines einzelnen Vektors? Ich glaub
ich versteh die Formel noch nicht so ganz richtig.
> Noch Fragen, Shaft?
Ja, wie du siehst, gibt es noch Fragen für mich. Keine Ahnung auf was
Shaft anspielen soll. Als erstes kommt mir der Film in den Sinn und
Babylon meint dazu: Schacht, Schaft, Welle, Deichsel, Strahl;
ankurbeln. Dabei macht das Verb ankurbeln noch ein bisschen Sinn.
Ist es im allgemeinen wirklich sooo schwierig bzw. mühsam das
Minimalpolynom auszurechen? Ich meine das charakteristische Polynom
ist recht einfach auszurechnen im Vergleich zu dem was ich über die
Berechnungn des Minimalpolynom weiss.
Vielen Dank & Gruss
Philipp
Hermann Kremer
>Christian Wahle wrote:
>> Nimm dir alle Faktoren des Charpols, setzte deren Exponenten auf 1, dann
>> setzt du die Matrix ein und schaust, ob null rauskommt. Wenn nicht,
>> erhöhst du etwa den Exponenten des ersten Faktors, der im Charpol auch mit
>> Vielfachheit >1 vorkommt und setzt wieder die Matrix ein und so weiter.
>> Die Exponenten erhöst du dabei natürlich nur bis zu der Vielfachheit, mit
>> der die Faktoren im Charpol auftauchen.
>> Das erste Polynom, bei dem 0 rauskommt, ist dann das MiPo.
>
>Beispiel: Charpol=(x-1)^5(x-2)^4, Minpol=(x-1)^3(x-2)^2. Wenn ich Deinen
>Algorithmus richtig verstehe, kommt allerdings (x-1)^5(x-2)^2 dabei heraus.
Diese Methode ist eine Folgerung des Satzes von Cayley-Hamilton.
Algorithmus (für das obige Beispiel mit Matrix A ):
(A - 1*E) *(A - 2*E) =?= 0 ja --> fertig
(A - 1*E)^2*(A - 2*E) =?= 0 ja --> fertig
(A - 1*E) *(A - 2*E)^2 =?= 0 ja --> fertig
(A - 1*E)^2*(A - 2*E)^2 =?= 0 ja --> fertig
(A - 1*E)^3*(A - 2*E) =?= 0 ja --> fertig
(A - 1*E)^3*(A - 2*E)^2 =?= 0 ja --> fertig
(A - 1*E)^3*(A - 2*E)^3 =?= 0 ja --> fertig
(A - 1*E)^4*(A - 2*E) =?= 0 ja --> fertig
usw.
Die Matrizen (A - 1*E) und (A - 2*E) rechnet man sich vorher aus und muß
dann nur noch multiplizieren. Ist zwar stumpfsinnig, aber sehr einfach zu
programmieren.
>Außerdem benötigst Du zuerst einmal eine Faktorisierung des Charpol's, was
>nicht immer einfach zu ermitteln ist.
Die brauchst Du aber sowieso, wenn Du die Eigenwerte benötigst.
> Die von Boudewijn zitierte Methode in
>Greub's "Lineare Algebra" umgeht dieses Problem.
Gruß
Hermann
--
Christian Stapfer
3bb39765$1...@news.bluewin.ch...
>
> Christian Ohn <si...@unten.am.ende>
> > > also, zunächst mußt Du das charakteristische Polynom
> > > bilden, das ist das
> > > Produkt der (T-a_ii), also in diesem Fall:
> > >
> > > T(T-1)(T-1)(T-2)=T((T-1)^2)(T-2).
> >
> > Nein!!!
>
> Puh. Da bin ich aber froh, dass das nicht stimmt.
<snip/>
> Die Faktoren des Minimalpolynoms sind also die gleichen
> wie die des char. Polynoms. Aber wie bekommt man die
> Vielfachheit bzw. die Exponenten heraus?
In der Jordanschen Normalform könnte man sie direkt
ablesen ;-) aber einfacher ist wohl durch Einsetzen
der Matrix in das Polynom (bei kleinen Exponenten
beginnend) herauszufinden, mit welchen Exponenten
erstmals eine glatte 0 herauskommt...
Gruss,
Christian
Wolfram Hinderer
> Christian Ohn schrieb in Nachricht <9p1qs4$hsv$1...@wanadoo.fr>...
>>Christian Wahle wrote:
>>> Nimm dir alle Faktoren des Charpols, setzte deren Exponenten auf 1, dann
>>> setzt du die Matrix ein und schaust, ob null rauskommt. Wenn nicht,
>>> erhöhst du etwa den Exponenten des ersten Faktors, der im Charpol auch
>>> mit Vielfachheit >1 vorkommt und setzt wieder die Matrix ein und so
>>> weiter. Die Exponenten erhöst du dabei natürlich nur bis zu der
>>> Vielfachheit, mit der die Faktoren im Charpol auftauchen.
>>> Das erste Polynom, bei dem 0 rauskommt, ist dann das MiPo.
>>
>>Beispiel: Charpol=(x-1)^5(x-2)^4, Minpol=(x-1)^3(x-2)^2. Wenn ich Deinen
>>Algorithmus richtig verstehe, kommt allerdings (x-1)^5(x-2)^2 dabei
>>heraus.
>
>
> Diese Methode ist eine Folgerung des Satzes von Cayley-Hamilton.
> Algorithmus (für das obige Beispiel mit Matrix A ):
>
> (A - 1*E) *(A - 2*E) =?= 0 ja --> fertig
> (A - 1*E)^2*(A - 2*E) =?= 0 ja --> fertig
> (A - 1*E) *(A - 2*E)^2 =?= 0 ja --> fertig
> (A - 1*E)^2*(A - 2*E)^2 =?= 0 ja --> fertig
> (A - 1*E)^3*(A - 2*E) =?= 0 ja --> fertig
> (A - 1*E)^3*(A - 2*E)^2 =?= 0 ja --> fertig
>
> (A - 1*E)^3*(A - 2*E)^3 =?= 0 ja --> fertig
> (A - 1*E)^4*(A - 2*E) =?= 0 ja --> fertig
> usw.
Höchst unpraktisch, und falsch dazu. Wenn das charakteristische Polynom
(X-1)^2(X-2)^3 ist, bekommst du (X-1)^3(X-2)^3 heraus, wenn ich dich
richtig verstanden habe (na gut, die Leerzeile kann alles mögliche
bedeuten). Man müsste schon so vorgehen, dass vor einem Polynom alle seine
Teiler (die in Frage kommen) getestet werden.
Praktischer ist wohl, nur den Rang von (A-E)^1, (A-E)^2 usw. zu bestimmen,
bis sich nichts mehr ändert. Mit (A-2E) genauso. Dann hat man die Faktoren.
Gruss
Wolfram
Philipp Zumstein
Wolfram Hinderer <wolfram....@math.uni-karlsruhe.de> schrieb
> Praktischer ist wohl, nur den Rang von (A-E)^1, (A-E)^2 usw. zu
bestimmen,
> bis sich nichts mehr ändert. Mit (A-2E) genauso. Dann hat man die
Faktoren.
Wenn die Eigenwerte 1, 2,... sind, dann besteht das charakteristische
Polynom und auch das Minimalpolynom aus Faktoren (lambda-1),
(lambda-2),... Falls jetzt gilt Rg(A-1*E)^k = Rg(A-1*E)^(k+1) für ein
minimales k, dann ist dieses k die Vielfachheit des Faktors (lambda-1)
im Minimalpolynom. Stimmt dies? Habe ich das richtig vestanden? Ich
glaube diese Methode zur Berechnung des Minimalpolynoms könnte mir
noch gefallen:-)
Gruss
Philipp
Wolfram Hinderer
> Wenn die Eigenwerte 1, 2,... sind, dann besteht das charakteristische
> Polynom und auch das Minimalpolynom aus Faktoren (lambda-1),
> (lambda-2),... Falls jetzt gilt Rg(A-1*E)^k = Rg(A-1*E)^(k+1) für ein
> minimales k, dann ist dieses k die Vielfachheit des Faktors (lambda-1)
> im Minimalpolynom. Stimmt dies? Habe ich das richtig vestanden? Ich
> glaube diese Methode zur Berechnung des Minimalpolynoms könnte mir
> noch gefallen:-)
Ja. Besonders, wenn man noch eine zur Jordannormalform gehörende Basis
berechnen soll, ist das praktisch.
> Gruss
> Philipp
Gruß
Wolfram
P.S.: Bitte nicht posten *und* mailen.
Boudewijn Moonen
nicht gerade als Frage nach der *effektiven numerischen*
Berechnung des Minimalpolynoms verstanden, sondern als grundsaetzliche
Frage nach seiner Struktur in Relation zum charakteristischen
Polynom. Die Zitate sollten verschiedene Aspekte dieser
Relation beleuchten, und ich habe an keiner Stelle
behauptet, dass sie alle gleichermassen zur effektiven
numerischen Berechnung geeignet seien.
Philipp Zumstein wrote:
>
> Boudewijn Moonen <Boudewij...@ipb.uni-bonn.de> schrieb:
> > Philipp Zumstein wrote:
> >
> > > Die Faktoren des Minimalpolynoms sind also die gleichen wie die
> des
> > > char. Polynoms. Aber wie bekommt man die Vielfachheit bzw. die
> > > Exponenten heraus?
> >
> > Als erstes haben wir da das gefuerchtete
> >
> > E. Brieskorn: Lineare Algebra und Analytische Geometrie II
> >
> > Dort finden wir auf Seite 75 ff.:
> >
> > >
> > > DEFINITION. A in M(nxn,K) sei irgendeine Matrix. Dann sind dieser
> > > Matrix wie folgt Polynome d_k(x) in K[x], k=0,...,n zugeordnet:
> > >
> > > d_k(x) ist der normierte groesste gemeinsame Teiler aller
> > > Determinanten von kxk Untermatrizen von xE-A. d_0(x) = 1.
> > >
> > > Die d_k heissen die *Dererminantenfaktoren* von A.
> > > [...]
>
> Diese Methode ist für - von Hand auszurechnen - doch recht mühsam.
> Wenn ich dich richtig verstehe muss ich z.B. bei einer 3x3-Matrix für
> d_2(x) zu berechnen zuerst die 9 2x2 Untermatrizen bilden und von
> diesen die Determinante berechnen.
>
Na und, das ist doch so schlimm nun auch wieder nicht. Und ab n = 4
wuerde ich das so und so nicht per Hand machen, sondern z.B. mit
Maple.
>
> > Als naechstes haben wir
> >
> > W. Greub: Lineare Algebra (erste Auflage)
> >
> > Da findet sich in den Aufgaben zu 11.10:
> >
> > >
> > > 4. Man zeige, dass man das Minimalpolynom einer linearen
> > > Selbstabbildung (sigma) auf folgende Art erhalten kann: Man waehle
> > > einen Vektor x_1 und bestimme die kleinste Zahl m_1, so dass
> > > die Vektoren sigma^{nu} (nu=0...m_1) linear abhaengig sind,
> > >
> > > sum_{nu=0}^{m_1} lambda_{nu} sigma^{nu} x_1 = 0 .
> > >
> > > Dann definiert man das Polynom f_1(u) durch
> > >
> > > f_1(u) = sum_{nu=0}^{m_1} lambda_{nu} u^{nu} .
> > >
> > > Spannen die Vektoren sigma^{nu} x_1 (nu=0...m_1) noch nicht den
> > > ganzen Raum A auf, so waele man einen Vektor x_2, der nicht in dem
> > > von diesen Vektoren erzeugten Unterraum liegt und wende auf diesen
> > > dasselbe Verfahren an. So erhaelt man ein Polynom f_2(x).
> > > Dieses Verfahren setze man fort, bis der ganze Raum A erschoepft
> > > ist. Das kleinste gemeinsame Vielfache der Polynome f_{rho} ist
> > > dann das Minimalpolynom von sigma.
>
> Ich hätte lieber etwas mit Matrizen. Tja...
>
Das Bestehen auf persoenlichen Idiosynkrasien ist nicht unbedingt
immer der Weg ins Licht. Ich denke mal, dass diese Greubsche
Methode gar nicht so uebel ist. Beruht sie doch zunaechst nur
darauf, iterativ Vektoren zu bilden und auf lineare Abhaengigkeit
zu pruefen. Das duerfte leicht zu programmieren sein, und
Softwarepakete zur Pruefung auf lineare Abhaengigkeit gibt
es doch mittlerweile wie Floehe auf einem Hund. Ich denke,
diese Vorgehen ist in der Numerischen Mathematik durchaus bekannt,
Stichwort "Krylov-Folgen". Der einzige womoeglich etwas
schwierigere Schritt ist dann die Bestimmung des kgV der
so gewonnenen polynomialen Faktoren, aber das duerfte
auch ohne Zerlegung in irreduzible Faktoren gehen. So what.
>
> Und kann man nicht
> ausnutzen, dass man das charakteristische Polynom kennt?
>
Haeh? Wieso kennt man das charakteristische Polynom? Bei groesseren
Matrizen ist das numerisch auch eine nichttriviale Angelegenheit.
Und wieso sollte man das charakteristische Polynom kennen wollen?
Zumeist will man ja die Eigenwerte kennen, und wenn man die
(bei reellen oder komplexen) Matrizen ueber C kennt, kennt
man auch das charakteristische Polynom. Und der richtige
Weg zu den Eigenwerten fuehrt eben, wie ich mich dunkel
zu erinnern glaube, nicht ueber die Nullstellen des
charakteristischen Polynoms, sondern wenn ich Stoer-Bulirsch,
Einfuehrung in die Numerische Mathematik II, richtig lese,
z.B. darueber, dass man die Matrix durch Householder-Transformationen
auf eine Hessenberg-Form bringt und dann die Eigenwerte davon
mit dem QR-verfahren iterativ bestimmt.
>
> Ich weiss
> nicht ob die obige Methode mühsam ist zum ausrechnen.
>
Denke ich eben nicht.
>
> > Dann haben wir noch
> >
> > W. Groebner: Matrizenrechnung
> >
> > und finden dort in Kapitel V, Paragraph 3:
> >
> > >
> > > (III) SATZ Eine quadratische n-zeilige Matrix A ueber dem
> > > Grundkoerper K besitzt ein charakteristisches Polynom
> > >
> > > (5.14) phi(sigma) = |sigma E-A| = sigma^n + ......
> > >
> > > und ein Minimalpolynom
> > >
> > > (5.2) m(sigma) = sigma^d + ...
> > >
> > > und zwar ist
> > >
> > > (5.16) phi(sigma) = m(sigma) mu(sigma) ,
> > >
> > > wo mu(sigma) der (n-1)-te *Determinantenteiler* der
> > > *charakteristischen Matrix* (sigma E-A), d.h. der (normierte)
> > > groesste gemeinsdame Teiler aller (n-1)-zeiligen
> > > Unterdeterminanten von (sigma E-A) oder derjenige aller
> > > Elemente von (sigma E-A)_ad ist.
>
> Dies erscheint mir ähnlich wie die erste Methode, wobei man nicht mehr
> alle Determinantenteiler auszurechnen braucht. Aber auch nur schon ein
> Determinantenteiler auszurechnen erscheint mir sehr mühsam.
>
Das ist richtig. Ebenso muehsam, wie das charakteristische Polynom ueber
die Determinante auszurechnen. Aber da gibt es eben
Gauss-Cholesky-Verfahren. Und, wie gesagt, ich habe nirgendwo
anempfohlen, das numerisch so zu machen.
>
> > Und schliesslich haben wir noch das (ziemlich aetzende)
> >
> > H.-J. Kowalsky: Lineare Algebra (6. Auflage)
> >
> > mit
> >
> > >
> > > 35.6 Das Minimalpolynom f eines Endomorphismus phi von X
> > > ist ein Teiler seines charakteristischen Polynoms g. Ist
> > >
> > > g = +-p_1^{k_1}...p_l{k_l}
> > >
> > > die eindeutig bestimmte Produktdarstellung von g als
> > > Produkt von Potenzen normierter irreduzibler Polynome, so gilt
> > >
> > > f = +-p_1^{s_1}...p_l{s_l}
> > >
> > > wobei die Exponenten s_lambda durch den zweiten Teil von 35.5
> bestimmt
> > > sind.
> > >
> >
> > Schaut man sich den zweiten Teil von 35.5 an, so findet sich dort
> >
> > >
> > > Es ist s_lambda die kleinste natuerliche Zahl k, fuer die
> > > Rg(p_lambda(phi)}^k = Rg(p_lambda(phi)}^{k+1} gilt.
>
> Diese Methode gefällt mir am besten aber ich verstehe sie nicht ganz.
> Also Mühe bekunde ich bei den lambda's. Bei dieser obigen Formel > >
> Rg(p_lambda(phi)}^k = Rg(p_lambda(phi)}^{k+1}.
>
> p_lambda(phi) ist doch ein Polynom in der Variablen phi.
>
Jein. p_lambda ist ein Polynom in einer Unbestimmten, sagen wir u.
p_lambda(phi) ist dann der Endomorphismus, der dadurch entsteht,
dass ich den Endomorphismus phi fuer u einsetze.
>
> Dann rechne
> ich dieses Polynom hoch k; dies ergibt wiederum ein Polynom.
>
Jein. Gibt wieder einen Endomorphismus.
>
> Was ist
> dann aber der Rang eines Polynoms? Der Rang macht doch eigentlich nur
> bei einem System von Vektoren Sinn. Klar kann ich Polynome als
> Vektoren betrachten, aber der Rang eines einzelnen Vektors? Ich glaub
> ich versteh die Formel noch nicht so ganz richtig.
>
Gemeint ist eben der Rang des so entstandenen Endomorphismus.
Falls das charakteristische Polynom vollstaendig zerfaellt,
ist dies genau das von Wolfram Hinderer vorgeschlagene Verfahren,
das Dich so in Ekstase versetzt hat.
>
> > Noch Fragen, Shaft?
>
> Ja, wie du siehst, gibt es noch Fragen für mich. Keine Ahnung auf was
> Shaft anspielen soll. Als erstes kommt mir der Film in den Sinn und
> Babylon meint dazu: Schacht, Schaft, Welle, Deichsel, Strahl;
> ankurbeln. Dabei macht das Verb ankurbeln noch ein bisschen Sinn.
>
Gruebel nicht. War nur eine ad-hoc-Assoziation zum Filmtitel.
Haette auch sagen koennen: Noch Fragen?
>
> Ist es im allgemeinen wirklich sooo schwierig bzw. mühsam das
> Minimalpolynom auszurechen?
>
Ist wohl nicht ohne.
>
> Ich meine das charakteristische Polynom
> ist recht einfach auszurechnen im Vergleich zu dem was ich über die
> Berechnungn des Minimalpolynom weiss.
>
Also, wie gesagt, die Berechnung des charakteristischen Polynoms ist
auch nicht so ohne. Zusammengefasst wuerde ich das Minimalpolynom
so ausrechnen (aber warum eigentlich ueberhaupt?)
a) Entweder nach der Greub-Methode
oder (ueber R, C)
b) erst die Eigenwerte, dann das charakteristische Polynom und
seine Faktorisierung ueber die Eigenwerte, und dann die
Multiplizitaeten der irreduziblen Faktoren ueber das
Konstantwerden der Raenge der iterierten Faktoren. Aber
vielleicht sagen dann Experten, dass man dann genausogut
die Frobenius-Normalform bestimmen kann, aus der man das
Minimalpolynom direkt abliest. Koennte so ziemlich
dasselbe sein.
Philipp Zumstein
"Boudewijn Moonen" <Boudewij...@ipb.uni-bonn.de> schrieb
> > Ist es im allgemeinen wirklich sooo schwierig bzw. mühsam das
> > Minimalpolynom auszurechen?
>
> Ist wohl nicht ohne.
>
> > Ich meine das charakteristische Polynom
> > ist recht einfach auszurechnen im Vergleich zu dem was ich über die
> > Berechnungn des Minimalpolynom weiss.
>
> Also, wie gesagt, die Berechnung des charakteristischen Polynoms ist
> auch nicht so ohne. Zusammengefasst wuerde ich das Minimalpolynom
> so ausrechnen (aber warum eigentlich ueberhaupt?)
Warum eigentlich überhaupt das Minimalpolynom ausrechnen? Berechtigte Frage.
Wahrscheinlich lese ich ungerne Theorie über das Minimalpolynom, ohne das
Minimalpolynom selbst ausrechnen zu können. Jetzt kann ich mir auf jedenfall
ein paar Beispiel ansehen/ausrechnen.
> a) Entweder nach der Greub-Methode
>
> oder (ueber R, C)
>
> b) erst die Eigenwerte, dann das charakteristische Polynom und
> seine Faktorisierung ueber die Eigenwerte, und dann die
> Multiplizitaeten der irreduziblen Faktoren ueber das
> Konstantwerden der Raenge der iterierten Faktoren. Aber
> vielleicht sagen dann Experten, dass man dann genausogut
> die Frobenius-Normalform bestimmen kann, aus der man das
> Minimalpolynom direkt abliest. Koennte so ziemlich
> dasselbe sein.
Ich glaube b) ist die mir zugänglichere Variante [hoffe Formulierung ist
klar?]. Übrigens ich will das Minimalpolynom nicht numerisch sondern von
Hand ausrechnen. Zumindest mal in erster Linie.
Ich hab' noch viel Information zum Verarbeiten von deinen Postings. Aber
jetzt hab' ich mal wieder etwas Zeit - nach den Prüfungen.