C++で行列が可逆（逆行列を持つ）かどうかを判定する方法

本記事では、与えられた行列が可逆（invertible、逆行列を持つ）かどうかをC++で判定する方法を解説します。

可逆行列の条件

ある行列 M の逆行列 M^-1 は、次の式で表されます。

$$M^{-1}=\frac{adj(M)}{|M|}$$

この式から分かるように、分母には行列式（determinant）が含まれています。したがって、行列Mの行列式が0以外（非ゼロ）である場合にのみ逆行列が存在し、行列式が0の場合は逆行列を求めることができません。

つまり、「行列が可逆かどうか」を判定するには、その行列式が非ゼロであるかを確認すればよいことになります。

行列式の求め方

行列式の計算は再帰的な処理として実装できます。具体的には以下の手順で行います。

• 元の行列から小行列（cofactor用の部分行列）を作成する
• 各小行列の行列式を再帰的に計算する
• その結果を用いて最終的な行列式を求める

C++での実装例

それでは、実際のコードを見てみましょう。ここでは4×4の正方行列を例に、行列式を再帰的に計算し、可逆性を判定しています。

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

// 小行列（余因子用の部分行列）を作成する関数
void findCoFactor(int mat[N][N], int mat2[N][N], int p, int q, int n) {
    int i = 0, j = 0;
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            if (row != p && col != q) {
                mat2[i][j++] = mat[row][col];
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}

// 行列式を再帰的に計算する関数
int getDeterminant(int mat[N][N], int n) {
    int determinant = 0;
    if (n == 1)
        return mat[0][0];
    int temp[N][N];
    int sign = 1;
    for (int f = 0; f < n; f++) {
        findCoFactor(mat, temp, 0, f, n);
        determinant += sign * mat[0][f] * getDeterminant(temp, n - 1);
        sign = -sign;
    }
    return determinant;
}

// 行列が可逆かどうかを判定する関数
bool isMatrixInvertible(int mat[N][N], int n) {
    if (getDeterminant(mat, N) != 0)
        return true;
    else
        return false;
}

int main() {
    int matrix[N][N] = {
        { 1, 0, 2, -1 },
        { 3, 0, 0, 5 },
        { 2, 1, 4, -3 },
        { 1, 0, 5, 0 }
    };
    if (isMatrixInvertible(matrix, N))
        cout << "The matrix is invertible";
    else
        cout << "The matrix is not invertible";
}

実行結果

The matrix is invertible

コードの解説

このプログラムは、主に3つの関数で構成されています。

• findCoFactor(): 指定した行と列を除外した小行列を生成します。余因子展開のために必要な処理です。
• getDeterminant(): 余因子展開を用いて行列式を再帰的に計算します。1次の行列に達した時点でその要素自体を返すことで再帰を終了します。符号は交互に入れ替わるため、sign 変数で管理しています。
• isMatrixInvertible(): 計算した行列式が0でなければ true（可逆）、0であれば false（不可逆）を返します。

なお、この再帰的な余因子展開による方法は理解しやすい反面、行列のサイズが大きくなると計算量が急増します（O(n!)程度）。大規模な行列に対しては、LU分解やガウスの消去法を用いた効率的な手法が推奨されます。