Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem

Abstract

We use the method of interlacing polynomials introduced in our previous article to prove two theorems known to imply a positive solution to the Kadison–Singer problem. The first is Weaver’s conjecture $\mathrm{KS}_{2}$, which is known to imply Kadison–Singer via a projection paving conjecture of Akemann and Anderson. The second is a formulation due to Casazza et al. of Anderson’s original paving conjecture(s), for which we are able to compute explicit paving bounds. The proof involves an analysis of the largest roots of a family of polynomials that we call the “mixed characteristic polynomials” of a collection of matrices.

Note: To view the article, click on the URL link for the DOI number.

  • [AhlswedeWinter] Go to document R. Ahlswede and A. Winter, "Strong converse for identification via quantum channels," IEEE Trans. Inform. Theory, vol. 48, iss. 3, pp. 569-579, 2002.
    @article{AhlswedeWinter, mrkey = {1889969},
      author = {Ahlswede, Rudolf and Winter, Andreas},
      title = {Strong converse for identification via quantum channels},
      journal = {IEEE Trans. Inform. Theory},
      fjournal = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory},
      volume = {48},
      year = {2002},
      number = {3},
      pages = {569--579},
      issn = {0018-9448},
      coden = {IETTAW},
      mrclass = {94A60 (81P68 81P99)},
      mrnumber = {1889969},
      doi = {10.1109/18.985947},
      zblnumber = {1071.94530},
      }
  • [akemann1991lyapunov] Go to document C. A. Akemann and J. Anderson, "Lyapunov theorems for operator algebras," Mem. Amer. Math. Soc., vol. 94, iss. 458, p. iv, 1991.
    @article{akemann1991lyapunov, mrkey = {1086563},
      author = {Akemann, Charles A. and Anderson, Joel},
      title = {Lyapunov theorems for operator algebras},
      journal = {Mem. Amer. Math. Soc.},
      fjournal = {Memoirs of the American Mathematical Society},
      volume = {94},
      year = {1991},
      number = {458},
      pages = {iv+88},
      issn = {0065-9266},
      coden = {MAMCAU},
      mrclass = {46Lxx (28B05 46G10 49N65)},
      mrnumber = {1086563},
      mrreviewer = {J. D. Maitland Wright},
      doi = {10.1090/memo/0458},
      zblnumber = {0769.46036},
      }
  • [akemann2012kadison] Go to document C. Akemann, J. Anderson, and B. Tanbay, "The Kadison-Singer problem for the direct sum of matrix algebras," Positivity, vol. 16, iss. 1, pp. 53-66, 2012.
    @article{akemann2012kadison, mrkey = {2892573},
      author = {Akemann, Charles and Anderson, Joel and Tanbay, Betul},
      title = {The {K}adison-{S}inger problem for the direct sum of matrix algebras},
      journal = {Positivity},
      fjournal = {Positivity. An International Mathematics Journal Devoted to Theory and Applications of Positivity},
      volume = {16},
      year = {2012},
      number = {1},
      pages = {53--66},
      issn = {1385-1292},
      mrclass = {46L30 (46L05 46L10)},
      mrnumber = {2892573},
      mrreviewer = {Esteban Andruchow},
      doi = {10.1007/s11117-010-0109-1},
      zblnumber = {1270.46056},
      }
  • [anderson1979a] Go to document J. Anderson, "Extensions, restrictions, and representations of states on $C^{\ast} $-algebras," Trans. Amer. Math. Soc., vol. 249, iss. 2, pp. 303-329, 1979.
    @article{anderson1979a, mrkey = {0525675},
      author = {Anderson, Joel},
      title = {Extensions, restrictions, and representations of states on {$C\sp{\ast} $}-algebras},
      journal = {Trans. Amer. Math. Soc.},
      fjournal = {Transactions of the American Mathematical Society},
      volume = {249},
      year = {1979},
      number = {2},
      pages = {303--329},
      issn = {0002-9947},
      coden = {TAMTAM},
      mrclass = {46L30},
      mrnumber = {0525675},
      mrreviewer = {Christopher Lance},
      doi = {10.2307/1998793},
      zblnumber = {0408.46049},
      }
  • [anderson1979b] Go to document J. Anderson, "Extreme points in sets of positive linear maps on $\mathcal{B}(\mathcal{H})$," J. Funct. Anal., vol. 31, iss. 2, pp. 195-217, 1979.
    @article{anderson1979b, mrkey = {0525951},
      author = {Anderson, Joel},
      title = {Extreme points in sets of positive linear maps on {$\mathcal{B}(\mathcal{H})$}},
      journal = {J. Funct. Anal.},
      fjournal = {Journal of Functional Analysis},
      volume = {31},
      year = {1979},
      number = {2},
      pages = {195--217},
      issn = {0022-1236},
      coden = {JFUAAW},
      mrclass = {46L30},
      mrnumber = {0525951},
      mrreviewer = {Christopher Lance},
      doi = {10.1016/0022-1236(79)90061-2},
      zblnumber = {0422.46049},
      }
  • [anderson1981] J. Anderson, "A conjecture concerning the pure states of $B(H)$ and a related theorem," in Topics in Modern Operator Theory, Boston: Birkhäuser, 1981, vol. 2, pp. 27-43.
    @incollection{anderson1981, mrkey = {0672813},
      author = {Anderson, Joel},
      title = {A conjecture concerning the pure states of {$B(H)$} and a related theorem},
      booktitle = {Topics in Modern Operator Theory},
      venue = {{T}imi\c soara/{H}erculane, 1980},
      series = {Operator Theory: Adv. Appl.},
      volume = {2},
      pages = {27--43},
      publisher = {Birkhäuser},
      address = {Boston},
      year = {1981},
      mrclass = {46L30},
      mrnumber = {0672813},
      mrreviewer = {C. J. K. Batty},
      zblnumber = {0455.47026},
      }
  • [bapat1989mixed] Go to document R. B. Bapat, "Mixed discriminants of positive semidefinite matrices," Linear Algebra Appl., vol. 126, pp. 107-124, 1989.
    @article{bapat1989mixed, mrkey = {1040776},
      author = {Bapat, R. B.},
      title = {Mixed discriminants of positive semidefinite matrices},
      journal = {Linear Algebra Appl.},
      fjournal = {Linear Algebra and its Applications},
      volume = {126},
      year = {1989},
      pages = {107--124},
      issn = {0024-3795},
      coden = {LAAPAW},
      mrclass = {15A15 (15A45 15A51)},
      mrnumber = {1040776},
      mrreviewer = {Marvin Marcus},
      doi = {10.1016/0024-3795(89)90009-8},
      zblnumber = {0696.15007},
      }
  • [bapatRaghavan] Go to document R. B. Bapat and T. E. S. Raghavan, Nonnegative Matrices and Applications, Cambridge: Cambridge Univ. Press, 1997, vol. 64.
    @book{bapatRaghavan, mrkey = {1449393},
      author = {Bapat, R. B. and Raghavan, T. E. S.},
      title = {Nonnegative Matrices and Applications},
      series = {Encyclopedia Math. Appl.},
      volume = {64},
      publisher = {Cambridge Univ. Press},
      address = {Cambridge},
      year = {1997},
      pages = {xiv+336},
      isbn = {0-521-57167-7},
      mrclass = {15A48 (90A14 90C08)},
      mrnumber = {1449393},
      mrreviewer = {J. Parida},
      doi = {10.1017/CBO9780511529979},
      zblnumber = {0879.15015},
      }
  • [BarDya2010] Go to document A. Baranov and K. Dyakonov, "The Feichtinger conjecture for reproducing kernels in model subspaces," J. Geom. Anal., vol. 21, iss. 2, pp. 276-287, 2011.
    @article{BarDya2010, mrkey = {2772073},
      author = {Baranov, Anton and Dyakonov, Konstantin},
      title = {The {F}eichtinger conjecture for reproducing kernels in model subspaces},
      journal = {J. Geom. Anal.},
      fjournal = {Journal of Geometric Analysis},
      volume = {21},
      year = {2011},
      number = {2},
      pages = {276--287},
      issn = {1050-6926},
      mrclass = {30J05 (30E05 30H10 46C05 46E22)},
      mrnumber = {2772073},
      mrreviewer = {D. Protas},
      doi = {10.1007/s12220-010-9147-y},
      zblnumber = {1230.30039},
      }
  • [BSS] Go to document J. Batson, D. A. Spielman, and N. Srivastava, "Twice-Ramanujan sparsifiers," SIAM J. Comput., vol. 41, iss. 6, pp. 1704-1721, 2012.
    @article{BSS, mrkey = {3029269},
      author = {Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil},
      title = {Twice-{R}amanujan sparsifiers},
      journal = {SIAM J. Comput.},
      fjournal = {SIAM Journal on Computing},
      volume = {41},
      year = {2012},
      number = {6},
      pages = {1704--1721},
      issn = {0097-5397},
      coden = {SMJCAT},
      mrclass = {05C85 (05C50 15B48 68R10)},
      mrnumber = {3029269},
      mrreviewer = {Steve Butler},
      doi = {10.1137/090772873},
      zblnumber = {1260.05092},
      }
  • [BGLS] Go to document H. H. Bauschke, O. Güler, A. S. Lewis, and H. S. Sendov, "Hyperbolic polynomials and convex analysis," Canad. J. Math., vol. 53, iss. 3, pp. 470-488, 2001.
    @article{BGLS, mrkey = {1827817},
      author = {Bauschke, Heinz H. and G{ü}ler, Osman and Lewis, Adrian S. and Sendov, Hristo S.},
      title = {Hyperbolic polynomials and convex analysis},
      journal = {Canad. J. Math.},
      fjournal = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
      volume = {53},
      year = {2001},
      number = {3},
      pages = {470--488},
      issn = {0008-414X},
      coden = {CJMAAB},
      mrclass = {90C46 (15A45 52A41)},
      mrnumber = {1827817},
      mrreviewer = {Vaithilingam Jeyakumar},
      doi = {10.4153/CJM-2001-020-6},
      zblnumber = {0974.90015},
      }
  • [berman1988matrix] Go to document K. Berman, H. Halpern, V. Kaftal, and G. Weiss, "Matrix norm inequalities and the relative Dixmier property," Integral Equations Operator Theory, vol. 11, iss. 1, pp. 28-48, 1988.
    @article{berman1988matrix, mrkey = {0920733},
      author = {Berman, Kenneth and Halpern, Herbert and Kaftal, Victor and Weiss, Gary},
      title = {Matrix norm inequalities and the relative {D}ixmier property},
      journal = {Integral Equations Operator Theory},
      fjournal = {Integral Equations and Operator Theory},
      volume = {11},
      year = {1988},
      number = {1},
      pages = {28--48},
      issn = {0378-620X},
      mrclass = {46L05},
      mrnumber = {0920733},
      mrreviewer = {J. P. Sproston},
      doi = {10.1007/BF01236652},
      zblnumber = {0647.47007},
      }
  • [Bhatia] Go to document R. Bhatia, Matrix Analysis, New York: Springer-Verlag, 1997.
    @book{Bhatia, mrkey = {1477662},
      author = {Bhatia, Rajendra},
      title = {Matrix Analysis},
      series = {Grad. Texts in Math.},
      number = {169},
      publisher = {Springer-Verlag},
      year = {1997},
      pages = {xii+347},
      isbn = {0-387-94846-5},
      mrclass = {15-02 (47-02)},
      mrnumber = {1477662},
      mrreviewer = {R. J. Bumcrot},
      doi = {10.1007/978-1-4612-0653-8},
      address = {New York},
      zblnumber = {0863.15001},
      }
  • [BiluLinial] Go to document Y. Bilu and N. Linial, "Lifts, discrepancy and nearly optimal spectral gap," Combinatorica, vol. 26, iss. 5, pp. 495-519, 2006.
    @article{BiluLinial, mrkey = {2279667},
      author = {Bilu, Yonatan and Linial, Nathan},
      title = {Lifts, discrepancy and nearly optimal spectral gap},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {26},
      year = {2006},
      number = {5},
      pages = {495--519},
      issn = {0209-9683},
      mrclass = {05C50},
      mrnumber = {2279667},
      mrreviewer = {Sebastian M. Cioab{\u{a}}},
      doi = {10.1007/s00493-006-0029-7},
      zblnumber = {1121.05054},
      }
  • [boppana] Go to document R. B. Boppana, "Eigenvalues and graph bisection: an average-case analysis," in Proc. 28th IEEE Symposium on Foundations of Computer Science, , 1987, pp. 280-285.
    @incollection{boppana,
      author = {Boppana, R. B.},
      title = {Eigenvalues and graph bisection: an average-case analysis},
      booktitle = {Proc. 28th IEEE Symposium on Foundations of Computer Science},
      year = {1987},
      pages = {280--285},
      doi = {10.1109/SFCS.1987.22},
     }
  • [BBjohnson] Go to document J. Borcea and P. Brändén, "Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products," Duke Math. J., vol. 143, iss. 2, pp. 205-223, 2008.
    @article{BBjohnson, mrkey = {2420507},
      author = {Borcea, Julius and Br{ä}nd{é}n, Petter},
      title = {Applications of stable polynomials to mixed determinants: {J}ohnson's conjectures, unimodality, and symmetrized {F}ischer products},
      journal = {Duke Math. J.},
      fjournal = {Duke Mathematical Journal},
      volume = {143},
      year = {2008},
      number = {2},
      pages = {205--223},
      issn = {0012-7094},
      coden = {DUMJAO},
      mrclass = {15A15 (30C15 32A60)},
      mrnumber = {2420507},
      mrreviewer = {Julio Ben{\'ı}tez},
      doi = {10.1215/00127094-2008-018},
      zblnumber = {1151.15013},
      }
  • [BBpolyaSchurI] Go to document J. Borcea and P. Brändén, "The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability," Invent. Math., vol. 177, iss. 3, pp. 541-569, 2009.
    @article{BBpolyaSchurI, mrkey = {2534100},
      author = {Borcea, Julius and Br{ä}nd{é}n, Petter},
      title = {The {L}ee-{Y}ang and {P}ólya-{S}chur programs. {I}. {L}inear operators preserving stability},
      journal = {Invent. Math.},
      fjournal = {Inventiones Mathematicae},
      volume = {177},
      year = {2009},
      number = {3},
      pages = {541--569},
      issn = {0020-9910},
      coden = {INVMBH},
      mrclass = {47B38 (33C45 82B26)},
      mrnumber = {2534100},
      mrreviewer = {Roland K. W. Roeder},
      doi = {10.1007/s00222-009-0189-3},
      zblnumber = {1175.47032},
      }
  • [BBpolyaSchurII] Go to document J. Borcea and P. Brändén, "The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications," Comm. Pure Appl. Math., vol. 62, iss. 12, pp. 1595-1631, 2009.
    @article{BBpolyaSchurII, mrkey = {2569072},
      author = {Borcea, Julius and Br{ä}nd{é}n, Petter},
      title = {The {L}ee-{Y}ang and {P}ólya-{S}chur programs. {II}. {T}heory of stable polynomials and applications},
      journal = {Comm. Pure Appl. Math.},
      fjournal = {Communications on Pure and Applied Mathematics},
      volume = {62},
      year = {2009},
      number = {12},
      pages = {1595--1631},
      issn = {0010-3640},
      coden = {CPAMA},
      mrclass = {82B26 (46E22 47B38)},
      mrnumber = {2569072},
      mrreviewer = {Roland K. W. Roeder},
      doi = {10.1002/cpa.20295},
      zblnumber = {1177.47041},
      }
  • [BBWeylAlgebra] Go to document J. Borcea and P. Brändén, "Multivariate Pólya-Schur classification problems in the Weyl algebra," Proc. Lond. Math. Soc., vol. 101, iss. 1, pp. 73-104, 2010.
    @article{BBWeylAlgebra, mrkey = {2661242},
      author = {Borcea, J. and Br{ä}nd{é}n, P.},
      title = {Multivariate {P}ólya-{S}chur classification problems in the {W}eyl algebra},
      journal = {Proc. Lond. Math. Soc.},
      fjournal = {Proceedings of the London Mathematical Society. Third Series},
      volume = {101},
      year = {2010},
      number = {1},
      pages = {73--104},
      issn = {0024-6115},
      mrclass = {47B37 (15A15 16S32 32A17 32A60)},
      mrnumber = {2661242},
      mrreviewer = {Vania D. Mascioni},
      doi = {10.1112/plms/pdp049},
      zblnumber = {1196.47028},
      }
  • [bourgainTzafririUrbana] Go to document J. Bourgain and L. Tzafriri, "Restricted invertibility of matrices and applications," in Analysis at Urbana, Vol. II, Cambridge: Cambridge Univ. Press, 1989, vol. 138, pp. 61-107.
    @incollection{bourgainTzafririUrbana, mrkey = {1009186},
      author = {Bourgain, J. and Tzafriri, L.},
      title = {Restricted invertibility of matrices and applications},
      booktitle = {Analysis at {U}rbana, {V}ol. {II}},
      venue = {{U}rbana, {IL},
      1986--1987},
      series = {London Math. Soc. Lecture Note Ser.},
      volume = {138},
      pages = {61--107},
      publisher = {Cambridge Univ. Press},
      address = {Cambridge},
      year = {1989},
      mrclass = {47B37 (15A09 46B20 46L30)},
      mrnumber = {1009186},
      mrreviewer = {T. Figiel},
      zblnumber = {0698.47018},
      doi = {10.1017/CBO9781107360204.006},
     }
  • [BTKS] Go to document J. Bourgain and L. Tzafriri, "On a problem of Kadison and Singer," J. Reine Angew. Math., vol. 420, pp. 1-43, 1991.
    @article{BTKS, mrkey = {1124564},
      author = {Bourgain, J. and Tzafriri, L.},
      title = {On a problem of {K}adison and {S}inger},
      journal = {J. Reine Angew. Math.},
      fjournal = {Journal für die Reine und Angewandte Mathematik. [Crelle's Journal]},
      volume = {420},
      year = {1991},
      pages = {1--43},
      issn = {0075-4102},
      coden = {JRMAA8},
      mrclass = {46L05 (46L30 47B35 47D25)},
      mrnumber = {1124564},
      mrreviewer = {H. Halpern},
      zblnumber = {0729.47028},
      doi = {10.1515/crll.1991.420.1},
     }
  • [casazza2005frames] Go to document P. G. Casazza, O. Christensen, A. M. Lindner, and R. Vershynin, "Frames and the Feichtinger conjecture," Proc. Amer. Math. Soc., vol. 133, iss. 4, pp. 1025-1033, 2005.
    @article{casazza2005frames, mrkey = {2117203},
      author = {Casazza, Peter G. and Christensen, Ole and Lindner, Alexander M. and Vershynin, Roman},
      title = {Frames and the {F}eichtinger conjecture},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the American Mathematical Society},
      volume = {133},
      year = {2005},
      number = {4},
      pages = {1025--1033},
      issn = {0002-9939},
      coden = {PAMYAR},
      mrclass = {46C05 (42C40 46L05)},
      mrnumber = {2117203},
      mrreviewer = {Dorin Ervin Dutkay},
      doi = {10.1090/S0002-9939-04-07594-X},
      zblnumber = {1082.46018},
      }
  • [CEKP07] Go to document P. Casazza, D. Edidin, D. Kalra, and V. I. Paulsen, "Projections and the Kadison-Singer problem," Oper. Matrices, vol. 1, iss. 3, pp. 391-408, 2007.
    @article{CEKP07, mrkey = {2344683},
      author = {Casazza, Pete and Edidin, Dan and Kalra, Deepti and Paulsen, Vern I.},
      title = {Projections and the {K}adison-{S}inger problem},
      journal = {Oper. Matrices},
      fjournal = {Operators and Matrices},
      volume = {1},
      year = {2007},
      number = {3},
      pages = {391--408},
      issn = {1846-3886},
      mrclass = {46L05 (42C15 47B99 47L05)},
      mrnumber = {2344683},
      mrreviewer = {Dorin Ervin Dutkay},
      doi = {10.7153/oam-01-23},
      zblnumber = {1132.46037},
      }
  • [casazza2006detailed] Go to document P. G. Casazza, M. Fickus, J. C. Tremain, and E. Weber, "The Kadison-Singer problem in mathematics and engineering: a detailed account," in Operator Theory, Operator Algebras, and Applications, Providence, RI: Amer. Math. Soc., 2006, vol. 414, pp. 299-355.
    @incollection{casazza2006detailed, mrkey = {2277219},
      author = {Casazza, Peter G. and Fickus, Matthew and Tremain, Janet C. and Weber, Eric},
      title = {The {K}adison-{S}inger problem in mathematics and engineering: a detailed account},
      booktitle = {Operator Theory, Operator Algebras, and Applications},
      series = {Contemp. Math.},
      volume = {414},
      pages = {299--355},
      publisher = {Amer. Math. Soc.},
      address = {Providence, RI},
      year = {2006},
      mrclass = {42B35 (42-02 46-02 46C05 46L30 47-02 47L30)},
      mrnumber = {2277219},
      mrreviewer = {Palle E. T. Jorgensen},
      doi = {10.1090/conm/414/07820},
      zblnumber = {1082.46018},
      }
  • [casazza2006kadison] Go to document P. G. Casazza and J. C. Tremain, "The Kadison-Singer problem in mathematics and engineering," Proc. Natl. Acad. Sci. USA, vol. 103, iss. 7, pp. 2032-2039, 2006.
    @article{casazza2006kadison, mrkey = {2204073},
      author = {Casazza, Peter G. and Tremain, Janet Crandell},
      title = {The {K}adison-{S}inger problem in mathematics and engineering},
      journal = {Proc. Natl. Acad. Sci. USA},
      fjournal = {Proceedings of the National Academy of Sciences of the United States of America},
      volume = {103},
      year = {2006},
      number = {7},
      pages = {2032--2039},
      issn = {1091-6490},
      coden = {PNASFB},
      mrclass = {46L99 (46B99 94A12)},
      mrnumber = {2204073},
      mrreviewer = {Palle E. T. Jorgensen},
      doi = {10.1073/pnas.0507888103},
      zblnumber = {1160.46333},
      }
  • [ChudnovskySeymour] Go to document M. Chudnovsky and P. Seymour, "The roots of the independence polynomial of a clawfree graph," J. Combin. Theory Ser. B, vol. 97, iss. 3, pp. 350-357, 2007.
    @article{ChudnovskySeymour, mrkey = {2305888},
      author = {Chudnovsky, Maria and Seymour, Paul},
      title = {The roots of the independence polynomial of a clawfree graph},
      journal = {J. Combin. Theory Ser. B},
      fjournal = {Journal of Combinatorial Theory. Series B},
      volume = {97},
      year = {2007},
      number = {3},
      pages = {350--357},
      issn = {0095-8956},
      coden = {JCBTB8},
      mrclass = {05C69},
      mrnumber = {2305888},
      mrreviewer = {Steven D. Noble},
      doi = {10.1016/j.jctb.2006.06.001},
      zblnumber = {1119.05075},
      }
  • [Dedieu] Go to document J. Dedieu, "Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?," J. Pure Appl. Algebra, vol. 81, iss. 3, pp. 269-278, 1992.
    @article{Dedieu, mrkey = {1179101},
      author = {Dedieu, Jean-Pierre},
      title = {Obreschkoff's theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?},
      journal = {J. Pure Appl. Algebra},
      fjournal = {Journal of Pure and Applied Algebra},
      volume = {81},
      year = {1992},
      number = {3},
      pages = {269--278},
      issn = {0022-4049},
      coden = {JPAAA2},
      mrclass = {12D10},
      mrnumber = {1179101},
      mrreviewer = {Thomas C. Craven},
      doi = {10.1016/0022-4049(92)90060-S},
      zblnumber = {0772.12002},
      }
  • [dubrovin] B. A. Dubrovin, "Matrix finite-gap operators," in Current Problems in Mathematics, Moscow: Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., 1983, vol. 23, pp. 33-78.
    @incollection{dubrovin, mrkey = {0734313},
      author = {Dubrovin, B. A.},
      title = {Matrix finite-gap operators},
      booktitle = {Current Problems in Mathematics},
      volume = {23},
      series = {Itogi Nauki i Tekhniki},
      pages = {33--78},
      publisher = {Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform.},
      address = {Moscow},
      year = {1983},
      mrclass = {58F07 (35Q20 81C05)},
      mrnumber = {0734313},
      mrreviewer = {L. A. Takhtajan (Takhtadzhyan)},
      }
  • [Fell] Go to document H. J. Fell, "On the zeros of convex combinations of polynomials," Pacific J. Math., vol. 89, iss. 1, pp. 43-50, 1980.
    @article{Fell, mrkey = {0596914},
      author = {Fell, H. J.},
      title = {On the zeros of convex combinations of polynomials},
      journal = {Pacific J. Math.},
      fjournal = {Pacific Journal of Mathematics},
      volume = {89},
      year = {1980},
      number = {1},
      pages = {43--50},
      issn = {0030-8730},
      coden = {PJMAAI},
      mrclass = {30C15},
      mrnumber = {0596914},
      mrreviewer = {M. Marden},
      doi = {10.2140/pjm.1980.89.43},
      zblnumber = {0416.30005},
      }
  • [GodsilGutman] C. D. Godsil and I. Gutman, "On the matching polynomial of a graph," in Algebraic Methods in Graph Theory, Vol. I, II, New York: North-Holland, 1981, vol. 25, pp. 241-249.
    @incollection{GodsilGutman, mrkey = {0642044},
      author = {Godsil, C. D. and Gutman, I.},
      title = {On the matching polynomial of a graph},
      booktitle = {Algebraic Methods in Graph Theory, {V}ol. {I},
      {II}},
      venue = {{S}zeged, 1978},
      series = {Colloq. Math. Soc. János Bolyai},
      volume = {25},
      pages = {241--249},
      publisher = {North-Holland},
      address = {New York},
      year = {1981},
      mrclass = {05C70 (33A65)},
      mrnumber = {0642044},
      mrreviewer = {E. J. Farrell},
      zblnumber = {0476.05060},
      }
  • [gurvitsMixed] Go to document L. Gurvits, "The Van der Waerden conjecture for mixed discriminants," Adv. Math., vol. 200, iss. 2, pp. 435-454, 2006.
    @article{gurvitsMixed, mrkey = {2200852},
      author = {Gurvits, Leonid},
      title = {The {V}an der {W}aerden conjecture for mixed discriminants},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {200},
      year = {2006},
      number = {2},
      pages = {435--454},
      issn = {0001-8708},
      coden = {ADMTA4},
      mrclass = {15A15},
      mrnumber = {2200852},
      mrreviewer = {My Hachem Lalaoui Rhali},
      doi = {10.1016/j.aim.2004.12.002},
      zblnumber = {1093.15011},
      }
  • [gurvitsOne] Go to document L. Gurvits, "Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all," Electron. J. Combin., vol. 15, iss. 1, p. 66, 2008.
    @article{gurvitsOne, mrkey = {2411443},
      author = {Gurvits, Leonid},
      title = {Van der {W}aerden/{S}chrijver-{V}aliant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all},
      note = {with a corrigendum},
      journal = {Electron. J. Combin.},
      fjournal = {Electronic Journal of Combinatorics},
      volume = {15},
      year = {2008},
      number = {1},
      pages = {Research Paper 66, 26},
      issn = {1077-8926},
      mrclass = {15A15 (05A15 05C70)},
      mrnumber = {2411443},
      mrreviewer = {Peter M. Gibson},
      url = {http://www.combinatorics.org/Volume_15/Abstracts/v15i1r66.html},
      zblnumber = {1182.15008},
      }
  • [heilmannLieb] Go to document O. J. Heilmann and E. H. Lieb, "Theory of monomer-dimer systems," Comm. Math. Phys., vol. 25, pp. 190-232, 1972.
    @article{heilmannLieb, mrkey = {0297280},
      author = {Heilmann, Ole J. and Lieb, Elliott H.},
      title = {Theory of monomer-dimer systems},
      journal = {Comm. Math. Phys.},
      fjournal = {Communications in Mathematical Physics},
      volume = {25},
      year = {1972},
      pages = {190--232},
      issn = {0010-3616},
      mrclass = {82.05},
      mrnumber = {0297280},
      doi = {10.1007/BF01877590},
      zblnumber = {0228.05131},
      }
  • [HeltonVinnikov] Go to document W. J. Helton and V. Vinnikov, "Linear matrix inequality representation of sets," Comm. Pure Appl. Math., vol. 60, iss. 5, pp. 654-674, 2007.
    @article{HeltonVinnikov, mrkey = {2292953},
      author = {Helton, J. William and Vinnikov, Victor},
      title = {Linear matrix inequality representation of sets},
      journal = {Comm. Pure Appl. Math.},
      fjournal = {Communications on Pure and Applied Mathematics},
      volume = {60},
      year = {2007},
      number = {5},
      pages = {654--674},
      issn = {0010-3640},
      coden = {CPAMA},
      mrclass = {93B40 (15A39 52A20)},
      mrnumber = {2292953},
      mrreviewer = {Driss Mentagui},
      doi = {10.1002/cpa.20155},
      zblnumber = {1116.15016},
      }
  • [orig_ks] Go to document R. V. Kadison and I. M. Singer, "Extensions of pure states," Amer. J. Math., vol. 81, pp. 383-400, 1959.
    @article{orig_ks, mrkey = {0123922},
      author = {Kadison, Richard V. and Singer, I. M.},
      title = {Extensions of pure states},
      journal = {Amer. J. Math.},
      fjournal = {American Journal of Mathematics},
      volume = {81},
      year = {1959},
      pages = {383--400},
      issn = {0002-9327},
      mrclass = {46.65},
      mrnumber = {0123922},
      mrreviewer = {C. Davis},
      doi = {10.2307/2372748},
      zblnumber = {0086.09704},
      }
  • [kummer] Go to document M. Kummer, D. Plaumann, and C. Vinzant, "Hyperbolic polynomials, interlacers, and sums of squares," Math. Program., pp. 1-23, 2013.
    @article{kummer, year={2013},
      issn={0025-5610},
      journal={Math. Program.},
      doi={10.1007/s10107-013-0736-y},
      title={Hyperbolic polynomials, interlacers, and sums of squares},
      publisher={Springer Berlin Heidelberg},
      keywords={Primary 14P99; Secondary 05E99; 11E25; 52A20; 90C22},
      author={Kummer, Mario and Plaumann, Daniel and Vinzant, Cynthia},
      pages={1-23},
      language={English},
     }
  • [Lawton2010] W. Lawton, "Minimal sequences and the Kadison-Singer problem," Bull. Malays. Math. Sci. Soc., vol. 33, iss. 2, pp. 169-176, 2010.
    @article{Lawton2010, mrkey = {2666420},
      author = {Lawton, Wayne},
      title = {Minimal sequences and the {K}adison-{S}inger problem},
      journal = {Bull. Malays. Math. Sci. Soc.},
      fjournal = {Bulletin of the Malaysian Mathematical Sciences Society. Second Series},
      volume = {33},
      year = {2010},
      number = {2},
      pages = {169--176},
      issn = {0126-6705},
      mrclass = {46L30 (37B10 42A55)},
      mrnumber = {2666420},
      mrreviewer = {Gabriel Picioroaga},
      zblnumber = {1209.37011},
      }
  • [lax] Go to document A. S. Lewis, P. A. Parrilo, and M. V. Ramana, "The Lax conjecture is true," Proc. Amer. Math. Soc., vol. 133, iss. 9, pp. 2495-2499, 2005.
    @article{lax, mrkey = {2146191},
      author = {Lewis, A. S. and Parrilo, P. A. and Ramana, M. V.},
      title = {The {L}ax conjecture is true},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the American Mathematical Society},
      volume = {133},
      year = {2005},
      number = {9},
      pages = {2495--2499},
      issn = {0002-9939},
      coden = {PAMYAR},
      mrclass = {90C25 (15A15)},
      mrnumber = {2146191},
      mrreviewer = {Hristo S. Sendov},
      doi = {10.1090/S0002-9939-05-07752-X},
      zblnumber = {1073.90029},
      }
  • [LiebSokal] Go to document E. H. Lieb and A. D. Sokal, "A general Lee-Yang theorem for one-component and multicomponent ferromagnets," Comm. Math. Phys., vol. 80, iss. 2, pp. 153-179, 1981.
    @article{LiebSokal, mrkey = {0623156},
      author = {Lieb, Elliott H. and Sokal, Alan D.},
      title = {A general {L}ee-{Y}ang theorem for one-component and multicomponent ferromagnets},
      journal = {Comm. Math. Phys.},
      fjournal = {Communications in Mathematical Physics},
      volume = {80},
      year = {1981},
      number = {2},
      pages = {153--179},
      issn = {0010-3616},
      coden = {CMPHAY},
      mrclass = {82A05 (28A12 32A40)},
      mrnumber = {0623156},
      mrreviewer = {Francesco Guerra},
      doi = {10.1007/BF01213009},
      }
  • [lifts_paper] Go to document A. Marcus, D. A. Spielman, and N. Srivastava, "Interlacing families I: Bipartite Ramanujan graphs of all degrees," Ann. of Math., vol. 182, pp. 307-325, 2015.
    @article{lifts_paper,
      author = {Marcus, A. and Spielman, D. A. and Srivastava, N.},
      title = {Interlacing families {I}: {B}ipartite {R}amanujan graphs of all degrees},
      journal = {Ann. of Math.},
      volume = {182},
      year = {2015},
      pages = {307--325},
      doi = {10.4007/2015.182.1.7},
      }
  • [icm_survey] A. Marcus, D. A. Spielman, and N. Srivastava, "Ramanujan graphs and the solution of the Kadison–Singer problem," in Proceedings of the International Congress of Mathematicians, , 2014.
    @incollection{icm_survey,
      author = {Marcus, A. and Spielman, D. A. and Srivastava, N.},
      title = {Ramanujan graphs and the solution of the {K}adison--{S}inger problem},
      booktitle = {Proceedings of the International Congress of Mathematicians},
      year = {2014},
      arxiv = {1408.4421},
      }
  • [Marden] M. Marden, Geometry of Polynomials, Providence, RI: Amer. Math. Soc., 1966, vol. 3.
    @book{Marden, mrkey = {0225972},
      author = {Marden, Morris},
      title = {Geometry of Polynomials},
      series = {Math. Surveys Monogr.},
      volume = {3},
      publisher = {Amer. Math. Soc.},
      year = {1966},
      pages = {xiii+243},
      mrclass = {30.11},
      mrnumber = {0225972},
      mrreviewer = {O. Shisha},
      address = {Providence, RI},
      zblnumber = {0162.37101},
      }
  • [Paulsen2008] Go to document V. I. Paulsen, "Syndetic sets, paving and the Feichtinger conjecture," Proc. Amer. Math. Soc., vol. 139, iss. 3, pp. 1115-1120, 2011.
    @article{Paulsen2008, mrkey = {2745663},
      author = {Paulsen, Vern I.},
      title = {Syndetic sets, paving and the {F}eichtinger conjecture},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the American Mathematical Society},
      volume = {139},
      year = {2011},
      number = {3},
      pages = {1115--1120},
      issn = {0002-9939},
      coden = {PAMYAR},
      mrclass = {46L05 (46B15)},
      mrnumber = {2745663},
      mrreviewer = {Gabriel Picioroaga},
      doi = {10.1090/S0002-9939-2010-10600-7},
      zblnumber = {1220.46008},
      }
  • [pemantle] R. Pemantle, "Hyperbolicity and stable polynomials in combinatorics and probability," in Current Developments in Mathematics, 2011, Somerville, MA: Int. Press, 2012, pp. 57-123.
    @incollection{pemantle, mrkey = {3098077},
      author = {Pemantle, Robin},
      title = {Hyperbolicity and stable polynomials in combinatorics and probability},
      booktitle = {Current Developments in Mathematics, 2011},
      pages = {57--123},
      publisher = {Int. Press},
      address = {Somerville, MA},
      year = {2012},
      mrclass = {62H20 (05A15 26C10 30C15)},
      mrnumber = {3098077},
      mrreviewer = {Marius R{\u{a}}dulescu},
      }
  • [Popa2013] Go to document S. Popa, "A ${ II}_1$ factor approach to the Kadison-Singer problem," Comm. Math. Phys., vol. 332, iss. 1, pp. 379-414, 2014.
    @article{Popa2013, mrkey = {3253706},
      author = {Popa, Sorin},
      title = {A {${\rm II}\sb 1$} factor approach to the {K}adison-{S}inger problem},
      journal = {Comm. Math. Phys.},
      fjournal = {Communications in Mathematical Physics},
      volume = {332},
      year = {2014},
      number = {1},
      pages = {379--414},
      issn = {0010-3616},
      mrclass = {81R10 (81R05)},
      mrnumber = {3253706},
      doi = {10.1007/s00220-014-2055-4},
      zblnumber = {06353809},
      }
  • [RudelsonIsotropic] Go to document M. Rudelson, "Random vectors in the isotropic position," J. Funct. Anal., vol. 164, iss. 1, pp. 60-72, 1999.
    @article{RudelsonIsotropic, mrkey = {1694526},
      author = {Rudelson, M.},
      title = {Random vectors in the isotropic position},
      journal = {J. Funct. Anal.},
      fjournal = {Journal of Functional Analysis},
      volume = {164},
      year = {1999},
      number = {1},
      pages = {60--72},
      issn = {0022-1236},
      coden = {JFUAAW},
      mrclass = {60G50 (46B99 47B10 47N30 60D05 60F25)},
      mrnumber = {1694526},
      mrreviewer = {Fran{ç}oise Lust-Piquard},
      doi = {10.1006/jfan.1998.3384},
      zblnumber = {0929.46021},
      }
  • [TaoBlog] Go to document T. Tao, Real stable polynomials and the Kadison-Singer problem, 2013.
    @misc{TaoBlog,
      author = {Tao, T.},
      title = {Real stable polynomials and the {K}adison-{S}inger problem},
      year = {2013},
      url = {http://terrytao.wordpress.com/2013/11/04/real-stable-polynomials-and-the-kadison-singer-problem/},
      }
  • [wagner] Go to document D. G. Wagner, "Multivariate stable polynomials: theory and applications," Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 53-84, 2011.
    @article{wagner, mrkey = {2738906},
      author = {Wagner, David G.},
      title = {Multivariate stable polynomials: theory and applications},
      journal = {Bull. Amer. Math. Soc.},
      fjournal = {American Mathematical Society. Bulletin. New Series},
      volume = {48},
      year = {2011},
      number = {1},
      pages = {53--84},
      issn = {0273-0979},
      coden = {BAMOAD},
      mrclass = {32A60 (05A20 05B35 15A45)},
      mrnumber = {2738906},
      doi = {10.1090/S0273-0979-2010-01321-5},
      zblnumber = {1207.32006},
      }
  • [weaver] Go to document N. Weaver, "The Kadison-Singer problem in discrepancy theory," Discrete Math., vol. 278, iss. 1-3, pp. 227-239, 2004.
    @article{weaver, mrkey = {2035401},
      author = {Weaver, Nik},
      title = {The {K}adison-{S}inger problem in discrepancy theory},
      journal = {Discrete Math.},
      fjournal = {Discrete Mathematics},
      volume = {278},
      year = {2004},
      number = {1-3},
      pages = {227--239},
      issn = {0012-365X},
      coden = {DSMHA4},
      mrclass = {46L05 (05A99 11K38)},
      mrnumber = {2035401},
      mrreviewer = {P. J. Stacey},
      doi = {10.1016/S0012-365X(03)00253-X},
      zblnumber = {1040.46040},
      }

Authors

Adam W. Marcus

Yale University, New Haven, CT

Daniel A. Spielman

Yale University, New Haven, CT

Nikhil Srivastava

Microsoft Research, Bangalore, India

Current address:

University of California Berkeley, Berkeley, CA 94720