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.
3
-
$\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$– BerciMar 28, 2013 at 21:45
-
$\begingroup$ d is correct but it is W=$F_2^r$ :( $\endgroup$– sumitMar 29, 2013 at 8:12
-
3$\begingroup$ Simultaneously cross-posted on cstheory.SE. Don't do that. $\endgroup$– JeffEMar 29, 2013 at 16:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
