0
$\begingroup$

Motivating question: Suppose I have a plane $P = \{(x,y,z)\in \textbf{R}^3\ :\ Ax+By+Cz+D = 0\}$, for some real numbers $A,B,C,D$, and three non-colinear points $p_1,p_2,p_3$ also in $\textbf{R}^3$. Is there a canonical way that I can define an orthogonal coordinate system on this plane and know where the $p_i$ lie on it?

Idea so far: I can let $p_1$ be the "origin" of this system, and let $p_2$ be at position $(d(p_1,p_2),0)$, where distance is measured as in $\textbf{R}^3$. For $p_3$, calculate its projection onto the vector $\overline{p_1p_2}$, and the distance $d_1$ to that projection from $p_1$. Then let $p_3$ lie at $(\pm d_1,\pm\sqrt{d(p_1,p_3)^2-d_1^2})$ on this new system ($\pm$ because I've only calculated the distance, not the direction). This works (up to signs), but doesn't seem too natural to me.

Actual problem: Suppose I have a $k$-plane $$ P = \left\{(x_1,\dots,x_n)\ :\ \sum_{i=1}^n A_{1,i}x_i + D_1 = 0,\dots,\sum_{i=1}^nA_{n-k,i}x_i + D_{n-k} = 0\right\} $$ and $k+1$ points $p_1,\dots,p_{k+1}$ in general position in $\textbf{R}^{n>k}$. Is there a canonical way I can define a orthogonal coordinate system on this $k$-plane and know where the $p_i$ lie on it?

Ideas so far: Let $p_1$ be again the "origin" of this system, and $p_2$ at position $(d(p_1,p_2),0,\dots,0)$. But where do I put $p_2$? Initially I thought it would be easiest to place the first $k-1$ points, on the axes of the new coordinate system, corresponding to the "degrees of freedom" in some sense, but I couldn't convince myself this works in $n=4$.


I'm guessing this is probably a simple problem something to do with projections or Gram-Schmidt, and I just haven't learned it / have forgot it / can't explain it clearly, so I would be glad for any suggestions on how to make the generalization work. The key part is that I need to know the coordinates of my original points $p_i$ in this new orthogonal system. Also, these $k+1$ points uniquely define this $k$-plane, so maybe I'm doing too many steps.

$\endgroup$

1 Answer 1

2
$\begingroup$

I’m not sure that there’s any particular coordinate system for $P$ that could be called “canonical.” If you have the defining equations for $P$, then you can build a coordinate system directly from them. For any $p,q\in P$, $p-q$ lies in the solution space $P'$ of the related homogeneous system of linear equations $\sum_iA_{1,i}x_k=0,\dots,\sum_iA_{k,i}x_i=0$, which is parallel to $P$ but passes through the origin. So, compute a basis for the kernel (null space) of the coefficient matrix $A$ of this system. If you need an orthonormal basis, apply the Gram-Schmidt process. If you only need it to be orthogonal, you can leave the resulting vectors unnormalized. Choosing any point $p_0\in P$ then gives you a coordinate system on $P$.

If, on the other hand, you want to build the coordinate system from some set of $k$ points, then the basic process you describe certainly works. Choose one of them, say $p_1$, to be the origin. The first basis vector is then $v_1=p_2-p_1$, normalized or not, as you like. The next basis vector will be the orthogonal rejection of $(p_3-p_1)$ from $v_1$, i.e., $v_2=(p_3-p_1)-{(p_3-p_1)\cdot v_1\over v_1\cdot v_1}v_1$, again, normalize or not as you see fit. The next basis vector $v_3$ will be the orthogonal rejection of $(p_4-p_1)$ from the span of these vectors, and so on. At each stage, you’ll be computing $v_i=(p_{i+1}-p_1)-\sum_{j=1}^{i-1}{(p_{i+1}-p_1)\cdot v_j\over v_j\cdot v_j}v_j$. Continue until you have $k$ basis vectors. If you ever get zero, the given set of points has a dependency and doesn’t actually define a $k$-plane. If you’re simply starting from a set of points and don’t really care about the dimension of their $m$-plane that they lie in, just throw that one out and keep going until you’ve processed all of the points.

You’ve now got a basis $\{v_i\}$ for $P'$. Recall that, by definition, the coordinates of a vector are the coefficients in its expression as a linear combination of basis vectors. So, to find the $P$-coordinates of a point $p\in P$, solve the equation $p-p_0=\sum_{i=1}^ka_iv_i$ for the unknown coefficients $a_i$. If there’s no solution, then $p\notin P$, of course. This can be done en masse by forming the matrix $B$ that has the $v_i$ as its columns, augmenting it with all of the points shifted by $p_0$, and row-reducing. The $P$-coordinates will be in the first $k$ rows. Alternatively, form the pseudo-inverse $(B^TB)^{-1}B^T$ and apply it to the shifted points, which can also be done in bulk. If the basis is orthogonal, the pseudo-inverse is particularly easy to compute: the $i$th row is $v_i/(v_i\cdot v_i)$. A disadvantage of this latter method is that it will happily assign $P$-coordinates to points that aren’t in $P$ (which might be an advantage if your data aren’t exact).

For example, let $P$ be defined by the equations $$\begin{align}x_1+x_3+2x_4&=12\\2x_1-x_2-x_4&=-4\end{align}$$ and points on this plane $p_1=(1,2,3,4)^T$, $p_2=(2,4,2,4)^T$ and $p_3=(4,9,2,3)^T$. Then $$A=\pmatrix{1&0&1&2\\2&-1&0&-1}$$ with kernel spanned by $(1,2,-1,0)^T$ and $(2,5,0,-1)^T$, which is easily found by row-reduction. We keep the first of these vectors for our kernel basis and take the orthogonal rejection of the second for the other basis vector: $$(2,5,0,-1)^T-{(2,5,0,-1)^T\cdot(1,2,-1,0)^T\over(1,2,-1,0)^T\cdot(1,2,-1,0)^T}(1,2,-1,0)^T=(0,1,2,-1)^T.$$ Taking $p_1$ as our origin, we form the matrix $$\left(\begin{array}{rr|rrr}1&0&1&3&2\\2&1&2&7&2\\-1&2&-1&-1&-1\\0&-1&0&-1&0\end{array}\right)$$ (I’ve thrown in a bogus point to illustrate error detection). Row-reduction yields $$\left(\begin{array}{rr|rrr}1&0&1&3&2\\0&1&0&1&-2\\0&0&0&0&5\\0&0&0&0&-2\end{array}\right)$$ and so the $P$-coordinates of $p_2$ are $B(p_2-p_1)=(1,0)^T$ and the $P$-coordinates of $p_3$ are $(p_3-p_1)=(3,1)^T$. The last column shows correctly that the third point was bogus.

For the pseudo-inverse, we have $$(B^TB)^{-1}B^T=\frac16\pmatrix{1&2&-1&0\\0&1&2&-1}$$ and applying it to the above shifted points produces $$\pmatrix{1&3&\frac76\\0&1&0}.$$ The first two columns agree with the previous result, but for the point not on our plane we’ve produced the coordinates of the point on the plane closest to it.

Starting from the given points instead, we have $v_1=p_2-p_1=(1,2,-1,0)^T$. Next, we compute $p_3-p_1=(3,7,-1,-1)^T$, and its orthogonal rejection from $v_1$ is $$(3,7,-1,-1)^T-{(3,7,-1,-1)^T\cdot(1,2,-1,0)^T\over(1,2,-1,0)^T\cdot(1,2,-1,0)^T}(1,2,-1,0)^T=(0,1,2,-1)^T.$$ This is, not coincidentally because of the way I derived the points for this example, the same as the above basis for $\ker A$, so the rest of the calculation proceeds as before.

$\endgroup$
3
  • $\begingroup$ As a final note, by constructing an oblique projection, you can fold translation to the origin point on $P$ into the psuedo-inverse matrix, but it’s a lot more work than explicitly offsetting the points. $\endgroup$
    – amd
    Jan 17, 2017 at 3:39
  • $\begingroup$ Thank you for your detailed answer (and apologies for the late reply)! Since my goal was to automate this process through Sage for a larger project (finding the radius of the unique sphere through these points, crudely implemented here), I used QR-decomposition to skip the manual Gram-Schmidt process, and completed a basis for the ambient space by adding standard basis vectors. But the idea is the same - normalize by subtracting the first vector from all, Gram-Schmidt, make change-of-basis matrix, apply to shifted vectors, take first $k$ coordinates. $\endgroup$ Jan 24, 2017 at 2:13
  • $\begingroup$ Edit to my comment above: I don't even need to complete the basis, QR-decomposition works for non-square matrices. Oops. $\endgroup$ Jan 24, 2017 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .