如何通过行和列切换进行矩阵转换？

Question

我有一个方形矩阵,由1或0元素组成.第i行切换切换所有第i行元素(1变为0,反之亦然)和第j列切换切换所有第j列元素.我有另一个相似大小的方阵.我想使用最小切换次数将初始矩阵更改为最终矩阵.例如

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

至

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

需要切换第一行和最后一列.

什么是正确的算法？

Answer 1

一般来说,问题不会有解决方案.为了看到这一点,请注意,将矩阵A变换为矩阵B相当于将矩阵A-B(使用二进制算法计算,使0-1 = 1)变换为零矩阵.查看矩阵A - B,并应用列切换(如果需要),以便第一行变为全0或全1.此时,您已完成列切换 - 如果您切换一列,则必须将它们全部切换以使第一行正确.如果此时甚至一行是0和1的混合,则问题无法解决.如果现在每一行都是0或全1,则可以通过切换适当的行来达到零矩阵来解决问题.

要获得最小值,请将第一行转换为0和1时所需的切换次数进行比较.在OP的示例中,候选者将切换第3列和第1行或切换第1列和第2列以及第2行和第3行.事实上,您可以通过查看第一个解决方案并查看切换次数是否更小或大于N - 如果大于N,则切换相反的行和列.