如我之前提的, A= 0 B B^T 0 這邊 B 是方陣. 若 t 為 A 的 eigenvalue 且 v 為相對於 t 的 eigenvector, 即 Av=tv. write v= (x,y)^T, 則 tv = Av = (By,B^Tx)^T. 故 By=tx, B^Tx=ty. 令 v'=(x,-y)^T, 則 Av'=(B(-y),B^Tx)^T=(-tx,ty)^T=-tv'.
所以 -t 是 A 的 eigenvalue. 因為 m 個線性獨立的 eigenvector w.r.t t 可以產生 m 個線性獨立的 eigenvector w.r.t. -t. 所以重數會一樣.
16 則留言:
加一些 isolated vertices 使得兩個 partite sets 一樣大, 考慮其 adjacencey matrix A 會長得像
0 B
B^T 0
然後分析 eigenvector and eigenvalue 就行了.
設 G=(V1∪V2,E) 為 bipartite graph
|V1|=k, |V2|=n-k, 對 V1 的點編號v_1,...,v_k,
V2的編v_(k+1),...,v_n, 則adjacency matrix A =
[0 M]
[M^T 0], 其中 M 為 k x (n-k) 的矩陣
若編號方式不同所產生的矩陣都會相似於A,
則特徵多項式都會相同, 因此僅考慮A:
若對 A-xI 的前 k 列都乘上-1倍, 會得到
[xI -M]
[M^T -xI]
再對後 n-k 行個乘上-1倍, 會得到
[xI M]
[M^T xI]
=> det(A-(-x)I) = [(-1)^n]det(A-xI) = 0
想請問一下為什麼編號方式不同的矩陣都會相似於A?
0080404199謝謝兩位替我的解答...我有一個想法..若t為A之eigenvalue..要如何證出-t也為A之eigenvalue..然後我在假設他們的蟲數不一樣正矛盾..但要怎麼證出-t也為A之eigenvalue
因為相似就是基底變換...而且p^-1 事實上就是P^t..因為它是排列矩陣
wynne 的證明有點問題, 如果 M 不是方陣, 當你在做 -xI 的時候, A-xI 不會剛好長得像你寫的那樣, 而且如果這個證明成立的話, 那麼所有長得像
0 M
M^T 0
的矩陣都擁有 ±λ 為其 eigenvalue, 似乎不太正確.
如我之前提的, A=
0 B
B^T 0
這邊 B 是方陣. 若 t 為 A 的 eigenvalue 且 v 為相對於 t 的 eigenvector, 即 Av=tv. write v= (x,y)^T, 則
tv = Av = (By,B^Tx)^T. 故 By=tx, B^Tx=ty. 令 v'=(x,-y)^T, 則
Av'=(B(-y),B^Tx)^T=(-tx,ty)^T=-tv'.
所以 -t 是 A 的 eigenvalue. 因為 m 個線性獨立的 eigenvector w.r.t t 可以產生 m 個線性獨立的 eigenvector w.r.t. -t. 所以重數會一樣.
ps. 因為行向量方式不好表達, 所以寫成 ( , )^T.
M 不用是方陣, 只要整個矩陣是方陣, 還有左上角和右下角的零矩陣都是方陣就可以了, 而這的確也證明了的確所有長的像
[0 M]
[M^T 0]
的矩陣都擁有 ±λ 為其 eigenvalue (且左下方的矩陣也不必要是 M 的transpose)
對, wynne 說的沒錯. 左上及右下的 block 皆為方陣, 所以 A-xI 就是長那樣子.
想了一下沒想出怎麼用這個證明證重數部份, 有想法嗎？
反證法..假設存在一EIGENVALUE t重數為m但-t這個eigenvalue重數不為m證矛盾.. 我沒想錯應該是跟trace產生矛盾
還有一個想法因為t之重數為m,故(x-t)^m可整除特徵多項式p(x)..現在已證出-t也為他的一個eigenvalue..則只要證出(x+t)^m也可整除p(x),但(x+t)^(m+1)無法整除p(x)
這兩個想法 我想都不 work.
我trace的想法有錯..因為可能存在若干個eigenvalue t與-t 重數不同使得trace of A 為0
我最後寫的那個式子隱含了重數相等的結果, 因為 det(A-xI) 和 det(A-(-x)I) 解出來的 eigenvalue事實上只差個負號而已, 再加上det(A+xI) 和 det(A-xI)只差常數倍, 因此他們會具有完全相同的根(且根的重數也相同), 所以
若 det(A-xI) 有 m 個 t, n 個 -t
=> det(A+xI) 有 m 個 -t, n 個 t
=> m=n
嗯 我覺得應該對.
其實還可以利用基底..就像凱那樣..給一個t的特徵向量.可以造依個-t的特徵向量..所以從基底出發造出m個線性獨立的eigenvector..在著手驗證他是maximal linearly independent set 即可..或是說造依個線性映射 T: V(t)->v(-t)by T(X Y)^t=(X -Y)^t 然後證明1-1 and onto 則就可以知道他們維度相同..或是利用排列群也做的出來(很難做而已.)
忘了說明他是對稱矩陣所以可以對角化.故只藥考慮eigenspace 即可
張貼留言