Submatrix with greatest determinant?

*To*: mathgroup at christensen.cybernetics.net*Subject*: [mg689] Submatrix with greatest determinant?*From*: rak at canon.co.uk (Richard Kirk)*Date*: Mon, 10 Apr 1995 11:29:15 GMT

Given M vectors in N dimensions, where M > N, I need to find the subset of N vectors that as an N*N matrix has the greatest determinant. I can do this by finding out all the possible subsets and evaluating all the determinants. My crude program went something like this... -------- Needs ["DiscreteMath`Combinatorica`"]; spectra = << WandN.spectra ; keeplist = Range[5,35,3]; patchlist = {1,2,3,4,5,6,7,10,11,14,16,23, 32,37,42,43,44,52,53,54}; subspec = spectra[[patchlist,keeplist]]; sublist = KSubsets[Range[Length[subspec]],Length[keeplist]] ; detlist = Abs[Det[subspec[[#]]]]& /@ sublist ; detmax = Max[detlist] {{p}} = Position[detlist,detmax,{1}] ; newlist = patchlist[[sublist[[p]]]] newspec = subspec[[sublist[[p]]]]; (etc) --------- The 'sublist' and the 'detlist' lines take a lot of calculating. I know the others are not as fast as they might be, but these two are the real killers. I can avoid keeping the values of 'sublist' and roll the two lines into one. There is a quick way of finding the nth Ksubset. It doesn't seem to save that much time, though. My vectors are bases on experimental results so it is not worth having a first pass to weed out similar vectors. Clearly it is possible to re-use a lot of the determinant calibrations and abandon some of the calculations where it is obvious the determinant will not exceed the maximum value. Has anyone got a fast solution to this? Or does anyone want to collaborate on building one? -- Richard Kirk 01483-448869 (phone) 01483-448845 (fax) Canon Research Europe Ltd, rak at canon.co.uk