퍼머넌트

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

퍼머넌트는 n × n 행렬 A의 정의된 함수로, 대칭군 Sn의 모든 원소 σ에 대한 곱의 합으로 계산된다. 행렬식과 유사하지만 순열의 부호를 고려하지 않는다는 점에서 다르다. 퍼머넌트는 행렬의 행 또는 열의 순열에 불변하며, 행렬의 한 행 또는 열에 스칼라를 곱하면 퍼머넌스도 스칼라만큼 곱해진다. 삼각 행렬의 경우 대각선 항목의 곱과 같다. 퍼머넌트는 조합론, 양자장론, 보손 샘플링 등 다양한 분야에 응용되며, (0, 1) 행렬의 퍼머넌트는 많은 계산 문제의 해답을 찾는 데 사용될 수 있다. 퍼머넌트 계산은 행렬식 계산보다 어려우며, #P-완전 문제로 알려져 있다.

퍼머넌트

📚 더 읽어볼만한 페이지

순열 - 레비치비타 기호
레비치비타 기호는 n차원 공간에서 정의되는 완전 반대칭 텐서로, 순열의 부호에 따라 +1, -1, 0의 값을 가지며 벡터곱, 행렬식 계산 등 다양한 분야에서 활용된다.
순열 - 완전순열
완전순열은 집합의 순열 중 모든 원소가 원래 위치에 있지 않은 순열, 즉 고정점이 없는 순열을 의미하며, 크기가 n인 집합의 완전순열의 수는 준계승 !n으로 나타내고, 점화식 또는 포함-배제 원리로 계산하며, 몽모르 수라고도 불린다.
행렬론 - 행렬식
행렬식은 정사각 행렬에 대해 정의되는 값으로, 선형 방정식의 해를 구하고 선형 독립성을 확인하며 기저의 방향과 부피를 계산하는 데 사용되며, 가우스 소거법 등의 계산 기법과 가역성 판단, 고유값 연관성 등의 성질을 갖는다.
행렬론 - 행렬 분해
행렬 분해는 주어진 행렬을 특정 성질을 갖는 여러 행렬의 곱으로 표현하는 방법으로, 수치 해석에서 행렬 알고리즘 구현 및 선형 연립 방정식 해를 구하거나 행렬 특성 분석에 활용되며 LU 분해, QR 분해, 특잇값 분해 등이 있다.
대수학 - 다항식
다항식은 변수, 계수, 상수항으로 구성되어 덧셈, 뺄셈, 곱셈, 거듭제곱 연산으로 결합된 항들의 유한한 합으로 표현되는 식이며, 대수 방정식 해를 구하는 데 중요하고 현대 수학에서 폭넓게 활용된다.
대수학 - 상수
상수는 변하지 않는 일정한 값을 가지는 수로, 함수에서 변수와 대비되며 수식 내에서 고정된 값을 갖고, 원주율, 자연로그의 밑, 허수 i 등이 대표적인 예시이다.

