Toeplitz matrix problem in C#

Programming C#
1

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

  1. Data Structure:

    • The matrix is represented as a jagged array (int[][]), where each inner array represents a row in the matrix.

  2. 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 returns false, indicating the matrix is not Toeplitz.
    • If all comparisons pass, it returns true.

  3. Main Method:

    • It initializes a sample matrix and calls the IsToeplitzMatrix method.
    • Finally, it prints whether the matrix is a Toeplitz matrix.

Complexity

  • Time Complexity: O(m * n), where m is the number of rows and n 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.