numeric solutions on quadric surfaces

Question

Maybe it's a trivial thing, but I can't seem to find solution I'm looking for. I need to find a parametric solution to the following equation ($\mathbf{A}$ is positive definite):

$$ \mathbf{x}^T\mathbf{A}\mathbf{x}+\mathbf{b}^T\mathbf{x}+c=0 $$

How to find $x$, then, in some parametric form? That is, I want to generate some $n-1$ dimensional parameter (something like spherical coördinates) and get one of the solutions in the original space.

Answer 1

Well you can factor the problem by completing the square as follows, \begin{align} x^T A x + b^T x + c &= (x^T A x + b^T x + \frac{b^TA^{-1}b}{4}) + c - \frac{b^TA^{-1}b}{4} \\ &= (x^T A^{1/2} + \frac{1}{2}b^T A^{-1/2})(A^{1/2} x + \frac{1}{2}A^{-1/2} b) + c - \frac{b^TA^{-1}b}{4} \\ &= (x + \frac{1}{2}A^{-1} b)^T A (x + \frac{1}{2}A^{-1} b) + c - \frac{b^TA^{-1}b}{4}, \end{align}

or $$x^T A x + b^T x + c = (x-p)^T A (x-p) - q$$ where $p := -\frac{1}{2}A^{-1} b$ and $q := \frac{b^TA^{-1}b}{4} - c$. So, an equivalent formulation of your equation is, $$(x-p)^T A (x-p) = q.$$

So, the solution set is an ellipsoid centered at $p$ with axes given by the singular vectors $u_i$ of $A$ and axis lengths $\frac{\sqrt{q}}{\sigma_i}$.

Edit: from the comment below for completeness, a numerical scheme for drawing samples from the solution set is,

1. Draw a collection of gaussian random vectors and put them as the columns of the matrix $X$.
2. Normalize the columns of $X$ to have length $\sqrt{q}$.
3. Compute a collection of random points on the ellipse as $S = A^{-1/2} X + p \mathbb{1}^T$ ($\mathbb{1}^T$ is the vector of all ones).