6
$\begingroup$

This is the theorem statement:

John's Theorem: Each convex body $K$ contains a unique ellipsoid of maximal volume. This ellipsoid is $B^n_2$ (Euclidean ball of unit radius) iff: $B^n_2 \subset K$ and (for some $m$), there are Euclidean unit vectors $(u_i)_1^m$ on the boundary of $K$ and positive numbers $(c_i)_1^m$ satisfying \begin{equation} \sum_{i=1}^m c_i u_i = 0 \end{equation} and \begin{equation} \sum_{i=1}^m c_i \langle x,u_i\rangle^2 = \|x\|^2 \text{ for each }x\in\mathbb{R}^n \end{equation}

Note that we're only working with centrally symmetric convex bodies for the rest of this post, in which case the second condition implies the first, i.e. the latter is redundant.

What part I'm specifically concerned with:

Suppose $B_2^n$ is an ellipsoid of largest volume in $K$. We want to show that there is a sequence of contact points $(u_i)$ and positive weights $(c_i)$ with $$\frac{1}{n}I_n = \frac{1}{n}\sum c_i \ u_i\otimes u_i$$

The proof begins:

Equating traces on both sides of the equation, we know that if this is possible, then $$\sum \frac{c_i}{n} = 1$$ So our aim is to show that the matrix $I_n/n$ can be written as a convex combination of (a finite number of) matrices of the form $u \otimes u$, where each $u$ is a contact point. Since the space of matrices is finite-dimensional, the problem is simply to show that $I_n /n$ belongs to the convex hull of the set of all such rank-one matrices,$$T = \{u \otimes u : u \text{ is a contact point}\}$$

  1. How does the space of matrices being finite-dimensional help?
  2. The definition of $T$ seems slightly off. Perhaps the author meant $T = \text{conv}\{u \otimes u : u \text{ is a contact point}\}$, i.e. the convex hull of all matrices of the form $uu^T$? Being a contact point between $B^n_2$ and $K$, $u\in\partial K$ and $\|u\| = 1$.

We shall aim to get a contradiction by showing that if $I_n/n$ is not in T, we can perturb the unit ball slightly to get a new ellipsoid in $K$ of larger volume than the unit ball. Suppose that $I_n/n$ is not in $T$. Apply the separation theorem in the space of matrices to get a linear functional $φ$ (on this space) with the property that $$φ\left(\frac{I_n}{n}\right) < φ(u\otimes u)$$ for each contact point $u$. Observe that $φ$ can be represented by an $n \times n$ matrix $H = (h_{jk})$ , so that, for any matrix $A = (a_ {jk})$, $$φ(A) = \sum_{jk}h_{jk}a_{jk}$$

  1. How did we come up with this linear functional? It makes intuitive sense, but I want to know exactly how we used the separation theorem as stated here.
  2. I saw this coming - since we are working in the space of matrices, we had to define an inner product similar to the one for $\mathbb{R}^n$ - hence we just chose the element-wise product and applied the separating hyperplane theorem? We didn't have any other option for the inner product though, right?

Since all the matrices $u \otimes u$ and $I_n /n$ are symmetric, we may assume the same for $H$. Moreover, since these matrices all have the same trace, namely $1$, the inequality $φ(I_n /n) < φ(u \otimes u)$ will remain unchanged if we add a constant to each diagonal entry of $H$. So we may assume that the trace of $H$ is $0$: but this says precisely that $φ(I_n) = 0$.

Hence, unless the identity has the representation we want, we have found a symmetric matrix $H$ with zero trace for which $$\sum_{jk}h_{jk}(u\otimes u)_{jk} > 0$$ for every contact point $u$. We shall use this $H$ to build a bigger ellipsoid inside $K$. Now, for each vector $u$, $$\sum_{jk}h_{jk}(u\otimes u)_{jk} = u^THu$$

  1. What does the author mean by "the representation we want"?

For sufficiently small $δ > 0$, the set $$E_δ = \{x ∈ \mathbb{R}^n : x^T (I_n + δH)x ≤ 1\}$$ is an ellipsoid and as $δ$ tends to $0$ these ellipsoids approach $B_2^n$. If $u$ is one of the original contact points, then $$u^T (I_n + δH)u = 1 + δu^T Hu > 1$$ so $u$ does not belong to $E_δ$. Since the boundary of $K$ is compact (and the function $x \mapsto x^T Hx$ is continuous) $E_δ$ will not contain any other point of $∂K$ as long as $δ$ is sufficiently small. Thus, for such $δ$, the ellipsoid $E_δ$ is strictly inside $K$ and some slightly expanded ellipsoid is inside $K$.

