Minimal möglicher Eigenwert einer streng diagonaldominanten Matrix

Aufrufe: 161     Aktiv: vor 4 Tagen, 7 Stunden

0

Hallo,

ich hätte da ein Problem aus der linearen Algebra, wo ich jetzt an die Grenzen stoße bzw. auch mein Rechner an seine Kapazität kommt (Rechenzeit!!!).

 

Es liegt eine (n+1)x(n+1)-Quadratmatrix vor, deren Elemente wie folgt definiert sind:

Die Diagonalelemente sind alle gleich:

a_ii = (n+1)^n          n: Element der Natürlichen Zahlen

Jede Zeile j weist stets dieselben n unterschiedlichen Elemente auf, die jedoch beliebig in der entsprechenden Zeile angeordnet werden können (mit Ausnahme der Diagonalelemente!):

a_ij = n*(n+1)^(n-k)     für k = 1 … n

 

Eine beliebig in den Zeilen durcheinandergewürfelte Quadratmatrix dieser Art hat immer denselben maximalen Eigenwert.

Lambda_max = 2*(n+1)^n – 1

 

Für den speziellen Fall (n = 6) würde ich nun gerne wissen, welcher minimalste Eigenwert bei einer bestimmten „Zeilen-Durchwürfelung“ der Matrix erreicht werden kann? Gibt es da eine Möglichkeit, dieses überhaupt berechnen bzw. abschätzen zu können? Den kleinsten Wert, den ich bisher herausgefunden habe, ist 391.Ich glaube aber, dass es noch einen kleineren Wert gibt. Aber da wird mein Rechner wahrscheinlich lange rechnen können, bis er diesen Treffer irgendwann rein zufällig mal landet.  

 

Lambda_min < 391 ???  (Vermutung)

Lambda_min = 355 ???  (Vermutung)

Lambda_min = ???

 

Vielleicht weiß ja jemand, wie man das Problem weiter eingrenzen oder gar lösen kann?

 

Diese Frage melden
gefragt

Punkte: 10

 

Formuliere erstmal Dein Problem präzise.
Anstelle von a_ij = n*(n+1)^(n-k) für k = 1 … n meinst Du vielleicht $\{a_{ij} | j=1,...?\} = \{ n\cdot (n+1)^{n-k} | k=...\}$? Bitte genaue Angaben und LaTeX verwenden.
"Eine beliebig in den Zeilen durcheinandergewürfelte Quadratmatrix dieser Art hat immer denselben maximalen Eigenwert." Was heißt "durcheinandergewürftelt"? Und ist diese Aussage bekannt/bewiesen oder was?
Und sprachlich, nebenbei, "minimalst" gibt es nicht.
  ─   mikn 27.01.2025 um 12:21

Vielen Dank für die Hinweise!

Bezüglich des maximalen Eigenwertes habe ich den Satz von "Perron-Frobenius" so gedeutet (siehe Punkt 11 vom folgenden Link).

https://en.wikipedia.org/wiki/Perron-Frobenius_theorem

Denn jede i-te Zeile weist (n+1) unterschiedliche Elemente auf, deren Summe in allen j Zeilen immer konstant ist. Also wäre diese konstante Summe zugleich der größte Eigenwert, bzw. der dazugehörige Eigenvektor weist dann nur Einsen auf (1,1,1,...,1). - Aber vielleicht bin ich ja auch einem Irrtum verfallen???

Mit "durchgewürfelte" Zeile meinte ich, dass n Elemente jeder Zeile beliebig vertauscht (permutiert) werden dürfen.

Ich gebe zu, die Wortwahl von "minimalste" ist sehr unschön, aber als umgangssprachlich flektierter Superlativ nicht strikt verboten. Sogar der Duden dekliniert inzwischen diese unreine Form. Aber ich gelobe Besserung und werde diesbezüglich künftig darauf achten und sowohl auf den Komparativ als auch auf den Superlativ verzichten ;)

https://www.duden.de/deklination/adjektive/minimal
https://de.wiktionary.org/wiki/Flexion:minimal
  ─   user4145c5 27.01.2025 um 14:22

Man zögert sich auf die Frage einzulassen, wenn. nicht eindeutig klar ist, worum es geht. Du wirbelst auch jetzt wieder mit i und j herum, in verschwommener Weise. Deine Antwort auf meine erste Rückfrage fehlt noch. Und auch evtl hilfreich: was ist der Hintergrund, woher stammt die Matrix?   ─   mikn 27.01.2025 um 14:57

Man kann zeigen, dass der betragsmäßig kleinste Eigenwert positiv ist:

