解法: 交差族によるMarcus–Spielman–Srivastavaの証明(2013年)
ステップ 4/8: 混合特性多項式:注文設計された実根平均 ざっくり言うとMarcus、Spielman、Srivastavaは、共分散行列 Ai=E[wiwi∗] に対して混合特性多項式 μ[A1,…,Am] を定義する。その微分作用素によるレシピは、この多項式が独立なランク1ランダム行列の和 ∑iwiwi∗ の期待特性多項式と正確に一致するよう設計されており、実安定性によってその根がすべて実数であることが保証される。
詳しい解説半正定な共分散行列 A1,…,Am に対して、μ[A1,…,Am](x):=∏i=1m(1−∂zi)det(xI+∑iziAi)z=0 と定義する。出発点の行列式は実安定であり、微分作用素と実数への特殊化も実安定性を保つ。論文の定理4.1は、この多項式が共分散 Ai を持つ独立ランダムベクトルに対する E[det(xI−∑iwiwi∗)] と一致することを示すため、これは実根を持ち、交差族の議論に適した平均である。
このステップの用語- 半正定行列
- すべての固有値が非負であるエルミート行列。単一のベクトル v から作られる vv∗ の形の行列は常に半正定である。
このステップで使う知識