Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I asked this (with background) here http://stats.stackexchange.com/questions/38494/principal-component-analysis-bootstrap-and-probability-of-eigenvalue-collision

but did not really get any answers. See that post for the background.

Let $D$ be some open set in the plane, say. Not really important where the set $D$ sits, but it shoud not be only a line/curve. Suppose we have defined a continuous function on $D$ $$ f \colon D \mapsto \text{Sym}^n $$ where $\text{sym}^n$ is the set of (real) symmetric $n \times n$ matrices. How can I define the eigenvectors of $f(x), x \in D$ as a continuous function on $D$? How can I calculate this? And how can I deal with eigenvalue collisions? A simple example clarifying this point (and defined on a curve): Let $$ f(t) =\left( \begin{matrix} 1+t & 0 \cr 0 & 1-t \end{matrix}\right) $$ Then the largest eigenvalue is $$ \lambda_1(t) = 1+ |t| $$ but the eigenvector corresponding to the largest eigenvalue cannot be defined as a continuous function: $$ v_1(t) = \begin{cases} e_2 & t\le 0 \cr e_1 & t > 0 \end{cases} $$ So what I want is to look at the two eigenvalue functions $1+t, 1-t$ and follow the eigenvectors corresponding to each one, which obviously can be done in a continuos (constant!) manner.

ADDED after the answer by Anthony Quas:

Is it possible to give some further conditions, under which a solution is possible? Differentiability? Or, if the matrices are realizations of some random field of matrices, can something be said about the probability some continuous selection is possible?

share|improve this question
1  
I fixed the latex by replacing "\\" with "\cr" FWIW –  Anthony Quas Dec 11 '12 at 23:50
add comment

6 Answers 6

up vote 22 down vote accepted

The example given by Anthony Quas reveals a phenomenon discussed in Kato's book Perturbation Theory for Linear Differential Operators. The point is the following:

  • If the symmetric matrix depends analytically upon one parameter, then you can follow analytically its eigenvalues and its eigenvectors. Notice that this requires sometimes that the eigenvalues cross. When this happens, the largest eigenvalues, as the maximum of smooth functions, is only Lipschitz.
  • On the contrary, if the matrix depends upon two or more parameters, the eigenvalues are at most Lipschitz when crossing happens, and the eigenvectors cannot be chosen continuously. A typical example is $$(s,t)\mapsto\begin{pmatrix} s & t \\\\ t & -s \end{pmatrix},$$ whose eigenvalues are $\pm\sqrt{s^2+t^2}$. Up to the shift by $I_2$, Quas' example is just a piecewise $C^1$ section of this two-parameters example, and it inherits its lack of continuous selection of eigenvectors.
  • Likewise, if analyticity is dropped, a $C^\infty$-example by Rellich shows that eigenvectors need not be continuous functions of a single parameter. Of course, Quas' example can be recast as a $C^\infty$ one, by flatening the parametrisation at $t=0$, say by replacing $t$ by $s$ such that $t={\rm sgn}(s)\cdot e^{-1/s^2}$.

Side remark: Kato's result is only local. If the domain is not simply connected, it could happen that a global continuous selection of eigenvectors is not possible. This is classical in the exemple above if you restrict to the unit circle $s^2+t^2=1$; then the eigenvalues $\pm1$ are global continuous functions, but when following an eigenvector, it experiences a flip $v\mapsto -v$ as one makes one turn.

share|improve this answer
    
Regarding the circle example: Here the problem is fixed if one allows for eigenvectors with complex entries. Over $\mathbb C$ (and with domain an open subset of $\mathbb R^2$) a continuous selection is possible as soon as the eigenvalues are always distinc –  Leonel Robert Dec 12 '12 at 15:01
7  
Attention: There is a 1-parameter $2\times 2$-symmetric matrix which is $C^\infty$, the eigenvalues are $C^\infty$, but the eigenvector cannot be chosen continuously: See Example 7.7 (due to Rellich) in Dmitri Alekseevky, Andreas Kriegl, Mark Losik, Peter W. Michor: Choosing roots of polynomials smoothly, Israel J. Math 105 (1998), p. 203-233. Page 21 in: mat.univie.ac.at/~michor/roots.pdf. –  Peter Michor Dec 12 '12 at 18:19
    
