After some search here and on Google, I couldn't find a way to determine the definiteness of this matrix:
\begin{bmatrix}0&1\\1&0\end{bmatrix}
My understanding is that it should be negative semi-definite since all principal minors are $\leq 0$.
However, in the sample solutions of the book I am working through it stated that it is neither positive nor negative semi-definite.
A general procedure (for positive and negative semi-definiteness) would be really helpful.
Why is that?
(Not a general procedure) Going back to the original definition, a matrix $M$ is positive semi-definite if $v^T Mv\ge 0$ for all $v\in\mathbb R^n$ (similar for negative). But
$$ \begin{bmatrix}a&b\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix} = 2ab $$ The expression is not always $\ge 0$ or $\le 0$, so the matrix is indefinite.
In general, the signs of the eigenvalues of a symmetric matrix $A$ determine whether the matrix is positive (semi)-definite or negative (semi)-definite. If all the eigenvalues are positive (non-negative), the matrix is positive (semi)-definite. If all the eigenvalues are negative (non-positive), the matrix is negative (semi)-definite. In your case, the characteristic polynomial of $A$ is
$$ p_A(\lambda) = \lambda^2 - \operatorname{tr}(A) \lambda + \det(A) = \lambda^2 - 1 = (\lambda - 1)(\lambda + 1). $$
Thus, $A$ has two eigenvalues $\pm 1$. Since one is positive and another is negative, the matrix $A$ is not positive nor negative.
Let $M$ be your matrix. You have $M(1, 1) = (1, 1)$ and $M(1, -1) = (-1, 1)$, so it has the eigenvalues $1 > 0$ and $-1 < 0$, so it is neither positive- nor negative-semidefinite.
A less complicated way of remembering/explaining this is to look at your first principle minor(H1). H1≤0 but technically H1≥0 as well, as H1=0. In this case, your optimal is at a saddle point, and the function is indeterminant at that point(none of the definites,semi or otherwise). That last conclusion might not be a perfect explanation, but if you are just worried about which semi-definite it is, just remember that anytime a principle minor=0, it is none of them.
