[詹兴致矩阵论习题参考解答]习题2.7

7. (Marcus-Ree) 一个非负矩阵称为是双随机的, 若它的每行元素之和等于 $1$, 且它的每列元素之和也等于 $1$. 设 $A=(a_{ij})$ 为 $n$ 阶双随机矩阵, 则存在 $1,2,\cdots,n$ 的一个排列 $\sigma$ 使得对每个 $i=1,\cdots,n$,

$$\bex a_{i\sigma(i)}\geq \sedd{\ba{ll} \cfrac{1}{k(k+1)},&n=2k,\\ \cfrac{1}{(k+1)^2},&n=2k+1. \ea} \eex$$

 

 

证明: (1) 我们先把定理 2.15 (K\"onig) 推广一下: 设 $A\in M_{m,n}$ 是一个实矩阵, $m\leq n$, $a\in\bbR$, 则 $A$ 的每条对角线都至少含有 $k$ 个元素 $<a$, 当且仅当 $A$ 有一个 $r\times s$ 的子矩阵 $B$ 满足

$$\bex r+s=n+k,\quad b_{ij}<a. \eex$$ 事实上, ``$A$ 的每条对角线都至少含有 $k$ 个元素 $<a$'' 当且仅当 `` $$\bex \chi_{<a}(A)[i,j]=\sedd{\ba{ll} 0,&a_{ij}<a\\ 1,&a_{ij}\geq a \ea} \eex$$ 的每条对角线都至少含有 $k$ 个零元素'', 由定理 2.15 (K\"onig), 这等价于 ``$\chi_{<a}(A)$ 有一个 $r\times s$ 阶的零子矩阵 $0_{r,s}$, $r+s=n+k$'', 把 $A$ 中与 $0_{r,s}$ 相应的子矩阵 $B$ 提出来, 不就是说 $B$ 的每个元素 $<a$ 么. 反之亦成立.

 

(2) 往证题目. 若结论不成立, 则 $A$ 的每条对角线至少有一个元素 $<a$, 其中

$$\bex a=\sedd{\ba{ll} \cfrac{1}{k(k+1)},&n=2k,\\ \cfrac{1}{(k+1)^2},&n=2k+1. \ea} \eex$$ 而由 (1), $A$ 有一个 $r\times s$ 的子矩阵 $B$, $r+s=n+1$, $B$ 的元素均小于 $a$. 作出 $$\bex A=\sex{\ba{cc} B_{r,s}&C\\ D&E \ea}, \eex$$ 用 $\sum B$ 表示对 $B$ 的所有元素求和, 则 $$\bee\label{2_7_B} \sum B<rsa, \eee$$ $$\bee\label{2_7_BC} \sum B+\sum C=r, \eee$$ $$\bee\label{2_7_BD} \sum B+\sum D=s, \eee$$ $$\bee\label{2_7_BCDE} \sum B+\sum C+\sum D+\sum E=n. \eee$$ 由 $\eqref{2_7_BC}+\eqref{2_7_BD}-\eqref{2_7_BCDE}$ 得 $$\bee\label{2_7_BE} \sum B-\sum E=r+s-n =(n+1)-n=1. \eee$$ 综合 $\eqref{2_7_B}$ 和 $\eqref{2_7_BE}$ 即知 $$\bex rsa>\sum B=\sum E+1\geq 1, \eex$$ $$\bee\label{2_7_a} a>\frac{1}{rs}=\frac{1}{r(n+1-r)}. \eee$$ 但 $\eqref{2_7_a}$ 不成立, 而证完题目. 事实上, 当 $n=2k$ 时, $$\bex \frac{1}{rs} =\frac{1}{r(2k+1-r)} \geq \frac{1}{k(2k+1-k)}=\frac{1}{k(k+1)}=a; \eex$$ 当 $n=2k+1$ 时, $$\bex \frac{1}{rs} =\frac{1}{r(2k+2-r)} \geq\frac{1}{(k+1)(2k+2-(k+1))} =\frac{1}{(k+1)^2}=a. \eex$$