퍼머넌트

3. 성질

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

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

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

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

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

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

4. 응용

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

• 대칭 텐서: 힐베르트 공간의 대칭 텐서 거듭제곱 연구에서 자연스럽게 나타난다.^[12] 힐베르트 공간 $H$의 $k$번째 대칭 텐서 거듭제곱 $\backslash vee^k\; H$에서, 내적은 다음과 같이 퍼머넌트로 표현된다.

• 사이클 커버: 정방 행렬 $A\; =\; (a\_\{ij\})\_\{i,j=1\}^n$은 가중 방향 그래프의 인접 행렬로 볼 수 있으며, 이때 $A$의 퍼머넌트는 방향 그래프의 모든 사이클 커버의 가중치 합과 같다.
• 완전 매칭: 이분 그래프의 인접 행렬 $A\; =\; (a\_\{ij\})$에 대해, $A$의 퍼머넌트는 그래프의 모든 완전 매칭의 가중치 합과 같다.
• (0, 1) 행렬: (0, 1) 행렬의 퍼머넌트는 다양한 조합론 문제의 해를 나타낼 수 있다.
• 양자역학: 양자역학에서 보손의 그린 함수 계산^[37], 보손 샘플링 시스템의 상태 확률 결정 등에 사용된다.^[37]

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

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

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

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

6. 상계

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

:$$\backslash operatorname\{perm\}\; A\; \backslash leq\; \backslash prod\_\{i=1\}^n\; (r\_i)!^\{1/r\_i\}.$$

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

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

8. 계산

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

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

$$\backslash operatorname\{perm\}(A)=\backslash sum\_\{k=0\}^\{n-1\}\; (-1)^\{k\}\; \backslash Sigma\_k.$$

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

$$\backslash operatorname\{perm\}\; (A)\; =\; (-1)^n\; \backslash sum\_\{S\backslash subseteq\backslash \{1,\backslash dots,n\backslash \}\}\; (-1)^$$

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

$A\; =\; (a\_\{ij\})$를 차수 ''n''의 정사각 행렬이라고 할 때, 다변수 생성 함수

:$F(x\_1,x\_2,\backslash dots,x\_n)\; =\; \backslash prod\_\{i=1\}^n\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{ij\}\; x\_j\; \backslash right\; )\; =\; \backslash left(\; \backslash sum\_\{j=1\}^n\; a\_\{1j\}\; x\_j\; \backslash right\; )\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{2j\}\; x\_j\; \backslash right\; )\; \backslash cdots\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{nj\}\; x\_j\; \backslash right)$

를 생각하면, $F(x\_1,x\_2,\backslash dots,x\_n)$에서 $x\_1\; x\_2\; \backslash dots\; x\_n$의 계수는 perm(''A'')이다.^[28]

일반화로, ''n''개의 음이 아닌 정수 수열 $s\_1,s\_2,\backslash dots,s\_n$에 대해 $\backslash operatorname\{perm\}^\{(s\_1,s\_2,\backslash dots,s\_n)\}(A)$를

:$\backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{1j\}\; x\_j\; \backslash right\; )^\{s\_1\}\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{2j\}\; x\_j\; \backslash right\; )^\{s\_2\}\; \backslash cdots\; \backslash left\; (\; \backslash sum\_\{j=1\}^n\; a\_\{nj\}\; x\_j\; \backslash right\; )^\{s\_n\}$에서 $x\_1^\{s\_1\}\; x\_2^\{s\_2\}\; \backslash cdots\; x\_n^\{s\_n\}$의 계수로 정의한다.

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

:$\backslash operatorname\{perm\}^\{(s\_1,s\_2,\backslash dots,s\_n)\}(A)\; =\; \backslash text\{\; \}x\_1^\{s\_1\}\; x\_2^\{s\_2\}\; \backslash cdots\; x\_n^\{s\_n\}\; \backslash text\{\; 의\; 계수\; in\; \}\; \backslash frac\{1\}\{\backslash det(I\; -\; XA)\}$

여기서 ''I''는 차수 ''n''의 항등 행렬이고, ''X''는 대각선이 $[x\_1,x\_2,\backslash dots,x\_n]$인 대각 행렬이다.

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

''m'' × ''n'' 행렬 $A\; =\; (a\_\{ij\})$ (여기서 ''m'' ≤ ''n'')에 대해 퍼머넌트를 다음과 같이 정의할 수 있다.^[30][31][48]

:$\backslash operatorname\{perm\}\; (A)\; =\; \backslash sum\_\{\backslash sigma\; \backslash in\; \backslash operatorname\{P\}(n,m)\}\; a\_\{1\; \backslash sigma(1)\}\; a\_\{2\; \backslash sigma(2)\}\; \backslash ldots\; a\_\{m\; \backslash sigma(m)\}$

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

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

:$\backslash operatorname\{perm\}(A)=\backslash sum\_\{k=0\}^\{m-1\}\; (-1)^\{k\}\backslash binom\{n-m+k\}\{k\}\backslash sigma\_\{n-m+k\}.$

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

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

참조

_[1] 논문 Permanents https://maa.org/prog[...]
_[2] 문서
_[3] 문서
_[4] 간행물 Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu'elles renferment. https://gallica.bnf.[...]
_[5] 문서
_[6] 문서
_[7] 문서
_[8] 문서
_[9] 문서
_[10] 문서
_[11] arXiv The Computational Complexity of Linear Optics 2010-11-14
_[12] 서적 Matrix Analysis Springer-Verlag 1997
_[13] 문서
_[14] 문서
_[15] 간행물 Upper bounds for permanents of (0,1)-matrices
_[16] 문서
_[17] 간행물 Aufgabe 45
_[18] 간행물 The common source of several inequalities concerning doubly stochastic matrices
_[19] 간행물 Reshenie problemy van-der-Vardena dlya permanentov Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz.
_[20] 간행물 Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix
_[21] 문서
_[22] 웹사이트 Fulkerson Prize https://mathopt.org/[...] Mathematical Optimization Society 2012-08-19
_[23] 문서
_[24] 문서 https://books.google[...]
_[25] 간행물 A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
_[26] 논문 Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography 2023
_[27] 논문 A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
_[28] 문서
_[29] 문서
_[30] 문서
_[31] 문서
_[32] 문서
_[33] 논문 Permanents https://www.maa.org/[...]
_[34] 논문 制限付き占有問題の簡単な計数公式
_[35] 논문 Immanant不等式とImmanantal Polynomials http://math.shinshu-[...]
_[36] 간행물 Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment. https://gallica.bnf.[...]
_[37] 논문 The Computational Complexity of Linear Optics 2010-11-14
_[38] 서적 Matrix Analysis Springer-Verlag
_[39] 간행물 Upper bounds for permanents of (0,1)-matrices
_[40] 간행물 Aufgabe 45
_[41] 간행물 The common source of several inequalities concerning doubly stochastic matrices
_[42] 간행물 Reshenie problemy van-der-Vardena dlya permanentov Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz.
_[43] 간행물 The solution of van der Waerden's problem for permanents
_[44] 간행물 Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix
_[45] 웹사이트 Fulkerson Prize http://www.mathopt.o[...] 2012-08-19
_[46] 간행물 A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
_[47] 간행물 A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
_[48] 문서 Minc, Ryser