二次型与(半)正负定性¶

1 标量函数的正(负)定性¶

对于一个 n 维空间，可以在上定义一个标量函数 \(V(x)\)，我们接下来讨论这个 \(V(x)\) 的性质。

正定性： \(V(0) = 0, \forall x \neq 0, V(x) > 0\)
半正定性：\(V(0) = 0, \forall x \neq 0, V(x) \ge 0\)
负定性：\(V(0) = 0, \forall x \neq 0, V(x) < 0\)
半负定性：\(V(0) = 0, \forall x \neq 0, V(x) \le 0\)
不定性：\(\exists x_1,x_2 \in \mathbb{R}^n, V(x_1) > 0, V(x_2) < 0\)

2 二次型的正(负)定性¶

当标量函数 \(V(x)\) 是二次型形式，也就是说，\(V(x) = x^{\top}Ax\)，其中\(A\)是一个线性定常矩阵时，我们也会说，\(A\) 具有与 \(V(x)\) 一致的 (半)正/负定性。

2.1 二次型为什么要求矩阵对称？¶

Note

这里有数学上的一个Trick。去看各种参考书中关于“二次型”的定义，它们会告诉你，二次型长这个样子

\[x^{\top}Ax = \sum\limits_{i}\sum\limits_{j}a_{i,j}x_ix_j\]

但它们同时也会要求 \(A\) 是一个对称矩阵，这是为什么呢？

我们从字面意义上思考“二次型”这个概念，很自然会觉得，如果标量函数可以完全表示成完全平方形式的线性组合，那么它就是一个二次型。

注意到，对于任意矩阵 \(A\) ，\(x^{\top}Ax\) 都是符合我们直觉的一个二次型。

举个例子，\(2x_1^2+2x_1x_2+2x_2^2 = x_1^2+(x_1+x_2)^2+x_2^2\)，只要根据耦合项 \(2x_1x_2\) 配系数，再留出单独的平方项 \(x_1^2+x_2^2\)，就能把任意一个二次型转化为完全平方的形式。

那么可以合理怀疑，对任意矩阵 \(A\) ，我们都可以把 \(x^{\top}Ax\) 改写成矩阵为对称矩阵的 \(x^{\top}Bx\) 形式，即 \(\forall A, \exists B, B = B^{\top}, x^{\top}Ax = x^{\top}Bx\).

事实上，我们也确实可以找到这样的一个\(B\)，\(B = (A^{\top} + A)/2\).

具体推导过程如下所示

\[\begin{aligned}x^{\top}\left(\frac{A^{\top}+A}{2}\right)x &= \frac{1}{2}\left(x^{\top}A^{\top}x + x^{\top}Ax\right)\\ &= \frac{1}{2}\left[(x^{\top}Ax)^{\top}+x^{\top}Ax\right]\\ &= \frac{1}{2}\left(x^{\top}Ax+x^{\top}Ax\right)\\ &=x^{\top}Ax.\end{aligned}\]

其中，第二行到第三行是因为 \(x^{\top}Ax\) 是一个标量。

2.2 二次型正定的充要条件：方阵的顺序主子式都大于零¶

塞尔维斯特准则：二次型正定的充要条件是方阵的顺序主子式都大于零。¶

顺序主子式：对于给定的 \(n\) 阶方阵 \(A_n\)，其前 \(k\) 行 \(k\) 列组成的方阵 \(A_{(k)}\) 的行列式 \(\Delta_k\) 为 \(A_n\) 的 \(k\) 阶顺序主子式。

Sylvester Criterion： \(A_n \in \mathbb{R}^{n\times n}, A_n \text{是正定的, iff,} \Delta_1 > 0, \Delta_2 > 0, ..., \Delta_n > 0\).

Proof¶

【引理1】：正定矩阵的特征值大于 0。¶

\(\forall x \neq 0, x^TAx = x^T\lambda_i x > 0\)，其中 \(\lambda_i\) 是 A 的第 i 个特征值，所以有 \(\lambda_i > 0\) .

【引理2】：方阵的行列式等于特征值的积。¶

方阵的特征多项式 \(|A-\lambda E| = (\lambda_1-\lambda)(\lambda_2 - \lambda)...(\lambda_n -\lambda)\) 。

（注意：不是 \((\lambda-\lambda_1)(\lambda-\lambda_2)...(\lambda-\lambda_n)\)，因为左式的负号在 \(\lambda\) 上）

取 \(\lambda = 0\)，就得到了 \(|A| = \prod_{i=1}^{n}\lambda_i\).

【引理3】：正定矩阵的行列式大于 0 。¶

由【引理1】【引理2】即得。

【引理4】：实对称矩阵的不同特征值对应的特征向量相互正交。¶

对于一个实对称矩阵 \(A_n\)，设它的两个不相等的特征值为 \(\lambda_1,\lambda_2\)，分别对应特征向量 \(x_1, x_2\).

