15
$\begingroup$

Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.

Here's the actual problem: We're given a black-box linear transformation from $V \rightarrow W$, where $V, W$ are vector spaces of dimensions m, n respectively (say m < n), and we want to know if it has full rank. (Numerical considerations aren't an issue; if you want, say it's over a finite field.) This is easy to do in time $O(m^2n)$ and with m calls to the black-box function, just by computing the image of a basis in m and using Gaussian elimination. It's also immediately obvious that we can't do better than m calls to the function in a deterministic algorithm, and I'm pretty sure but haven't quite managed to prove that you can't beat Gaussian elimination asymptotically either.

But can we do better if we just want a probabilistic algorithm? If we're allowed to make as many function calls as we want? What's the best lower bound we can get, probabilistically? These are probably pretty trivial questions (since everything's linear-algebraic and nice), but I just don't know how to approach them.

$\endgroup$
8
  • 1
    $\begingroup$ “How to compute the rank of a linear transformation” would be more accurate I think, but I like your little joke. Don't change the title unless confronted by hordes of mathematicians with pitch forks and torches. $\endgroup$ Nov 19, 2009 at 23:18
  • 2
    $\begingroup$ If the algorithm is to be probabilistic, I think it does matter what the field is. For instance, whatever "reasonable" measure you choose to select a random transformation R^m->R^n, the probability that it'll have full rank will be very close to 1, so an algorithm that says "full rank!" without asking any questions is actually a pretty good algorithm. Over a finite field, the situation is obviously different, but if the field is large relative to m, n I suspect you're in the same ball game. Am I misinterpreting your question? $\endgroup$
    – Alon Amit
    Nov 20, 2009 at 0:25
  • 1
    $\begingroup$ @Alon: Yeah, I think so. It's easy on average, which is what you're talking about. But I want a randomized algorithm that for every black-box function returns the right answer with high probability. $\endgroup$ Nov 20, 2009 at 0:39
  • 1
    $\begingroup$ Gaussian elimination takes longer than O(mn) time, unless you have a revolutionary algorithm, or some a priori knowledge of sparseness. $\endgroup$
    – S. Carnahan
    Nov 20, 2009 at 15:40
  • 1
    $\begingroup$ haha I think its fine to have a misleading title as long as its all fun and games. $\endgroup$
    – user1447
    Nov 20, 2009 at 17:32

2 Answers 2

8
$\begingroup$

I think there would be a problem if the transformation was almost independent. If one vector were a combination of the others but otherwise there was independence. I think you would have to compute the image of basis to test for this.

If you want to have a high probability for any every black box function it will have to deal with a distribution with either full rank or rank n-1 and that specific case of rank n-1 with no dependent set of rows smaller than n-2 which looks hard.

I have found a paper on randomized algorithms for computing the rank of a matrix here:

www.emis.de/journals/ELA/ela-articles/articles/vol11_pp16-23.ps

$\endgroup$
2
  • $\begingroup$ Right, that's the argument that shows that you have to make dim(V) function calls, and it's intuitively where the lower bounds should come from, but I don't see how to make it precise. $\endgroup$ Nov 20, 2009 at 0:50
  • $\begingroup$ Ooh, that paper is nice! Apparently it's an open problem (as of 2004?) over a field of positive characteristic, and they explain where the difficulty is with their methods. Other papers on the authors' webpages are also helpful. I'm tempted to accept this, but I kind of want to see if anyone knows the current status. $\endgroup$ Nov 20, 2009 at 17:28
0
$\begingroup$

Do you just want a lower bound on the number of function calls? You say that "we can't do better than m calls to the function in a deterministic algorithm". I would expect the same to be true for a bounded-error probabilistic algorithm as well.

EDIT: I thought I could prove this easily, but now I'm not so sure. Is this what you're asking though?

$\endgroup$
2
  • $\begingroup$ A lower bound on the number of function calls would be nice, although I suppose what I really want is the number of basic operations in the base field... And yes, it's definitely trickier than it seems at first glance! $\endgroup$ Nov 29, 2009 at 7:04
  • $\begingroup$ Interesting. How do you show that you need &Omega;(m) function calls in the deterministic algorithm case? And how in the world do you show that Gaussian elimination is optimal? $\endgroup$
    – Rune
    Nov 29, 2009 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.