It remains to check that each $E_δ$ has volume at least that of $B_2^n$. If we denote by $(μ_j)$ the eigenvalues of the symmetric matrix $I_n + δH$, the volume of $E_δ$ is $v_n/\prod\mu_j$ so the problem is to show that, for each $δ$, we have $\prod μ_j ≤ 1$. What we know is that $\sum μ_j$ is the trace of $I_n + δH$, which is $n$, since the trace of $H$ is $0$. So the AM/GM inequality again gives $$\prod \mu_j^{1/n} \le \frac{1}{n}\sum \mu_j \le 1$$ as required.

  1. $v_n$ denotes the volume of $B^n_2$ - how did we write the volume of the ellipsoid $E_\delta$ in terms of the eigenvalues of $I_n + \delta H$?

  2. We assumed $I_n/n\notin T$, in order to get a contradiction. Where is the contradiction?


I know this is a long post! Thanks a lot for reading this far. Since this is a long one, and understanding the proof requires several clarifications, I have decided to award a bounty to an answer that helps with all (or most) of my questions. Thanks again - I'd appreciate any help!

$\endgroup$
8
  • 1
    $\begingroup$ +1, I too struggled to understand John's theorem! I will make an effort anyway now. $\endgroup$ – Teresa Lisbon Jan 17 at 5:13
  • $\begingroup$ (1, 2): I'm not sure that finite-dimensionality helps, and yes I think the author means for $T$ to be the convex hull of the $u \otimes u$. (3): "Separation Theorem I" on that page is what is being used, but stated in a different form we could phrase it like this: "If $A, B \subseteq \mathbb{R}^n$ are convex and one is compact, then there is a hyperplane $H$ strictly separating (not intersecting) $A$ and $B$". Such a hyperplane is of the form $\varphi(-) = c$ for some functional $\varphi$ and number $c$, and we must have $\varphi(a) < c < \varphi(b)$ for all $a \in A$ and $b \in B$. $\endgroup$ – Joppy Jan 19 at 0:40
  • $\begingroup$ (4): As in (3), the separating hyperplane theorem has little to do with a norm (really the only role the norm is playing is to define compactness). If you have an inner product handy, then every functional $\varphi(-)$ is of the form $\langle v, - \rangle$ for some vector $v$, so this is why the theorem is sometimes stated that way. (5) Rather than looking at the vector space of all matrices, look at the subspace of symmetric matrices: both $T$ and $I_n$ live here, and apply the separating hyperplane theorem in this space. $\endgroup$ – Joppy Jan 19 at 0:43
  • 1
    $\begingroup$ Oof, it's been ages. Let me help you out. I've got a couple of things in the pipeline, but I've got a weekend coming up, most importantly. And that means that I can give time to both your question and another one that's been bothering me for some time. Just give me like two days, I promise you I'll respond. $\endgroup$ – Teresa Lisbon Apr 15 at 17:21
  • 1
    $\begingroup$ @TeresaLisbon Thank you, no worries! Take your time. About the side-note: Haha, I'm surprised you noticed! I like to keep changing my username every now and then, and it's a fun challenge to come up with a new witty one every time I do so! If you noticed, I'm also a fan of two word alliterations in usernames :) $\endgroup$ – epsilon-emperor Apr 18 at 11:13
1
+50
$\begingroup$

So first, I'll attach for the benefit of others, a preliminary discussion to this one, in an answer of mine here and the PDF file contaning the above proof here.

Let's start with... the second one. For the first one, I will delay it to a more convenient point. I basically think that finite-dimensionality manifests itself in more than one way through the paper and wasn't mentioned at the best point. There are other places where it is better to mention.

Along the way I will also clarify stuff that you haven't asked explicitly but may still be confused about. That's because others could get confused here, so it's better to go over it anyway!


(ii)

The easiest one : it's off , indeed $T = \mbox{conv}\{u \otimes u : u \text{ is a contact point}\}$ is correct.


(iii)

The separation theorem works here as follows : we treat matrices as vectors , as elements of $\mathbb R^{n^2}$, for example by writing one row after another (e.g. write $\begin{pmatrix}1&2\\3&4\end{pmatrix}$ as $[1,2,3,4]$). With that, the inner product is the usual "dot" product of vectors, and what is meant then , by "$\varphi$ is represented by $H$" is that $\varphi(A) = \langle H,A\rangle_{\mathbb R^{n^2}}$ for all $A \in \mathbb R^{n^2}$.

