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 lσ = (λσ(1), . . . , λσ(n)) be

the vector with the permuted coordinates. Prove that

X = conv

lσ

: σ 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 Xσ = (ξij) σ as

ξij

σ

=

1 if σ(j) = i,

0 if σ(j) = i.

Prove that the convex hull of all n! permutation matrices

Xσ

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 .