Finden der Quadratwurzel einer Laplace-Matrix

11

Angenommen, die folgende Matrix ist mit ihrer Transponierten . Das Produkt ergibt ,[ 0,500 - 0,333 - 0,167 - 0,500 0,667 - 0,167 - 0,500 - 0,333 0,833 ] A T A T A = G [ 0,750 - 0,334 - 0,417 - 0,334 0,667 - 0,333 - 0,417 - 0,333 0,750 ]A

[0.5000.3330.1670.5000.6670.1670.5000.3330.833]
ATATA=G
[0.7500.3340.4170.3340.6670.3330.4170.3330.750]

wobei eine Laplace-Matrix ist . Es ist zu beachten, dass die Matrizen und Rang 2 haben, wobei der Null-Eigenwert dem Eigenvektor .GG 1 n = [ 1 1 1 ] T.AG1n=[111]T

Ich frage mich, wie man erhält, wenn nur gegeben wird. Ich habe versucht, die Eigenzusammensetzung , und dann , aber ein anderes Ergebnis erhalten. Ich denke, das hat mit Rangmangel zu tun. Könnte jemand das erklären? Das obige Beispiel dient eindeutig der Veranschaulichung. Sie könnten eine allgemeine Laplace-Matrix-Zerlegung der obigen Form in Betracht ziehen.G G = U E U T A ' = U E 1 / 2AGG=UEUTA=UE1/2


Da zum Beispiel die Cholesky-Zersetzung verwendet werden könnte, um , könnte die Zersetzung auf viele Lösungen ergeben. Ich interessiere mich für die Lösung, die ausgedrückt werden kann als wobei eine Identitätsmatrix ist, und ein Vektor ist Erfüllung von . Wenn es die Sache vereinfacht, können Sie annehmen, dass die Einträge von nicht negativ sind.G=LLTA = ( I - 1 n w T ) , I 3 × 3 1 n = [ 1 1 1 ] w w T 1 n = 1 wG

A=(I1nwT),
I3×31n=[1 1 1]wwT1n=1w
usero
quelle
Ich denke, der Kommentar, den Sie zur Darstellung von hinzugefügt haben, ist nur teilweise hilfreich. Es wird davon ausgegangen, dass es genau einen Eigenwert gibt, der gleich Null ist, aber die Nichtdeterminanz ist immer da, nicht wahr? A
Wolfgang Bangerth
@ WolfgangBangerth Ich versuche die Bedeutung von "Nicht-Determinanz" herauszufinden. Wenn das , gilt dies für das obige Beispiel, und ich bin nicht sicher, ob es für verallgemeinert werden kann . Mit Ausnahme von bezweifle ich jedoch, dass die Lösung immer existieren würde. A = I - 1 n w T n = 3det(A)=0A=I1nwTn=3
Usero
Nein, ich meinte damit, dass die Lösung Ihres Problems nicht eindeutig festgelegt ist. Ich habe darauf hingewiesen, dass die Tatsache, dass die Matrix einen Null-Eigenwert hat oder nicht, nichts an der Tatsache ändert, dass das Quadratwurzelproblem keine eindeutige Lösung hat.
Wolfgang Bangerth

Antworten:

11

