×

The largest subdeterminant of a matrix. (English) Zbl 0592.15004

Summary: It is a problem arising in a number of contexts, given a real matrix, to find the square submatrix with the largest determinant (in absolute or ordinary value). We show a connection between this problem and certain graph theoretic concepts, as well as propositional logic. It follows from our results that finding the largest subdeterminant of a matrix is an NP- complete problem, which suggests that it can only be done exhaustively.

MSC:

15A15 Determinants, permanents, traces, other special matrix functions
15A45 Miscellaneous inequalities involving matrices
90C30 Nonlinear programming
05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: EuDML