@Peter. You're right. I edit my answer. –  Denis Serre Dec 13 '12 at 10:34
add comment

Unfortunately it can get worse than your example. There can be no continuously choosable eigenvectors at all.

Here's an example: Consider the family of matrices $$ g(t)=\begin{cases} \begin{pmatrix}1+t&0\cr 0&1-t\end{pmatrix}&\text{for $t<0$}; \cr \begin{pmatrix}1&t\cr t&1\end{pmatrix}&\text{for $t\ge 0$.} \end{cases} $$ Then the eigenvectors are $\begin{pmatrix}1\cr 0\end{pmatrix}$ and $\begin{pmatrix}0\cr1\end{pmatrix}$ for $t<0$ and $\begin{pmatrix}1\cr1\end{pmatrix}$ and $\begin{pmatrix}1\cr-1\end{pmatrix}$ for $t>0$.

Obviously there's no continuous selection possible.

share|improve this answer
add comment

See the following article which contains an overview of available results:

Andreas Kriegl, Peter W. Michor, Armin Rainer: Denjoy-Carleman differentiable perturbation of polynomials and unbounded operators. Integral Equations and Operator Theory 71,3 (2011), 407-416. (pdf)

In particular, if your mapping $f$ is Hölder continuous (of class $C^{0,\alpha}$ for $0<\alpha\le1$) then the eigenvalues can be parameterized in a $C^{0,\alpha}$ way also.

EDIT: I describe the results which seem most relevant to your question:

Let $t\mapsto A(t)$ for $t\in T$ be a parameterized family of unbounded operators in a Hilbert space $H$ with common domain of definition and with compact resolvent.

If $t\in T=\mathbb R$ and all $A(t)$ are self-adjoint then the following holds:

(A) (Rellich) If $A(t)$ is real analytic in $t\in \mathbb R$, then the eigenvalues and the eigenvectors of $A(t)$ can be parameterized real analytically in $t$.

(B) If $A(t)$ is quasianalytic of class $C^Q$ in $t\in \mathbb R$, then the eigenvalues and the eigenvectors of $A(t)$ can be parameterized $C^Q$ in $t$.

If $t\in T=\mathbb R^n$ and all $A(t)$ are normal then the following holds:

(L) If $A(t)$ is real analytic or quasianalytic of class $C^Q$ in $t\in \mathbb R^n$, then for each $t_0\in \mathbb R^n$ and for each eigenvalue $z_0$ of $A(t_0)$, there exist a neighborhood $D$ of $z_0$ in $\mathbb C$, a neighborhood $W$ of $t_0$ in $\mathbb R^n$, and a finite covering $\{\pi_k : U_k \to W\}$ of $W$, where each $\pi_k$ is a composite of finitely many mappings each of which is either a local blow-up along a real analytic or $C^Q$ submanifold or a local power substitution, such that the eigenvalues of $A(\pi_k(s))$, $s \in U_k$, in $D$ and the corresponding eigenvectors can be parameterized real analytically or $C^Q$ in $s$. If $A$ is self-adjoint, then we do not need power substitutions.

(M) If $A(t)$ is real analytic or quasianalytic of class $C^Q$ in $t\in \mathbb R^n$, then for each $t_0\in \mathbb R^n$ and for each eigenvalue $z_0$ of $A(t_0)$, there exist a neighborhood $D$ of $z_0$ in $\mathbb C$ and a neighborhood $W$ of $t_0$ in $\mathbb R^n$ such that the eigenvalues of $A(t)$, $t \in W$, in $D$ and the corresponding eigenvectors can be parameterized by functions which are special functions of bounded variation (SBV) in $t$.

share|improve this answer
add comment

(1) If the eigenvalues of $f$ always have multiplicity 1, then indeed you can make a continuous selection of eigenvectors. Say $\lambda_j(z)$, with $j=1,2,\dots,n$, denote the eigenvalues of $f(z)$ arranged in increasing order. For each $j$ choose a continuous $\alpha_j(t,z)$, with $t\in \mathbb R$ and $z\in D$ such that $$\alpha_j(\lambda_j(z),z)=1\mbox{ and }\alpha_j(\lambda_{i}(z),z)=0\mbox{ if }i\neq j.$$ Using functional calculus let us define $$p_j(z)=\alpha_j(f_j(z),z).$$ These are the rank one orthogonal projections onto the eigenspaces of $f(z)$. Since $D$ is an open subset of the plane, it only has trivial complex line bundles. So for each each $p_j(z)$ there exists a continuous section $v_j(z)\in \mathbb C^n$ such that $p_j(z)v_j(z)=v_j(z)$.

