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

[泛函分析] 幾何平均與算術平均不等式的一類推廣

回憶中學時期學過的 幾何平均與算術平均關係：令 $a,b \in \mathbb{R}$則 幾何平均 有 算術平均作為上界
\[
\sqrt{ab} \leq \frac{a+b}{2}
\]現在我們將上述結果做一類推廣

Claim: 令 $\theta \in (0,1)$ 且 $a, b \geq 0$則
\[
a^{1-\theta}b^{\theta} \leq (1-\theta)a + \theta b
\]
在給出證明之前我們先做出一些說明

Remarks:
1. 上述 claim 不等式左方：$a^{1-\theta}b^{\theta}$ 一般稱作廣義幾何平均 (Generalized Geometric Mean)。
2. 上述 claim 不等式右方：$(1-\theta)a + \theta b$ 有些學者將其稱作廣義算術平均 (Generalized Arthmic Mean)。但若有涉獵凸分析或者凸最優問題的讀者大概不難看出 此式具備 convex combinaiton 的形式。事實上此不等式在 與凸分析中的 log-convexity 有相關，讀者可自行查閱相關文獻。
3. 上述 Claim 一般又稱作 Auxiliary  Holder inequality.

以下我們給出 Claim 的證明。

Proof of the Claim: 首先做以下觀察：若 $a,b = 0$ 或任一為 $0$ 則不等式自動成立。故在不失一般性的情況下 我們設 $a \geq b >0$ 並且注意到 $a^{1-\theta} = a a^{-\theta}$ 故我們可改寫要證明的不等式如下
\begin{align*}
\left(\frac{b}{a}\right)^\theta \leq (1-\theta) + \theta \frac{b}{a}
\end{align*}
令 $x:=b/a$ 則 $x \in (0,1)$ 且我們僅需證明
\[
x^\theta \leq (1-\theta) +\theta x
\]令 $g(x):=  1-\theta +\theta x - x^\theta $，注意到 $g(1) = 0$ 且 $g(0) = 1-\theta>0$
\[
g'(x) = \theta -\theta x^{\theta-1} < \theta -\theta = 0
\]亦即 $g'(x) <0$ 表示 $g$ 為在 $x \in (0,1)$ 處為遞減函數。故由 $g$ 的連續性，對 $x \in [0,1]$ 我們有
\[
g(x) \geq 0
\]此等價為
\[
1-\theta +\theta x - x^\theta \geq 0
\]同理
\[
x^\theta \leq (1-\theta) +\theta x
\]上述即為我們待證的不等式，至此證明完畢。$\square$