algorithm - 交换矩阵中的行以确保每个对角线值都非零？

Question

我有一个 12x12 矩阵，其对角线值从非零到零不等，我想知道是否有一种算法可以交换矩阵中的所有行以确保没有非零值。我的矩阵 C 在 C(i,i) 处不能有任何非零值。想法？

例子:我有一个 5x5 矩阵

3 4 5 0 6
1 0 4 3 0
0 5 1 0 3
0 1 0 2 0 
2 0 5 0 0

如何做到不存在非零对角线元素？

Answer 1

1. 构建二分图。
   • 在左侧创建一组节点，每个节点对应一个行索引。
   • 在右侧创建一组节点，每个节点对应一个列索引。
2. 对于矩阵的每个元素 A(i, j):
   • 如果 A(i, j) 为零，则在第 i 行的节点和第 j 列的节点之间添加一条边。
3. 在二部图中找到完美匹配。匹配中的 n 条边将告诉您如何排列行。匹配中的边(i,j)表示第i行应该成为第j行。

完美匹配算法见这里:http://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs