선형대수학에서 기저(basis)는 벡터 공간 전체를 선형 결합으로 표현할 수 있으면서 서로 선형 독립인 벡터들의 집합을 의미하며, 차원(dimension)은 그 기저를 이루는 벡터의 개수를 뜻합니다. 정방행렬의 행렬식(determinant)이 0이 아니면, 해당 행렬의 열벡터들은 Rn 공간의 기저를 형성합니다.
아래는 이 원리를 이용해 주어진 행렬의 기저 여부를 판별하는 C++ 프로그램입니다. 프로그램은 재귀적으로 행렬식을 계산하고, 그 값이 0인지 아닌지에 따라 결과를 출력합니다.
알고리즘
시작
함수 determinant() :
행렬의 행렬식을 계산한다.
/*
매개변수:
n = 원소의 개수.
matrix[10][10] = 입력 행렬.
*/
부분행렬 submatrix[10][10]을 선언한다.
// 함수 본문:
if (n == 2)
return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] * matrix[0][1]))
else
c = 0부터 n-1까지 for 반복문 수행
submati = 0으로 선언 및 초기화, submatj 선언.
i = 1부터 n-1까지 for 반복문 수행
subj = 0으로 초기화
j = 0부터 n-1까지 for 반복문 수행
if (j == c)이면 continue
submatrix[submati][submatj] = matrix[i][j]
subj 증가
submati 증가
d = d + (pow(-1, c) * matrix[0][c] * determinant(n-1, submatrix)) 계산
종료알고리즘 설명
행렬식 계산 함수 determinant()는 여인자 전개(cofactor expansion) 방식을 사용합니다. 첫 번째 행을 기준으로 각 원소에 대해 부분행렬(submatrix)을 만들고, 부호 (-1)c를 곱한 뒤 재귀 호출로 부분행렬의 행렬식을 구해 모두 더합니다. 행렬의 크기가 2×2가 되면 공식 (ad − bc)로 바로 계산하여 재귀를 종료합니다.
예제 코드
#include<iostream>
#include<math.h>
using namespace std;
double d = 0;
double determinant(int n, double matrix[10][10]) {
double submatrix[10][10];
if (n == 2)
return ((matrix[0][0] * matrix[1][1]) - (matrix[1][0] *
matrix[0][1]));
else {
for (int c = 0; c < n; c++) {
int submati = 0,submatj;
for (int i = 1; i < n; i++) {
int subj = 0;
for (int j = 0; j < n; j++) {
if (j == c)
continue;
submatrix[submati][submatj] = matrix[i][j];
subj++;
}
submati++;
}
d = d + (pow(-1, c) * matrix[0][c] * determinant(n -
1, submatrix));
}
}
return d;
}
int main(int argc, char **argv) {
cout << "Enter the number of elements:\n";
int n;
cin >> n;
double matrix[10][10];
cout << "Enter elements one by one:\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[j][i];
}
}
d = determinant(n, matrix); //함수 호출
if (d != 0)
cout << "The elements form the basis of R" << n << " as the determinant is non-zero";
else
cout << "The elements don't form the basis of R" << n << " as the determinant is zero";
}코드 해설
메인 함수에서는 먼저 행렬의 크기 n을 입력받고, n×n 크기의 행렬 원소를 하나씩 입력받습니다. 이후 determinant() 함수를 호출해 행렬식을 계산한 뒤, 결과값이 0이 아니면 해당 원소들이 Rn의 기저를 이룬다고 출력하고, 0이면 기저를 이루지 못한다고 출력합니다.
실행 결과 1
Enter the number of elements: 3 Enter elements one by one: 7 6 1 2 3 4 5 8 9 The elements form the basis of R3 as the determinant is non-zero
3×3 행렬의 행렬식이 0이 아니므로, 세 열벡터는 R³ 공간의 기저를 형성하며 이 행렬의 차원은 3입니다.
실행 결과 2
Enter the number of elements: 4 Enter the elements one by one: 7 6 1 4 2 3 5 4 9 8 2 3 2 1 3 0 The elements don't form the basis of R4 as the determinant is zero
4×4 행렬의 행렬식이 0이므로, 네 열벡터 중 일부가 선형 종속 관계에 있어 R⁴ 공간의 기저를 형성하지 못합니다.