R help - Oct 2016 - Extract an invertible submatrix

Dear R helpers,

I am looking for an efficient way to extract (any) one of the biggest invertible
submatrix.

I have a rectangular matrix A (p x n), with rank k <= min(p, n). I would like
to get a submatrix (k x k) invertible, or even better, the list of rows and
columns of A which
would form the submatrix (A[rows, columns] would be invertible, with
length(rows)=length(columns)=k).

This is the general problem, but in my particular R code, the rank of A would be
p (p<n), so I only need to select p columns to get the submatrix. But I am
not sure it is
easier.
For now, my (very bad) solution would be to try every submatrix until I find one
invertible.

Do you think of any solution which would be more efficient ?

Best regards,
Bertrand

Use qr

tmp <- cbind(matrix(rnorm(30), 5, 6), 0)[, c(1,2,3,4,7,5,6)]
tmp
tmp.qr <- qr(tmp)
tmp.qr
tmp.qr$pivot
tmp.subset <- tmp[, tmp.qr$pivot[1:tmp.qr$rank]]
solve(tmp.subset)


On Sun, Oct 2, 2016 at 2:19 PM, Bertrand Marc <beberking at gmail.com>
wrote:
> Dear R helpers,
>
> I am looking for an efficient way to extract (any) one of the biggest
invertible submatrix.
>
> I have a rectangular matrix A (p x n), with rank k <= min(p, n). I would
like to get a submatrix (k x k) invertible, or even better, the list of rows and
columns of A which
> would form the submatrix (A[rows, columns] would be invertible, with
length(rows)=length(columns)=k).
>
> This is the general problem, but in my particular R code, the rank of A
would be p (p<n), so I only need to select p columns to get the submatrix.
But I am not sure it is
> easier.
> For now, my (very bad) solution would be to try every submatrix until I
find one invertible.
>
> Do you think of any solution which would be more efficient ?
>
> Best regards,
> Bertrand
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.