본문 바로가기
영문 위키피디아 번역

(번역) Permanent (mathematics)

by 다움위키 2024. 3. 17.
Original article: w:Permanent (mathematics)

 

선형 대수(linear algebra)에서, 정사각 행렬의 퍼머넌트(permanent)는 행렬식(determinant)과 유사한 행렬의 함수입니다. 행렬식뿐만 아니라 퍼머넌트는 행렬의 엔트리에서 다항식입니다. 둘 다 임머넌트(immanant)라고 불리는 행렬의 보다 일반적인 함수의 특수한 경우입니다.

Definition

n×n 행렬 \(A=(a_{i,j})\)의 퍼머넌트는 다음과 같이 정의됩니다:

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

그 합은 여기서 대칭 그룹(symmetric group) \(S_n\)의 모든 원소 σ에 걸쳐; 즉, 숫자 1, 2, ..., n의 모든 순열(permutations)에 걸쳐 전개합니다.

예를 들어,

\(\quad\displaystyle \operatorname{perm}\begin{pmatrix}a&b \\ c&d\end{pmatrix}=ad+bc,\)

그리고

\(\quad\displaystyle \operatorname{perm}\begin{pmatrix}a&b&c \\ d&e&f \\ g&h&i \end{pmatrix}=aei + bfg + cdh + ceg + bdi + afh.\)

A의 퍼머넌트의 정의는 순열의 시그니처(signatures)가 고려되지 않는다는 점에서 A의 행렬식(determinant)의 정의와 다릅니다.

행렬 A의 퍼머넌트는 per A, perm A, 또는 Per A로 표시되며, 때로는 인수를 괄호로 묶습니다. Minc는 직사각 행렬의 퍼머넌트에 대해 Per(A)를 사용하고, A가 정사각 행렬이면 per(A)를 사용합니다. Muir와 Metzler는 \(\displaystyle \overset{+}{|}\quad \overset{+}{|}\) 표기법을 사용합니다.

단어, permanent는 1812년 코시에 의해 관련된 유형의 함수에 대한 “fonctions symétriques permanentes”로 기원되었고, Muir와 Metzler에 의해 현대적이고 보다 구체적인 의미로 사용되었습니다.

Properties

만약 퍼머넌트를 n개의 벡터를 인수로 취하는 맵으로 본다면, 그것은 다중-선형 맵(multilinear map)이고 대칭적입니다 (벡터의 임의의 순서가 같은 퍼머넌트를 생성함을 의미합니다). 게다가, 차수 n의 정사각 행렬 \(\displaystyle A = \left(a_{ij}\right)\)가 주어졌을 때:

  • perm(A)는 A의 행 및/또는 열의 임의적인 순열 아래에서 불변입니다. 이 속성은 임의의 적절하게 크기-지정된 순열 행렬(permutation matrices) P와 Q에 대해 기호로 perm(A) = perm(PAQ)로 쓸 수 있습니다.
  • A의 임의의 단일 행 또는 열에 스칼라(scalar) s를 곱하면 perm(A)를 s⋅perm(A)로 변경합니다.
  • perm(A)는 전치(transposition) 아래에서 불변, 즉, \(\text{perm}(A)=\text{perm}(A^{\text{T}})\)입니다.
  • 만약 \(\displaystyle A = \left(a_{ij}\right)\)와 \(\displaystyle B=\left(b_{ij}\right)\)가 차수 n의 정사각 행렬이면,
    • \(\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 \bar{s}, \bar{t}\)는 해당 집합에서 그것들의 각각 여집합입니다.
  • 만약 \(\displaystyle A\)가 삼각 행렬(triangular matrix), 즉, \(\displaystyle i>j\)일 때마다, 또는, 대안적으로, \(\displaystyle i<j\)일 때마다 \(\displaystyle a_{ij}=0\)이면, 그것의 퍼머넌트 (및 마찬가지로 행렬식)는 대각 엔트리의 곱과 같습니다:
    • \(\displaystyle \operatorname{perm}\left(A\right) = a_{11} a_{22} \cdots a_{nn} = \prod_{i=1}^n a_{ii}.\)

