The Kadison-Singer Conjecture

John E. McCarthy

April 18, 2006

1 Set-up

We are given a large integer N, and a fixed basis {e_{i} : 1 ≤ i ≤ N} for the space H = ℂ^{N}. We are also given an N-by-N matrix H that has all its diagonal entries zero, and has norm one.

If σ ⊆ {1, 2, …, N}, let P_{σ} be the projection onto the space H_{σ} := ∨{e_{i} : i ∈ σ}. Call such a projection basic, and the range of a basic projection a basic subspace.

For each constant 0 < γ < 1, we want to know

K(H, γ) := max{|σ| : ∥P_{σ}HP_{σ}∥ ≤ γ}  (1.1)

and

Π(H, γ) := min{k : there is a partition σ_{1}, …, σ_{k} of {1, …, N}
such that ∀ i, ∥P_{σ_{i}}HP_{σ_{i}}∥ ≤ γ }.  (1.2)

The Kadison-Singer conjecture [3] is equivalent to the assertion that for each γ, there is a universal bound on Π(H, γ) that is independent of H and N.

For the Kadison-Singer conjecture to hold, it is clearly necessary that there exists some constant c_{γ} > 0 such that

K(H, γ) ≥ c_{γ}N.  (1.3)

In [1], K. Berman, H. Halpern, V. Kaftal and G. Weiss proved that there exists a self-adjoint Hadamard matrix H (a unitary all of whose entries have modulus 1/\sqrt{N}) such that, if you drop the diagonal and renormalize,

Π(H, γ) ≈ γ^{−2}.

In [2], J. Bourgain and L. Tzafiri proved that there exists a universal constant C (of order 10^{−7}) such that

K(H, γ) ≥ Cγ^{2} ∀ H.  (1.4)

2 An approach to K(γ, H)

For now, let us assume that H is self-adjoint, and try to find a large σ so that the one-sided inequality

P_{σ}HP_{σ} ≤ γI  (2.1)

holds. (Later, we hope to extend the method to satisfying (2.1) simultaneously with several operators; if they are H and −H, we would get a bound on ∥H∥).

Assume that σ of size k has been chosen; after relabelling the indices, let us assume that σ = {1, …, k}. Let P_{k} denote P_{σ}, and assume that

P_{k}HP_{k} ≤ C_{k}I_{k}.

We wish to choose i in {k+1, …, N} so that, if σ′ = σ∪{i} and P_{k+1} := P_{σ′}, then

P_{k+1}HP_{k+1} < C_{k+1}I_{k+1},  (2.2)

with C_{k+1} = C_{k} + ε_{k} as small as possible.

Let u^{i} be the k-vector P_{k}He_{i}.

Lemma 2.3 Inequality (2.2) holds, with ε_{k} ≥ 0, if and only if

C_{k+1} > ⟨(C_{k+1} − P_{k}HP_{k})^{−1}u^{i}, u^{i}⟩.

Proof: This is just the condition for something in block matrix form to be positive definite. □

Let the eigenvalues of P_{k}HP_{k} be μ_{1}^{k} ≥ μ_{2}^{k} ≥ … ≥ μ_{k}^{k}, and let the corresponding orthonormal eigenvectors be w_{j}. If ε is so small that (2.2) fails for every i, with C_{k+1} = C_{k} + ε, then

(N − k) (C_{k} + ε) < ∑_{i=k+1}^{N}⟨(C_{k} + ε − P_{k}HP_{k})^{−1}u^{i}, u^{i}⟩
= ∑_{i=k+1}^{N} ∑_{j,l=1}^{k}⟨(C_{k} + ε − P_{k}HP_{k})^{−1}⟨u^{i}, w_{j}⟩w_{j}, ⟨u^{i}, w_{l}⟩w_{l}⟩
= ∑_{j=1}^{k} ∑_{i=k+1}^{N} |⟨u^{i}, w_{j}⟩|^{2} \frac{1}{C_{k} + ε − μ_{j}}
= ∑_{j=1}^{k} \frac{∥(I − P_{k})Hw_{j}∥^{2}}{C_{k} + ε − μ_{j}}
≤ ∑_{j=1}^{k} \frac{1}{C_{k} + ε − μ_{j}} .

Therefore we have

Lemma 2.4 The smallest attainable ε_{k} is less than or equal to that value of ε where the decreasing function

∑_{j=1}^{k} \frac{1}{C_{k} + ε − μ_{j}^{k}}

equals (N − k)C_{k}.

The very crude estimate μ_{j}^{k} ≤ C_{k} for each j would give the bound

ε_{k} ≤ \frac{k}{(N − k)C_{k}} ,

but this is not sharp enough.

3 Weyl’s inequality

Weyl’s inequality for self-adjoint n-by-n matrices A, B and D with A+B = D is that

μ_{j}(D) ≤ μ_{j−m+1}(A) + μ_{m}(B)  (3.1)

for 1 ≤ m ≤ j ≤ n, where μ_{j}(A) is the j^{th} largest eigenvalue of A. If we apply this to P_{k+1}HP_{k+1}, which we think of the sum of the matrix

A_{k} = ( 0 ; P_{k}HP_{k}  0 ; ⋮ ; 0  0  ⋯ 0 )

with the rank two, trace zero, matrix

B = u^{i} ⊗ e_{k+1} + e_{k+1} ⊗ u^{i},

