東京大学 数理科学研究科 数理科学専攻 2023年8月実施 専門科目A 第3問

标签：

• Tokyo-University
• Maximum-Size-of-Pairwise-Obtuse-Vector-Set

Author

藍色日和

Description

標準的な内積の入った線型空間 $\mathbb{R}^n$ を考える。以下の条件を満たす自然数 $m$ として最大のものを求めなさい。

• 任意の相異なる $i,j$ に対して $v_i・v_j < 0$ であるような $v_1,\cdots,v_m\in\mathbb{R}^n$ が存在する。

题目描述

考虑带有标准内积的线性空间 $\mathbb{R}^n$。求满足下述条件的自然数 $m$ 的最大值：

• 存在向量 $v_1,\ldots,v_m\in\mathbb{R}^n$，使得对任意互不相同的 $i,j$，都有 $v_i\cdot v_j<0$。

考点

• 两两成钝角的向量集的最大规模：需要利用内积严格为负的条件与 $\mathbb{R}^n$ 的维数限制证明规模上界，并构造达到该上界的向量组。

Kai

このような自然数を $N(n)$ とする。まず $N(n)\leq n+1$ であることを背理法で示す。条件を満たすような $v_1,\cdots,v_{n+2}$ が存在したとする。このとき

$$\sum_{i=1}^{n+2}a_iv_i=0$$

を満たすような $(a_1,\cdots,a_{n+2})$ 全体の集合 $W$ を考える。この集合は次元 $\geq2$ の線型空間であるから、$W$ の元 $a=(a_1,\cdots,a_{n+2})$ で、$a_i>0$ を満たすような $i$ と $a_j<0$ を満たすような $j$ が一つ以上存在するようなものを取ることができ、これを一つ固定する。いま

$$I=\{i|a_i>0\}$$

$$J=\{j|a_j<0\}$$

と置いたとき等式

$$\sum_{i\in I}a_iv_i=\sum_{j\in J}(-a_j)v_j$$

が成り立つ。この元を $v$ と置いたとき

$$\begin{aligned} v・v&=\left(\sum_{i\in I}a_iv_i\right)・\left(\sum_{j\in J}(-a_j)v_j\right)\\ &=\sum_{(i,j)\in I\times J}(-a_ia_j)v_i・v_j<0 \end{aligned}$$

となり、内積の正定値性に矛盾する。以上から $N(n)\leq n+1$ である。

次に $N(n)\geq n+1$ であることを帰納法によって示す。$n=1$ のときは $v_1=1,v_2=-1$ とすればよい。次に $\mathbb{R}^n$ に於いて条件を満たす $v_1,\cdots,v_{n+1}$ が取れたとする。このとき正の実数 $\varepsilon$ を

$$\epsilon<\sqrt{\min_{i,j}\left\{|v_iv_j|\middle|i\neq j\right\}}$$

を満たすようにとり、$\mathbb{R}^{n+1}$ の元 $w_i$ を $i=1,\cdots,n+1$ に対しては

$$w_i:=(v_i,\varepsilon)$$

と定義し、そして

$$w_{n+2}:=(0,\cdots,0,-\varepsilon)$$

と定義する。このとき $w_1,\cdots,w_{n+2}$ は所望の条件を満たしている。

以上から $N(n)=n+1$ である。