how do you recognize a positive (semi)definite matrix?

Question

I understand that the definition of (semi-)definiteness of matrix $A$ is $$\forall z_{\neq0}\in\mathbb R^k: z^TAz>0$$

I also know that this doesn't mean that all elements of a negative definite matrix $A$ are negative (in fact, they may all be positive or 0, such as with a 180 degree rotation in $\mathbb R^2$).

Nevertheless, I'm wondering if there is a way to recognize, just by looking at the matrix, whether it is likely going to be a positive definite matrix? Is there a way to see this just from the matrix itself, or does it always require some form of computation first?

Answer 1

There are some things you can test...

Full Rank
If the matrix is not of full rank, it has a non-trivial kernel. Hence there exists a vector $v$ such that $Av=0$ and thus $v^\top Av=0$. And therefore $A$ is not positive definite.
An easy way to test this, is linear dependence of the rows / columns.

Eigenvalues
If $A$ is symmetric/hermitian and all eigenvalues are positive, then the matrix is positive definite.

Main Diagonal Elements
Because of $a_{ii}=e_i^\top Ae_i>0$ all main diagonal entries have to be positive. If not the matrix is not positive definite.

Gerschgorin Circles
This is a cool criterion, that you usually don't learn in linear algebra. Consider the circle disks $$K^i:= K_{r_i}(a_{ii})⊂ℂ$$ with midpoint $a_{ii}$ and radius $r_i = \sum_{j\neq i}|a_{ij}|$. All eigenvalues of $A$ are in the union of these disks.

Again you can tell something about the eigenvalues. E.g. if $A$ is symmetric, $a_{ii}>0$ and $a_{ii}>r_i$ all circles are in the right half of the complex plane, and thus $A$ is positive definite. [keyword diagonal dominance]

Note, that you can also compute the circles for $A^\top$.

Hurwitz criterion
The north-west minors of a matrix $A$ are the determinants of the sub-matrices $$ H_1 = \pmatrix{a_{11}}, \qquad H_2=\pmatrix{a_{11} & a_{12} \\ a_{21} & a_{22}}, \qquad H_3=\pmatrix{a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33}} \qquad ...$$ If $\det(H_i)>0$ for all $i=1,…,n$ then $A$ is positive definite. If they have alternating sign $\det(H_i)=(-1)^ia$, with $a>0$, then $A$ is negative definite.

Note that this is very expensive to compute.

Addition of Transpose
It is $v^TAv=(v^TAv)^T=v^TA^Tv$. And therefore $$2 v^\top A v = v^\top Av + v^\top A^\top v = v^\top(A+A^\top)v,$$ So, $A$ is positive definite if, and only if, $A+A^\top$ is positive definite. Since $A+A^\top$ is symmetric it might be easier to check for positive definiteness.

Answer 2

So we can assume with out loss of generality that $A$ is symmetric, and the reason for it is written in @P.Siehr's answer. I have a small addition for that answer.

It might be easier to actually work with another matrix from which you can immediately see it is positive definite. So let us define what one calls a symmetric matrix operation.

Definition. A symmetric matrix operation is one of the following operations on a matrix:

(1) Multiplying the $i$-th row and the $i$-th column by the same number $\beta\neq 0$;

(2) Interchanging the $i$-th and the $j$-th column and interchanging the $i$-th and the $j$-th row;

(3) Adding $\beta$ times the $i$-th column to the $j$-th column and $\beta$ times the $i$-th row to the $j$-th row.

If matrix $B$ can be gotten from matrix $A$ with symmetric matrix operations, then we say $A\simeq B$.

Lemma. Let $A\simeq B$. Then $A$ is positive definite if and only if $B$ is positive definite.

This can be very useful. Because then you can use all the things that is told in the other answers on another matrix that is easier to handle. Because this might be vague. Let me illustrate it with an example.

Example. Let $A$ be the following matrix: \begin{align} A= \begin{pmatrix} 1 & 4 \\ 4 & 3 \end{pmatrix} \end{align} This matrix might be easy. But let's do some symmetric operations on it, in particular number 3, we substract 4 times the first column from the second column and must also do something similar for the rows: \begin{align} \begin{pmatrix} 1 & 4 \\ 4 & 3 \end{pmatrix} \stackrel{(3)}{\simeq} \begin{pmatrix} 1 & 0 \\ 0 & -13 \end{pmatrix} =B \end{align} Now you immediately see that B is not positive definite, hence $A$ is also not positive definite. You can check yourself that an eigenvalue of $A$ are $2- \sqrt[]{17}$ which is surely negative.

In the above example we got a diagonal matrix after the first operation, but that is not always the case. For larger matrices that might take longer. However that is not a reason to put this method down, because sometimes you see that you get a matrix $B$ after some number of operations such that $B$ is not positive definite by just looking at its diagonals, say.

Here you have got an extra tool for achieving your goal faster. I hope that this helped you a little bit.

PS: the lemma also works if we would have positive semidefinite instead of positive definite.

Answer 3

If the matrix is symmetric, positive semi-definiteness ($\forall z \neq 0\ z^T A z \geq 0$) is equivalent to the matrix having non-negative eigenvalues. In general, there is always some computation required. An easy sanity check is to make sure the trace of the matrix is not negative, because that would imply that the matrix has a negative eigenvalue. You could use Gershgorin's circle theorem (see here) to check whether the matrix will always have positive eigenvalues. Otherwise, Sylvester's criterion is the most direct approach.