2D-Arrays V
So ,while learning about the Symmetrix matrix we had to revise our concepts on the Transpose of a matrix , the upper triangular matrix and the lower triangular matrix as well. Let's now learn about more such 2D-Arrays .
Q13. Identity Matrix
An identity matrix is a square matrix where, all diagonal elements are 1 and all non-diagonal elements are 0.
Example
Input
mat[][]= {{1,0,0},{0,1,0},{0,0,1}}
Output= Yes , it is an Identity matrix
Approach
If we read what an Identity matrix is , we say that we need to check two things, one is whether all the diagonal elements are 1 and non diagonal-elements are 0. If both the conditions holds true, then we can conclude that the matrix is an Identity Matrix.
Step 1: Initialize an outer loop that traverses from i= 0 to i<mat.length.
Step 2: For each 1D-Array we will initialize an inner loop that runs from j=0 to j<mat[0].length.
For each iteration, we will check if
- i==j and mat[i][j] not equals 1: If this conditions is satisfied, we can return a false since an identity matrix must have all the diagonal elements as 1.
- i!=j and mat[i][j] != 0 , then we will return a false.
Step 3: At end we can return a true if the execution pointer enters none of the above two conditions which means we can conclude that the matrix is an Identity matrix.
Dry-Run
Iteration 1: i=0,j=0 (Diagonal Element)
- Matrix[0][0] = 1
- Since i=j, it should be 1, which it is.
- No issue, continue to next element.
Iteration 2: i=0,j=1i = 0, j = 1i=0,j=1 (Off-Diagonal Element)
- Matrix[0][1] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 3: i=0,j=2(Off-Diagonal Element)
- Matrix[0][2] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 4: i=1,j=0(Off-Diagonal Element)
- Matrix[1][0] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 5: i=1,j=1 (Diagonal Element)
- Matrix[1][1] = 1
- Since i=j, it should be 1, which it is.
- No issue, continue to next element.
Iteration 6: i=1,j=2 (Off-Diagonal Element)
- Matrix[1][2] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 7: i=2,j=0 (Off-Diagonal Element)
- Matrix[2][0] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 8: i=2,j=1(Off-Diagonal Element)
- Matrix[2][1] = 0
- Since i≠j, it should be 0, which it is.
- No issue, continue to next element.
Iteration 9: i=2,j=2(Diagonal Element)
- Matrix[2][2] = 1
- Since i=j, it should be 1, which it is.
- No issue, end of the check.
Step 4: Final Decision
We have checked all the elements and confirmed that:
- All diagonal elements are 1.
- All off-diagonal elements are 0.
Since the matrix satisfies the conditions for an identity matrix, the result is:
"Yes, it is an Identity Matrix."
Code in all Languages
1. C++ Try on Compiler
#include <iostream>
using namespace std;
// Function to check if a matrix is an identity matrix
bool isIdentityMatrix(int matrix[][100], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j && matrix[i][j] != 1) {
return false; // Diagonal element is not 1
} else if (i != j && matrix[i][j] != 0) {
return false; // Off-diagonal element is not 0
}
}
}
return true; // All checks passed
}
int main() {
int n;
cout << "Enter the size of the square matrix: ";
cin >> n;
int matrix[100][100];
cout << "Enter the matrix elements row by row:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
if (isIdentityMatrix(matrix, n)) {
cout << "Yes, it is an identity matrix." << endl;
} else {
cout << "No, it is not an identity matrix." << endl;
}
return 0;
}
2. Java Try on Compiler
import java.util.Scanner;
public class IdentityMatrix {
public static boolean isIdentityMatrix(int[][] matrix, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j && matrix[i][j] != 1) {
return false; // Diagonal element is not 1
} else if (i != j && matrix[i][j] != 0) {
return false; // Off-diagonal element is not 0
}
}
}
return true; // All checks passed
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the square matrix: ");
int n = sc.nextInt();
int[][] matrix = new int[n][n];
System.out.println("Enter the matrix elements row by row:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
if (isIdentityMatrix(matrix, n)) {
System.out.println("Yes, it is an identity matrix.");
} else {
System.out.println("No, it is not an identity matrix.");
}
sc.close();
}
}
3. Python Try on Compiler
def is_identity_matrix(matrix, n):
for i in range(n):
for j in range(n):
if i == j and matrix[i][j] != 1:
return False # Diagonal element is not 1
elif i != j and matrix[i][j] != 0:
return False # Off-diagonal element is not 0
return True # All checks passed
n = int(input("Enter the size of the square matrix: "))
matrix = []
print("Enter the matrix elements row by row:")
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
if is_identity_matrix(matrix, n):
print("Yes, it is an identity matrix.")
else:
print("No, it is not an identity matrix.")
4. JavaScript Try on Compiler
function isIdentityMatrix(matrix, n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i === j && matrix[i][j] !== 1) {
return false; // Diagonal element is not 1
} else if (i !== j && matrix[i][j] !== 0) {
return false; // Off-diagonal element is not 0
}
}
}
return true; // All checks passed
}
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.question("Enter the size of the square matrix: ", (n) => {
n = parseInt(n);
const matrix = [];
console.log("Enter the matrix elements row by row:");
let rowIndex = 0;
const readRow = () => {
if (rowIndex < n) {
rl.question(`Row ${rowIndex + 1}: `, (row) => {
matrix.push(row.split(" ").map(Number));
rowIndex++;
readRow();
});
} else {
if (isIdentityMatrix(matrix, n)) {
console.log("Yes, it is an identity matrix.");
} else {
console.log("No, it is not an identity matrix.");
}
rl.close();
}
};
readRow();
});
Time Complexity: O(n²)
We iterate over all the elements of the matrix exactly once to check if they are correct (i.e., diagonal elements should be 1, and non-diagonal elements should be 0).
The time taken for each comparison is constant, O(1).
So, we perform a constant time check O(1) for each of the n^2 elements, resulting in a total time complexity of O(n^2)
Space Complexity: O(1)
Auxiliary Space Complexity
Auxiliary space refers to the additional memory used during the execution of the algorithm, excluding the space used by the input matrix itself.
In-place Comparison:
- We are only using a few extra variables (like loop counters i and j), which take constant space.
- There is no extra space used for creating another matrix or storing additional data structures.
Thus, the auxiliary space complexity is: Auxiliary Space Complexity=O(1).
Total Space Complexity
Total space complexity accounts for both the space used by the input matrix and the extra memory used during execution.
Input Matrix: The matrix itself takes up O(n^2) space as it is an n×n matrix.
Auxiliary Space: As mentioned above, the algorithm uses constant auxiliary space O(1).
Thus, the total space complexity is the space used by the input matrix plus the constant auxiliary space:
Total Space Complexity= O(n^2) + O(1) = O(n^2).
Now, let's dive into another such type of matrix which is sparse matrix