C++で対合行列（インボリュートリー行列）を判定するプログラムの実装方法

行列 M[r][c] が与えられたとき、「r」は行数、「c」は列数を表します。ここでは r = c、つまり正方行列である場合を考えます。この記事では、与えられた正方行列が対合行列（インボリュートリー行列）であるかどうかを判定する方法を解説します。

対合行列とは

対合行列とは、ある行列を自分自身と掛け合わせたとき、その積が単位行列になるような行列のことです。単位行列 I とは、主対角成分がすべて 1 で、それ以外の要素がすべて 0 である行列を指します。

したがって、行列 M が対合行列であるための必要十分条件は次のように表せます。

M × M = I

ここで、M は任意の行列、I は単位行列です。

以下の例を見てみましょう。

この例では、行列を自分自身で掛け合わせた結果が単位行列になっています。そのため、この行列は対合行列であると言えます。

入力例と出力例

入力: { {1, 0, 0},
   {0, -1, 0},
   {0, 0, -1}}
出力: yes

入力: { {3, 0, 0},
   {0, 2, 0},
   {0, 0, 3} }
出力: no

1つ目の例では、行列の2乗が単位行列になるため「yes」となります。一方、2つ目の例では対角成分が3や2であり、2乗しても単位行列にはならないため「no」が出力されます。

アルゴリズム

開始
ステップ1 → マクロを定義する：#define size 3
ステップ2 → 行列の掛け算を行う関数を宣言する。
   void multiply(int arr[][size], int res[][size])
      i = 0 から i < size までループ
         j = 0 から j < size までループ
            res[i][j] = 0 を設定
            k = 0 から k < size までループ
               res[i][j] += arr[i][k] * arr[k][j]
            ループ終了
         ループ終了
      ループ終了
ステップ3 → 対合行列かどうかを判定する関数を宣言する。
   bool check(int arr[size][size])
   int res[size][size] を宣言
   multiply(arr, res) を呼び出す
   i = 0 から i < size までループ
      j = 0 から j < size までループ
         IF (i == j && res[i][j] != 1)
            false を返す
         終了
         IF (i != j && res[i][j] != 0)
            false を返す
         終了
      ループ終了
   ループ終了
   true を返す
ステップ4 → main() 内で処理を行う。
   int arr[size][size] = { { 1, 0, 0 },
      { 0, -1, 0 },
      { 0, 0, -1 } } を宣言
   IF (check(arr))
      「対合行列です」と出力
   ELSE
      「対合行列ではありません」と出力
終了

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][size]){
   int res[size][size];
   multiply(arr, res);
   for (int i = 0; i < size; i++){
      for (int j = 0; j < size; j++){
         if (i == j && res[i][j] != 1)
            return false;
         if (i != j && res[i][j] != 0)
            return false;
      }
   }
   return true;
}
int main(){
   int arr[size][size] = { { 1, 0, 0 },
      { 0, -1, 0 },
      { 0, 0, -1 } };
   if (check(arr))
      cout << "its an involutory matrix";
   else
      cout << "its not an involutory matrix";
   return 0;
}

出力結果

its an involutory matrix

まとめ

このプログラムでは、まず与えられた正方行列を自分自身と掛け合わせ、その結果が単位行列と一致するかどうかを確認しています。計算量は O(n³) となり、行列のサイズが大きくなると処理時間が増加しますが、小規模な行列であれば十分に高速に動作します。対合行列は線形代数における重要な概念の一つであり、変換の反復適用などさまざまな場面で応用されています。