Wir haben die Laplace-Matrix die eine Menge von Eigenwerten λ 0λ 1λ n für G R n × n hat, wobei wir immer λ 0 = 0 kennen . Somit ist die Laplace-Matrix immer symmetrisch positiv semidefinit. Weil die Matrix G.G=ATAλ0λ1λnGRn×nλ0=0Gist nicht symmetrisch positiv definitiv müssen wir vorsichtig sein, wenn wir die Cholesky-Zerlegung diskutieren. Die Cholesky-Zerlegung existiert für eine positive semidefinitive Matrix, ist jedoch nicht mehr eindeutig. Zum Beispiel ist die positive semidefinitive Matrix Unendlich viele Cholesky Zerlegungen A= [

A=[0001],
A=[0001]=[00sinθcosθ][0sinθ0cosθ]=LLT.

Da wir jedoch eine Matrix , von der bekannt ist, dass sie eine Laplace-Matrix ist, können wir die komplexeren linearen Algebra-Werkzeuge wie Cholesky-Zerlegungen oder das Finden der Quadratwurzel der positiven semidefinitiven Matrix G vermeiden, so dass wir A wiederherstellen . Wenn wir zum Beispiel die Laplace-Matrix G R 4 × 4 haben , ist G = [GGAGR4×4 wir die Graphentheorie verwenden, um die gewünschte MatrixAwiederherzustellen. Dazu formulieren wir die orientierte Inzidenzmatrix. Wenn wir die Anzahl der Kanten im Graphen alsmund die Anzahl der Eckpunkte alsn definieren,ist die orientierte InzidenzmatrixAeinem×n-Matrix, die durch A e v = { 1 gegeben ist, wenn  e = ( v , w )  und  v < w - 1, wenn  e = ( v , w )

G=[3111110010101001]
AmnAm×n wobeie=(v,w)die Kante bezeichnet, die die Eckpunktevundw verbindet. Wenn wir einen Graphen fürGmit vier Eckpunkten und drei Kanten nehmen, haben wir die orientierte Inzidenzmatrix A=[
Aev={1if e=(v,w) and v<w1if e=(v,w) and v>w0otherwise,
e=(v,w)vwG Und wir können feststellendassG= A T A. Für das von Ihnen beschriebene Matrixproblem würden Sie ein Diagramm fürGmit der gleichen Anzahl von Kanten wie Eckpunkte erstellen. Dann sollten Sie die Möglichkeit haben, die MatrixAzu rekonstruieren,wenn Sie nur die Laplace-MatrixG erhalten.
A=[110010101001],
G=ATAGAG

Aktualisieren:

Wenn wir die Diagonalmatrix der Scheitelpunktgrade eines Graphen als und die Adjazenzmatrix des Graphen als M definieren , wird die Laplace-Matrix G des Graphen durch G = N - M definiert . Zum Beispiel in der folgenden GrafikNMGG=NM

G=[3000010000100001][0111100010001000].
GAA
Aev={1if e=(v,w) and v<w1if e=(v,w) and v>w0otherwise,.
e1v1v2Ae1,v1v1v2v<wAevAe1,v1=1Ae1,v2=1A
A=v1v2v3v4e11100e21010e31001.

GrVE

w:V×VR+,
uvw(u,v)uVu
du=vVw(u,v).
GrAd(Gr)n×nVw(u,v)D(Gr)VG
G=D(Gr)Ad(Gr).

G=[34135121323135121334].
GG=ATAAA=I1nwTwT1n=1AAAd(Gr)G
G=[5400010001112][12135121313135121316]=D(Gr)Ad(Gr).

v1v2v31/21/31/6w[12 13 16]TA
A=I1nwT=[121316122316121356].

A

Andrew Winters
quelle
AGO(n2)G
GG
AG
AG
1
GA=I1nwTGG=ATA=(I1nwT)T(I1nwT)
9

AB

B2=A,

C

CHC=A,

CQCQ

Schließlich kann man die eindeutige Matrixquadratwurzel einer hermitisch positiven semidefiniten Matrix konstruktiv definieren, beispielsweise durch ihre Eigenwertzerlegung

A=UΛUH,

UΛA

B=UΛUH.
Jack Poulson
quelle
A
6

G=ATA.
GGG=LTLA=LAGWenn Sie eine bestimmte haben möchten, müssen Sie die Frage so umformulieren, dass Sie die strukturellen Eigenschaften des "Zweigs" der Quadratwurzel angeben, an dem Sie interessiert sind.

Ich würde sagen, dass diese Situation nicht unähnlich ist, die Quadratwurzel unter den reellen Zahlen unter Verwendung der komplexen Zahlen zu ziehen: Auch dort haben Sie im Allgemeinen zwei Wurzeln, und Sie müssen sagen, welche Sie die Antwort eindeutig machen möchten.

Wolfgang Bangerth
quelle
Du hast definitiv recht. Ein anderer Weg wäre der spektrale Zerlegungsansatz, wie ich oben dargelegt habe. Ich habe eine Bearbeitung vorgenommen, um die Lösung einzigartig zu machen. Hoffentlich wird es die Sache nicht komplizieren.
Usero
Gibt es immer eine Lösung mit der oben angegebenen Einschränkung? Vielleicht gilt es nur für einige Fälle und nicht allgemein.
Usero
Tatsächlich funktioniert Cholesky in seinem Fall nicht, da es (im Wesentlichen) erfordert, dass die Matrix hermitisch positiv-definit ist.
Jack Poulson
4

LDLTD^=DG=LD^

Willowbrook
quelle
LDLT
1
@JackPoulson Ich versuche eine singuläre Matrix A in Matlab und führe ldl aus, es funktioniert. Die Null-Eigenwerte entsprechen den Nullen in der Diagonale von D.
Willowbrook
2
LDLTPAP=LDLTD2×2