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

  1. each polynomial has degree $n$,
  2. each has a positive leading coefficient, and
  3. 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,

  1. $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.
  2. $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:

  1. 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?.
  2. 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.

1 Answer 1

  1. You are correct -- we mean the the $l^{th}$ largest root where $1 \leq l \leq n$

  2. The "eventually positive" condition is used to make sure all of the polynomials are oriented the same way. For a given $l$, let $r^i_l$ be the $l^{th}$ root of $f_i$ and assume $r^1_l \leq \dots \leq r^k_l$. The thing you need to show something for the $l^{th}$ root is that

(a) Every polynomial has the same sign (or $0$) at $r^1_l$, and

(b) Every polynomial has the same sign (or $0$) at $r^k_l$

That ensures that $\sum_i f_i(r^1_l)$ and $\sum_i f_i(r^k_l)$ have different signs (or $0$) which means that $\sum_i f_i$ has a root in that interval. The interlacer guarantees that each polynomial has exactly one root in the interval (so if they start with same sign, they end with same sign) and the "eventually positive" condition ensures they all have the same sign at some point.

I'm not sure what you mean by ''we cannot assume this kind of facts'' -- the statement regarding the leading coefficients being positive is a necessary condition for the theorem to hold (for any $1 \leq l \leq n$). If this hypothesis does not hold, then the theorem is not necessarily true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.