Relation to determinants

행, 열 또는 대각선을 따라 행렬식을 계산하기 위한 라플라스의 소행렬식의 전개(expansion by minors)는 모든 부호를 무시함으로써 영구적으로 전개됩니다.

모든 각 \(\displaystyle i\)에 대해,

\(\quad\displaystyle \mathbb{perm}(B)=\sum_{j=1}^n B_{i,j} M_{i,j},\)

여기서 \(\displaystyle B_{i,j}\)는 \(\displaystyle B\)의 \(\displaystyle i\)-번째 행과 \(\displaystyle j\)-번째 열의 엔트리이고, \(\displaystyle M_{i,j}\)는 \(\displaystyle B\)의  \(\displaystyle i\)-번째 행과 \(\displaystyle j\)-번째 열을 제거함으로써 얻은 부분행렬의 퍼머넌트입니다.

예를 들어, 첫 번째 열을 따라 전개하여,

\(\quad\displaystyle \begin{align}
\operatorname{perm} \left ( \begin{matrix} 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end{matrix} \right )
= {} & 1 \cdot \operatorname{perm} \left( \begin{matrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{matrix}\right) + 2\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}\right) \\
& {} + \ 3\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}\right) + 4 \cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}\right) \\
= {} & 1(1) + 2(1) + 3(1) + 4(1) = 10,
\end{align} \)

반면에 마지막 행을 따라 전개하여 다음을 제공합니다,

\(\quad\displaystyle \begin{align}
\operatorname{perm} \left ( \begin{matrix} 1 & 1 & 1 & 1\\2 & 1 & 0 & 0\\3 & 0 & 1 & 0\\4 & 0 & 0 & 1 \end{matrix} \right )
= {} & 4 \cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}\right) + 0\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}\right) \\
& {} + \ 0\cdot \operatorname{perm} \left(\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}\right) +
1 \cdot \operatorname{perm} \left( \begin{matrix} 1&1&1\\ 2&1&0\\ 3&0&1\end{matrix}\right) \\
= {} & 4(1) + 0 + 0 + 1(6) = 10.
\end{align} \)

다른 한편으로, 행렬식의 기본 곱셈 속성은 퍼머넌트에 대해 유효하지 않습니다. 간단한 예제는 이것이 사실임을 보여줍니다.

\(\quad\displaystyle \begin{align} 4 &= \operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right )\operatorname{perm} \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \\
&\neq \operatorname{perm}\left ( \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \left ( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right ) \right ) = \operatorname{perm} \left ( \begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix} \right )= 8. \end{align} \)

