영구(수학)

선형대수학에서 정사각형 행렬의 영구성은 결정요인과 유사한 행렬의 함수다.결정인자뿐만 아니라 영구적인 것은 행렬의 항목에서 다항식이다.^[1]둘 다 임마넌트라고 불리는 행렬의 보다 일반적인 함수의 특별한 경우들이다.

정의

n×n 행렬 A = (a_i,j)의 영구성은 다음과 같이 정의된다.

여기서의 합은 대칭군_n S의 모든 요소 σ에 걸쳐 있다. 즉, 숫자 1, 2, ..., n의 모든 순열에 걸쳐 있다.

예를 들어,

그리고

A의 영구적 정의는 순열의 서명이 고려되지 않는다는 점에서 A의 결정인자의 정의와 다르다.

행렬 A의 영구성은 A, Perm A 또는 Per A에 따라 표시되며, 때로는 인수 주위에 괄호를 사용하여 표시되기도 한다.Minc는 직사각형 행렬의 영구적인 경우 Per(A)를 사용하고, A가 정사각형 행렬인 경우 Per(A)를 사용한다.^[2]Muir와 Metzler는 표기법$++{\$을(를) 사용한다$.$^[3]

영구라는 단어는 1812년 카우치(Cauchy)에서 관련 유형의 기능에 대한 "포네이션스 symétrikes permanent"로 유래하였으며,^[4] 현대적이고 보다 구체적이며 의미 있는 뮤어(Muir)와^[5] 메츨러(Metzler가 사용하였다.^[6]

특성.

만약 어떤 사람이 상수를 n 벡터를 인수로 삼는 지도로 본다면, 그것은 다행 지도로서 대칭이다 (어떤 벡터의 순서가 같은 영구성을 낳는다는 것을 의미한다).또한 다음 순서의 정사각형 $행렬{\displaystyle }$ A${\displaystyle }$= (${\displaystyle }$i ${\displaystyle j_{}}$) ${\$ A$=\좌측(a_{ij}\우측)$을 지정한다.^[7]

• perm(A)은 A의 행 및/또는 열의 임의 순열에 따라 불변한다.이 특성은 적절한 크기의 순열 매트릭스 P와 Q에 대해 perm(A) = perm(PAQ)로 상징적으로 작성할 수 있다.
• A의 단일 행 또는 열에 스칼라 s 변경 perm(A)을 s⋅perm(A)에 곱한 값
• perm(A)은 전이 시 불변, 즉 perm(A) = perm(A^T)이다.
• $A{\displaystyle }$=${\displaystyle }$( ${\displaystyle i_{}}$ j${\displaystyle {}_{}}$) ${\$ A$=\left(a_{ij}\right)}$ 및$$ $B{\displaystyle }$=${\displaystyle }$(${\displaystyle {bi}_{}}$ ${\displaystyle j_{}}$) ${\$이 n의 제곱 행렬이면$$,^[8]
  $${\displaystyle \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}과${\displaystyle \stackrel{}{(}}$와)의 하위 집합이며${\displaystyle ,}$ ${\${\$bar{$s},{\$bar$ {$t}$은(는) 해당 집합의 각 보완물이다${\displaystyle \stackrel{}{.}}$
• ${\displaystyle A}$이(가) 삼각 행렬인 경우(: ${\displaystyle {}_{}}$j = ${\displaystyle 0}${\$displaystyle$ $a_{ij}=0$ i> j ${\displaystyle$ i$>$$j},$ 또는 그 대신 < ${\displaysty$i$<j$ 그리고 결정인자)는 대각 항목의 제품과 동일하다.
  $${\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}$$

  

결정요인과의 관계

행, 열 또는 대각선을 따라 결정인자를 계산하기 위해 미성년자에 의한 라플레이스의 확장은 모든 기호를 무시함으로써 영구적인 것으로 확장된다.^[9]예를 들어, 첫 번째 열을 따라 확장하는 경우,

마지막 줄을 따라 확장하는 동안

반면에 결정요인의 기본 승법특성은 영속성에 유효하지 않다.^[10]간단한 예로 이것이 그렇다는 것을 알 수 있다.

결정요인과 달리 상수는 쉬운 기하학적 해석이 없다. 상수는 주로 결합기, 양자장 이론에서 보손 그린의 함수 처리, 보손 샘플링 시스템의 상태 확률을 결정하는 데 사용된다.^[11]그러나, 두 개의 그래프 이론적 해석을 가지고 있다: 지시된 그래프의 주기 가중치의 합과 초당적 그래프의 완벽한 일치의 가중치의 합이다.

적용들

대칭 텐서

영구성은 힐버트 공간의 대칭 텐서 파워에 대한 연구에서 자연적으로 발생한다.^[12]특히 Hilbert 공간 $H{\displaystyle }$ ${\displaystyle H}$의 경우$,$ ${\displaystyle {}^{}}{\displaystyle {}^{}}$k H ${\displaystyle \ve ^{k}H}$는 대칭 텐서 $공간$인 H ${\displaysty H}$의 $k{\displaystyle }$ ${\displaystyk} 대칭$ 텐서 출력을 나타내도록$$ 한다$.$Note in particular that ${\displaystyle \vee ^{k}H}$ is spanned by the Symmetric products of elements in ${\displaystyle H}$. For ${\displaystyle x_{1},x_{2},\dots ,x_{k}\in H}$, we define the symmetric product of these elements by

If we consider ${\displaystyle \vee ^{k}H}$ (as a subspace of ${\displaystyle \otimes ^{k}H}$, the kth tensor power of ${\displaystyle H}$) and define the inner product on ${\displaystyle \vee ^{k}H}$ accordingly, we find that for ${\displaystyle x_{j},y_{j}\in H}$ Cauchy-Schwarz 불평등을 적용하면, ${\displaystyle \mathrm{perm}}$ ${\displaystyle {[⟨}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {i_{}}_{}^{}}$, x ${\displaystyle {j_{}}_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$],${\displaystyle j_{}^{}}$= ${\displaystyle 1}$ k ${\displaystyle {}_{}^{}}$ 0 ${\displaystyle \operatorname {perm} \left[\langle x_},x_{j}\$angle $\ri]$_{i,$j=1}{k}\geq$0$\},\{$$k$}, $그리고$ 그 결과를 확인할 수 있다.

사이클 커버

Any square matrix ${\displaystyle A=(a_{ij})_{i,j=1}^{n}}$ can be viewed as the adjacency matrix of a weighted directed graph on vertex set ${\displaystyle V=\{1,2,\dots ,n\}}$, with ${\displaystyle a_{ij}}$ representing the weight of the arc from vertex i to vertex j. 가중 지시된 그래프의 사이클 커버는 그래프의 모든 정점을 포함하는 디그그래프의 정점 분리 지시 사이클 모음입니다.따라서 digraph의 각 꼭지점 ${\displaystyle i}$에는 사이클 커버에$$ 고유한 "successor" ${\displaystyle )}$ ($$i ) {\$displaystyle$ \sigma ($i)}$이(가) 있으며, 따라서 $\sigma {\displaystyle }$ ${\displaystyle \sigma }$은 V의 순열을 나타낸다$$.반대로 V의 모든 순열 $perm{\displaystyle }$ ${\displaystyle$\$sigma$$}$은(는$)$ 각 정점 i에서 정점$(($ ${\displaystyle )}$까지 호가 있는 사이클 커버에 해당한다$.$

사이클 커버의 무게가 각 사이클에서 호 무게의 산물로 정의되는 경우,

을 암시하는.따라서 A의 영구치는 모든 주기의 중량의 합과 같다.

퍼펙트 매치

A square matrix ${\displaystyle A=(a_{ij})}$ can also be viewed as the adjacency matrix of a bipartite graph which has vertices ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ on one side and ${\displaystyle y_{1},y_{2},\dots ,y_{n}}$ on the other side, with ${\displaystyle a_{ij}}$ representing the weight of the edge from vertex ${\displaystyle x_{i}}$ to vertex ${\displaystyle y_{j}}$. If the weight of a perfect matching ${\displaystyle \sigma }$ that matches ${\displaystyle x_{i}}$ to ${\displaystyle y_{\sigma ($$i)}}}$은(는) 일치에서 가장자리 무게의 산물로 정의한 다음

따라서 A의 영구성은 그래프의 모든 완벽한 일치에 대한 가중치의 합과 같다.

행렬의 영속성(0, 1)

열거

많은 카운팅 질문에 대한 답은 항목으로 0과 1만 있는 행렬의 영속성으로 계산할 수 있다.

Ω(n,k)을 k와 같은 각 행과 열 합을 가진 n 순서의 모든 (0, 1) 행렬의 등급으로 한다.이 클래스의 모든 매트릭스 A는 0보다 큰 파마(A)를 가지고 있다.^[13]투사 평면의 발생 행렬은 n 정수 1에 대한 Ω(n² + n + 1, n + 1) 등급이다.가장 작은 투영 평면에 해당하는 영속성이 계산되었다.n = 2, 3, 4의 경우 값은 각각 24, 3852 및 18,534,400이다.^[13]Z를 Fano 평면인 n = 2를 갖는 투영 평면의 입사 행렬이 되게 한다.놀랍게도, perm(Z) = 24 = det(Z) , Z의 결정인자의 절대값.이것은 Z가 순환 행렬이고 정리된 결과물이다.^[14]

If A is a circulant matrix in the class Ω(n,k) then if k > 3, perm(A) > det (A) and if k = 3, perm(A) = det (A) . Furthermore, when k = 3, by permuting rows and columns, A can be put into the form of a direct sum of e copies of the matrix Z and consequently, n = 7e and perm(A) = 24^e.

영속성은 제한된 (금지된) 위치의 순열 수를 계산하는 데도 사용할 수 있다.표준 n-set {1, 2, ..., n}의 $경우{\displaystyle }$ A${\displaystyle }$= (${\displaystyle }$i ${\displaystyle {}_{}}$) ${\displaystyle$ A$=(a_{ij}}$를 (0, 1) 매트릭스로 하고$$ 여기서_ij i → j는 순열에서, a = 0으로_ij 허용한다.그런 다음 perm(A)은 모든 제한을 충족하는 n-set의 순열 수와 동일하다.^[9]이것에 대해 잘 알려진 두 가지 특별한 경우는 변색 문제와 메네지 문제의 해결책이다: 고정된 점(변형)이 없는 n-set의 순열 수는 다음에 의해 주어진다.

여기서 J는 1의 모든 행렬의 n×n이고 나는 정체 행렬이며, 메니지 번호는 다음과 같이 주어진다.

여기서 i'는 위치(i, i + 1) 및 (n, 1)에 0이 아닌 항목이 있는 (0, 1) 매트릭스다.

경계

1963년^[15] H. Minc에 의해 추측되고 1973년 L. M. Brégman에 의해 증명된 Bregman-Minc 불평등은 n × n (0, 1) 매트릭스의 영구적인 상한선을 부여한다.^[16]만약 A가 1 i i n n에 대해 i행으로_i r을 가지고 있다면, 불평등은 다음과 같이 말한다.

반데르 베르덴의 추측

1926년에 Van der Waerden은 모든 n × n 이중 확률 매트릭스 중 최소 영구값이 n!/n이며ⁿ, 모든 항목이 1/n과 동일한 매트릭스에 의해 달성된다고 추측했다.^[17]이 추측의 증거는 1980년에 B에 의해 발표되었다.Gyires와^[18] 1981년 G. P. Egorychev와^[19] D.I. 팔릭만;^[20] 에고리체프의 증거는 알렉산드로프-펜첼 불평등을 응용한 것이다.^[21]이 작품으로 에고리체프와 팔릭만은 1982년 풀커슨상을 수상하였다.^[22]

연산

컴퓨터 영속성의 정의를 사용하는 순진한 접근법은 비교적 작은 행렬에도 계산적으로 실현 불가능하다.가장 빨리 알려진 알고리즘 중 하나는 H. J. 라이저 때문이다.^[23]라이저의 방법은 다음과 같이 주어질^[24] 수 있는 포함-배제 공식에 기초한다.Let ${\displaystyle A_{k}}$ be obtained from A by deleting k columns, let ${\displaystyle P(A_{k})}$ be the product of the row-sums of ${\displaystyle A_{k}}$, and let ${\displaystyle \Sigma _{k}}$ be the sum of the values of ${\displaystyle P(A_{k})}$ over all possi${\displaystyle A_{}}$ ${\$을(를) 표백하다$.$그러면

다음과 같이 매트릭스 항목으로 다시 작성할 수 있다.

영구적인 것은 결정인자보다 계산하기가 더 어렵다고 여겨진다.결정 인자는 가우스 제거에 의해 다항 시간에서 계산할 수 있지만 가우스 제거는 영구적인 계산에 사용할 수 없다.더욱이 a(0,1) 매트릭스의 영구적인 계산은 #P-완전하다.따라서 상수를 어떤 방법으로든 다항식 시간으로 계산할 수 있다면 FP = #P, 즉 P = NP보다 훨씬 강력한 문장이 된다.그러나 A의 항목이 음수가 아닌 경우, ${\displaystyle \mathrm{permanent}}$ $M{\displaystyle }$ {\$displaystyle \varepsilon M}$의 오류까지 대략 확률론적 다항식 시간에서 영구값을 계산할 수 있다$.$ $여기$서 M ${\displaystyle M}$은 영구값이고 > ${\displaystyle \varepsilon >0}$은 임의 값이다.^[25]양수 세미더파인 행렬의 특정 집합의 영구성은 확률론적 다항식 시간에도 근사치를 구할 수 있다. 이 근사치의 가장 잘 달성할 수 있는 오차는 ${\displaystyle \epsilon \sqrt{}}$ M ${\$이다($$${\displaystyle }$ ${\displaystym M}$은 다시 영구값).^[26]

맥마흔의 마스터 정리

영속성을 보는 또 다른 방법은 다변량 생성 기능을 통해서이다.$A{\displaystyle }$=${\displaystyle }$( ${\displaystyle i_{}}$ j${\displaystyle {}_{}}$) ${\displaystyle$ A$=(a_{ij})$를 순서의 제곱 행렬로 한다.다변량 생성 함수를 고려하십시오.

$F{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ 2$,$ $,x_{1$}$x_{2$}\$dots x_$${n})$에서 x$$ ${\displaystyle {}_{}{}_{}{2}_{}}$의 계수는 perm(A)이다$.$^[27]

일반적으로 n개의 음이 아닌 정수의 순서에 대해 s ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$s ${\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle \dots ,{}_{}}$ ${\displaystyle n_{}}$ ${\$을 정의한다$$.

as the coefficient of ${\displaystyle x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}}$ in${\displaystyle \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}}.$$}$

맥마흔의 영속성 및 결정요인과 관련된 마스터 정리:^[28]

여기서 I는 순서 n ID 행렬이고 X는 대각선 행렬이며 대각선 행렬은 대각선 행렬이다${\displaystyle }$[${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$ 2,${\displaystyle \dots ,}$ ${\displaystyle x_{}}$ ${\displaystyle [x_{1},x_{2},\dots ,x_{n}].$$}$

직사각형 행렬의 영속성

영구 함수는 일반화하여 비제곱 행렬에 적용할 수 있다.실제로, 몇몇 저자들은 이것을 영구적인 것의 정의로 만들고, 행렬을 제곱하기 위한 제한을 특별한 경우로 여긴다.^[29]특히 m × n ${\displaystyle {\mathrm{매트릭스}}_{}{}_{}}$= (${\displaystyle {}_{}{i}_{}}$ j$$) {\$displaystyle A=(a_${ij$})$에 대해 m × n을 정의하십시오.

여기서 P(n,m)는 n-set {1,2,...,^[30]n}의 모든 m-permutions 집합이다.

영속성에 대한 라이저의 계산 결과도 일반화된다.If A is an m × n matrix with m ≤ n, let ${\displaystyle A_{k}}$ be obtained from A by deleting k columns, let ${\displaystyle P(A_{k})}$ be the product of the row-sums of ${\displaystyle A_{k}}$, and let ${\displaystyle \sigma _{k}}$ be the sum of the values of ${\dis$${\displaystyle {가능}_{}}$한 $모든{\displaystyle {}_{}}$ A k ${\$에 대해 재생 $스타일 P$$($$A_{k}}).$그러면^[10]

별개의 대표자 제도

영구적인 행렬에서 비제곱 행렬의 정의의 일반화를 통해 어떤 용도에서는 개념을 보다 자연적인 방법으로 사용할 수 있다.예를 들어,

S₁, S₂, ..., S는_m m ≤ n을 가진 n-set의 부분 집합(꼭 구별되는 것은 아님)이 되도록 한다.이 부분 집합의 발생 행렬은 m × n (0,1)-매트릭스 A이다.이 컬렉션의 구별되는 대표자(SDR)의 시스템 수는 perm(A)이다.^[31]

참고 항목

• 영구 컴퓨팅
• 순서 통계에 영속성을 적용한 바파트-베그 정리
• 양자역학에서 영속성의 응용인 슬레이터 결정인자

메모들

참조

• Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
• Minc, Henryk (1978). Permanents. Encyclopedia of Mathematics and its Applications. Vol. 6. With a foreword by Marvin Marcus. Reading, MA: Addison–Wesley. ISSN 0953-4806. OCLC 3980645. Zbl 0401.15005.
• Muir, Thomas; Metzler, William H. (1960) [1882]. A Treatise on the Theory of Determinants. New York: Dover. OCLC 535903.
• Percus, J.K. (1971), Combinatorial Methods, Applied Mathematical Sciences #4, New York: Springer-Verlag, ISBN 978-0-387-90027-8
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, The Mathematical Association of America
• van Lint, J.H.; Wilson, R.M. (2001), A Course in Combinatorics, Cambridge University Press, ISBN 978-0521422604

추가 읽기

• Hall Jr., Marshall (1986), Combinatorial Theory (2nd ed.), New York: John Wiley & Sons, pp. 56–72, ISBN 978-0-471-09138-7 반 데어 웨르덴 추측의 증거가 들어있다.
• Marcus, M.; Minc, H. (1965), "Permanents", The American Mathematical Monthly, 72 (6): 577–591, doi:10.2307/2313846, JSTOR 2313846

외부 링크

• PlanetMath에서 영구적임.
• 플래닛매스에서의 밴더 웨르덴의 영구적인 추측.