Let $v_1,\ldots, v_n\in \mathbb{F}_{2}^r$ be $n$ column vectors chosen uniformly and independently at random from ${\mathbb{F}_2}^r$. Let $f$ be a function defined as follows:$ [f(v_1,\ldots, v_n)$= $\min _{D\subseteq [n], \{v_i~|~i\in D\}\mbox{ are linearly dependent}}|D|, ]$ i.e., $f(v_1,\ldots, v_n)$ is the minimum number of columns that are linearly dependent. Show that $f$ satisfies the Lipschitz property.

  • $\begingroup$ What are the metrics (and on exactly which spaces)? Are we considering $W:={(\Bbb F_2^r)}^n$ with metric $d((v_1,..,v_n)\,,\,(w_1,..,w_n)):=\sum_i d(v_i,w_i)$? $\endgroup$
    – Berci
    Mar 28, 2013 at 21:45
  • $\begingroup$ d is correct but it is W=$F_2^r$ :( $\endgroup$
    – sumit
    Mar 29, 2013 at 8:12
  • 3
    $\begingroup$ Simultaneously cross-posted on cstheory.SE. Don't do that. $\endgroup$
    – JeffE
    Mar 29, 2013 at 16:57

1 Answer 1


As stated, $f$ is identically zero; the smallest linearly independent subset of any set of vectors is the empty set. The zero function is trivially Lipschitz for every metric.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .