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

```

• Prev by Date: Re: Performance of student version of Mathematica?
• Next by Date: Student version in high schools
• Previous by thread: Constructing expressions
• Next by thread: Re: Submatrix with greatest determinant?