让M是一个 nxn 矩阵，每个条目等于 0 或 1。让m[i][j]
表示 rowi和 column中的条目j。对角线条目是m[i][i]某些 i 的一种形式。交换矩阵的行i和表示以下动作：jM
我们交换值m[i][k]和m[j][k]for k = 1, 2 ..... n。交换两列的定义类似 我们说M如果可以交换一些行对和一些列对（以任何顺序），那么它是可重新安排的，这样，在所有交换之后，所有对角线条目M都是等于 1。
(a) 给出一个M不可重排矩阵的例子，但在每一行和每一列中至少有一个条目等于!。
(b) 给出一个多项式时间算法，该算法确定
M具有0-1条目的矩阵是否可重排。
我尝试了很多但无法得出任何结论，请为此建议我算法。
我认为这篇文章是这里的主题，因为我认为答案是http://en.wikipedia.org/wiki/Assignment_problem。考虑在第 i 列中为每个 i 放置 1 的工作。每行都可以完成这些工作的一部分。如果您可以找到行的分配，使得有不同的行能够在每列中放置 1，那么您可以通过重新排列行来使矩阵对角线，以便第 i 行在第 i 列上放置 1。
假设有一个作业可以解决这个问题。将溶液中含有 1 的单元格涂成红色。请注意，置换行会在每行和每列中留下一个红色单元格。类似地，排列列会在每一行和每一列中留下一个红色单元格。因此，无论您置换多少行和列，我都可以通过置换行来恢复对角线。因此，如果有任何解决方案可以在所有对角线上放置 1，那么无论您如何尝试通过排列行和列来伪装它，我都可以通过仅排列行来恢复对角线。因此，当没有解决方案时，分配算法无法准确解决这个问题，例如，如果只有 1 在顶行和最左边的列中。