A recursive test for P-matrices (Q1577730)

The paper is devoted to the problem of testing whether a given square matrix is a P-matrix, that is all its principle minors are positiv. It is known that the comlexity of a direct approach (direct computation of all principle minors) or of an LU factorization method is \(O(2^n n^3)\). The authors propose now an \(O(n^2)\) algorithm for solving the P-matrix problem. The new method is based on a criterion for recursive transformation of the \(n\)-th order P-matrix problem to two P-matrix problems of order \(n-1\) using Schur complementation. A simple MATLAB program is included and complexity related observations are reported as well.