행렬식과 달리, 퍼머넌트는 기하학적으로 쉽게 해석될 수 없습니다; 그것은 주로 조합론(combinatorics), 양자 필드 이론(quantum field theory)에서 보손 그린의 함수(Green's functions)를 처리하고, 보손 표본화(boson sampling) 시스템의 상태 확률을 결정하는 데 사용됩니다. 어쨌든, 그것은 두 가지 그래프-이론적(graph-theoretic) 해석을 가집니다: 방향화된 그래프(directed graph)의 주기 덮개(cycle cover)의 가중의 합과 이분 그래프(bipartite graph)에서 완벽 일치 가중의 합입니다.

Applications

Symmetric tensors

퍼머넌트는 힐베르트 공간(Hilbert spaces)의 대칭 텐서 거듭제곱 연구에서 자연스럽게 발생합니다. 특히, 힐베르트 공간 \(\displaystyle H\)에 대해, \(\displaystyle \vee^k H\)는 대칭 텐서(symmetric tensors)의 공간인 \(\displaystyle H\)의 \(\displaystyle k\)-번째 대칭 텐서 거듭제곱을 나타낸다고 놓습니다. 특히 \(\displaystyle \vee^k H\)는 \(\displaystyle H\)에 있는 원소의 대칭 곱(symmetric products)에 의해 스팬됨에 주목하십시오. \(\displaystyle x_1,x_2,\dots,x_k \in H\)에대해, 이들 원소의 대칭 곱을 다음과 같이 정의합니다:

\(\quad\displaystyle 
x_1 \vee x_2 \vee \cdots \vee x_k =
(k!)^{-1/2} \sum_{\sigma \in S_k}
x_{\sigma(1)} \otimes x_{\sigma(2)} \otimes \cdots \otimes x_{\sigma(k)}
\)

만약 \(\displaystyle \vee^k H\) (\(\displaystyle \otimes^kH\)의 부분공간, \(\displaystyle H\)의 \(\displaystyle k\)-번째 텐서 거듭제곱)를 고려하고 이에 따라 \(\displaystyle \vee^kH\) 위에 안의 곱을 정의하면, \(\displaystyle x_j,y_j \in H\)에 대해, 다음임을 찾습니다:

\(\quad\displaystyle \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\)

코시-슈바르츠 부등식(Cauchy–Schwarz inequality)을 적용하여, \(\displaystyle \operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \geq 0\)임을 찾고, 그리고 다음임을 찾습니다:

\(\quad\displaystyle \left|\operatorname{perm} \left[\langle x_i,y_j \rangle\right]_{i,j = 1}^k \right|^2 \leq
\operatorname{perm} \left[\langle x_i,x_j \rangle\right]_{i,j = 1}^k \cdot
\operatorname{perm} \left[\langle y_i,y_j \rangle\right]_{i,j = 1}^k
\)

Cycle covers

임의의 정사각 행렬 \(\displaystyle A = (a_{ij})_{i,j=1}^n\)은 꼭짓점 집합 \(\displaystyle V=\{1,2,\dots,n\}\) 위에 가중된 방향화된 그래프(directed graph)의 인접 행렬(adjacency matrix)로 볼 수 있으며, \(\displaystyle a_{ij}\)는 꼭짓점 \(\displaystyle i\)에서 정점 \(\displaystyle j\)까지의 호의 가중을 나타냅니다. 가중된 방향화된 그래프의 주기 덮개(cycle cover)는 그래프에서 모든 꼭짓점을 덮는 다이그래프(digraph)에서 꼭짓점-서로소 방향화된 주기(directed cycles)의 모음입니다. 따라서, 다이그래프에서 각 꼭짓점 \(\displaystyle i\)는 주기 덮개의 고유한 "후속" \(\displaystyle \sigma(i)\)가 있고, 따라서 \(\displaystyle \sigma\)는 V 위에 [[permutation|순열(permutation)]]을 나타냅니다. 반대로, V 위에 임의의 순열 \(\displaystyle \sigma\)는 각 꼭짓점 \(\displaystyle i\)에서 꼭짓점 \(\displaystyle \sigma(i)\)로의 호를 갖는 주기 덮개에 해당합니다.

만약 주기 덮개의 가중이 각 주기에서 호의 가중의 곱으로 정의되면, 다음이며, 

\(\quad\displaystyle  \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)},\)

다음임을 의미합니다:

\(\quad\displaystyle  \operatorname{perm}(A)=\sum_\sigma \operatorname{weight}(\sigma).\)

따라서 A의 퍼머넌트는 다이그래프의 모든 주기-덮개의 가중의 합과 같습니다.

Perfect matchings

정사각 행렬 \(\displaystyle A = (a_{ij})\)는 한 변 위에 [[vertex (graph theory)|꼭짓점(vertices)]] \(\displaystyle x_1, x_2, \dots, x_n\)를 가지고 나머지 다른 변 위에 \(\displaystyle y_1, y_2, \dots, y_n\)를 가지는 이분 그래프(bipartite graph)의 인접 행렬(adjacency matrix)로도 볼 수 있으며, \(\displaystyle a_{ij}\)는 꼭짓점 \(\displaystyle x_i\)에서 꼭짓점 \(\displaystyle y_j\)로의 가장자리의 가중을 나타냅니다. 

