Given $n$ points in $n$-dimensions, using MatLab, how should we find the equation of the $(n-1)$-dimensional hyperplane passing through these $n$ points.
[Math] Equation of hyperplane in Matlab
computational geometrygeometrylinear algebraMATLAB
Related Solutions
You want a normal vector rather than "tangent vector." You make an $(n-1)$ by $n$ matrix with row $i$ given by $x_i - x_n.$ Then the normal vector is the null space of this matrix. The fast way to do this is Gauss elimination, but it can also be done as a recipe by pretending the matrix is square, and find the entries of the proper column of the adjoint matrix, given by cofactors with certain $\pm$ signs. The traditional cross product is often taught this way in physics classes.
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.
Best Answer
Let the given points be $$ p_1 = \left[\begin{matrix} p_{11} \\ p_{12} \\ \vdots \\ p_{1n} \end{matrix}\right] \quad\text{,}\quad p_2 = \left[\begin{matrix} p_{21} \\ p_{22} \\ \vdots \\ p_{2n} \end{matrix}\right] \quad\text{,}\quad \dots \quad\text{,}\quad p_n = \left[\begin{matrix} p_{n1} \\ p_{n2} \\ \vdots \\ p_{nn} \end{matrix}\right] $$ You want to find $a_1,\dotsc,a_n,c$ such that the equation $$ a_1 x_1 + \dotsc + a_n x_n = c $$ is satisfied by all the $p_i$. In other words, you want the $a_i$ and $c$ to be a solution of $$ \left[\begin{matrix} p_{11} & p_{12} & \dots & p_{1n} & -1 \\ p_{21} & p_{22} & \dots & p_{2n} & -1 \\ & \vdots \\ p_{n1} & p_{n2} & \dots & p_{nn} & -1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_n \\ c \end{matrix}\right] = \left[\begin{matrix} 0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{matrix}\right] $$ So, tell Matlab to solve that system... however you tell Matlab to do such things.