Check if a Matrix is an Identity Matrix

An identity matrix constrains every position, not just the main diagonal

A matrix is an identity matrix only when it is square and satisfies two rules at every position. If the row index i equals the column index j, the value must be 1. If i and j are different, the value must be 0. The matrix A is square with three rows and three columns, so it passes the dimension requirement before its cell values are checked.

A =
[1  0  0]
[0  1  4]
[0  0  1]

A has 1 at A[0][0], A[1][1], and A[2][2], so every main-diagonal position has the required value. That is not enough. A[1][2] is off the main diagonal, so it must contain 0, but it contains 4. This single value makes A fail the identity-matrix test.

One nested traversal can test both identity rules

A nested traversal visits each position using its row index i and column index j. At each position, calculate the value that should be there: expected is 1 when i equals j, and expected is 0 otherwise. Then compare the actual cell with expected. This uses one traversal for both kinds of positions instead of writing one traversal for the diagonal and another for the remaining cells.

bool isIdentity(const vector<vector<int>>& A) {
    int rows = A.size();
    int cols = A[0].size();

    if (rows != cols) return false;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int expected = (i == j) ? 1 : 0;
            if (A[i][j] != expected) return false;
        }
    }

    return true;
}

For A, row-major order starts at A[0][0]. The expected values for A[0][0], A[0][1], and A[0][2] are 1, 0, and 0, and all three comparisons pass. The next row expects 0 at A[1][0] and 1 at A[1][1], so those comparisons pass too. At A[1][2], i is 1 and j is 2, so the expected value is 0, but the actual value is 4. The comparison fails there.

One mismatch proves false, but true requires every position to pass

The test can return false as soon as an actual value differs from its expected value. For A, that happens at A[1][2], before the traversal reaches A[2][0]. There is no reason to inspect later positions after a mismatch, because one failed condition is enough to prove that the whole matrix is not an identity matrix.

The true return has a different requirement. It must wait until both loops finish, because reaching one matching cell proves only that one position is correct. If true were returned after A[0][0], the unchecked positions could contain any values, including the invalid 4 at A[1][2]. Only a complete traversal without an early false return proves true.

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        int expected = (i == j) ? 1 : 0;
        if (A[i][j] != expected) return false;
    }
}

return true;

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        int expected = (i == j) ? 1 : 0;
        if (A[i][j] != expected) return false;
        return true;
    }
}

The complete check uses constant extra space and has quadratic worst-case time

The square-dimension test compares the number of rows with the number of columns, so it takes constant time. After that, an n x n matrix can require every one of its n squared cells to be compared with its expected value. For A, the row-major check stops on the sixth comparison at A[1][2]. A matrix that passes, or one whose first mismatch is at the final position, requires all nine comparisons.

The algorithm uses constant extra space, written as O(1), because it stores only a few values: the row index, the column index, the expected value, and the dimension variables. It does not create another matrix or a collection that grows with the input. Its worst-case running time is O(n squared) for an n x n matrix.