イマナント

数学では、行列のイマナントは、ダドリー・E・リトルウッドとアーチボルド・リード・リチャードソンによって、行列式とパーマネントの概念の一般化として定義されました。^{[ 1 ]}

させて${\displaystyle \lambda =(\lambda _{1},\lambda _{2},\ldots )}$整数の分割である${\displaystyle n}$そして${\displaystyle \chi _{\lambda }}$対称群の対応する既約表現論的指標とする${\displaystyle S_{n}}$内在するもの${\displaystyle n\times n}$マトリックス${\displaystyle A=(a_{ij})}$キャラクターに関連付けられている${\displaystyle \chi _{\lambda }}$は、式として定義されます。

$\displaystyle \operatorname {Imm} _{\lambda }(A)=\sum _{\sigma \in S_{n}}\chi _{\lambda }(\sigma )a_{1\sigma (1)}a_{2\sigma (2)}\cdots a_{n\sigma (n)}=\sum _{\sigma \in S_{n}}\chi _{\lambda }(\sigma )\prod _{i=1}^{n}a_{i\sigma (i)}.}$

行列式は、内在式の特殊なケースであり、${\displaystyle \chi _{\lambda }}$交互に現れる文字${\displaystyle \operatorname {sgn} }$S _nの、置換のパリティによって定義される。

永続的なケースは、${\displaystyle \chi _{\lambda }}$は自明な文字であり、常に1と等しい 。

例えば、${\displaystyle 3\times 3}$行列には、3 つの既約表現があります。${\displaystyle S_{3}}$文字表に示すように：

上記のとおり、$\displaystyle \chi _{1}}$永久的なものを生成し、$\displaystyle \chi _{2}}$行列式を生成するが、$\displaystyle \chi _{3}}$以下のようにマッピングされる操作を生成します。

${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}\rightsquigarrow 2a_{11}a_{22}a_{33}-a_{12}a_{23}a_{31}-a_{13}a_{21}a_{32}}$

イマナントは、行列式やパーマネントといくつかの性質を共有しています。特に、イマナントは行列の行と列に関して多重線形であり、対称群の同じ要素による行または列の同時置換に対して不変です。

リトルウッドとリチャードソンは、対称群の表現論におけるイマナントとシューア関数の関係を研究した。

グラム行列のイマナントが${\displaystyle 0}$ガマスの定理によって与えられる。

イマナントは行列式とパーマネントの両方を一般化しており、この一般性はこれらの関数を評価する際の計算の難しさに反映されています。ガウス消去法を使用すれば行列式は多項式時間で計算できますが、一般行列のパーマネントの計算は、たとえ に制限した場合でも♯P完全です。${\displaystyle 0}$–${\displaystyle 1}$行列、 Valiantによる結果。 ^{[ 2 ]}

イマナントは対称群の既約指標によってインデックス付けされる${\displaystyle S_{n}}$あるいは、ヤング図によって同等に表現される 。イマナントを評価する計算複雑性は、関連する図の形状に大きく依存する。代数的複雑性理論の初期の結果では、多くの分割族に対して、対応するイマナントはヴァリアントの意味で VNP完全であり、パーマネントの困難性を一般化していることが示された。 ^{[ 3 ]}

より洗練された分類は、イマナントのファミリーに対する完全な複雑性二分法を証明したカーティカピアンによって得られた。 ^{[ 4 ]}${\displaystyle b(\lambda )}$パーティションのヤング図の最初の列の右側にあるボックスの数を表す${\displaystyle \lambda }$。 もし${\displaystyle b(\lambda )}$が分割の族に対して有界である場合、対応するイマナントは多項式時間で評価できます。${\displaystyle b(\lambda )}$が無制限である場合、パラメータ化複雑性理論の標準的な仮定の下では、多項式時間アルゴリズムは存在しない。さらに、${\displaystyle b(\lambda )}$行列サイズとともに多項式的に増加し、対応するイマナントを評価すると♯P-困難かつVNP-完全であることが示され、 BürgisserとBrylinskiおよびBrylinski の永続的かつ以前の研究に対する古典的な困難性の結果を拡張しました。 ^{[ 3 ] [ 5 ]}さらに、多くのイマナントが、 0-1行列やグラフの隣接行列などの構造的に制約された入力を含む制限されたクラスの行列で評価された場合でも♯P-困難のままであることを示すことで、これらの困難性の結果を強化しました。 ^{[ 6 ]}

これらの結果は、行列式を除いて、ほとんどの非自明なイマナントは計算上扱いが困難であることを示唆している。イマナントの複雑さは代数的複雑性理論において役割を果たし、イマナントの表現論的性質を用いてパーマネント関数および関連関数の下限を研究する幾何学的複雑性理論などのより広範な研究プログラムと関連している。^{[ 5 ]}

• D. E. Littlewood; A.R. Richardson (1934). "Group characters and algebras". Philosophical Transactions of the Royal Society A. 233 (721–730): 99–124. Bibcode:1934RSPTA.233...99L. doi:10.1098/rsta.1934.0015.
• D. E. Littlewood (1950). The Theory of Group Characters and Matrix Representations of Groups (2nd ed.). Oxford Univ. Press (reprinted by AMS, 2006). p. 81.