如何通过行和列切换做矩阵转换？ [英] How to do matrix conversions by row and columns toggles?

问题描述

我有一个方阵组成元素是1的 或0的第i行切换切换所有的第i行元素（1 变为0，反之亦然）j列切换切换所有 第j列的元素。我已经得到了一个方阵 类似的大小。我想改变最初的矩阵的 使用切换的最小数目最终基质。例如

I have got a square matrix consisting of elements either 1 or 0. An ith row toggle toggles all the ith row elements (1 becomes 0 and vice versa) and jth column toggle toggles all the jth column elements. I have got another square matrix of similar size. I want to change the initial matrix to the final matrix using the minimum number of toggles. For example

|0 0 1|
|1 1 1|
|1 0 1|

到

|1 1 1|
|1 1 0|
|1 0 0|

将需要的最后的第一行和肘节 列。

would require a toggle of the first row and of the last column.

将什么正确的算法呢？

推荐答案

在一般情况下，这个问题将不会有一个解决方案。看到这一点，请注意，变换矩阵A到矩阵B等效变换矩阵A - B（使用二进制算术计算，以便0 - 1 = 1）到零矩阵。看矩阵A - B和应用柱切换（如果需要的话），以使第一行变为全0或全1。在这一点上，你与柱切换完成 - 如果选中一列，你必须切换他们都拿到了第一排正确。如果连一行是0和1的在这一点上的混合物中，该问题不能得到解决。如果每行现在是全0或全1，这个问题是可以解决的通过切换相应的行达到零矩阵。

In general, the problem will not have a solution. To see this, note that transforming matrix A to matrix B is equivalent to transforming the matrix A - B (computed using binary arithmetic, so that 0 - 1 = 1) to the zero matrix. Look at the matrix A - B, and apply column toggles (if necessary) so that the first row becomes all 0's or all 1's. At this point, you're done with column toggles -- if you toggle one column, you have to toggle them all to get the first row correct. If even one row is a mixture of 0's and 1's at this point, the problem cannot be solved. If each row is now all 0's or all 1's, the problem is solvable by toggling the appropriate rows to reach the zero matrix.

要得到的最小值，当第一行被接通到0与1的比较需要切换的数目。在OP的例子中，考生会触发第3列和行1或切换1和2列和行2和3。其实，你可以通过查看第一个解决方案，看简化，如果切换的数量小于或大于N - 。如果大于N，比切换相对行和列

To get the minimum, compare the number of toggles needed when the first row is turned to 0's vs. 1's. In the OP's example, the candidates would be toggling column 3 and row 1 or toggling columns 1 and 2 and rows 2 and 3. In fact, you can simplify this by looking at the first solution and seeing if the number of toggles is smaller or larger than N -- if larger than N, than toggle the opposite rows and columns.

这篇关于如何通过行和列切换做矩阵转换？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！