Discussion:
Semi-Definitheit und Indefinitheit symmetrischer Matrizen
Add Reply
Stephan Gerlach
2017-05-19 23:33:30 UTC
Antworten
Permalink
Raw Message
Im Folgenden betrachte ich nur reelle, symmetrische nxn-Matrizen.
(Mit komplexen Matrizen funktioniert das Ganze ähnlich.)

Jedes Kind kennt das Hauptminoren-Kriterium von Sylvester für positiv
definite Matrizen:

Satz [1]
--------
Eine Matrix A ist positiv definit
<=> A hat nur positive Eigenwerte
<=> Die Determinanten derjenigen Haupt-Untermatrizen, die jeweils die
Spalten/Zeilen von 1 bis k enthalten, wobei k die Menge {1,...,n}
durchläuft, sind alle > 0.

JFTR: Daraus kann man leicht ein ähnliches Kriterium für negativ
definite Matrizen herleiten.


Für positiv semidefinite (andere Bezeichnung: nichtnegativ definite)
Matrizen A ist es schon komplizierter, jedenfalls was die
Determinanten-Bedingung betrifft.
Die Implikation
"Eine Matrix A ist positiv definit"
=> "die genannten Hauptuntermatrizen haben alle nichtnegative Determinanten"
ist einfach zu beweisen. Die Rückwärts-Richtung "<=" ist IMHO aber i.a.
falsch(!); es gibt einfache Gegenbeispiele.


Irgendwo habe ich mal gelesen, daß "<=" jedoch gilt, wenn man die
Determinanten-Aussage auf *alle* Hauptuntermatrizen ausdehnt, also nicht
nur diejenigen, bei denen genau "die ersten k Spalten und Zeilen vorkommen".

Der Beweis dafür ist mir aber nicht a priori klar; bzw. mir fällt
partout nicht ein, wie man das aus Satz [1] für positiv definite
Matrizen herleiten könnte.
Für dessen Beweis wird BTW das Schurkomplement benötigt; es geht mit
vollständiger Induktion.

Ebenfalls nicht zum Ziel zu führen scheint die indirekte Variante:
"Wir nehmen an, daß A indefinit wäre, und zeigen, daß es dann eine
Hauptuntermatrix mit Determinante <0 gäbe..."

Argumentationen über die Eigenwerte bzw. Hauptachsentransformation
erscheinen auf den ersten Blick ebenfalls nicht zielführend.

Kennt jemand eine Lösung dieses Problems?
--
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Roland Franzius
2017-05-20 07:24:59 UTC
Antworten
Permalink
Raw Message
Post by Stephan Gerlach
Im Folgenden betrachte ich nur reelle, symmetrische nxn-Matrizen.
(Mit komplexen Matrizen funktioniert das Ganze ähnlich.)
Jedes Kind kennt das Hauptminoren-Kriterium von Sylvester für positiv
Satz [1]
--------
Eine Matrix A ist positiv definit
<=> A hat nur positive Eigenwerte
<=> Die Determinanten derjenigen Haupt-Untermatrizen, die jeweils die
Spalten/Zeilen von 1 bis k enthalten, wobei k die Menge {1,...,n}
durchläuft, sind alle > 0.
JFTR: Daraus kann man leicht ein ähnliches Kriterium für negativ
definite Matrizen herleiten.
Für positiv semidefinite (andere Bezeichnung: nichtnegativ definite)
Matrizen A ist es schon komplizierter, jedenfalls was die
Determinanten-Bedingung betrifft.
Die Implikation
"Eine Matrix A ist positiv definit"
=> "die genannten Hauptuntermatrizen haben alle nichtnegative
Determinanten"
ist einfach zu beweisen. Die Rückwärts-Richtung "<=" ist IMHO aber i.a.
falsch(!); es gibt einfache Gegenbeispiele.
Irgendwo habe ich mal gelesen, daß "<=" jedoch gilt, wenn man die
Determinanten-Aussage auf *alle* Hauptuntermatrizen ausdehnt, also nicht
nur diejenigen, bei denen genau "die ersten k Spalten und Zeilen vorkommen".
Der Beweis dafür ist mir aber nicht a priori klar; bzw. mir fällt
partout nicht ein, wie man das aus Satz [1] für positiv definite
Matrizen herleiten könnte.
Für dessen Beweis wird BTW das Schurkomplement benötigt; es geht mit
vollständiger Induktion.
"Wir nehmen an, daß A indefinit wäre, und zeigen, daß es dann eine
Hauptuntermatrix mit Determinante <0 gäbe..."
Argumentationen über die Eigenwerte bzw. Hauptachsentransformation
erscheinen auf den ersten Blick ebenfalls nicht zielführend.
Kennt jemand eine Lösung dieses Problems?
Das kann doch jedes Kind ganz einfach anhand der nach größe der reellen
Eigenwerten geordneten, diagonalisierten Matrizen einer
positiv-semidefiniten Matrix A beantworten.

Tritt ein nichttrivaler Kern der Dimension m>0 längs der Diagonale auf
sind alle Determinanten aller Hauptminoren positiv semidefinit davon
gibts es mit Wert 0

sum_k=0^n (n über k)

mit Determinante 0.

Das sind natürlich i.a. mehr als die n auf der aufsteigenden
Hauptdiagonalen, die bei dieser Ordnung alle 0 sind, während zB bei
umgekehrter Ordung (n-m) positiv und m 0 sind.

Bleibt der Fall der indefiniten Matrizen:
Die haben Hauptminoren mit Determinanten beider Vorzeichen.

Der Satz läßt sich auf die aufsteigende Schachtelung der Projektionen
auf der Diagonalen in einer gebenene Basis und Anordnung reduzieren,
wenn jede Projektion positiv ist.

Der allgemeine Fall ist die Zerlegung einer Abbildung A in ihen Kern,
positiven und negativen Teil als direkte Summe A_0 (+) A_+ (+) A_ über
der direkten Summe der Eigenräume V_0 (+) V_+ (+) V_-
--
Roland Franzius
Stephan Gerlach
2017-05-25 01:10:29 UTC
Antworten
Permalink
Raw Message
Post by Roland Franzius
Post by Stephan Gerlach
Im Folgenden betrachte ich nur reelle, symmetrische nxn-Matrizen.
(Mit komplexen Matrizen funktioniert das Ganze ähnlich.)
Jedes Kind kennt das Hauptminoren-Kriterium von Sylvester für positiv
Satz [1]
--------
Eine Matrix A ist positiv definit
<=> A hat nur positive Eigenwerte
<=> Die Determinanten derjenigen Haupt-Untermatrizen, die jeweils die
Spalten/Zeilen von 1 bis k enthalten, wobei k die Menge {1,...,n}
durchläuft, sind alle > 0.
JFTR: Daraus kann man leicht ein ähnliches Kriterium für negativ
definite Matrizen herleiten.
Für positiv semidefinite (andere Bezeichnung: nichtnegativ definite)
Matrizen A ist es schon komplizierter, jedenfalls was die
Determinanten-Bedingung betrifft.
Die Implikation
"Eine Matrix A ist positiv definit"
=> "die genannten Hauptuntermatrizen haben alle nichtnegative
Determinanten"
ist einfach zu beweisen. Die Rückwärts-Richtung "<=" ist IMHO aber i.a.
falsch(!); es gibt einfache Gegenbeispiele.
Irgendwo habe ich mal gelesen, daß "<=" jedoch gilt, wenn man die
Determinanten-Aussage auf *alle* Hauptuntermatrizen ausdehnt, also nicht
nur diejenigen, bei denen genau "die ersten k Spalten und Zeilen vorkommen".
Der Beweis dafür ist mir aber nicht a priori klar; bzw. mir fällt
partout nicht ein, wie man das aus Satz [1] für positiv definite
Matrizen herleiten könnte.
Für dessen Beweis wird BTW das Schurkomplement benötigt; es geht mit
vollständiger Induktion.
"Wir nehmen an, daß A indefinit wäre, und zeigen, daß es dann eine
Hauptuntermatrix mit Determinante <0 gäbe..."
Argumentationen über die Eigenwerte bzw. Hauptachsentransformation
erscheinen auf den ersten Blick ebenfalls nicht zielführend.
Kennt jemand eine Lösung dieses Problems?
Das kann doch jedes Kind ganz einfach anhand der nach größe der reellen
Eigenwerten geordneten, diagonalisierten Matrizen einer
positiv-semidefiniten Matrix A beantworten.
Du schreibst "... einer positiv-semidefiniten Matrix A..." und gehst
bereits davon als Voraussetzung aus?
Eigentlich wollte ich "positiv-semidefinit" erst zeigen...

Aber egal:

Was sind diese diagonalisierten Matrizen (im Plural!) einer Matrix A?

Ich kenne "nur" den Satz über die Hauptachsentransformation, der besagt,
daß man (unter anderem) eine positiv-semidefinite Matrix A darstellen
kann als

A = B * D * B^T.

D ist dabei die "diagonalisierte Matrix" (wenn man es so nennen will)
von A, die die Eigenwerte von A auf der Hauptdiagonale enthält; die
Eigenwerte können dabei der Größe nach sortiert werden. B enthält die
Eigenvektoren ("passend" zu den Eigenwerten in D sortiert) als Spalten.


Oder meinst du mit Matrizen (im Plural), daß man dies auf alle
Hauptuntermatrizen anwenden solle?
Wenn ja: Haben die Eigenwerte der Hauptuntermatrizen etwas mit den
Eigenwerten von A selbst zu tun? Das erscheint mir nicht a priori klar.
Post by Roland Franzius
Tritt ein nichttrivaler Kern der Dimension m>0 längs der Diagonale auf
Was genau ist gemeint mit "ein Kern tritt längs der Diagonale auf"?

Du meinst sicher
"tritt eine Hauptuntermatrix mit Determinante 0 auf, weswegen diese
Matrix einen Kern mit Dimension m>0 hat"?!
Post by Roland Franzius
sind alle Determinanten aller Hauptminoren positiv semidefinit...
Gemeint ist vermutlich "die Determinanten sind nichtnegativ"?
Positive Semidefinitheit ist im vorliegenden Fall eine Eigenschaft einer
Matrix.
Post by Roland Franzius
... davon
gibts es mit Wert 0
sum_k=0^n (n über k)
mit Determinante 0.
Wie kommt man auf diese Summenformel?
BTW: sum_k=0^n (n über k) = 2^n.
Post by Roland Franzius
Das sind natürlich i.a. mehr als die n auf der aufsteigenden
Hauptdiagonalen, die bei dieser Ordnung alle 0 sind, während zB bei
umgekehrter Ordung (n-m) positiv und m 0 sind.
Mir scheint "irgendwie", du gehst bereits von positiver-Semidefinitheit
von A aus. In diesem Fall ist mir aber ohnenin klar, wie man auf die
Nicht-Negativität der genannten Hauptminoren kommt:

1.) Mit dem Satz über die Hauptachsentransformation bekommt man leicht,
daß die Determinante einer positiv-semidefiniten Matrix nichtnegativ ist.

2.) Man zeigt, daß für beliebige Matrizen C passenden Formats C^T*A*C
positiv-semidefinit ist.

3.) Man zeigt durch spezielle Wahl von C in 2.), daß jede
Hauptuntermatrix von A positiv-semidefinit ist.

4.) Aus 3.) und 1.) folgert man die Nicht-Negativität einer jeden
Hauptuntermatrix von A.


Meine Frage bezog sich aber auf die umgekehrte Richtung:
Wie kommt man von
"alle Hauptminoren sind nichtnegativ" auf "A ist positiv semidefinit"?

Diese Implikation wird mir aus deinen Ausführungen leider nicht ganz klar.

Man muß ja letztenendes auf eine der beiden folgenden Aussagen kommen:

(i) Für alle x aus R^n gilt x^T*A*x >= 0.
oder
(ii) Alle Eigenwerte von A sind >= 0.

(i) ist die Definition von "positiv-semidefinit"; (ii) ist eine
äquivalente Aussage.


