Recursive function to check if a matrix is symmetric

Question

I have an assignment to implementthe matrix class and a method that checks if the matrix is symmetric. The method has to be recursive and then I have to calculate its complexity. After I have to transform the recursive function to its iterative version.

For now this is how my matrix class looks like:

public class Matrix<T> {
    private int m, n;
    private T[][] data;

    public Matrix(int m, int n) {
        this.m = m;
        this.n = n;
    }

    public Matrix(T[][] data) {
        this.data = data;
    }

    public boolean isSymmetric() {
        if (m != n) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (data[i][j] != data[j][i]) {
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    }

    public boolean isSymmetric(int i, int j) {
        if (i < 0 && j < 0) return true;
        else {
            return isSymmetric(i - 1, j - 1);
        }
    }

    public T get(int i, int j) {
        return data[i][j];
    }

    public void set(int i, int j, T value) {
        data[i][j] = value;
    }

    public int[] getSize() {
        return new int[]{m, n};
    }

    @Override
    public String toString() {
        String rep = "";
        for (int i = 0; i < m; i++) {
            rep += "( ";
            for (int j = 0; j < n; j++) {
                rep += data[i][j].toString() + "\t";
            }
            rep += ")\n";
        }
        return rep;
    }
}

I have a iterative version of the isSymmetric() function, but I cannot get the recursive one.

Answer 1

In the recursive version, you forgot to add a check to see if the two elements are equal. Without it, there is no case where the method would return false.

public boolean isSymmetric() {
    return m == n && isSymmetric(m - 1, n - 1);
}

public boolean isSymmetric(int i, int j) {
    if (i < 0 && j < 0) return true;
    else if (data[i][j] != data[j][i]) return false;
    else {
        return isSymmetric(i - 1, j - 1);
    }
}

Answer 2

You can start check from maximum row and col each recursion will be decrese it by 1 until 0;

public class Matrix<T> {

    private final int height;
    private final int width;
    private final T[][] data;

    public Matrix(T[][] data) {
        height = data.length;
        width = data[0].length;
        this.data = data;   // it brakes OOP: encapsulation
    }

    public boolean isSymmetricIterative() {
        if (height != width)
            return false;

        for (int row = 0; row < height; row++)
            for (int col = 0; col < width; col++)
                if (data[row][col] != data[col][row])
                    return false;

        return true;
    }

    public boolean isSymmetricRecursive() {
        return isSymmetricRecursive(height - 1, width - 1);
    }

    private boolean isSymmetricRecursive(int row, int col) {
        return row < 0 && col < 0 || data[row][col] == data[col][row] && isSymmetricRecursive(row - 1, col - 1);
    }

}

Answer 3

Symmetric matrix is a square matrix that is equal to its transpose. Let's assume that we have a square matrix.

To avoid unnecessary iterations and to reduce the time complexity, you can iterate over the indices only in the lower left corner of the matrix and compare the corresponding elements with those in the upper right corner m[i][j]==m[j][i], excluding the main diagonal, until the first mismatch.

Try it online!

// let's assume that we have a square matrix
public static void main(String[] args) {
    int[][] matrix = {
            {1, 2, 3, 4, 5},
            {2, 3, 4, 5, 6},
            {3, 4, 5, 6, 7},
            {4, 5, 6, 7, 8},
            {5, 6, 7, 8, 9}};

    System.out.println(isSymmetric(matrix)); // true
    System.out.println(isSymmetricR(matrix, 1, 0)); // true
}

// iterative version
static boolean isSymmetric(int[][] matrix) {
    return IntStream.range(1, matrix.length)
            .allMatch(i -> IntStream.range(0, i)
                    //intermediate output
                    .peek(j -> System.out.println("i=" + i + ",j=" + j))
                    .allMatch(j -> matrix[i][j] == matrix[j][i]));
}

// recursive version
static boolean isSymmetricR(int[][] matrix, int i, int j) {
    if (i < matrix.length && j < i) {
        //intermediate output
        System.out.println("i=" + i + ",j=" + j);
        if (matrix[i][j] == matrix[j][i]) {
            if (j == i - 1) {
                return isSymmetricR(matrix, i + 1, 0);
            } else {
                return isSymmetricR(matrix, i, j + 1);
            }
        } else {
            // the first mismatch, the
            // matrix is not symmetric
            return false;
        }
    } else {
        // if reached this point,
        // the matrix is symmetric
        return true;
    }
}

The intermediate output is the same in both cases:

i=1,j=0
i=2,j=0
i=2,j=1
i=3,j=0
i=3,j=1
i=3,j=2
i=4,j=0
i=4,j=1
i=4,j=2
i=4,j=3

---

^{See also: How to remove rows and columns containing only zeros from a 2d matrix?}