[行列解析8.7.4]系：二重確率行列上の凸関数の最大値と凹関数の最小値

8.7.4　二重確率行列上の凸関数の最大値と凹関数の最小値
- 系 8.7.4.
- 証明
行列解析の総本山

8.7.4　二重確率行列上の凸関数の最大値と凹関数の最小値

系 8.7.4.

二重確率 \( n \times n \) 行列の集合上で定義された実数値関数 \( f \) が凸関数（または凹関数）であるとき、凸関数 \( f \) の最大値（または凹関数 \( f \) の最小値）は、置換行列において達成される。

証明

\( f \) を \( n \times n \) の二重確率行列上の凸な実数値関数とし、\( f \) がその最大値を達成する行列を \( A \) とする。Birkhoffの定理より、\( A \) は置換行列 \( P_1, \ldots, P_N \) と正のスカラー \( t_1, \ldots, t_N \) によって

A = t_1 P_1 + \cdots + t_N P_N, \quad t_1 + \cdots + t_N = 1

の形に表される。ここで、\( f(P_k) = \max\{ f(P_i) : i = 1, \ldots, N \} \) となる添字 \( k \) を選ぶ。このとき、凸性の定義から次の関係が成り立つ。

f(A) = f(t_1 P_1 + \cdots + t_N P_N) \le t_1 f(P_1) + \cdots + t_N f(P_N) \le t_1 f(P_k) + \cdots + t_N f(P_k) = (t_1 + \cdots + t_N) f(P_k) = f(P_k)

したがって、\( f \) が \( A \) で最大値をとることから \( f(A) = f(P_k) \) が得られる。すなわち、最大値は置換行列において達成される。凹関数についても同様の議論により最小値が置換行列で達成されることがわかる。

非負行列 \( A \in M_n \) が 二重劣確率（doubly substochastic） であるとは、\( A e \le e \) かつ \( e^T A \le e^T \) が成り立つ、すなわちすべての行および列の総和が高々1であることをいう。次の補題は、任意の二重劣確率行列が二重確率行列によって上から抑えられることを示す。