C++で特定の行列がハンケル行列かどうかを判定する方法

ハンケル行列（Hankel行列）とは、正方行列の一種で、左下から右上へ向かう各反対角線（スキュー対角線）上の要素が、すべて同じ値となる行列のことです。この記事では、与えられた正方行列がハンケル行列であるかどうかをC++で判定する方法を解説します。

まず、次のような5×5の行列を例に考えてみましょう。

この行列では、反対角線ごとに値が一定（例：1 ／ 2, 2 ／ 3, 3, 3 …）になっているため、ハンケル行列であることがわかります。

ハンケル行列の判定条件

ハンケル行列かどうかを判定するには、すべての要素について mat[i][j] = a_i+j が成り立つかどうかを確認します。ここで a_i+j は、添字 i + j の値に応じて次のように定義されます。

• i + j < n の場合：a_i+j = mat[i+j][0]（第0列の要素）
• それ以外の場合：a_i+j = mat[i+j-n+1][n-1]（最終列の要素）

つまり、各反対角線の基準値として行列の左端または右端の要素を参照し、その反対角線上の全要素が一致するかを調べます。1つでも不一致が見つかれば、その行列はハンケル行列ではありません。

C++での実装例

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

// 行列がハンケル行列かどうかを判定する関数
bool isHankelMat(int mat[N][N], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i + j < n) {
                // 左下側の反対角線：第0列の要素と比較
                if (mat[i][j] != mat[i + j][0])
                    return false;
            } else {
                // 右上側の反対角線：最終列の要素と比較
                if (mat[i][j] != mat[i + j - n + 1][n - 1])
                    return false;
            }
        }
    }
    return true;
}

int main() {
    int n = 5;
    int mat[N][N] = {
        { 1, 2, 3, 4, 5},
        { 2, 3, 4, 5, 6},
        { 3, 4, 5, 6, 7},
        { 4, 5, 6, 7, 8},
        { 5, 6, 7, 8, 9}
    };
    if(isHankelMat(mat, n))
        cout << "This is Hankel Matrix";
    else
        cout << "This is not Hankel Matrix";
}

実行結果

This is Hankel Matrix

計算量について

このアルゴリズムは行列の全要素を一度ずつ確認するため、時間計算量は O(n²) です。また、判定のために追加のメモリを必要としないため、空間計算量は O(1) となります。シンプルな二重ループで実装できるため、理解しやすく実用的な判定方法です。