detecting non-singular square sub-matrices in rectangular matrice s.

Dear All,

I was wondering whether anyone knew of an efficient way of testing 
whether a non-singular square sub matrix of dimensions p X p exists 
within a rectangular matrix of dimensions p x m.  Typically, p will 
be about 4, and m several thousand so an exhaustive test of all 
possible sub matrices would be prohibitive when dealing with a large 
number of rectangular matrices.

Thanks for any suggestions,

Jarrod.