有 \(A_nx_1 = \lambda_1x_1\)，将等式两边都取转置，得 \(x_1^TA_n^T = \lambda_1x_1^T\)，再右乘 \(x_2\)，有

\[x_1^TA_n^Tx_2 = \lambda_1x_1^Tx_2.\]

同理，有 \(A_nx_2 = \lambda_2x_2\)，左乘 \(x_1^T\)，有

\[x_1^TA_nx_2 = \lambda_2x_1^Tx_2.\]

因为 \(A_n^T=A_n\)，我们可以得到 \((\lambda_1-\lambda_2)x_1^Tx_2 = 0\)，因为 \(\lambda_1 \neq \lambda_2\)，所以 \(x_1^Tx_2 = 0\)，证毕.

【充分性】：\(A_n \text{正定} \Rightarrow \Delta_k>0, 0<k\le n\) .¶

对于任意一个 \(k\) 维向量 \(z_k = \{z_1,z_2,...,z_k\}^T\)，

我们都可以构造一个 \(n\) 维向量 \(\mathbf{x}_{(k)} = \{x_1, x_2,...,x_k,0,0,...,0\}^T\).

因为 \(\mathbf{x_{(k)}}^TA\mathbf{x_{(k)}}>0\)，所以 \(z_k^TA_{(k)}z_k>0\) 恒成立。

所以 \(A_{(k)}\) 也是正定的，根据【引理3】，\(\Delta_k>0\).

【必要性】：\(\Delta_k>0, 0<k\le n \Rightarrow A_n \text{正定}\)。¶

用数学归纳法证明。

当 n=1 时，\(\Delta_1 = a_1 > 0\)，有 \(x^TA_{(1)}x = a_1x^Tx = a_1x^2 > 0, x \neq 0\)，所以 \(A_{(1)}\) 是正定的；
当 n=2 时，\(\Delta_1 = a_{11}>0, \Delta_2 = a_{11}a_{22}-a_{12}^2>0\)，有

\[x^TA_{(2)}x = a_{11}x_1^2+2a_{12}x_1x_2+a_{22}x_2^2 = a_{11}(x_1+\frac{a_{12}}{a_{11}}x_2)^2+\frac{a_{11}a_{22}-a_{12}^2}{a_{11}}x_2^2,\]

当 \(x_1,x_2\neq 0\) 时，\(x^TA_{(2)}x\) 恒成立，所以 \(A_{(2)}\) 是正定的。

接下来需要证明，若 \(A_{(j)}\) 正定且 \(\Delta_{j+1}>0\)，则 \(A_{(j+1)}\) 也正定。其中 \(1\le j \le n-1\).

我们使用反证法。假设 \(A_{(j+1)}\) 非正定，利用 \(\Delta_{j+1}>0\) 导出 \(A_{(j)}\) 非正定。

根据【引理1】，\(A_{(j+1)}\) 非正定，则有一个小于等于 0 的特征值。

因为 \(\Delta_{j+1}>0\)，根据【引理2】，这个特征值必须小于 0 ，并且同时存在偶数个负特征值。

我们挑取其中 2 个负特征值 \(\lambda_a, \lambda_b\)，其对应的 j+1 维特征向量分别为 \(x_a,x_b\)。

选择 \(\alpha,\beta\)，我们可以得到一个新的 j+1 维向量 \(u = \alpha x_a + \beta x_b \neq 0\)，其第 j+1 维值为 0 .

考虑二次型

\[\begin{aligned} u^TA_{(j+1)}u &= (\alpha x_a+\beta x_b)^TA_{(j+1)}(\alpha x_a+\beta x_b)\\ &= (\alpha x_a^T + \beta x_b^T)(\alpha A_{(j+1)}x_a + \beta A_{(j+1)}x_b)\\ &= (\alpha x_a^T + \beta x_b^T)(\alpha\lambda_ax_a+\beta\lambda_bx_b)\\ &= (\alpha^2\lambda_ax_a^Tx_a + \alpha\beta\lambda_bx_a^Tx_b + \beta\alpha\lambda_ax_b^Tx_a+\beta^2\lambda_bx_b^Tx_b)\\ &= (\alpha^2\lambda_ax_a^Tx_a + \beta^2\lambda_bx_b^Tx_b)\\ &= \alpha^2x_a^TA_{(j+1)}x_a + \beta^2x_b^TA_{j+1}x_b\\ & < 0\end{aligned}\]

其中的化简过程利用了【引理四】。

因为 u 的第 j+1 维值为0，所以利用分块矩阵的计算可知 \(u^TA_{(j+1)}u = u_{(j)}^TA_{(j)}u_{(j)} < 0\)，这与 \(A_{(j)}\) 正定相互矛盾，因此我们的假设错误，\(A_{(j+1)}\) 是正定的。

综上所述，我们完成了 Sylvester Criterion 的证明。