Use QR factorizations to find intersection of two planes

360 Views Asked by At

This question is Problem $7.4$ in Numerical Linear Algebra by Lloyd N. Trefethen and David Bau, III.

Problem $7.4$: Let $\newcommand{\1}{^{(1)}} \newcommand{\2}{^{(2)}} \newcommand{\ip}[1]{\left \langle #1 \right \rangle} x\1,y\1,x\2,$ and $y\2$ be nonzero vectors in $\mathbb{R}^3$ with the property that $x\1$ and $y\1$ are linearly independent and so are $x\2$ and $y\2$. Consider the two planes in $\mathbb{R}^3$, $$ P\1 = \ip{x\1,y\1} \qquad P\2 = \ip{x\2,y\2} $$ Suppose we wish to find a nonzero vector $v \in \mathbb{R}^3$ which lies in the intersection of the planes, $P = P\1 \cap P\2$, the intersection of the planes. Devise a method for solving this problem by reducing it to the computation of the QR factorizations of three $3 \times 2$ matrices.

I can numerically compute the $QR$ factorization but I don't see how I could find the three matrices and how that would help me find the intersection of $P^{(1)}$ and $P^{(2)}$.

1

There are 1 best solutions below

0
On

Consider matrices $\newcommand{\nc}{\newcommand} \nc{\para}[1]{\left( #1 \right)} \nc{\abs}[1]{\left| #1 \right|} \nc{\br}[1]{\left[ #1 \right]} \nc{\set}[1]{\left\{ #1 \right\}} \nc{\ip}[1]{\left \langle #1 \right \rangle} \nc{\n}[1]{\left\| #1 \right\|} \nc{\norm}[1]{\left\| #1 \right\|} \nc{\floor}[1]{\left \lfloor #1 \right \rfloor} \nc{\ceil}[1]{\left \lceil #1 \right \rceil} \nc{\setb}[2]{\set{#1 \, \middle| \, #2}} \nc{\dd}{\mathrm{d}} \nc{\dv}[2]{\frac{\dd #1}{\dd #2}} \nc{\p}{\partial} \nc{\pdv}[2]{\frac{\partial #1}{\partial #2}} \nc{\a}{\alpha} \nc{\b}{\beta} \nc{\g}{\gamma} \nc{\d}{\delta} \nc{\ve}{\varepsilon} \nc{\t}{\theta} \nc{\m}[1]{\begin{bmatrix} #1 \end{bmatrix}} \nc{\C}{\mathbb{C}} \nc{\N}{\mathbb{N}} \nc{\R}{\mathbb{R}} \nc{\P}{\mathbb{P}} \nc{\Q}{\mathbb{Q}} \nc{\Z}{\mathbb{Z}} \nc{\AA}{\mathcal{A}} \nc{\BB}{\mathcal{B}} \nc{\CC}{\mathcal{C}} \nc{\FF}{\mathcal{F}} \nc{\GG}{\mathcal{G}} \nc{\II}{\mathcal{I}} \nc{\JJ}{\mathcal{J}} \nc{\KK}{\mathcal{K}} \nc{\PP}{\mathcal{P}} \nc{\RR}{\mathcal{R}} \nc{\SS}{\mathcal{S}} \nc{\TT}{\mathcal{T}} \nc{\1}{^{(1)}} \nc{\2}{^{(2)}} \nc{\i}{^{(i)}} M\1,M\2$ where $$ M\i := \br{ x\i \, \middle| \, y\i } $$ and generate corresponding full QR factorizations $M\i = Q\i R\i$.

Recall that $M\i \in \C^{3 \times 2}$, so in the QR factorization, for $Q\i$ to be square, it needs to be "padded out" with an additional column (one that is missing from the other two one would find in the reduced QR factorization via, say, Gram-Schmidt).

Call this extra column $q\i$. By the orthogonality of the other two, it holds that $q\i \perp P\i$. Form a new matrix, $$ \widetilde{M} := \br{ q\1 \, \middle| \, q\2 } $$ Each column is a unit normal for its respective plane. Of course, this matrix also has a full QR factorization, $\widetilde{M} = \widetilde{Q} \widetilde{R}$. If a vector $v$ lies in $P\1 \cap P\2$, it must be perpendicular to the normals of both planes, to the first two columns of $\widetilde{Q}$.

It is then easy to see that the line containing $v$ must be perpendicular to those columns - hence, in the span of third column of $\widetilde{Q}$.