Sei A irgendeine Matrix, die dem Schema der Aufgabenstellung genügt.
Sei \(d=(n+1)^n\).
Setze \(A'=d^{-1}A\).
Betrachte nun die Eigenwertaufgabe \(A'^{-1}x = \mu x\).
Es gilt: \(A'^{-1}>0\;\;\;\) (*)
Das soll bedeuten: Alle Einträge von \(A'^{-1}\) sind positiv.
(Bew.: s.u.) Also gibt es laut dem Perron-Frobenius-Theorem ein \(\mu>0\), so dass \(\mu\) der betragsmäßig größte Eigenwert von \(A'^{-1}\) ist.
Also ist \(\lambda = \alpha/\mu>0 \) der betragsmäßig kleinste Eigenwert von A.

Beweis von (*): Setze \(B=A'-I\), wobei \(I\) = Einheitsmatrix.
Wegen Diagonaldominanz ist \(\|B\|<1\), wobei \(\|.\|\) die Zeilensummennorm ist.
Dann ist \(\displaystyle A'^{-1} = (I-(-B))^{-1} = \sum_{k=0}^{\infty} (-B)^k = (I-B) \sum_{k=0}^{\infty} B^{2k}\).
Wegen Diagonaldominanz ist \(I-B>0\).
B>0 also auch \(B^{2k}>0\).
Also ist \(A'^{-1}>0\).
  ─   m.simon.539 27.01.2025 um 19:27

Vielen lieben Dank für diese ausführliche Herleitung!!!

Die Aussage, dass der betragsmäßig kleinste Eigenwerte positiv ist, sichert schon mal die untere Grenze für den minimalen Eigenwert ab. Den Beweis (*) werde ich mir noch ganz in Ruhe zu Gemüte führen.
  ─   user4145c5 27.01.2025 um 21:11

Vergiß meinen letzten Kommentar. "\(I-B>0\)" gilt natürlich nicht, da negative Elemente vorhanden.
Habe "positiv" mit "positiv definit" verwechselt.
  ─   m.simon.539 28.01.2025 um 03:00

Habe mal ein Programm geschrieben, welches per Zufallsgenerator eine Matrix erzeugt, die den Vorgaben genügt. Der kleinste reelle Eigenwert war 2509,065.
Der Eigenvektor lautete hier:
\(\left(\begin{array}{r}
0,\!401497914 \\
0,\!400183520 \\
0,\!403296972 \\
0,\!300420426 \\
-0,\!409687582 \\
0,\!302476100 \\
-0,\!407941159 \\
\end{array} \right) \)

Die Beträge der Einträge gleichen sich auffallend.

Ziemlich oft lag der Wert zwischen 16.000 und 17.000.

Ja, und natürlich habe ich auch jede Menge Matrizen gefunden, bei denen der betragsmäßig kleinste Eigenwert nicht reell war.

Alle \((720!)^7\) möglichen Matrizen durchzuprobieren dauert wirklich!

Tja, die Aufgabenstellung ist einigermaßen widerlich.

Noch eine interessante Beobachtung: Bei n=3 sind alle gefundenen Eigenwerte Quadratzahlen (16, 25).
  ─   m.simon.539 28.01.2025 um 20:42

Danke für das Gegenchecken der Matrizen!!!

Für n=3 erhalte ich als kleinsten betragsmäßigen Eigenwert 7. Ein Beispiel wären die Eigenwerte dieser Matrix:

$$ \begin{pmatrix} 64 & 3 & 12 & 48 \\ 3 & 64 & 48 & 12 \\ 12 & 48 & 64 & 3 \\ 12 & 48 & 3 & 64 \end{pmatrix} $$
Bei n=6 stolpere ich stets über den (bisher!) betragsmäßig kleinsten Eigenwert 391. An diesem Kandidat komme ich nicht mehr vorbei. Der maximale Eigenwert wird dann mit dieser Zeilensumme gebildet:

$$ \lambda_{max}=6+42+294+2058+14406+100842+117649=235297 $$
Zum Generieren von möglichst kleinen Eigenwerten (als prüfende Vorstufe) hat sich bei mir gezeigt, dass ich dazu erst einmal nur in den Zeilen 1, 2, 3, 5, 6 vertauschen (permutieren) muss. Die Zeile 4 und 7 habe ich konstant gelassen mit folgenden Einträgen. Dann sollten einem eigentlich recht schnell reelle Eigenwerte < 2509 begegnen.

$$ i=4: \text{ } \begin{pmatrix} 294 & 42 & 6 & 117649 & 100842 & 14406 & 2058 \end{pmatrix} $$
$$ i=7: \text{ } \begin{pmatrix} 100842 & 14406 & 2058 & 294 & 42 & 6 & 117649 \end{pmatrix} $$

Doch irgendwie habe ich das Gefühl, dass da noch ein reeller Eigenwert < 391 in der Matrix schlummert. Aber Angesichts der Vielzahl an Möglichkeiten scheint mir es ausgeschlossen, das überprüfen zu können.
  ─   user4145c5 29.01.2025 um 10:43

Nochmal meine Frage: "Und auch evtl hilfreich: was ist der Hintergrund, woher stammt die Matrix?"   ─   mikn 29.01.2025 um 12:00

Der Hintergrund (als Nicht-Mathematiker) ist eigentlich nur ein amateurhaftes Interesse daran, wie sich die Matrix-Einträge auf die Eigenwerte auswirken. Eigentlich bin ich auf diese Einträge nur gekommen, weil mich eine generelle Form einer streng diagonaldominanten Matrix interessiert hat. Das war der Ausgangspunkt. Der Rest war dann nur mein ingenieurhafter Spieltrieb und die daran geküpfte Frage, wie man an die betragsmäßig unteren Eigenwerte einer nicht mehr berechenbaren Quadratmatrix herankommt, deren Schwelle bei n=6 so langsam erreicht ist. Mehr steckt da leider nicht dahinter. Die Einträge hätten auch ganz anders aussehen können, um die Matrix diagonaldominant zu besetzen. Letztenendes ist das nur die Betrachtung eines Spezialfalles einer speziell besetzten Matrix. Und ich denke, es lässt sich lediglich nur eine grobe Abschätzung angeben was die unteren Eigenwerte betrifft, wie es ja die Gerschgorin-Kreise zeigen. Das wäre dann aber eine äußerst grobe Abschätzung. Man sollte hier aber auch nicht zu viel Mühe reinstecken. Ich hatte nur die Hoffnung, es gäbe eine bessere Abschätzungsmöglichkeit für die betragsmäßig unteren Eigenwerte. Aber dann wird das Thema bestimmt zu diffizil.   ─   user4145c5 29.01.2025 um 14:04

Danke, ok, verstehe. Für Abschätzungen für EWe gibt es generell nicht viele Resultate, besonders wie hier im nichtsymmetrischen Fall.   ─   mikn 29.01.2025 um 14:27
Kommentar schreiben
2 Antworten
0

Zur Anwendung des Perron-Frobenius-Theorems:

Deine Zeilensumme stimmt (wenn ich Deine fehlenden Angaben richtig ergänzt habe). Aber die Aussage ist nur, dass dies der Betrag des betragsgrößten EWs ist. Der dahinter stehende EW kann durchaus negativ oder auch komplex sein.

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 40.03K

 

Mithilfe von Gerschgorin-Kreisen kann man schnell sehen, dass alle EW Realteil $\ge 1$ haben müssen.   ─   mikn 27.01.2025 um 20:09

Vielen lieben Dank für den Hinweis!

Die Gerschgorin-Kreise sind ein sehr gutes Instrument, um die EW mit Realteil einzugrenzen. Interessant finde ich, dass man in diesem Beispiel nach oben hin (maximaler Eigenwert-real) ganz konkret einen Wert angeben kann, aber nach unten hin (minimaler Eigenwert-real) nur eine untere Schwelle setzen kann. Ich glaube, da enden auch schnell weitere Aussagen darüber, welchen minimalen Eigenwert-real man als Untergrenze erwarten kann.
  ─   user4145c5 27.01.2025 um 21:03

Kommentar schreiben

0
Ich habe jetzt ein Java-Programm geschrieben, welches von einer Startmatrix aus den kleinsten Eigenwert aller benachbarten Matrizen ausrechnet, und dann zu der Nachbarmatrix mit dem kleinsten reellen EW übergeht. Das wird so lange wiederholt, bis sich der kleinste Eigenwert nicht weiter verkleinert.

Dabei sind zwei Matrizen A, B benachbart, wenn
- A und B der Beschreibung der Aufgabenstellung genügen
- es einen Zeile-Index i gibt, so dass B aus A entsteht, wenn man Zeile i zwei Elemente vertauscht.

Ich habe den Algorithmus mit etlichen zufallsgenerierten Start-Matrizen laufen lassen. Ich landete immer beim Eigenwert 391,0000. Dieser Eigenwert ist vermutlich ganzzahlig.

Das schließt kleinere Eigenwerte nicht aus. 391 kann auch sowas wie ein lokales Minimum sein, und das globale Minimum liegt in einem schmalen, tiefen Tal, welches man so schnell nicht findet.
Diese Antwort melden
geantwortet

Punkte: 2.59K

 

Noch einmal vielen Dank für weitere Versuchsdurchläufe bzgl. der Matrizen!!!
Ich habe ebenfalls feststellen müssen, dass der Wert "391" eine knallharte Grenze darstellt. Oberhalb von 391 ist das nicht der Fall, da man sich diesem (lokalem?) Minimum allmählich nähern kann. Wenn man bedenkt, dass bei n=4 nur insgesamt 26880 Treffer existieren, um den minimalen Wert "29" zu erhalten (bei 7 962 624 verschiedenen Matrixanordnungen!), dann kann sich erst recht bei n=6 noch ein globales Minimum in $720^7$ Matrix-Anordnungen verbergen. Ich glaube, damit wären wir am Ende mit unserer Weisheit.
  ─   user4145c5 vor 4 Tagen, 7 Stunden

Kommentar schreiben