C++で行列の基底と次元を求めるプログラムの作り方

本記事では、行列の基底(basis)と次元(dimension)を求めるためのC++プログラムを紹介します。

基底と次元とは

線形代数における基底とは、ベクトル空間全体を張る線形独立なベクトルの集合のことです。そして次元とは、その基底に含まれるベクトルの個数を指します。

n個のベクトルがR^n(n次元実ベクトル空間)の基底を成すかどうかは、それらを並べてできるn次正方行列の行列式を計算すれば判定できます。行列式が0でなければベクトル群は線形独立であり、R^nの基底となります。逆に行列式が0であれば、ベクトル群は線形従属のため基底にはなりません。

アルゴリズム

このプログラムでは、determinant()関数が余因子展開を用いて行列式を再帰的に計算します。処理の流れは以下の通りです。

Begin
   関数 determinant():
   行列の行列式を計算する。
   /*
      引数:
      n = 行列のサイズ(次数)
      matrix[10][10] = 入力行列
   */
   部分行列 submatrix[10][10] を宣言する。
   // 関数の本体:
   if (n == 2)
      return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1]))
   else
      c = 0 から n-1 までの for ループを作る
         submati = 0 と submatj を宣言・初期化する
         i = 1 から n-1 までの for ループを作る
            subj = 0 で初期化する
            j = 0 から n-1 までの for ループを作る
               if (j == c)
                  continue
               submatrix[submati][submatj] = matrix[i][j] を代入する
               subj をインクリメントする
         submati をインクリメントする
      d = d + (pow(-1, c) * matrix[0][c] * determinant(n-1, submatrix)) を計算する
End

サンプルコード

#include<iostream>
#include<math.h>
using namespace std;
double d = 0;
double determinant(int n, double matrix[10][10]) {
   double submatrix[10][10];
   if (n == 2)
      return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] *
      matrix[0][1]));
   else {
      for (int c = 0; c < n; c++) {
         int submati = 0, submatj;
         for (int i = 1; i < n; i++) {
            int subj = 0;
            for (int j = 0; j < n; j++) {
               if (j == c)
                  continue;
               submatrix[submati][submatj] = matrix[i][j];
               subj++;
            }
            submati++;
         }
         d = d + (pow(-1, c) * matrix[0][c] * determinant(n -
         1, submatrix));
      }
   }
   return d;
}
int main(int argc, char **argv) {
   cout << "要素数を入力してください:\n";
   int n;
   cin >> n;
   double matrix[10][10];
   cout << "要素を1つずつ入力してください:\n";
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         cin >> matrix[j][i];
      }
   }
   d = determinant(n, matrix); // 関数の呼び出し
   if (d != 0)
      cout << "行列式が0でないため、これらの要素はR" << n << "の基底を形成します";
   else
      cout << "行列式が0のため、これらの要素はR" << n << "の基底を形成しません";
}

コードの解説

• determinant()関数: 余因子展開により行列式を再帰的に計算します。nが2の場合は、2×2行列の公式(ad − bc)をそのまま返します。
• 部分行列 submatrix: 注目している列を除いた小行列を作るために使用され、再帰計算のたびにサイズが1つずつ縮まっていきます。
• main()関数: 行列のサイズnと各要素を入力として受け取り、determinant()を呼び出して行列式を求めます。結果が非ゼロなら「R^nの基底を形成する」、ゼロなら「形成しない」と出力します。

実行結果1

要素数を入力してください:
3
要素を1つずつ入力してください:
7 6 1
2 3 4
5 8 9
行列式が0でないため、これらの要素はR3の基底を形成します

実行結果2

要素数を入力してください:
4
要素を1つずつ入力してください:
7 6 1 4
2 3 5 4
9 8 2 3
2 1 3 0
行列式が0のため、これらの要素はR4の基底を形成しません

まとめ

このプログラムのように、n次正方行列の行列式を求めれば、n個のベクトルがR^nの基底を成すかどうかを簡単に判定できます。行列式が非ゼロであればベクトル群は線形独立で空間の次元はnとなり、ゼロであれば線形従属のため基底にはなりません。