Note that the first use of finite dimensionality is the idea that every linear transformation can be represented as a matrix. You can't associate a $\varphi$ to a $H$ in infinite dimensions.

Now, with that in mind, since the sets $T$ and $\{\frac {I_n}n\}$ are disjoint non-empty convex sets and the second set is compact, the extended separation theorem tells us that there is a $\varphi$ (or an $H$) and a $C$ such that $\varphi(A) <C$ and $\varphi(t) > C$ for all $t \in T$.

However, any linear functional is a convex function (obviously), and it's a well known theorem that "a convex functional on a convex compact set attains its extrema at an extreme point".

What is an extreme point of a convex set? It's a point that's "in a corner" of the set. More precisely, a point $x \in T$ such that there don't exist points $y,z\in T$ and $0<\lambda<1$ such that $x = \lambda y + (1-\lambda)z$. That is, $x$ doesn't kind of "lie strictly between" two points in the set.

So, to conclude that $\varphi$ actually attains its extrema at one of the $u \otimes u$, we will need to prove that $T$ is compact, and that $u \otimes u$ are in fact the extreme points.

For the latter, finite dimensionality does the job : the convex hull of infinitely many vectors in an infinite dimensional space need not be closed, and hence not compact. But in finite dimensional space, the requirement is fulfilled, and the convex hull that is taken turns out to be closed and bounded, hence compact. That's where this is important, and it's not quite written in the right place as far as I'm concerned.

What about extremality? It's not a simple exercise, but certainly a worthwhile one to show that the extreme points of $T$ are in fact given by the $\{u \otimes u\}$. I'll write a proof for this one , but after some time.

But now : if that is confirmed, then indeed the statement $\varphi(t) > C$ for all $t \in T$ is equivalent to $\varphi(u \otimes u) > C$ for all contact points $u$. So the point is, that $\varphi(\frac{I_n}{n}) < \varphi(u \otimes u)$ for all contact points $u$ and some chosen $\varphi$, in fact comes from the separation theorem, with a lot of background work.


(iv)

I think the most natural inner product sufficed, after all we just wanted to use the separation theorem, and the transition from functional to matrix requires an inner product, so why not the natural one? I personally don't see a a motivation for choosing a different inner product at this step, since we just wanted to fit in hyperplane separation.


(v)

The representation we want is the existence of $c_i$ such that $\frac{I_n}{n} = \sum c_i u_i \otimes u_i$. Indeed, this is the only contradiction so far that has been employed.

I'm honestly not sure how the fact that the matrix $H$ can be stated to be symmetric, was stated so trivially! It's not that obvious.

Anyway, the answer to that question comes from the proof of the separation theorem. The separation theorem, for two convex sets $K,L$, considers the element of minimum norm in $K-L$ and shows that it works. But the point is, that for us both the sets $T$ and $\{\frac {I_n}n\}$ consist of symmetric matrices, since $u\otimes u$ are all symmetric matrices and taking linear combinations of these preserve symmetry (and of course the identity is symmetric).

Therefore, any point that is in the set $T - \{\frac{I_n}{n}\}$ is basically the difference of two symmetric matrices, and hence symmetric itself. This will include the minimizer which we call $H$. That's why $H$ can be symmetric. Funnily enough, I can see a workaround that wouldn't require the symmetry at all.

The addition of the constants of the diagonal of $H$ are actually done because in some sense, the matrix $H$ will be used to stretch the ellipsoid, and the point is that a unit stretch corresponds to the eigenvalue $1$, because the identity matrix has all its eigenvalues as $1$. Essentially, the matrix $H$ is being designed to perturb the identity, and this constraint ensures that its trace is zero. Of course, this is the same as saying that $\varphi(I_n) = 0$, since $\varphi(I_n) = \langle H,I_n\rangle$ is the elementwise product which turns out to be the sum of the diagonal elements.


(vi)

For this, John mentions that on page number $13$, there is a formula for the volume of ellipsoids of a certain description.

The way to derive that formula of comes from the fact that every ellipsoid is the image of a unit ball under a linear transformation , and then you can use a change-of-variables formula for integration to finish things up, there a determinant factor comes up.

That formula applies to our case very specifically, and I'll explain why symmetry is important now.

