 Solution

If the center $z$ violates a constraint, choose a row $a^T$ with $a^{T}z<b_i$. Under the assumption of nonempty $P$, this row cannot have $a=0$. Every $x\in P$ satisfies $a^{T}x\ge b_i>a^{T}z$. Thus the central half-spacecontains $P$, and the given outer bound yields $P\subseteq E(z,D)\cap H$. Checking the rows of $A$ therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that $P$ is empty.

Whiten the ellipsoid by $x=z+D^{1/2}y$ and rotate the cut normal to $e_1$. The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for $n\ge 2$, the shape matrix has eigenvalue $n^2/(n+1{)}^2$ in the $e_1$ direction and $n^2/(n^2-1)$ in each of the other $n-1$ directions. The center does not affect volume, soUsing $\log (1-a)<-a$ for $0<a<1$ and $\log (1+b)<b$ for $b>0$ givesThereforeThis is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when $n=1$; in that case interval bisection gives the stronger ratio $1/2$.

Undoing the normalization gives the general central-cut updateIt preserves containment of the feasible region while reducing volume geometrically. After $k$ cuts the volume is less than $V_0{e}^{-k/(2(n+1))}$. If a feasible region has a known positive-volume lower bound $V_{\min }$, more than $2(n+1)\log (V_0/V_{\min })$ unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.

For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.