推 peterscaa :感謝>_< 不知昨天鬼打牆還是怎樣 卡在一些笨地方 05/02 15:45
唔嗯...這比較像是把 relation 的性質轉化成矩陣性質的題目...
不過照你下面的敘述這個 M 比較不像是平常數字的矩陣 而比較像是邏輯矩陣
(就是這玩意:
http://zh.wikipedia.org/wiki/%E9%82%8F%E8%BC%AF%E7%9F%A9%E9%99%A3 )
故以下我都照這個模式來寫
也就是矩陣乘法變成那兩排的兩兩元素 and 之後再全部 or 起來
那個 <= 這裡也理解成逐元素比較都成立
※ 引述《peterscaa (lousai)》之銘言：
: 不知道這樣分類有沒有錯誤 Orz
: Given a set a with |A| = n and a relation R on A,
: let M (zero-one metirc) denote the relation matrix for R.
: Then
: R is transitive if and only if M^2 <= M
R 有遞移性就是 a R b & b R c 可推得 a R c
表現在矩陣上就是當 M(a,b) 跟 M(b,c) 都是 1 則可推得 M(a,c) 也是 1
而 M^2(a,c) = 1 表示存在 b, M(a,b) 跟 M(b,c) 都是 1
也就是說, 若 R 有遞移性, 則「M^2(a,c) = 1 可推得 M(a,c) = 1」
因此對任何元素都會有 M^2(a,c) <= M(a,c)
(因為不會出現前者是 1 後者是 0 的狀況)
: R is antisymmetric if and only if M 且 M^tr <= In
: In 是指大小為n的乘法單位矩陣
R 是反對稱即是當 a R b & b R a 則 a = b
表現在矩陣上就是 M 跟 M^tr 同時是 1 的元素只會在主對角線上
那麼 M and M^tr 的 1 當然也只會在主對角線上 自然這個矩陣 <= In
--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1398966579.A.5C0.html