Research Space for Linear Algebra & Discrete Mathematics
17. 這題其實在書上有出現過, 不過我發現他題目中的ideal和書上定義的不太一樣, 如果照他的假設:(1) 假設 0∈I, 因為 for all x in R, -x 存在 => 0-(-x)=x∈I => I=R(2) 若存在 a!=0 屬於 I, 因為(R,+,˙)為field, 所以a^-1存在 => 1=a(a^-1)∈I 則 for all x∈R, 因為 1∈I=> x=1x∈I => I=R所以總共就只會有一個ideal I, I=R(若是照書上的假設(題目在p9-120), 會多一個I={0})18. claim: (a,n)=1 iff a is an unit (1) (a,n)=1 => a^φ(n)=1 => 存在 a^(φ(n)-1) 為 a 的 inverse(2) 若(a,n)!=1, 則存在 k!=0 s.t. ka=n=0假設 a^-1 存在, a(a^-1)=1 => ka(a^-1)=k => 0(a^-1)=k, a contradiction所以在 Z_n 中總共會有φ(n)個units (φ: Euler's phi function)19. 相異transitive tournaments的總數應該是n!, 至於證明的話, 我的想法是這樣的: 對於每個Kn*裡的node, 他們的in-degree值都會唯一(out-degree值也是, 因為indeg+outdeg=n-1), 你可以試著證看看, 歸納法我想應該也行得通; 如此一來, 考慮in-degree為0,1,...,n-1, 因為每個in-degree皆可以對應到一個player, 所以總排列數就是n!14. A 為對稱且為方陣這兩個顯然成立, 令 X=[x_1 ... x_l], 則 A=(X^T)X, 所以 A 為 positive semi-definite, 則 (B),(D) 也會成立, (C)的反例不難找, 取線性相依的向量放入X的行即可, 所以答案是 (C)
不好意思 19題不大懂可以麻煩在解說一點嗎?
就是說因為in-degree值會唯一, 所以每個n個點的transitive tournament其實都會同構, 所以圖都長成同一種樣子, 而因為player是相異的, player_1, ..., player_n 分別可對應到in-degree為 0,1,...,n-1 的node, 所以總共的排列數就是n!例如當 n=3, 假設3個player分別是 p1,p2,p3, 則transitive tournament就只會長得像這樣:a → b ↘ c ↗其中 indeg(a)=0, indeg(c)=1, indeg(b)=2, 而 a,b,c 那三個node分別代表的player可能是(p1,p2,p3) or (p1,p3,p2), ..., (p3,p2,p1), 共3!種
我已修改過文章了 把我的問題打出來且多了一張圖 麻煩助教看看 謝謝
這張圖沒有符合indegree值唯一是因為它不符合transitive, 譬如假設那 5 個點依序是 a,b,c,d,e, 那麼有(d,a),(a,b)應該就要有(d,b), 可是你畫的是(b,d), 還有像是 e 可以經由 a,b 走到 c, 所以(c,e)應該要改成 (e,c); 如果是改上述那兩個邊, 那麼改了之後a~e的in-degree就會依序是2,3,4,1,0
張貼留言
5 則留言:
17. 這題其實在書上有出現過, 不過我發現他題目中的ideal和書上定義的不太一樣, 如果照他的假設:
(1) 假設 0∈I, 因為 for all x in R, -x 存在
=> 0-(-x)=x∈I => I=R
(2) 若存在 a!=0 屬於 I, 因為(R,+,˙)為field, 所以a^-1存在 => 1=a(a^-1)∈I
則 for all x∈R, 因為 1∈I
=> x=1x∈I => I=R
所以總共就只會有一個ideal I, I=R
(若是照書上的假設(題目在p9-120), 會多一個I={0})
18. claim: (a,n)=1 iff a is an unit
(1) (a,n)=1 => a^φ(n)=1
=> 存在 a^(φ(n)-1) 為 a 的 inverse
(2) 若(a,n)!=1, 則存在 k!=0 s.t. ka=n=0
假設 a^-1 存在, a(a^-1)=1 => ka(a^-1)=k
=> 0(a^-1)=k, a contradiction
所以在 Z_n 中總共會有φ(n)個units
(φ: Euler's phi function)
19. 相異transitive tournaments的總數應該是n!, 至於證明的話, 我的想法是這樣的: 對於每個Kn*裡的node, 他們的in-degree值都會唯一(out-degree值也是, 因為indeg+outdeg=n-1), 你可以試著證看看, 歸納法我想應該也行得通; 如此一來, 考慮in-degree為0,1,...,n-1, 因為每個in-degree皆可以對應到一個player, 所以總排列數就是n!
14. A 為對稱且為方陣這兩個顯然成立, 令 X=[x_1 ... x_l], 則 A=(X^T)X, 所以 A 為 positive semi-definite, 則 (B),(D) 也會成立, (C)的反例不難找, 取線性相依的向量放入X的行即可, 所以答案是 (C)
不好意思 19題不大懂
可以麻煩在解說一點嗎?
就是說因為in-degree值會唯一, 所以每個n個點的transitive tournament其實都會同構, 所以圖都長成同一種樣子, 而因為player是相異的, player_1, ..., player_n 分別可對應到in-degree為 0,1,...,n-1 的node, 所以總共的排列數就是n!
例如當 n=3, 假設3個player分別是 p1,p2,p3,
則transitive tournament就只會長得像這樣:
a → b
↘ c ↗
其中 indeg(a)=0, indeg(c)=1, indeg(b)=2,
而 a,b,c 那三個node分別代表的player可能是
(p1,p2,p3) or (p1,p3,p2), ..., (p3,p2,p1), 共3!種
我已修改過文章了 把我的問題打出來
且多了一張圖 麻煩助教看看 謝謝
這張圖沒有符合indegree值唯一是因為它不符合transitive, 譬如假設那 5 個點依序是 a,b,c,d,e, 那麼有(d,a),(a,b)應該就要有(d,b), 可是你畫的是(b,d), 還有像是 e 可以經由 a,b 走到 c, 所以(c,e)應該要改成 (e,c); 如果是改上述那兩個邊, 那麼改了之後a~e的in-degree就會依序是2,3,4,1,0
張貼留言