C++でべき等行列を判定するプログラムの作成方法

行数を r、列数を c とする行列 M[r][c] が与えられ、r = c となる正方行列を考えます。この記事では、与えられた正方行列がべき等行列(アイデンポテント行列)であるかどうかを判定するC++プログラムを解説します。

べき等行列とは

行列 M がべき等行列であるとは、行列 M と自分自身の積が元の行列 M と等しくなること、すなわち M × M = M が成り立つことを指します。

例えば、次の行列を見てください。

この行列を自分自身で掛け合わせても、結果は元の行列とまったく同じになります。したがって、この行列はべき等行列であると言えます。

べき等行列の代表的な例としては、ベクトルを部分空間へ射影する射影行列が挙げられます。また、べき等行列の固有値は必ず 0 または 1 になるという性質も知られています。

入力例と出力例

入力: m[3][3] = { {2, -2, -4},
    {-1, 3, 4},
    {1, -2, -3}}
出力: べき等行列である

入力: m[3][3] = { {3, 0, 0},
    {0, 2, 0},
    {0, 0, 3} }
出力: べき等行列ではない

アルゴリズム

開始
ステップ1 → マクロを定義する:#define size 3
ステップ2 → 行列の積を計算する関数を宣言する
    void multiply(int arr[][size], int res[][size])
        int i = 0 から i < size まで繰り返す
            int j = 0 から j < size まで繰り返す
                res[i][j] = 0 とする
                int k = 0 から k < size まで繰り返す
                    res[i][j] += arr[i][k] * arr[k][j]
                繰り返し終了
            繰り返し終了
        繰り返し終了
ステップ3 → べき等行列かどうかを判定する関数を宣言する
    bool check(int arr[][size])
    int res[size][size] を宣言する
    multiply(arr, res) を呼び出す
        int i = 0 から i < size まで繰り返す
            int j = 0 から j < size まで繰り返す
                もし (arr[i][j] != res[i][j]) ならば
                    false を返す
                終了
            繰り返し終了
        繰り返し終了
    true を返す
ステップ4 → main() 内で
    int arr[size][size] = {{1, -1, -1},
        {-1, 1, 1},
        {1, -1, -1}} を宣言する
    もし (check(arr)) ならば
        「べき等行列です」と出力する
    そうでなければ
        「べき等行列ではありません」と出力する
終了

C++での実装例

#include<bits/stdc++.h>
#define size 3
using namespace std;
// 行列の積を計算する
void multiply(int arr[][size], int res[][size]){
    for (int i = 0; i < size; i++){
        for (int j = 0; j < size; j++){
            res[i][j] = 0;
            for (int k = 0; k < size; k++)
                res[i][j] += arr[i][k] * arr[k][j];
        }
    }
}
// べき等行列かどうかを判定する
bool check(int arr[][size]){
    int res[size][size];
    multiply(arr, res);
    for (int i = 0; i < size; i++)
    for (int j = 0; j < size; j++)
        if (arr[i][j] != res[i][j])
            return false;
    return true;
}
int main(){
    int arr[size][size] = {{1, -1, -1},
        {-1, 1, 1},
        {1, -1, -1}};
    if (check(arr))
        cout << "べき等行列です";
    else
        cout << "べき等行列ではありません";
    return 0;
}

実行結果

べき等行列です

計算量について

このプログラムでは、行列の積の計算に3重のループを使用しているため、時間計算量は O(n³) となります(n は行列の次元)。また、計算結果を格納するための2次元配列が別途必要となるため、空間計算量は O(n²) です。

まとめ

このように、行列を自分自身で掛けた結果を元の行列と要素ごとに比較することで、べき等行列かどうかを簡単に判定できます。射影行列をはじめ、べき等行列は線形代数や統計学のさまざまな場面で登場する重要な概念です。ぜひこの判定方法をマスターしておきましょう。