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

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.