【C言語】行列が特異行列かどうかを判定するプログラムの書き方

行列を mat[行][列] の形式で与えたとき、関数を使ってその行列が「特異行列」かどうかを判定し、結果を表示するのが本記事の目的です。

特異行列とは、行列式（determinant）が 0 になる行列のことを指します。逆に、行列式が 0 でない行列は「非特異行列（正則行列）」と呼ばれます。

したがって、行列が特異かどうかを調べるには、まず行列式を計算する必要があります。3×3 行列の行列式は、次の式で求められます。

$$M1[3][3]\:=\:\begin{bmatrix}a & b & c \\d & e & f \\g & h & i \end{bmatrix}$$

|m1| = a(e×i − f×h) − b(d×i − f×g) + c(d×h − e×g)

入力例

入力 -: mat[3][3]= { 4, 10, 1 },
    { 0, 2, 3 },
    { 1, 4, -3 }
出力 -: 非特異行列である

入力 -: mat[3][3]= { 0, 0, 0 },
    { 10, 20, 30 },
    { 1, 4, -3 }
出力 -: 特異行列である
最初の行がすべて 0 のため、行列式は必ず 0 になります

アルゴリズム

開始
関数 cofactor(int matrix[N][N], int matrix2[N][N], int p, int q, int n)
{
    ステップ 1-> i = 0, j = 0, row, col を宣言・初期化
    ステップ 2-> row = 0 ～ row < n まで row++ のループ
    col = 0 ～ col < n まで col++ のループ
        if (row != p && col != q) の場合、
        matrix2[i][j++] に matrix[row][col] を代入
            j == n - 1 の場合、
                j = 0 に設定し、i を 1 増やす
        ループ終了
関数 int check_singular(int matrix[N][N], int n)
    ステップ 1-> int D = 0 を宣言・初期化
    ステップ 2-> n == 1 の場合、
        matrix[0][0] を返す
    ステップ 3-> matrix2[N][N]、sign = 1 を宣言
    ステップ 4-> f = 0 ～ f < n まで f++ のループ
        cofactor(matrix, matrix2, 0, f, n) を呼び出す
        D += sign * matrix[0][f] * check_singular(matrix2, n - 1)
        sign = -sign に設定（符号を交互に入れ替える）
    ループ終了
    ステップ 5-> D を返す
main()
    ステップ 1-> matrix[N][N] を宣言・初期化
    ステップ 2-> check_singular(matrix, N) の戻り値が 0 の場合、
        「Matrix is Singular」と表示
    ステップ 3-> それ以外の場合、
        「Matrix is non-Singular」と表示
終了

C言語での実装例

#include <stdio.h>
#define N 4
// 余因子を求める関数
int cofactor(int matrix[N][N], int matrix2[N][N], int p, int q, int n) {
    int i = 0, j = 0;
    int row, col;
    // 行列の各要素に対してループ処理を行う
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            // 指定された行・列に含まれない要素だけを
            // 一時的な行列へコピーする
            if (row != p && col != q) {
                matrix2[i][j++] = matrix[row][col];
                // 1 行分のコピーが完了したら、
                // 行インデックスを進め、列インデックスをリセットする
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
    return 0;
}
/* matrix[][] が特異行列かどうかを再帰的に判定する関数 */
int check_singular(int matrix[N][N], int n) {
    int D = 0; // 結果の初期化
    // 基底ケース：行列の要素が 1 つだけの場合
    if (n == 1)
    return matrix[0][0];
    int matrix2[N][N]; // 余因子を格納するための行列
    int sign = 1; // 符号の係数を保持
    // 1 行目の各要素について繰り返す
    for (int f = 0; f < n; f++) {
        // matrix[0][f] の余因子を取得
        cofactor(matrix, matrix2, 0, f, n);
        D += sign * matrix[0][f] * check_singular(matrix2, n - 1);
        // 各項は符号を交互に変えながら加算する
        sign = -sign;
    }
    return D;
}
// 上記の関数をテストするドライバプログラム
int main() {
    int matrix[N][N] = { { 4, 10, 1 },
    { 0, 2, 3 },
    { 1, 4, -3 } };
    if (check_singular(matrix, N) == 0)
        printf("Matrix is Singular\n");
    else
        printf("Matrix is non-Singular\n");
    return 0;
}

実行結果

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

Matrix is non-Singular

解説

このプログラムでは、余因子展開（cofactor expansion）を用いて行列式を再帰的に計算しています。1 行目の各要素について、その行と列を取り除いた小行列の余因子を求め、符号（＋と−）を交互に付けながら掛け合わせていくことで、任意のサイズ n の正方行列の行列式を求められます。

計算結果の行列式 D が 0 であれば特異行列、0 以外であれば非特異行列と判定できます。なお、この再帰的な手法は理解しやすい反面、計算量が O(n!) と大きいため、大規模な行列を扱う場合は LU 分解などの効率的な手法を検討するとよいでしょう。