4 I. Convex Sets at Large
c∗)
Assume that one cannot find a non-zero vector c
Rd
and a number α such
that c, vi = α for i = 1, . . . , m. Prove that H is injective.
Remark: The map H is an example of a moment map; see Chapter 4 of [F93].
4∗ (The Brickman Theorem). Let q1,q2 : Rn −→ R be quadratic forms and let
Sn−1 = x Rn : x = 1 be the unit sphere. Consider the map T : Rn −→ R2,
T (x) =
(
q1(x),q2(x)
)
. Prove that the image T (Sn−1) of the sphere is a convex set
in
R2,
provided n 2.
Remark: We prove this in Chapter II (see Theorem II.14.1).
5∗ (The Schur-Horn Theorem). For an n × n real symmetric matrix A = (αij),
let diag(A) = (α11, . . . , αnn) be the diagonal of A, considered as a vector from Rn.
Let us fix real numbers λ1,... , λn. Consider the set X Rn of all diagonals of
n × n real symmetric matrices with the eigenvalues λ1,... , λn. Prove that X is
a convex set. Furthermore, let l = (λ1, . . . , λn) be the vector of eigenvalues, so
l Rn. For a permutation σ of the set {1,... , n}, let = (λσ(1), . . . , λσ(n)) be
the vector with the permuted coordinates. Prove that
X = conv

: σ ranges over all n! permutations of the set {1,... , n} .
Remark: See Theorem II.6.2.
6 (The Birkhoff - von Neumann Theorem). For a permutation σ of the set
{1,... , n}, let us define the n × n permutation matrix = (ξij) σ as
ξij
σ
=
1 if σ(j) = i,
0 if σ(j) = i.
Prove that the convex hull of all n! permutation matrices

is the set of all n × n
doubly stochastic matrices, that is, matrices X = (ξij), where
n
i=1
ξij = 1 for all j,
n
j=1
ξij = 1 for all i and
ξij 0 for all i, j.
We consider an n × n matrix X as a point in
Rn2
.
Remark: We prove this in Chapter II (see Theorem II.5.2).
7. Let us fix an even number n = 2m and let us interpret Rn+1 as the space of
all polynomials p(τ) = α0 + α1τ + . . . + αnτ n of degree at most n in one variable
τ. Let
K = p
Rn+1
: p(τ) 0 for all τ R
be the set of all non-negative polynomials. Prove that K is a convex set and that K
is the set of all polynomials that are representable as sums of squares of polynomials
of degree at most m:
K =
k
i=1
qi
2,
where deg qi m .
Previous Page Next Page