Let A∈Rn×nA \in \mathbb{ R } ^{n \times n} be positive semi-definite matrix. Then f(x)≐xTAx:Rn×n→Rf (x) \doteq \sqrt {x^T A x}: \mathbb{ R } ^{n \times n} \rightarrow \mathbb{ R } is a norm.

Proof. We only check that it satisfies triangle inequality, i.e., ∀x,y∈Rn\forall x, y \in \mathbb{R}^n

f(x+y)≤f(x)+f(y)⟷(x+y)TA(x+y)T≤xTAx+yTAy⟷yTAx≤xTAxyTAy \begin{aligned} f(x + y) &\le f(x) + f(y) \\ &\longleftrightarrow \\ \sqrt{ (x + y)^T A (x + y)^T } &\le \sqrt{ x^T A x} + \sqrt{y^T A y} \\ &\longleftrightarrow \\ y^T A x &\le \sqrt{ x^T A x} \sqrt{y^T A y} \end{aligned}

Since AA is PSD, then ∃B∈Rn×n\exists B \in \mathbb{ R } ^{n \times n}, s.t., A=BTBA = B^T B. Define yˉ=By\bar y = B y and xˉ=Bx\bar x = B x, we need to prove

yˉTxˉ≤∥xˉ∥⋅∥yˉ∥ \bar y^T \bar x \le \| \bar x\| \cdot \| \bar y \|

But this is just Cauchy-Schwarz inequality.

□\square