1
$\begingroup$

Consider a set $\{\mathbf{X}_1,\cdots , \mathbf{X}_M\}$ of distinct points in $\mathbb{R}^n$ with $M$ finite. The $M$ values of the $i$-th coordinate do not all have to be dinstinct. For example, in $\mathbb{R}^2$ the points could be placed on a regular grid so that several points have the same x or y coordinates.

Let's now consider a rotation, that maps the original set into a new set $\{\mathbf{X}_1', \cdots, \mathbf{X}_M'\}$.

I would like to show that if we select the rotation randomly, i.e. if we project on a random orthogonal basis, the $M$ values of the $i$-th coordinates of the new set will be distinct for all $i=1, \cdots, n$ with probability almost one.

Intuitively it sounds like that should be the case. But I have no experience with random matrices and I wonder where I could start from to prove it.

$\endgroup$
2
  • $\begingroup$ The set of rotations forms a compact group $SO(n)$. The result you are looking for comes from results in algebraic geometry applied to this group, with a little measure theory at the end. $\endgroup$
    – user44191
    Apr 26 '18 at 17:03
  • $\begingroup$ You can also use a counting type argument based on a geometric interpretation. Draw hyper planes including the points, so that a rotation of the point set to one with agreement on some coordinates means "making one of the planes vertical". How often can you do this? Gerhard "Not Very Often, I'd Say" Paseman, 2018.04.26. $\endgroup$ Apr 26 '18 at 17:11
1
$\begingroup$

For any two distinct integers $l,m \in \{1,\ldots, M\}$, let us define $\mathbb{P}_{lm}$; be the $(n-1)$-dimensional space consisting of vectors in $v \in \mathbb{R}_n$ satisfying $v^T(\mathbf{X}_l-\mathbf{X}_m) = 0$ Then as long as $\mathbf{X}_l-\mathbf{X}_m$ is nonzero the probability that a randomly chosen vector of norm 1 from ${\mathbb{R}}_n$ lands in $\mathbb{P}_{lm}$ is 0 (as it would be for any $(n-1)$-dimensional space).

So let $A$ be the randomly chosen matrix from $SO_3$. For any positive integers $l,m \le M$ and $p \le n$ only way $A\mathbf{X}_l$ and $A\mathbf{X}_m$ can agree on the $p$-th coordinate is if the $p$-th row $v_p$ of $A$ is in $\mathbb{P}_{lm}$. However, given $A$ randomly chosen from $SO_3$ according to the uniform distribution, then for any one such integer $p$, the $p$-th row $v_p$ of $A$ is also chosen according to the uniform distribution from the set of vectors of norm 1. The probability of $v_p$ so chosen being in $\mathbb{P}_{lm}$ is 0. Thus, for any one choice of $p,l,m$ the probability that the $p$-th coordinate of $A\mathbf{X}_l$ equals the $p$-th coordinate of $\mathbf{X}_m$ is 0. To conclude that the probability is 0 that there is any such $p,l,m$ where the $p$-th coordinate of $A\mathbf{X}_l$ equals the $p$-th coordinate of $\mathbf{X}_m$ use the Union Bound; only $nM^2$ such choices for $p,l,m$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! I will go through it in detail. It might take a bit cause I am not used to this sort of proofs. $\endgroup$
    – Cesare
    Apr 27 '18 at 16:17

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