[線性代數] 構造 正定矩陣 其元素含有負值的例子

首先回憶 正定 (positive definite)矩陣 定義:

Definition: 令 $Q \in \mathbb{R}^{n\times n}$且 $Q^T=Q$。我們說 $Q$ 為 positive definite 若下列條件成立: 對任意 ${\bf x} \in \mathbb{R}^n$ 且 ${\bf x} \neq {\bf 0}$,
$$
{\bf x}^TQ{\bf x}>0
$$


我們想問是否有可能構造出一正定矩陣其部分元素取值為負。答案是肯定的。請看以下例子:

==============
Example: 
令 $Q = \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix}$。試証 $Q$ 為 positive definite。
================

Proof: 首先注意到 $Q^T=Q$ 為顯然。故我們僅需証明 對任意 ${\bf x} \neq 0$, ${\bf x}^TQ{\bf x}>0。$為此，取${\bf x}=[x_1\;\;x_2]^T$ 且 $x_1,x_2$不全為零， 觀察
$$
{\bf x}^TQ{\bf x} = [x_1 \;\; x_2]  \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix}x_1\\x_2 \end{bmatrix} = 2x_1^2+2x_2^2-2x_1x_2$$上述稱為 矩陣二次式(quadratic form)。

以下我們分幾個情況討論：

Case 1: 若 $x_2 \neq 0$ 且 $x_1 \neq 0$：
若 $x_1\geq x_2$ ，則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_2^2>0$
若 $x_2 \geq x_1$，則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_1^2>0$

Case 2: 若 $x_2 \neq 0$ 且 $x_1 = 0$：則我們有
$$
 2x_1^2+2x_2^2-2x_1x_2 = 2x_2^2 > 0
$$

Case 3: 若 $x_1 \neq 0$ 且 $x_2 = 0$：則我們有
$$
 2x_1^2+2x_2^2-2x_1x_2 = 2x_1^2 > 0
$$
綜合以上所述，$Q$ 為 positive definite。至此証明完畢。 $\square$


Comments:
1. 熟習 positive definiteness 性質的讀者可以知道有另一等價定義可以快速檢查 此性質：亦即若對稱矩陣 $Q$ 的 eigenvalue 為正數，則 $Q$ 為 positive definite。上述例子中，$Q$ 的 eigenvalues 不難計算可得 $1,3$ 故滿足此性質，$Q$ 為 positive definite。

2. 當然，positive definiteness 性質還有諸多其他常用的定義比如 leading principal 或者透過 pivots 在此我們不贅述。

[線性代數] 若 $A$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite

Definitions:
1. 我們說一個矩陣 $A$ 為 symmetric 若 $A^T=A$
2. 我們說一個矩陣 $A \in \mathbb{R}^{n \times n}$ 為 正定 (positive definite) 若 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言，
\[
{\bf x}^T A {\bf x} >0
\]
Comments:
上述positive definite 建構的 ${\bf x}^T A {\bf x} $ 稱作 矩陣的二次式。
判斷矩陣正定的方式有許多，上述只是其中一種，另外還有許多等價定義。下列敘述等價
1. 矩陣 $A$ 為 positive definite
2. 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言，${\bf x}^T A {\bf x} >0$
3. 矩陣 $A$ 有 正的 特徵值(eigenvalues)
4. 矩陣 $A$ 有 正的 leading principal minors
5. 矩陣 $A$ 有 正 的 pivots

接著我們給出當 $A$ 非方陣的時候，如何找出其對應的 正定矩陣。



==========
Theorem:
$A \in \mathbb{R}^{m\times n}$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite
==========
Proof:
首先證明 $A^TA$ 為 symmetric。觀察 $(A^TA)^T = A^TA$故得證。

接著證明 $A^TA$ 為 positive definite。令 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ ，觀察
\[
x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2
\]我們要證明 $\|Ax\|^2>0$，利用反證法：假設若不然，亦即 $\|Ax\|^2 =0$ ，由於因為 $A$ 有線性獨立(linear independent)的 column，記作 ${\bf a}_1,{\bf a}_2,...,{\bf a}_n$ 故由線性獨立的定義，
\[
A{\bf x} = x_1 {\bf a}_1 + x_2 {\bf a}_2 + \cdots x_n {\bf a}_n = {\bf 0}
\]若且唯若 $x_1= x_2 = ... x_n = 0$ 此與原本假設 ${\bf x} \neq 0$ 矛盾，故 $\|Ax\|^2>0$。$\square$


