Positive Definiteness

1. Definite Matrices

An `Ntimes N` symmetric matrix `A` is positive definite if and only if for all `Ntimes 1` vector `x ne 0`, `x^tAx>0`.
An `Ntimes N` symmetric matrix `A` is positive semi-definite if and only if for all `Ntimes 1` vector `x ne 0`, `x^tAx geq 0`.
An `Ntimes N` symmetric matrix `A` is negative definite if and only if for all `Ntimes 1` vector `x ne 0`, `x^tAx<0`.
An `Ntimes N` symmetric matrix `A` is negative semi-definite if and only if for all `Ntimes 1` vector `x ne 0`, `x^tAx leq 0`.
A matrix that is not positive semi-definite and not negative semi-definite is indefinite.

2. What they look like

Suppose that `A` is a symmetric `2times 2` matrix and `x ne 0` is a `2times 1` vector.

\begin{align} A=
\begin{pmatrix} a & b \\ b & c \end{pmatrix} \Rightarrow
x^tAx=
\begin{pmatrix} x_1 & x_2 \end{pmatrix}
\begin{pmatrix} a & b \\ b & c \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} =
ax_1^2+2bx_1x_2+cx_2^2
\end{align}

As an example of the positive definiteness, let `a=c=1` and `b=0`. It means `x^tAx=x_1^2+x_2^2>0`. It looks like a convex function.
As an example of the positive semi-definiteness, let `a=1` and `b=c=0`. It means `x^tAx=x_1^2 geq 0`. It looks like a convex function, but there exists a point such that `x^tAx=0` for `x ne 0`.
As an example of the negative definiteness, let `a=c=-1` and `b=0`. It means `x^tAx=-x_1^2-x_2^2<0`. It looks like a concave function.
As an example of the negative semi-definiteness, let `a=-1` and `b=c=0`. It means `x^tAx=-x_1^2 leq 0`. It looks like a concave function, but there exists a point such that `x^tAx=0` for `x ne 0`.

As an example of the indefiniteness, let `a=1`, `b=0`, and `c=-1`. It means `x^tAx=x_1^2-x_2^2`. It does not look like a shape of the positive and negative definiteness. It has rather a saddle point.

3. Application: Hessian matrix

Suppose that `f: mathbb{R}^n rightarrow mathbb{R}` is twice continuously differentiable function and `x` is a critical point of `f`. According to Taylor’s Theorem,

\begin{align} f(x+s)=f(x)+\nabla f(x)^ts + \frac{1}{2} s^tH_f(x+\alpha s)s
\end{align}
where `s` is a `Ntimes 1` vector, `H_f` is the Hessian matrix of `f` and `alpha in (0,1)`. Since `x` is a critical point, `nabla f(x)=0`. Meanwhile, if `H_f` is positive definite, this property should be also true near `x`, so is `H_f``(x+alpha s)`. It means that `f` is increasing near `x`. Therefore, `f(x+s)>f(x)` and `f(x)` is a local minimum.

For a critical point `x`, if `H_f` is positive definite, then `x` is a minimum of `f`.
For a critical point `x`, if `H_f` is negative definite, then `x` is a maximum of `f`.
For a critical point `x`, if `H_f` is indefinite, then `x` is a saddle point of `f`.
For a critical point `x`, if `H_f` is semi-definite, then it requires a higher order differentiation.

4. Application: Cholesky factorization

If `A` is symmetric and positive (semi-)definite, the Cholesky factorization of `A` is available, which is arranged so that `LL^t=A` where `L` is lower triangular.
If there exists `L` such that `LL^t=A`, then for `x ne 0`, `x^tAx=``x^tLL^tx=``(L^tx)^t(L^tx)=``|| L^tx ||^2 geq 0`. Therefore, `A` is positive (semi-)definite.
Here are some examples:

\begin{align}
A_1 &=
\begin{pmatrix} 9 & 6 \\ 6 & 5 \end{pmatrix} =
\begin{pmatrix} 3 & 0 \\ 2 & 1 \end{pmatrix}
\begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix} \\
&\Rightarrow x^tA_1x=(3x_1+2x_2)^2+x_2^2 > 0 \text{ : positive definite} \\ \\
A_2 &=
\begin{pmatrix} 9 & 6 \\ 6 & 4 \end{pmatrix} =
\begin{pmatrix} 3 & 0 \\ 2 & 0 \end{pmatrix}
\begin{pmatrix} 3 & 2 \\ 0 & 0 \end{pmatrix} \\
&\Rightarrow x^tA_2x=(3x_1+2x_2)^2 \geq 0 \text{ : positive semi-definite} \\ \\
A_3 &=
\begin{pmatrix} 9 & 6 \\ 6 & 3 \end{pmatrix}
\Rightarrow x^tA_2x=(3x_1+2x_2)^2 \geq 0 \text{ : indefinite} \\ \\
A_4 &=
\begin{pmatrix} 0 & 0 \\ 0 & 4 \end{pmatrix} =
\begin{pmatrix} 0 & 0 \\ 2 & 0 \end{pmatrix}
\begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix} =
\begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix}
\begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix} \\
&\Rightarrow x^tA_2x=4x_2^2 \geq 0 \text{ : positive semi-definite}
\end{align}
Note that `A_3` cannot be factorized because it is indefinite. Moreover, the Cholesky factorization can have more than one solution such as `A_4`.

5. How to tell the matrix is positive definite

All pivots are positive: After Gaussian elimination, pivots are the first non-zero element in each row of a matrix. If all pivots of a matrix are positive, then it is positive definite.

\begin{align} A=
\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \Rightarrow
\begin{pmatrix} 1 & 2 \\ 0 & -3 \end{pmatrix}
\end{align}
After Gaussian elimination, `A` has the negative pivot, so it is not positive definite.

All the determinants of upper-left submatrices are positive:

\begin{align} A=
\begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix} \Rightarrow
|2|=2,
\begin{vmatrix} 2 & -1 \\ -1 & 2 \end{vmatrix}=3,
\begin{vmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{vmatrix} =4
\end{align}
So, `A` is positive definite.

All the eigenvalues are positive:

\begin{align} A=
\begin{pmatrix} 9 & 0 & -8 \\ 6 & -5 & -2 \\ -9 & 3 & 3 \end{pmatrix} \Rightarrow
\lambda_1=14.48, \lambda_2=-5.90, \lambda_3=-1.57
\end{align}
Since there are negative eigenvalues, `A` is not positive definite.

By definition: For a `Ntimes N` matrix `M`, `quad M^tM` is positive (semi-)definite.

\begin{align} x^tM^tMx = (Mx)^t(Mx)=\left\| Mx \right\|^2 \geq 0
\end{align}
If `Mx ne 0` for all `x ne 0`, `M^tM` is positive definite.