ニュートンの恒等式
上記の多項式が行列Aの特性多項式である場合(特にAが多項式の同伴行列である場合)、根 x i {\displaystyle x_{i}} は行列の固有値となる。また、任意の正の整数kに対して、行列 Aは固有値 x i k {\displaystyle x_{i}^{k}} を持ち、これらの和はAのトレース:
p k = tr  ( A k ) . {\displaystyle p_{k}=\operatorname {tr} (A^{k})\,.}
により表される。ニュートンの恒等式によりこれらから基本対称式が求まるため、Aの特性多項式の係数をAのトレースを計算することにより求めることができる。
この計算では、行列のべき乗Aのトレースの計算と、ニュートンの恒等式を解く際に三角化された連立方程式を解く必要がある。これらの計算はどちらも複雑度クラスNCで実行できる。したがって、行列の特性多項式はNCで計算できる。ケイリー・ハミルトンの定理により、すべての行列はその特性多項式を満たし、単純な変換により、NCで余因子行列を見つけることができる。
計算を効率的な形式に再配置すると、ファデーエフ・ルベリエアルゴリズム(1840)が得られる。これの高速並列実装は、L. Csanky(1976)により得られた。この方式の欠点は、整数による除算が必要なことである。したがって、群の標数は0である必要がある。
ニュートンの恒等式は、クラメルの法則を適用することで、行列式の形で表すことができる。以下に示すニュートンの恒等式:
e 1 = 1 p 1 , 2 e 2 = e 1 p 1 − 1 p 2 , 3 e 3 = e 2 p 1 − e 1 p 2 + 1 p 3 , ⋮ n e n = e n − 1 p 1 − e n − 2 p 2 + ⋯ + ( − 1 ) n e 1 p n − 1 + ( − 1 ) n − 1 p n {\displaystyle {\begin{aligned}e_{1}&=1p_{1},\\2e_{2}&=e_{1}p_{1}-1p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+1p_{3},\\&\,\,\,\vdots \\ne_{n}&=e_{n-1}p_{1}-e_{n-2}p_{2}+\cdots +(-1)^{n}e_{1}p_{n-1}+(-1)^{n-1}p_{n}\\\end{aligned}}}
について、 p 1 , − p 2 , p 3 , ... , ( − 1 ) n p n − 1 {\displaystyle p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}} を未知変数として、連立方程式を解く。これにより以下の表現が得られる。
i m i {\displaystyle {\begin{aligned}h_{1}&=p_{1},\\h_{2}&={\frac {1}{2}}p_{1}^{2}+{\frac {1}{2}}p_{2}&&={\frac {1}{2}}(p_{1}^{2}+p_{2}),\\h_{3}&={\frac {1}{6}}p_{1}^{3}+{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&={\frac {1}{6}}(p_{1}^{3}+3p_{1}p_{2}+2p_{3}),\\h_{4}&={\frac {1}{24}}p_{1}^{4}+{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}+{\frac {1}{4}}p_{4}&&={\frac {1}{24}}(p_{1}^{4}+6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}+6p_{4}),\\&~~\vdots \\h_{n}&=\sum _{m_{1}+2m_{2}+\dots +nm_{n}=n \atop m_{1}\geq 0,\dots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {p_{i}^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}}
この場合もベル多項式により以下のように表される。
h n = 1 n ! B n ( p 1 , 1 ! p 2 , 2 ! p 3 , ... , ( n − 1 ) ! p n ) . {\displaystyle h_{n}={\frac {1}{n!}}B_{n}(p_{1},1!p_{2},2!p_{3},\dots ,(n-1)!p_{n}).}
これらの式は、対称群の巡回指標多項式に対応する。単項式 p1p2...pl に対応するhk を表す式の係数は、k の置換のうち、m1の固定点をもち、m2 の長さ2の巡回をもち、...、ml の長さ l の巡回をもつ置換のすべての置換に対する割合である。