证明任一双随机矩阵都可分解为若干个置换阵的乘积

证明任一双随机矩阵都可分解为若干个置换阵的乘积。

证：

一、定义与基本情况

双随机矩阵是指每行每列元素之和都等于1的矩阵。置换矩阵是一个方阵，它由单位矩阵经过行交换得到，每行每列有且仅有一个元素为1，其余元素为0。

对于 $2\times 2$ 的双随机矩阵 $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$ ，其中$a+b=1$且$c+d=1$，同时$a+c=1$ 和$b+d=1$。可以具体构造如下置换矩阵:

若 $a=1$，则$\left[\begin{array}{cc}1& 0\\ c& d\end{array}\right]$，此时可构造置换矩阵 $P_1=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$和$P_2=\left[\begin{array}{cc}1& 0\\ c& d\end{array}\right]$，使得关系式$P_1{P}_2$等于该矩阵。同理，对其他情况进行类似构造。

二、归纳假设

假设所有$n-1$阶的双随机矩阵都可以分解为置换矩阵的乘积。

三、归纳步骤

现在考虑一个$n$阶的双随机矩阵$A$。

1. 情况一：如果矩阵$A$的某一行（假设是第$i$行）恰好是一个置换矩阵的行，那么可以通过以下方式进行分解。找到一个置换矩阵P，使得$P$将第$i$行置换到第一行的位置。接着，忽略这一行和对应的列，得到一个$n-1$阶的双随机矩阵$A^{\prime }$。根据归纳假设，$A^{\prime }$可以分解为置换矩阵的乘积$P_1{P}_2\cdots P_k$。那么原矩阵$A=P(P_1{P}_2\cdots P_k)$，从而完成了对这种情况的证明。

2. 情况二：如果$A$的每一行都不是一个置换矩阵的行，那么进行如下操作。由于$A$是双随机矩阵，一定存在两个不同的行$i$和$j$，使得$A[i,:]$和$A[j,:]$的元素之和大于1，必然存在两个位置k和l满足$A[i,k]>0$且$A[i,l]>0$，同时$A[j,k]>0$且$A[j,l]>0$。设 m = min ⁡ { A [ i , k ] , A [ j , k ] } m=\min \{ A[i,k],A[j,k]\} m=min{A[i,k],A[j,k]}，构造一个置换矩阵$P$，它只交换行i和行j的位置，其余行保持不变。然后，构造一个置换矩阵$Q$，它只交换列k和列l的位置，其余列保持不变。矩阵$P$和$Q$的乘积$QP\cdot P^{\prime }$($P^{\prime }$是$P$的逆矩阵，也是一个置换矩阵)将不会改变$A$的行和列的和，并且至少在两个位置上改变了$A$的元素，使得新的矩阵在至少一个行或列上更接近置换矩阵的形式。重复这一过程，由于矩阵的元素是有限的，且每次操作都使得矩阵更接近置换矩阵的形式，所以最终可以将$A$转化为一个置换矩阵。

综上，可以证明任一双随机矩阵都可以分解为置换矩阵的乘积。