0492-1995 东大工 数学 WEB

线性代数 空间向量

$S=\{{\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_k\}$ を $k$ 個の $n$ 次元実数行ベクトルの集合とする。
$S$ の任意の部分集合 $Q$ に対し、$Q$ 中のベクトルの和を $\mathbf{V}(Q)$ と書く。
とくに $Q$ が空集合の場合には、$\mathbf{V}(Q)$ は零ベクトルと定義する。
また $S$ の任意の部分集合 $R$ に対し、ベクトルの集合 $P(R)$ を $P(R)=\{\mathbf{V}(Q)\mid Q\subseteq S,Q\ne R\}$ と定義する。
以下の間に答えよ。

(1) $n=2,k=3,S=\{(2,1),(1,3),(-2,2)\},R=\{(2,1),(1,3)\}$ としたとき、$P(R)$ の要素をすべてあげよ。

(2) $n=2,k=3,S=\{(2,1),(1,3),(-2,2)\}$ としたとき、$S$ の部分集合 $R$ で、$\mathbf{V}(R)$ が $P(R)$ 中のベクトルの凸結合で表すことができないようなものをすべてあげよ。

(3) $S$ が線形独立ならば、$S$ の任意の部分集合 $R$ に対し、ベクトル $\mathbf{V}(R)$ は $P(R)$ 中のベクトルの凸結合で表すことはできないことを示せ。

(4) ベクトル ${\mathbf{x}}_1$ が、${\mathbf{x}}_2,{\mathbf{x}}_3,\cdots ,{\mathbf{x}}_k$ の非負結合で表されるとき、${\mathbf{x}}_1$ が零ベクトルと、${\mathbf{x}}_1+{\mathbf{x}}_2,{\mathbf{x}}_1+{\mathbf{x}}_3,\cdots ,{\mathbf{x}}_1+{\mathbf{x}}_k$ の凸結合で表されることを示せ。

(5) ベクトル ${\mathbf{x}}_1$ が、${\mathbf{x}}_2,{\mathbf{x}}_3,\cdots ,{\mathbf{x}}_k$ の線形結合で表されるとき、適当な $S$ の部分集合 $R$ が存在して、$\mathbf{V}(R)$ は $P(R)$ 中のベクトルの凸結合で表されることを示せ。
ここで、非負結合とは係数がすべて非負の線形結合をいう。凸結合とは、係数の和が $1$ である非負結合をいう。

---

解答：

(1)
$S$ のすべての部分集合 $Q$ に対する $\mathbf{V}(Q)$ を計算する。
$Q=\varnothing ⟹\mathbf{V}(\varnothing )=(0,0)$
$Q=\{(2,1)\}⟹\mathbf{V}(Q)=(2,1)$
$Q=\{(1,3)\}⟹\mathbf{V}(Q)=(1,3)$
$Q=\{(-2,2)\}⟹\mathbf{V}(Q)=(-2,2)$
$Q=\{(2,1),(1,3)\}=R⟹\mathbf{V}(Q)=(3,4)$
$Q=\{(2,1),(-2,2)\}⟹\mathbf{V}(Q)=(0,3)$
$Q=\{(1,3),(-2,2)\}⟹\mathbf{V}(Q)=(-1,5)$
$Q=\{(2,1),(1,3),(-2,2)\}⟹\mathbf{V}(Q)=(1,6)$

$P(R)$ は $Q\ne R$ なるすべての $\mathbf{V}(Q)$ の集合であるから、

$$\boxed{P(R)=\{(0,0),(2,1),(1,3),(-2,2),(0,3),(-1,5),(1,6)\}}$$

(2)
$\mathbf{V}(R)$ が $P(R)$ の凸結合で表せないための必要十分条件は、$\mathbf{V}(R)$ が集合 $\{\mathbf{V}(Q)\mid Q\subseteq S\}$ の凸包の狭義の端点となることである。
(1)より、全8個の $\mathbf{V}(Q)$ を平面上にプロットし、その凸包を考えると、端点となるのは以下の6点である。
$(0,0),(2,1),(3,4),(1,6),(-1,5),(-2,2)$
一方、残りの2点は以下のように他の端点の凸結合で表される。

$$\begin{array}{rl}(1,3)& =\frac{6}{19}(0,0)+\frac{8}{19}(3,4)+\frac{5}{19}(-1,5)\\ (0,3)& =\frac{2}{13}(2,1)+\frac{5}{13}(-2,2)+\frac{6}{13}(-1,5)\end{array}$$

したがって、凸結合で表せない $\mathbf{V}(R)$ に対応する $R$ は、

$$\boxed{\varnothing ,\{(2,1)\},\{(-2,2)\},\{(2,1),(1,3)\},\{(1,3),(-2,2)\},\{(2,1),(1,3),(-2,2)\}}$$

(3)
背理法により示す。$\mathbf{V}(R)$ が $P(R)$ 中のベクトルの凸結合で表せると仮定すると、${\lambda }_Q\ge 0,\sum _{Q\ne R}{\lambda }_Q=1$ を満たす実数 ${\lambda }_Q$ が存在して、

$$\sum _{{\mathbf{x}}_i\in R}{\mathbf{x}}_i=\sum _{Q\ne R}{\lambda }_Q\left(\sum _{{\mathbf{x}}_i\in Q}{\mathbf{x}}_i\right)=\sum _{i=1}^k\left(\sum _{Q\ne R,{\mathbf{x}}_i\in Q}{\lambda }_Q\right){\mathbf{x}}_i$$

$S$ は線形独立であるため、両辺の各 ${\mathbf{x}}_i$ の係数は一致する。
${\mathbf{x}}_i\in R$ のとき、係数は $1$ であり、$\sum _{Q\ne R,{\mathbf{x}}_i\in Q}{\lambda }_Q=1$ となる。$\sum _{Q\ne R}{\lambda }_Q=1$ と ${\lambda }_Q\ge 0$ より、${\lambda }_Q>0$ なるすべての $Q$ は ${\mathbf{x}}_i$ を含まなければならない。
${\mathbf{x}}_j\notin R$ のとき、係数は $0$ であり、$\sum _{Q\ne R,{\mathbf{x}}_j\in Q}{\lambda }_Q=0$ となる。${\lambda }_Q\ge 0$ より、${\lambda }_Q>0$ なるすべての $Q$ は ${\mathbf{x}}_j$ を含んではならない。
以上より、${\lambda }_Q>0$ となる $Q$ は $R$ と完全に一致する必要があるが、和は $Q\ne R$ について取られているため、そのような $Q$ は存在しない。
これは $\sum _{Q\ne R}{\lambda }_Q=1$ に矛盾する。したがって示された。
(証明終)

(4)
仮定より、${\mathbf{x}}_1=\sum _{i=2}^k{c}_i{\mathbf{x}}_i$ ($c_i\ge 0$) と表せる。ここで、

$${\lambda }_0=\frac{1}{1+{\sum }_{j=2}^k{c}_j},{\lambda }_i=\frac{c_i}{1+{\sum }_{j=2}^k{c}_j}(i=2,3,\cdots ,k)$$

とおくと、$c_i\ge 0$ より ${\lambda }_0>0,{\lambda }_i\ge 0$ であり、${\lambda }_0+\sum _{i=2}^k{\lambda }_i=1$ を満たす。
これらの係数を用いて凸結合を計算すると、

$$\begin{array}{rl}{\lambda }_{0}0+\sum _{i=2}^k{\lambda }_i({\mathbf{x}}_1+{\mathbf{x}}_i)& =\left(\sum _{i=2}^k{\lambda }_i\right){\mathbf{x}}_1+\sum _{i=2}^k{\lambda }_i{\mathbf{x}}_i\\ & =\frac{{\sum }_{i=2}^k{c}_i}{1+{\sum }_{j=2}^k{c}_j}{\mathbf{x}}_1+\frac{{\sum }_{i=2}^k{c}_i{\mathbf{x}}_i}{1+{\sum }_{j=2}^k{c}_j}\\ & =\frac{{\sum }_{i=2}^k{c}_i}{1+{\sum }_{j=2}^k{c}_j}{\mathbf{x}}_1+\frac{1}{1+{\sum }_{j=2}^k{c}_j}{\mathbf{x}}_1\\ & ={\mathbf{x}}_1\end{array}$$

となり、${\mathbf{x}}_1$ は零ベクトルと ${\mathbf{x}}_1+{\mathbf{x}}_i$ の凸結合で表される。
(証明終)

(5)
${\mathbf{x}}_1=\sum _{i=2}^k{c}_i{\mathbf{x}}_i$ と表せるため、$c_1=-1$ として $\sum _{i=1}^k{c}_i{\mathbf{x}}_i=0$ と書く。
集合 $R\subseteq S$ を $R=\{{\mathbf{x}}_i\in S\mid c_i<0\}$ と定義する。$c_1=-1<0$ より ${\mathbf{x}}_1\in R$ であり、$R\ne \varnothing$ である。実数 $t$ を

$$t=\min \left(\left\{-\frac{1}{c_i}|c_i<0\right\}\cup \left\{\frac{1}{c_i}|c_i>0\right\}\right)$$

と定める。$-\frac{1}{c_1}=1$ であるからこの集合は空でなく $t>0$ である。
各 $i$ について実数 $a_i$ を

$$a_i=\{\begin{array}{ll}1+t{c}_i& ({\mathbf{x}}_i\in R\text{ のとき})\\ t{c}_i& ({\mathbf{x}}_i\notin R\text{ のとき})\end{array}$$

と定める。$t$ の定義より、すべての $i$ について $0\le a_i\le 1$ となる。
さらに $t>0,c_1=-1$ より $a_1=1-t<1$ である。
点 $\mathbf{a}=(a_1,\dots ,a_k)$ は単位超立方体 $[0,1{]}^k$ に属するため、その頂点の凸結合で表せる。
頂点は $S$ の部分集合 $Q$ の指示ベクトル ${\mathbf{e}}_Q$ と一対一対応するので、${\lambda }_Q\ge 0,\sum _{Q\subseteq S}{\lambda }_Q=1$ を用いて $\mathbf{a}=\sum _{Q\subseteq S}{\lambda }_Q{\mathbf{e}}_Q$ と表せる。
第 $i$ 成分は $a_i=\sum _{Q\ni {\mathbf{x}}_i}{\lambda }_Q$ であるから、

$$\sum _{i=1}^k{a}_i{\mathbf{x}}_i=\sum _{i=1}^k\left(\sum _{Q\ni {\mathbf{x}}_i}{\lambda }_Q\right){\mathbf{x}}_i=\sum _{Q\subseteq S}{\lambda }_Q\mathbf{V}(Q)$$

一方で、$a_i$ の定義より、

$$\begin{array}{rl}\sum _{i=1}^k{a}_i{\mathbf{x}}_i& =\sum _{{\mathbf{x}}_i\in R}(1+t{c}_i){\mathbf{x}}_i+\sum _{{\mathbf{x}}_i\notin R}t{c}_i{\mathbf{x}}_i\\ & =\sum _{{\mathbf{x}}_i\in R}{\mathbf{x}}_i+t\sum _{i=1}^k{c}_i{\mathbf{x}}_i\\ & =\mathbf{V}(R)+0=\mathbf{V}(R)\end{array}$$

よって $\mathbf{V}(R)=\sum _{Q\subseteq S}{\lambda }_Q\mathbf{V}(Q)$ である。
${\mathbf{x}}_1\in R$ かつ $a_1<1$ であるため、${\lambda }_R=1$ になることはない。すなわち $1-{\lambda }_R>0$ である。
したがって、両辺から ${\lambda }_R\mathbf{V}(R)$ を引き $1-{\lambda }_R$ で割ることで、

$$\mathbf{V}(R)=\sum _{Q\ne R}\frac{{\lambda }_Q}{1-{\lambda }_R}\mathbf{V}(Q)$$

となり、$\mathbf{V}(R)$ は $P(R)$ 中のベクトルの凸結合で表される。
(証明終)

---

这道题探讨了凸几何与线性代数中的一个经典对象，即由给定向量集合生成的多面体（Zonotope）。所有子集的向量和构成了这个多面体的投影顶点。第二问直观地反映了如果子集的向量和不是多面体的严格极点，它就可以被其他的子集和通过凸组合表示出来。第三问指出当向量组线性无关时，多面体实际上是一个高维的平行体，其所有子集和都会落在几何形体的最外层顶点上，因此无法相互用凸组合表示。第五问则是第三问的逆否延伸，通过构造超立方体上的内点并映射到多面体内部，巧妙地利用了线性相关性造成的降维挤压现象，证明了必然存在某些子集和被包络在内部或边界的平坦面上，从而能够被其余顶点凸表示。