most recent 30 from http://mathoverflow.net 2013-06-18T07:00:14Z http://mathoverflow.net/feeds/question/6194 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6194/how-to-compute-the-rank-of-a-matrix Harrison Brown 2009-11-19T22:57:55Z 2009-11-29T05:33:58Z

<p>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.</p> <p>Here's the actual problem: We're given a <em>black-box</em> linear transformation from $V \rightarrow W$, where $V, W$ are vector spaces of dimensions m, n respectively (say m &lt; 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.</p> <p>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. </p>

http://mathoverflow.net/questions/6194/how-to-compute-the-rank-of-a-matrix/6197#6197 Kristal Cantwell 2009-11-20T00:08:13Z 2009-11-20T17:04:14Z

<p>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.</p> <p>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.</p> <p>I have found a paper on randomized algorithms for computing the rank of a matrix here:</p> <p><a href="http://www.emis.de/journals/ELA/ela-articles/articles/vol11%5Fpp16-23.ps" rel="nofollow">www.emis.de/journals/ELA/ela-articles/articles/vol11_pp16-23.ps</a> </p>

http://mathoverflow.net/questions/6194/how-to-compute-the-rank-of-a-matrix/7111#7111 Rune 2009-11-29T05:33:58Z 2009-11-29T05:33:58Z

<p>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. </p> <p>EDIT: I thought I could prove this easily, but now I'm not so sure. Is this what you're asking though?</p>