Algorithm that determines if a given binary matrix can be reached by flipping rows and columns of a matrix of ones

Question

I need help finding an Algorithm that is as effective as possible for checking if a given binary matrix can be reached by flipping rows and columns of a matrix with only one's. Whenever you flip a row or a col all the 0 become 1 and all 1 become 0

Algorithm that determines if a given binary matrix can be reached by flipping rows and columns of a matrix of ones

for example this matrix can be reached by flipping the second row and then flipping the second col:

+---+---+---+
| 1 | 0 | 1 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 1 | 0 | 1 |
+---+---+---+

but this matrix can't be whatever flipping you do

+---+---+---+
| 1 | 0 | 0 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 0 | 0 | 1 |
+---+---+---+

Inversion

what's the max size of the matrix? – Laktasic

Can you please describe with example what a flip does exactly? – Sapers

That looks like a difficult problem, that requires some testing. Have you written a brute-force-algorithm to try this with simple examples? There could be a mathematical solution to it (i.e. by computing the determinant) but you need to be able to find the difference between a working matrix and a non-working one. If that's not possible, you're quite lost, because then it's a termination problem, which is inherently unsolvable. – Stedt

@trincot: A flip changes all 0's to 1's and vice versa on either a row or a column. The first example gives, after flipping the middle row and then the middle column, all 1's. – Stedt

Answer 1

This can be tested as follows:

Take the first column of the target matrix. All other columns should be either the same as that first column, or should be its opposite (flipped). If, and only when, this is the case then the target matrix can be reached through flips of rows/columns from the initial matrix having all 1 values.

You can also do the test with rows of course, but it is enough to perform it with either rows or columns.

Which flips to perform?

You can also see which flips you can perform to reach a target matrix in case the above test is positive:

In the first row of the target matrix, identify the cells with value 0: those are the columns you need to flip in the initial matrix.

In the first column of the target matrix, identify the cells with a value different from the value in the top-left corner of the target matrix (so this already excludes the first value): those are the rows you need to flip in the initial matrix.

The order in which the flips are performed is not important. Obviously, this gives just one solution. There can be more than one in general.

Implementation

Here is a simple JavaScript snippet that performs the verification and provides a list of columns and rows to swap if possible:

function getFlips(matrix) {
    // Verification
    for (let i = 1; i < matrix.length; i++) {
        let flip = matrix[i][0] ^ matrix[0][0]; // XOR operation
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] ^ flip != matrix[0][j]) return false; // Not possible
        }
    }
    // If we get here, it is possible: determine which rows/columns to flip
    let flips = { rows: [], columns: [] };
    for (let j = 0; j < matrix[0].length; j++) {
        if (matrix[0][j] == 0) flips.columns.push(j+1);
    }
    for (let i = 1; i < matrix.length; i++) {
        if (matrix[i][0] != matrix[0][0]) flips.rows.push(i+1);
    }
    return flips;
}


// I/O management
inp.oninput = function () {
    // Convert input to matrix of numbers
    let matrix = inp.value.split('\n').map(row => Array.from(row, Number));
    // Perform algorithm
    let flips = getFlips(matrix);
    // Output the result in human readable format
    out.textContent = flips 
        ? 'Number(s) of the column(s) to flip: ' 
            + (flips.columns.length ? flips.columns : 'none') + '\n' +
          'Number(s) of the row(s) to flip: ' 
            + (flips.rows.length ? flips.rows : 'none')
        : 'Not possible';
};

inp.oninput();

Enter the values of the matrix:<br>
<textarea id="inp" rows="4" cols="4">101
010
101</textarea><br>
Solution:
<pre id="out"></pre>

Sapers

Answer 2

Considering we have a N by N(square) matrix, we can reach the target matrix in N steps with the use of dynamic programming.

Suppose we have already matched the top-left K by K submatrix through some flips on initial matrix. Then, by flipping K+1'th row or/and K+1'th column, we can match the submatrix K+1 by K+1. At each step, we can have one of 4 options:

• flip K+1'th row, and flip K+1'th column
• flip K+1'th row, not flip K+1'th column
• not flip K+1'th row, flip K+1'th column
• not flip K+1'th row, not flip K+1'th column

With each option, we check if the submatrix of size K+1 matches the same region of the target matrix. If it matches, then we move to the next step (K+2), otherwise, we stop our search and conclude that two original matrices don't match. We go on this process till we match submatrix of size N.

So, every time, we move on with next row and next column, trying to avoid flipping of previous rows/columns and thus keeping already matched submatrix unchanged.

The process goes this way:
1. We match top-left 1x1 submatrix by flipping 1st row/column
2. We match top-left 2x2 submatrix by flipping 2nd row/column
3. We match top-left 3x3 submatrix by flipping 3rd row/column
...
N. We match top-left NxN submatrix by flipping N'th row/column

Laktasic

Answer 3

To determine if it's possible to make all elements in the given matrix equal to 0 by flipping either all row values or all column values, you can use the following approach:

• Count the number of 1s in each row and each column.
• If the count of 1s in any row or column is odd, it's not possible to make all elements 0. In this case, return False.
• If the count of 1s in all rows and all columns is even, it's possible to make all elements 0. Return True.

Code:

def canMakeAllZeros(matrix):
if not matrix:
    return True  # An empty matrix is considered valid

rows = len(matrix)
cols = len(matrix[0])

# Count the number of 1s in each row and each column
row_counts = [0] * rows
col_counts = [0] * cols

for i in range(rows):
    for j in range(cols):
        if matrix[i][j] == 1:
            row_counts[i] += 1
            col_counts[j] += 1

# Check if there is any row or column with an odd count of 1s
for count in row_counts + col_counts:
    if count % 2 != 0:
        return False

return True

Non