What is the relation between these two definitions of an ellipsoid

Question

There are two definitions of an ellipsoid in Boyd's book (Convex Optimization)

1. $E = \{ x | (x-x_c)^T P (x-x_c) \leq 1 \}$

In the above, P is a positive semi definite matrix.

2. $ E=\{ x_c+Au |\; ||u|| \leq 1 \}$

In the second definition, $A$ is non-singular.

I have certain questions about the above definitions.

1. Why is positive definite required for the first case? what if $P$ is not positive semi definite?
2. I know that non-singularity is required for $A$, otherwise ellipsoid dimensionality would reduce. I want to know that what is the relation between these two definitions. Is there any relation between $A$ and $P$?

Answer 1

I'll consider only vector spaces over $\mathbb R^n$ if that's OK.

Since $A$ is non-singular, $A^{-1}$ exists and is non-singular. So $x = Au + x_c$ is equivalent to $u = A^{-1}(x - x_c)$, and we can rewrite the second definition as follows:

$$ E = \{ x \mid \|A^{-1}(x - x_c)\| \leq 1 \}.$$

But $\|A^{-1}(x - x_c)\| = (x - x_c)^T \left(A^{-1}\right)^T A^{-1}(x - x_c)$, and since $A^{-1}$ is non-singular, $\left(A^{-1}\right)^T A^{-1}$ is positive definite.

In fact, if we let $P = \left(A^{-1}\right)^T A^{-1}$, then $P$ is the positive definite matrix you need for the first definition: $(x - x_c)^T P (x - x_c) = \|u\|$ where $u = A^{-1}(x - x_c)$, hence the set of $x$ such that $(x - x_c)^T P (x - x_c) \leq 1$ is just the set of $x = Au + x_c$ such that $\|u\| \leq 1$.

Answer 2

The condition that $P$ be positive definite, is equivalent to saying that all of it's eigen values are positive. This means, that if you take the eigendecomposition, $P= U^{-1}DU$, where $D$ is a diagonal matrix and $U$ unitary, $D$ will have only positive values.

If you think of the unitary $U$ as a combination of rotation and stretching, you see that your first equation reduces to taking an axis aligned ellipsoid $\sum a_i x_i^2 \le 1,\ a_i > 0$, and then rotating and stretching it.

If $P$ is not positive definite, then some of the values of $D$ will be negative, leading to a hyperbola or some other shape (e.g. $x^2-y^2 =1$).