# how to proove function satisfy Lipschitz condition

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.

-
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)$? –  Berci Mar 28 '13 at 21:45
d is correct but it is W=$F_2^r$ :( –  sumit Mar 29 '13 at 8:12
Simultaneously cross-posted on cstheory.SE. Don't do that. –  JeffE Mar 29 '13 at 16:57

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.