Theorem 2:
任意 positive definite matrix 為 invertible

Proof: 令 $A$ 為 positive definite matrix。利用反證法，假設 $A$ 的反矩陣不存在，此表示存在 ${\bf x} \neq {\bf 0}$ 使得 $A{\bf x} = {\bf 0}$。現在觀察
\[
{\bf x}^T A{\bf x} = \underbrace{{\bf x}^T {\bf 0}}_{={\bf 0}} \;\;\;\;\;(**)
\]但是由於 $A$為 positive definite，我們知道對任意非零向量 ${\bf x}$，${\bf x}^TA{\bf x} > 0$此與 式 $(**)$ 矛盾。故 $A$ 反矩陣存在，換言之$A$ 為 invertible。$\square$



Theorem 3:
若 $A^TA$ 為 invertible，則 $A$ 具有 線性獨立 columns。

Proof:
令 $A:=[{\bf a}_1 \;\; \cdots \;\; {\bf a}_n]$ 其中 ${\bf a}_i$ 為 $A$ 的 columns。我們要證明
$$
\sum_{i=1}^n x_i {\bf a}_i ={\bf 0} \Rightarrow x_i = 0,\;\; \forall i
$$ 注意到對任意 $x_i$，$\sum_{i=1}^n x_i {\bf a}_i ={\bf 0}$ 表示
\[
A{\bf x} = {\bf 0}
\]其中 ${\bf x}:=[x_1\;\;x_2\;\;\cdots x_n]^T$。故
\[
A^T A{\bf x} = A^T {\bf 0} = {\bf 0}
\]由於 $A^TA$ 為 invertible，故 ${\bf x}={\bf 0}$，亦即 $x_i = 0, \;\; \forall i$ 。至此證明完畢。$\square$



Comments:
相關文章參閱：[線性系統] 矩陣的二次式 與 正定矩陣

[凸分析] 常見的凸集性質(1) - 線性矩陣不等式之解 所成的集合 為 凸集

給定 $a \in \mathbb{R}^n$ ，我們定義 線性函數 $f : \mathbb{R}^n \to \mathbb{R}$ 滿足
\[
f(x) := a^T x = a_1 x_1 + ... + a_n x_n
\]
現在我們進一步推廣上述結果：亦即上述的向量 $a = (a_1,...,a_n)$ 可以用 對稱矩陣 $(A_1,...,A_n)$ 替換，且 $ A_i \in S^m$ 為 $\mathbb{R}^{m \times m}$ 對稱矩陣，現在我們模仿上述線性函數 $f$ 定義一個新的函數如下：定義  $F: \mathbb{R}^n \to S^m$ 滿足
\[
F(x) := x_1 A_1 + ... + x_n A_n
\]

Comments:
1. $ F(x) $ 仍為 $\mathbb{R}^{m \times m}$ 的對稱矩陣。
2. 上述提及的 線性函數 $f(x)$  (或者又說標準內積 或者 hyperplane) 可用以形成所謂 convex polyhedra 的集合，在此不贅述。


接著我們想問 對於上述 矩陣等式 $g(x)$ 而言，是否可以定義不等式？ 一般而言在線性代數中我們定義 $F(x) \succ 0$ 表示 $F(x)$ 為正定矩陣，亦即 對任意 $z \in \mathbb{R}^n$ 且 $z \neq 0$ 我們有
\[
z^T F(x) z > 0
\] 我們說 $F(x) \succeq 0$ 表示 $F(x)$ 為半正定矩陣，亦即 對任意 $z \in \mathbb{R}^n$
\[
z^T F(x) z \geq 0
\]

FACT:
令 $A,B$ 為 兩實係數 對稱矩陣，若 $A \succeq 0$ 且 $B \succeq 0$ 則
\[
A+B \succeq 0
\]
Proof: omitted (此證明相對容易，在此略過)

