Intersection of an ellipsoid with a plane

Question

Let $P\in\mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. The question is what is the biggest value $C$ such that $$x^\top P x \le C \Rightarrow x_1^2 \le c_x$$ for all $x\in\mathbb{R}^n$, where $x_1$ is the first element of $x$ and $c_x>0$ is a constant.

As far as I understand, it means that I am looking for such $C$ that the ellipsoid $x^\top P x = C$ touches the plane $x_1=\sqrt{c_x}$, right? I can write that the maximum value of $x^\top P x$ is $\lambda_M|x|^2$, where $\lambda_M$ is the maximum eigenvalue of $P$. Then for $C=\frac{c_x}{\lambda_M}$ we have that for all $x$ $$ x^\top P x \le C \Rightarrow |x|^2 \le c_x \Rightarrow x_1^2 \le c_x,$$ but this $C$ seems to be conservative. How to find the largest value of $C$?

Answer 1

Use Lagrange Multipliers. If you want to maximize $x_1$ with $\vec x^tP\vec x=1$, then form

$$L=x_1+\lambda (\vec x^tP\vec x-1)$$ Differentiate it. Let $\vec v=(1,0,0,...,0)^t$, and you get

$$\vec v+2\lambda P\vec x=0\\ x=-\frac1{2\lambda} P^{-1}v$$

So the point with the highest $x_1$ is in the direction $P^{-1}\vec v$ from the origin. Put in your constants to find the right multiple of $P^{-1}\vec v$, then $x_1=\vec v^t\vec x$.

Answer 2

Working in homogeneous coordinates, the hyperplane $x_1=\sqrt{c_x}$ can be represented by the vector $\mathbf\pi = \left(\mathbf e_1^T, -\sqrt{c_x}\right)^T$. It is tangent to the quadric with matrix $Q$ iff it satisfies the dual conic equation $\mathbf\pi^TQ^*\mathbf\pi=0$. Here, $Q^*$ is the dual quadric matrix, which for a nondegenerate quadric is a nonzero multiple of $Q^{-1}$. For your ellipsoid, this equation expands in block form into $$\begin{bmatrix}\mathbf e_1^T&-\sqrt{c_x}\end{bmatrix} \begin{bmatrix}P^{-1} & \mathbf 0 \\ \mathbf 0^T & -\frac1C\end{bmatrix}\begin{bmatrix}\mathbf e_1\\-\sqrt{c_x}\end{bmatrix} = \mathbf e_1^TP^{-1}\mathbf e_1-{c_x\over C} = [P^{-1}]_{(1,1)}-{c_x\over C}=0$$ from which $$C = {c_x \over [P^{-1}]_{(1,1)}}.$$ Since $P^{-1}=\operatorname{cof}P/\det P$, this can be computed as $$C = {\det P \over P_{1,1}}c_x,$$ where $P_{1,1}$ stands for the $(1,1)$ minor of $P$. To be thorough, we should also examine the hyperplane $x_1=-\sqrt{c_x}$, but by symmetry we’ll get the same result. A similar result applies for the other variables $x_i$, but with the corresponding minor in the denominator.