The Toeplitz matrix problem involves checking whether a given matrix is a Toeplitz matrix. A matrix is defined as a Toeplitz matrix if each descending diagonal from left to right is constant, meaning that all elements in that diagonal have the same value.
Problem Statement
Given an m x n matrix, determine if it is a Toeplitz matrix.
Example
For the matrix:
[
[1, 2, 3, 4],
[5, 1, 2, 3],
[6, 5, 1, 2]
]
This is a Toeplitz matrix because all descending diagonals have the same values:
- Diagonal starting at (0,0): 1
- Diagonal starting at (0,1): 2
- Diagonal starting at (0,2): 3
- Diagonal starting at (1,0): 5
- Diagonal starting at (1,1): 1
- etc.
C# Implementation
Here’s how to implement the Toeplitz matrix check in C#:
using System;
public class ToeplitzMatrix
{
public static bool IsToeplitzMatrix(int[][] matrix)
{
int rows = matrix.Length;
int cols = matrix[0].Length;
for (int i = 0; i < rows - 1; i++)
{
for (int j = 0; j < cols - 1; j++)
{
// Compare current element with the diagonal element
if (matrix[i][j] != matrix[i + 1][j + 1])
{
return false; // Not a Toeplitz matrix
}
}
}
return true; // It is a Toeplitz matrix
}
public static void Main(string[] args)
{
int[][] matrix = new int[][]
{
new int[] { 1, 2, 3, 4 },
new int[] { 5, 1, 2, 3 },
new int[] { 6, 5, 1, 2 }
};
bool result = IsToeplitzMatrix(matrix);
Console.WriteLine($"Is the matrix a Toeplitz matrix? {result}");
}
}
Explanation
-
Data Structure:
- The matrix is represented as a jagged array (
int[][]
), where each inner array represents a row in the matrix.
- The matrix is represented as a jagged array (
-
IsToeplitzMatrix Method:
- This method checks whether the matrix is a Toeplitz matrix.
- It uses nested loops to iterate through the matrix, stopping one row and one column before the end (to avoid out-of-bounds access).
- For each element at
(i, j)
, it compares it to the element at(i + 1, j + 1)
. If they are not equal, it returnsfalse
, indicating the matrix is not Toeplitz. - If all comparisons pass, it returns
true
.
-
Main Method:
- It initializes a sample matrix and calls the
IsToeplitzMatrix
method. - Finally, it prints whether the matrix is a Toeplitz matrix.
- It initializes a sample matrix and calls the
Complexity
- Time Complexity: O(m * n), where
m
is the number of rows andn
is the number of columns, as we check almost every element once. - Space Complexity: O(1) since we are using a constant amount of additional space for variables.
Output
When you run the program, it will display:
Is the matrix a Toeplitz matrix? True
This implementation effectively checks whether a matrix is a Toeplitz matrix by comparing the necessary elements in a straightforward manner.