Der Beweis kann IMHO auch nicht ganz einfach sein; denn bereits für den
positiv-definiten Fall (ohne "semi") benutzt man Aussagen über das
Schurkomplement; der Beweis geht über vollständige Induktion.
Allerdings braucht man für diesen Beweis nur die schwächere Aussage
"all diejenigen Hauptminoren mit Spalten/Zeilen [von 1 bis k], wobei k
eine Zahl aus {1,...,n} ist, sind positiv",
d.h. es werden nur *spezielle* Hauptminoren benötigt.

Evtl. kommt man bei Benutzung *aller* Hauptminoren auch ohne
Schurkomplement aus.
Post by Roland Franzius
Die haben Hauptminoren mit Determinanten beider Vorzeichen.
Wenn(!) die Implikation

"alle Hauptminoren sind nichtnegativ" => "A ist positiv semidefinit"

gilt, ist diese Aussage über die indefiniten Matrizen tatsächlich
relativ einfach zu begründen.

Per Definiton heißt "A ist indefinit":

Es gibt Vektoren x und y aus dem R^n mit
x^T*A*x > 0 und y^T*A*y < 0.
Post by Roland Franzius
Der Satz läßt sich auf die aufsteigende Schachtelung der Projektionen
auf der Diagonalen in einer gebenene Basis und Anordnung reduzieren,
wenn jede Projektion positiv ist.
Der allgemeine Fall ist die Zerlegung einer Abbildung A in ihen Kern,
positiven und negativen Teil als direkte Summe A_0 (+) A_+ (+) A_ über
der direkten Summe der Eigenräume V_0 (+) V_+ (+) V_-
--
Post by Roland Franzius
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Roland Franzius
2017-05-27 05:25:48 UTC
Antworten
Permalink
Raw Message
Post by Stephan Gerlach
Post by Roland Franzius
Post by Stephan Gerlach
Im Folgenden betrachte ich nur reelle, symmetrische nxn-Matrizen.
(Mit komplexen Matrizen funktioniert das Ganze ähnlich.)
Jedes Kind kennt das Hauptminoren-Kriterium von Sylvester für positiv
Satz [1]
--------
Eine Matrix A ist positiv definit
<=> A hat nur positive Eigenwerte
<=> Die Determinanten derjenigen Haupt-Untermatrizen, die jeweils die
Spalten/Zeilen von 1 bis k enthalten, wobei k die Menge {1,...,n}
durchläuft, sind alle > 0.
JFTR: Daraus kann man leicht ein ähnliches Kriterium für negativ
definite Matrizen herleiten.
Für positiv semidefinite (andere Bezeichnung: nichtnegativ definite)
Matrizen A ist es schon komplizierter, jedenfalls was die
Determinanten-Bedingung betrifft.
Die Implikation
"Eine Matrix A ist positiv definit"
=> "die genannten Hauptuntermatrizen haben alle nichtnegative Determinanten"
ist einfach zu beweisen. Die Rückwärts-Richtung "<=" ist IMHO aber i.a.
falsch(!); es gibt einfache Gegenbeispiele.
Irgendwo habe ich mal gelesen, daß "<=" jedoch gilt, wenn man die
Determinanten-Aussage auf *alle* Hauptuntermatrizen ausdehnt, also nicht
nur diejenigen, bei denen genau "die ersten k Spalten und Zeilen vorkommen".
Das ist wohl richtig, jedenfalls hats der Wiki-Autor auch schon gesehen

