Recursive structure of S-matrices and an \(O(m^ 2)\) algorithm for recognizing sign solvability
type: Item
instance of: scholarly article
title: Recursive structure of S-matrices and an \(O(m^ 2)\) algorithm for recognizing sign solvability
zbMATH Open document ID: 0628.65034
DOI: 10.1016/0024-3795(87)90347-8
author: Victor Klee
published in: Linear Algebra and its Applications
publication date: 1987-01-01T00:00:00Z
review text: An S-matrix is an \(m\times (m+1)\) real matrix B such that for each matrix C of the same sign pattern as B, C's columns are the vertices of an m- simplex that has the origin in its interior. An \(S^*\)-matrix is one that can be made into an S-matrix by replacing some columns with their negatives. This paper establishes new results on the recursive structure of the class of all S-matrices and the class of all \(S^*\)-matrices. The results form the basis of algorithms of time complexity \({\mathcal O}(m^ 2)\) for recognizing S-matrices, \(S^*\)-matrices and strong sign solvability of linear systems.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15B57
zbMATH DE Number: 4022484
zbMATH Keywords: S-star matrix
zbMATH Keywords: S-matrix
zbMATH Keywords: recursive structure
zbMATH Keywords: algorithms
zbMATH Keywords: strong sign solvability of linear systems
MaRDI profile type: Publication
full work available at URL: 0024-3795(87)90347-8
OpenAlex ID: W2000044784
cites work: Qualitative Economics and the Scope of the Correspondence Principle
cites work: Recognizing sign solvable graphs
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Signsolvability revisited
cites work: The Theory of Qualitative Linear Systems
cites work: Graph-theoretical approach to qualitative solvability of linear systems
cites work: Q3959807
description: scientific article; zbMATH DE number 4022484