On the Complexity of Matrix Rank and Rigidity

DOI10.1007/978-3-540-74510-5_28zbMath1188.68158MaRDI QIDQ3499780

M. N. Jayalal Sarma, Meena Mahajan

Publication date: 3 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74510-5_28

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

15A15: Determinants, permanents, traces, other special matrix functions

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Matrix Rigidity from the Viewpoint of Parameterized Complexity, Some optimization problems on ranks and inertias of matrix-valued functions subject to linear matrix equation restrictions, Formulas for calculating the extremum ranks and inertias of a four-term quadratic matrix-valued function and their applications, Max-min problems on the ranks and inertias of the matrix expressions \(A - BXC \pm (BXC)^{\ast}\) with applications, Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method, Rigidity of a simple extended lower triangular matrix, The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems, Relations between least-squares and least-rank solutions of the matrix equation \(AXB=C\)