Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am attempting to calculate the intersection of quadric surfaces defined by $0 = X^T A X$, $0 = X^T B X$, $0 = X^T C X$ with X = [x, y, z, 1]. Matrices A, B and C are real and symmetric.

There are several methods for solving, most of which trace to Levin's Method (e.g. Xu, Wang), or Dupont's rational method with implementation.

Despite it's apparent flaws, I am interested in implementing Levin's method. I am stuck on the one of the steps in the method, where I am required to transform a "pencil" (two intersecting surfaces) into canonical form. The "pencil" is guaranteed to be a ruled surface quadric under the conditions that I am interested in.

So, I need to find some matrix $P$ that transforms $Q_R: X^T R X$ (i.e. quadric of the pencil) into a canonical form. In my specific problem, I know that my ruled surface is a Hyperbolic Paraboloid based on the eigenvalues of the pencil, which has a normal form of $x^2 - y^2 + z$.

That is, find some congruence transform $R = P^T S P$, where R is the pencil, S is the canonical form (which I don't know what it is) and P is the transform I need to find.

This is where I'm stuck. Levin's paper instructs me to firstly calculate a rotation matrix $R_u$ from the principle submatrix of $R$ (i.e. the upper 3x3), which can be achieved via an Eigendecomposition. Easy enough.

Next, however, I need to find a translation matrix $T = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ a & b & c & 1\end{bmatrix}$, which gets me into a canonical form, $P = T R_u$. This is done by "eliminating, by congruence transforms, as many other elements as possible". (At this point, it references a technical report from 1976 that I cannot find for the life of me).

Hence, I would like to ask:

  • What is the canonical form that I need, given that I know the shape of the resultant (a hyperbolic paraboloid)?; and
  • How do I perform the necessary congruence transforms to find my desired $P$?
share|improve this question

1 Answer 1

up vote 0 down vote accepted

It took a while, but I have an answer.

This answer describes the transformation of a hyperbolic paraboloid into canonical form. The procedure is similar for other quadric shapes.

An affine transform $\mathbf{T}$ is of the form: \begin{equation} \mathbf{T} = \begin{bmatrix} T_{11} & T_{12} & T_{13} & T_{14} \\ T_{21} & T_{22} & T_{23} & T_{24} \\ T_{31} & T_{32} & T_{33} & T_{34} \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{equation}

Every quadric may be transformed via affine transformations into either a diagonal matrix or a near diagonal matrix, i.e. \begin{equation} \mathbf{X}^T \mathbf{T}^T \mathbf{A} \mathbf{T} \mathbf{X} = \mathbf{X}^T \mathbf{D} \mathbf{X} \end{equation} where $\mathbf{D}$ is a (near-)diagonal matrix. A near-diagonal matrix is symmetric and is of the form: \begin{equation} \mathbf{D} = \begin{bmatrix} D_{11} & 0 & 0 & 0 \\ 0 & D_{22} & 0 & 0 \\ 0 & 0 & 0 & D_{43} \\ 0 & 0 & D_{43} & 0 \end{bmatrix} \end{equation}

The canonical form of a hyperbolic paraboloid listed in Xu (Table 1, pp518) is not strictly in near-diagonal form: \begin{align} 0 &= z - xy \\ &= \mathbf{X}^T \mathbf{D'} \mathbf{X} \\ &= \mathbf{X}^T \begin{bmatrix} 0 & -0.5 & 0 & 0 \\ -0.5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.5 \\ 0 & 0 & 0.5 & 0 \end{bmatrix} \mathbf{X} \end{align} but may be re-written in near-diagonal form as: \begin{align} 0 &= -x^2 + y^2 + z \\ &= \mathbf{X}^T \mathbf{D} \mathbf{X} \\ &= \mathbf{X}^T \begin{bmatrix} -1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0.5 \\ 0 & 0 & 0.5 & 0 \end{bmatrix} \mathbf{X} \end{align}

The Xu form $\mathbf{D'}$ and the near-diagonal form $\mathbf{D}$ are related via an affine transform: \begin{align} \mathbf{D'} = \mathbf{M}^T \mathbf{D} \mathbf{M} \end{align} where: \begin{equation} \mathbf{M} = \begin{bmatrix} 0.5 & -0.5 & 0 & 0 \\ 0.5 & 0.5 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \end{equation}

Since the Xu's canonical form can be found from the near-diagonal form, our immediate task is to find the transformation $\mathbf{T}$ that casts a given hyperbolic paraboloid $\mathbf{A}$ into near-diagonal form. Although Dupont recommends determining the transform via Gaussian Reductions to avoid radicals, perhaps the easiest first step is to remove the rotation via an Eigendecomposition as suggested by Levin.

Consider the principle submatrix $\mathbf{A}_u$. Since it is symmetric, of rank 2 and has known signs for the eigenvalues, an eigendecomposition may be found such that \begin{align} \mathbf{A}_u = {\mathbf{R}_u}^T \mathbf{\Lambda} \mathbf{R}_u \end{align} where $\mathbf{R} \in SO(3)$ and $\mathbf{\Lambda}$ is in the form: \begin{equation} \mathbf{\Lambda} = \begin{bmatrix} \lambda_+ & 0 & 0 \\ 0 & \lambda_- & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \end{equation} where $\lambda_+ > 0$ and $\lambda_- < 0$. Therefore, the first affine transform may be built as: \begin{align} \mathbf{T}_1 = \begin{bmatrix} \mathbf{R}_u & \mathbf{0} \\ \mathbf{0} & 1 \end{bmatrix} \end{align}

The second transform forces the eigenvalues to unit magnitude and it can be verified that: \begin{align} \mathbf{T}_2 = \begin{bmatrix} \frac{1}{\sqrt{\lambda_+}} & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{\|\lambda_-\|}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \end{align}

Let $\mathbf{A}_2 = {\mathbf{T}_2}^T {\mathbf{T}_1}^T \mathbf{A} \mathbf{T}_1 \mathbf{T}_2$, which will be of the form: \begin{equation} \mathbf{A}_2 = \begin{bmatrix} 1 & 0 & 0 & a \\ 0 & -1 & 0 & b \\ 0 & 0 & 0 & c \\ a & b & c & d \end{bmatrix} \end{equation}

It can be verified that the transform required to cast into near-diagonal form is: \begin{equation} \mathbf{T}_3 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \frac{-a}{c} & \frac{-a}{b} & \frac{-1}{2c} & \frac{-d}{2c} \\ 0 & 0 & 0 & 1 \end{bmatrix} \end{equation}

Therefore, the complete transformation required to cast the hyperbolic paraboloid into Xu's canonical form is: \begin{align} \mathbf{T} = \mathbf{T}_1 \mathbf{T}_2 \mathbf{T}_3 \mathbf{M} \end{align}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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