Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns

Tao Jiang, Minbo Gao, Shaowei Cai

Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their c…