만약 \(\displaystyle x_i\)에서 \(\displaystyle y_{\sigma(i)}\)까지 일치하는 완벽 일치(perfect matching) \(\displaystyle \sigma\)의 가중이 일치에서 가장자리의 가중의 곱으로 정의하면, 다음과 같습니다:

\(\quad\displaystyle  \operatorname{weight}(\sigma) = \prod_{i=1}^n a_{i,\sigma(i)}.\)

따라서 A의 퍼머넌트는 그래프의 모든 완벽 일치의 가중의 합과 같습니다.

Permanents of (0, 1) matrices

Enumeration

많은 세는 질문에 대한 답변은 엔트리로 0과 1만 가지는 행렬의 퍼머넌트로 계산될 수 있습니다.

Ω(n,k)를 각 행과 열의 합이 k와 같은 차수 n의 모든 (0, 1)-행렬의 클래스라고 놓습니다. 이 클래스에서 모든 각 행렬 A는 perm(A) > 0을 가집니다. 투영 평면의 발생 행렬은 정수 > 1인 n에 대해 클래스 \(\Omega(n^2+n+1, n+1)\)에 있습니다. 가장 작은 투영 평면에 해당하는 퍼머넌트는 계산되었습니다. n = 2, 3, 및 4에 대해, 그 값은 각각 24, 3852, 및 18,534,400입니다. Z를 파노 평면(Fano plane), n = 2를 갖는 투영 평면의 발생 행렬이라고 놓습니다. 놀랍게도, perm(Z) = 24 = |det (Z)|, Z의 행렬식의 절댓값입니다. 이것은 Z가 순환 행렬(circulant matrix)이고 다음 정리의 결과입니다:

  • 만약 A가 클래스 Ω(n,k)에서 순환 행렬이면 k > 3일 때, perm(A) > |det (A)|이고 k = 3일 때, perm(A) = |det (A)|입니다. 게다가, k = 3일 대, 행과 열을 순열함으로써, A는 행렬 Z의 e 복사본의 직접 합의 형식으로 넣을 수 있고 결과적으로, n = 7e이고 \(\text{perm}(A)=24^e\)입니다.

퍼머넌트는 제한된 (금지된) 위치를 갖는 순열(permutations)의 숫자를 계산하는 데에도 사용될 수 있습니다. 표준 n-집합 {1, 2, ..., n}에 대해, \(\displaystyle A = (a_{ij})\)를 (0, 1)-행렬로 놓으며, 여기서 i → j가 순열에서 허용되면 \(a_{ij}=1\)이고 그렇지 않으면 \(a_{ij}=0\)입니다. 그런-다음 perm(A)는 모든 제한을 만족시키는 n-집합의 순열의 숫자와 같습니다. 이에 대한 두 가지 잘 알려진 특별한 경우는 교란(derangement) 문제와 미나지 문제(ménage problem)의 해법입니다: 고정된 점을 가지지 않는 n-집합의 순열의 숫자 (교란)는 다음에 의해 지정됩니다:

\(\quad\displaystyle \operatorname{perm}(J - I) = \operatorname{perm}\left (\begin{matrix} 0 & 1 & 1 & \dots & 1 \\ 1 & 0 & 1 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \dots & 0 \end{matrix} \right) = n! \sum_{i=0}^n \frac{(-1)^i}{i!},\)

여기서 J는 n×n 모두 1의 행렬이고 I는 항등 행렬이고, 미나지 숫자(ménage numbers)는 다음에 의해 지정됩니다:

