================================================================================
AN EXACT SEMIDEFINITE LIFT OF A NONSPECTRAHEDRAL HYPERBOLICITY CONE
A self-contained rewrite for a reader with high school algebra
================================================================================
A NOTE TO THE READER
This file explains, from scratch, what a research paper proves. It has the
same mathematical content but no gaps and no jargon without a definition.
Every new term is introduced before it is used. Every formula is checked.
When a step looks magical, that is only because we have not yet written the
small computation that justifies it - the computation is always nearby.
You do not need calculus. You need:
- arithmetic, fractions, powers
- the idea of a "function of several variables"
- a willingness to read slowly and to plug numbers in
Everything else - vectors, matrices, eigenvalues, trig polynomials - is
defined here. If you get stuck at some line, that line is wrong on our side,
not on yours. Fix it by walking through the nearest example.
THE MAIN RESULT IN ONE PARAGRAPH
Some shapes in geometry can be drawn as "the set of numbers x where a
certain symmetric matrix M(x) is positive semidefinite." Those shapes are
called spectrahedra; they are always convex. Some shapes are not of this
form, but become so if we allow a few extra variables to float freely; such
shapes are called spectrahedral shadows, or "semidefinite lifts."
This paper takes a specific 23-dimensional convex cone K that is known NOT
to be a spectrahedron in its own 23 coordinates. It then proves that K still
has a semidefinite lift: there is an explicit 100 x 100 matrix pencil, with
307 auxiliary variables, whose positive-semidefinite locus projects exactly
onto K. So K is a spectrahedral shadow even though it is not a spectrahedron.
Everything below builds up to that statement and proves it.
================================================================================
PART 1. THE BASIC OBJECTS
================================================================================
1.1 VECTORS AND MATRICES
A vector is an ordered list of real numbers. Example: v = (3, -1, 2.5).
The length of v is the number of entries. We will frequently use vectors in
R^3 (length 3) and R^4 (length 4).
A matrix is a rectangular array of numbers. Example:
M = [ 2 1 0 ]
[ 1 3 -1 ]
[ 0 -1 5 ]
is a 3 x 3 matrix. The number in row i, column j is called M_{ij}. We will
mostly use square matrices: same number of rows and columns.
A matrix M is symmetric if M_{ij} = M_{ji} for every i and j: M is a mirror
image of itself across the diagonal. The matrix above is symmetric.
The transpose M^T of a matrix M is the matrix obtained by flipping M across
its diagonal. So (M^T)_{ij} = M_{ji}. Symmetric means M^T = M.
Given a vector v = (v_1, ..., v_n) and a symmetric n x n matrix M, we can
form the single number
v^T M v = sum over i, j of v_i M_{ij} v_j.
This is called the quadratic form of M at v. It is a quadratic function of
the entries of v: each term has degree 2.
Concrete example. With M above and v = (x, y, z):
v^T M v = 2x^2 + 2xy + 3y^2 - 2yz + 5z^2.
Notice the cross-terms come in pairs (xy appears twice, once from M_12 and
once from M_21), the diagonal terms are single squares times M_ii.
1.2 POSITIVE SEMIDEFINITE MATRICES
A symmetric matrix M is positive semidefinite (PSD, written M >= 0) if
v^T M v >= 0 for every vector v.
That is: the quadratic form of M is nonnegative as a function of v.
Example (PSD):
M = [ 2 1 ]
[ 1 2 ]
Then v^T M v = 2x^2 + 2xy + 2y^2 = (x + y)^2 + (x^2 + y^2) >= 0. PSD.
Example (not PSD):
M = [ 1 0 ]
[ 0 -1 ]
Then v^T M v = x^2 - y^2. At v = (0, 1) this is -1 < 0. Not PSD.
A key fact (we will use it everywhere):
For a 2 x 2 symmetric matrix [ [a, b], [b, c] ],
[ [a, b], [b, c] ] >= 0 if and only if
a >= 0, c >= 0, and ac - b^2 >= 0.
Here ac - b^2 is the ordinary determinant: both diagonal entries must be
nonnegative and the determinant nonnegative. (Both entries are needed:
[ [0,0],[0,-1] ] has a = 0 and det = 0 yet is not PSD.)
Proof. The quadratic form is q(x, y) = a x^2 + 2b xy + c y^2.
If a > 0, complete the square:
q = a (x + (b/a) y)^2 + (c - b^2/a) y^2.
If q >= 0 for all (x, y), taking x = -(b/a) y gives c - b^2/a >= 0,
i.e. ac >= b^2. Conversely, if ac - b^2 >= 0 and a > 0, this is a sum
of two squares, so q >= 0. Also q(1, 0) = a and q(0, 1) = c, so a >= 0
and c >= 0 are necessary.
If a = 0, the form is q = 2b xy + c y^2. For q >= 0 for all (x, y) we
need b = 0 (take x = -t y with large t > 0; if b != 0 we get q < 0) and
c >= 0. Conversely, a = 0 forces ac - b^2 = -b^2 >= 0, so b = 0; with
c >= 0 the form is q = c y^2 >= 0. So the test holds here too.
The general n x n case is the same idea but harder. The key rule we will
actually use is:
Block PSD test (Schur complement, positive definite case).
For symmetric block matrices of the shape
N = [ P Q ]
[ Q^T S ]
with P positive definite (i.e. P >= 0 and P x = 0 implies x = 0), we
have N >= 0 if and only if P >= 0 and S - Q^T P^{-1} Q >= 0.
If P can be singular, replace P^{-1} by the pseudoinverse and add a
range condition; see Part 8.7-8.9.
A pure algebraic fact we will use: the set of PSD matrices is itself convex.
If M_1 and M_2 are PSD and 0 <= t <= 1, then t M_1 + (1 - t) M_2 is PSD:
for every vector v,
v^T (t M_1 + (1-t) M_2) v = t (v^T M_1 v) + (1-t) (v^T M_2 v) >= 0.
1.3 THE CIRCLE AS A SPECTRAHEDRON
Here is the warm-up example, the source of every idea in this paper.
Fix a radius r >= 0. For every point (x, y) in the plane, define a 2 x 2
symmetric matrix
M(x, y) = [ r + x y ]
[ y r - x ]
Claim. M(x, y) >= 0 if and only if x^2 + y^2 <= r^2.
Proof. Apply the 2 x 2 test from 1.2 with a = r + x, b = y, c = r - x.
The three conditions become
a = r + x >= 0, c = r - x >= 0, ac - b^2 = r^2 - x^2 - y^2 >= 0.
Forward. If M >= 0, the test gives ac - b^2 = r^2 - x^2 - y^2 >= 0,
i.e. x^2 + y^2 <= r^2.
Backward. If x^2 + y^2 <= r^2, then |x| <= r, so both
r + x >= r - |x| >= 0 and r - x >= r - |x| >= 0, and also
r^2 - x^2 - y^2 >= 0. All three conditions hold, so M >= 0.
So the disk of radius r is described as "the set of (x, y) for which the
matrix M(x, y) is PSD." Each entry of M is affine (degree-1, no
multiplications of x by y) in (x, y). This is the entry point for
everything that follows.
1.4 THE DEFINITION OF A SPECTRAHEDRON
Generalizing the circle example:
A spectrahedron is a set S in R^n such that there exist symmetric
d x d matrices A_0, A_1, ..., A_n with the property
x in S <==> A_0 + x_1 A_1 + ... + x_n A_n >= 0.
Here d and the matrices A_i are fixed, and only x = (x_1, ..., x_n)
varies. If all x_i are zero, the matrix is A_0.
Spectrahedra are automatically convex, because the PSD cone is convex (1.2)
and the map x -> A(x) is affine. That is: if x and x' are in S, the midpoint
(x + x')/2 is too. Convexity is a geometric niceness property; it is why
spectrahedra are "tame" for optimization.
The circle is a spectrahedron. So is any ellipsoid, any box, any cone that
can be described by a Lorentz-type inequality. In fact, nearly every convex
shape you draw by hand is a spectrahedron, but not all of them: the question
"which convex sets are spectrahedra?" is hard.
================================================================================
PART 2. SHADOWS AND LIFTS
================================================================================
2.1 PROJECTION (SHADOWS)
Imagine a 3D object and a 2D wall. The sun casts a shadow of the object onto
the wall. The shadow is the set of points on the wall through which some
point of the object lies.
Mathematically: let C be a set in R^{n+k}. Its projection onto the first n
coordinates is
proj(C) = { x in R^n : some (x, v) in C with v in R^k }.
The extra k coordinates v are called auxiliary coordinates.
Shadows can be dramatically simpler than the object that casts them (a
sphere's shadow is a disk), or more complicated in a different sense. In
this paper, the extra coordinates may be thought of as "hidden knobs" we
are allowed to turn in order to make a shape fit into a simple form.
2.2 SPECTRAHEDRAL SHADOWS (SEMIDEFINITE LIFTS)
A spectrahedral shadow is a projection of a spectrahedron.
A set S in R^n is a spectrahedral shadow if there exist symmetric
matrices A_0, A_1, ..., A_n, B_1, ..., B_k such that
x in S <==> exists v in R^k with
A_0 + sum x_i A_i + sum v_j B_j >= 0.
Equivalently: S is a spectrahedral shadow if there is a spectrahedron C in
R^{n+k} whose projection onto the first n coordinates is S.
Another word for "S is a spectrahedral shadow" is "S has a semidefinite
lift." We use both phrases.
Every spectrahedron is a spectrahedral shadow trivially (take k = 0). But
sometimes a shape that is not a spectrahedron is still a shadow of one.
Why do we care? Because optimizing a linear function over a spectrahedron
is a well-understood computational problem (semidefinite programming, SDP).
If our shape is a shadow of a spectrahedron, we can optimize over the shadow
by optimizing over the parent and projecting the answer back. Many hard
convex optimization problems in engineering and statistics are solved this
way. So "is this shape a shadow of a spectrahedron?" is a real question with
real applications.
================================================================================
PART 3. HYPERBOLICITY CONES
================================================================================
3.1 HOMOGENEOUS POLYNOMIALS
A polynomial p(x_1, ..., x_n) is homogeneous of degree d if, for every
positive scalar t and every vector x,
p(t x) = t^d p(x).
Example: p(x, y) = x^2 - y^2 is homogeneous of degree 2.
p(2, 1) = 3, p(4, 2) = 12 = 4 * 3 = 2^2 * 3. Yes.
3.2 HYPERBOLICITY
Fix a direction e in R^n with p(e) > 0. Say p is hyperbolic with respect
to e if, for every x in R^n, the one-variable polynomial
t |--> p(t e - x)
has all of its roots real (as a function of t).
Example. p(x, y) = x^2 - y^2 in R^2, direction e = (1, 0).
p(t e - x) where x = (x_1, x_2) is p(t - x_1, -x_2)
= (t - x_1)^2 - x_2^2.
This is an upward parabola in t; its roots are t = x_1 +- |x_2|
... well, if x_2 >= 0, t = x_1 +- x_2, both real. If x_2 < 0, still
both real. So p is hyperbolic with respect to e.
Non-example. p(x, y) = x^2 + y^2 with e = (1, 0).
p(t e - x) = (t - x_1)^2 + x_2^2. For x_2 != 0 this has roots
t = x_1 +- i x_2, complex. Not hyperbolic.
So "hyperbolic with respect to e" is a strong constraint. In the examples:
p = x^2 - y^2 passes, p = x^2 + y^2 fails.
3.3 HYPERBOLICITY CONES
Given a hyperbolic polynomial p with direction e, define its hyperbolicity
cone (closed convention, roots allowed to be zero):
K(p, e) = { x in R^n : every root of t |--> p(t e - x) is >= 0 }.
For p = x^2 - y^2 and e = (1, 0): the roots of (t - x_1)^2 - x_2^2 are
t = x_1 +- x_2. Both >= 0 iff x_1 >= |x_2|. So
K(x^2 - y^2, (1, 0)) = { (x_1, x_2) : x_1 >= |x_2| }.
That is the familiar "second-order cone" or "ice cream cone" in the plane:
the set of points (x_1, x_2) with x_1 positive and enough of it.
Remarkable fact (Garding 1959): K(p, e) is always a closed convex cone.
Convexity is not obvious; it is a theorem. We will use it but not prove it.
For a 3-variable polynomial, the hyperbolicity cone is a 2D cone. It is
known (Helton-Vinnikov 2007) that EVERY 3-variable hyperbolicity cone is
actually a spectrahedron. Going to 4 or more variables, this is no longer
automatic, which is exactly the interesting case.
One genuinely helpful small fact we will use over and over: if p is
hyperbolic with respect to e, then
dim K = n (full-dimensional)
K has a nonempty interior, and 0 is in K.
So K is always a "fat" cone, not a sliver.
================================================================================
PART 4. THE SPECIFIC CONE IN THIS PAPER
================================================================================
4.1 THE QUADRATIC MATRIX Q(y)
For y = (y_1, y_2, y_3) in R^3, define a 3 x 3 symmetric matrix
Q(y) = [ y_1^2 + y_2^2 -y_1 y_2 -y_1 y_3 ]
[ -y_1 y_2 y_2^2 + y_3^2 -y_2 y_3 ]
[ -y_1 y_3 -y_2 y_3 y_3^2 + y_1^2 ]
Two facts about Q:
(a) Q is homogeneous of degree 2 in y: Q(t y) = t^2 Q(y).
(b) Q(y) >= 0 (PSD) for every y. In fact, rank(Q(y)) = 2 unless
y = 0, where Q = 0. We prove this in Part 5.2 via a Gram
factorization.
Sanity check. Take y = (1, 0, 0). Then
Q(1, 0, 0) = [ 1 0 0 ]
[ 0 0 0 ]
[ 0 0 1 ]
which is diagonal with entries (1, 0, 1). PSD. Good.
The form z^T Q(y) z for z = (z_1, z_2, z_3) is a "biquadratic" (degree 2
in z, degree 2 in y). It is known in the literature as the coefficient-one
Choi-Lam form, but you do not need that name to follow this paper.
4.2 THE LINEAR MAP PHI_y
For y in R^3 and any 4 x 4 symmetric matrix W, write W in blocks:
W = [ a r^T ]
[ r T ]
with a scalar a in R, r in R^3, T a 3 x 3 symmetric matrix. Define
Phi_y(W) = [ tr(Q(y) T) -r^T Q(y) ]
[ -Q(y) r a Q(y) ]
Here tr is the trace (sum of diagonal entries of a square matrix). The
block structure of Phi_y(W) is 1 x 1, 1 x 3, 3 x 1, 3 x 3, so Phi_y(W) is
again 4 x 4 symmetric. You can check:
- Phi_y(W) is linear in W: Phi_y(s W + t W') = s Phi_y(W) + t Phi_y(W').
- Phi_y depends on y through Q(y), hence quadratically.
- Consequently Phi_{-y} = Phi_y (since Q(-y) = Q(y)).
Sanity check. Take y = (1, 0, 0) and W = I_4 (so a = 1, r = (0,0,0), T = I_3).
Then Q(1,0,0) = diag(1, 0, 1), so tr(Q T) = 1 + 0 + 1 = 2, and the block
form is
Phi_y(I_4) = [ 2 (0, 0, 0) ]
[ (0,0,0)^T diag(1,0,1) ]
which is block diagonal with entries (2, 1, 0, 1). PSD.
4.3 THE POLYNOMIAL p
For X, Z in Sym^4 (4 x 4 symmetric) and y in R^3, define
p(X, Z, y) = det( (det X) Z - Phi_y(adj X) )
where adj X is the classical adjugate of X (the transpose of the cofactor
matrix). It satisfies X * adj X = (det X) I_4:
For invertible X, adj X = (det X) X^{-1}.
The inside argument is a 4 x 4 symmetric matrix. p is the determinant of it.
Degree. Each entry inside the determinant has degree exactly 5 in
(X, Z, y):
det X has degree 4 in X, so (det X) Z has degree 5.
adj X has degree 3 in X (each entry is a 3 x 3 determinant).
Phi_y(adj X) has degree 3 + 2 = 5 in (X, y), independent of Z.
So the two terms match: both degree 5.
A 4 x 4 determinant sums 24 products of four entries, so p has total degree
20. It is homogeneous of degree 20.
The "witness point". Define e = (I_4, I_4, 0) in Sym^4 x Sym^4 x R^3.
Then
p(e) = det( (det I_4) I_4 - Phi_0(adj I_4) )
= det( I_4 - Phi_0(I_4) ).
Now Q(0) = 0, so Phi_0(I_4) = 0. Hence p(e) = det(I_4) = 1. Good - this
matches the requirement p(e) > 0 for hyperbolicity.
4.4 THE CONE K AND THE MAIN THEOREM
Define K = K(p, e), i.e. the set of all x = (X, Z, y) in the 23-dimensional
space Sym^4 x Sym^4 x R^3 for which the polynomial t -> p(te - x) has all
roots >= 0.
Since Sym^4 has 10 independent coordinates, Sym^4 x Sym^4 x R^3 has
10 + 10 + 3 = 23 dimensions. So K is a cone in R^23.
Main Theorem (of this paper). There exist fixed symmetric 100 x 100
matrices A_1, ..., A_23 and B_1, ..., B_307 such that, for every x in R^23,
x in K <==> there exists v in R^307 with
sum_{nu=1}^{23} x_nu A_nu
+ sum_{j=1}^{307} v_j B_j
>= 0 (as a 100 x 100 PSD matrix).
That is: K is the projection of a spectrahedron in R^(23 + 307) = R^330
down to R^23. K is a spectrahedral shadow.
The sizes 100 and 307 are explicit. The theorem does NOT say they are the
smallest possible. It just gives one valid lift.
Companion fact (from a prior paper, cite "parent"). The same cone K has NO
homogeneous semidefinite representation in its own 23 coordinates. More
precisely: there is no 23-tuple of 4 x 4 (or larger) fixed symmetric
matrices A_0, ..., A_23 such that
x in K <==> A_0 + x_1 A_1 + ... + x_23 A_23 >= 0.
And no affine representation either (an affine rep can always be converted
to a homogeneous one when K contains 0, which it does - the companion
paper's argument gives the conversion explicitly).
So the picture is: K is not a spectrahedron, but it IS a spectrahedral
shadow.
================================================================================
PART 5. SLICING THE CONE BY ANGULAR PLANES
================================================================================
The main proof strategy is to reduce a hard 4 x 4 problem to a family of
easy 3 x 3 problems, one per angular slice through the y-space. This part
sets up the slices. Part 6 will show how to combine all slices into one
finite matrix inequality.
5.1 THE ANGULAR PLANES
For theta in R, set
c = cos theta, s = sin theta, w = e^{i theta} (a unit complex
number)
d(theta) = (c, s, 0) in R^3 (a unit vector in the (y_1, y_2)
plane, at angle theta)
k = (0, 0, 1) in R^3
For any real numbers eta, xi, define
Y_theta(eta, xi) = eta d(theta) + xi k
= (eta cos theta, eta sin theta, xi) in R^3.
This is a 2D plane in R^3 spanned by d(theta) and k. As theta ranges over
R, and eta, xi over R, the planes cover all of R^3: for every (y_1, y_2, y_3),
pick theta with (cos theta, sin theta) proportional to (y_1, y_2) (i.e. set
eta = sqrt(y_1^2 + y_2^2)), and set xi = y_3.
Equivalently: every point y in R^3 lies on one of these planes.
5.2 THE GRAM FACTORIZATION OF Q ON EACH PLANE
For theta in R define a 3 x 2 complex matrix
U(theta) = (1/sqrt(2)) * [ -w^{-1} -w ]
[ s w^{-2} s w^2 ]
[ c w^{-2} -c w^2 ]
And a fixed 3 x 2 complex matrix
V_0 = (1/sqrt(2)) * [ 0 0 ]
[ i i ]
[ 1 1 ]
For real eta, xi, set
F_theta(eta, xi) = eta U(theta) + xi V_0 (3 x 2 complex matrix).
Realification. For any complex 3 x 2 matrix F with columns f_1, f_2 in C^3,
define the real 3 x 4 matrix F~ by writing f_1 = (p_1 + i q_1) and
f_2 = (p_2 + i q_2) with p_j, q_j in R^3, and stacking:
F~ = [ p_1 q_1 p_2 q_2 ] (each column is a 3-vector)
Claim (this is the load-bearing lemma). For every theta, eta, xi,
F~_theta(eta, xi) * F~_theta(eta, xi)^T = Q( Y_theta(eta, xi) ).
(The left side is a 3 x 4 times a 4 x 3, so a 3 x 3 matrix. It is symmetric
and PSD: it is literally a Gram matrix.)
Direct proof by expansion. Compute Re(F F*), which equals F~ F~^T for a
complex matrix F. Write out F F* in the three contributions eta^2, xi^2,
eta xi:
Re(U U*) = [ 1 -sc 0 ]
[ -sc s^2 0 ]
[ 0 0 c^2 ]
(Check one entry. U's top row is u_1 = (1/sqrt(2))(-w^{-1}, -w). Then
|u_1|^2 = (1/2)(1 + 1) = 1. The entry (1,2) of Re(UU*) is
(1/2) * -s (w + w^{-1}) = -s cos theta = -sc. The rest is similar.)
And
Re(V_0 V_0*) = [ 0 0 0 ]
[ 0 1 0 ]
[ 0 0 1 ]
And
Re(U V_0* + V_0 U*) = [ 0 0 -c ]
[ 0 0 -s ]
[ -c -s 0 ]
Summing with coefficients eta^2, xi^2, eta xi:
(1,1) entry = eta^2 * 1 + xi^2 * 0 + eta xi * 0 = eta^2.
Q(Y_theta)_{1,1} = Y_1^2 + Y_2^2 = (eta c)^2 + (eta s)^2 = eta^2. Match.
(1,2) entry = eta^2 * (-sc) + 0 + 0 = -eta^2 sc.
Q(Y_theta)_{1,2} = -Y_1 Y_2 = -(eta c)(eta s) = -eta^2 cs. Match.
(1,3) entry = eta xi * (-c) = -eta xi c.
Q(Y_theta)_{1,3} = -Y_1 Y_3 = -(eta c)(xi) = -eta xi c. Match.
(2,2) entry = eta^2 s^2 + xi^2.
Q(Y_theta)_{2,2} = Y_2^2 + Y_3^2 = eta^2 s^2 + xi^2. Match.
(2,3) entry = eta xi * (-s) = -eta xi s.
Q(Y_theta)_{2,3} = -Y_2 Y_3 = -eta s xi. Match.
(3,3) entry = eta^2 c^2 + xi^2.
Q(Y_theta)_{3,3} = Y_3^2 + Y_1^2 = xi^2 + eta^2 c^2. Match.
All six distinct entries match, so the claimed identity holds.
Consequence. Q(y) = F~ F~^T is a Gram matrix for some real 3 x 4 matrix,
so Q(y) >= 0. Since every y lies on some plane, Q(y) >= 0 for all y.
Done with the statement in 4.1(b).
5.3 THE SLICE PENCIL L_theta
Introduce two auxiliary objects.
For any real 3-vector r, define the 4 x 4 "square wedge" matrix
B(r) = [ 0 r^T ]
[ -r 0_{3x3} ]
(antisymmetric: B(r)^T = -B(r)).
For u = (u_0, u') in R x R^3, define the 3 x 4 row-block matrix
J_u = [ u' -u_0 I_3 ] (3 rows, 4 columns).
Key algebraic identity:
B(r) u = J_u^T r (both sides are 4-vectors).
Check. Left side, writing u = (u_0, u_1, u_2, u_3):
B(r) u = ( r_1 u_1 + r_2 u_2 + r_3 u_3 , -r_1 u_0 , -r_2 u_0 , -r_3 u_0 ).
Right side: J_u^T r is a 4-vector whose entries are
(u_1 r_1 + u_2 r_2 + u_3 r_3, -u_0 r_1, -u_0 r_2, -u_0 r_3).
Same. Match.
Another key identity. If r_1, r_2, r_3, r_4 are the four columns of F~_theta(eta, xi),
then for every 4 x 4 symmetric W,
sum_{j=1}^{4} B(r_j)^T W B(r_j) = Phi_{Y_theta(eta, xi)}(W).
This is the whole reason B(r) and Phi_y exist. We verify it block by block.
Write W = [ a r^T ]
[ r T ]
and compute B(r)^T W B(r) for a single r. (Recall B(r)^T = -B(r).)
Multiplying [ 0 -r^T ; r 0 ] [ a r^T ; r T ] [ 0 r^T ; -r 0 ]:
a routine 3-step check gives
B(r)^T W B(r) = [ r^T T r -r^T v r^T ]
[ -r^T v r a r r^T ]
where v is the 3-vector written into W's upper-right block.
Now sum over the four columns r_1, ..., r_4 of F~. The four Gram outer
products sum to sum_j r_j r_j^T = F~ F~^T = Q(Y_theta(eta, xi)). So:
sum_j (r_j^T T r_j) = tr(T Q(Y_theta(eta, xi))),
sum_j (r_j^T v) r_j^T = v^T Q(Y_theta(eta, xi)),
sum_j (r_j^T v) r_j = Q(Y_theta(eta, xi)) v,
sum_j a r_j r_j^T = a Q(Y_theta(eta, xi)).
Assembled into a 4 x 4 block matrix, these are exactly the four blocks of
Phi_{Y_theta(eta, xi)}(W). Done.
5.4 THE SLICE PENCIL AND THE SLICE LEMMA
Fix theta, eta, xi. For arbitrary X, Z in Sym^4, define a 20 x 20 symmetric
matrix L_theta(X, Z, eta, xi) built in blocks:
L_theta = [ I_4 ⊗ X B_theta(eta, xi) ]
[ B_theta(...)^T Z ]
where
I_4 ⊗ X = a 16 x 16 block-diagonal matrix with four copies of X.
(Concretely: block (j,k) is X if j = k, else 0_{4x4}.)
B_theta(eta, xi) = a 16 x 4 matrix, obtained by stacking the four
4 x 4 matrices B(r_1), B(r_2), B(r_3), B(r_4)
vertically (r_1, ..., r_4 are the columns of
F~_theta(eta, xi)).
So L_theta is a 20 x 20 symmetric matrix. Its entries are:
- linear in X, Z, eta, xi (uniform, plus the four-block stacking)
- trig polynomials of degree <= 3 in theta (because F~_theta's rows
involve sin, cos of theta, times powers of w = e^{i theta} up to w^{-2}
and w^2; the worst case is degree 3).
Each entry of r_j has this degree-3 property: for example, the second row
of U is (s w^{-2}, s w^2). Expanding s w^{-2} = (w - w^{-1}) w^{-2}/(2i) =
(w^{-1} - w^{-3})/(2i), which has frequencies -1 and -3. So degree 3 in
theta.
THE SLICE LEMMA. For every theta, eta, xi in R and X, Z in Sym^4:
(X, Z, Y_theta(eta, xi)) is in K
<==> L_theta(X, Z, eta, xi) >= 0 (PSD).
Consequences:
(i) p is hyperbolic with respect to e (so K really is a hyperbolicity
cone).
(ii) K's slice at y = Y_theta(eta, xi) is a spectrahedron in (X, Z).
(iii) If X > 0 (positive definite), then L_theta >= 0 <==>
Z >= Phi_{Y_theta(eta, xi)}(X^{-1}).
Proof.
Step 1. For any X, Z in Sym^4, eta, xi in R,
p(X, Z, Y_theta(eta, xi)) = det L_theta(X, Z, eta, xi). (*)
Assume first X is invertible. Block determinant:
det L_theta = (det X)^4 * det(Z - B_theta^T (I_4 ⊗ X^{-1}) B_theta)
(the (det X)^4 = det of the 16 x 16 top-left block). Now
I_4 ⊗ X^{-1} is block-diagonal with X^{-1} in each 4 x 4 block, so
B_theta^T (I_4 ⊗ X^{-1}) B_theta
= sum_{j=1}^{4} B(r_j)^T X^{-1} B(r_j)
= Phi_{Y_theta(eta,xi)}(X^{-1}) (Part 5.3 identity).
So det L_theta = (det X)^4 det(Z - Phi_y(X^{-1})) with y = Y_theta(eta,xi).
Meanwhile, using adj X = (det X) X^{-1} and linearity of Phi_y in its matrix
argument:
p(X, Z, y) = det((det X) Z - Phi_y(adj X))
= det((det X) Z - (det X) Phi_y(X^{-1}))
= (det X)^4 det(Z - Phi_y(X^{-1})).
Match. Both sides of (*) are polynomials in X, Z, y that agree on the dense
open set {X invertible}. Two polynomials that agree on a dense open set
agree everywhere (a polynomial that vanishes on a nonzero open set is
identically zero). So (*) holds for singular X too.
Step 2. The "witness value" is L_theta(I_4, I_4, 0, 0) = I_20. Indeed,
X = I_4 gives I_4 ⊗ I_4 = I_16; eta = xi = 0 gives F~ = 0 hence
B_theta = 0; Z = I_4 gives I_4. So:
det(t I_20 - L_theta) with (X, Z, eta, xi) = (I_4, I_4, 0, 0) is
det(t I_20 - I_20) = (t - 1)^{20}.
Step 3. For general X, Z, eta, xi and general t,
det(t I_20 - L_theta(X, Z, eta, xi))
= det(t I_16 - I_4 ⊗ X, -B_theta; -B_theta^T, t I_4 - Z)
= det((det X_t) Z_t - Phi_{-Y_theta}(adj X_t)) with
X_t = t I_4 - X, Z_t = t I_4 - Z
= p(X_t, Z_t, -Y_theta(eta, xi))
= p(t e - (X, Z, Y_theta(eta, xi))).
Here we used t I_16 - I_4 ⊗ X = I_4 ⊗ (t I_4 - X) = I_4 ⊗ X_t, and
Phi_{-Y}(adj X_t) = Phi_{Y}(adj X_t) (since Phi_y depends on y through Q(y),
and Q(-y) = Q(y)).
So the eigenvalues of the symmetric matrix L_theta(X, Z, eta, xi) are
exactly the roots of t -> p(te - x) for x = (X, Z, Y_theta(eta, xi)).
Step 4. Hyperbolicity. The matrix L_theta is real symmetric, hence its
eigenvalues are real, hence the roots of t -> p(te - x) are real for every
x that lies on some plane (i.e. every x in R^23). So p is hyperbolic with
respect to e.
Step 5. Slice equivalence. Using the definition of K, x in K iff every
root of t -> p(te - x) is >= 0. Since the roots are the eigenvalues of the
symmetric matrix L_theta, this holds iff every eigenvalue is >= 0, i.e. iff
L_theta >= 0.
Step 6. If X > 0, Schur complement gives L_theta >= 0 iff X > 0 (automatic)
and Z - Phi_{Y_theta(eta,xi)}(X^{-1}) >= 0. Good.
================================================================================
PART 6. ONE FINITE MATRIX FOR ALL ANGLES
================================================================================
6.1 THE OBSTACLE
Part 5 gives us an exact characterization of K, but with a problem: it is
an INFINITE family of matrix conditions. For each y in R^3 we must find a
theta with Y_theta(eta, xi) = y (for appropriate eta, xi), and then require
L_theta(X, Z, eta, xi) >= 0. There are infinitely many thetas.
To turn this into a finite matrix inequality, we must somehow collapse the
theta-dependence into a single finite-matrix condition. The trick is: we
do not ask "is L_theta >= 0 for the theta that matches y?" We instead ask
"does there exist a linear functional on the space of trig-polynomial
test vectors that (a) reproduces y when applied to Y_theta(eta, xi), and
(b) is nonnegative on q^T L_theta q for all test vectors q?"
The trick works because of a careful algebraic identity (Part 7). We build
it in stages.
6.2 THE TEST SPACE OF TRIG POLYNOMIALS
A real trigonometric polynomial of degree at most j is any function of
theta of the form
a_0 + sum_{k=1}^{j} ( a_k cos(k theta) + b_k sin(k theta) )
with real coefficients. The set of such functions is a vector space, call it
T_j. Its dimension is 1 + 2j = 2j + 1. Basis:
1, cos theta, sin theta, cos 2theta, sin 2theta, ..., cos j theta,
sin j theta.
We will need j = 2 (dimension 5) and j = 7 (dimension 15).
6.3 THE AMBIENT SPACE E
Let V_22 = Sym^4 x Sym^4 x R x R. Its dimension is 10 + 10 + 1 + 1 = 22
(coordinates: X_{ij} for i <= j, Z_{ij} for i <= j, eta, xi).
Let E be the real vector space of functions
f(theta; X, Z, eta, xi)
that are real-linear in (X, Z, eta, xi) and trig polynomials of degree <= 7
in theta. An element of E is a sum of terms like "coefficient times X_{ij}
times a trig polynomial of degree <= 7", plus similar for Z, eta, xi.
Dimension: for each of the 22 coordinates, we have 15 basis trig polynomials
(T_7 basis). So dim E = 22 * 15 = 330.
6.4 THE LIFTING FUNCTIONAL LAMBDA
Introduce a real linear functional Lambda: E -> R. Think of Lambda as a
"black box" that takes an element of E and spits out a real number, and
respects linear combinations. It is specified by its 330 values on the 330
basis elements of E. We will treat those 330 numbers as the unknowns of our
finite matrix pencil.
Two families of conditions on Lambda.
OUTPUT CONDITIONS. For every pair (i, j) with i <= j:
Lambda(X_{ij}) = X_{ij} (here X on the right is the
"input" numeric entry, our target)
Lambda(Z_{ij}) = Z_{ij}
And, for the y-coordinate:
Lambda(eta cos theta) = y_1
Lambda(eta sin theta) = y_2
Lambda(xi * 1) = y_3 (the "* 1" just names the constant
basis function)
Count: 10 + 10 + 3 = 23 output equations. They pin down 23 of the 330
coordinates of Lambda. The remaining 330 - 23 = 307 coordinates will be our
auxiliary variables.
MOMENT CONDITION. For every vector q(theta) in (T_2)^20 (each of the 20
components of q is a trig polynomial of degree <= 2):
Lambda( q(theta)^T L_theta(X, Z, eta, xi) q(theta) ) >= 0.
Note: q^T L q is genuinely an element of E. Each entry of L_theta is
degree <= 3 in theta; each entry of q is degree <= 2; the product is
degree <= 3 + 2 + 2 = 7. And q^T L q is linear in (X, Z, eta, xi). So the
expression is in E, and Lambda can eat it.
Equivalently (see 6.5), the moment condition is exactly H(Lambda) >= 0
where H(Lambda) is a 100 x 100 symmetric matrix.
6.5 THE 100 x 100 MATRIX H(Lambda)
Let (f_1, f_2, f_3, f_4, f_5) = (1, cos theta, sin theta, cos 2theta, sin 2theta)
be the standard real basis of T_2.
Index the 100 rows and columns by pairs (i, a) with i in {1, ..., 20} and
a in {1, ..., 5}. Define:
H(Lambda)_{(i, a), (j, b)} = Lambda( f_a(theta) f_b(theta) * (L_theta)_{ij} ).
Here (L_theta)_{ij} is the entry of L_theta in row i, column j: a specific
element of E (linear in X, Z, eta, xi; trig of degree <= 3 in theta). The
product f_a f_b * (L_theta)_{ij} is in E (degree <= 2 + 2 + 3 = 7). Good.
H(Lambda) is real symmetric 100 x 100 (because f_a f_b = f_b f_a and L_theta
is symmetric) and linear in Lambda. Using the 23 output coordinates pinned
by X, Z, y and 307 remaining coordinates as v = (v_1, ..., v_307), H(Lambda)
becomes a fixed affine linear pencil in (X, Z, y, v) of size 100 x 100.
Equivalence of the two conditions. Take any q in (T_2)^20 and write each
component q_i = sum_a t_{i,a} f_a(theta) with real coefficients t_{i,a}.
Then:
q^T L q = sum_{i,j} q_i q_j (L_theta)_{ij}
= sum_{i,j,a,b} t_{i,a} t_{j,b} f_a f_b (L_theta)_{ij}
Lambda(q^T L q) = sum_{i,j,a,b} t_{i,a} t_{j,b} H(Lambda)_{(i,a),(j,b)}
= t^T H(Lambda) t.
So "Lambda(q^T L q) >= 0 for all q in (T_2)^20" is exactly the same as
"t^T H(Lambda) t >= 0 for all t in R^100", which is H(Lambda) >= 0.
6.6 THE KEY PROPOSITION
Proposition. For every (X, Z, y) in Sym^4 x Sym^4 x R^3, the following are
equivalent:
(a) (X, Z, y) is in K.
(b) There exists a linear functional Lambda: E -> R that satisfies the
output conditions (6.4) AND the moment condition H(Lambda) >= 0.
Direction (a) => (b) (the easy direction).
Suppose (X, Z, y) in K. Choose theta_0, eta_0, xi_0 in R with
Y_{theta_0}(eta_0, xi_0) = y. (Always possible since the planes cover R^3.)
Define Lambda_0: E -> R by evaluation at (theta_0, X, Z, eta_0, xi_0):
Lambda_0(f) := f(theta_0; X, Z, eta_0, xi_0) for f in E.
Check output conditions:
Lambda_0(X_{ij}) = X_{ij}. Good (the entry of E-evaluation equals the
numeric matrix entry).
Lambda_0(Z_{ij}) = Z_{ij}. Good.
Lambda_0(eta cos theta) = eta_0 cos theta_0 = Y_{theta_0, 1} = y_1. Good.
Lambda_0(eta sin theta) = eta_0 sin theta_0 = y_2. Good.
Lambda_0(xi * 1) = xi_0 = y_3. Good.
Check moment condition: for any q in (T_2)^20,
Lambda_0(q^T L q) = q(theta_0)^T L_{theta_0}(X, Z, eta_0, xi_0) q(theta_0).
By the slice lemma and (X, Z, y) in K,
L_{theta_0}(X, Z, eta_0, xi_0) >= 0. So the quadratic form is >= 0. So
H(Lambda_0) >= 0.
Direction (b) => (a) (the hard direction). This is Part 7.
Note. The construction of Lambda_0 is elementary and explicit. The
remarkable part is that the converse also holds: ANY Lambda satisfying the
conditions (output + moment) lands you back in K. We do not need Lambda to
be evaluation at a single angle; any feasible Lambda works. This is exactly
Theorem 1 of the paper, and is proved in Part 7.
================================================================================
PART 7. THE MATCHING LEMMA (the central algebraic identity)
================================================================================
7.1 WHAT THE LEMMA MUST DO
In Part 6 we reduced membership in K to: does there exist a linear
functional Lambda with the output conditions and H(Lambda) >= 0. The easy
direction (a) => (b) was done there: every point of K gives such a Lambda
by evaluation at a matching angle. The hard direction is whether every
feasible Lambda comes from some point of K.
For the hard direction we need to squeeze scalar inequalities out of the
moment condition Lambda(q^T L q) >= 0. We will plug in a clever family of
test vectors q (depending on parameters u, D, z) chosen so that
Lambda(q^T L q) collapses to one clean inequality. The whole job of the
matching lemma is to build those test vectors: it produces a trig matrix
C(theta) whose cross terms against L_theta evaluate to exactly the number
tr(S Q(y, z)) we want.
All of this is finite algebra. We just have to write the computation.
7.2 THE PAIRING AND THE BILINEAR FORM
Since Q is quadratic in y, it has a symmetric bilinear form (the
"polarization") defined by
Q(y, z) = (1/2) ( Q(y + z) - Q(y) - Q(z) ).
It is symmetric: Q(y, z) = Q(z, y). And Q(y, y) = Q(y). For example
Q(y, 0) = 0.
For a symmetric 3 x 3 real matrix S (S need NOT be positive semidefinite)
and complex 3 x 2 matrices F, H, define the real number
<F, H>_S = Re tr(F* S H),
where F* is the conjugate transpose of F and tr is trace. This is a
symmetric real bilinear form in (F, H).
There is a second useful formula at the real level. Recall the realification
F~ (Part 5.2): the real 3 x 4 matrix made of real and imaginary parts of the
two columns of F. Then
<F, H>_S = tr( F~^T S H~ ),
because F* S H has real part equal to the trace of the realified product.
7.3 THE STATEMENT
Lemma (Degree-two matching). Let S be a symmetric 3 x 3 real matrix and let
z = (z_1, z_2, z_3) with (z_1, z_2) != (0, 0). Then there exists a complex
3 x 2 matrix C(theta), whose entries are real trigonometric polynomials of
degree at most 2, such that for all real theta, eta, xi:
(i) C~(theta) C~(theta)^T = Q(z),
(ii) <F_theta(eta, xi), C(theta)>_S = tr(S Q(Y_theta(eta, xi), z)).
Recall F_theta(eta, xi) = eta U(theta) + xi V_0 from Part 5.2. Property (i)
says the Gram matrix of C is the constant Q(z); property (ii) is the
matching of the pairing to the number we care about.
7.4 PROOF OF THE LEMMA
The plan: write C(theta) = R_0 M(theta) with a fixed base matrix R_0 whose
Gram matrix is Q(z) and a 2 x 2 unitary M(theta) we get to choose. Any
unitary M preserves the Gram matrix. We choose M to make two pairings
behave: the pairing with V_0 constant, and the pairing with U(theta) a
first harmonic (a combination of cos theta and sin theta). Then we pin
both pairings down by matching their value and one derivative at a single
angle.
Step 1: put z on a slice. Since (z_1, z_2) != (0, 0), there are tau > 0,
alpha real, rho real with
z = tau d(alpha) + rho k,
tau = sqrt(z_1^2 + z_2^2),
(cos alpha, sin alpha) = (z_1, z_2) / tau,
rho = z_3.
Step 2: base matrix and its Gram. Set w_0 = e^{i alpha} and
R_0 = tau U(alpha) + rho V_0.
By the angular Gram factor (Part 5.2), R~_0 R~_0^T = Q(z). So the Gram
matrix we want is already realized by R_0.
Step 3: any unitary M preserves the Gram. Take
M(theta) = [ a(theta) b(theta) ]
[ -conj(b(theta)) conj(a(theta)) ]
Any matrix of this shape with |a|^2 + |b|^2 = 1 is unitary. Put
C(theta) = R_0 M(theta). Then
C~ C~^T = Re(C C*) = Re(R_0 M M* R_0*) = Re(R_0 R_0*) = Q(z),
since M M* = I. So property (i) is automatic for any unitary M.
Step 4: choose M. Let N = S R_0 (3 x 2 complex). Let N_j be the jth row of
N, and form the two-component complex row
v = N_3 - i N_2.
Write v = (v_+, v_-) for its two entries. Define the complex numbers and
the frequency-two scalar
g = v_+ + conj(v_-),
h = v_+ - conj(v_-),
kappa(theta) = (w_0 / w)^2,
delta = |g|^2 + |h|^2.
We want M to satisfy, with v^M = v M,
v^M_+ + conj(v^M_-) = g,
v^M_+ - conj(v^M_-) = h kappa(theta).
Why: the first left side is what controls the pairing with V_0 (see
Step 6); the second multiplies w^3 in the pairing with U (Step 7), and the
factor kappa(theta) lowers that frequency from three to one. The first
condition keeps the V_0 pairing constant; the second keeps the U pairing at
frequency one.
Step 5: solve for a, b. A direct expansion gives
v^M_+ + conj(v^M_-) = g a + conj(h) conj(b) and
v^M_+ - conj(v^M_-) = h a - conj(g) conj(b). So the two conditions are the
linear system
[ g conj(h) ] [ a ] [ g ]
[ h -conj(g)] [ conj(b)] = [ h kappa ].
The coefficient matrix A satisfies A* A = delta I_2 (its two rows are
orthogonal and each has squared norm delta). So for delta > 0 it is
invertible and the unique solution is
a = (|g|^2 + |h|^2 kappa) / delta,
conj(b) = g h (1 - kappa) / delta.
Taking norms gives |a|^2 + |b|^2 = 1, so M is unitary. For delta = 0, take
a = 1 and b = 0 (then g = h = 0 and the system is satisfied).
Degree. The scalars a and conj(b) involve kappa at most once, and
kappa(theta) = w_0^2 w^{-2} has frequency -2. So a(theta) and b(theta) have
frequencies 0 and -2 only, hence degree at most 2. Therefore
C(theta) = R_0 M(theta) has entries of degree at most 2. Also
M(alpha) = I_2 (at theta = alpha, kappa = 1, so a = 1, b = 0), hence
C(alpha) = R_0.
Step 6: the V_0 pairing is constant. Using the formula for V_0 from
Part 5.2, a short computation gives
sqrt(2) <V_0, C(theta)>_S = Re(v^M_+ + v^M_-) = Re(g),
which does not depend on theta. So <V_0, C(theta)>_S is a constant,
independent of theta.
Step 7: the U pairing is a first harmonic. Set m = N_3 + i N_2 and n = N_1,
and write m^M = m M, n^M = n M. If we expand cos theta and sin theta as
powers of w = e^{i theta}, the defining formula for U gives
sqrt(2) <U(theta), C(theta)>_S
= Re[ (1/2) w^3 v^M_+
+ w ( (1/2) m^M_+ - n^M_+ )
- (1/2) w^{-3} v^M_-
+ w^{-1} ( -(1/2) m^M_- - n^M_- ) ].
Inside "Re" we may replace any negative-power term by its complex conjugate
(the real part is unchanged). This leaves
sqrt(2) <U(theta), C(theta)>_S
= Re[ (w^3 / 2) ( v^M_+ - conj(v^M_-) )
+ w ( (1/2) m^M_+ - n^M_+
- (1/2) conj(m^M_-) - conj(n^M_-) ) ].
The first bracket is (w^3 / 2) h kappa = (w^3 / 2) h w_0^2 w^{-2}
= (w / 2) h w_0^2, pure frequency 1.
For the second bracket, note that for any fixed complex row r,
(r M)_+ = r_+ a - r_- conj(b),
conj((r M)_-) = conj(r_+) conj(b) + conj(r_-) a.
Since a and conj(b) have frequencies 0 and -2 only, the entire parenthesis
inside the second bracket has frequencies 0 and -2. Multiplying by
w = e^{i theta} makes the second bracket have frequencies -1 and 1, whose
real part is a combination of cos theta and sin theta.
Conclusion of Step 7: <U(theta), C(theta)>_S is a real linear combination of
cos theta and sin theta. Call this a "first harmonic".
Step 8: match at alpha for V_0. By polarization of the angular Gram factor
in the plane spanned by d(alpha) and k, and because R_0 = tau U(alpha) +
rho V_0 with R~_0 R~_0^T = Q(z), we have
<V_0, R_0>_S = tr(S Q(k, z)),
<U(alpha), R_0>_S = tr(S Q(d(alpha), z)).
(These come from <V_0, R_0>_S = tr(S Q(k, z)) by bilinearity of Q(.,.): the
Gram matrix R~_0 R~_0^T = Q(z) written in the (d(alpha), k) plane, read off
coefficient by coefficient.)
Both sides of the desired identity "<V_0, C(theta)>_S = tr(S Q(k, z))" are
constant in theta, and they agree at theta = alpha (because C(alpha) = R_0).
So they agree for all theta. This proves the V_0 part.
Step 9: match value and derivative at alpha for U. Both
theta -> <U(theta), C(theta)>_S and theta -> tr(S Q(d(theta), z)) are first
harmonics (the second because d(theta) = (cos theta, sin theta, 0) and Q is
quadratic, so the right side is a combination of cos 2theta, sin 2theta,
and constants via cos^2, sin^2, cos sin). A first harmonic is fully
determined by its value and its derivative at one angle. They agree at
alpha by Step 8. So we only need to compare derivatives at alpha.
Derivative of the U pairing. Constancy of the V_0 pairing (Step 6) gives
<V_0, C'(alpha)>_S = 0.
The Gram identity <C(theta), C(theta)>_S = tr(S Q(z)) is constant, so
differentiating gives 2 <C(alpha), C'(alpha)>_S = 0, i.e.
<R_0, C'(alpha)>_S = 0.
Since R_0 = tau U(alpha) + rho V_0 with tau > 0, these two facts force
<U(alpha), C'(alpha)>_S = 0.
Derivative of the target. Differentiate the Gram identity
<tau U(theta) + rho V_0, tau U(theta) + rho V_0>_S
= tr(S Q(tau d(theta) + rho k))
with respect to theta and evaluate at alpha; divide by 2 tau. Because
tau U(alpha) + rho V_0 = R_0, this gives
<U'(alpha), R_0>_S = tr(S Q(d'(alpha), z)).
Now put the two derivative pieces together. The derivative of
theta -> <U(theta), C(theta)>_S at alpha is
<U'(alpha), C(alpha)>_S + <U(alpha), C'(alpha)>_S
= <U'(alpha), R_0>_S + 0
= tr(S Q(d'(alpha), z)).
So at alpha, <U(theta), C(theta)>_S and tr(S Q(d(theta), z)) have the same
value (Step 8) and the same derivative. Since both are first harmonics, they
are equal for all theta.
Step 10: assemble. The two identities just proved are
<V_0, C(theta)>_S = tr(S Q(k, z)),
<U(theta), C(theta)>_S = tr(S Q(d(theta), z)),
both for all theta. By bilinearity in the first slot (in eta, xi) and in
the second (in z, since Q(.,.) is bilinear),
<eta U(theta) + xi V_0, C(theta)>_S
= eta tr(S Q(d(theta), z)) + xi tr(S Q(k, z))
= tr(S Q(eta d(theta) + xi k, z))
= tr(S Q(Y_theta(eta, xi), z)).
That is property (ii). Property (i) was Step 3. The lemma is proved.
7.5 HOW THE LEMMA FEEDS THE LIFT
The lemma says: given any symmetric S and any nonzero (z_1, z_2), we can
build test columns whose cross pairing against F_theta equals
tr(S Q(Y_theta, z)). In Part 8 we take S = J_u D J_u^T, so this pairing
becomes tr(J_u D J_u^T Q(Y_theta, z)), exactly the cross term of the
matrix pencil. The theta-dependence cancels, which is the whole miracle.
================================================================================
PART 8. THE HARD DIRECTION: ANY FEASIBLE LAMBDA LANDS IN K
================================================================================
Now we prove direction (b) => (a) of the Proposition in Part 6.6. We assume
Lambda satisfies the output conditions and the moment condition
H(Lambda) >= 0, and we show the target point (X, Z, y) actually lies in K.
By the slice lemma (Part 5.4) it is enough to find one angle theta and
real eta, xi with Y_theta(eta, xi) = y such that L_theta(X, Z, eta, xi) is
positive semidefinite. Fix such (theta, eta, xi) once and for all. Then
Y_theta(eta, xi) = y, and the r_j are the columns of F~_theta(eta, xi);
write B_j = B(r_j). We will show L_theta(X, Z, eta, xi) >= 0.
8.1 FIRST, X IS POSITIVE SEMIDEFINITE
Take q in (T_2)^20 to be a CONSTANT (degree 0) vector whose only nonzero
block is the j-th of the four top 4-blocks, set equal to a fixed vector
v in R^4. Then q^T L_theta q = v^T (I_4 block j) v part = v^T X v (the
bottom block of q is zero, so no Z term and no cross term appear). More
carefully, with q = (0,...,0, v at block j, 0,...,0, 0):
q^T L_theta q = v^T X v.
This is an element of E that is constant in theta and linear in X. Applying
Lambda, and using the output condition Lambda(X_{ij}) = X_{ij}, gives
Lambda(q^T L_theta q) = v^T X v.
The moment condition says this is >= 0 for every v. Hence X >= 0 (positive
semidefinite). This holds whether or not X is invertible.
8.2 BUILDING THE TEST VECTOR FROM THE MATCHING LEMMA
Fix u in R^4, D in Sym^4, and z in R^3 with (z_1, z_2) != (0, 0). Define
the symmetric 3 x 3 matrix
S = J_u D J_u^T (S is allowed to be indefinite).
Apply the matching lemma (Part 7) with this S. It gives a complex matrix
C(theta), whose realification C~(theta) is a real 3 x 4 matrix; call its
four columns b_1(theta), b_2(theta), b_3(theta), b_4(theta). Each b_j is a
real 3-vector with trig-polynomial entries of degree at most 2.
Define the 20-component test vector q(theta) in blocks:
q(theta) = ( -D J_u^T b_1(theta), <- first 4-block
-D J_u^T b_2(theta), <- second 4-block
-D J_u^T b_3(theta), <- third 4-block
-D J_u^T b_4(theta), <- fourth 4-block
u ) <- bottom 4-block.
Each of the first four blocks is a 4-vector whose entries are linear
combinations of the entries of b_j, hence trig of degree at most 2. The
bottom block u is constant. So q is in (T_2)^20. Good.
8.3 COMPUTING q^T L q
Write L_theta in its block form (Part 5.4):
row blocks 1..4 = the top part [ I_4 (x) X | B_theta ],
row block 5 = the bottom part [ B_theta^T | Z ],
where B_theta is the 16 x 4 stack of B_1, B_2, B_3, B_4. For a test vector
q = (q_1, q_2, q_3, q_4, q_5) with each q_j in R^4, the quadratic form is
q^T L q = sum_{j=1}^4 q_j^T X q_j
+ 2 sum_{j=1}^4 q_j^T B_j q_5
+ q_5^T Z q_5.
(Because the cross terms are q_j^T B_theta applied to q_5, and B_theta's
j-th 4-row block is B_j; and the top-left is block-diagonal I_4 copies of X.)
Plug in q_j = -D J_u^T b_j for j = 1..4 and q_5 = u.
Top blocks. sum_j q_j^T X q_j = sum_j (-D J_u^T b_j)^T X (-D J_u^T b_j)
= sum_j b_j^T J_u D X D J_u^T b_j. Now sum_j b_j b_j^T is exactly
C~ C~^T = Q(z) (matching lemma, property (i)). Therefore
sum_j q_j^T X q_j = tr( J_u D X D J_u^T Q(z) ).
This removed all theta dependence from the top contribution.
Cross terms. 2 sum_j q_j^T B_j u = 2 sum_j (-D J_u^T b_j)^T B_j u
= -2 sum_j b_j^T J_u D B_j u. Use the identity B_j u = J_u^T r_j
(Part 5.3). Then
2 sum_j q_j^T B_j u = -2 sum_j b_j^T J_u D J_u^T r_j.
The sum sum_j b_j^T (J_u D J_u^T) r_j is the trace of F~^T S C~ with
S = J_u D J_u^T. But by the second formula in Part 7.2, that trace is
<F_theta(eta,xi), C(theta)>_S. By the matching lemma, property (ii), this
equals tr(S Q(Y_theta(eta,xi), z)) = tr(J_u D J_u^T Q(Y_theta(eta,xi), z)).
So
2 sum_j q_j^T B_j u = -2 tr( J_u D J_u^T Q(Y_theta(eta,xi), z) ).
Since Y_theta(eta,xi) = y, this is linear in (eta, xi) and has no bare
theta left (it depends on theta only through Y_theta, which is linear in
cos theta, sin theta - but we already fixed the slice, and after applying
Lambda we will substitute the output condition).
Bottom block. q_5^T Z q_5 = u^T Z u.
Putting these three pieces together:
q^T L_theta q
= u^T Z u
+ tr( J_u D X D J_u^T Q(z) )
- 2 tr( J_u D J_u^T Q(Y_theta(eta,xi), z) ).
8.4 APPLYING LAMBDA (THE CERTIFICATE)
The right-hand side above is an element of E: linear in (X, Z, eta, xi).
Applying Lambda and using the output conditions Lambda(X) = X, Lambda(Z) = Z,
Lambda(Y_theta(eta,xi)) = y:
Lambda(q^T L_theta q)
= u^T Z u
+ tr( J_u D X D J_u^T Q(z) )
- 2 tr( J_u D J_u^T Q(y, z) ).
The moment condition says this is >= 0. So for every u in R^4, D in Sym^4,
and every z with (z_1, z_2) != (0,0):
u^T Z u + tr( J_u D X D J_u^T Q(z) )
- 2 tr( J_u D J_u^T Q(y, z) ) >= 0. [CERT]
8.5 EXTENDING [CERT] TO ALL z
For fixed u and D, the left side of [CERT] is a polynomial in z of degree
at most 2 (Q(z) is quadratic; Q(y,z) is linear in z). It is >= 0 on the
open dense set {(z_1, z_2) != (0,0)}. A polynomial that is nonnegative on
a dense open set is nonnegative everywhere (by continuity). So [CERT]
holds for every z in R^3.
Note: we extend only this scalar inequality - not any function C(theta).
The complex matrix C(theta) was a tool for building the test vector; its
continuity never enters.
8.6 THE POSITIVE DEFINITE CASE
Suppose X is positive definite (invertible, with X > 0). Set z = y and
D = X^{-1} in [CERT]. Since D X D = X^{-1} X X^{-1} = X^{-1}, the middle
term is tr(J_u X^{-1} J_u^T Q(y)) = u^T Phi_y(X^{-1}) u, using the identity
u^T Phi_y(W) u = tr(J_u W J_u^T Q(y)) (Part 5.3, eq Phi-quadratic). The
last term, with z = y, is -2 tr(J_u X^{-1} J_u^T Q(y, y)); and Q(y, y) =
Q(y), so it is -2 u^T Phi_y(X^{-1}) u. Thus [CERT] reads
u^T Z u + u^T Phi_y(X^{-1}) u - 2 u^T Phi_y(X^{-1}) u
= u^T ( Z - Phi_y(X^{-1}) ) u >= 0.
This holds for every u. So Z - Phi_y(X^{-1}) >= 0, i.e.
Z >= Phi_y(X^{-1}). Combined with X > 0, the Schur complement criterion
(Part 1.2) gives L_theta(X, Z, eta, xi) >= 0. By the slice lemma, (X,Z,y)
is in K.
8.7 THE SINGULAR CASE, PART A: THE RANGE CONDITION
Now X is only positive semidefinite; its kernel may be nontrivial. We still
want L_theta >= 0. Fix v in ker X (so X v = 0), and pick D = t v v^T for a
real number t; take z = y in [CERT].
Middle term. D X D = t^2 (v v^T) X (v v^T) = t^2 v (v^T X v) v^T = 0,
since X v = 0. So the middle term vanishes.
Last term. With z = y it becomes -2 tr(J_u D J_u^T Q(y, y)) with D = t v v^T.
Since Q(y, y) = Q(y), this is -2t (J_u v)^T Q(y) (J_u v): a scalar linear in
t. Write c = (J_u v)^T Q(y) (J_u v), which is >= 0 because Q(y) >= 0.
So [CERT] becomes u^T Z u - 2 t c >= 0 for all t in R. Since u^T Z u and c
are fixed real numbers and t can be positive or negative, a linear-in-t
expression bounded below by 0 on all of R must have slope 0. Hence c = 0:
(J_u v)^T Q(y) (J_u v) = 0.
By the Gram factorization Q(y) = sum_j r_j r_j^T (Part 5.2 with z = y on
our slice; note the r_j are exactly the columns of F~_theta(eta,xi)),
we get
0 = (J_u v)^T Q(y) (J_u v) = sum_j ( r_j^T J_u v )^2
= sum_j ( (B_j u)^T v )^2.
The last equality used J_u^T r_j = B_j u (Part 5.3). Every square is >= 0,
so the sum being 0 forces each term 0:
(B_j u)^T v = 0 for every j = 1..4, every u in R^4, every v in ker X.
Since u and v are arbitrary, this says B_j u is orthogonal to ker X for all
u, i.e. B_j u lies in (ker X)^perp = range X (X is symmetric). Therefore
range B_j is contained in range X, j = 1, 2, 3, 4. [RANGE]
8.8 THE SINGULAR CASE, PART B: THE SCHUR INEQUALITY
Let X^dagger be the pseudoinverse of X: it acts as X^{-1} on range X (the
positive eigenvalues) and as 0 on ker X. It satisfies the identity
X^dagger X X^dagger = X^dagger.
Take D = X^dagger and z = y in [CERT]. The middle term is
tr(J_u X^dagger J_u^T Q(y)) = u^T Phi_y(X^dagger) u, and the last term with
z = y is -2 u^T Phi_y(X^dagger) u. So [CERT] gives
u^T Z u - u^T Phi_y(X^dagger) u = u^T ( Z - Phi_y(X^dagger) ) u >= 0
for all u. Hence
Z >= Phi_y(X^dagger). [PSCHUR]
Also, by eq Phi-factor (Part 5.3), Phi_y(X^dagger) = sum_j B_j^T X^dagger B_j.
So [PSCHUR] says Z - sum_j B_j^T X^dagger B_j >= 0.
8.9 THE SINGULAR CASE, PART C: COMPLETING THE SQUARE
We now verify L_theta(X, Z, eta, xi) >= 0 directly. Let (a_1, a_2, a_3, a_4, w)
be an arbitrary 20-vector, with a_j in R^4 and the bottom part w in R^4.
The quadratic form of L_theta at this vector is
F = sum_{j=1}^4 a_j^T X a_j + 2 sum_{j=1}^4 a_j^T B_j w + w^T Z w.
We claim
F = sum_{j=1}^4 (a_j + X^dagger B_j w)^T X (a_j + X^dagger B_j w)
+ w^T ( Z - sum_{j=1}^4 B_j^T X^dagger B_j ) w. [SQUARE]
Expand the right side. The j-th squared term is
a_j^T X a_j + 2 a_j^T X X^dagger B_j w + w^T B_j^T X^dagger X X^dagger B_j w.
By [RANGE], B_j w lies in range X, on which X X^dagger acts as the identity;
so X X^dagger B_j w = B_j w, making the cross term 2 a_j^T B_j w, as needed.
The w-quadratic term from the j-sum is
w^T B_j^T ( X^dagger X X^dagger ) B_j w = w^T B_j^T X^dagger B_j w,
using X^dagger X X^dagger = X^dagger. Adding the explicit
- w^T sum_j B_j^T X^dagger B_j w from the last bracket cancels it exactly.
What is left is exactly F. So [SQUARE] holds.
Now bound the two pieces of [SQUARE]:
- Each (a_j + X^dagger B_j w)^T X (a_j + X^dagger B_j w) >= 0 because
X >= 0 (shown in 8.1). Sum >= 0.
- The last factor Z - sum_j B_j^T X^dagger B_j is >= 0 by [PSCHUR].
Hence F >= 0 for every choice of (a_1,...,a_4, w). So the symmetric matrix
L_theta(X, Z, eta, xi) is positive semidefinite.
8.10 CONCLUSION OF THE HARD DIRECTION
We fixed any angle theta and slice parameters (eta, xi) with Y_theta(eta,xi)
= y, and showed L_theta(X, Z, eta, xi) >= 0 (in the positive definite case
via 8.6, in the singular case via 8.9). The slice lemma (Part 5.4) then
gives (X, Z, y) in K.
This completes direction (b) => (a) of the Proposition in Part 6.6, for an
ARBITRARY feasible Lambda. In particular we never needed Lambda to be an
evaluation functional or an integral against a measure, and we never needed
any closure or continuity of the projected feasible set. The matching lemma
(Part 7) was the only extra ingredient, and it is pure finite algebra.
================================================================================
PART 9. THE 100 x 100 PENCIL AND THE MAIN THEOREM
================================================================================
9.1 COUNTING FREE PARAMETERS
Recall the ambient space E (Part 6.3). It consists of trig polynomials of
degree at most 7 with coefficients linear in the 22 coordinates
(X_{ij} for i <= j, Z_{ij} for i <= j, eta, xi). The real trig polynomials
of degree at most 7 have basis
1, cos theta, sin theta, ..., cos 7theta, sin 7theta,
which is 1 + 2*7 = 15 functions. So
dim E = 22 * 15 = 330.
The output conditions (Part 6.4) pin down 23 specific coordinates of the
functional Lambda in E*:
Lambda(X_{ij}) = X_{ij} for 1 <= i <= j <= 4 (10 numbers),
Lambda(Z_{ij}) = Z_{ij} for 1 <= i <= j <= 4 (10 numbers),
Lambda(eta cos theta) = y_1,
Lambda(eta sin theta) = y_2,
Lambda(xi * 1) = y_3 (3 numbers).
These 23 are independent members of the coordinate basis of E* (each
corresponds to a different basis function of E). They pin down exactly 23 of
the 330 coordinates of Lambda. The remaining
330 - 23 = 307
coordinates are completely free. Call them v_1, ..., v_307.
9.2 THE PENCIL
Now form the 100 x 100 matrix H(Lambda) of Part 6.5. Every entry of H is
Lambda applied to some basis element of E, so H is a linear function of the
330 Lambda-coordinates. Substitute:
- 23 of the coordinates are replaced by the fixed target numbers
X, Z, y (exactly as prescribed by the output conditions);
- the other 307 coordinates are replaced by the free numbers v_1,...,v_307.
The result is a fixed 100 x 100 real symmetric matrix that is linear and
homogeneous in (x, v), where x = (X, Z, y) in R^23 collects all the pinning
data. Concretely there are fixed symmetric matrices A_1, ..., A_23 and
B_1, ..., B_307, all 100 x 100, such that
H(Lambda) = sum_{nu=1}^{23} x_nu A_nu + sum_{j=1}^{307} v_j B_j.
There is NO constant term, because every entry of H is linear homogeneous in
the Lambda-coordinates and every Lambda-coordinate is either an x_nu or a
v_j (and each enters linearly, with no bare constant).
9.3 THE MAIN THEOREM
Theorem. Let p, e, K be as in Part 4 (K is the hyperbolicity cone of p with
respect to e, a closed convex cone in R^23). There exist fixed symmetric
100 x 100 matrices A_1, ..., A_23 and B_1, ..., B_307 such that for every
x = (X, Z, y) in R^23:
x is in K
<==> there exists v in R^307 with
sum_{nu=1}^{23} x_nu A_nu + sum_{j=1}^{307} v_j B_j
>= 0 (as a 100 x 100 PSD matrix).
The equivalence holds on the whole closed cone, including points where X is
singular.
Proof. Build H(Lambda) as in Part 9.2. By Part 6.6, the statement "there
exists a Lambda with output conditions and H(Lambda) >= 0" is equivalent to
choosing v in R^307 with the displayed PSD condition; the "output
conditions" simply ARE the substitution of x = (X,Z,y) for the 23 pinned
coordinates. Then the Proposition in Part 6.6 says this equivalent to (X,Z,y)
in K for direction (a) => (b), and Part 8 says (b) => (a) for an arbitrary
feasible Lambda. Hence the displayed existence statement holds if and only
if x is in K. QED.
So K is a spectrahedral shadow (a "semidefinite lift"): it is the projection
of a spectrahedron in R^(23+307) = R^330 down to R^23. The matrix size is
N = 100 and the number of auxiliary variables is m = 307.
9.4 WHAT THIS DOES AND DOES NOT SAY
- It does NOT say 100 and 307 are smallest. They are one explicit valid
pair. Nothing in the proof relies on minimality.
- It does NOT claim the lift is unique. Any Lambda subject to the two
families of conditions (output + moment) works; there may be many.
- It DOES say K is a spectrahedral shadow, i.e. a linear projection of a
spectrahedron in a larger space, even though:
Companion fact (from the earlier paper, cite "parent"; Theorem 1.1 there).
The same cone K has NO homogeneous semidefinite representation in its own
23 coordinates. That is, there is no fixed tuple of 23 symmetric matrices
A_1, ..., A_23 (of any size) with
x in K <==> sum_nu x_nu A_nu >= 0.
And no affine representation
x in K <==> A_0 + sum_nu x_nu A_nu >= 0
either. (Reduction: if K, which contains 0, equals such an affine set, then
A_0 >= 0; for x in K and t > 0, A_0/t + sum x_nu A_nu >= 0, and letting
t -> infinity gives sum x_nu A_nu >= 0. Conversely that implies
A_0 + sum x_nu A_nu >= 0. So an affine representation of a cone containing
0 is really a homogeneous one after all.)
Therefore K is a genuine example of a shape that is NOT a spectrahedron in
its own coordinates, yet IS a spectrahedral shadow once a few hundred extra
variables are allowed. Auxiliary variables make all the difference here.
We used the companion paper only for this comparison. The proof of the main
theorem above is self-contained: Parts 5, 6, 7, 8 and 9 do not rely on the
companion result except for the impossibility sentence in the last
paragraph.
9.5 WHY THE ANGULAR PARAMETER DOES NOT NEED TO BE REMEMBERED
A reader might worry: the lift sits on the infinite family of slices indexed
by theta, and Lambda "remembers" a whole trig polynomial's worth of
information. Does the lift secretly depend on theta?
It does not. Here is what happens:
- The easy direction (a) => (b) uses a single evaluation angle theta_0 and
produces a feasible Lambda. That is fine.
- The hard direction (b) => (a) works for ANY feasible Lambda, whether or
not it is a single evaluation. The matching lemma converts the moment
inequality into scalar inequalities that no longer mention theta: the
theta-dependence cancels at the level of the test vectors (the first
harmonic facts in Part 7 make it cancel; see Part 8.3, where the cross
term becomes a plain function of Y_theta, and then the output condition
replaces Y_theta by y).
So the finite 100 x 100 pencil is a genuine finite object. The angle theta
never has to be recovered from Lambda. The lifting functional can be quite
far from any single evaluation, and the cone membership test still holds.
9.6 THE WHOLE PROOF IN SIX LINES
For a reader who wants the skeleton before the flesh:
1. Write p as a determinant of a 20 x 20 slice pencil L_theta on each
angular plane y = Y_theta(eta, xi). This makes K a family of spectrahedra
indexed by theta, exactly (Part 5).
2. Encode "nonnegative on q^T L_theta q for all degree-2 test vectors q" as
one 100 x 100 PSD condition H(Lambda) >= 0, with Lambda a linear
functional on degree-7 trig polynomials (Part 6).
3. Show every point of K gives a feasible Lambda by evaluation at a single
angle (Part 6.6, easy direction).
4. Prove the matching lemma: build degree-2 trig test columns that turn the
cross term of L_theta into tr(S Q(y, z)), independent of the angle
(Part 7).
5. Use those test columns to prove the converse: any feasible Lambda forces
X >= 0, the certificate inequality, the range condition, and the
pseudoinverse Schur inequality, which together give L_theta >= 0 on the
slice, hence (X, Z, y) in K (Part 8).
6. Count coordinates: 330 - 23 = 307 free, giving a fixed 100 x 100 matrix
pencil with zero constant term (Part 9).
That is the whole paper.
9.7 ONE CONCRETE CHECK A READER CAN DO BY HAND
Take y = (0, 0, 1), theta = 0, eta = 0, xi = 1. Then d(0) = (1, 0, 0), and
Y_0(0, 1) = (0, 0, 1). On this trivial slice the whole machinery reduces to
a 20 x 20 verification. The angular Gram factor at (theta, eta, xi) =
(0, 0, 1) is F = xi V_0 = V_0, whose realification V~_0 satisfies
V~_0 V~_0^T = Q(0, 0, 1) = diag(0, 1, 1). (Indeed Q_11 = y_1^2 + y_2^2 = 0,
Q_22 = y_2^2 + y_3^2 = 1, Q_33 = y_3^2 + y_1^2 = 1 at y = (0, 0, 1).) Check:
V_0 = (1/sqrt2) [ 0 0 ]
[ i i ]
[ 1 1 ]
Columns are f_1 = (0, i, 1)/sqrt2, f_2 = (0, i, 1)/sqrt2 (identical here).
Realification: Re f_1 = (0, 0, 1)/sqrt2, Im f_1 = (0, 1, 0)/sqrt2, and the
same for f_2. So
V~_0 = (1/sqrt2) [ 0 0 0 0 ]
[ 0 1 0 1 ]
[ 1 0 1 0 ],
and V~_0 V~_0^T has entries: row 1 all zero, row 2 dot row 2 = (0+1+0+1)/2
= 1, row 3 dot row 3 = (1+0+1+0)/2 = 1, row 2 dot row 3 = 0. That is the
matrix diag(0, 1, 1), which matches Q(0,0,1) = diag(0, 1, 1) exactly - no
coordinate relabeling needed. So the Gram factorization is correct on this simple
slice, and the reader can watch the slice pencil L_theta become an honest
20 x 20 PSD test.
================================================================================
END OF THE PROOF
================================================================================