東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問A

标签：

• TITech
• Positive-Semidefinite-Matrix
• Matrix-Rank

Author

GPT-5

Description

Let $A\in\mathbb{R}^{n\times n}$ be a real symmetric matrix of order $n$, $b\in\mathbb{R}^n$, and define

$$f(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x.$$

(1) Assume that $A$ is positive definite. Show that $f$ attains its minimum at a unique point.

(2) Assume that $A$ is positive semidefinite and $\operatorname{rank}A=k$ $(1\leq k<n)$. Let $S$ be the set of all minimum points of $f$, take any $x^*\in S$, and define $S_{x^*}=\{s-x^*\mid s\in S\}$. Show that $S_{x^*}$ is a linear subspace of $\mathbb{R}^n$.

(3) Determine $\dim S_{x^*}$ in terms of $n$ and $k$.

题目描述

设 $A\in\mathbb R^{n\times n}$ 为 $n$ 阶实对称矩阵，$b\in\mathbb R^n$，并定义

$$f(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x.$$

1. 假设 $A$ 正定，证明 $f$ 在唯一一点取得最小值。

2. 假设 $A$ 半正定且 $\operatorname{rank}A=k$，其中 $1\leq k<n$。令 $S$ 为 $f$ 的全部最小点组成的集合，任取 $x^*\in S$，并定义

   $$S_{x^*}=\{s-x^*\mid s\in S\}.$$

   证明 $S_{x^*}$ 是 $\mathbb R^n$ 的线性子空间。

3. 用 $n$ 和 $k$ 表示 $\dim S_{x^*}$。

考点

• 正定二次型的极小化：由实对称正定矩阵的可逆性或配方法证明二次函数存在唯一极小点。
• 半正定矩阵的零空间与秩：刻画全部极小点之间的差属于 $\ker A$，据此证明平移后的集合为子空间并用秩－零化度定理求其维数。

Kai

(1)

正定値性から $A$ は可逆である。$x^*=A^{-1}b$ とおき、$y=x-x^*$ とすると、$Ax^*=b$ と $A^{\mathsf T}=A$ より

$$\begin{aligned} f(x) &=\frac12(y+x^*)^{\mathsf T}A(y+x^*)-b^{\mathsf T}(y+x^*)\\ &=\frac12y^{\mathsf T}Ay-\frac12b^{\mathsf T}A^{-1}b. \end{aligned}$$

$A$ は正定値なので $y\neq0$ なら $y^{\mathsf T}Ay>0$ である。したがって $f$ は

$$\boxed{x^*=A^{-1}b}$$

でのみ最小値 $-\frac12b^{\mathsf T}A^{-1}b$ をとる。

(2)

$f$ は微分可能であり、最小点 $x^*$ では

$$\nabla f(x^*)=Ax^*-b=0$$

である。任意の $x$ に対して $d=x-x^*$ とおけば

$$f(x)-f(x^*)=\frac12d^{\mathsf T}Ad.$$

$A$ は半正定値なので、右辺が 0 になることと $Ad=0$ は同値である。実際、直交行列による対角化 $A=Q\Lambda Q^{\mathsf T}$ を用いれば、$d^{\mathsf T}Ad=\sum_i\lambda_i(Q^{\mathsf T}d)_i^2$ であり、正の固有値に対応する成分がすべて 0 になる。

よって

$$S=x^*+\ker A, \qquad S_{x^*}=\ker A.$$

核 $\ker A$ は線形部分空間であるから、$S_{x^*}$ も線形部分空間である。

(3)

階数・退化次数定理より

$$\boxed{\dim S_{x^*}=\dim\ker A=n-\operatorname{rank}A=n-k}.$$