how to find/define eigenvectors as a continuous function of matrix? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:08:25Z http://mathoverflow.net/feeds/question/116123 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix how to find/define eigenvectors as a continuous function of matrix? Kjetil B Halvorsen 2012-12-11T22:54:51Z 2012-12-14T13:31:48Z <p>I asked this (with background) here <a href="http://stats.stackexchange.com/questions/38494/principal-component-analysis-bootstrap-and-probability-of-eigenvalue-collision" rel="nofollow">http://stats.stackexchange.com/questions/38494/principal-component-analysis-bootstrap-and-probability-of-eigenvalue-collision</a></p> <p>but did not really get any answers. See that post for the background.</p> <p>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 &amp; 0 \cr 0 &amp; 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 &amp; t\le 0 \cr e_1 &amp; 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.</p> <p>ADDED after the answer by Anthony Quas:</p> <p>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?</p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116129#116129 Answer by Anthony Quas for how to find/define eigenvectors as a continuous function of matrix? Anthony Quas 2012-12-11T23:57:23Z 2012-12-11T23:57:23Z <p>Unfortunately it can get worse than your example. There can be no continuously choosable eigenvectors at all.</p> <p>Here's an example: Consider the family of matrices $$g(t)=\begin{cases} \begin{pmatrix}1+t&amp;0\cr 0&amp;1-t\end{pmatrix}&amp;\text{for t&lt;0}; \cr \begin{pmatrix}1&amp;t\cr t&amp;1\end{pmatrix}&amp;\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&lt;0$ and $\begin{pmatrix}1\cr1\end{pmatrix}$ and $\begin{pmatrix}1\cr-1\end{pmatrix}$ for $t>0$.</p> <p>Obviously there's no continuous selection possible.</p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116131#116131 Answer by Watson Ladd for how to find/define eigenvectors as a continuous function of matrix? Watson Ladd 2012-12-12T00:46:03Z 2012-12-12T00:46:03Z <p>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.</p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116153#116153 Answer by Denis Serre for how to find/define eigenvectors as a continuous function of matrix? Denis Serre 2012-12-12T07:30:25Z 2012-12-14T13:31:48Z <p>The example given by Anthony Quas reveals a phenomenon discussed in Kato's book <em>Perturbation Theory for Linear Differential Operators</em>. The point is the following:</p> <ul> <li>If the symmetric matrix depends analytically upon <strong>one</strong> 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.</li> <li>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 &amp; t \\ t &amp; -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.</li> <li>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}$.</li> </ul> <p>Side remark: Kato's result is only <em>local</em>. 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.</p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116154#116154 Answer by Leonel Robert for how to find/define eigenvectors as a continuous function of matrix? Leonel Robert 2012-12-12T07:50:01Z 2012-12-12T08:05:39Z <p>(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)$. </p> <p>(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. </p> <p>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. </p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116156#116156 Answer by Peter Michor for how to find/define eigenvectors as a continuous function of matrix? Peter Michor 2012-12-12T07:56:58Z 2012-12-13T07:18:15Z <p>See the following article which contains an overview of available results:</p> <p>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. <a href="http://www.mat.univie.ac.at/~michor/DC-perturb.pdf" rel="nofollow">(pdf)</a></p> <p>In particular, if your mapping $f$ is H&ouml;lder continuous (of class $C^{0,\alpha}$ for $0&lt;\alpha\le1$) then the eigenvalues can be parameterized in a $C^{0,\alpha}$ way also.</p> <p>EDIT: I describe the results which seem most relevant to your question:</p> <p>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.</p> <p>If $t\in T=\mathbb R$ and all $A(t)$ are self-adjoint then the following holds:</p> <p>(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$. </p> <p>(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$. </p> <p>If $t\in T=\mathbb R^n$ and all $A(t)$ are normal then the following holds:</p> <p>(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. </p> <p>(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$.</p> http://mathoverflow.net/questions/116123/how-to-find-define-eigenvectors-as-a-continuous-function-of-matrix/116213#116213 Answer by Aaron Meyerowitz for how to find/define eigenvectors as a continuous function of matrix? Aaron Meyerowitz 2012-12-12T22:29:10Z 2012-12-13T07:30:55Z <p>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.</p> <p>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.</p> <p>A related problem is constructive versions of the Fundamental Theorem of Algebra ( cribbed from a <a href="http://math.fau.edu/richman/Docs/Fta.pdf" rel="nofollow">paper</a> 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.</p>