minimum height of a 0-1 simplex
Mike
vertices are members {0, 1}**n ?
Equivalently, what is the minimum non-zero distance to the origin from
a hyperplane defined by members of {0, 1}**n ?
The answer is at most 1/sqrt(n) .
The corner simplex provides an example.
A smaller answer might be possible if the simplex is oblique enough
that the height-defining segment does not lie entirely within the
hypercube.
Anyone have the answer or a lower bound on it?
I tried this in sci.math, but no go.
Corbennick
The lower bound is 1/sqrt(n).
Proof as follows. Let e_1,...,e_n be the standard basis of R^n.
Let s be a simplex of dimension n in R^n.
The minimal height is taken at a vertex v_1 which lies opposite to a
face F of maximal area.
(This is so since the volume of the simplex is height times area(F)
times dimension factor.)
Let v_2,...,v_n be the vertices spanning F.
THEN: The angle between F and v_1-v_2 is smaller than \pi/2.
PROOF: Let F_1 be the convex hull of v_3,...,v_n. The area of F is
equal to the area of F_1 times the height of F
times a dimension factor. If the angle was \pi/2 or bigger, then the
height of the face (F_1,v_1) is bigger than
the height of F_1, hence this face has bigger area, a contradiction!
Now assume that all vertices of s lie in {0,1}^n.
By symmetry we can assume that zero is a vertex and the minimal height
is taken in the vertex 0.
Let y_1,...,y_n be the other vertices and let v in R^n be of length
one and orthogonal to the
face spanned by y_1,...,y_n. This fixes v up to sign, which we choose
in such a way that
<y_j,v> = h, the minimal height for every j=1,...,n.
By the above it follows that hv lies in the simplex s, so v lies in (R
+)^n, i.e., all coordinates
of v are greater or equal to zero.
For each j there is a subset Ej of {1,2,...,n} such that y_j is the
sum of all e_k with k in Ej.
Since the y_j are linearly independent, every e_k occurs at least
once.
We conclude
h^2n = \sum_k <y_k,v>^2 = \sum_k (\sum_{j\in E_k} v_j)^2 >= \sum_k
\sum_{j\in E_k}v_j^2 >= \sum_j v_j^2 = 1
So it follows h >= 1/sqrt(n) as claimed.
Mike
Excellent news. Thanks much.
I'm having trouble following the proof, though.
I'll get back to it when I'm not supposed to be working.
> Proof as follows. Let e_1,...,e_n be the standard basis of R^n.
> Let s be a simplex of dimension n in R^n.
> The minimal height is taken at a vertex v_1 which lies opposite to a
> face F of maximal area.
The crucial point that I didn't think of.
Once I can prove that both ends of the height-defining segment are in
n-cube,
the rest is easy.
Anton
no, is not.
For example, consider the simplex spanned by zero, e=e_1+...+e_n, e_1,
e_2,...,e_{n-1},
where e_1,...,e_n is the standard basis.
A calculation shows that the vertex at zero has height equal to 1/
sqrt(n-1+(n-2)^2)
which for n>3 is less that 1/sqrt(n).
Corbennick
> The crucial point that I didn't think of.
> Once I can prove that both ends of the height-defining segment are in
> n-cube,
> the rest is easy.
Yes, but it seems I made a mistake there, as the height-defining
segment
does not always lie inside the simplex.
However, it does so, if the simplex has the property that all angles
between
edges are at most \pi/2.
Now for a simplex with vertices in {0,1}^n this condition is
satisfied!
By symmetry, it is enough to check this at the vertex zero.
Here is means that if you vave two non-zero vectors v,w in {0,1}^n,
then
the angle between them is at most \pi/2.
This is equivalent to saying that ther inner product <v,w> is >= 0,
which indeed is the case as all coordinates of v and w are >= 0.
Mike
>
> Proof as follows. Let e_1,...,e_n be the standard basis of R^n.
> Let s be a simplex of dimension n in R^n.
> The minimal height is taken at a vertex v_1 which lies opposite to a
> face F of maximal area.
> (This is so since the volume of the simplex is height times area(F)
> times dimension factor.)
> Let v_2,...,v_n be the vertices spanning F.
>
> THEN: The angle between F and v_1-v_2 is smaller than \pi/2.
I'm not sure what this means,
but I think that it is not true even in three dimension.
>From later statements, I gather that it implies
that a minimal-height-defining line segment of a
tetrahedron lies within the tetrahedron.
Consider a tetrahedron with the following vertices:
(0, 0, 0), (3, 2, 0), (3, -2, 0) and (4, 0, 1).
Its minimal-height-defining segment is (4, 0, 1)_(4, 0, 0).
(4, 0, 0) is outside the tetrahedron.
So far I haven't found a counterexample among 0-1 simplexes.
> PROOF: Let F_1 be the convex hull of v_3,...,v_n. The area of F is
> equal to the area of F_1 times the height of F
> times a dimension factor. If the angle was \pi/2 or bigger, then the
> height of the face (F_1,v_1) is bigger than
> the height of F_1, hence this face has bigger area, a contradiction!
>
> Now assume that all vertices of s lie in {0,1}^n.
> By symmetry we can assume that zero is a vertex and the minimal height
> is taken in the vertex 0.
> Let y_1,...,y_n be the other vertices and let v in R^n be of length
> one and orthogonal to the
> face spanned by y_1,...,y_n. This fixes v up to sign, which we choose
> in such a way that
> <y_j,v> = h, the minimal height for every j=1,...,n.
> By the above it follows that hv lies in the simplex s, so v lies in (R
> +)^n, i.e., all coordinates
> of v are greater or equal to zero.
> For each j there is a subset Ej of {1,2,...,n} such that y_j is the
> sum of all e_k with k in Ej.
> Since the y_j are linearly independent, every e_k occurs at least
> once.
> We conclude
>
> h^2n = \sum_k <y_k,v>^2 = \sum_k (\sum_{j\in E_k} v_j)^2 >= \sum_k
> \sum_{j\in E_k}v_j^2 >= \sum_j v_j^2 = 1
>
> So it follows ?h >= 1/sqrt(n) as claimed.
Mike
That is what I get, also.
The base satisfies the linear equation
n-1
SUM x[j] + (2-n)*x[n] = 1
j=1
Lower bound, anyone?
Mike
The above is roughly 1/n, but there are worse examples:
e_j for j in 1..k
k
SUM e_j + e_L for L in k+1..n
j=1
k n
The vertices satisfy SUM x_j + (1-k) SUM x_j = 1
j=1 j=k+1
For k=2n/3, the distance to zero is roughly sqrt(27/(4n**3)).
I still don't have a lower bound.
I was hoping for something better than the reciprocal of a maximum
determinate.