2
$\begingroup$

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is:

Is the asymptotic lower bound for finding a single vector in $\operatorname{null}(A)$ also $O(nk^2)$?

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ Certainly not. You can focus on a $k\times (k+1)$ submatrix and find a vector in $O(k^3)$ steps (assuming your bound is correct). $\endgroup$
    – Christian Remling
    Commented Jun 1, 2014 at 3:59
  • 1
    $\begingroup$ What do you mean by "discover"? A basis contains (at least) $n-k$ vectors in $\mathbb{R}^n$, so to output one you need at least $O(n^2)$ operations. $\endgroup$
    – Federico Poloni
    Commented Jun 1, 2014 at 6:46
  • 2
    $\begingroup$ @ChristianRemling I don't see how one can get the vector in $\mathbb R^n$ from the $k \times (k+1)$ submatrix. What about the other $n-k-1$ components? $\endgroup$
    – Yuan Gao
    Commented Jun 1, 2014 at 7:52
  • 2
    $\begingroup$ @YuanGao You find $v\neq 0 \in \mathbb{R}^{k+1}$ in the kernel of the $k\times (k+1)$ submatrix and pad the vector with zeros in the other positions. $\endgroup$
    – Federico Poloni
    Commented Jun 1, 2014 at 10:11
  • 2
    $\begingroup$ Similar question posted to m.se, math.stackexchange.com/questions/815803/… without any notice to either site. $\endgroup$
    – Gerry Myerson
    Commented Jun 2, 2014 at 0:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .