Re: [線代] 2題線代證明
※ 引述《kkman162 (不怕是一種幸福)》之銘言：
: 1.A permutation matrix p is a 0,1-matrix having exactly
: one 1 in each row and column.Prove that a square matrix
: of nonnegative integers can be expressed as the sum of k
: permutation matrices if and only if all row sums and
: column sums equal k.
一個方向很明顯。
另一個方向用歸納法做，
使用這個矩陣造一個圖，假設nxn矩陣，頂點分別 x_1,...,x_n,y_1,...,y_n
邊為： x_i連到y_j的邊個數為矩陣的 (i,j)-entry.（即允許多重邊）
這個圖是 k-regular bipartite，
跟據結婚定理，存在一個perfect matching，
利用這個perfect matching，可對回一個permutation matrix；
接下來balabala，你應該要可以自己寫完，打包收工。
: 2.A doubly stochastic matrix Q is a nonnegative real matrix
: in which every row and every column sums to 1.Prove that
: a doubly stochastic matrix Q can be expressed
: Q=C1P1+C2P2+....,where C1,C2... are nonnegative real numbers
: summing to 1 and P1,P2.... are permutation matrices.
http://www.math.ntu.edu.tw/~gjchang/
-> Course -> 2004年2月 NCTS數學科學高中生講習班 上課資料
-> 1. 相異代表系
btw,第一題是Introduction to Graph Theory,2nd Edition, Exercise 3.1.24。
第二題是 3.1.25，
暨 94下 張鎮華 圖論一期中考考題，
暨 91學年度 台大數研所博士班資格考題（離散數學）。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.189.13
※ 編輯: Eeon 來自: 182.235.189.13 (12/21 00:47)
推
12/21 02:07, , 1F
12/21 02:07, 1F
討論串 (同標題文章)