1. 개요
2. 정의
3. 성질
4. 응용
5. (0, 1) 행렬의 퍼머넌트
6. 상계
7. 판데르발던 추측 (Van der Waerden's Conjecture)
8. 계산
9. 맥마흔 마스터 정리 (MacMahon Master Theorem)
10. 직사각 행렬의 퍼머넌트
11. 완전 대표계 (System of Distinct Representatives)

2. 정의

permanent^영어는 n×n 정사각행렬 A에 대하여 다음과 같이 정의된다.

: $\operatorname{perm}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$

여기서 합은 대칭군 S_n의 모든 원소 σ에 걸쳐 이루어진다. 즉, 숫자 1, 2, ..., n의 모든 순열에 걸쳐 이루어진다.

예를 들어, 2차 정사각행렬의 경우

: $\operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc,$

3차 정사각행렬의 경우

: $\operatorname{perm}\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh.$
이다.

행렬 A의 퍼머넌트는 행렬식과 달리, 순열의 부호를 고려하지 않는다.

행렬 A의 퍼머넌트는 per A, perm A, 또는 Per A로 표기하며, 때로는 인수를 괄호로 묶기도 한다. Minc는 직사각형 행렬의 퍼머넌트를 Per(A)로, 정사각 행렬의 퍼머넌트를 per(A)로 사용한다. Muir와 Metzler는 $\overset{+}{|}\quad \overset{+}{|}$ 표기법을 사용한다.

"퍼머넌트"라는 단어는 1812년 코시가 관련 유형의 함수에 대해 "fonctions symétriques permanentes"로 처음 사용했으며, Muir와 Metzler가 현대적이고 더 구체적인 의미로 사용했다.

3. 성질

퍼머넌트는 n개의 벡터를 인수로 받는 함수로 볼 때, 다중선형 맵이며 대칭 함수이다. 즉, 벡터의 순서를 바꿔도 결과는 변하지 않는다.

n차 정사각 행렬 A에 대해 다음 성질들이 성립한다:

* 행/열 치환 불변성: A의 행 또는 열을 임의로 치환해도 퍼머넌트 값은 변하지 않는다. 임의의 치환 행렬 P, Q에 대해 perm(A) = perm(PAQ)로 표현할 수 있다.
* 스칼라 곱: A의 한 행 또는 열에 스칼라 s를 곱하면, 퍼머넌트는 s⋅perm(A)가 된다.
* 전치 불변성: perm(A) = perm(A^T). 즉, 행렬을 전치해도 퍼머넌트 값은 변하지 않는다.

n차 정사각 행렬 A와 B에 대해 다음 덧셈 공식이 성립한다:

: $\operatorname{perm}\left(A + B\right) = \sum_{s,t} \operatorname{perm} \left(a_{ij}\right)_{i \in s, j \in t} \operatorname{perm} \left(b_{ij}\right)_{i \in \bar{s}, j \in \bar{t}}$

(s와 t는 {1,2,...,n}의 같은 크기의 부분 집합이며, $\bar{s}, \bar{t}$ 는 해당 집합 내에서의 여집합이다.)

* 삼각 행렬: A가 삼각 행렬이면, perm(A)는 대각선 항목의 곱과 같다.

: $\operatorname{perm}\left(A\right) = a_{11} a_{22} \cdots a_{nn} = \prod_{i=1}^n a_{ii}.$

* 곱셈 불가: 행렬식과 달리, 일반적으로 perm(AB) ≠ perm(A)perm(B)이다.

* 라플라스 전개: 행렬식과 유사하게, 퍼머넌트도 행, 열, 또는 대각선을 따라 전개할 수 있다. (단, 행렬식과 달리 부호는 붙지 않는다.)

4. 응용

퍼머넌트는 여러 분야에서 응용된다.

* 대칭 텐서: 힐베르트 공간의 대칭 텐서 거듭제곱 연구에서 자연스럽게 나타난다. 힐베르트 공간 $H$ 의 $k$ 번째 대칭 텐서 거듭제곱 $\vee^k H$ 에서, 내적은 다음과 같이 퍼머넌트로 표현된다.
: $\langle x_1 \vee x_2 \vee \cdots \vee x_k, y_1 \vee y_2 \vee \cdots \vee y_k\rangle = \operatorname{perm}\left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k$
* 사이클 커버: 정방 행렬 $A = (a_{ij})_{i,j=1}^n$ 은 가중 방향 그래프의 인접 행렬로 볼 수 있으며, 이때 $A$ 의 퍼머넌트는 방향 그래프의 모든 사이클 커버의 가중치 합과 같다.
* 완전 매칭: 이분 그래프의 인접 행렬 $A = (a_{ij})$ 에 대해, $A$ 의 퍼머넌트는 그래프의 모든 완전 매칭의 가중치 합과 같다.
* (0, 1) 행렬: (0, 1) 행렬의 퍼머넌트는 다양한 조합론 문제의 해를 나타낼 수 있다.
* 양자역학: 양자역학에서 보손의 그린 함수 계산, 보손 샘플링 시스템의 상태 확률 결정 등에 사용된다.

5. (0, 1) 행렬의 퍼머넌트

클래스 Ω(n,k)는 각 행과 열의 합이 k인 n차 (0, 1) 행렬의 집합으로 정의된다. 이 클래스에 속하는 모든 행렬 A는 perm(A) > 0을 만족한다.

사영 평면의 접속 행렬은 n > 1인 정수에 대해 Ω(n² + n + 1, n + 1)에 속한다. 가장 작은 사영 평면에 해당하는 퍼머넌트 값은 계산되었는데, n = 2, 3, 4일 때 각각 24, 3852, 18,534,400이다. n = 2인 사영 평면(파노 평면)의 접속 행렬을 Z라 하면, perm(Z) = 24 = |det(Z)|가 성립한다. 이는 Z가 순환 행렬이기 때문이며, 다음 정리에 따른 결과이다.

: A가 Ω(n,k)에 속하는 순환 행렬일 때, k > 3이면 perm(A) > |det(A)|이고, k = 3이면 perm(A) = |det(A)|이다. 또한 k = 3일 때, A는 행과 열의 치환을 통해 Z의 e개 복사본의 직접합 형태로 나타낼 수 있으며, 이 경우 n = 7e이고 perm(A) = 24^e이다.

6. 상계

브레그만-민크 부등식은 1963년 H. 민크가 제안하고, 1973년 L. M. 브레그만이 증명한 n × n (0, 1)-행렬의 퍼머넌트에 대한 상한을 제공한다. 만약 A가 각 1 ≤ i ≤ n에 대해 i번째 행에 r_i개의 1을 가진다면, 부등식은 다음과 같다.

: $\operatorname{perm} A \leq \prod_{i=1}^n (r_i)!^{1/r_i}.$

7. 판데르발던 추측 (Van der Waerden's Conjecture)

1926년, 판 데르 바르던은 모든 n × n 이중 확률 행렬의 퍼머넌트 최소값은 n!/nⁿ이며, 모든 항목이 1/n과 같은 행렬에서 달성된다고 추측했다. 이 추측은 1980년 B. 기레스, 1981년 G. P. 예고리체프와 D. I. 팔릭만에 의해 증명되었으며, 예고리체프의 증명은 알렉산드로프-펜켈 부등식을 응용했다. 예고리체프와 팔릭만은 이 업적으로 1982년 풀커슨 상을 수상했다.

8. 계산

퍼머넌트의 계산은 행렬식 계산보다 훨씬 어려운 것으로 알려져 있다. 행렬식은 가우스 소거법을 통해 다항 시간 내에 계산할 수 있지만, 퍼머넌트는 가우스 소거법으로 계산할 수 없다.

H. J. 라이저가 제시한 라이저의 방법은 포함-배제 공식에 기반하며, 가장 빠른 알고리즘 중 하나이다. $A_k$ 를 A에서 k개의 열을 삭제하여 얻은 행렬, $P(A_k)$ 를 $A_k$ 의 행 합의 곱, $\Sigma_k$ 를 가능한 모든 $A_k$ 에 대한 $P(A_k)$ 값의 합이라고 하면, 라이저 공식은 다음과 같다.

$\operatorname{perm}(A)=\sum_{k=0}^{n-1} (-1)^{k} \Sigma_k.$

이는 행렬 항목을 사용하여 다음과 같이 표현할 수 있다.

$\operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^$

👆

좌우로 밀어서 보기

\prod_{i=1}^n \sum_{j\in S} a_{ij}.

(0,1)-행렬의 퍼머넌트 계산은 #P-완전 문제이다. 따라서 퍼머넌트를 다항 시간에 계산할 수 있다면, FP = #P가 되며, 이는 P = NP보다 더 강력한 명제이다.

하지만, A의 항목이 음수가 아닌 경우, 퍼머넌트는

\varepsilon M

의 오차까지 근사적으로 확률적 다항 시간 내에 계산할 수 있다. 여기서

M

은 퍼머넌트의 값이고

\varepsilon > 0

는 임의의 값이다.

9. 맥마흔 마스터 정리 (MacMahon Master Theorem)

$A = (a_{ij})$ 를 차수 n의 정사각 행렬이라고 할 때, 다변수 생성 함수
: $F(x_1,x_2,\dots,x_n) = \prod_{i=1}^n \left ( \sum_{j=1}^n a_{ij} x_j \right ) = \left( \sum_{j=1}^n a_{1j} x_j \right ) \left ( \sum_{j=1}^n a_{2j} x_j \right ) \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right)$
를 생각하면, $F(x_1,x_2,\dots,x_n)$ 에서 $x_1 x_2 \dots x_n$ 의 계수는 perm(A)이다.

일반화로, n개의 음이 아닌 정수 수열 $s_1,s_2,\dots,s_n$ 에 대해 $\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)$ 를
: $\left ( \sum_{j=1}^n a_{1j} x_j \right )^{s_1} \left ( \sum_{j=1}^n a_{2j} x_j \right )^{s_2} \cdots \left ( \sum_{j=1}^n a_{nj} x_j \right )^{s_n}$ 에서 $x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n}$ 의 계수로 정의한다.

