How to calculate cost to Convert an N X M binary matrix to all 0 matrix with only allowed moves as square-matrix toggle?

Question

Given an N X M binary matrix ( every element is either 1 or 0) , find the minimum number of moves to convert it to an all 0 matrix. For converting a matrix, one can choose squares of any size and convert the value of that square. '1' changes to '0' and '0' changes to '1'.This process can be done multiple times with square of the same size. Converting any square counts as 1 move.

Calculate minimum number of moves required..

Example : input matrix

0 1 1
0 0 0
0 1 1

we need to calculate minimum moves to convert this to all '0' matrix

0 0 0
0 0 0
0 0 0

Here, For square of size 1 ( 1 X 1 or single element sub-matrix), the total number of moves required to convert this matrix is 4 . he converts elements for position (1,2),(1,3),(3,2),(3,3)

For square of size 2 ( 2 X 2 or single element sub-matrix), it takes 2 moves to convert the matrix First we can convert elements from (1,2) to (2,3) and the matrix becomes, {{0 0 0}, {0 1 1}, {0 1 1}} And then we convert elements from (2,2)to (3,3) and the matrix becomes ``{{0 0 0}, {0 0 0}, {0 0 0}}```

So minimum is 2.

Could some help in designing an approach to this ?

I attempted to solve it using Gaussian elimination for every possible square size. But the result is not correct here. There must be some gap in my approach to this problem.

package com.practice.hustle;

import java.util.Arrays;

public class GaussianElimination {

    public static void main(String[] args) {
        int countMoves = Integer.MAX_VALUE;

        byte[][] inputMatrix = new byte[3][3];
        inputMatrix[0][0] = 0;
        inputMatrix[0][1] = 1;
        inputMatrix[0][2] = 1;
        inputMatrix[1][0] = 0;
        inputMatrix[1][1] = 0;
        inputMatrix[1][2] = 0;
        inputMatrix[2][0] = 0;
        inputMatrix[2][1] = 1;
        inputMatrix[2][2] = 1;
        int N = inputMatrix.length;
        int M = inputMatrix[0].length;

        int maxSize = Math.min(N, M);

        for (int j = 2; j <= maxSize; ++j) { // loop for every possible square size
            byte[][] a = new byte[N * M][(N * M) + 1];

            for (int i = 0; i < N * M; i++) { // logic for square wise toggle for every element of N*M elements

                byte seq[] = new byte[N * M + 1];
                int index_i = i / M;
                int index_j = i % M;
                if (index_i <= N - j && index_j <= M - j) {
                    for (int c = 0; c < j; c++) {
                        for (int k = 0; k < j; k++) {
                            seq[i + k + M * c] = 1;
                        }
                    }
                    a[i] = seq;
                } else {
                    if (index_i > N - j) {
                        seq = Arrays.copyOf(a[i - M], N * M + 1);
                    } else {
                        seq = Arrays.copyOf(a[i - 1], N * M + 1);
                    }
                }
                seq[N * M] = inputMatrix[index_i][index_j];
                a[i] = seq;

            }
            System.out.println("\nSolving for square size = " + j);
            print(a, N * M);

            int movesPerSquareSize = gaussian(a);
            if (movesPerSquareSize != 0) { // to calculate minimum moves
                countMoves = Math.min(countMoves, movesPerSquareSize);
            }
        }
        System.out.println(countMoves);
    }

    public static int gaussian(byte a[][]) {
        // n X n+1 matrix
        int N = a.length;
        for (int k = 0; k < N - 1; k++) {

            // Finding pivot element
            int max_i = k, max_value = a[k][k];
            for (int i = k + 1; i < N; i++) {
                if (a[i][k] > max_value) {
                    max_value = a[i][k];
                    max_i = i;
                }
            }

            // swap max row with kth row
            byte[] temp = a[k];
            a[k] = a[max_i];
            a[max_i] = temp;

            // convert to 0 all cells below pivot in the column
            

            for (int i = k+1; i < N; i++) {
                // int scalar = a[i][k] + a[k][k]; // probability of a divide by zero
                
                if (a[i][k] == 1) {
                    for (int j = 0; j <= N; j++) {
                        if (a[i][j] == a[k][j]) {
                            a[i][j] = 0;
                        } else {
                            a[i][j] = 1;
                        }
                    }
                }
            }
        }

        System.out.println("\n\tAfter applying gaussian elimination :  ");
        print(a, N);

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (a[i][N] == 1)
                ++count;
        }
        return count;
    }

    private static void print(byte[][] a, int N) {
        for (int i = 0; i < N; i++) {
            System.out.print("\t ");
            for (int j = 0; j < N + 1; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println(" ");
        }
    }

}

Its giving final reduced Euler matrix formed is incorrect and thereby the result is also incorrect.

I think its failing due to the logic used for element like - the cell at index-(2,3) , for that we are not sure which square would it be a part of ( either the square from (1,2) to (2,3) or the square from ( 2,2) to (3,3))

here the input matrix to Gaussian algo is having exactly same sequence at 2nd and 3rd row which could be the culprit of incorrect results.

     1 1 0 1 1 0 0 0 0 0  
   * 0 1 1 0 1 1 0 0 0 1 *
   * 0 1 1 0 1 1 0 0 0 1 * 
     0 0 0 1 1 0 1 1 0 0  
     0 0 0 0 1 1 0 1 1 0  
     0 0 0 0 1 1 0 1 1 0  
     0 0 0 1 1 0 1 1 0 0  
     0 0 0 0 1 1 0 1 1 1  
     0 0 0 0 1 1 0 1 1 1 

for a sqaure size 2, the above program prints :

Solving for square size = 2
The input to Gaussian algo : 
     1 1 0 1 1 0 0 0 0 0  
     0 1 1 0 1 1 0 0 0 1  
     0 1 1 0 1 1 0 0 0 1  
     0 0 0 1 1 0 1 1 0 0  
     0 0 0 0 1 1 0 1 1 0  
     0 0 0 0 1 1 0 1 1 0  
     0 0 0 1 1 0 1 1 0 0  
     0 0 0 0 1 1 0 1 1 1  
     0 0 0 0 1 1 0 1 1 1  

    After applying gaussian elimination :  
     1 0 1 0 0 0 1 0 1 1  
     0 1 1 0 0 0 0 1 1 0  
     0 0 0 0 0 0 0 0 0 0  
     0 0 0 1 0 1 1 0 1 0  
     0 0 0 0 1 1 0 1 1 1  
     0 0 0 0 0 0 0 0 0 0  
     0 0 0 0 0 0 0 0 0 0  
     0 0 0 0 0 0 0 0 0 1  
     0 0 0 0 0 0 0 0 0 1