A problem on Cartesian coordinates

Yesterday Paul Lai asked the following
Question: Suppose there are {m} distinct points {p_1, \cdots, p_m} in {{\mathbb R}^n, n\geq 2}, can we find a Cartesian coordinates {x_i} such that {x_i(p_j)\neq x_i(p_k)} for all {i} and distinct {p_j, p_k}?

As expected, the answer is positive. After discussing with Paul Lai, we arrived at the following

Theorem 1 (Paul Lai’s theorem, 2011) For {m} distinct points {p_1, \cdots, p_m} in {{\mathbb R}^n, n\geq 2}, there are infinitely many Cartesian coordinates systems {\{x_i\}} such that {x_i(p_j)\neq x_i(p_k)} for all {i} and distinct {p_j, p_k}.  

(In this note, for a line we mean a one-dimensional subspace (of some {\mathbb{R}^n}), and by a hyperplane we mean a codimension one subspace (e.g. a plane inside a 3-dimensional space). In particular they all contain {0}. )

Proof: First of all note that for distinct {p} and {q}, {x_i(p)=x_i(q)} if and only if {p} and {q} both lies on a coordinate hyperplane {\{x_i=\text{const}\}}, and this is equivalent to the coordinate vector {e_i} lies on the hyperplane {\overrightarrow{pq}^\perp}.

Now, since there are only finitely many {p_i}, the problem is equivalent to finding orthonormal bases {\{v_i\}_{i=1}^n} such that no {v_i} lies on a given collection of finitely many hyperplanes. (In our situation, they are {\overrightarrow {p_jp_k}^\perp} and there are at most {\begin{pmatrix} m\\2 \end{pmatrix}} of them. ) We will use induction on {n} to prove this claim, more precisely we will show: given finitely many hyperplanes in {{\mathbb R}^n}, there are infinitely many orthnormal bases {\{v_i\}_{i=1}^n} such that no {v_i} lies on any of these hyperplanes.

For {n=2}, the hyperplanes are just lines, the collection {C} of all these lines and their orthogonal complements contains only finitely many lines. For any line {l\notin C}, {l^\perp\notin C}, and clearly there are infinitely many such {l}. We can then find a unit vector {v_1} which generates {l} and {v_2} which generates {l^\perp}. {\{v_i\}} is then our desired basis.

Assume the claim is true up to dimension {n}. Now, let {l} be a line in {\mathbb{R}^{n+1}} which does not lie on any of the given hyperplanes P_j and also is not perpendicular to any of them (there are only one line perpendicular to each hyperplane), then {l^\perp\cong {\mathbb R}^n} is not any of the {P_j}. In particular, each {P_j':=P_j\cap l^\perp} is a hyperplane in {l^\perp}. So by induction assumption we can find infinitely many basis {\{v_1, \cdots, v_n\}} for which no {v_i} lies on any {P_j'}. We then find a generator {v_{n+1}} for {l} and {v_1,\cdots, v_{n+1}} is the desired basis. \Box

Actually we can do more. Intuitively, for “almost all” choices of the Cartesian coordinates system (i.e. except some very special choices), the conclusion in Theorem 1 holds, i.e. the coordinates of all points are sufficiently distinct. This can be formulated more rigorously as follows.

As remarked in the previous proof, the problem is equivalent to finding (ordered) orthonormal bases which avoids lying on some hyperplanes. The set of all ordered orthonormal basis is exactly the space {O(n)} of orthogonal matrices, as is seen by looking at each column vector of the matrices. It is not hard to see that {O(n)} is a smooth closed (i.e. comapct without boundary) submanifold of dimension {n(n-1)/2} (the exact dimension is not important) of the space of all matrices, identified with {{\mathbb R}^{n^2}}. Therefore {O(n)} inherits a {n(n-1)/2} dimensional volume element (or Hausdorff measure) {\mu} on it. (I don’t know the relation between this measure and its bi-invariant Haar measure, it seems to me that {\mu} is not necessarily left or right invariant. ) With this notations, we have

Theorem 2 (Paul Lai’s theorem, 2011) Given finitely (or countably) many hyperplanes in {{\mathbb R}^n}, for {\mu} almost every {A\in O(n)}, no column of {A} lies in any of these hyperplanes.  

Actually we will see in the proof that the exceptional set is nearly a codimension one submanifold, indeed it is a union of finitely (or countably) many codimension one submanifolds.
Proof: Clearly it suffices to assume that there is only one given hyperplane {P}. The conclusion follows by the countable subadditivity of the Hausdorff measure. We can further assume that {P=\{x_n=0\}}.

For {A\in O(n)}, the first column of {A} lies in {P} if and only if {f_1(A):=\langle Ae_1, e_n\rangle=0}. We will show that {S_1=\{A\in O(n): f_1(A)=0\}} is a codimension one smooth submanifold of {O(n)}. Indeed by regular value theorem(a special form of implicit function theorem), it suffices to show that {0} is a regular value of {f_1}. To see this, suppose {A=(v_1, v_2, \cdots, v_n)\in O(n)} such that {f_1(A)=0}, i.e. {\langle v_1, e_n\rangle =0}. Clearly there is one {v_j}, {j\geq 2} such that {\langle v_j, e_n\rangle\neq0} (why), we can w.l.o.g. assume {j=2}. Then

\displaystyle \gamma(t):=(\cos (t) v_1+\sin (t) v_2, -\sin (t) v_1+\cos (t) v_2, v_3, \cdots , v_n)

is a curve in {O(n)} through {A}, and

\displaystyle df_1(\gamma'(0))=\left.\frac{d}{dt}\right|_{t=0}f(\gamma(t))=\langle v_2, e_n\rangle\neq0.

From this we see that {0} is a regular value for {f_1}, and thus {S_1} is a smooth codimension one submanifold of {O(n)}. It follows that {S_1} has {n(n-1)/2} dimensional measure zero. With the same argument we conclude that {\{A\in O(n): \langle Ae_j, e_n\rangle=0 \text{ for some }j=1,\cdots n\}} has {\mu} measure {0}. \Box

This entry was posted in Geometry, Linear Algebra. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s