C++で行列が双対称行列かどうかを判定する方法

双対称行列とは？

本記事では、与えられた行列が「双対称行列（bisymmetric matrix）」であるかどうかを判定するC++プログラムを紹介します。

双対称行列とは、正方行列において主対角線（左上から右下への対角線）と反対角線（右上から左下への対角線）の両方に対して対称な行列のことです。言い換えると、通常の対称行列（転置しても元の行列と同じ）であり、同時に中心対称な行列でもあるものを指します。

以下の5×5の行列は、双対称行列の一例です。

1 2 3 4 5
2 6 7 8 4
3 7 9 7 3
4 8 7 6 2
5 4 3 2 1

アルゴリズム

checkBiSymmetric(mat, n)

判定は次の2段階のチェックで行います。

1. 主対角線に関する対称性の確認： mat[i][j] と mat[j][i] がすべて等しいかどうかを調べます。一致しない要素が見つかった時点で false を返します。
2. 反対角線に関する対称性の確認： mat[i][j] と mat[n-j-1][n-i-1] がすべて等しいかどうかを調べます。ここでも一致しない要素があれば false を返します。

両方のチェックを通過できた場合のみ、その行列は双対称行列であるとして true を返します。

開始
　　i を 0 から n-1 まで繰り返す：
　　　　j を 0 から i-1 まで繰り返す：
　　　　　　もし mat[i, j] と mat[j, i] が等しくなければ
　　　　　　　　false を返す
　　i を 0 から n-1 まで繰り返す：
　　　　j を 0 から n-i-1 まで繰り返す：
　　　　　　もし mat[i, j] と mat[n-j-1, n-i-1] が等しくなければ
　　　　　　　　false を返す
　　true を返す
終了

C++による実装例

#include<iostream>
#define N 5
using namespace std;
int matrix[N][N] = {{1, 2, 3, 4, 5},
{2, 6, 7, 8, 4},
{3, 7, 9, 7, 3},
{4, 8, 7, 6, 2},
{5, 4, 3, 2, 1}};
bool checkBiSymmetric() {
　　for (int i = 0; i < N; i++) // 主対角線に沿って走査
　　　　for (int j = 0; j < i; j++)
　　　　　　if (matrix[i][j] != matrix[j][i]) // 対応する要素が一致しなければfalseを返す
　　　　　　　　return false;
　　for (int i = 0; i < N; i++) // 反対角線に沿って走査
　　　　for (int j = 0; j < N - i; j++)
　　　　　　if (matrix[i][j] != matrix[N - j - 1][N - i - 1]) // 対応する要素が一致しなければfalseを返す
　　　　　　　　return false;
　　return true; // どちらの条件も満たしていればtrueを返す
}
main() {
　　if(checkBiSymmetric()){
　　　　cout << "はい、この行列は双対称です";
　　} else {
　　　　cout << "いいえ、この行列は双対称ではありません";
　　}
}

出力結果

はい、この行列は双対称です

計算量について

このアルゴリズムの計算量は O(n²) です。各チェックで行列の要素を最大1回ずつ参照するため、行列のサイズに比例した時間で効率的に判定できます。また、入力行列を書き換えないため、追加のメモリ領域もほとんど必要としません。