C++で行列が対称行列かどうかを判定するプログラム

対称行列とは

線形代数において、行列 M[][] が「対称行列（symmetric matrix）」であるとは、その転置行列が元の行列と完全に等しい場合を指します。転置行列とは、行列を対角線を軸として裏返す操作であり、これにより行と列のインデックスが入れ替わります。

以下に対称行列の例を示します。

$$\begin{bmatrix} 1 & 4 & 7 \\ 4 & 5 & 6 \\ 7 & 6 & 9 \\ \end {bmatrix} \Rightarrow \begin{bmatrix} 1 & 4 & 7 \\ 4 & 5 & 6 \\ 7 & 6 & 9 \\ \end{bmatrix}$$

上記の行列は対称行列です。左側の行列を転置しても、結果は元の行列と同一になるためです。対称行列では、必ず M[i][j] = M[j][i] という性質が成り立ちます。

入力例と出力例

入力: arr1[][n] = { { 1, 2, 3 },
   { 2, 2, 4 },
   { 3, 4, 1 } };
出力: 対称行列です

入力: arr1[][n] = { { 1, 7, 3 },
   { 2, 9, 5 },
   { 4, 6, 8 } };
出力: 対称行列ではありません

アプローチ

対称行列の判定は、以下の手順に従うことで実現できます。

• 手順1: 入力行列を受け取り、その転置行列を別の行列に格納します。
• 手順2: 得られた転置行列と元の入力行列を比較し、すべての要素が一致するかどうかを確認します。

なお、実際には転置行列を明示的に作成しなくても、「arr1[i][j] == arr1[j][i]」の条件を直接チェックするだけで判定することも可能です。ここでは、アルゴリズムの理解を助けるために転置行列を作成する方法を採用します。

アルゴリズム

開始
ステップ1 -> マクロを定義: #define n 10
ステップ2 -> 行列の転置を求める関数を宣言
   void transpose(int arr1[][n], int arr2[][n], int a)
      ループ: int i = 0 から i < a まで i++
         ループ: int j = 0 から j < a まで j++
           arr2[i][j] = arr1[j][i] を設定
      終了
   終了
ステップ3 -> 対称行列かどうかを判定する関数を宣言
   bool check(int arr1[][n], int a)
   変数 int arr2[a][n] を宣言
   transpose(arr1, arr2, a) を呼び出す
   ループ: int i = 0 から i < a まで i++
      ループ: int j = 0 から j < a まで j++
         IF (arr1[i][j] != arr2[i][j]) の場合
           false を返す
         終了
      終了
   終了
   true を返す
ステップ4 -> main() 内で
   変数 int arr1[][n] = { { 1, 2, 3 },
      { 2, 2, 4 },
      { 3, 4, 1 } } を宣言
   IF (check(arr1, 3)) の場合
      「対称行列です」と出力
   それ以外の場合
      「対称行列ではありません」と出力
終了

C++実装コード

#include <iostream>
#define n 10
using namespace std;
// 行列の転置を求める関数
void transpose(int arr1[][n], int arr2[][n], int a){
   for (int i = 0; i < a; i++)
      for (int j = 0; j < a; j++)
         arr2[i][j] = arr1[j][i];
}
// 対称行列かどうかを判定する関数
bool check(int arr1[][n], int a){
   int arr2[a][n];
   transpose(arr1, arr2, a);
   for (int i = 0; i < a; i++)
      for (int j = 0; j < a; j++)
         if (arr1[i][j] != arr2[i][j])
            return false;
   return true;
}
int main(){
   int arr1[][n] = { { 1, 2, 3 },
      { 2, 2, 4 },
      { 3, 4, 1 } };
   if (check(arr1, 3))
      cout << "対称行列です";
   else
      cout << "対称行列ではありません";
   return 0;
}

出力結果

対称行列です

計算量について

このプログラムの時間計算量は O(n²) です。転置行列の作成に n² 回、比較処理にも n² 回のループが必要となるためです。空間計算量も転置行列を保存するために O(n²) となります。メモリ使用量を抑えたい場合は、転置行列を作成せずに入力行列内で arr1[i][j] と arr1[j][i] を直接比較する方法がおすすめです。この場合、空間計算量は O(1) に抑えられます。