Menemukan akar kuadrat dari matriks Laplacian

11

Misalkan matriks berikut diberikan [ 0.500 - 0,333 - 0,167 - 0.500 ,667 - 0,167 - 0.500 - 0,333 0,833 ] dengan transposnya A T . Produk A T A = G menghasilkan [ 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]

di mana adalah matriks Laplacian . Perhatikan bahwa matriks A dan G adalah peringkat 2, dengan nol eigenvalue sesuai dengan vektor eigen 1 n = [ 1 1 1 ] T .GAG1n=[111]T

Saya bertanya-tanya apa yang akan menjadi cara untuk mendapatkan jika hanya G yang diberikan. Saya mencoba eigendecomposition G = U E U T , dan kemudian menetapkan A ' = U E 1 / 2 , tetapi diperoleh hasil yang berbeda. Saya kira ini ada hubungannya dengan defisiensi peringkat. Bisakah seseorang menjelaskan ini? Jelas, contoh di atas adalah untuk ilustrasi; Anda dapat mempertimbangkan dekomposisi matriks Laplacian umum dari formulir di atas.AGG=UEUTA=UE1/2


Karena, misalnya, dekomposisi Cholesky dapat digunakan untuk menemukan , dekomposisi pada G dapat menghasilkan banyak solusi. Saya tertarik pada solusi yang dapat dinyatakan sebagai A = ( I - 1 n w T ) , di mana saya adalah 3 × 3 matriks identitas, 1 n = [ 1 1 1 ] , dan w menjadi beberapa vektor memuaskan w T 1 n = 1G=LLTG

A=(I1nwT),
I3×31n=[1 1 1]wwT1n=1. Jika ini menyederhanakan masalah, Anda dapat mengasumsikan bahwa entri tidak negatif.w
usero
sumber
Saya pikir komentar yang Anda tambahkan tentang representasi hanya membantu sebagian. Ini mengasumsikan bahwa hanya ada satu nilai eigen yang sama dengan nol, tetapi non-determinasi selalu ada, bukan? A
Wolfgang Bangerth
@ WolfgangBangerth Saya mencoba untuk mencari tahu arti dari "non-determinancy". Jika itu , itu berlaku untuk contoh di atas, dan aku tidak yakin apakah itu dapat digeneralisasi untuk A = I - 1 n w T . Namun, kecuali untuk n = 3 , saya ragu bahwa solusinya akan selalu ada. det(A)=0A=I1nwTn=3
usero
Tidak, yang saya maksudkan adalah bahwa solusi untuk masalah Anda tidak ditentukan secara unik. Saya menunjukkan fakta bahwa apakah matriks memiliki nilai eigen nol atau tidak tidak benar-benar mengubah fakta bahwa masalah akar kuadrat tidak memiliki solusi unik.
Wolfgang Bangerth

Jawaban:

11

G=ATAλ0λ1λnGRn×nλ0=0G

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

GGAGR4×4

G=[3111110010101001]
AmnAm×n
Aev={1if e=(v,w) and v<w1if e=(v,w) and v>w0otherwise,
e=(v,w)vwG
A=[110010101001],
G=ATAGAG

Memperbarui:

NMGG=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
sumber
AGO(n2)G
GG
AG
AG
1
GA=I1nwTGG=ATA=(I1nwT)T(I1nwT)
9

AB

B2=A,

C

CHC=A,

CQCQ

Terakhir, seseorang dapat secara konstruktif mendefinisikan akar kuadrat matriks unik dari matriks semi-pasti positif Hermitian melalui dekomposisi nilai eigennya, katakanlah

A=UΛUH,

UΛA

B=UΛUH.
Jack Poulson
sumber
A
6

G=ATA.
GGG=LTLA=LAG, dan jika Anda ingin memiliki satu, Anda perlu menyusun ulang pertanyaan sedemikian rupa sehingga Anda menentukan properti struktural dari "cabang" dari akar kuadrat yang Anda minati.

Saya akan mengatakan bahwa situasi ini tidak berbeda dengan mengambil akar kuadrat di antara bilangan real menggunakan bilangan kompleks: di sana, secara umum Anda memiliki dua akar, dan Anda harus mengatakan yang mana yang Anda ingin jadikan jawabannya unik.

Wolfgang Bangerth
sumber
Anda pasti benar. Cara lain adalah pendekatan dekomposisi spektral seperti yang saya nyatakan di atas. Saya telah mengedit agar solusinya unik. Semoga itu tidak memperumit masalah.
usero
Apakah solusi dengan kendala yang saya berikan di atas selalu ada? Mungkin hanya berlaku untuk beberapa kasus, dan tidak secara umum.
usero
Sebenarnya, Cholesky tidak bekerja dalam kasusnya, karena (pada dasarnya) mensyaratkan bahwa matriksnya adalah Hermitian positive-definit.
Jack Poulson
4

LDLTD^=DG=LD^

Willowbrook
sumber
LDLT
1
@JackPoulson Saya mencoba matriks A tunggal di matlab, dan menjalankan LDL, ia bekerja. Nilai nol eigen sesuai dengan nol di diagonal D.
Willowbrook
2
LDLTPAP=LDLTD2×2