\(\quad\displaystyle \begin{align}
\operatorname{perm}(J - I - I') & = \operatorname{perm}\left (\begin{matrix} 0 & 0 & 1 & \dots & 1 \\ 1 & 0 & 0 & \dots & 1 \\ 1 & 1 & 0 & \dots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 1 & \dots & 0 \end{matrix} \right) \\
& = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!,
\end{align}\)

여기서 I'는 위치 (i, i + 1)와 (n, 1)에 비-영 엔트리를 갖는 (0, 1)-행렬입니다.

Bounds

브레그만-민크 부등식(Bregman–Minc inequality)은, 1963년에 H. Minc에 의해 추측되고 1973년에 L. M. Brégman에 의해 입증되었으며, n × n (0, 1)-행렬의 퍼머넌트에 대한 위쪽 경계를 제공합니다. 만약 A가 각 1 ≤ i ≤ n에 대해 i 행에 \(r_i\)개의 1을 가지면, 부등식은 다음임을 설명합니다:

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

Van der Waerden's conjecture

1926년에, 반 데르 바르던(Van der Waerden)은 모든 n × n 이중 확률 행렬(doubly stochastic matrices) 중 최소 퍼머넌트가 \(n!/n^n\)이며, 모든 엔트리가 1/n인 행렬에 의해 달성된다고 추측했습니다. 이 추측의 증명은 1980년에 B. Gyires에 의해, 및 1981년에 G. P. Egorychev와 D. I. Falikman에 의해 출판되었습니다; Egorychev의 증명은 알렉산드로프–펜힐 부등식(Alexandrov–Fenchel inequality)의 적용입니다. 이 연구로, Egorychev와 Falikman은 1982년에 풀커슨 상(Fulkerson Prize)을 수상했습니다.

Computation

퍼머넌트를 계산하는, 정의를 사용하여, 소박한 접근 방식은 상대적으로 작은 행렬에 대해서도 계산적으로 실행 불가능합니다. 가장 빠른 알려진 알고리듬 중 하나는 허버트 존 라이서(H. J. Ryser)에 기인합니다. 라이서의 방법(Ryser's method)은 다음과 같이 주어질 수 있는 포함-제외(inclusion–exclusion) 공식을 기반으로 합니다: \(\displaystyle A_k\)를 A에서 k 열을 삭제함으로써 얻은 것으로 놓고, \(\displaystyle P(A_k)\)를 \(\displaystyle A_k\)의 행-합의 곱으로 놓고, \(\displaystyle \Sigma_k\)를 모든 가능한 \(\displaystyle A_k\)에 걸쳐 \(\displaystyle P(A_k)\)의 값의 합으로 놓습니다. 그런-다음

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

그것은 다음과 같이 행렬 엔트리의 관점에서 다시 쓸 수 있습니다:

\(\quad\displaystyle \operatorname{perm} (A) = (-1)^n \sum_{S\subseteq\{1,\dots,n\}} (-1)^{|S|} \prod_{i=1}^n \sum_{j\in S} a_{ij}.\)

퍼머넌트는 행렬식보다 계산하기가 더 어려운 것으로 믿어집니다. 행렬식은 가우스 소거법(Gaussian elimination)에 의해 다항식 시간(polynomial time)에서 계산될 수 있지만, 가우스 소거법은 퍼머넌트를 계산하기 위해 사용될 수 없습니다. 게다가, (0,1)-행렬의 퍼머넌트를 계산하는 것은 #P-완전(#P-complete)입니다. 따라서, 만약 퍼머넌트가 임의의 방법에 의해 다항식 시간에서 계산될 수 있으면, FP = #P이며, 이는 P = NP보다 훨씬 더 강력한 명제입니다. 어쨌든, A의 엔트리가 비-음수이면, 퍼머넌트는 확률적(probabilistic) 다항식 시간에서 근사적으로, \(\displaystyle \varepsilon M\)의 오차까지, 계산될 수 있으며, 여기서 \(\displaystyle M\)은 퍼머넌트의 값이고 \(\displaystyle \varepsilon > 0 \)은 임의적입니다. 양수 반-한정 행렬(positive semidefinite matrices)의 특정 집합의 퍼머넌트는 확률적 다항식 시간에서 근사화될 수도 있습니다: 이 근사에서 가장 좋은 달성할 수 있는 오차는 \(\displaystyle \varepsilon\sqrt{M}\)입니다 (\(\displaystyle M\)은 다시 퍼머넌트의 값입니다).

MacMahon's master theorem

퍼머넌트를 보는 또 다른 방법은 다변수 생성 함수(generating functions)를 통한 것입니다. \(\displaystyle A = (a_{ij})\)를 차수 ''n''의 정사각 행렬이라고 놓습니다. 다음과 같은 다변수 생성 함수를 생각해 보십시오:

\(\quad\displaystyle \begin{align} 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). \end{align}\)

\(\displaystyle F(x_1,x_2,\dots,x_n)\)에서 \(\displaystyle x_1 x_2 \dots x_n\)의 계수는 perm(A)입니다.

일반화로, n 비-음의 정수의 임의의 수열에 대해, \(\displaystyle s_1,s_2,\dots,s_n\)은 \(\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}\)에서 \(\displaystyle x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} \)의 계수로 다음과 같이 정의합니다:

