I have a question regarding the computation of a hyperplane equation (especially the orthogonal) given n points, where n>3.
For lower dimensional cases, the computation is done as in :
http://tutorial.math.lamar.edu/Classes/CalcIII/EqnsOfPlanes.aspx
Here we simply use the cross product for determining the orthogonal. However, best of our knowledge the cross product computation via determinants is limited to dimension 7 (?).
How to get the orthogonal to compute the hessian normal form in higher dimensions?
Thank you in advance for any hints and
with best regards
Dan
Best Answer
The method of using a cross product to compute a normal to a plane in 3-D generalizes to higher dimensions via a generalized cross product: subtract the coordinates of one of the points from all of the others and then compute their generalized cross product to get a normal to the hyperplane. Once you have that, an implicit Cartesian equation for the hyperplane can then be obtained via the point-normal form $\mathbf n\cdot(\mathbf x-\mathbf x_0)=0$, for which you can take any of the given points as $\mathbf x_0$. If the cross product vanishes, then there are linear dependencies among the points and the solution is not unique. (Note that this is Cramer’s Rule for solving systems of linear equations in disguise.)
For example, given the points $(4,0,-1,0)$, $(1,2,3,-1)$, $(0,-1,2,0)$ and $(-1,1,-1,1)$, subtract, say, the last one from the first three to get $(5, -1, 0, -1)$, $(2, 1, 4, -2)$ and $(1, -2, 3, -1)$ and then compute the determinant $$\det\begin{bmatrix}5&-1&0&-1\\2&1&4&-2\\1&-2&3&-1\\\mathbf e_1&\mathbf e_2&\mathbf e_3&\mathbf e_4\end{bmatrix} = (13, 8, 20, 57).$$ An equation of the hyperplane is therefore $(13,8,20,57)\cdot(x_1+1,x_2-1,x_3+1,x_4-1)=0$, or $13x_1+8x_2+20x_3+57x_4=32$.
An equivalent method uses homogeneous coordinates. In homogeneous coordinates every point $\mathbf p$ on a hyperplane satisfies the equation $\mathbf h\cdot\mathbf p=0$ for some fixed homogeneous vector $\mathbf h$. The components of this vector are simply the coefficients in the implicit Cartesian equation of the hyperplane. So, given $n$ points on the hyperplane, $\mathbf h$ must be a null vector of the matrix $$\begin{bmatrix}\mathbf p_1^T \\ \mathbf p_2^T \\ \vdots \\ \mathbf p_n^T\end{bmatrix}.$$ The null space of this matrix can be found by the usual methods such as Gaussian elimination, although for large matrices computing the SVD can be more efficient. If the null space is not one-dimensional, then there are linear dependencies among the given points and the solution is not unique. This is where this method can be superior to the cross-product method: the latter only tells you that there’s not a unique solution; this one gives you all solutions.
Using the same points as before, form the matrix $$\begin{bmatrix}4&0&-1&0&1 \\ 1&2&3&-1&1 \\ 0&-1&2&0&1 \\ -1&1&-1&1&1 \end{bmatrix}$$ (the extra column of $1$s comes from homogenizing the coordinates) and row-reduce it to $$\begin{bmatrix} 1 & 0 & 0 & 0 & \frac{13}{32} \\ 0 & 1 & 0 & 0 & \frac{1}{4} \\ 0 & 0 & 1 & 0 & \frac{5}{8} \\ 0 & 0 & 0 & 1 & \frac{57}{32} \\ \end{bmatrix}.$$ The null space is therefore spanned by $(13,8,20,57,-32)^T$, and so an equation of the hyperplane is $13x_1+8x_2+20x_3+57x_4=32$ as before.
In fact, you can write the equation itself in the form of a determinant. Adding any point on the plane to the set of defining points makes the set linearly dependent. The determinant of a matrix vanishes iff its rows or columns are linearly dependent. Therefore, given $n$ linearly-independent points an equation of the hyperplane they define is $$\det\begin{bmatrix} x_1&x_2&\cdots&x_n&1 \\ x_{11}&x_{12}&\cdots&x_{1n}&1 \\ \vdots&\vdots&\ddots&\vdots \\x_{n1}&x_{n2}&\cdots&x_{nn}&1 \end{bmatrix} = 0,$$ where the $x_{ij}$ are the coordinates of the given points. This determinant method is applicable to a wide class of hypersurfaces.