[線性代數] 若 $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:
相關文章參閱：[線性系統] 矩陣的二次式 與 正定矩陣