In their proof of the celebrated Kadison-Singer conjecture, Marcus, Spielman and Srivastava exploited so-called interlacing families which are originally defined for their work on Ramanujan graphs. And I have a question on a variant of their Lemma 4.2 about common interlacing stated in http://arxiv.org/pdf/1304.4132v2.pdf. I may need to explain some terminologies before presenting the lemma.
Suppose we have a set of polynomials $f_1,\cdots,f_k$ where
- each polynomial has degree $n$,
- each has a positive leading coefficient, and
- each has $n$ real roots.
Let $\beta_{i,j}$ be the $j^\mathrm{th}$ smallest root of $f_i$. Then we say these polynomials $f_1,\cdots,f_k$ have a common interlacing when there are numbers $\alpha_0 \leq \alpha_1 \leq \cdots\leq\alpha_n$ so that $\beta_{i,j} \in [\alpha_{j−1}, \alpha_j]$ for all $i$ and $j$. In other words, degree-$n$ polynomials $f_1,\cdots,f_k$ have a common interlacing when there are $n$ non-overlapping regions in $x$ so that all the $i^\mathrm{th}$ root of each polynomial is located the $i^\mathrm{th}$ region.
For example,
- $f_1 = (x+10)(x-1)(x-10)$ and $f_2=(x+11)(x-2)(x-11)$ have a common interlacing. The smallest roots are $\{-10,-11\}$, the second smallest roots are $\{1,2\}$ and the largest roots are $\{10,11\}$. And these three sets of numbers can be placed in three non-overlapping regions.
- $f_1 = (x + 5)(x − 9)(x − 10)$ and $f_2=(x + 6)(x − 1)(x − 8)$ don't have a common interlacing. The smallest roots are $\{-5,-6\}$, the second smallest roots are $\{1,9\}$ and the largest roots are $\{8,10\}$. The last two sets of numbers cannot be placed on two non-overlapping regions.
Lemma 4.2 in http://arxiv.org/pdf/1304.4132v2.pdf: Let $f_1,\cdots,f_k$ be polynomials of the same degree $n$ that are real-rooted and have positive leading coefficients. Define \begin{equation*} f_\emptyset = \sum_{i=1}^k f_i. \end{equation*}
If $f_1,\cdots,f_k$ have a common interlacing, then there exists an $i$ so that the largest root of $f_i$ is at most the largest root of $f_\emptyset$.
The proof of Lemma 4.2 is simple. (You may try another simple proof by Dustin G. Mixon.)
The paper says "The conclusion of the lemma also holds for the $k^\mathrm{th}$ largest root by a similar argument."
My question is:
- I'm guessing, when they mean by $k^\mathrm{th}$ largest root in the above statement, $k$ means any number between 1 and $n$ but not the number of polynomials $k$ in the definition of common interlacing, right?.
- The original proof about the largest root of $f_\emptyset$ proceeds with the fact that each $f_i$ has a positive leading coefficient and each of them is positive for sufficiently large $x$ which is larger than each of the largest roots of $f_1,\cdots,f_k$. I'm not sure how we can prove it for the $\ell^\mathrm{th}$ largest roof of $f_\emptyset$ because we cannot assume this kind of facts.