I want to find out the intersection of two surfaces that exist in $n$-dimensions. These surfaces are defined by a system of $2$ linear equations.

$$A_1x+B_1y+C_1z+\cdots = D_1$$

$$A_2x+B_2y+C_2z+\cdots = D_2$$

But first, how would these surfaces look like? In $3$-D space, they would be planes, but in dimensions higher than $3$ are these not planes? Can we generalize a way to find the intersection of such linear expressions in some way?

Also can this problem be solved using some tools, preferably Matlab?

  • 2
    $\begingroup$ The surfaces are hyperplanes. Solve a linear system of the form $\rm A x = b$, where $\rm A$ is a $2 \times n$ matrix. If $n > 2$, the linear system is underdetermined. If $n=3$, the intersection could be a line. If $n=4$, the intersection could be a $2$-dimensional plane. $\endgroup$ – Rodrigo de Azevedo Jul 16 '17 at 15:27
  • 1
    $\begingroup$ You can use Gaussian elimination to find a parametrization of the affine space that is the intersection, assuming that the intersection is not empty. $\endgroup$ – Rodrigo de Azevedo Jul 16 '17 at 15:31
  • 1
    $\begingroup$ @RodrigodeAzevedo And how do I figure out t1 and t2? $\endgroup$ – Vidor Vistrom Jul 16 '17 at 15:44
  • 2
    $\begingroup$ Suppose we have $$\begin{bmatrix} 1 & 0 & -1 & -1\\ 0 & 1 & -1 & -1\end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\end{bmatrix} = \begin{bmatrix} 1\\ 1\end{bmatrix}$$ The solution set is the plane parameterized as follows $$\left\{ \begin{bmatrix} 1\\ 1\\ 0\\ 0\end{bmatrix} + t_1 \begin{bmatrix} 1\\ 1\\ 1\\ 0\end{bmatrix} + t_2 \begin{bmatrix} 1\\ 1\\ 0\\ 1\end{bmatrix} : t_1, t_2 \in \mathbb R \right\}$$ $\endgroup$ – Rodrigo de Azevedo Jul 16 '17 at 15:48
  • 2
    $\begingroup$ @RodrigodeAzevedo: I suggest that you post your solution, perhaps mentioning the reduced row-echelon form of the augmented matrix for the $2\times n$ system, as an Answer. I will certainly upvote even if you mostly transcribe your Comments into the Answer box. $\endgroup$ – hardmath Jul 16 '17 at 21:49

Suppose we would like to find the intersection of $2$ hyperplanes in $\mathbb R^n$

$$\begin{array}{rl} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n &= b_1\\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n &= b_2\end{array}$$

In matrix form,

$$\begin{bmatrix} — \mathrm a_1^\top —\\ — \mathrm a_2^\top —\end{bmatrix} \mathrm x = \begin{bmatrix} b_1\\ b_2\end{bmatrix}$$

or, more economically, $\rm A x = b$, where $\rm A$ is a $2 \times n$ matrix. Without loss of generality, we assume that both hyperplanes are in Hessian normal form, i.e., $\| \mathrm a_1 \|_2 = \| \mathrm a_2 \|_2 = 1$.

If vectors $\rm a_1$ and $\rm a_2$ are collinear, then the $2$ given hyperplanes are either parallel or overlapping, neither of which are very interesting. Thus, we assume that vectors $\rm a_1$ and $\rm a_2$ are not collinear, i.e., matrix $\rm A$ has full row rank. Let $\theta := \arccos ( \mathrm a_1^\top \mathrm a_2 )$ be the angle formed by vectors $\rm a_1$ and $\rm a_2$.

The solution set of the linear system $\rm A x = b$ is a $(n-2)$-dimensional affine space. To find this affine space, we must find a particular solution and the null space of $\rm A$. One particular solution would be the least-norm solution, i.e., the one closest to the origin

$$\begin{array}{rl} \mathrm x_{\text{LN}} := \mathrm A^\top \left( \mathrm A \mathrm A^\top \right)^{-1} \mathrm b &= \begin{bmatrix} | & | \\ \mathrm a_1 & \mathrm a_2\\ | & |\end{bmatrix} \begin{bmatrix} \| \mathrm a_1 \|_2^2 & \langle \mathrm a_1, \mathrm a_2 \rangle\\ \langle \mathrm a_2, \mathrm a_1 \rangle & \| \mathrm a_2 \|_2^2\end{bmatrix}^{-1} \begin{bmatrix} b_1\\ b_2\end{bmatrix}\\ &= \begin{bmatrix} | & | \\ \mathrm a_1 & \mathrm a_2\\ | & |\end{bmatrix} \begin{bmatrix} 1 & \cos (\theta)\\ \cos (\theta) & 1\end{bmatrix}^{-1} \begin{bmatrix} b_1\\ b_2\end{bmatrix}\\ &= \frac{1}{\sin^2 (\theta)} \begin{bmatrix} | & | \\ \mathrm a_1 & \mathrm a_2\\ | & |\end{bmatrix} \begin{bmatrix} 1 & -\cos (\theta)\\ -\cos (\theta) & 1\end{bmatrix} \begin{bmatrix} b_1\\ b_2\end{bmatrix}\\ &= \left(\frac{b_1 - b_2 \cos (\theta)}{\sin^2 (\theta)}\right) \begin{bmatrix} | \\ \mathrm a_1 \\ | \end{bmatrix} + \left(\frac{b_2 - b_1 \cos (\theta)}{\sin^2 (\theta)}\right) \begin{bmatrix} | \\ \mathrm a_2 \\ | \end{bmatrix}\end{array}$$

where $\sin (\theta) \neq 0$ is ensured by the non-collinearity of vectors $\rm a_1$ and $\rm a_2$.

To find the $(n-2)$-dimensional null space of $\rm A$, we solve the homogeneous linear system $\rm A x = 0_2$. Introducing an $n \times n$ permutation matrix $\rm P$ with certain desired properties, we reorder the columns of $\rm A$, i.e., $\rm A P P^\top x = 0_2$, and obtain a homogeneous linear system in $\rm y:= P^\top x$

$$\rm A P y = 0_2$$

If $\rm P$ is chosen wisely, then there is a $2 \times 2$ matrix $\rm E$, a product of elimination matrices, that puts $\rm A P$ in reduced row echelon form (RREF), i.e.,

$$\rm E A P = \begin{bmatrix} \mathrm I_2 & \mathrm F\end{bmatrix}$$

where $\rm F$ is a $2 \times (n-2)$ matrix. Hence, the null space of $\rm A P$ is given by

$$\left\{ \begin{bmatrix} -\mathrm F \\ \mathrm I_{n-2} \end{bmatrix} \eta : \eta \in \mathbb R^{n-2} \right\}$$

and, thus, the null space of $\rm A$ is given by

$$\left\{ \mathrm P \begin{bmatrix} -\mathrm F \\ \mathrm I_{n-2} \end{bmatrix} \eta : \eta \in \mathbb R^{n-2} \right\}$$

Lastly, the intersection of the $2$ given hyperplanes is given by

$$\left\{ \color{blue}{\mathrm x_{\text{LN}} + \mathrm P \begin{bmatrix} -\mathrm F \\ \mathrm I_{n-2} \end{bmatrix} \eta} : \eta \in \mathbb R^{n-2} \right\}$$

In MATLAB, we can use function rref to find permutation matrix $\rm P$ and matrix $\rm F$. Of course, we can also use function null to find an orthonormal basis for the null space of $\rm A$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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