MathGroup Archive 1995

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

Search the Archive

Re: Submatrix with greatest determinant?

  • To: mathgroup at christensen.cybernetics.net (mathgroup)
  • Subject: [mg821] Re: [mg689] Submatrix with greatest determinant?
  • From: hannibal at caesar.physik.uni-oldenburg.de (Dr. L. Hannibal)
  • Date: Mon, 24 Apr 1995 02:45:09 -0400

>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...

Richard, 

here is a straightforward solution, 
check if it is faster than yours.

1) Create the full list of all possible combinations of the indices
 of  N rows of an M x N matrix  by:

 sublist[m_, n_] := 
  Module[{l, i, j, k, r},
   l = Table[{i}, {i, 1, m - n + 1}]; 
   For[j = 2, j <= n, j++,
        For[k = 1, k <= Length[l], k++, 
          l[[k]] = Table[Append[l[[k]], r], {r, Last[l[[k]]] + 1, m - n + j}]
            ];
        l = Flatten[l, 1]
       ];
   l]

2) Calculate the (sub-)determinants with Laplace' rule. The values
of  calculated subdeterminants are stored for multiple use.

 subdet[1, rows_, columns_] := matr[[rows[[1]],columns[[1]]]]
 
 subdet[n_, rows_, columns_] := 
  subdet[n, rows, columns] = 
   Sum[(-1)^(k + 1)*subdet[n - 1, Drop[rows, {k}], Drop[columns, 1]]*
     matr[[rows[[k]],columns[[1]]]], {k, 1, n}]

3) I found it practical to do the following. Assume your matrix will be spec.

Define 

 setup[matr_] := 
  (Clear[subdet]; 
   subdet[1, rows_, columns_] := 
     matr[[rows[[1]],columns[[1]]]]; 
   subdet[n_, rows_, columns_] := 
     subdet[n, rows, columns] = 
      Sum[(-1)^(k + 1)*subdet[n - 1, Drop[rows, {k}], Drop[columns, 1]]*
        matr[[rows[[k]],columns[[1]]]], {k, 1, n}]; Null)

then run

 setup[spec] (* Clears previous values, and defines subdet for spec *)
 spec= ... (* whatever M x N matrix, do not define it before using setup *)
 sl=sublist[M,N];
 dets=subdet[N,#,Range[1,N]]& /@sl;

 maxdet=Max[Abs[dets]]


Hope this helps, Ludger

-------------------------
Ludger Hannibal (hannibal at caesar.physik.uni-oldenburg.de)


  • Prev by Date: Re: ODE solver
  • Next by Date: Re: Programming Options for Power Expand
  • Previous by thread: Submatrix with greatest determinant?
  • Next by thread: Student version in high schools