Pythonで与えられた行列がテプリッツ行列かどうかを判定するプログラム

テプリッツ行列とは？

ある行列 M が与えられたとき、それがテプリッツ行列（Toeplitz matrix）であるかどうかを判定することを考えます。テプリッツ行列とは、左上から右下へ向かうすべての対角線（斜めの並び）上の要素が同じ値であるような行列のことです。

例として、次のような入力行列を考えてみましょう。

この行列では、どの対角線を見ても値が一定になっています。たとえば「7 → 7 → 7」「2 → 2」「3 → 3」といった具合です。したがって、この場合の出力は True となります。

判定アルゴリズムの考え方

テプリッツ行列の性質を利用すると、判定は非常にシンプルです。各要素は、そのすぐ右下の要素と必ず等しくなければなりません。そこで、次の手順で確認します。

• 最後の行を除く各行 i について繰り返す
  • 最後の列を除く各列 j について繰り返す
    • matrix[i][j] と matrix[i+1][j+1] が等しくない場合は、その時点で False を返す
• すべてのチェックを通過したら True を返す

この方法なら、行列内の隣接する対角要素だけを比較すればよいため、効率的に判定できます。

Pythonでの実装例

以下が実際の実装コードです。

class Solution:
   def solve(self, matrix):
      for i in range(len(matrix)-1):
         for j in range(len(matrix[0])-1):
            if matrix[i][j]!=matrix[i+1][j+1]:
               return False
      return True
ob = Solution()
matrix = [ [7, 2, 6], [3, 7, 2], [5, 3, 7]]
print(ob.solve(matrix))

入力

[[7, 2, 6],
[3, 7, 2],
[5, 3, 7]]

出力

True

計算量について

このアルゴリズムは、行列のすべての要素を一度ずつ調べるため、行数を m、列数を n とすると時間計算量は O(m × n) になります。追加のデータ構造を使わずに行内で判定できるため、空間計算量は O(1) と非常に効率的です。

まとめ

テプリッツ行列の判定は、「各要素とその右下の要素が等しいか」を全要素に対して確認するだけで実現できます。Pythonでは二重ループを使ったシンプルな実装で対応でき、面接や競技プログラミングでもよく出題される基本的な問題なので、ぜひ覚えておきましょう。