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

テプリッツ行列とは？

テプリッツ行列（Toeplitz行列）とは、左上から右下に向かうすべての対角線上の要素が同じ値である行列のことを指します。

例1：テプリッツ行列の場合

[[1,2,3,4],
[5,1,2,3],
[9,5,1,2]]

出力：

true

この行列の対角線は以下のようになっています。

"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".

それぞれの対角線上の要素はすべて同じ値であるため、この行列はテプリッツ行列であり、答えは true となります。

例2：テプリッツ行列でない場合

入力：matrix
[[1,2],
[2,2]]

出力：

false

この場合、対角線 "[1, 2]" の要素が異なる値（1と2）を持っているため、テプリッツ行列ではありません。

C#による判定コード

以下のコードでは、各行・各列の要素をその左上の要素と比較することで、すべての対角線が同一要素で構成されているかどうかを確認しています。

public class Matrix
{
    public bool ToeplitzMatrix(int[] mat)
    {
        int row = getMatrixRowSize(mat);
        int col = getMatrixColSize(mat);
        for (int i = 1; i < row; i++)
        {
            for (int j = 1; j < col; j++)
            {
                if (mat[i, j] != mat[i - 1, j - 1])
                {
                    return false;
                }
            }
        }
        return true;
    }
    private int getMatrixRowSize(int[] mat)
    {
        return mat.GetLength(0);
    }
    private int getMatrixColSize(int[] mat)
    {
        return mat.GetLength(1);
    }
}
static void Main(string[] args)
{
    Matrix m = new Matrix();
    int[] mat = new int[3, 4] { { 1, 2, 3, 4 }, { 5, 1, 2, 3 }, { 9, 5, 1, 2 } };
    Console.WriteLine(m.ToeplitzMatrix(mat));
}

実行結果

TRUE

アルゴリズムのポイント

この判定方法のポイントは、各要素をひとつ左上の要素と比較するだけでよいという点です。なぜなら、ある要素がその左上の要素と一致していれば、それは同じ対角線上にあることを意味するからです。計算量は O(row × col) となり、行列の全要素を一度ずつ確認するだけで効率的に判定できます。