Linear-time copositivity detection for tridiagonal matrices and extension to block-tridiagonality

摘要

Determining whether a given symmetric matrix is copositive (i.e., whether it generates a quadratic form taking no negative values on the positive orthant) is an NP-hard problem. However, for diagonal matrices this amounts to the trivial check of signs of the diagonal entries. Here, a linear-time algorithm for tridiagonal matrices is presented which similarly checks only for signs of diagonal entries, but (depending on the sign of an off-diagonal entry) sometimes updates the matrix by an ordinary pivot step. Ramifications for the sign-constrained border and generalizations for the block-tridiagonal case are also specified. As a key tool, we establish a monotonicity result for the Lowner ordering of partial Schur complements for general symmetric matrices with a positive definite principal block. [References: 9]