知恵袋で見かけた問題について

Yahoo知恵袋で見かけた記事（現在消去済み）についてのメモ. 問は「$x_1, x_2, \cdots , x_{1001}$ を実数とし, 各 $1 \leqq i \leqq 1001$ について, 残りの元 $x_1, \cdots, x_{i-1}, x_{i+1}, \cdots, x_{1001}$ を500個ずつの総和の等しいグループに分ける方法が存在する時, $x_1 = x_2 = \cdots = x_{1001}$ であることを示せ.」というもの.

【補題】

$n$ 次正方行列 $A=(a_{ij}) \in M_n(\mathbb{Z})$ は対角成分が全て奇数であり, それ以外の成分は全て偶数とする. このとき $A$ は $M_n(\mathbb R)$ の元として正則である（ユニモジュラーとは限らない. 逆行列の成分は整数でない可能性もある）.

（証明）

行列式が0でないことを示せばいい. $\mathfrak S_n$ を $n$ 次の置換全体の集合とする. 行列式の定義は$ \displaystyle \det(A)=\sum_{ σ \in \mathfrak S_n} \mathrm{sgn}(σ) \prod_{i=1}^n a_{i σ(i)}$であった. 恒等置換でない $σ$ について考えると, ある $i$ について $a_{i σ(i)}$ は対角成分ではなくなる. すなわち偶数になる. したがって $\displaystyle \prod$ の部分が偶数になる. 一方 $σ$ が恒等置換の場合, それは対角成分を順に掛けていくことになり, 対角成分は全て奇数であったから, それらを全て掛けたものも奇数になる. したがって $\displaystyle \sum_{σ \in \mathfrak S_n}$ で足される数たちは奇数を1つだけ含み, それ以外は全て偶数であるから, その総和である $\det(A)$ は奇数になる. すなわち0になりえないから $A$ は正則であることが示された（証明終）.

この補題を踏まえた上で冒頭の問を証明する.

まず, 実数の組 $x_1, x_2, \cdots , x_{1001}$ が問の条件を満たす（resp. 満たさない）とすると, 任意の定数 $C$ について $x_1+C, x_2+C, \cdots , x_{1001}+C$ も条件を満たす（resp. 満たさない）ことが分かる. つまり定数だけの差は無視してよいことになる. そこで上の式で $C=-(x_1+x_2+ \cdots +x_{1001}) \div 1001$ とおくことにより, 初めから $x_1+x_2+\cdots +x_{1001}=0$ と仮定しても一般性を失わない.

仮定より各 $x_i$ について, それ以外の1000個の数を500個ずつの総和の等しいグループに分けられる. 言い換えれば, うまく500個を選べばその和を

$\displaystyle \{(x_1+\cdots +x_{1001})-x_i\} \div 2 = -\frac{x_i}{2}$

にできるということである. これをベクトルを用いて表現する.

ベクトル $v = (x_1, x_2, \cdots, x_{1001})^T$ とする. すなわち1001個の成分をもつ列ベクトルである. $x_i$ についての上の記述は「成分として1を500個, 0を501個含み, 第 $i$ 成分は0であるような1001次元の行ベクトル $b_i$ があって, $\displaystyle b_i v=-\frac{x_i}{2}$ となる」と表現できる. そこで行列 $B$ を

$\displaystyle B= \left( \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_{1001} \end{array} \right) $

と定めることにすればこれは1001次の正方行列になり, またその対角成分は全て0である. そして行列の積の等式として,

$\displaystyle Bv=-\frac{1}{2}v$

が得られることになる. 整理すれば $(I+2B)v=0$ である. ここで $I$ は1001次の単位行列.

行列 $B$ の成分は作り方から分かるように1と0のみである. よって $2B$ の成分はすべて偶数である. したがって $I+2B$ は対角成分は全て奇数で, それ以外の成分は全て偶数であるような行列になる. よって補題よりこれは正則である. $(I+2B)v=0$ の両辺に左から $(I+2B)^{-1}$ を掛ければ $v=0$ が得られ, これは $x_1=x_2= \cdots = x_{1001}=0$ を示している. よって示された.

※$x_i$ たちは実数とのことであったが, 多分アーベル群の元としても同じことが成り立つはず.

アティマク演習解答メモ1-1

1章

1.

この解答はiso.2022.jpというサイトのPDFとほぼ同じであるが, 一部新たに注意を加えたものである. 先のPDFの繰り返しになってしまう部分もあるが証明全体を書くこととする.