\(\quad\displaystyle \operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A)\)퍼머넌트와 행렬식과 관련하여 맥메이헌의 마스터 정리(MacMahon's master theorem)는 다음과 같습니다:

\(\quad\displaystyle \operatorname{perm}^{(s_1,s_2,\dots,s_n)}(A) = \text{ coefficient of }x_1^{s_1} x_2^{s_2} \cdots x_n^{s_n} \text{ in } \frac{1}{\det(I - XA)},\)

여기서 I은 차수 n 항등 행렬이고 X는 대각선 \(\displaystyle [x_1,x_2,\dots,x_n]\)을 갖는 대각 행렬입니다.

Rectangular matrices

퍼머넌트 함수는 비-정사각 행렬에 적용하기 위해 일반화될 수 있습니다. 실제로, 몇몇 저자는 이것을 퍼머넌트의 정의로 만들고 정사각 행렬에 대한 제한을 특별한 경우로 고려합니다. 구체적으로, m ≤ n을 갖는 m × n 행렬 \(\displaystyle A = (a_{ij})\)에 대해, 다음을 정의합니다:

\(\quad\displaystyle \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)은 n-집합 {1,2,...,n}의 모든 m-순열의 집합입니다.

퍼머넌트에 대한 라이서의 계산적 결과도 일반화합니다. 만약 A가 m ≤ n을 갖는 m × n 행렬이면, \(\displaystyle A_k\)를 A에서 k 열을 제거함으로써 얻은 것이라고 놓고, \(\displaystyle P(A_k)\)를 \(\displaystyle A_k\)의 행-합의 곱이라고 놓고, \(\displaystyle \sigma_k\)를 모든 가능한 \(\displaystyle A_k\)에 걸쳐 \(\displaystyle P(A_k)\)의 값의 합이라고 놓습니다. 그런-다음

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

Systems of distinct representatives

비-정사각 행렬에 대한 퍼머넌트의 정의의 일반화는 일부 응용에서 보다 자연스러운 방법에서 그 개념을 사용하도록 허용합니다. 예를 들어:

\(S_1,S_2,...,S_m\)을 m ≤ n을 갖는 n-집합의 부분집합 (반드시 구별될 필요는 없음)이라고 놓습니다. 이 부분집합의 모음의 발생 행렬(incidence matrix)은 m × n (0,1)-행렬 A입니다. 이 모음의 구별되는 대표의 시스템 (SDR)의 숫자는 perm(A)입니다.

References

Further reading

External links

 

 

관련글

티스토리툴바