MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For any $x \in \mathbb{R}^n$, the following statement is trivially true:

There exists a set $I \subset \mathbb{R}^n$ with $|I| \leq n$ such that for any $x' \in \mathbb{R}^n$, if $x \cdot y = x' \cdot y$ for all $y \in I$, then $x \cdot y = x' \cdot y$ for all $y \in \mathbb{R}^n$.

Simply let $I$ be a set of vectors forming a basis for $\mathbb{R}^n$, and in fact, we uniquely specify $x$.

This simple fact ceases to be true in general, if we don't require that the dotproducts $x\cdot y$ and $x' \cdot y$ be equal, but simply that they be close. However, for a particular subset of vectors $C \subset \mathbb{R}^n$, we might hope for an analogue:

For any vector $x \in \mathbb{R}^n$ there exists a set $I \subset C$ with $|I| \lt\lt |C|$ such that if $x' \in \mathbb{R}^n$ satisfies: $|y\cdot x - y\cdot x'| \leq \alpha$ for all $y \in I$, then: $|y \cdot x - y \cdot x'| \leq \beta$ for all $y \in C$.

where $\beta > \alpha$, and an interesting parameter is how $\beta$ must relate to $\alpha$.

My question: What properties must a collection of vectors $C$ satisfy for a theorem like this to be true?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.