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$?



Probability of collision of sums of vectors multiplied by random matrix
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.


