• positive definite matrices
• computation and definition
• connection to Newton Method
• connection to Least-Squares

Positive Definite Matrices

An $n\times n$ matrix $A$ (assume symmetric) is positive definite if (SPD)

$x^TAx \gt 0$, $\forall x\in \mathbb{R}^n \ne 0$

positive semi definite if (PSD)

$x^TAx \ge 0$, $\forall x\in \mathbb{R}^n$

negative definite matrix

$x^TAx \lt 0$, $\forall x \ne 0$

Properties

1. for any full rank $n\times k$ matrix $X$, $X^TAX\gt 0$ if $A \gt 0$ ①

   for all $y\in \mathbb{R}^k$ nonzero, $0 \ne Xy$ ⇒ $y^T(X^TAX)y=\underbrace{(Xy)^T}{\equiv Z^T}A(\underbrace{Xy}{\equiv Z \ne 0})\gt 0$

① ⇒ every principle sub-matrix of $A$ is also positive definite

$X^T_1AX_1=\begin{matrix}& P_1 & P_2 & P_3& \\ [& I & 0& 0&]\end{matrix}\begin{bmatrix}A_1 &&\\&A_2&\\&&A_3\end{bmatrix}\begin{bmatrix}I\\0\\0\end{bmatrix}=A_1$

$X_2^TAX_2=\begin{bmatrix}1 & 0 & \ldots &0 \end{bmatrix}A\begin{bmatrix}1\\0\\ \vdots \\0\end{bmatrix}=a_{11}$

⇒ every diagonal element $a_{ii} \gt 0$

1. A is positive definite ↔ eigenvalues are positive

   $(x,\lambda)\in \mathbb{R}^n\times \mathbb{R}$ is an eigen-pair of the matrix $A$ if

   $Ax=\lambda x$

   without loss of generality, $\lVert x\rVert =1$

   ⇒ $0 \le x^TAx=x^T(\lambda x)=\lambda x^Tx=\lambda \lVert x\rVert^2=\lambda$

<aside> ➡️ If $X\in \mathbb{C}^{n \times k}$ (conjugate transpose) If $A$ non symmetric: $\frac{1}{2}(A+A^T)$ is “symmetric part” of A

</aside>

1. A is positive definite ↔ A has a Cholesky Decomposition

   Make simplifying assumption that

   

   “Block” Gaussian Elimination:

   $A=\begin{bmatrix}1&w^T\\w&K\end{bmatrix}=\underbrace{\begin{bmatrix}1&0\\w&I\end{bmatrix}}_{\equiv L}\begin{bmatrix}1&w^T\\0&K-w^T\end{bmatrix}$

   $\begin{bmatrix}1&w^T\\0&K-ww^T\end{bmatrix}=\begin{bmatrix}1&0\\0&K-ww^T\end{bmatrix}\begin{bmatrix}1&w^T\\0&I\end{bmatrix}$

   $\begin{aligned}A & = \begin{bmatrix}1&0\\w&I\end{bmatrix}\begin{bmatrix}1&\\&K-ww^T\end{bmatrix} \begin{bmatrix}1&w^T\\0&I\end{bmatrix} \\ &= L D L^T\end{aligned}$

   ($L^{-1}AL^{-T}=D$) $\overset{\text{By Property ①}}{⇒} K-ww^T \gt 0$

   Now, allow $a_{11}$ arbitrary (positive) $\alpha := \sqrt{a_{11}}$

   $A=\underbrace{\begin{bmatrix}\alpha&0\\ \frac{w}{\alpha}&I\end{bmatrix}}{R_1^T}\underbrace{\begin{bmatrix}1&0\\0&K-\frac{ww^T}{\alpha}\end{bmatrix}}{A_1}\underbrace{\begin{bmatrix}\alpha&\frac{w^T}{\alpha}\\ 0&I\end{bmatrix}}_{R_1}$,

   where

   

   Because $K-ww^T/\alpha^2$ is positive definite, it also has the factorization

   $\underbrace{k-ww^T/\alpha^2}_{(n-1)\times (n-1)}=\bar{R}^T_2\bar{A}_2\bar{R}_2$

   where

   

   Cholesky Decomposition of $A \gt 0$

   $A=R^TR$, $R$ is upper triangle

   $\begin{aligned}A =R^T_1A_1R_1 &= R^T_1\begin{bmatrix}1&0\\0&\bar{R}^T_2\bar{A}_2\bar{R}2\end{bmatrix}R_1\\&=R^T_1\begin{bmatrix}1&0\\0&\bar{R}^T_2\end{bmatrix}\begin{bmatrix}1&\\&\bar{A}2\end{bmatrix}\begin{bmatrix}1&0\\0&\bar{R}2\end{bmatrix}R_1\\ &= R^T_1R^T_2A_2R_2R_1\\ (n-1) & \vdots\\& = \underbrace{R^T_1R^T_2\ldots R^T_n}{\text{lower triangle}}(I)\underbrace{R_nR{n-1}\ldots R_1}{\text{upper triangle}}\end{aligned}$