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.

- 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,
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:
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.
After Gaussian elimination, `A` has the negative pivot, so it is not positive definite.
- All the determinants of upper-left submatrices are positive:
So, `A` is positive definite.
- All the eigenvalues are positive:
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.
If `Mx ne 0` for all `x ne 0`, `M^tM` is positive definite.
︎Reference
[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.
[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.
emoy.net