[行列解析8.7.P15]

8.7.問題15

(8.7.2) における上界 \( n^2 - n + 1 \) を、\( (n^2 - n + 1) - (n - 1) = n^2 - 2n + 2 \) に改良できることを示せ。詳細を以下の手順で説明せよ：

(a) 任意の \( n \times n \) 二重確率行列 \( S = [s_{ij}] \) は、次の \( 2n - 1 \) 個の線形方程式を満たす：

\sum_{k=1}^n s_{ik} = 1, \quad i = 1, \dots, n, \\ \sum_{k=1}^n s_{ki} = 1, \quad i = 1, \dots, n-1

(b) これらの方程式を \( A \, \mathrm{vec}(S) = e \in \mathbb{R}^{2n-1} \) の形に書き直せ（式 (0.7.7) を参照）。

(d) \( \mathrm{nullspace}(A) \) の次元は \( n^2 - 2n + 1 \) である。

(e) 二重確率行列の集合は、\( \mathbb{R}^{n^2 - 2n + 1} \) における凸多面体とみなせる。

(f) 式 (8.7.3) および Carathéodory の定理（付録B参照）より、任意の二重確率 \( n \times n \) 行列は、高々 \( n^2 - 2n + 2 \) 個の置換行列の凸結合として表せる。