我有从被非零到零改变，我想知道是否有一个算法来交换所有行的矩阵内，以确保不存在非零值对角值的12×12的矩阵。 我的矩阵C，不得有在C（I，i）任何非零值。思考？

例： 我有一个5×5矩阵

  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
 

我怎么让这个不存在非零对角线元素？

解决方案 构造一个二分图。 创建一组节点，每个行索引，在左侧。 创建一组节点，每列一个索引，在右边。 对于矩阵的各元素A（I，J）： 如果A（I，J）是零，添加的节点行i和列j的节点之间存在边。 找到的二分图完美匹配。在匹配的n条边将告诉你如何重​​排的行。边（i，j）的在匹配表示行i应该成为行j

在这里看到的完美匹配算法：的http://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs

I have a 12x12 matrix with diagonal values that vary from being nonzero to zero, I am wondering if there is an algorithm to swap all the rows within a matrix to make sure there is no nonzero value. My matrix C, must not have any nonzero value at C(i,i). Thoughts?

Example: I have a 5x5 matrix

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

How do I make it so that there are no nonzero diagonal elements?

解决方案

Construct a bipartite graph. Create a set of nodes, one for each row index, on the left. Create a set of nodes, one for each column index, on the right. For each element A(i, j) of the matrix: If A(i, j) is zero, add an edge between the node for row i and the node for column j. Find a perfect matching in the bipartite graph. The n edges in the matching will tell you how to permute your rows. Edge (i,j) in the matching indicates that row i should become row j.

See here for the perfect matching algorithm: http://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs