Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 멱등 행렬(Idempotent Matrix) 판별하기: 개념, 알고리즘, 구현 예제

행렬 M[r][c]가 주어졌을 때 'r'은 행(row)의 개수, 'c'는 열(column)의 개수를 의미하며, r = c일 때 이를 정방행렬(스퀘어 행렬)이라고 합니다. 이 글에서는 주어진 정방행렬이 멱등 행렬(Idempotent Matrix)인지 아닌지 판별하는 프로그램을 C++로 작성해 보겠습니다.

멱등 행렬(Idempotent Matrix)이란?

행렬 'M'에 자기 자신을 곱했을 때 그 결과가 원래의 행렬 'M'과 동일하다면, 즉 M × M = M이 성립할 때 이 행렬을 멱등 행렬이라고 부릅니다.

아래 예시를 살펴보겠습니다.

C++로 멱등 행렬(Idempotent Matrix) 판별하기: 개념, 알고리즘, 구현 예제

위 행렬에 자기 자신을 곱해도 동일한 행렬이 반환되므로, 이 행렬은 멱등 행렬입니다.

예제

입력: m[3][3] = { {2, -2, -4},
   {-1, 3, 4},
   {1, -2, -3}}
출력: 멱등 행렬(Idempotent)

입력: m[3][3] = { {3, 0, 0},
   {0, 2, 0},
   {0, 0, 3} }
출력: 멱등 행렬 아님(Not Idempotent)

알고리즘

시작
1단계 → 매크로를 #define size 3으로 정의한다
2단계 → 행렬 곱셈용 함수를 선언한다
   void multiply(int arr[][size], int res[][size])
      int i = 0; i < size; i++ 반복
         int j = 0; j < size; j++ 반복
            res[i][j] = 0으로 초기화
            int k = 0; k < size; k++ 반복
               res[i][j] += arr[i][k] * arr[k][j]
            반복 종료
         반복 종료
      반복 종료
3단계 → 멱등 행렬 여부를 확인하는 함수를 선언한다
   bool check(int arr[][size])
   int res[size][size] 선언
   multiply(arr, res) 호출
      int i = 0; i < size; i++ 반복
      int j = 0; j < size; j++ 반복
         IF (arr[i][j] != res[i][j])
            false 반환
         END IF
      반복 종료
      반복 종료
   true 반환
4단계 → main() 함수에서
   int arr[size][size] = {{1, -1, -1},
      {-1, 1, 1},
      {1, -1, -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]){
   int res[size][size];
   multiply(arr, res);
   for (int i = 0; i < size; i++)
   for (int j = 0; j < size; j++)
      if (arr[i][j] != res[i][j])
         return false;
   return true;
}

int main(){
   int arr[size][size] = {{1, -1, -1},
      {-1, 1, 1},
      {1, -1, -1}};
   if (check(arr))
      cout << "멱등 행렬입니다";
   else
      cout << "멱등 행렬이 아닙니다";
   return 0;
}

실행 결과

멱등 행렬입니다

시간 복잡도 및 공간 복잡도

n×n 크기의 행렬 두 개를 곱해야 하므로 이 알고리즘의 시간 복잡도는 O(n³)입니다. 공간 복잡도는 곱셈 결과를 저장하기 위한 추가 행렬 때문에 O(n²)입니다.

참고: 멱등 행렬의 성질

멱등 행렬은 선형대수학에서 중요하게 다루어지는 행렬로, 다음과 같은 성질을 가집니다.

  • 멱등 행렬의 고유값(eigenvalue)은 항상 0 또는 1입니다.
  • 단위 행렬(I)과 영행렬(O)은 모두 멱등 행렬입니다.
  • 멱등 행렬은 대각화 가능하며, 통계학에서는 사영 행렬(projection matrix)로 활용됩니다.