C++로 인볼루토리 행렬(Involutory Matrix) 판별하기

행렬 M[r][c]가 주어졌을 때 'r'은 행(row)의 개수, 'c'는 열(column)의 개수를 의미하며, r = c일 때 정사각 행렬(square matrix)이 됩니다. 이 글에서는 주어진 정사각 행렬이 인볼루토리 행렬(Involutory Matrix)인지 아닌지 판별하는 방법을 알아보겠습니다.

인볼루토리 행렬이란?

행렬을 자기 자신과 곱했을 때 그 결과가 단위 행렬(identity matrix)이 되면, 그 행렬을 인볼루토리 행렬이라고 합니다. 행렬 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단계 → 매크로 정의: #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까지 반복
            만약 (i == j && res[i][j] != 1)이면
                false 반환
            만약 (i != j && res[i][j] != 0)이면
                false 반환
        반복문 종료
    반복문 종료
    true 반환
4단계 → main() 함수에서
    배열 선언: int arr[size][size] = { { 1, 0, 0 }, { 0, -1, 0 }, { 0, 0, -1 } }
    만약 check(arr)이 참이면
        "인볼루토리 행렬입니다" 출력
    그렇지 않으면
        "인볼루토리 행렬이 아닙니다" 출력
종료

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

프로그램을 실행하면 위와 같이 주어진 행렬이 인볼루토리 행렬이라는 결과가 출력됩니다.

시간 복잡도

행렬 곱셈에 세 개의 중첩 루프를 사용하므로, n×n 크기의 행렬 기준 시간 복잡도는 O(n³)입니다. 공간 복잡도는 곱셈 결과를 저장할 추가 배열 하나만 필요하므로 O(n²)입니다.