1
$\begingroup$

Let $S$ and $T$ be sets of vectors from $\mathbb{R}^d$ such that $S$ and $T$ are at least different in one element.

Does there exist a random matrix $M \in \mathbb{R}^{d \times k}$, e.g., a gaussian matrix, such that the probability of $ \sum_{s \in S} s M = \sum_{t \in T} t M $ is small in terms of $k$?

$\endgroup$
1
$\begingroup$

I hope this makes sense.

Let $v$ be the difference of the two vector sums. Since a randomly chosen Gaussian matrix will have maximuml rank $\min(d,k)$ with constant probability and almost maximum rank with overwhelming probability, the answer would be yes for most vectors $v \neq 0$.

So the answer would be dominated by the probability those two vector sums being equal.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.