I'm given a matrix [][]a, int size and int x. I need to write a method which takes the a[x][x] element and returns true if it is the top-left corner cell of an identity matrix in the given size. for example if a is :

 {{1 0 0 0}, 
 {1 0 1 0},
 {0 0 1 0},
 {0 0 0 1}}

size = 2, x = 2 - the method will return true, as a[2][2] is the top-left element of identity matrix 2x2.

Below is what I've been working on. The logic is: if current element is 1 and exactly size-1 elements below and left to current element are equal to 0, I move on to next element in the diagonal, while reducing size by 1 with every step. The method returns true for a =

{{1,0,0},
{0,1,0},
{0,0,1}}

size = 3, x = 0. However, if a[2][0] == 1 the method still returns true, and if a[1][0] == 1 it returns false as expected. Can anyone assist spotting the logic flaws here? much appreciated. Also, the method must not include any kind of loops, recursion only.

public static boolean isIdentity(int[][]a, int size, int x){
    return isIdentity(a, size, x, a[x][x]);
}
private static boolean isIdentity(int[][]a, int size, int x, int current){
    if(size == 0){
        return true;
    }
    if(size < 0 || x > a.length-1 || x > a[0].length-1){
        return false;
    }
    boolean t = false;
    if(current == 1 && x   1 < a.length && allZeros(a,size-1,a[x 1][x],a[x][x 1],x)){
        t =  isIdentity(a,size-1, x,a[x 1][x 1]);
    }
    return t;
}
private static boolean allZeros(int[][]a, int size, int current_down, int current_right,int x){
    if(current_down != 0 || current_right != 0){
        return false;
    }
    if(size == 0){
        return true;
    }
   return allZeros(a, size - 1, a[x 1][x],a[x][x 1],x);
    
}

                       
                     
                      

CodePudding user response：

You might find it easier to define allZeros using the following definition:

allZeros(a,size,x,i) = "a[x 1..x i][x] and a[x][x 1..x i] are all 0s"

When i=size, this equivalent to all of both edges (not including the corner) are 0.

Then your task becomes:

• What can I initialze i to be to make this trivially true?
• What do I need to do so that solving for the "next" i (i.e. the recursive call) solves the whole thing?

CodePudding user response：

If you are open to a different recursive implementation, here is my take on it:

public class CheckIdentity {

    public static void main(String[] args) {
    int [][] a = {{1, 0, 0, 0}, 
            {1, 0, 1, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1}};

    int [][] b = {{1,0,0},
        {0,1,0},
        {0,0,1}};
    int [][] b_2 = {{1,0,0},
        {0,1,0},
        {1,0,1}};

    System.out.println(isIdentity(a, 2, 2));
    System.out.println(isIdentity(b, 3, 0));
    System.out.println(isIdentity(b_2, 3, 0));

    }
    
    public static boolean isIdentity(int [][]a, int size, int x) {
    return isIdentity(a, x size,x, x,x);
    }

    public static boolean isIdentity(int[][] a, int size, int x, int r, int c) {
    int rI = (r   (c 1)/size);
    int cI = (c 1)==size ? x : c 1;
    
    //System.out.println(r   " "  c   " " rI   " " cI);
    
    if (r==size) {
        return true;
    }
    
    else if(r==c && a[r][c]==1) {
        return true && isIdentity(a, size, x, rI,cI);
    }
    else if(r!=c && a[r][c]==0) {
        return true && isIdentity(a, size, x, rI,cI);
    }
    else {
        return false;
    }
    }

}

The idea is we go to the next row only when we reach the specified size of the matrix. Further, if we go to a new row, our column will start back at x, the initial position of the column.

Since we are guaranteed to start on an index of a diagonal of the matrix, we can check when r is equal to c to determine whether the entry should be 1 or 0.

Output:

true
true
false