# How to determine positive or negative definite of a bordered Hessian ?

I want to determine the minimization result I get using Lagrange Multiplier method is a local minimum by determining whether the Bordered Hessian is positive definite or negative definite.(Hopefully negative definite for a local minimum)

But since I have a system of 1000 variables, I am stuck with a 1000*1000 matrix to determine whether it is positive definite or negative definite.(this is all real numbers)

Is there any way to do it other than calculates all the eigenvalue ? Someone suggests a cholesky decomposition, but I failed to understand why.

• since the number in first row and first column in Bordered Hessian is 0,Sylvester's criterion could not apply. – user56134 Aug 3 '15 at 22:29
• a symmetric matrix is positive definite if and only if it has a cholesky decomposition – user251257 Aug 3 '15 at 22:37

@ user56134 , a bordered Hessian cannot be $>0$ or $<0$ (cf. your comment)!). If there are $n$ unknowns and $m<n$ constraints, then you must consider the signum(s) of $n-m$ minors of the bordered Hessian. A priori, (if $m<<n$) the complexity of the calculation is in $O(n^4)$, that is here in $10^{12}$ ; yet, eventually there is a faster algorithm.