========================
Definition: Linear Matrix Inequality (LMI)
我們稱一不等式 為對 $x$ 而言的線性矩陣不等式 (Linear Matrix Inequality in $x$, LMI) 若 前述的矩陣 $F(x)$ 具有下列形式：
\[
F(x) := x_1 A_1 + ... + x_n A_n \preceq B
\] 其中 $x_i \in \mathbb{R}^1$ 且 $B, A_i $ 為 $m \times m$ 對稱矩陣，$i=1,2,...,n$。
========================

Comments:
1. 上述 LMI 要求 $F(x) \preceq B $ 亦即 $B - F(x) \succeq 0$ ，也就是說 $B - F(x) $ 為正定對稱矩陣，由前述定義可知我們要求：對任意 $z \in \mathbb{R}^n$，
\[
z^T (B-F(x))z \geq 0
\]
2. LMI 為 "線性" in $x$
3. LMI 在 強健控制理論中扮演重要的角色，在此不贅述。


以下我們給出主要結果：
========================
FACT:
上述 LMI 之解所成之集合 \[
L:=\{x \in \mathbb{R}^n : F(x) \preceq B\}
\]為凸集。
========================

Proof:
令 $x,y \in L$ 且 $\theta \in [0,1]$ 我們要證明 $ \theta x + (1-\theta)y \in L $ 此等價於證明
\[
F(\theta x + (1-\theta)y) \preceq B
\] 現在觀察
\begin{align*}
  F(\theta x + (1 - \theta )y) &= (\theta {x_1} + (1 - \theta ){y_1}){A_1} + ... + (\theta {x_n} + (1 - \theta ){y_n}){A_n} \hfill \\
   &= \sum\limits_{i = 1}^n {(\theta {x_i} + (1 - \theta ){y_i}){A_i}}  \hfill \\
   &= \theta \sum\limits_{i = 1}^n {{x_i}{A_i}}  + (1 - \theta )\sum\limits_{i = 1}^n {{y_i}{A_i}}  \;\;\;\;\; (*) \hfill \\
\end{align*}
由於  $x,y \in L$ ，故我們有
\begin{align*}
F(x) &:= \sum_{i=1}^n x_i A_i  \preceq B; \\
F(y) &:= \sum_{i=1}^n  y_i A_i \preceq B
\end{align*}故將上述結果帶入 $(*)$ ，由於 $\theta \in [0,1]$ 利用前述 FACT 可得
\[
F(\theta x + (1-\theta)y) \preceq B
\]至此得證。$\square$

[線性系統] 矩陣的二次式 與 正定矩陣

=======================
Definition: (Symmetric matrix)
一個 $n \times n$ 實數 矩陣 $M$ 稱為 對稱 (symmetric) 矩陣 若 $M^T = M$。

Definition: (Quadratic form of matrix)
令 $x \in \mathbb{R}^n$ 實數向量 與  $M$ 為 $n \times n$ 實數對稱矩陣 ( $M^T =M$)，則我們稱下列形式
\[
x^T M x
\]為一個 M矩陣的二次式 (quadratic form of matrix) 
=======================
Comment
1. 若 $x$ 為 complex vector，則 $M$ 的 二次式表示為 $x^* M x$。
2. 矩陣的二次式 $x^TMx$ 幫我們把 矩陣 轉成 純量。

上面矩陣二次式 與 對稱矩陣 實際上有甚麼用呢? 事實上 對稱矩陣 具有非常特殊的 eigenvalue 性質，也就是 eigenvalue 保證必定是 實數 (沒有 complex part) 。而在系統理論裡面我們又知道 eigenvalue 對系統穩定性與系統性能至關重要，故我們先看一個結果：

