interlacing roots/eigenvalues results and modern analogues - MathOverflow

interlacing roots/eigenvalues results and modern analogues

2011-11-20T00:26:24Z

Is there any relation between these theorems on interlacing roots?

The roots of $f(x), f'(x)$ interlace (if all the roots of $f(x)$ are real and have real coefficients).
The eigenvalues of an $n \times n$ matrix $A$ and it's minor $n-1\times n-1$ matrix $A_{ii}$ interlace (is a real symmetric matrix, or Hermitian).

Is there a more modern version of these results?

EDIT: Picturing Terry Tao's answer, let $f(x)= (x-1)(x-2)\dots(x-8)(x-9)$.

A plot of $\{(f(x), f'(x)): 0.5 < x < 9\}$. This figure is symmetric, and not very representative.

Answer by Terry Tao for interlacing roots/eigenvalues results and modern analogues

2011-11-20T05:35:50Z

Interlacing often comes from a monotonicity formula: if $\hbox{arg}(f(x)/g(x))$ is monotone in x (assuming that $f$ and $g$ do not simultaneously vanish), then the zeroes of f and g will interlace, as can be seen geometrically by seeing how the curve $x \mapsto (f(x),g(x))$ winds around the plane.

The monotonicity of the phase is equivalent to the Wronskian $f g{'} - f{'} g$ of the two functions $f,g$ having a definite sign. I think one can prove the two classical interlacing properties you mentioned (as well as the orthogonal polynomial one Noam mentioned) by verifying this definiteness property (for the functions $f$ and $f{'}$ in the first case, and for the two characteristic functions in the second case).

But monotonicity formulae are ubiquitous throughout mathematics, and any two such formulae selected at random are unlikely to be related. So my feeling is that most pairs of interlacing formulae similarly have no strong connection to each other.

Answer by Brendan McKay for interlacing roots/eigenvalues results and modern analogues

2011-11-20T06:22:41Z

One fuzzy connection: Say matrix $A$ has characteristic polynomial $f(x)$. Then the derivative $f'(x)$ is the sum of the characteristic polynomials of the principal minors $A_{ii}$.

Answer by Aaron Meyerowitz for interlacing roots/eigenvalues results and modern analogues

2011-11-21T08:25:24Z

This is fuzzy (and related to Brendan's fuzzy answer) but maybe someone will tease out more details or give a better explanation:

Let $f(x)$ have degree $n$ and all roots real. I will assume that $f$ is monic and that the roots are distinct. $$f=\prod_1^n(x-\alpha_i) \text{ with } \alpha_1 \lt \cdots \lt \alpha_n$$ (the case of repeated roots seems no harder but I don't want to make a careless misstatement. ) Then the scaled derivative $f'(x)/n$ is one monic polynomial with roots interlacing those of $f$.

What is a nice description of the set of polynomials with this property?

We could say that it is $$W=\lbrace\prod_1^{n-1}(x-\beta_i) \text{ with } \alpha_j \le \beta_j \le \alpha_{j+1} \rbrace$$ and let $S$ be the corresponding set with requirement that $\alpha_j \lt \beta_j \lt \alpha_{j+1}$ (the sets of weakly and strongly interlacing polynomials.) However that seems unsatisfying.

Consider the $n$ polynomials $$f_j=\frac{f(x)}{x-\alpha_j}$$ obtained by dropping one root. They are in $W$ and it seems intuitive that the set of convex combinations of these polynomials $$\sum{c_i}f_i(x) \text{ with } \sum c_i=1 \text{ and } c_i \ge 0$$ is $W$, that each polynomial in $W$ is a unique combination, and that $S$ arises from requiring all the $c_i$ positive. Of course $f'$ is the case that all $c_j=\frac1n.$ The coefficients range over a simplex and the derivative comes from the centroid. I will give an interesting justification below although it may not be the "right" one.

A connection is that the $n \times n$ diagonal matrix $D$ with diagonal entries $\alpha_i$ has characteristic polynomial $f(x)$ and the principal submatrix $D_{jj}$ has characteristic polynomial $f_j(x).$ Furthermore, any real symmetric matrix with these eigenvalues is $A=QDQ^T$ for an orthogonal matrix Q (whose rows are eigenvectors for $A$). There must be more to say about that but I won't.

Here is my justification of the statement about convex combinations. I include it because I am not sure it satisfies me (so maybe someone else will tell me what I should have seen) and because it seems to enhance the connection: It would be nice to have a direct recipe for the combination giving a desired polynomial $g$ with chosen roots. One case with something like that is the Lagrange interpolation formula although it gives arbitrarily chosen values at fixed points rather than the fixed value $0$ at arbitrarily chosen points. However the polynomials $f_i$ are the ingredients used by Lagrange interpolation to specify values of a polynomial at the $n$ places $x=\alpha_i$. A polynomial $g$ with the interlacing properties we desire is uniquely determined by the values it has at those $n$ points (which should alternate in sign) so we should take something like $c_j=\frac{\prod{\alpha_j-\beta_i}}{\prod \alpha_j-\alpha_k}$ where $1 \le i \le n-1$ and $1 \le k \le n$ with $k \ne j.$

Answer by J. M. for interlacing roots/eigenvalues results and modern analogues

2011-11-22T03:08:07Z

A rather tenuous connection, but I'll throw it out and hope somebody can build a better answer from this (in short, too long for a comment):

It is well known (or it should be!) that one can use the Sturm sequence construction for a polynomial $p(x)$ with all roots real and its derivative to construct a symmetric tridiagonal companion matrix (that is, the symmetric tridiagonal matrix whose characteristic polynomial is $p(x)$). See Fiedler's paper for details.

One could then apply Cauchy's interlacing theorem on the tridiagonal matrix just constructed. As a matter of fact, the characteristic polynomials of successive leading submatrices of a tridiagonal form a Sturm sequence.

To expand on the comment I gave regarding orthogonal polynomials: consider the monic orthogonal polynomials $p_n(x)$ satisfying the difference equation

$$p_{n+1}(x)=(x-c_n)p_n(x)-d_np_{n-1}(x),\qquad p_{-1}(x)=0,p_0(x)=1$$

One can associate a symmetric tridiagonal matrix with this recursion, called a Jacobi matrix:

$$\begin{pmatrix}c_0&\sqrt{d_1}&&\\\sqrt{d_1}&\ddots&\ddots&\\&\ddots&&\sqrt{d_{n-1}}\\&&\sqrt{d_{n-1}}&c_{n-1}\end{pmatrix}$$

whose characteristic polynomial is $p_n(x)$. It can be seen that the characteristic polynomials of the leading $1\times1, 2\times 2, \dots$ submatrices are $p_1(x),p_2(x),\dots$ We see here the correspondence between the Sturm sequences for orthogonal polynomials and tridiagonal matrices.