and let m = 2, we get that, for 2 ≤ j ≤ k + 1,

μ_{j}^{k+1}(P_{k+1}HP_{k+1}) ≤ μ_{j−1}(A_{k})
≤ max(μ_{j−1}^{k}, 0).  (3.2)

Applying (3.2) inductively to Lemma 2.4, we get

Lemma 3.3

(N − k)C_{k+1} ≤ ∑_{j=1}^{k} \frac{1}{C_{k+1} − C_{j}} .  (3.4)

Equation (3.4) gives, I think, that

C_{k} = O(k log(k)/N)^{1/2},

which is logarithmically worse than (1.4).

4 Tightening it up

One can redo the arguments in Section 3 and Lemma 2.4 to keep track of all the eigenvalues at once. Indeed, typically (ie unless the first component of u with respect to the basis w_{1}, …, w_{k} is 0) the second eigenvalue at the k + 1^{st} stage will be strictly smaller than the largest eigenvalue at the k^{th} stage.

Indeed, look at C − A_{k+1}, for some constant C, and take the Schur complement for the (k + 1)-by-(k + 1) slot.

C − A_{k+1} = ( \begin{matrix}C − μ_{1} & 0 & ⋯ & 0 & −u_{1} \\ 0 & C − μ_{2} & ⋯ & 0 & −u_{2} \\ 0 & 0 & ⋯ & C − μ_{k} & ⋮ \\ −\overline{u_{1}} & −\overline{u_{2}} & ⋯ & & C \end{matrix} ) ,

where we suppress the superscripts and write u_{j} for ⟨u^{i}, w_{j}⟩.

This gives that the signature (number of positive minus number of negative eigenvalues) for C − A_{k+1} is the same as the sum for the k-by-k matrix C − A_{k} and the 1-by-1 matrix

C − ∑_{j=1}^{k} \frac{|u_{j}|^{2}}{C − μ_{j}} .  (4.1)

As C varies, looking at the sign changes in (4.1) one gets that the new eigenvalues are the intercepts of the function

F (x) = ∑_{j=1}^{k} \frac{|u_{j}|^{2}}{x − μ_{j}^{k}}

with the function G(x) = x. (If u_{j} ≠ 0, one doesn’t get a sign change in the signature at μ_{j}).

Looking at a picture of the graphs of F and G, if the old (k^{th} stage) eigenvalues with an extra 0 added are

μ′_{1} ≥ μ′_{2} ≥ … ≥ μ′_{k+1}

and the new ones are ν_{1} ≥ … ≥ ν_{k+1}, then

|ν_{j}| ≥ |μ_{j}| ∀ j.

So as the Hilbert-Schmidt norm squared of the matrix equals the sum of the squares of the eigenvalues, writing ν_{j} = μ_{j} + ε_{j}, we get

2 ∑ |ε_{j}||μ_{j}| + ∑ ε_{j}^{2} = 2 ∑ |u_{j}|^{2}.  (4.2)

The game then is to show that the solutions of F (x) = x don’t grow to fast as k increases. If the largest root goes up a lot, then by (4.2) the others can’t change much. So at the next stage the largest root does not increase much (draw picture of F (x) to see this).

5 Case u_{j} = \frac{1}{\sqrt{N}}

In this case, the solutions of F (x) = x are the roots of the polynomial q_{k+1}, where, after rescaling by y = \sqrt{N}x, we have q_{1}(y) = y, and

q_{k+1}(y) = yq_{k}(y) − q′_{k}(y).

One then wants the largest root of q_{k} to be O(\sqrt{k}). The q_{k}’s turn out to be approximately the Hermite polynomials, for which indeed the largest root is O(\sqrt{k}).

6 Possible Refinements

1. There are several analogies with orthogonal polynomials; if one believes they are profound, one could be led to the conjecture that

|μ_{j}^{k}| = O (\sqrt{\frac{k}{N}} cos [\frac{j − 1}{k − 1}π]) .

2. The estimate preceding Lemma 2.4 is sharp only if all the terms are the same — if some u^{i}’s actually contribute a lot to the sum, others will contribute less. Can this be exploited?

3. It seems one cannot rule out occasional large jumps. For example, suppose N is a power of 2, and H is the tensor product of

\frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} )

with itself may times. (The diagonal entries of H are not 0, but ±1/\sqrt{N}; this doesn’t really matter). If you choose the indices in order, then at the k = 2^{l} stage, you have 2^{l−1} eigenvalues of size \sqrt{\frac{k}{N}}, and the other half are −\sqrt{\frac{k}{N}}.

At the k + 1 stage, one eigenvalue leaps to \sqrt{\frac{2^{l+1}}{N}}, a large increase. But for each successive step up to the 2^{l+1} stage, you get one more eigenvalue with size \sqrt{\frac{2^{l+1}}{N}}, without any increase in the largest eigenvalue. By the time you reach 2k, the overall norm of the compression has gone up only by a factor of \sqrt{2}, but it did it all in one step.

References

[1] K. Berman, H. Halpern, V. Kaftal, and G. Weiss. Matrix norm inequalities and the relative Dixmier property. Integral Equations and Operator Theory, 1:28–48, 1988.

[2] J. Bourgain and L. Tzafiri. On a problem of kadison and singer. J. Reine Angew. Math., 420:1–43, 1991.

[3] R. Kadison and I. Singer. Extensions of pure states. Amer. J. Math., 81:547–564, 1959.