=====================
FACT: 對任意 實數對稱矩陣 $M$ 其 eigenvalue 必定為實數。
=====================
Proof:
由於實數矩陣可能具有 complex 的 eigenvalue 與 eigenvector，故我們必須考慮 eigenvalue 為複數的情況。現在令 $x$ 為 complex number 且我們透過 $M$ 的二次式 $x^* M x$ 來幫助我們
首先對 $M$ 的二次式再取一次 complex conjugate 可得
\[\begin{array}{l}
{\left( {{x^*}Mx} \right)^*} = {x^*}{M^*}x\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array}\mathop  = \limits^{M\begin{array}{*{20}{c}}
{}
\end{array}is\begin{array}{*{20}{c}}
{}
\end{array}real} {x^*}{M^T}x\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array}\mathop  = \limits^{M\begin{array}{*{20}{c}}
{}
\end{array}is\begin{array}{*{20}{c}}
{}
\end{array}symmetric} {x^*}Mx \ \ \ \ \ (*)
\end{array}\]由上式可知 對任意 complex vector $x$，$x^*Mx$ 皆為 實數。

現在我們令 $\lambda$ 為 $M$ 的 eigenvalue 且 $v$ 為對應 $\lambda$ 的 eigenvector，亦即此兩者必須滿足 eigenvalue-eigenvector 關係 $M v = \lambda v$，故我們可改寫 $(*)$ 如下：
\[{v^*}\underbrace {Mv}_{ = \lambda v} = {v^*}\lambda v = \lambda {v^*}v = \lambda {\left\| v \right\|^2}\]且由於 $v^*Mv$ 與 $v^*v$ 皆為 實數，故 $\lambda$ 必定為實數。$\square$


現在我們介紹矩陣的正定性質，一般而言我們對於數字純量可以很容易判斷正負，但是對於矩陣而言便有所困難；故此我們引入 "正定 (positive definiteness)" 的概念：

=================================
Definition: (Positive definiteness and positive semidefinite)
一個 對稱 矩陣 $M$ 稱為 正定 (positive definite) 記做 $M \succ 0$ 若下列條件成立：
對任意非零向量 $x$，其二次式 $x^T M x >0$。

一個對稱矩陣 $M$ 稱為 半正定 (positive semidefinite) 記做 $M \succeq 0$ 若下列條件成立：
對任意非零向量 $x$，其二次式 $x^T M x \ge 0$。

=================================

Comment:

若 $M \succ 0$ 且 $x^T Mx =0$ 若且為若 $x =0$。
若 $M  \succeq 0$ ( $x^TMx \ge 0\;\;\text{for} \; x \ne 0$) $\Rightarrow$ 存在一個 $x \ne 0$ 使得 $x^T M x =0$。

現在我們看看除了定義之外，還有甚麼方法判別矩陣是否為正定?

================================
Theorem: Criterion of positive definiteness
一個對稱的 $n \times n$ 矩陣 $M$ 為 positive definite 若且為若 下列任一條件成立：
1. 所有 $M$ 的 eigenvalue $\lambda$ 都為正  ($\lambda > 0$)。
2. 所有 $M$ 的 leading principal minors 皆為正。
3. 存在一個 $n \times n$ 的 nonsingular 矩陣 $N$ 使得 $M = N^TN$
================================
Proof: omitted.

這邊我們省略證明，有興趣得讀者可參閱任何一本 線性系統或者線性代數的教科書即可。我們這邊只關注第三點：
若 $M = N^TN$，則我們觀察其 二次式：對任意 $x$ 而言，我們有
\[{x^T}Mx = {x^T}{N^T}Nx = \left( {N{x^T}} \right)Nx = \left\| {Nx} \right\|_2^2 \ge 0
\]現在若 $N$ 為 nonsingular 則我們知道 對任意 $x$，$N x \ne 0$，故只有當 $x =0$ 時候才會使 $Nx =0$。故可推知 $M \succ 0$

================================

Theorem: Criterion of positive semidefiniteness
一個對稱的 $n \times n$ 矩陣 $M$ 為 positive definite 若且為若 下列任一條件成立：
1. 所有 $M$ 的 eigenvalue $\lambda$ 都為 非負 ($\lambda \ge 0$)。
2. 所有 $M$ 的 leading principal minors 皆為非負。
3. 存在一個 $n \times n$ 的 singular 矩陣 $N$ 或者 $m \times n$ (n > m) 的矩陣 $N$使得 $M = N^TN$

================================

Proof: omitted.