The point is, that symmetric matrices are diagonalizable, and therefore admit an orthonormal basis of eigenvectors. This is a very well known result. So , let $\lambda_1,...,\lambda_n$ be the eigenvalues and $v_1,...,v_n$ be the corresponding orthonormal basis , which applies to the symmetric matrix $I_n + \delta H$. According to the theorem ,we have $(I_n+\delta H)v = \sum_{i=1}^n \lambda_i \langle v,v_i\rangle v_i$ (where the inner product is the dot product for vectors) for all $v$.

A small point here is that if $\delta$ is small enough then all the $\lambda_i$ are positive, so we can take their square roots.

Now, take the ellipsoid $E_{\delta} = \{x : x^T(I_n + \delta_H) x \leq 1\}$. Then, we can write this as : $$ \{x : x^T (I_n +\delta_H) x \leq 1\} = \{x : \sum_{i=1}^n \lambda_i\langle x,v_i\rangle^2 \leq 1\} $$

which means, according to the true statement of John, the area of this ellipsoid is $v_n \prod_{i=1}^n \frac 1{\sqrt{\lambda_i}} = \frac{v_n}{\sqrt{\prod_{i=1}^n \lambda_i}}$.

Which differs from the book, and I'm sure I'm right, but the rest of the argument still goes through. The reason it goes through is that $\sqrt{\prod_{i=1}^n \lambda_i} \leq 1$ if and only if $\prod_{i=1}^n \lambda_i \leq 1$, and then you can apply the given argument.


(vii)

Let me explain what's going on, with reference to the first line from John's theorem which I quote :

The proof is in two parts, the harder of which is to show that if $B_n^2$ is an ellipsoid of largest volume, then we can find an appropriate system of weights on the contact points.

We started by assuming that there is no appropriate system of weights on the contact points, which is the same as saying that $\frac{I_n}{n} \notin T$.

We then proceeded to prove that one of the $E_{\delta}$ has size at least bigger than that of $B_n^2$. This is a contradiction, since the assumption is that $B_n^2$ is an ellipsoid of largest volume, and the point is that John asserts that it must be the unique ellipsoid of largest volume i.e. that no ellipsoid can match it, let alone cross it. But the ellipsoids $E_{\delta}$ for small enough $\delta$ certainly do this job.

So the contradiction is in the uniqueness : IF $\frac{I_n}{n} \notin T$ then $B_n^2$ is not the unique ellipsoid of largest volume contained in $K$. Taking the contrapositive, if $B_n^2$ is in fact the unique ellipsoid of largest volume contained in $K$, then $\frac{I_n}{n} \in T$ must hold.

The first part of the theorem proves the converse : that if $\frac{I_n}{n} \in T$ then $B_n^2$ is the unique ellipsoid of largest volume contained in $K$. So we are done!

$\endgroup$
7
  • 1
    $\begingroup$ Note : I will still add a few things : you have written some things in bold which may have confused you. I have sought to clarify some of them and have decided to leave the rest out so that I can neatly write it up. $\endgroup$ – Teresa Lisbon Apr 22 at 4:27
  • 1
    $\begingroup$ @epsilon-emperor You are so good at guessing! Indeed, there is. The answer is quite simple actually : see, provided that $A$ is positive definite (symmetric with positive eigenvalues), one can prove there exists a $B$ such that $A = B^TB$. Now, we have $x^TAx = x^TB^TBx = \|(Bx)\|^2$. Therefore, we have : $$\{x : x^TAx \leq 1\} = \{x : \|Bx\|^2 \leq 1\} = B^{-1}(B_n^2)$$ as a set. Then, using the usual change of variable formula, we get the formula $vol(E) = \sqrt{\det(A^{-1})}$. $\endgroup$ – Teresa Lisbon Apr 22 at 11:06
  • 1
    $\begingroup$ This whole "change of variables" business should carry over, although I'm not entirely sure but still expectant, to the non-symmetric case, hopefully. $\endgroup$ – Teresa Lisbon Apr 22 at 11:09
  • 1
    $\begingroup$ Thank you so, so very much for the bounty! Hope to be at your service more often. Still have to add that little couple of things, I'll do it soon. $\endgroup$ – Teresa Lisbon Apr 24 at 11:03
  • 1
    $\begingroup$ No worries, thank you so much for your help! Math is hard, and it's so important to have a helpful and supportive community as one learns and struggles with it. To that end, you've been incredibly supportive, and I hope to discuss math with you more often! @TeresaLisbon $\endgroup$ – epsilon-emperor Apr 24 at 11:10

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.