Principal minors. I: A method for computing all the principal minors of a matrix

DOI10.1016/J.LAA.2006.04.008MaRDI QIDQ854862zbMATH OpenOpenAlexFDO

Authors Kent Griffin, M. Tsatsomeros

Publication date 7 December 2006

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2006.04.008

zbMATH Keywords

\(LU\)-factorizationcomplexityMATLAB programP-matrixP-problemparallel computationprincipal submatrixSchur complement

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to linear algebra (15-04) Determinants, permanents, traces, other special matrix functions (15A15) Positive matrices and their generalizations; cones of matrices (15B48) Numerical computation of determinants (65F40) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Review text

It is known that the direct evaluation of all the principal minors of an arbitrary \(n\times n\) matrix via \(LU\)-factorization entails a time complexity of \(O(2^{n}n^{3}),\) therefore the computation is inherently exponentially hard. Nevertheless, this paper proposes a method which achieves a considerable saving in computing time, so that the complexity becomes of \( O(2^{n}).\) This allows the computation of all the principal minors of large matrices, which in practice we could not afford until now. The method resorts recursively to Schur complements and is simple to implement and suitable to parallel computers. This remarkable paper contains even the MATLAB program, which implements the presented method and is also available for download on the web.

Recommendations

• Principal minors. II: The principal minor assignment problem
• An algorithm to find formulae and values of minors for Hadamard matrices. II
• A recursive test for P-matrices
• The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
• scientific article; zbMATH DE number 2214023

Cites work

• An Algorithm for Checking Regularity of Interval Matrices
• An Identity for the Schur Complement of a Matrix
• Computing exact bounds on elements of an inverse interval matrix is NP-hard
• Drużkowski matrix search and D-nilpotent automorphisms.
• scientific article; zbMATH DE number 4214280 (Why is no real title available?)
• scientific article; zbMATH DE number 4109935 (Why is no real title available?)
• scientific article; zbMATH DE number 3661547 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• Interval P-Matrices
• Matrix Analysis
• On inverse multiplicative eigenvalue problems for matrices
• Open problems on GKK \(\tau\)-matrices
• Principal minors. II: The principal minor assignment problem
• Principal pivot transforms: Properties and applications
• Self-validating methods
• Some generalizations of positive definiteness and monotonicity
• The P-matrix problem is co-NP-complete
• Verification for existence of solutions of linear complementarity problems

Cited in

(18)

• A practical test for assessing the reachability of discrete-time Takagi-Sugeno fuzzy systems
• Determinant evaluations for binary circulant matrices
• An efficient algorithm for the symmetric principal minor assignment problem
• An eigenvalue approach evaluating minors for weighing matrices \(W(n, n-1)\)
• Hyperdeterminantal relations among symmetric principal minors
• Determination of the degrees of \(P\)-property and nonnegative invertibility for a fuzzy matrix
• The quadrifocal variety
• Mapping and preserver properties of the principal pivot transform
• Noncirculant Toeplitz matrices all of whose powers are Toeplitz
• Determinantal properties of generalized circulant Hadamard matrices
• The signed enhanced principal rank characteristic sequence
• The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
• The sepr-sets of sign patterns
• Hadamard matrices: insights into their growth factor and determinant computations
• Characterizing principal minors of symmetric matrices via determinantal multiaffine polynomials
• On sign-real spectral radii and sign-real expansive matrices
• Skew-symmetric matrices and their principal minors
• Principal minors. II: The principal minor assignment problem

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: Principal minors. I: A method for computing all the principal minors of a matrix

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