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

证：

一、定义与基本情况

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

对于 的双随机矩阵 ，其中且，同时 和。可以具体构造如下置换矩阵:

若 ，则，此时可构造置换矩阵 和，使得关系式等于该矩阵。同理，对其他情况进行类似构造。

二、归纳假设

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

三、归纳步骤

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

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

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

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