Re: [線代] 證明一個矩陣nonsingular
※ 引述《ohyesiamhone (3.14159265358979)》之銘言：
: let A be a 2n*2n matrix
: with zeros diagonal and +-1 everywhere else.
: Prove that A is nonsingular.
: 請教各位數學前輩此題證法
: 有看過類似的題目在非主對角線全為1
: 但這題是正負1
: 不知道怎麼假設才可以不失其一般性
關鍵就是a大說的觀察A^2囉
【解法一】
0 , i=j
寫出 A = {a_ij} =
1 or -1 , i≠j
odd , i=j
則 C := A^2 = {c_ij} =
even , i≠j
再來用公式降階展開第一列(行也可)計算
2n
det(C) = Σ (-1)^(i+1) * c_1i * M_1i , M_ij是c_ij的minor
i=1
其中 M_ij是c_ij的minor, 就是砍掉以c_ij為中心的十字延伸後所形成的矩陣之行列式
這i=2~2n共2n-1項，每一項的c_1i都是偶數，所以這2n-1項加起來都是偶數
所以det(C)的奇偶取決於c_11 * M_11, where c_11 is odd
所以 det(C) = 奇*D_(2n-1) + 偶，D_(2n-1) := M_11
而M_11這個(2n-1)X(2n-1)的矩陣的行列式又再降階展開一次變成奇*D_(2n-2) + 偶
因此 det(C) = 奇(奇*D_(2n-2)+偶)+偶
= 奇*D_(2n-2) + 偶
一直做下去會變成 det(C) = 奇*D_1 + 偶, D_1=a_2n2n = 奇
所以答案變成 det(C) = 奇 + 偶 = 奇 = det(A)^2
因此det(A)不可能是0，nonsingular
【解法二】(a大說的F_2代數法)
如果你學過代數，那我接下來說的就不陌生，僅列出而已
令p為質數，在整數上定義一個關係"~" 如下：
a,b為兩整數，定義a~b(a與b有關係) if a=b+kp, k€Z
則可以驗證這個關係為等價關係：
(1) a~a
(2) if a~b then b~a
(3) if a~b,b~c then a~c
接著對每個整數a，都可以定義bracket [] 如下：
[a] := {b€Z：b~a} 即收集那一些與a有關係的整數們形成一個整數的子集合
則可以驗證
(1) [a] = [b] if and only if a~b
(2) 任何整數a一定在[0],[1],...,[p-1]這p個集合其中一個
(3) [0],[1],...,[p-1] 這p個集合兩兩互不相交，形成整數的一組不互交的分割
再來，考慮這些[a]成的集合為 F_p := {[a]:a€Z}
( 這個集合不難從以上性質看出共有p個元素 F_p = {[0],[1],...,[p-1]} )
接著在F_p定義兩個運算：加┼ 乘╳
[a]┼[b]:= [a+b] (後者為整數相加)
[a]╳[b]:= [a*b] (後者為整數相乘)
再來需要驗證這兩個運算是良好定義well-defined (因為運算是一種二元函數)：
if [a]=[a'], [b]=[b']
then (1) [a]┼[b] = [a']┼[b']
(2) [a]╳[b] = [a']╳[b']
這個驗證是要確保在同一個bracket中，不論你拿誰當替死鬼來算，都是一樣結果
最後，就可以驗證（F_p,┼,╳）會形成一個體(field)，即是交換可除環
而注意到三件事：
(1) 矩陣裡面的元素通常看到實數或是複數，但廣義而言他可以是任何體的元素
(2) F_p可以只寫成{0,1,...,p-1}，因為你知我知大家知，你的1=[1]
所以0=p也是對的，因為他就是[0]=[p]
(3) p=2時，F_2 = {[0],[1]}，其實[0]就是偶數、[1]就是奇數
-----------------------------------------------------------------
代數完畢，回到這題a大說用F_2的作法的詳細解釋如下：
0 , i=j
寫出 A = {a_ij} =
1 or -1 , i≠j
定義 B = {b_ij} = {[a_ij]}
則B就是entry為F_2的元素所形成的矩陣
接著注意到[1]=[-1]
[0] , i=j
所以 B =
[1] , i≠j
[1] , i=j
則經由計算 B^2 = I :=
[0] , i≠j
因此 det(B)^2 = det(B^2) = det(I) = [1]
所以 det(B) = [1]
最後就是要找 det (A) 與 det (B) 的關係
從 (1) bracket的加與乘的運算可以往內搬變成該bracket的代表的整數運算
(2) 行列式為entry的互相乘積的線性組合
我們可以發現 [det (A)] = det (B)
因此 [det (A)] = [1]
所以 det(A) ≠ 0
--------------------------
其實這兩種方法是等價的，只是odd=[1], even=[0]
乍看之下若不要那麼多解釋，後者比前者快很多
若沒有體觀念的最好先了解一下再用【解法二】
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.255.237.196
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1507815129.A.213.html
※ 編輯: znmkhxrw (111.255.237.196), 10/12/2017 21:34:45
推
10/12 23:26,
8年前
, 1F
10/12 23:26, 1F
推
10/12 23:54,
8年前
, 2F
10/12 23:54, 2F
推
10/13 12:08,
8年前
, 3F
10/13 12:08, 3F
a大跟H大應該是指：
定義【a】:= a (mod2) €{0,1}
然後check 【a+b】=【【a】+【b】】
【ab】=【【a】【b】】
就不用花大篇幅去說明F_2是體吧??
我會說明F_2是體主要是線代一開始的general setting 是vector space over field
所以文中的 B = {b_ij} , b_ij=[a_ij]€F_2, B矩陣自然適用任何線代理論
你們的意思是不是單純定義 E = {e_ij}, e_ij=【a_ij】€{0,1} (因此 E€M_2n(R) )
最後藉由 (1) E^2 = I
(2) 【det(A)】 = det(E)
就可以得到結果
不需要F_2是field的論證
推
10/13 17:36,
8年前
, 4F
10/13 17:36, 4F
→
10/13 19:06,
8年前
, 5F
10/13 19:06, 5F
我是直接把E€M_2n(R)耶 這樣就不用引進環體了
而【a】€{0,1} 中的這個0,1，完全是R裡面的0,1
所以我在運算上才寫兩次括號 【a+b】=【【a】+【b】】
這樣就不用環與體 只接把看成E€M_2n(R) 就去做就好了
※ 編輯: znmkhxrw (111.255.237.196), 10/13/2017 20:13:26
推
10/14 03:00,
8年前
, 6F
10/14 03:00, 6F
推
10/14 03:02,
8年前
, 7F
10/14 03:02, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：