맥마흔 마스터 정리는 퍼머넌트와 행렬식 사이의 관계를 나타내는 정리이다.

: $\operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A) = \text{ }x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} \text{ 의 계수 in } \frac{1}{\det(I - XA)}$

여기서 I는 차수 n의 항등 행렬이고, X는 대각선이 $[x_1,x_2,\dots,x_n]$ 인 대각 행렬이다.

10. 직사각 행렬의 퍼머넌트

m × n 행렬 $A = (a_{ij})$ (여기서 m ≤ n)에 대해 퍼머넌트를 다음과 같이 정의할 수 있다.

: $\operatorname{perm} (A) = \sum_{\sigma \in \operatorname{P}(n,m)} a_{1 \sigma(1)} a_{2 \sigma(2)} \ldots a_{m \sigma(m)}$

여기서 P(n,m)는 집합 {1,2,...,n}의 모든 m-순열의 집합이다.

라이저의 공식도 직사각 행렬에 대해 일반화될 수 있다. A가 m × n 행렬(m ≤ n)인 경우, $A_k$ 는 A에서 k개의 열을 삭제하여 얻고, $P(A_k)$ 는 $A_k$ 의 행 합의 곱이며, $\sigma_k$ 는 가능한 모든 $A_k$ 에 대한 $P(A_k)$ 값의 합이라고 하면, 다음이 성립한다.

: $\operatorname{perm}(A)=\sum_{k=0}^{m-1} (-1)^{k}\binom{n-m+k}{k}\sigma_{n-m+k}.$

11. 완전 대표계 (System of Distinct Representatives)

S₁, S₂, ..., S_m을 n-집합의 부분 집합(반드시 서로 다를 필요는 없음)이라고 하고, m ≤ n이라고 하자. 이 부분 집합 모음의 접속 행렬은 m × n(0,1)-행렬 A이다. 이 모음의 완전 대표계(SDR)의 수는 perm(A)이다.