https://de.wikipedia.org/wiki/Definitheit
Post by Stephan Gerlach
Post by Roland Franzius
Post by Stephan Gerlach
Der Beweis dafür ist mir aber nicht a priori klar; bzw. mir fällt
partout nicht ein, wie man das aus Satz [1] für positiv definite
Matrizen herleiten könnte.
Für dessen Beweis wird BTW das Schurkomplement benötigt; es geht mit
vollständiger Induktion.
"Wir nehmen an, daß A indefinit wäre, und zeigen, daß es dann eine
Hauptuntermatrix mit Determinante <0 gäbe..."
Argumentationen über die Eigenwerte bzw. Hauptachsentransformation
erscheinen auf den ersten Blick ebenfalls nicht zielführend.
Kennt jemand eine Lösung dieses Problems?
Dieser Einleitungssatz bezieht sich auf die Kinderei von oben. Die
Methodik der Spektralradiusabschätzungen linearer symmetrischer
Abbildungen ist ein wenig bekanntes Spezialgebiet zB der
Wahrscheinlichkeits- und Quantentheorie.
Post by Stephan Gerlach
Post by Roland Franzius
Das kann doch jedes Kind ganz einfach anhand der nach größe der
reellen Eigenwerten geordneten, diagonalisierten Matrizen einer
positiv-semidefiniten Matrix A beantworten.
Du schreibst "... einer positiv-semidefiniten Matrix A..." und gehst
bereits davon als Voraussetzung aus?
Eigentlich wollte ich "positiv-semidefinit" erst zeigen...
Was sind diese diagonalisierten Matrizen (im Plural!) einer Matrix A?
Jede symmetrische Matrix ist unter der orthogonalen Gruppe äquivalent
zur Klasse der Diagonalmatrizen modulo der orthogonalen Untergruppe der
Basispermutationen. Daraus ergibt sich, dass die Abgrenzung der
positiv-semidefiniten Matrizenklasse gegen die indefinite für beliebige
Diagonalmatrizen nur durch Prüfung "alle a_ii>=0" möglich ist, nicht
durch die Folge der Produkte von oben links wie bei positiv definiten.

Da ein indefinites Eigenwertpaar durch Basispermutation auf die Ecken
eines beliebiegen, zur Diagonalen symmetrischen Quadrats transformiert
werden kann, liegt es nahe, Den Satz aller solche Determinanten als
Indikatorfunktion für Indefinitheit zu benutzen.

