Papadimitriou, Christos H. The largest subdeterminant of a matrix. (English) Zbl 0592.15004 Bull. Greek Math. Soc. 25, 95-105 (1984). 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. Cited in 4 Documents MSC: 15A15 Determinants, permanents, traces, other special matrix functions 15A45 Miscellaneous inequalities involving matrices 90C30 Nonlinear programming 05A05 Permutations, words, matrices Keywords:square submatrix with largest determinant; NP-complete problem PDFBibTeX XMLCite \textit{C. H. Papadimitriou}, Bull. Greek Math. Soc. 25, 95--105 (1984; Zbl 0592.15004) Full Text: EuDML