Alexandrov–Fenchelの不等式(Alexandrov–Fenchel inequality)とは、$\mathbb{R}^n$($n\ge2$)の凸体 $K_1,\dots,K_n$ の混合体積について $V(K_1,K_2,K_3,\dots,K_n)^2\ge V(K_1,K_1,K_3,\dots,K_n)V(K_2,K_2,K_3,\dots,K_n)$ が成り立つという不等式である。Cauchy–Schwarz の不等式と向きが逆で、混合体積の列の対数凹性、Minkowski の第 1 不等式、Brunn–Minkowski の不等式を導く。行列の版である混合判別式の Alexandrov の不等式は Perron–Frobenius 型の議論で証明でき、座標軸に平行な箱の場合を含む。
Alexandrov–Fenchel の不等式(Alexandrov–Fenchel inequality)は、$\mathbb R^n$($n\ge2$)の凸体 $K_1,\dots,K_n$ の 混合体積 について
$$
V(K_1,K_2,K_3,\dots,K_n)^2\ge V(K_1,K_1,K_3,\dots,K_n)\,V(K_2,K_2,K_3,\dots,K_n)
$$
が成り立つという不等式である。A. D. Alexandrov と W. Fenchel が 1937 年ごろ独立に見いだし(Gar02 p. 390)、Alexandrov が証明を発表した(SvH19 p. 2)。左辺を「内積」、右辺を「長さの 2 乗の積」と見ると、Cauchy–Schwarz の不等式と向きが逆である。
$n=2$ の場合は $V(K,L)^2\ge\mathrm{vol}(K)\mathrm{vol}(L)$ で、混合体積 の定理「Minkowski の第 1 不等式」の平面の場合である。一般の $n$ では、この不等式から $V(K[k],L[n-k])$ の列の対数凹性、Minkowski の第 1 不等式、Brunn–Minkowskiの不等式、等周不等式 が導かれ、凸体の体積の不等式の多くを一つにまとめる。組合せ論では、半順序集合の線形拡大の数え上げに使われる。
証明は深い。この記事では、行列の版である 混合判別式についての Alexandrov の不等式 を完全に証明し(thm-af-discriminant)、そこから座標軸に平行な箱についての Alexandrov–Fenchel の不等式を導く(cor-af-boxes)。凸体の一般の場合は、同じ考え方で証明する Y. Shenfeld と R. van Handel の方法の組み立てを述べる。そのあと、一般の不等式から従う結果を証明する。
凸体(空でないコンパクト凸集合)と混合体積 $V(K_1,\dots,K_n)$ は 混合体積 のとおりとし、$K$ を $k$ 個並べることを $K[k]$ と書く。
$n\ge2$ と $\mathbb R^n$ の凸体 $K_1,\dots,K_n$ について
$$
V(K_1,K_2,K_3,\dots,K_n)^2\ge V(K_1,K_1,K_3,\dots,K_n)\,V(K_2,K_2,K_3,\dots,K_n)
$$
が成り立つ。
$n\times n$ の実対称行列の全体を $\mathrm{Sym}_n$ と書く。$M\succeq0$ は半正定値、$M\succ0$ は 正定値行列 であることを表す。
$M_1,\dots,M_m\in\mathrm{Sym}_n$ について $\det(\lambda_1M_1+\dots+\lambda_mM_m)$ は $\lambda$ の $n$ 次斉次多項式である。引数について対称な多重線形関数 $D\colon(\mathrm{Sym}_n)^n\to\mathbb R$ で
$$
\det\Bigl(\sum_{i=1}^m\lambda_iM_i\Bigr)=\sum_{i_1,\dots,i_n=1}^m\lambda_{i_1}\cdots\lambda_{i_n}D(M_{i_1},\dots,M_{i_n})
$$
をみたすものがただ一つあり、これを 混合判別式(mixed discriminant)という。$D(M_1,\dots,M_n)$ は $\det(\sum_{i=1}^n\lambda_iM_i)$ の $\lambda_1\cdots\lambda_n$ の係数の $1/n!$ で、$D(M,\dots,M)=\det M$ である。
混合体積と同じく、$D$ は $\det$ の偏極(混合体積 の命題「基本性質」の 2 と同じ包除の式)で与えられる。
$M_1,\dots,M_n\in\mathrm{Sym}_n$ とする。
要点:スペクトル定理 により対称行列は $vv^{\mathsf T}$ の 1 次結合なので、多重線形性から階数 1 の場合に帰着する。
1:$\sum\lambda_iv_iv_i^{\mathsf T}=V\,\mathrm{diag}(\lambda)\,V^{\mathsf T}$ なので行列式は $\lambda_1\cdots\lambda_n\det(V)^2$ である。$\lambda_1\cdots\lambda_n$ の係数は定義の和で $n!$ 個の並びから来るので $n!D=\det(V)^2$ である。
2:$U(vv^{\mathsf T})U^{\mathsf T}=(Uv)(Uv)^{\mathsf T}$ と 1 から、階数 1 の場合は $\det(UV)^2=\det(U)^2\det(V)^2$ による。一般には多重線形性で広げる。
3:半正定値行列は $vv^{\mathsf T}$ の $0$ 以上の係数の和なので、1 から $D$ は $0$ 以上の項の和である。
4:$M_1=v_1v_1^{\mathsf T}+M_1'$($v_1\ne0$、$M_1'\succeq0$)と書ける。$v_1$ を基底 $v_1,\dots,v_n$ に延ばす。$M_k\succ0$ なので、小さい $\varepsilon>0$ で $M_k-\varepsilon v_kv_k^{\mathsf T}\succeq0$($k\ge2$)である。多重線形性で展開すると、3 から $D(M_1,\dots,M_n)\ge D(v_1v_1^{\mathsf T},\varepsilon v_2v_2^{\mathsf T},\dots,\varepsilon v_nv_n^{\mathsf T})=\varepsilon^{n-1}\det(v_1,\dots,v_n)^2/n!>0$ である。
5:$M_k=v_kv_k^{\mathsf T}$ のとき、$\det(e_i,v_2,\dots,v_n)$ を第 1 列で展開すると $\pm\det(W)$($W$ は $v_2,\dots,v_n$ から第 $i$ 成分を除いた列からなる行列)で、$(v_kv_k^{\mathsf T})^{(i)}=v_k^{(i)}v_k^{(i)\mathsf T}$ である。1 から左辺は $\det(W)^2/n!$、右辺は $\frac1n\det(W)^2/(n-1)!$ で等しい。一般には多重線形性で広げる。$\blacksquare$
対角行列では混合判別式はパーマネントになる。$a^1,\dots,a^n\in\mathbb R^n$ について $\det(\sum_i\lambda_i\mathrm{diag}(a^i))=\prod_k\sum_i\lambda_ia^i_k$ なので、$n\times n$ 行列 $(a^i_k)_{i,k}$ のパーマネントを $\mathrm{per}$ として $n!\,D(\mathrm{diag}(a^1),\dots,\mathrm{diag}(a^n))=\mathrm{per}(a^i_k)$ である(Huh18 §2.1、p. 4)。
$W$ を有限次元実ベクトル空間、$Q$ を $W$ 上の対称双線形形式とする。
1:$Q(y,y)=0$ なら明らかなので $Q(y,y)>0$ とする。仮定から $Q(y,w)\ne0$ である。$a:=Q(x,w)/Q(y,w)$、$z:=x-ay$ とおくと $Q(z,w)=0$ なので
$$
0\ge Q(z,z)=Q(x,x)-2aQ(x,y)+a^2Q(y,y)\ge Q(x,x)-\frac{Q(x,y)^2}{Q(y,y)}
$$
である。最後の不等号は、$a$ の 2 次式の最小値が右辺であることによる。
2:正の固有値がなければ $Q(x,x)\le0$ がつねに成り立ち、$w=0$ でよい。正の固有値 $\lambda_1$ がただ一つなら、その固有ベクトルを $w$ とする。スペクトル定理 で $T$ を正規直交基底で対角化すると、$(x,w)=0$ のとき $Q(x,x)$ は $0$ 以下の固有値だけの和で $0$ 以下である。$Q(x,w)=\lambda_1(x,w)$ なので $Q(x,w)=0$ と $(x,w)=0$ は同じである。$\blacksquare$
これは SvH19 Lemma 2.9(arXiv 版 pp. 8–9)の一部である。Alexandrov–Fenchel の不等式は、混合体積の定める 2 次形式の正の固有値が 1 つであることの言い換えになっている。
$n\ge2$ とし、$A\in\mathrm{Sym}_n$、$B,M_3,\dots,M_n\succeq0$ とする。このとき
$$
D(A,B,M_3,\dots,M_n)^2\ge D(A,A,M_3,\dots,M_n)\,D(B,B,M_3,\dots,M_n)
$$
が成り立つ。
これは SvH19 Theorem 1.3(arXiv 版 p. 3。そこでは行列の次数を $n-1$ と書いている)である。証明は $n$ についての帰納法で、SvH19 §4(Lemma 4.1・4.2、Corollary 4.3、arXiv 版 pp. 11–12)に従う。
$n=2$。 まず $B\succ0$ とする。lem-af-discriminant-basic の 2 を $U=B^{-1/2}$ で使うと両辺は同じ $\det(U)^4$ 倍になるので、$B=I$ としてよい。さらに直交行列で $A$ を対角化しても(2 から)両辺は変わらないので、$A=\mathrm{diag}(a,b)$ としてよい。$\det(\lambda A+\mu I)=(\lambda a+\mu)(\lambda b+\mu)$ から $D(A,I)=\frac{a+b}2$、$D(A,A)=ab$、$D(I,I)=1$ で、主張は $\bigl(\frac{a+b}2\bigr)^2\ge ab$ である。$B\succeq0$ の場合は $B+\varepsilon I$ に当てて $\varepsilon\to0$ とする($D$ は成分の多項式で連続)。
$n\ge3$、対角の場合。 $n-1$ 次で定理が成り立つと仮定する。$M_4,\dots,M_n\succ0$($n=3$ ではなし)を固定し、$x,y\in\mathbb R^n$ について
$$
Q(x,y):=D\bigl(\mathrm{diag}(x),\mathrm{diag}(y),I,M_4,\dots,M_n\bigr)
$$
とおく。$\mathrm{diag}(x)=\sum_ix_ie_ie_i^{\mathsf T}$ と lem-af-discriminant-basic の 5 から、$Y_i:=\mathrm{diag}(y)^{(i)}$、$\mathcal M_i:=(M_4^{(i)},\dots,M_n^{(i)})$ と書いて
$$
Q(x,y)=\frac1n\sum_{i=1}^nx_i\,D(Y_i,I,\mathcal M_i)
$$
である(右辺の $I$ は $n-1$ 次)。$p_i:=\frac1nD(I,I,\mathcal M_i)$ とおくと、$M_k^{(i)}$ は $M_k$ の主小行列で正定値なので、lem-af-discriminant-basic の 4 により $p_i>0$ である。$(Ty)_i:=D(Y_i,I,\mathcal M_i)/D(I,I,\mathcal M_i)$ で行列 $T$ を定め、内積 $(x,y)_p:=\sum_ip_ix_iy_i$ を入れると $Q(x,y)=(x,Ty)_p$ である。$Q$ は対称なので $T$ は $(\cdot,\cdot)_p$ について自己随伴で、スペクトル定理 により固有値は実数で、固有ベクトルからなる基底がある。
$T$ の成分は、$j\ne i$ では $(e_j)^{(i)}\ne0$ なので 4 により $T_{ij}>0$、また $T_{ii}=0$ である。$\mathbf 1=(1,\dots,1)$ では $Y_i=I$ なので $T\mathbf 1=\mathbf 1$、すなわち各行の和は $1$ である。固有値 $\lambda$、固有ベクトル $y$ について $|y_i|$ が最大の $i$ をとると $|\lambda||y_i|\le\sum_jT_{ij}|y_j|\le|y_i|$ なので $|\lambda|\le1$ である。$Ty=y$ なら $y_i$ が最大の $i$ で $y_i=\sum_{j\ne i}T_{ij}y_j\le y_i$ で、$T_{ij}>0$ から等号はすべての $y_j=y_i$ のときに限るので、固有値 $1$ の固有空間は $\mathbf 1$ で張られる。
帰納法の仮定を $n-1$ 次の行列 $Y_i$、$I$、$\mathcal M_i$ に当てると $D(Y_i,I,\mathcal M_i)^2\ge D(Y_i,Y_i,\mathcal M_i)D(I,I,\mathcal M_i)$ なので
$$
p_i(Ty)_i^2=\frac{D(Y_i,I,\mathcal M_i)^2}{n\,D(I,I,\mathcal M_i)}\ge\frac1nD(Y_i,Y_i,\mathcal M_i)
$$
である。$i$ について足し、第 1 引数の $I=\sum_ie_ie_i^{\mathsf T}$ に 5 を使うと、右辺の和は $D(I,\mathrm{diag}(y),\mathrm{diag}(y),M_4,\dots,M_n)=Q(y,y)$ である。よって
$$
(Ty,Ty)_p\ge(y,Ty)_p
$$
である。$y$ を固有値 $\lambda$ の固有ベクトルにとると $\lambda^2\ge\lambda$、すなわち $\lambda\le0$ または $\lambda\ge1$ で、$|\lambda|\le1$ と合わせて正の固有値は $1$ だけ、その重複度は $1$ である。lem-af-hyperbolic の 2 と 1 を $y=\mathbf 1$($Q(\mathbf 1,\mathbf 1)=D(I,I,I,M_4,\dots)>0$)に使うと、
$$
D(Z,I,I,M_4,\dots,M_n)^2\ge D(Z,Z,I,M_4,\dots,M_n)\,D(I,I,I,M_4,\dots,M_n)\qquad(\ast)
$$
がすべての対角行列 $Z$ について成り立つ。
$n\ge3$、一般の場合。 まず $M_3,\dots,M_n\succ0$ とする。2 を $U=M_3^{-1/2}$ で使うと、両辺は同じ $\det(U)^4$ 倍になり、$A$ は対称、$B$ は半正定値、$M_k$ は正定値のままなので、$M_3=I$ としてよい。$\mathrm{Sym}_n$ 上の対称双線形形式 $Q(Z,Z'):=D(Z,Z',I,M_4,\dots,M_n)$ を考える。$Z\in\mathrm{Sym}_n$ を直交行列 $O$ で $O^{\mathsf T}ZO$ と対角化すると、2 から $Q$ の値は $Z$、$I$、$M_k$ を $O^{\mathsf T}ZO$、$I$、$O^{\mathsf T}M_kO\succ0$ に替えても変わらない。よって $(\ast)$ から $Q(Z,I)^2\ge Q(Z,Z)Q(I,I)$ がすべての $Z\in\mathrm{Sym}_n$ で成り立ち、$Q(I,I)>0$ なので「$Q(Z,I)=0$ なら $Q(Z,Z)\le0$」である。lem-af-hyperbolic の 1 を $w=I$ で使うと、$Q(B,B)\ge0$(3)なので $Q(A,B)^2\ge Q(A,A)Q(B,B)$ で、これが主張である。$M_k\succeq0$ の場合は $M_k+\varepsilon I$ に当てて $\varepsilon\to0$ とする。$\blacksquare$
$B=I$ の場合を見ると、この不等式は「固定した $M_3,\dots,M_n$ について $Z\mapsto D(Z,Z,M_3,\dots,M_n)$ の正の固有値は 1 つ」という主張にあたる(Huh18 §2.1 の Theorem 1、p. 4 はこの形で述べる)。
$a^1,\dots,a^n\in\mathbb R_{\ge0}^n$ について、座標軸に平行な箱 $K_i:=\prod_{k=1}^n[0,a^i_k]$ は thm-af-main の不等式をみたす。言い換えると、$0$ 以上の成分の列ベクトルについて $\mathrm{per}(a^1,a^2,a^3,\dots)^2\ge\mathrm{per}(a^1,a^1,a^3,\dots)\,\mathrm{per}(a^2,a^2,a^3,\dots)$ である。
$\lambda_i\ge0$ について $\sum_i\lambda_iK_i=\prod_k[0,\sum_i\lambda_ia^i_k]$ なので、$\mathrm{vol}(\sum_i\lambda_iK_i)=\prod_k\sum_i\lambda_ia^i_k=\det\bigl(\sum_i\lambda_i\mathrm{diag}(a^i)\bigr)$ である。係数を比べると $V(K_1,\dots,K_n)=D(\mathrm{diag}(a^1),\dots,\mathrm{diag}(a^n))$ で、引数が重複する場合も同じである。$\mathrm{diag}(a^i)\succeq0$ なので thm-af-discriminant から主張が従う。パーマネントの形は、$n!\,D=\mathrm{per}$ による。$\blacksquare$
たとえば $n=3$、$a^1=(1,2,3)$、$a^2=(3,1,1)$、$a^3=(1,1,2)$ では、パーマネントは $29^2=841\ge26\cdot20=520$ である。パーマネントの不等式は、van der Waerden予想(パーマネント) の Egorychev・Falikman による解決に使われた(Huh18 §2.1、p. 4)。
thm-af-main を一般の凸体について示すには、混合体積を混合判別式で表す必要がある。SvH19 は次の順に進む。この記事ではこの部分を証明しない。
以下、thm-af-main を認めて使う。
凸体 $K,L\subset\mathbb R^n$ について $V_k:=V(K[k],L[n-k])$($0\le k\le n$)とおくと、$1\le k\le n-1$ で $V_k^2\ge V_{k-1}V_{k+1}$ である。
thm-af-main を $K_1=K$、$K_2=L$ と、残りの $n-2$ 個を $K[k-1]$、$L[n-k-1]$ として使う。左辺は $V(K[k],L[n-k])^2$、右辺は $V(K[k+1],L[n-k-1])\,V(K[k-1],L[n-k+1])$ である。$\blacksquare$
これは Huh18 §2.2(p. 5)にある形で、対数凹数列 の典型例である。
凸体 $K,L\subset\mathbb R^n$ について $V(K[n-1],L)^n\ge\mathrm{vol}(K)^{n-1}\mathrm{vol}(L)$ であり、$\mathrm{vol}(K+L)^{1/n}\ge\mathrm{vol}(K)^{1/n}+\mathrm{vol}(L)^{1/n}$ である。
まず $K,L$ が内点をもつとする。混合体積 の定理「単調性」により $V_k>0$ で、cor-af-logconcave から比 $r_k:=V_k/V_{k-1}$($1\le k\le n$)は $k$ について増加しない($V_k^2\ge V_{k-1}V_{k+1}$ は $r_k\ge r_{k+1}$ と同じ)。よって
$$
\frac{V_{n-1}}{V_0}=r_1r_2\cdots r_{n-1}\ge r_n^{\,n-1}=\Bigl(\frac{V_n}{V_{n-1}}\Bigr)^{n-1}
$$
で、$V_{n-1}^n\ge V_n^{n-1}V_0$ である。$V_n=\mathrm{vol}(K)$、$V_{n-1}=V(K[n-1],L)$、$V_0=\mathrm{vol}(L)$ なので第 1 の不等式を得る。一般の場合は $K+\varepsilon B$、$L+\varepsilon B$ に当てて、混合体積の連続性で $\varepsilon\to0$ とする。
第 2 の不等式:$M:=K+L$ とすると、多重線形性から $\mathrm{vol}(M)=V(M[n-1],K+L)=V(M[n-1],K)+V(M[n-1],L)$ で、第 1 の不等式から右辺は $\mathrm{vol}(M)^{(n-1)/n}\bigl(\mathrm{vol}(K)^{1/n}+\mathrm{vol}(L)^{1/n}\bigr)$ 以上である。$\mathrm{vol}(M)>0$ なら両辺を $\mathrm{vol}(M)^{(n-1)/n}$ で割ればよく、$\mathrm{vol}(M)=0$ なら $\mathrm{vol}(K)=\mathrm{vol}(L)=0$ で明らかである。$\blacksquare$
混合体積 の記事ではこの 2 つを逆向きに、Brunn–Minkowskiの不等式 から第 1 の不等式を導いた。$L=B$(単位球)とすると 等周不等式 になる(混合体積 の定理「Minkowski の第 1 不等式」のあとの注意)。
$n=3$ で $K_1=K$、$K_2=B$、$K_3=K$ とすると $V(K,K,B)^2\ge\mathrm{vol}(K)\,V(K,B,B)$ である。Steinerの公式 の内在的体積で書くと $V(K,K,B)=\frac13S(K)$($S$ は表面積)、$V(K,B,B)=\frac\pi3V_1(K)$ なので
$$
S(K)^2\ge3\pi\,V_1(K)\,\mathrm{vol}(K)
$$
である。半径 $r$ の球では $S=4\pi r^2$、$V_1=4r$、$\mathrm{vol}=\frac43\pi r^3$ で等号が成り立つ。1 辺 $1$ の立方体では $S=6$、$V_1=3$、$\mathrm{vol}=1$ で $36\ge9\pi\approx28.3$ である。
組合せ論への応用。 有限の半順序集合 $P$ と $x\in P$ について、$P$ の線形拡大(全順序への延長)のうち $x$ が大きい方から $i$ 番目に来るものの割合を $\Pr_i(x)$ とすると、$\Pr_i(x)^2\ge\Pr_{i-1}(x)\Pr_{i+1}(x)$ が成り立つ。これは Chung・Fishburn・Graham の予想で、R. P. Stanley が適当な凸多面体を作って Alexandrov–Fenchel の不等式から証明した(1981 年。Huh18 §2.2、p. 5)。同じ方法で J. Kahn と M. Saks は、鎖でない有限半順序集合には $\frac3{11}\le\Pr(x_1< x_2)\le\frac8{11}$ となる 2 元があることを示した(同)。半順序集合 を参照。
| 外す仮定 | 対象 | 成り立たなくなること |
|---|---|---|
| thm-af-discriminant の $B\succeq0$($n=2$) | $A=\mathrm{diag}(1,-1)$、$B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ | $D(A,B)^2=0$、$D(A,A)D(B,B)=1$ で、不等式が成り立たない |
| thm-af-discriminant の $M_3\succeq0$($n=3$) | $A=\mathrm{diag}(1,-1,0)$、$B=I$、$M_3=\mathrm{diag}(1,1,-1)$ | $D(A,B,M_3)^2=0$、$D(A,A,M_3)D(B,B,M_3)=\frac19$ で、不等式が成り立たない |
| lem-af-hyperbolic の 2 の「正の固有値は高々 1 個」 | $\mathbb R^2$ の標準内積で $Q(x,y)=(x,y)$ | $x=e_1$、$y=e_2$ で $Q(x,y)^2=0< 1=Q(x,x)Q(y,y)$ で、逆向きの Cauchy–Schwarz の不等式が成り立たない |
各行で外した仮定は一つだけである。
1 行目:$A$ は対称で、$B$ は固有値 $\pm1$ をもち半正定値でない($n=2$ なのでほかの行列はない)。$\det(\lambda A+\mu B)=-\lambda^2-\mu^2$ なので $D(A,A)=D(B,B)=-1$、$\lambda\mu$ の係数は $0$ で $D(A,B)=0$ である。
2 行目:$A$ は対称、$B=I$ は半正定値で、$M_3$ だけが半正定値でない。$\det(\lambda A+\mu I+\nu M_3)=\bigl((\mu+\nu)^2-\lambda^2\bigr)(\mu-\nu)$ である。$\lambda\mu\nu$ の項はないので $D(A,I,M_3)=0$、$\lambda^2\nu$ の係数は $1$ で $3D(A,A,M_3)=1$、$\mu^2\nu$ の係数は $-1+2=1$ で $3D(I,I,M_3)=1$ である。
3 行目:$Q$ は対称で、対応する写像は恒等写像で正の固有値 $1$ を 2 個もつ。$Q(y,y)=1\ge0$ なので lem-af-hyperbolic の 1 の結論が当てはまるはずの組であり、$0<1$ で成り立たない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する