C++で与えられた行列がテプリッツ行列かどうかを判定する方法

問題の概要

この記事では、サイズ n×n の2次元正方行列 mat[][] が与えられたとき、その行列がテプリッツ（Toeplitz）行列であるかどうかを判定する方法を解説します。

テプリッツ行列とは？

テプリッツ行列とは、左上から右下に向かうすべての斜め線（対角線）上の要素が同じ値になる行列のことです。数式で表すと、任意の i, j に対して次の関係が常に成り立ちます。

mat[i][j] == mat[i+1][j+1]

具体例で理解しよう

入力：

Mat[][] = {{6, 7, 8, 9},
           {4, 6, 7, 8},
           {1, 4, 6, 7},
           {0, 1, 4, 6}}

出力： Yes

説明：

この行列では、左上から右下へ向かう各対角線上の値が一致しています。

• (0,0)→(1,1)→(2,2)→(3,3)：6, 6, 6, 6
• (0,1)→(1,2)→(2,3)：7, 7, 7
• (1,0)→(2,1)→(3,2)：4, 4, 4

すべての対角線で値が一定であるため、この行列はテプリッツ行列だと判定できます。

解法アプローチ

最もシンプルな解法は、各要素とその右下の隣接要素を順番に比較することです。すべての組み合わせが一致すればテプリッツ行列であり、1つでも不一致が見つかればそうではありません。

具体的には、i を 0 から n-2 まで、j を 0 から n-2 まで動かしながら、mat[i][j] と mat[i+1][j+1] が等しいかどうかを確認します。

ソリューションの実装例

#include <iostream>
using namespace std;
#define N 4

bool isToeplizMatrix(int mat[N][N])
{
    // 各要素をその右下の要素と比較する
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N - 1; j++)
        {
            if (mat[i][j] != mat[i + 1][j + 1]) {
                return false;
            }
        }
    }
    return true;
}

int main(){

    int mat[N][N] = { { 6, 7, 8, 9 },
                      { 4, 6, 7, 8 },
                      { 1, 4, 6, 7 },
                      { 0, 1, 4, 6 }};

    if (isToeplizMatrix(mat))
        cout<<"Matrix is a Toepliz matrix.";
    else
        cout<<"Matrix is not a Toepliz matrix.";

    return 0;
}

実行結果

Matrix is a Toepliz matrix.

計算量の分析

• 時間計算量：O(n²) ― 行列のほぼすべての要素を一度ずつ比較するため
• 空間計算量：O(1) ― 追加のメモリ領域は不要

まとめ

テプリッツ行列の判定は「各要素とその右下の要素が一致するか」というシンプルな条件で実現できます。二重ループによる O(n²) のアルゴリズムで効率的に判定でき、画像処理や信号処理などで利用されるテプリッツ構造の検証にも応用できます。