On the Complexity of Matrix Rank and Rigidity

DOI10.1007/978-3-540-74510-5_28MaRDI QIDQ3499780zbMATH OpenOpenAlexFDO

Authors Meena Mahajan, Jayalal Sarma M. N.

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

Determinants, permanents, traces, other special matrix functions (15A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of matrix rank and rigidity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• scientific article; zbMATH DE number 37868
• Probabilistic rank and matrix rigidity

Cited in

(19)

• Verifying the determinant in parallel
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Matrix rank and communication complexity
• On the complexity of matrix rank and rigidity
• Relations between least-squares and least-rank solutions of the matrix equation \(AXB=C\)
• ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID
• Some optimization problems on ranks and inertias of matrix-valued functions subject to linear matrix equation restrictions
• Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid
• Formulas for calculating the extremum ranks and inertias of a four-term quadratic matrix-valued function and their applications
• scientific article; zbMATH DE number 1555922 (Why is no real title available?)
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Probabilistic rank and matrix rigidity
• The computational complexity of some problems of linear algebra (extended abstract)
• scientific article; zbMATH DE number 7204284 (Why is no real title available?)
• 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

This page was built for publication: On the Complexity of Matrix Rank and Rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499780)