C++で行列式を求める方法｜余因子展開を使った再帰的な実装を解説

行列式とは？

行列式は正方行列に対してのみ計算できる値です。1行目の各要素に、それに対応する余因子（小行列）の行列式を掛け合わせ、符号を交互につけながら足し合わせることで最終的な結果が得られます。この手法は「余因子展開（cofactor expansion）」と呼ばれます。

3×3の行列Aに対する行列式は、次のように表されます。

$$A = \begin{bmatrix}a & b & c\\d & e & f \\g & h & i\end{bmatrix}$$
$$|A| = a(ei-fh) - b(di-gf) + c(dh-eg)$$

この記事では、C++を使って再帰処理により任意の次元の正方行列の行列式を求める方法を解説します。

アルゴリズムの全体像

実装は主に以下の3つの関数で構成されます。

• determinantOfMatrix() — 行列式を再帰的に計算するメインの関数
• cofactor() — 指定した行・列を除いた小行列（余因子行列）を作成する関数
• display() — 行列の内容を出力する補助関数

determinantOfMatrix() 関数

まず、determinantOfMatrix(int mat[N][N], int dimension) は、対象の行列とその次元を受け取ります。次元が1の場合、つまり要素が1つだけの場合は mat[0][0] の値をそのまま返します。

この条件は再帰呼び出しの基底ケース（base case）としても機能します。再帰のたびに行列の次元を1ずつ減らしていくため、最終的に必ずこの条件に到達する仕組みです。

int determinantOfMatrix(int mat[N][N], int dimension){
    int Det = 0;
    if (dimension == 1)
        return mat[0][0];

余因子展開による再帰計算

続いて、cofactorMat[N][N] を宣言し、firstRow が dimension 未満である間、cofactor() 関数に渡していきます。各行の処理では、符号（sign）を交互に切り替えながら、第1行の要素と対応する余因子行列の行列式の積を Det 変数に加算していきます。

int cofactorMat[N][N];
int sign = 1;
for (int firstRow = 0; firstRow < dimension; firstRow++){
    cofactor(mat, cofactorMat, 0, firstRow, dimension);
    Det += sign * mat[0][firstRow] * determinantOfMatrix(cofactorMat, dimension - 1);
    sign = -sign;
}
return Det;
}

ここでのポイントは sign = -sign; の部分です。ループが1回回るごとに符号が反転することで、「+、−、+、…」という交互の符号が自動的に実現されます。

cofactor() 関数

cofactor(int mat[N][N], int temp[N][N], int p, int q, int n) は、元の行列・一時保存用の行列・除外する行 p・列 q・行列のサイズ n を引数として受け取ります。ネストされたforループで行列全体を走査し、行が p と一致せず、かつ列が q とも一致しない要素だけを temp 行列にコピーします。これにより、指定した行と列を取り除いた小行列が作られます。

void cofactor(int mat[N][N], int temp[N][N], int p,int q, int n){
    int i = 0, j = 0;
    for (int row = 0; row < n; row++){
        for (int column = 0; column < n; column++){
            if (row != p && column != q){
                temp[i][j++] = mat[row][column];

temp の1行が埋まったら、行インデックス i を進め、列インデックス j を先頭に戻します。

if (j == n - 1){
    j = 0;
    i++;
}

display() 関数

最後に、display(int mat[N][N], int row, int col) は行列と行数・列数を受け取り、2次元配列として走査しながら各行・各列の値を出力します。動作確認のためのシンプルな補助関数です。

void display(int mat[N][N], int row, int col){
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

完全なサンプルコード

以下に、行列の行列式を求める完全な実装例を示します。

#include <iostream>
using namespace std;
const int N = 3;

void cofactor(int mat[N][N], int temp[N][N], int p,int q, int n){
    int i = 0, j = 0;
    for (int row = 0; row < n; row++){
        for (int column = 0; column < n; column++){
            if (row != p && column != q){
                temp[i][j++] = mat[row][column];
                if (j == n - 1){
                    j = 0;
                    i++;
                }
            }
        }
    }
}

int determinantOfMatrix(int mat[N][N], int dimension){
    int Det = 0;
    if (dimension == 1)
        return mat[0][0];
    int cofactorMat[N][N];
    int sign = 1;
    for (int firstRow = 0; firstRow < dimension; firstRow++){
        cofactor(mat, cofactorMat, 0, firstRow, dimension);
        Det += sign * mat[0][firstRow] * determinantOfMatrix(cofactorMat, dimension - 1);
        sign = -sign;
    }
    return Det;
}

void display(int mat[N][N], int row, int col){
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++)
            cout<<mat[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}

int main(){
    int mat[3][3] = {
        { 1, 0, 2},
        { 3, 0, 0},
        { 2, 1, 4}};
    cout<<"The matrix is "<<endl;
    display(mat,3,3);
    cout<<"Determinant of the matrix is "<<determinantOfMatrix(mat, N);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

The matrix is
1 0 2
3 0 0
2 1 4

Determinant of the matrix is 6

まとめ

このように、余因子展開と再帰呼び出しを組み合わせることで、C++でも簡単に行列式を計算できます。ただし、この手法の計算量は O(n!) と非常に大きいため、大規模な行列を扱う場合はLU分解など計算量 O(n³) の手法を選ぶのが実用的です。学習目的や小さな行列の検証には、本記事の再帰的なアプローチが理解しやすくおすすめです。