Quickly determine the definiteness of a large sparse matrix without using Sylvester’s criterion

hessian-matrixlinear algebramatricesoptimizationpositive definite

I am currently trying to classify the stationary points of a function as either a maximum, minimum or saddle points based on the definiteness of the Hessian at those points.

I have worked out that the Hessian at two of the points are
$$\begin{bmatrix}
aI_{n-1} & -v\\
-v^{T} & n-1
\end{bmatrix}_{n\times n}$$

Where $I_{n-1}$ is the identity matrix of size $n-1$, $a=0,3$ and $v$ is an $n-1$-dimensional column vector

$$v = \begin{bmatrix}
1\\
1\\
\vdots \\
1
\end{bmatrix}$$

  1. The solution to the problem states that the matrix is obviously indefinite for $a=0$. How is it obvious? Sylvester's criterion shows that it is not positive definite or negative definite, nothing more. The determinants of the n upper left matrices are all 0.

  2. Also, the solution says that the Hessian is positive definite for $a=3$ due to the relation

$$
\begin{bmatrix}
I_{n-1} & 0\\
v^{T}/3 & 1
\end{bmatrix}
\begin{bmatrix}
3I_{n-1} & -v\\
-v^{T} & n-1
\end{bmatrix}\begin{bmatrix}
I_{n-1} & v/3\\
0 & 1
\end{bmatrix}=\begin{bmatrix}
3I_{n-1} & 0\\
0 & 2(n-1)/3
\end{bmatrix}
$$

What relation is this? Is there a toolset that can be used to help classify these types of matrices?

Best Answer

For the second question, for $n\in \mathbb N \setminus \{1\}$ and any $a\in \mathbb R\setminus \{0\}$, we can use the Schur's complement. Under these assumptions, using the Schur's complement, the positive definiteness of the matrix $$ H=\begin{bmatrix} a I_{n-1} & v \\ v^T & n-1\end{bmatrix},$$ is equivalent to the positivity of $n-1-\frac{v^Tv}{a}=n-1-\frac{{n-1}}{a}.$ This means that for any $a$ such that $a>\frac{{n-1}}{n-1}=1$. Of course, this implies that $a$ must be poisitve for the positive definiteness of the matrix $H$.

By the way, using the given decomposition (related to $a=3$) in the solution of the question for $H$, you should be able to show the positive definiteness of this matrix through the standard definition.

For the first question, for $n\in \mathbb N \setminus \{1\}$, we can also use the Schur's complement to say that $H$ is PD iff $aI_{n-1}-\frac{vv^T}{n-1}$ is PD. For $a=0$, we have $\frac{vv^T}{n-1}\succeq 0$, implying that $H$ is not PD for $a=0$. To show $-H$ is not PD, use the vector $[0,\dots,0, 1]^T$ and the definition. Consequently, $H$ and $-H$ are not PD, so the matrix $H$ is indefinite.