The Kadison-Singer Conjecture

We are given a large integer N, and a fixed basis {ei: 1 ≤ i ≤ N} for the space H = CN. 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σ:= ∨{ei: 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σiHPσ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) 1 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/ 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) simultane-ously 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 Pk denote Pσ, and assume that PkHPk ≤ CkIk. We wish to choose i in {k+1,..., N} so that, if σ ′ = σ∪{i} and Pk+1: = Pσ ′, then Pk+1HPk+1 < Ck+1Ik+1, (2.2) with Ck+1 = Ck + εk as small as possible. Let ui be the k-vector PkHei. Lemma 2.3 Inequality (2.2) holds, with εk ≥ 0, if and only if Ck+1> 〈(Ck+1 − PkHPk)−1ui, ui〉. 2 Proof: This is just the condition for something in block matrix form to be positive definite. 2 Let the eigenvalues of PkHPk be µ k 1 ≥ µk2 ≥... ≥ µkk, and let the corre-sponding orthonormal eigenvectors be wj. If ε is so small that (2.2) fails for every i, with Ck+1 = Ck + ε, then (N − k) (Ck + ε) < N∑ i=k+1 〈(Ck + ε − PkHPk)−1ui, ui〉 N∑ i=k+1 k∑ j,l=1 〈(Ck + ε − PkHPk)−1〈ui, wj〉wj, 〈ui, wl〉wl〉 k