$x$ はnilpotentなので $\exists N>0$ について $x^N=0$ である. 一般の $y$ と $n>0$ について $1-y^n=(1-y)(1+y+\cdots+y^{n-1})$ である. この式に $y=-x$ と $n=N$ を代入すると,

（左辺）$=1-(-x)^N=1-(-1)^N x^N = 1-0 = 1$

（右辺）$=(1+x)(1+(-x)+\cdots+(-x)^{n-1})$

ゆえに $1+x$ はunitになることが示された.

注意：いま, 所与の環 $A$ は可換環であることが仮定されているが, この証明は乗法についての可換性が無くても成り立つ. 実際 $y$ は $y$ それ自身と可換なので

$1-y^n=(1-y)(1+y+\cdots+y^{n-1})=(1+y+\cdots+y^{n-1})(1-y)$

という等式は可換環でなくても成り立つ. よって $1+x$ は乗法についての左逆元かつ右逆元（すなわち普通の意味での逆元）を持つのでunitになる. また $(-x)^N=(-1)^Nx^N$ の箇所で $-1$ と $x$ の可換性を使っているが, これは $1x=x1=x$ より導かれる事実なのでやはり可換性は必要ない.

意見：抽象的議論によってunitであることを示すこともできるが, 具体的に逆元の形を示している点でこの証明は有用である.

後半部分を示す. $u$ をunit, $x$ を上と同様にnilpotentとする. $u+x$ がunitになることを示す.

$u+x=u(1+u^{-1}x)$

なので $1+u^{-1}x$ がunitであることを示せばよく, そのためには前半の証明より $u^{-1}x$ がnilpotentであることを示せばいい. ”乗法の可換性から”

$(u^{-1}x)^N=u^{-N}x^N=0$なので, $u^{-1}x$ はnilpotentであり, よって命題が示された.

注意：後半の証明には可換性が不可欠である. 実際, 可換性がない場合には反例が存在する. 考えるのは行列の成す環である.

$\displaystyle u^{-1} = \left( \begin{array}{cc} 1 & 0 \\ 1 & 1 \end{array} \right) , x = \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right)$

とする（省スペースのため直接 $u^{-1}$ を書いてしまっているが, これは正則な行列なので $u$ の存在は問題ない）. $x^2=0$ なのでnilpotentである. 一方で

$\displaystyle u^{-1}x = \left( \begin{array}{cc} 0 & 1 \\ 0 & 1 \end{array} \right)$であり, 計算してみると分かるがこの行列はべき等である（つまり何乗しても元のまま）. よって $x$ はnilpotentだが $u^{-1}x$ はnilpotentでない例となっている. このとき$\displaystyle u+x = \left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right)$

なので, unitにはなっていない.

問の主張に「$x$ と可換なunit $u$ について」という条件を加えれば可換環でない一般の環でも成り立つ. ただ可換代数の本なのであまり非可換性とかは気にしなくてもいいかもしれない.

平方数が偶数ならば元の数も偶数であることについて

$n$ が整数のとき, $n^2$ が偶数なら $n$ も偶数という命題は, 対偶を用いて証明する例としてよく使われる. しかし対偶を使わないで証明できないか？という意見を見たのでやってみる. ただ, あくまで示したい命題の対偶は使わないだけであって, 証明の中には二重否定則を暗黙的に使用している箇所もあり得る.

整数の部分集合 $A$ を, $A=\{n \in \mathbb{Z} ~|~ n^2は偶数 \}$ として定める. $A$ が加法に関して $\mathbb{Z}$ の部分群になっていることを示す.

• $0^2=0$ なので $0 \in A$. つまり $A$ は加法についての単位元をもつ.
• $n, m \in A$ とする. $(n+m)^2=n^2+2mn+m^2$ は明らかに偶数になっているので $n+m \in A$. つまり $A$ は加法について閉じている.
• $n \in A$ とする. $(-n)^2=n^2$ よりこれは偶数なので $-n \in A$. つまり $A$ は逆元について閉じている.

以上より $A$ は群になることが示された.

一般に $\mathbb{Z}$ の部分群は, ある整数 $k>0$ によって $k\mathbb{Z}$ と表される. $A=k\mathbb{Z}$ とおいて $k$ を求める.

しかしこれは容易で, $0, 2 \in A$ かつ $1 \notin A$ なので $k=2$ しかありえない. したがって $A$ は偶数全体の集合と一致していることがわかった. そもそも２乗したら偶数になるような整数をすべて集めた集合が $A$ だったのだから, 命題が示されたことになる.