パーマネント (数学)
パーマネントの計算は行列式の場合に比べて複雑になると信じられている(例えば、行列式はガウスの消去法を用いて多項式時間で計算できるが、パーマネントはガウス消去では計算できない)。もっと言えば、(0, 1)-行列のパーマネントの計算は#P完全(英語版)である。したがって、何らかの方法でパーマネントが多項式時間で計算できたと仮定すると、FP(英語版) = #P となるが、これは P = NP よりもいっそう強い主張である。しかし、A の成分が全て非負の場合、パーマネントは確率的多項式時間で近似的に計算することができる(その誤差は、パーマネントの値 M と任意の ε > 0 に対する εM に関するオーダーでとる)。半正定値行列のある種の集合上ではパーマネントが確率的多項式時間で近似的に計算できる(この近似で達成可能な最良の誤差は ε√M である。M はやはりパーマネントの値とする)。
パーマネント函数の定義域を正方行列でない矩形行列も含むように拡張することができる。実際いくつかの文献では、そのようにパーマネントを定義して、正方行列に制限したものを特別の場合と見るものがある。具体的には、m × n 行列 A = (aij) で m ≤ n とするとき、
perm  ( A ) := ∑ σ ∈ P ( n , m ) a 1 σ ( 1 ) a 2 σ ( 2 ) ... a m σ ( m ) {\displaystyle \operatorname {perm} (A):=\textstyle \sum \limits _{\sigma \in P(n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\dotsc a_{m\sigma (m)}}
と定める。ただし、P(n,m) は n元-集合 {1, 2, ..., n} から m 元選ぶ部分置換(順列)全体の成す集合である。
パーマネントに対するRyserの計算論的結果も一般化できる。A が m × n 行列 (m ≤ n) のとき、A から k 個の列を取り除いて Ak が得られるとすると、Ak の行和の積を P(Ak), 可能な全ての Ak に対する P(Ak) の総和を σk と書けば、
perm  ( A ) = ∑ k = 0 m − 1 ( − 1 ) k ( n − m + k k ) σ n − m + k {\displaystyle \operatorname {perm} (A)=\textstyle \sum \limits _{k=0}^{m-1}(-1)^{k}{\dbinom {n-m+k}{k}}\sigma _{n-m+k}}
が成り立つ。
⋁ k H {\displaystyle \bigvee ^{k}H} を(H の k次テンソル冪(英語版) ⨂ k H {\displaystyle \bigotimes ^{k}H} の部分空間として)考えるとき、その上に内積 ⟨,⟩ が定義されれば、それに応じて
⟨ x 1 ∨ x 2 ∨ ⋯ ∨ x k , y 1 ∨ y 2 ∨ ⋯ ∨ y k ⟩ = perm  ( ( ⟨ x i , y j ⟩ ) 1 ≤ i , j ≤ k ) ( x j , y j ∈ H ) {\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} ((\langle x_{i},y_{j}\rangle )_{1\leq i,j\leq k})\qquad (x_{j},y_{j}\in H)}
となることが分かる。