A homological characterization of Q-matrices

• 成果类型: Article
• 署名作者: Naiman, DQ; Stone, RE
• 署名单位: Johns Hopkins University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.23.2.463
• 发表日期: 1998
• 页码: 463-478
• 关键词: arrangements

摘要

A real square matrix M is said to be a e-matrix if the linear complementarity problem (q, M) has a solution for every vector q. There is, as yet, no characterization of e-matrices which makes it easy to determine whether or not a given matrix is Q. Ideas from topology, in particular degree theory, have previously been used to obtain sufficient conditions fdr when a matrix is Q. In this paper we will apply some other ideas from topology to give a homological characterization of Q-matrices. Continuing to borrow from topology, we define the nerve of a matrix which, along with our characterization, leads to an algorithm for checking whether or not a matrix is Q. This algorithm has smaller bounds on its worst-case time complexity than previous methods.