(2) The set of functions $f$ with all eigenvalues of multiplicity 1 is dense (and $G_\delta$) among the bounded continuous functions on $D$ with values on the $n\times n$ selfadjoint matrices. Here it is crucial that $D$ is at most of dimension 2. This is proven in "Density of the self-adjoint elements with finite spectrum in an irrational rotation C∗-algebra. Math. Scand. 67 (1990), 73–86.", by Choi and Elliott.

The gist of their argument is this: the set of $n\times n$ self-adjoint matrices such that at least two eigenvalues agree is a finite union of submanifolds of the set of all self-adjoint matrices, where each submanifold has codimension at least 3. This makes it that a suitable perturbation of $f$ can avoid such finite union of submanifolds provided that the domain of $f$ has dimension at most 2.

share|improve this answer
add comment

I think this might salvage the situation: Assume that you do have a path parameterized by $t$ and that it is stationary for a while any time that the multiplicity of an eigenvalue increases. In the case $n=2$ the eigenvectors are (usually) perpendicular so we could represent them as four points on the unit circle separated by $\frac{\pi}{2}$ radians . Imagine time as an axis so the eigenvectors form four black paths traveling up a cylinder. Any time the matrix becomes a scalar multiple of the identity matrix you suddenly have the solid unit circle. As long as this is a band of some width you can arrange to leave the band in the appropriate configuration.

With larger $n$ and even more general matrices I think it would be about the same. So one point is that it can not be a function of merely where you are, but also where you were and where you will be next.

A related problem is constructive versions of the Fundamental Theorem of Algebra ( cribbed from a paper by Fred Richman which I recommend.) Let $\mathbb{A} \subset \mathbb{C}$ be the field of algebraic numbers (roots of polynomials with rational coefficients) Consider degree $n+1$ monic polynomials $x^{n+1}+\sum_0^na_iz^i$ They can be parameterized by their coefficient vectors $\mathbf{a}=(a_0,a_1,\cdots,a_n) \in \mathbb{A}^n$ and by their "list" of roots $\boldsymbol\alpha=(\alpha_0,\cdots,\alpha_n) \in \mathbb{A}^n$ ordered somehow. There is an obvious continuous map (uniformly bicontinuous on bounded sets) in one direction $\boldsymbol\alpha \to \prod(z-\alpha_i)$ i.e. extract the coefficients using elementary symmetric functions. Is there a continuous mapping in the other? Read the paper (which gets into Dedikind cuts, extension to all of $\mathbb{C}$ and other matters.) As I recall, the correct target in the space of roots should instead be multisets of algebraic numbers with an appropriate metric. A motivating example is $z^2-b$ with $b$ real. For $b$ close to $0$ we have a sudden shift from the two roots spanning a horizontal line to a vertical one.

share|improve this answer
    
With respect to your first paragraph, this particular way of moving the goal posts seems to be a special case of part (L) of Peter Michor's answer. –  Igor Khavkine Dec 15 '12 at 20:39
add comment

The eigenvalues are roots of the characteristic polynomial, whose coefficients are a continuous function of the parameter. Therefore we have that the eigenvalues and parameter lie on some submanifold. By examining the parametrization things can be said about how nice this manifold is.

share|improve this answer
    
I don't understand how your use of the word "submanifold" makes sense. If you have a continuous family of diagonalizable matrices parametrized by a space $D$, then the spectrum is a continuous map from $D$ to the symmetric power $\operatorname{Sym}^n \mathbb{C}$ that doesn't necessarily lift to a continuous map with target $\mathbb{C}^n$. –  S. Carnahan Dec 12 '12 at 7:51
    
So consider the map $det(M-\lambdaI)$. This is a continuous map from $\mathbb{C}\times D$ to $\mathbb{C}$, with nice properties of the derivative. Apply the Inverse Function Theorem. –  Watson Ladd Dec 12 '12 at 20:08
1  
Are you sure about "nice properties of the derivative"? –  Charles Staats Dec 13 '12 at 14:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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