5 Best Ways to Check Whether a Given Matrix is Toeplitz in Python

πŸ’‘ Problem Formulation: In this article, we target the problem of verifying the Toeplitz matrix property within a given 2D matrix using Python. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements. Given an input matrix, we want to output a boolean indicating whether the matrix is Toeplitz or not.

Method 1: Iterative Comparison

This method involves iteratively comparing elements across descending diagonals from the top-left corner to the bottom-right corner of the matrix. The function will return False if it finds any diagonal with differing elements, otherwise it will return True.

Here’s an example:

def is_toeplitz(matrix):
    rows, cols = len(matrix), len(matrix[0])
    for row in range(rows-1):
        for col in range(cols-1):
            if matrix[row][col] != matrix[row+1][col+1]:
                return False
    return True

# Example matrix
matrix_example = [
    [1,2,3],
    [4,1,2],
    [5,4,1]
]

print(is_toeplitz(matrix_example))

Output: True

In this code snippet, we loop through the matrix with nested for-loops, but stop short of the last row and column to avoid index errors. The function compares the current element with the one diagonally below and to the right, returning False if they do not match, thus checking the Toeplitz property.

Method 2: Using NumPy Library

By utilizing the NumPy library, we can harness efficient array operations to validate the Toeplitz property. The method includes creating shifted versions of the original matrix and comparing them.

Here’s an example:

import numpy as np

def is_toeplitz_np(matrix):
    mat = np.array(matrix)
    for shift in range(1, mat.shape[0]):
        if not np.allclose(np.diag(mat, k=shift), np.diag(mat, k=-shift)):
            return False
    return True

# Example matrix
matrix_example = [
    [1,2,3],
    [4,1,2],
    [5,4,1]
]

print(is_toeplitz_np(matrix_example))

Output: True

The is_toeplitz_np function uses NumPy’s diag function to extract diagonals from the matrix at various offsets (both above and below the main diagonal). Then it uses np.allclose to test if the diagonals contain close or equal values, ensuring it accounts for possible floating-point errors.

Method 3: List Comprehension and All Function

This approach capitalizes on Python’s list comprehension and built-in all function to compare diagonals in a more concise and Pythonic manner. The method loops over each element only once and maintains readability.

Here’s an example:

def is_toeplitz_compact(matrix):
    return all(matrix[row][col] == matrix[row+1][col+1] for row in range(len(matrix) - 1) for col in range(len(matrix[0]) - 1))

# Example matrix
matrix_example = [
    [1,2,3],
    [4,1,2],
    [5,4,1]
]

print(is_toeplitz_compact(matrix_example))

Output: True

The is_toeplitz_compact function leverages a nested list comprehension to iterate through the elements and uses the all function to check if every diagonal element complies with the Toeplitz criteria. This makes for a clean and efficient solution.

Method 4: Zip and Slicing

This method uses a more functional programming approach by employing zip, slicing, and the all function to compare rows and diagonals after appropriately slicing the matrix.

Here’s an example:

def is_toeplitz_zip(matrix):
    return all(r1[:-1] == r2[1:] for r1, r2 in zip(matrix, matrix[1:]))

# Example matrix
matrix_example = [
    [1,2,3],
    [4,1,2],
    [5,4,1]
]

print(is_toeplitz_zip(matrix_example))

Output: True

The is_toeplitz_zip function pairs each row with the next one using zip and compares them after slicing off the ends to correspond to the diagonals. This method is both clean and highly readable, effectively utilizing Python’s built-in functionalities.

Bonus One-Liner Method 5: Itertools and All

This one-liner uses the itertools module to chain the rows together while comparing elements. It’s a compact and clever use of Python’s capabilities, suitable for those who enjoy a functional style in their code.

Here’s an example:

import itertools

is_toeplitz_itertools = lambda m: all(m[i][j] == m[i+1][j+1] for i, j in itertools.product(range(len(m)-1), range(len(m[0])-1)))

# Example matrix
matrix_example = [
    [1,2,3],
    [4,1,2],
    [5,4,1]
]

print(is_toeplitz_itertools(matrix_example))

Output: True

This compact lambda function utilizes itertools.product to create a cartesian product of indices, simulating the nested loops in a single line. This method provides a functional and extremely concise way to verify a Toeplitz matrix.

Summary/Discussion

  • Method 1: Iterative Comparison. Strengths: Simple to understand and implement. Weaknesses: Potentially slower for large matrices due to the nested loops.
  • Method 2: Using NumPy Library. Strengths: Leverages optimized array operations, easy to read. Weaknesses: Requires an additional library, may not be the most performant for small matrices.
  • Method 3: List Comprehension and All Function. Strengths: Pythonic and succinct, involves only a single pass. Weaknesses: Readability may suffer for those unfamiliar with list comprehensions.
  • Method 4: Zip and Slicing. Strengths: Elegant and functional programming-oriented solution, does efficient comparisons. Weaknesses: Might be less intuitive for newcomers.
  • Bonus Method 5: Itertools and All. Strengths: Extremely concise one-liner that demonstrates functional Python prowess. Weaknesses: Readability is low for those not accustomed to itertools or lambda functions.