In chapter 2 section 2.2.2 of Boyd & Vandenberghe's Convex Optimization, the definition of an ellipsoid (which is a convex set) is given as the

$$ \mathcal{E} = \left\{x \mid (x - x_c)^{\intercal} P^{-1} (x - x_c) \le 1 \right\} $$

where $P = P^\intercal $ is symmetric and positive definite and $x_c$ is the center.

If we restrict to real matrices, the way I understand is:

Symmetric real matrices are always diagonalizable, so $P = RSR^\intercal$ where $R$ is an orthogonal matrix (rotation) with eigenvectors in the columns, and $S$ is a scaling matrix composed of the eigenvalues in the diagonals.

So if we multiply all points in the ellipsoid by the inverse of $P$, we get a circle (by undoing the rotation and scaling). And the condition for a point $x$ to be in the sphere with center $x_c$ is that the squared length of $(x - x_c) \le 1$. All in all, $x$ should be a point in the ellipsoid if

$$ x'^\intercal x' \le 1 $$

where $$ x' = P^{-1}(x - x_c) $$

What am I missing?


Note that $(AB)^T = B^TA^T$. So $x'^T = (x - x_c)^T(P^{-1})^T$. Thus the correct formula must be

$$(x - x_c)^T(P^{-1})^TP^{-1}(x - x_c) \leq 1$$

But notice that there's no reason you had to call that first matrix $P$. Instead, let's call $P$ the inverse of that matrix in the middle - so what was "$(P^{-1})^TP^{-1}$" is now just called "$P^{-1}$".

That also explains why $P$ has to be positive-definite!

  • $\begingroup$ I see. This made me the look up the "A = R^T R" definition of positive definite matrices. Thanks. $\endgroup$
    – slnsoumik
    Aug 23 '20 at 5:19

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.