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)