Consider two $N \times N$ hermitian indefinite matrices $A_1$ and $A_2$. Consider their affine combination \begin{align} M(t)=(1-t)A_1+tA_2 \end{align} I am interested in the minimum eigenvalue of $M(t)$. I can write this as \begin{align} \lambda(t)=\min_{x ~\in~\mathbb{C}^{N\times 1}}~&x^HM(t)x \\\ &x^{H}x = 1 \end{align}

When I simulated this, I made the following observations

  • It is a concave function of $t$
  • It is a piece-wise linear function of $t$ (at least, that is what the plot looks like).

My question, 1) how do I explain this behavior 2) Any comments on $t$ where the maxima occurs?

Some Thoughts:

I have a feeling that this is connected to the Toeplitz-Hausdorff theorem. From it, it follows that the subset of 2-D plane \begin{align} \mathbb{S}=\{[x_1,x_2]\in \mathbb{R}^2\mid ~x_1=x^HA_1x,~x_2=x^HA_2x,~x^{H}x=1\} \end{align} is a closed compact convex subset of $\mathbb{R}^2$. Thus, it follows that minimum eigenvalue of $M(t)$ is \begin{align} \lambda(t)=(1-t)x_1+tx_2, ~~[x_1,x_2]\in \mathbb{S} \end{align} Now from here (if this is correct?), How do I conclude the observations, I made earlier?


This is related to so-called hyperbolic polynomials, studied by L. Gaarding in the fifties. More generally, let $\lambda(\xi)$ be the least eigenvalue of $A(\xi)=\sum_\alpha\xi_\alpha A^\alpha$, where $A^\alpha$ are Hermitian matrices and $\xi$ is a real vector. Then $\lambda$ is a concave function. It is generically strictly concave, except in the radial directions of course because of homogeneity $\lambda(s\xi)=s\lambda(\xi)$ for $s>0$. The strict concavity is related to the lack of commutativity of pairs $(A^\alpha,A^\beta)$. For instance, the Pauli matrices yield $\lambda(\xi)=-|\xi|$, which is clearly strictly concave away from rays ${\mathbb R}^+\xi$. On the opposite, if $[A^\alpha,A^\beta]=0$ for every pair, then $\lambda$ is piecewise linear.

Strict concavity occurs for instance when the least eigenvalue is simple for every $\xi\ne0$, or if it has a constant multiplicity. Then $\lambda$ is analytic away of the origin, with a Hessian matrix of rank $n-1$. It turns out that this property implies a so-called Strichartz inequality for the solutions of the system of Partial Differential Equations $$\frac{\partial u}{\partial t}+\sum_\alpha A^\alpha\frac{\partial u}{\partial x_\alpha}=0.$$ Obviously, the symbol of the system is $\det(\tau I_n+A(\xi))$.Thus the characteristic manifold is related to the eigenvalues of $A(\xi)$, in particular to $\lambda(\xi)$.

The other eigenvalues satisfy more involved inequalities such as Weyl, Lidskii, Ky Fan -type inequalities. For instance, the sum of the $k$ least eigenvalues is concave too. This is a part of Alfred Horn's conjecture, now a theorem thanks to the work of many people, including Knutson & Tao.

The last part of the question, that about Toeplitz-Hausdorff theorem, is unclear. ${\mathbb S}$ is not a singleton, so what means \begin{align} \lambda(t)=(1-t)x_1+tx_2, ~~[x_1,x_2]\in \mathbb{S} \qquad ? \end{align} The equality certainly holds true for teh particular point $(x_1,x_2)$ obtained by taking $x$ a unit eigenvector associated with $\lambda(t)$, but what else ? To see some deep relations between Toeplitz-Hausdorff and hyperbolic polynomials, have a look to our paper with Th. Gallay, Numerical measure of a complex matrix, in Comm. Pure Appl. Math. 65 (2012), no. 3, 287–336.

  • $\begingroup$ Can we relate it to Toeplitz-Hausdorff theorem and comment about the observations? $\endgroup$ – dineshdileep Dec 19 '12 at 7:01
  • $\begingroup$ great answer -- minor typo (teh -> the) in last paragraph $\endgroup$ – J.J. Green Dec 19 '12 at 11:39

The function $t\mapsto x^TM(t)x$ is affine for every $x$. Inf of affine functions is usually concave. (I mean it is concave under some broad assumptions which are certainly satisfied here).

About "piecewise-linear", it is not true, even for simple 2 times 2 matrices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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