6 Sylvester theorem
Sylvester’s theorem provides an operational criterion to determine whether a matrix is symmetric positive definite (SPD). We now state Sylvester’s theorem:
Theorem 6.1 (Sylvester’s Criterion) A symmetric matrix \bm{A} \in \Bbb{R}^{n \times n} is positive definite if and only if all its leading principal minors are positive. That is, \bm{A} is positive definite if and only if: \det(\bm{A}_k) > 0 \quad \text{for} \quad k = 1, 2, \ldots, n where \bm{A}_k is the upper-left k \times k submatrix (leading principal minor) of \bm{A}.
6.1 Why use sylvester theorem
The tedious and error prone operation of finding the minimum with the Lagrangian multiplier is the one that’s performed to determine if the matrix is (semi) positive defined in the kernel
\ker\{\nabla \bm{h}(\bm{x}^\star)\}
of the gradient of the constraints map. In fact for every stationary point \bm{x}^\star of the lagrangian we have to check that
\bm{z}^T \, \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) \, \bm{z} \geq 0 \qquad \forall \bm{z}\in \ker\{\nabla \bm{h}(\bm{x}^\star)\}
For sake of simplicity from now we will denote the matrix \nabla_{\bm{x}}^2 \mathcal{L}(\bm{x}^\star,\bm{\lambda}^\star) as \bm{A}. We can note that the vector \bm{z} \in \ker\{\nabla \bm{h}(\bm{x}^\star)\} (and from now on we refer to the matrix \nabla \bm{h} as \bm{B}) can be expressed as a linear combination of the vectors \bm{k}_i (that are representing the base of \bm{B}) in the way
\bm{z} = \bm{k}_1 \alpha_1 + \bm{k}_2 \alpha_2 + \dots + \bm{k}_p \alpha_p = \bm{K} \bm{\alpha} \qquad \bm{\alpha} \in \Bbb{R}^p
We can see that this expression can be reduced to a multiplication of a matrix K \in \Bbb{R}^{n\times p} (whose columns are the vector \bm{k}_i of the kernel base) and a p-dimensional vector \bm{\alpha} (where p is the number of constraints in the map \bm{h}(\bm{x}) ).
We can now rewrite the second order necessary condition considering that
\bm{z}^T \bm{A} \bm{z} = \bm{\alpha}^T \bm{K}^T \bm{A} \bm{K} \bm{\alpha} = \bm{\alpha}^T \bm{C} \bm{\alpha}, \quad \bm{C} := \bm{K}^T\bm{A}\bm{K} \in \Bbb{R}^{p\times p}
Example 6.1 Let’s consider the numerical problem when the values of the matrix
\bm{A} = \nabla_{\bm{x}}\mathcal{L} \quad\textrm{and}\quad \bm{B}=\nabla \bm{h}
are given with values
\bm{A} = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 0 & 1 \\ 3 & 1 & 0 \end{bmatrix} \qquad \bm{B} = \begin{bmatrix}1&0&0\end{bmatrix}
The first thing now is to compute the manually compute the kernel of the matrix \bm{B} in \Bbb{R}^3 solving the linear system
\begin{bmatrix} 1 &0 &0 \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix}= \bm{0} \quad \implies \quad \begin{cases} z_1 = 0 \\ z_2 = \alpha \\ z_3 = \beta \end{cases} \quad \alpha,\beta\in\Bbb{R}
At this point we can rewrite the kernel of B using the linear combination of the vector composing the base:
\ker\{\bm{B}\} = \begin{bmatrix}0 \\ \alpha \\ \beta\end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix} \alpha + \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\beta = \underbrace{ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1\end{bmatrix}}_{=\bm{K}} \begin{bmatrix} \alpha \\ \beta \end{bmatrix}
The last thing is now to compute the matrix C that should be analyzed to know if it’s (semi) positive defined or not:
\begin{aligned} \bm{K}^T\bm{A}\bm{K} & = \begin{bmatrix}0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 2 & 3 \\ 2 & 0 & 1 \\ 3 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \\ \bm{C} & = \begin{bmatrix} 0&1\\1&0 \end{bmatrix} \end{aligned}
This definition reduces the complexity of the problem at analyzing the matrix \bm{C} (that’s smaller than the original matrix A) and determining if that particular matrix is (semi) positive defined using two methods:
Considering the fact that \bm{C} is a symmetric matrix we know for sure that it can be diagonalised \bm{C}=\bm{T}^T \bm{\Lambda}\bm{T} (where \bm{\Lambda} is a diagonal matrix containing all the eigenvalues of \bm{C}); considering the expression \bm{\alpha}^T \bm{C} \bm{\alpha} = \bm{\alpha}^T \bm{T}^T \bm{\Lambda} \bm{T} \bm{\alpha} in order to have a semi positive defined matrix all the eigenvalue \lambda_i must be positive or at least equals to zero. If it happens that \lambda_i > 0 \qquad \forall i then the matrix is positive defined and the point is a local minimum;
One other solution is to use the Sylvester theorem that states:
a symmetric matrix \bm{A}\in \Bbb{R}^{n\times n} is positive defined if and only if all the principal minors of \bm{A} are strictly positive
(note that if one minor is equal to zero, no information can be retrieved with this method).
Example 6.2 (application of the Sylvester theorem) Let’s consider now the matrix
\bm{A} = \begin{bmatrix} 1 & 2 \\ 2 & 5 \end{bmatrix}
In order to determine if \bm{A} is positive defined we have to compute all the principle minors starting from the first \bm{A}_1 that’s represented only by the element a_{11} of \bm{A} and so
\bm{A}_1 = \det[1] = 1 > 0
The second (and last) principle minor of \bm{A} is the determinant of the whole matrix and it happens that
\bm{A}_2 = \det \begin{bmatrix} 1 & 2 \\ 2 & 5 \end{bmatrix} = 1 > 0
Having all minors greater then zero, this means that the matrix \bm{A} is positive defined.
The same result can be achieved by determining all the eigenvalues of the matrix and showing they are all positive; we can in fact see that the characteristic polynomial of \bm{A} is equal to
\begin{aligned} p(\lambda) & = \det \big[\bm{A}-\lambda \bm{I}\big] \\ & = \det\begin{bmatrix} 1-\lambda & 2 \\ 2 & 5-\lambda \end{bmatrix} \\ & = \lambda^2 - 6\lambda + 1 \end{aligned}
and thus \lambda_{1,2} = \frac{6\pm \sqrt{36-4}}{2} = 3 \pm \frac{\sqrt{32}}{2}
nothing that
\frac{\sqrt{32}}{2} < \frac{\sqrt{36}}{2} = 3
then all the eigenvalues \lambda_1,\lambda_2 are strictly positive and so \bm{A} is positive defined.
Trick for semi positive matrices
The Sylvester theorem gives no hint to determine if a matrix is semi-positive defined when a minor is equal to zero. However a way to determine if the matrix is semi-positive defined is by considering that the matrix
\bm{A} +\varepsilon \bm{I}
should be positive defined for values of \varepsilon approaching zero from the positive direction (for \varepsilon\rightarrow 0^+).
Example 6.3 (Trick for usage of the Sylvester theorem on semi-positive matrrices) Let’s consider now the matrix
\bm{A} = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}
The first minor \bm{A}_1 = \det[1] = 1 is positive, and so we have to compute the second principal minor noting that it’s equal to zero:
\bm{A}_2 = \det\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} = 4 - 2\cdot 2 = 0
This relation gives no clue on determining if \bm{A} is positive defined or not, but considering the trick yet defined we can compute
\det\begin{bmatrix} 1+\varepsilon & 2 \\ 2 & 4 + \varepsilon \end{bmatrix} = (1+ \varepsilon)(4+\varepsilon) - 4 = 5\varepsilon
We can see that this expression, for \varepsilon \rightarrow 0^+, is strictly greater then zero and this might conclude our analyses stating that \bm{A} is semi positive defined.
The same result can be defined by computing the eigenvalues of \bm{A} and so calculating the roots of the polynomial
\begin{aligned} p(\lambda) &= \det\begin{bmatrix} 1-\lambda & 2 \\ 2 & 4-\lambda \end{bmatrix} \\ & = (1-\lambda)(4-\lambda) - 4 \\ & = \lambda^2-5\lambda \qquad \implies \quad \lambda_1=0,\; \lambda_2 = 5 \end{aligned}
Having one eigenvalues zero (and the other positive) determines that \bm{A} is semi positive defined.
Example 6.4 (Counter example of the Sylvester theorem) Let’s consider now the matrix
\bm{A} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix}
The first minor \bm{A}_1 = \det[1] = 1 is positive, while the second one is zero, in fact
\bm{A}_2 = \det\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = 0
This result gives no information but we can use the trick by considering the determinant
\det\begin{bmatrix} 1 + \varepsilon & 1 \\ 1 & 1 + \varepsilon \end{bmatrix} = (1+\varepsilon)^2 - 1 = \varepsilon^2 +2\varepsilon > 0
for \varepsilon > 0.
Being \bm{A} a 3\times3 matrix we also need to compute the third minor that leads to another zero:
\begin{aligned} \bm{A}_3 &= \det \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \end{bmatrix} \\ & = 1 \det\begin{bmatrix} 1&1\\1&1 \end{bmatrix} - 1 \det\begin{bmatrix}1&1\\1&1\end{bmatrix} + 0 \det\begin{bmatrix}1&1\\1&1\end{bmatrix} \\ & = 0 \end{aligned}
We can use another time the Sylvester theorem trick considering the determinant
\begin{aligned} p(\varepsilon) & = \det\begin{bmatrix} 1+\varepsilon & 1 & 1 \\ 1 & 1+\varepsilon & 1 \\ 1 & 1 & \varepsilon\end{bmatrix} \\ & = (1+\varepsilon)\big(\varepsilon^2 + \varepsilon - 1\big) - (\varepsilon-1) - \varepsilon \\ & = \varepsilon\big(\varepsilon^2 + 2\varepsilon - 2\big) \end{aligned}
Having that the derivative
p'(\varepsilon) =3\varepsilon^2 + 4\varepsilon -2
is negative for \varepsilon approaching zero, then we can conclude that \bm{A} is not semi positive defined.
The same result can be confirmed calculating the eigenvalues of the matrix and so
p(\lambda) = \det\begin{bmatrix} 1 -\lambda & 1 & 1 \\ 1 & 1 -\lambda & 1 \\ 1 & 1 & -\lambda \end{bmatrix} = -\lambda\big(\lambda^2 - 2\lambda - 2\big)
\implies \qquad \lambda_1 = 0 \qquad \lambda_{2,3} = \frac{2\pm \sqrt{12}}{2} = 1 \pm \sqrt 3
Noting that \lambda_3 = 1-\sqrt 3 <0 is negative, than the matrix \bm{A} is for sure not semi positive defined.
This trick can be resumend in the following Lemma
Lemma 6.1 (Sylvester’s Trick) A symmetric matrix \bm{A} \in \mathbb{R}^{n \times n} is semi-positive definite if and only if all its leading principal minors \bm{A}_k satisfy the following conditions:
\det(\bm{A}_k) > 0, or
\det(\bm{A}_k) = 0 and the derivative of the perturbed determinant at \varepsilon = 0 is positive:
\frac{\mathrm{d}}{\mathrm{d}\varepsilon} \det(\bm{A}_k + \varepsilon \bm{I})\Big|_{\varepsilon=0} > 0