A b o u t   M e      |       P r o j e c t s     |       N o t e s       |       T h e   D a y    ︎ ︎

# 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.

︎Reference

[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.

emoy.net