证：
一、定义与基本情况
双随机矩阵是指每行每列元素之和都等于1的矩阵。置换矩阵是一个方阵，它由单位矩阵经过行交换得到，每行每列有且仅有一个元素为1，其余元素为0。
对于 
的双随机矩阵 
，其中
且
，同时
和
。可以具体构造如下置换矩阵:
若 
，则
，此时可构造置换矩阵 
和
，使得关系式
等于该矩阵。同理，对其他情况进行类似构造。
二、归纳假设
假设所有
阶的双随机矩阵都可以分解为置换矩阵的乘积。
三、归纳步骤
现在考虑一个
阶的双随机矩阵
。
情况一：如果矩阵的某一行（假设是第
行）恰好是一个置换矩阵的行，那么可以通过以下方式进行分解。找到一个置换矩阵P，使得
将第行置换到第一行的位置。接着，忽略这一行和对应的列，得到一个
阶的双随机矩阵
。根据归纳假设，可以分解为置换矩阵的乘积
。那么原矩阵)
，从而完成了对这种情况的证明。
情况二：如果的每一行都不是一个置换矩阵的行，那么进行如下操作。由于是双随机矩阵，一定存在两个不同的行和
，使得![A[i,:]](https://math.jianshu.com/math?formula=A%5Bi%2C%3A%5D)
和![A[j,:]](https://math.jianshu.com/math?formula=A%5Bj%2C%3A%5D)
的元素之和大于1，必然存在两个位置k和l满足![A[i,k] > 0](https://math.jianshu.com/math?formula=A%5Bi%2Ck%5D%20%3E%200)
且![A[i,l] > 0](https://math.jianshu.com/math?formula=A%5Bi%2Cl%5D%20%3E%200)
，同时![A[j,k] > 0](https://math.jianshu.com/math?formula=A%5Bj%2Ck%5D%20%3E%200)
且![A[j,l] > 0](https://math.jianshu.com/math?formula=A%5Bj%2Cl%5D%20%3E%200)
。设![m=\min \{ A[i,k],A[j,k]\}](https://math.jianshu.com/math?formula=m%3D%5Cmin%20%5C%7B%20A%5Bi%2Ck%5D%2CA%5Bj%2Ck%5D%5C%7D)
，构造一个置换矩阵，它只交换行i和行j的位置，其余行保持不变。然后，构造一个置换矩阵
，它只交换列k和列l的位置，其余列保持不变。矩阵和的乘积
(
是的逆矩阵，也是一个置换矩阵)将不会改变的行和列的和，并且至少在两个位置上改变了的元素，使得新的矩阵在至少一个行或列上更接近置换矩阵的形式。重复这一过程，由于矩阵的元素是有限的，且每次操作都使得矩阵更接近置换矩阵的形式，所以最终可以将转化为一个置换矩阵。
综上，可以证明任一双随机矩阵都可以分解为置换矩阵的乘积。
