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