Method to check for Positive definite matrices.

Question

I think its already been asked , but still i can't figure out a way to do it computationally,

I had to check for positive definiteness of a matrix $A$ of order $n$ by $n$.I know that for any vector $x$ of order $1$ by $n$ , $x^{t}Ax > 0$,

But the problem is i want to implement it while coding a C++ program for Cholesky method in which i need both 1)Symmetric matrix and 2)Positive definite matrix.

How do i approach this situation,if i go for the definition then it can be computationally inefficient as i have to check for each vector $x$.

Any other method which i can use for Positive - definiteness. ?

Any help is great!

Answer 1

A matrix $A$ is positive definite if and only if the symmetric matrix $M = A + A^T$ is positive definite. You should be able to find a program that attempts a Cholesky decomposition on $M$. If it succeeds, then $A$ is positive semidefinite. If it succeeds and the resulting lower-triangular matrix has only non-zero elements on the diagonal (or a non-square lower-triangular matrix), then $A$ is positive definite. If the Cholesky decomposition fails, then $A$ is not positive semidefinite (and of course, not positive definite).

Note: The above is a standard method for checking whether a matrix is positive definite. While this method is fine in the "general case", it is liable to yield false positives/negatives in the case that $A$ is close to being (or is) singular. See the other answer (and the linked extension) for a more thorough discussion of these "edge cases".

---

About $A + A^T$: note that for any $x$, we have $$ 2(x^TAx) = x^T(Ax) + (Ax)^Tx = x^TAx + x^TA^Tx = x^T(A + A^T)x $$ clearly, $x^TAx$ will be positive (or non-negative) if and only if $x^T(A + A^T)x$ is positive (or non-negative).

Answer 2

There are symmetric positive definite matrices $M$ for which Cholesky's algorithm will fail due to the limitations of floating point arithmetic.

A specific example is given here. Let $u \ll 1$ denote the unit round off error and consider the matrix $$ M = \begin{bmatrix} 1 + 2u & 1 \\ 1 & 1 - u \end{bmatrix}.$$ This matrix is exactly representable. It is clear that $M$ is symmetric positive definite, for $$ \text{Tr}(M) = 2 + u > 0$$ and $$ \text{det}(M) = u - 2u^2 > 0.$$

Now let $\text{fl}(x)$ denote the floating point representation of the real number $x$. Since $$1+2u = (1 + u)^2 - u^2$$ we have $$ 1 < \sqrt{1 + 2 u} < 1 + u < 1 + 2u. $$ It follows that $\text{fl}(\sqrt{1+2u}) = 1$ as there are no floating point numbers in the open interval between $1$ and $1+2u$ and we must pick the option which has the smallest error. After processing the first column of $M$ and performing the linear update of the lower right corner, we are left with $$ M^{(1)} = \begin{bmatrix} 1 & 1 \\ 1 & - u \end{bmatrix}.$$ The algorithm will now fail because the final pivot is strictly negative.

In general, if Cholesky's algorithm runs to completion, then it produces the exact factorization of a matrix $\hat{M} = \hat{L}\hat{L}^T $ which is close to $M$. This may very well be enough for your purposes, especially if you can establish that the smallest eigenvalue of $\hat{M}$ is not too small.