Der Beweis, dass jede indefinite Matrix mindestens einen Hauptminor mit
negativer Determinante besitzt, überlassen wir dem Leser.
--
Roland Franzius
Stephan Gerlach
2017-06-07 00:03:52 UTC
Antworten
Permalink
Raw Message
Post by Roland Franzius
Post by Stephan Gerlach
Post by Roland Franzius
Post by Stephan Gerlach
Im Folgenden betrachte ich nur reelle, symmetrische nxn-Matrizen.
(Mit komplexen Matrizen funktioniert das Ganze ähnlich.)
Jedes Kind kennt das Hauptminoren-Kriterium von Sylvester für positiv
Satz [1]
--------
Eine Matrix A ist positiv definit
<=> A hat nur positive Eigenwerte
<=> Die Determinanten derjenigen Haupt-Untermatrizen, die jeweils die
Spalten/Zeilen von 1 bis k enthalten, wobei k die Menge {1,...,n}
durchläuft, sind alle > 0.
JFTR: Daraus kann man leicht ein ähnliches Kriterium für negativ
definite Matrizen herleiten.
Für positiv semidefinite (andere Bezeichnung: nichtnegativ definite)
Matrizen A ist es schon komplizierter, jedenfalls was die
Determinanten-Bedingung betrifft.
Die Implikation
"Eine Matrix A ist positiv definit"
=> "die genannten Hauptuntermatrizen haben alle nichtnegative Determinanten"
ist einfach zu beweisen. Die Rückwärts-Richtung "<=" ist IMHO aber i.a.
falsch(!); es gibt einfache Gegenbeispiele.
Irgendwo habe ich mal gelesen, daß "<=" jedoch gilt, wenn man die
Determinanten-Aussage auf *alle* Hauptuntermatrizen ausdehnt, also nicht
nur diejenigen, bei denen genau "die ersten k Spalten und Zeilen vorkommen".
Das ist wohl richtig, jedenfalls hats der Wiki-Autor auch schon gesehen
https://de.wikipedia.org/wiki/Definitheit
Eine Begründung steht aber nicht dabei.
Ist wohl nicht ganz trivial.
Post by Roland Franzius
Post by Stephan Gerlach
Post by Roland Franzius
Post by Stephan Gerlach
Der Beweis dafür ist mir aber nicht a priori klar; bzw. mir fällt
partout nicht ein, wie man das aus Satz [1] für positiv definite
Matrizen herleiten könnte.
Für dessen Beweis wird BTW das Schurkomplement benötigt; es geht mit
vollständiger Induktion.
"Wir nehmen an, daß A indefinit wäre, und zeigen, daß es dann eine
Hauptuntermatrix mit Determinante <0 gäbe..."
Argumentationen über die Eigenwerte bzw. Hauptachsentransformation
erscheinen auf den ersten Blick ebenfalls nicht zielführend.
Kennt jemand eine Lösung dieses Problems?
Dieser Einleitungssatz bezieht sich auf die Kinderei von oben. Die
Methodik der Spektralradiusabschätzungen linearer symmetrischer
Abbildungen ist ein wenig bekanntes Spezialgebiet zB der
Wahrscheinlichkeits- und Quantentheorie.
Ja, und zudem dürfte der Zusammenhang zu den Hauptminoren sowie
insbesondere deren Vorzeichen schwierig herzustellen sein.
Post by Roland Franzius
Post by Stephan Gerlach
Post by Roland Franzius
Das kann doch jedes Kind ganz einfach anhand der nach größe der
reellen Eigenwerten geordneten, diagonalisierten Matrizen einer
positiv-semidefiniten Matrix A beantworten.
Du schreibst "... einer positiv-semidefiniten Matrix A..." und gehst
bereits davon als Voraussetzung aus?
Eigentlich wollte ich "positiv-semidefinit" erst zeigen...
Was sind diese diagonalisierten Matrizen (im Plural!) einer Matrix A?
Jede symmetrische Matrix ist unter der orthogonalen Gruppe äquivalent
zur Klasse der Diagonalmatrizen modulo der orthogonalen Untergruppe der
Basispermutationen. Daraus ergibt sich, dass die Abgrenzung der
positiv-semidefiniten Matrizenklasse gegen die indefinite für beliebige
Diagonalmatrizen nur durch Prüfung "alle a_ii>=0" möglich ist, nicht
durch die Folge der Produkte von oben links wie bei positiv definiten.
Ja, bei Diagonalmatrizen ist das ziemlich einleuchtend.
Post by Roland Franzius
Da ein indefinites Eigenwertpaar durch Basispermutation auf die Ecken
eines beliebiegen, zur Diagonalen symmetrischen Quadrats transformiert
werden kann, liegt es nahe, Den Satz aller solche Determinanten als
Indikatorfunktion für Indefinitheit zu benutzen.
Der Beweis, dass jede indefinite Matrix mindestens einen Hauptminor mit
negativer Determinante besitzt, überlassen wir dem Leser.
Selbst jede negativ(!) definite Matrix besitzt einen Hauptminor mit
negativer Determinante. Genaugenommen sind im negativ defninten Fall
alle Hauptminoren mit ungerader Spalten-/Zeilenzahl negativ.

D.h. es müßte im indefiniten Fall wohl eher heißen
"... Beweis, daß jede indefinite Matrix mindestens einen Hauptminor mit
gerader Spalten-/Zeilen-Anzahl mit negativer Determinante besitzt..."
[#]

Ich glaube aber mittlerweilse, es ist einfacher, den positiv
semidifiniten Fall (der aus "alle Hauptminoren nichtnegativ" gezeigt
werden soll) auf den positiv definiten Fall zurückzuführen. Die Details
sind allerdings IMHO nicht offensichtlich.
Bei Bedarf kann ich das hier mal aufschreiben (bzw. skizzieren); auf den
ersten Blick finde ich keinen "Fallstrick" dabei.
Hinweis: Man braucht für diesen Beweis tatsächlich *alle* Hauptminoren.
Weitere Stichworte für die Beweis-Skizze:
Polynom, differenzienen, Koeffizienten, Grenzwert.
Evtl. ist dem ein oder anderen damit bereits klar, wie dieser Beweis geht...

Die obige Aussage [#] für indefinite Matrizen ist dann eine relativ
einfache Folgerung aus den anderen "Definitheits-Arten".
--
Post by Roland Franzius
Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Loading...