Matroids Matheplanet Forum Index
Moderiert von Fabi Dune ligning
Lineare Algebra » Eigenwerte » Fragen zu "Fast algorithms for the characteristic polynomial" v. Walter Keller-Gehrig
Autor
Universität/Hochschule J Fragen zu "Fast algorithms for the characteristic polynomial" v. Walter Keller-Gehrig
mathaematician
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.10.2020
Mitteilungen: 5
  Themenstart: 2021-09-25 20:51

Guten Abend zusammen, ich lese gerade folgenden Artikel: Fast algorithms for the characteristic polynomial . Ich bin allerdings der Meinung, dass der "simple" Algorithmus in Abschnitt 3 ein signifikantes Problem hat. Vielleicht missinterpretiere ich "with indeterminate coefficients" auch einfach falsch, für mich heißt das einfach, dass die Einträge der Matrix beliebig sein können. Aber wenn ich dann noch einen beliebigen Vektor \(e \neq 0\) nehme, dann ist das System \( (e,Ae,...,A^{n-1}e ) \) im allg. doch nicht linear unabhängig.. Man kann sich ja ein einfaches Gegenbeispiel überlegen, z.B. \[A = \begin{pmatrix} 1&0&0\\0&1&1 \\ 0&0&1 \end{pmatrix} \text{ und } e = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\] und hier ist doch sogar für alle \( e \in k^n \) das System \( (e,Ae,A^{2}e) \) linear abhängig! Und die Matrix U somit auch niemals regulär?! Übersehe oder missinterpretiere ich hier vielleicht einfach irgendwas? Ich vermute das geht nur, falls das MiPo gleich dem char. Poly. ist, sonst bekommt man doch immer eine nicht-triviale Linearkombination dieser Vektoren hin.. Aber was bringt mir der Algorithmus dann? ^^ LG und schönen Abend noch!


   Profil
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3299
Wohnort: Berlin
  Beitrag No.1, eingetragen 2021-09-25 21:37

Ohne das im Detail nachvollzogen zu haben: Mit "unbestimmten" Koeffizienten sind hier vermutlich tatsächlich Variablen gemeint, nicht beliebige Werte. Genau genommen ist $A$ also eine Matrix über dem Polynomring in $n^2$ Unbestimmten, $k[X_{11}, \ldots, X_{1n}, X_{21}, \ldots, X_{nn}]$, nämlich die mit den Einträgen $A_{ij} = X_{ij}$.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2677
  Beitrag No.2, eingetragen 2021-09-25 22:09

Vermutlich eher über $k(X_{11}, \ldots, X_{1n}, X_{21}, \ldots, X_{nn})$, da man die entstehende Matrix $U$ ja invertieren möchte. --zippy


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3017
  Beitrag No.3, eingetragen 2021-09-25 22:54

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Wie ligning und zippy gesagt haben, ist $A$ als Matrix über dem Körper $K=k(X_{11},\ldots,X_{nn})$ gemeint, wobei $A_{ij}=X_{ij}$. Dann ist $U$ invertierbar, denn wenn man z.B. $X_{ij}=\delta_{i,j+1}$ einsetzt wird $U$ invertierbar und folglich kann die Determinante von $U$ in $K$ nicht verschwinden. Eine wichtige Beobachtung ist noch, dass die Matrix $U^{-1}AU$ in Frobeniusnormalform ist und nur Einträge in $k[X_{11},\ldots, X_{nn}]$ hat (also nur polynomiale Einträge, keine gebrochen rationalen). Letzteres gilt, weil $AU$ offenbar nur polynomiale Einträge hat und es damit für jedes $v\in k^n$ Polynome $\lambda_1,\cdots, \lambda_n\in k[X_{11},\ldots, X_{nn}]$ gibt mit $$AUv = \sum_{j=0}^{n-1}\lambda_j A^je = \sum_{j=0}^{n-1}\lambda_j Ue_{j},$$ wobei $e_0,\ldots, e_{n-1}\in K^n$ die Standardbasis ist. Also ist $$U^{-1}AUv = \sum_{j=0}^{n-1}\lambda_je_j\in k[X_{11},\ldots, X_{nn}]^n.$$ \(\endgroup\)


   Profil
mathaematician
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.10.2020
Mitteilungen: 5
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-26 10:13

Guten morgen, und Danke euch! Ihr habt natürlich vollkommen Recht, ich war da evtl. etwas zu ungeduldig beim lesen. Im Beweis zu Theorem 5.1 schrieb er dann auch, dass der Algorithmus hier jetzt für die Anwendung auf beliebige Matrizen adaptiert wird Ich habs gerade auch mal aus Spaß für 3x3 durch Sage gejagt \[A = \left(\begin{array}{rrr} T_{0} & T_{1} & T_{2} \\ T_{3} & T_{4} & T_{5} \\ T_{6} & T_{7} & T_{8} \end{array}\right), e = \left(\begin{array}{r} 1 \\ 0 \\ 0 \end{array}\right)\rightarrow U = \left(\begin{array}{rrr} 1 & T_{0} & T_{0}^{2} + T_{1} T_{3} + T_{2} T_{6} \\ 0 & T_{3} & T_{0} T_{3} + T_{3} T_{4} + T_{5} T_{6} \\ 0 & T_{6} & T_{0} T_{6} + T_{3} T_{7} + T_{6} T_{8} \end{array}\right)\] \[U^{-1}AU = \left(\begin{array}{rrr} 0 & 0 & -T_{2} T_{4} T_{6} + T_{1} T_{5} T_{6} + T_{2} T_{3} T_{7} - T_{0} T_{5} T_{7} - T_{1} T_{3} T_{8} + T_{0} T_{4} T_{8} \\ 1 & 0 & T_{1} T_{3} - T_{0} T_{4} + T_{2} T_{6} + T_{5} T_{7} - T_{0} T_{8} - T_{4} T_{8} \\ 0 & 1 & T_{0} + T_{4} + T_{8} \end{array}\right)\] \[\chi_A = x^{3} + \left(-T_{0} - T_{4} - T_{8}\right) x^{2} + \left(-T_{1} T_{3} + T_{0} T_{4} - T_{2} T_{6} - T_{5} T_{7} + T_{0} T_{8} + T_{4} T_{8}\right) x + T_{2} T_{4} T_{6} - T_{1} T_{5} T_{6} - T_{2} T_{3} T_{7} + T_{0} T_{5} T_{7} + T_{1} T_{3} T_{8} - T_{0} T_{4} T_{8}\] und siehe da, plötzlich funktioniert es. Jetzt bin ich gespannt wie er das für beliebige Matrizen anpasst. Vielen Dank nochmals! Und einen schönen Sonntag euch :)


   Profil
mathaematician
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.10.2020
Mitteilungen: 5
  Beitrag No.5, vom Themenstarter, eingetragen 2021-09-27 14:48

Vielleicht noch eine Anmerkung zu Kapitel 5, m.M.n. sollte es dort \[ W_{ij} = \begin{cases} V_{ij} & \text{if } V_{ij} \text{ has less than } 2^i \text{ columns},\\\left(V_{ij},A^{2^i}V_{ij}\right) & \text{otherwise.} \end{cases} \] heißen. Man möchte ja, dass die \( V_{ij} \) von der Form \( V_{ij} = (e_j, Ae_j, A^2e_j,...) \) sind.


   Profil
mathaematician hat die Antworten auf ihre/seine Frage gesehen.
mathaematician hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]