MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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?