Johnの楕円体定理(John's ellipsoid theorem)とは、$\mathbb R^n$ の凸体(内部が空でないコンパクト凸集合)$K$ に含まれる楕円体のうち体積が最大のものがただ一つあり、$K$ が単位球 $B$ を含むとき、それが $B$ であることは、$K$ の境界上の単位ベクトル $u_i$ と正の重み $c_i$ で $\sum c_iu_i=0$ かつ $\sum c_iu_iu_i^{\mathsf T}=I$ となるものがあることと同値である、という定理である。F. John が 1948 年に示した。ここから、凸体は最大体積の楕円体を中心のまわりに $n$ 倍したものに含まれ、中心対称なら $\sqrt n$ 倍に含まれることが従い、正単体と立方体ではそれぞれの倍率を小さくできない。
前提知識: 凸集合, 凸集合の分離定理, 相加相乗平均の不等式, 行列式
Johnの楕円体定理(John's ellipsoid theorem)は、$\mathbb R^n$ の凸体(内部が空でないコンパクト凸集合)$K$ に含まれる楕円体のうち体積が最大のものがただ一つあり、$K$ が単位球 $B$ を含むとき、それが $B$ であることは、$K$ の境界と単位球面の接点に「重心が原点で、慣性テンソルが単位行列」となる重みを置けることと同値である、という定理である。F. John が 1948 年に示した(Bal97 Lecture 3、p. 13)。
この特徴づけからすぐに、$K$ は最大体積の楕円体 $E$ を中心のまわりに $n$ 倍した楕円体に含まれ、$K$ が中心対称なら $\sqrt n$ 倍に含まれることが従う。どんな凸体も、アフィン変換で形を整えれば球から $n$ 倍(対称なら $\sqrt n$ 倍)以内にあるということで、ノルム空間の Banach–Mazur距離 の評価や、Brascamp–Liebの不等式 を使った体積の評価の出発点になる。
この記事では、最大体積の楕円体の存在と一意性(thm-john-unique)、接点による特徴づけ(thm-john-main)、包含の評価(cor-john-inclusion)を完全に証明し、立方体と正単体で評価が最良であることを確かめる。
以下 $n\ge1$ とし、$\mathbb R^n$ に標準内積 $\langle\cdot,\cdot\rangle$ と Euclid ノルム $\lvert\cdot\rvert$ を入れる。$B:=\{x\mid\lvert x\rvert\le1\}$ を閉単位球、$S^{n-1}:=\partial B$ を単位球面、$\omega_n$ を $B$ の体積とする。$n$ 次の実対称行列の全体を $\mathrm{Sym}(n)$、正定値なものの全体を $\mathrm{Sym}^+(n)$ と書き、$A\in\mathrm{Sym}(n)$ の作用素ノルムを $\|A\|$ とする。$u\in\mathbb R^n$ を縦ベクトルとみて、$uu^{\mathsf T}$ は $x\mapsto\langle x,u\rangle u$ を表す行列である。
内部が空でないコンパクト凸集合 $K\subset\mathbb R^n$ を 凸体 という。$c\in\mathbb R^n$ と可逆な線形写像 $T$ による $B$ の像 $c+T(B)$ を 楕円体 といい、$c$ をその中心という。楕円体 $c+T(B)$ の体積は $\lvert\det T\rvert\,\omega_n$ である。
$T$ の極分解 $T=PU$($P=(TT^{\mathsf T})^{1/2}\in\mathrm{Sym}^+(n)$、$U$ は直交行列。極分解)をとると $U(B)=B$ なので $T(B)=P(B)$、$\det P=\lvert\det T\rvert$ である。したがって楕円体はいつも $c+P(B)$($P\in\mathrm{Sym}^+(n)$)と書け、以下ではこの形を使う。$P$ の固有値は楕円体の半径(主軸の長さの半分)である。
凸体 $K$ に含まれる楕円体のうち体積が最大のもの(thm-john-unique によりただ一つある)を $K$ の John 楕円体 という。$B\subset K$ のとき、$S^{n-1}\cap\partial K$ の点を $K$ と $B$ の 接点 という。
$\varphi(x)=Ax+b$($A$ は可逆)をアフィン写像とすると、$\varphi$ は凸体を凸体に、楕円体を楕円体に写し、どの体積も同じ $\lvert\det A\rvert$ 倍にする。したがって $\varphi(K)$ の John 楕円体は $\varphi(E)$ である($E$ は $K$ の John 楕円体)。とくに、$E=c+P(B)$ のとき $\varphi(x)=P^{-1}(x-c)$ で $E$ を $B$ に移せるので、John 楕円体についての主張の多くは $E=B$ の場合に帰着する。
$A_1,A_2\in\mathrm{Sym}^+(n)$ について
$$
\det\Bigl(\frac{A_1+A_2}2\Bigr)\ge\sqrt{\det A_1\det A_2}
$$
であり、等号は $A_1=A_2$ のときに限る。
要点:$A_1^{-1/2}A_2A_1^{-1/2}$ の固有値ごとに相加相乗平均の不等式を使う。
$A_1^{1/2}$ を $A_1$ の正定値な平方根とし、$M:=A_1^{-1/2}A_2A_1^{-1/2}$ とおく。$M\in\mathrm{Sym}^+(n)$ なので固有値 $\lambda_1,\dots,\lambda_n$ はすべて正で、$\det M=\det A_2/\det A_1$ である。$\frac{A_1+A_2}2=A_1^{1/2}\frac{I+M}2A_1^{1/2}$ なので、$\det\frac{A_1+A_2}2=\det A_1\prod_i\frac{1+\lambda_i}2\ge\det A_1\prod_i\sqrt{\lambda_i}=\det A_1\sqrt{\det M}=\sqrt{\det A_1\det A_2}$ である。不等号は各因子の $\frac{1+\lambda_i}2\ge\sqrt{\lambda_i}$(相加相乗平均の不等式)で、因子はすべて正なので、等号はすべての $i$ で $\lambda_i=1$、すなわち $M=I$、すなわち $A_2=A_1$ のときに限る。$\square$
凸体 $K\subset\mathbb R^n$ に含まれる楕円体のうち、体積が最大のものがただ一つある。
存在。 $\mathcal S:=\{(c,A)\in\mathbb R^n\times\mathrm{Sym}(n)\mid A\text{ は半正定値},\ c+A(B)\subset K\}$ とおく。$(c,A)\in\mathcal S$ なら $c\in K$ で、$\lvert x\rvert\le1$ について $c\pm Ax\in K$ から $2\lvert Ax\rvert\le\operatorname{diam}K$ なので、$\mathcal S$ は有界である。$(c_k,A_k)\in\mathcal S$ が $(c,A)$ に収束すれば、各 $x\in B$ で $c+Ax=\lim(c_k+A_kx)\in K$($K$ は閉)なので $\mathcal S$ は閉で、したがってコンパクトである。連続関数 $\det$ は $\mathcal S$ 上で最大値をとる。$K$ は内点 $p$ をもつので $p+\varepsilon B\subset K$ となる $\varepsilon>0$ があり、$(p,\varepsilon I)\in\mathcal S$ だから最大値は $\varepsilon^n>0$ 以上である。最大を与える $(c_0,A_0)$ では $A_0$ は正定値で、$E_0:=c_0+A_0(B)$ は楕円体である。$K$ に含まれる楕円体はどれも $c+P(B)$($P\in\mathrm{Sym}^+(n)$)と書けて $(c,P)\in\mathcal S$ なので、体積 $\omega_n\det P$ は $\omega_n\det A_0$ 以下である。
一意性。 $E_i=c_i+A_i(B)$($i=1,2$、$A_i\in\mathrm{Sym}^+(n)$)がともに最大体積とする。$x\in B$ について
$$
\frac{c_1+c_2}2+\frac{A_1+A_2}2x=\frac12(c_1+A_1x)+\frac12(c_2+A_2x)\in K
$$
($K$ は凸)なので、楕円体 $\frac{c_1+c_2}2+\frac{A_1+A_2}2(B)$ は $K$ に含まれる。lem-john-det によりその体積は $E_1,E_2$ の体積以上で、最大性から等号が成り立つので $A_1=A_2=:A$ である。
$c_1\ne c_2$ と仮定して矛盾を導く。アフィン写像 $\varphi(x)=A^{-1}(x-c_1)$ で写すと、凸体 $K':=\varphi(K)$ は $B$ と $B+v$($v:=A^{-1}(c_2-c_1)\ne0$)を含み、$B$ は $K'$ に含まれる最大体積の楕円体である。$v=2te$($t>0$、$\lvert e\rvert=1$)と書き、楕円体
$$
F:=te+\Bigl\{y\ \Big|\ \frac{\langle y,e\rangle^2}{(1+t)^2}+\lvert y-\langle y,e\rangle e\rvert^2\le1\Bigr\}
$$
を考える。$K'$ は凸なので、$B$ と $B+v$ の凸包 $B+[0,v]$($B$ と線分 $[0,v]$ の Minkowski 和)を含む。$F$ の点 $te+y$ について $s:=\langle y,e\rangle$、$w:=y-se$ とおくと $\lvert w\rvert^2\le1-s^2/(1+t)^2$、$\lvert s\rvert\le1+t$ で、$te+y=(t+s)e+w$ である。$\lvert s\rvert\le t$ なら $(t+s)e\in[0,v]$ からの距離が $\lvert w\rvert\le1$ である。$t< s\le1+t$ なら $v=2te$ からの距離の 2 乗は $(s-t)^2+\lvert w\rvert^2\le(s-t)^2+1-s^2/(1+t)^2$ で、$0< s-t\le s/(1+t)$($s\le1+t$ と同値)からこれは $1$ 以下である。$-1-t\le s< -t$ も同様で、どの場合も $te+y\in B+[0,v]\subset K'$ である。$F$ の体積は $(1+t)\omega_n>\omega_n$ なので、$B$ の最大性に反する。よって $c_1=c_2$ で、$E_1=E_2$ である。$\square$
凸体 $K$ が $B$ を含み、$u$ が接点なら、$K\subset\{x\mid\langle x,u\rangle\le1\}$ である。
要点:$K$ の $u$ での支持超平面は $B$ の支持超平面でもあり、それは $u$ に垂直なものに限る。
$K$ の内部 $\operatorname{int}K$ は空でない開凸集合で、$u\in\partial K$ は $\operatorname{int}K$ に属さないので、凸集合の分離定理 により $a\ne0$ で、すべての $y\in\operatorname{int}K$ について $\langle y,a\rangle< \langle u,a\rangle$ となるものがある。凸体は内部の閉包に等しいので、$y\in K$ について $\langle y,a\rangle\le\langle u,a\rangle$ である。$y=a/\lvert a\rvert\in B\subset K$ を入れると $\lvert a\rvert\le\langle u,a\rangle\le\lvert u\rvert\lvert a\rvert=\lvert a\rvert$ で、Cauchy–Schwarzの不等式 の等号条件から $a=\lvert a\rvert u$ である。よって $y\in K$ なら $\langle y,u\rangle\le\langle u,u\rangle=1$ である。$\square$
凸体 $K\subset\mathbb R^n$ が $B$ を含むとする。次の 2 条件は同値である。
等方の条件は、すべての $x$ について $\lvert x\rvert^2=\sum_ic_i\langle x,u_i\rangle^2$、すなわち $x=\sum_ic_i\langle x,u_i\rangle u_i$ と同じである。接点に重み $c_i$ を置くと、重心が原点にあり(重心の条件)、どの方向にも同じだけ広がっている(等方の条件)。$K$ が中心対称($K=-K$)なら、等方の条件を満たす接点の組の各 $u_i$ を重み $c_i/2$ の $\pm u_i$ に置き換えれば重心の条件も成り立つ($-u_i$ も接点である)。
2 ⇒ 1。 $E=a+T(B)\subset K$($T\in\mathrm{Sym}^+(n)$)を任意の楕円体とする。$\max_{\lvert y\rvert\le1}\langle Ty,u\rangle=\max_{\lvert y\rvert\le1}\langle y,Tu\rangle=\lvert Tu\rvert$ なので、lem-john-support から各 $i$ で
$$
\langle a,u_i\rangle+\lvert Tu_i\rvert=\max_{x\in E}\langle x,u_i\rangle\le1
$$
である。$c_i$ を掛けて足すと、重心の条件から $\sum_ic_i\langle a,u_i\rangle=0$ なので $\sum_ic_i\lvert Tu_i\rvert\le\sum_ic_i=n$ である。一方 $\langle Tu_i,u_i\rangle\le\lvert Tu_i\rvert$ と 等方の条件から
$$
\operatorname{tr}T=\operatorname{tr}\Bigl(T\sum_ic_iu_iu_i^{\mathsf T}\Bigr)=\sum_ic_i\langle Tu_i,u_i\rangle\le\sum_ic_i\lvert Tu_i\rvert\le n
$$
である。$T$ の固有値 $\mu_1,\dots,\mu_n>0$ に 相加相乗平均の不等式 を使うと $\det T=\prod_j\mu_j\le(\operatorname{tr}T/n)^n\le1$ なので、$E$ の体積は $\omega_n$ 以下である。$B\subset K$ だから $B$ は最大体積の楕円体で、thm-john-unique により John 楕円体である。
1 ⇒ 2。 接点の集合 $C:=S^{n-1}\cap\partial K$ はコンパクトである。$C$ は空でない。実際、空なら $S^{n-1}\subset\operatorname{int}K$ で、コンパクト集合 $S^{n-1}$ と閉集合 $\mathbb R^n\setminus\operatorname{int}K$ の距離 $\delta$ は正だから $(1+\delta)B\subset K$ となり、$B$ の最大性に反する。
ベクトル空間 $V:=\mathrm{Sym}(n)\times\mathbb R^n$ に内積 $\langle(X,v),(Y,w)\rangle:=\operatorname{tr}(XY)+\langle v,w\rangle$ を入れ、$\Phi(u):=(uu^{\mathsf T},u)$ とおく。2 つの条件は、$(I_n/n,0)$ が $\Phi(C)$ の点の凸結合 $\sum_i\lambda_i\Phi(u_i)$($\lambda_i=c_i/n$)であることと同じである。$\Phi(C)$ はコンパクトなので、その凸包 $\operatorname{conv}\Phi(C)$ もコンパクトである(Carathéodoryの定理(凸幾何))。
$(I_n/n,0)\notin\operatorname{conv}\Phi(C)$ と仮定して矛盾を導く。点とコンパクト凸集合の分離(凸集合の分離定理)により $(H_0,h)\in V$ で、すべての $u\in C$ について
$$
\frac{\operatorname{tr}H_0}n< u^{\mathsf T}H_0u+\langle h,u\rangle
$$
となるものがある($\operatorname{tr}(uu^{\mathsf T}H_0)=u^{\mathsf T}H_0u$)。$H:=H_0-\frac{\operatorname{tr}H_0}nI_n$ とおくと $\operatorname{tr}H=0$ で、$\lvert u\rvert=1$ から $u^{\mathsf T}Hu=u^{\mathsf T}H_0u-\frac{\operatorname{tr}H_0}n$ なので、$g(x):=x^{\mathsf T}Hx+\langle h,x\rangle$ は $C$ の上で正である。
$0<\delta<1$、$\delta\|H\|<1$ について $I+\delta H$ は正定値で、
$$
q_\delta(x):=\Bigl(x+\frac{\delta h}2\Bigr)^{\mathsf T}(I+\delta H)\Bigl(x+\frac{\delta h}2\Bigr),\qquad E_\delta:=\{x\mid q_\delta(x)\le1\}
$$
とおくと $E_\delta=-\frac{\delta h}2+(I+\delta H)^{-1/2}(B)$ は楕円体である。$I+\delta H$ の固有値は正で和が $\operatorname{tr}(I+\delta H)=n$ なので、相加相乗平均の不等式から $\det(I+\delta H)\le1$ で、$E_\delta$ の体積 $\omega_n\det(I+\delta H)^{-1/2}$ は $\omega_n$ 以上である。
$E_\delta$ が $\partial K$ と交わらないことを、$\delta$ を小さくして示す。展開すると
$$
q_\delta(x)=\lvert x\rvert^2+\delta g(x)+\delta^2r_\delta(x),\qquad r_\delta(x):=\frac{\lvert h\rvert^2}4+x^{\mathsf T}Hh+\frac\delta4h^{\mathsf T}Hh
$$
である。$K\subset RB$ となる $R\ge1$ をとると、$x\in K$ について $\lvert g(x)\rvert\le G$、$\lvert r_\delta(x)\rvert\le Q$ となる定数 $G,Q$($\delta$ によらない)がある。$\eta:=\min_Cg>0$ とおき、開集合 $U:=\{x\mid g(x)>\eta/2\}$ をとる。
Bal97 pp. 16–19 は対称な場合だけを証明しており、2 ⇒ 1 では中心が原点の楕円体を比べている(p. 17)。上の証明では中心のずれ $a$ を重心の条件で消した。1 ⇒ 2 で $E_\delta$ を作る考え方(接点が球面の片側に寄っていれば球を動かして膨らませ、ある部分空間の近くに寄っていればその方向を縮めて直交方向を伸ばす)は Bal97 pp. 14, 17–19 にある。
凸体 $K$ の John 楕円体を $E=c+P(B)$ とすると
$$
E\subset K\subset c+nP(B)
$$
である。$K$ が $c$ について対称($x\in K\Rightarrow2c-x\in K$)なら $K\subset c+\sqrt n\,P(B)$ である。
アフィン写像 $x\mapsto P^{-1}(x-c)$ で写して $E=B$ の場合を示せばよい(対称の中心は $0$ に移る)。thm-john-main の $u_i,c_i$ をとり、$x\in K$、$t_i:=\langle x,u_i\rangle$ とおく。lem-john-support から $t_i\le1$、また $\lvert t_i\rvert\le\lvert x\rvert$ である。2 つの条件から $\sum_ic_it_i=0$、$\sum_ic_it_i^2=\lvert x\rvert^2$、$\sum_ic_i=n$ なので、各項が $0$ 以上であることから
$$
0\le\sum_ic_i(1-t_i)(\lvert x\rvert+t_i)=n\lvert x\rvert+\sum_ic_it_i-\lvert x\rvert\sum_ic_it_i-\sum_ic_it_i^2=n\lvert x\rvert-\lvert x\rvert^2
$$
となり、$\lvert x\rvert\le n$ である。$K=-K$ なら $-x\in K$ からも $-t_i\le1$ なので $\lvert t_i\rvert\le1$ で、$\lvert x\rvert^2=\sum_ic_it_i^2\le\sum_ic_i=n$ である。$\square$
対称な場合の包含は、Banach–Mazur距離 の定理「John の定理(対称な場合)」で、接点の特徴づけを経ずにはみ出す点の方向へ楕円体を伸ばす方法でも証明されている。$n$ 次元のノルム空間と $\ell_2^n$ の Banach–Mazur 距離が $\sqrt n$ 以下であることは、この包含の言い換えである。対称でない場合の評価 $\lvert x\rvert\le n$ は Bal97 p. 16 では演習として残されている。
$\langle u_i,u_j\rangle=\frac{n+1}n\bigl(\delta_{ij}-\frac1{n+1}\bigr)$ なので $\lvert u_j\rvert=1$、$i\ne j$ なら $\langle u_i,u_j\rangle=-\frac1n$ で、$\sum_ju_j=0$ である。$y\in L$ について $\sum_j\langle y,u_j\rangle^2=\frac{n+1}n\sum_jy_j^2=\frac{n+1}n\lvert y\rvert^2$ なので、$c_j:=\frac n{n+1}$ で 2 つの条件が成り立つ。$\Delta:=\{x\in L\mid\langle x,u_j\rangle\le1\ (j=0,\dots,n)\}$ は $B$ を含み、$u_j\in\Delta$ かつ $\langle u_j,u_j\rangle=1$ なので各 $u_j$ は接点である。$x\in\Delta$ なら $\sum_j\langle x,u_j\rangle=0$ から $\langle x,u_j\rangle\ge-n$ で、$\lvert x\rvert^2=\frac n{n+1}\sum_j\langle x,u_j\rangle^2\le n^2$ なので $\Delta$ は有界であり、凸体である。$B$ は $\Delta$ の John 楕円体で、$w_k:=-nu_k$ は $\langle w_k,u_j\rangle=1$($j\ne k$)、$\langle w_k,u_k\rangle=-n$ を満たす $\Delta$ の点(頂点)で、$\lvert w_k\rvert=n$ である。
Bal97 p. 19 は、凸体を含む楕円体のうち体積が最小のものもただ一つで、接点による同様の特徴づけをもち、双対性によって John の定理から導けることを述べている。立方体 $[-1,1]^n$ を含む体積最小の楕円体は半径 $\sqrt n$ の球で、立方体は相似な楕円体で $\sqrt n$ 倍より良くは挟めない(同 p. 19)。
各行は仮定を 1 つだけ外し、成り立たなくなる結論を名指しする。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 内部が空でない | $K=[-1,1]\times\{0\}\subset\mathbb R^2$(コンパクト凸) | thm-john-unique の存在:$K$ は楕円体を 1 つも含まない |
| 有界 | $K=\mathbb R\times[-1,1]\subset\mathbb R^2$(閉凸、内部は空でない) | thm-john-unique の存在:面積が最大の楕円はない |
| 凸 | $K=B(-3e_1,1)\cup B(3e_1,1)$(コンパクト、内部は空でない) | thm-john-unique の一意性:最大体積の楕円体が 2 つある |
| 重心の条件 | $n=1$、$K=[-1,3]$、接点 $u_1=-1$、$c_1=1$ | thm-john-main の 2 ⇒ 1:$B=[-1,1]$ は John 楕円体でない |
| 等方の条件 | $K=[-1,1]\times[-3,3]$、接点 $(\pm1,0)$、重み $\frac12$ | thm-john-main の 2 ⇒ 1:$B$ は John 楕円体でない |
| $K$ の対称性 | 正単体 $\Delta$($n\ge2$) | cor-john-inclusion の $K\subset\sqrt n\,B$ |
1 行目:楕円体は内部が空でない($c+P(B)$ は $c$ のまわりの球 $c+\mu B$ を含む。$\mu$ は $P$ の最小固有値)ので、内部が空の $K$ には含まれない。2 行目:$a>0$ について楕円 $\{x_1^2/a^2+x_2^2\le1\}$ は $K$ に含まれ、面積は $\pi a$ で上限がない。3 行目:楕円体は連結なので一方の球に含まれる。$c+P(B)\subset B(p,1)$ なら、$P$ の固有値 $\mu$ と単位固有ベクトル $v$ について $c\pm\mu v$ の距離 $2\mu$ は直径 $2$ 以下なので $\det P\le1$ で、体積は $\omega_n$ 以下である。2 つの球はどちらも体積 $\omega_n$ を実現する。4 行目:$\partial K=\{-1,3\}$ なので接点は $-1$ だけで、$c_1u_1u_1^{\mathsf T}=1=I_1$ だが $c_1u_1\ne0$。$K$ 自身が長さ $4$ の区間($1+2B$)で、$B$ より長い。5 行目:単位ベクトル $x$ が $\partial K$ にあれば $\lvert x_2\rvert\le1<3$ から $\lvert x_1\rvert=1$ なので接点は $(\pm1,0)$ だけで、重み $\frac12$ で重心の条件は成り立つが $\sum c_iu_iu_i^{\mathsf T}=\operatorname{diag}(1,0)\ne I_2$。楕円 $\{x_1^2+x_2^2/9\le1\}\subset K$ の面積は $3\pi>\pi$。6 行目:ex-john-cube-simplex の 2 で $B$ は $\Delta$ の John 楕円体だが、頂点 $w_k$ の長さは $n>\sqrt n$ である。
F. John は 1948 年の論文「Extremum problems with inequalities as subsidiary conditions」(R. Courant の 60 歳の記念論文集、Joh48)で、凸体に含まれる最大体積の楕円体がただ一つであることとその特徴づけを示した(Bal97 p. 13 と文献表 p. 54)。Bal97 は、この定理を出発点に、線形写像の行列式を条件のもとで最大にして凸体に付随する楕円体を作る理論が凸幾何で大きな役割を果たしたと述べている(p. 19)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する