wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Prove/Disprove a function is continuous
        
(Message started by: archau on Dec 13^th, 2007, 4:59pm)

Title: Prove/Disprove a function is continuous
Post by archau on Dec 13^th, 2007, 4:59pm

Consider the euclidean space of all (2n+1) x (2n+1) matrices.

Prove/Disprove that the function mapping an element A to is largest real eigenvalue is continuous.

Note: There was a mistake in the original statement of the problem so I changed it.

Title: Re: Prove a function is continuous
Post by Aryabhatta on Dec 14^th, 2007, 2:16am

Perhaps this should be in the putnam section.

Title: Re: Prove a function is continuous
Post by Obob on Dec 14^th, 2007, 8:11pm

I think this result is false. Consider the family of polynomials (x + 1)(x² + a²), where a is a nonzero real number. Expanding, this is the polynomial x³ + x² + a²x + a². This is the characteristic polynomial of the companion matrix

0 0 -a²
1 0 -a²
0 1 -1

So the eigenvalues of this matrix are -1, ia, and -ia. Hence the largest real eigenvalue is -1. But as we let a->0, the eigenvalues of the limit matrix are -1, 0, and 0, so that the largest real eigenvalue is 0.

The problem here is that a conjugate pair of complex eigenvalues can specialize in the limit to a real eigenvalue with multiplicity two.

Here's a problem for somebody else to solve: Show that the problem becomes true again if we consider instead the space of symmetric n x n matrices.

Title: Re: Prove a function is continuous
Post by archau on Dec 15^th, 2007, 6:52am

You are correct, I will add a correction to the original problem.

Title: Re: Prove a function is continuous
Post by Aryabhatta on Dec 15^th, 2007, 12:58pm

on 12/14/07 at 20:11:07, Obob wrote:

Here's a problem for somebody else to solve: Show that the problem becomes true again if we consider instead the space of symmetric n x n matrices.

Do you mean symmetric real matrices (sorry if it is obvious, I am rusty...)

In which case, I think the [hide] Rayleigh Quotient [/hide] should somehow do it, though I am not confident...

Title: Re: Prove/Disprove a function is continuous
Post by Obob on Dec 15^th, 2007, 1:22pm

Yes, I did mean real symmetric; otherwise in more generality you could do it for complex Hermitian matrices.

That idea does seem to be fruitful, Aryhabhatta. It's actually quite a bit nicer than what I was thinking of. Anybody care to flesh out the details?

Title: Re: Prove/Disprove a function is continuous
Post by Hippo on Dec 28^th, 2007, 2:09am

I thing the main problem here is the unstability of being real.
To select one from the complex numbers is not trivial.
What about the mapping to set of eigenvalues with multicities. Is this mapping (from arbitrary matrices) continuous?

Title: Re: Prove/Disprove a function is continuous
Post by Eigenray on Jan 6^th, 2008, 6:22pm

on 12/28/07 at 02:09:05, Hippo wrote:

Yes, exactly. Choosing the largest real eigenvalue is a composition of two functions: (matrix) -> (set of eigenvalues) -> (largest real eigenvalue), but only the first is continuous.

To state this formally: fix a matrix A, with (multi-)set of eigenvalues S. Then for any http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif>0, there exists a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif>0 such that: whenever each entry of A' is within http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/delta.gif of the corresponding entry of A, there exists a bijection between S and S' such that corresponding elements are within http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif of each other.

For otherwise, there's an http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif>0 for which we can pick a sequence of matrices A_n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif A entry-wise, but where no S_n is uniformly within http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif of S under any ordering.

Now put an arbitrary ordering on S and S_n so that they become elements of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbc.gif^N. Now, two sets close in one order need not be in another, but this is okay: there are finitely many coordinates, and moreover, since A_n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif A, the entries of {A_n} are all bounded, and therefore so are the entries of {S_n}. So by compactness, we may pass to a subsequence such that S_n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif S' http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbc.gif^N.

Let p_n(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(x-S_n(i)) be the characteristic polynomial of A_n. For any x, p_n(x) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif p'(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(x-S'(i)). But also p_n(x) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif p(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(x-S(i)). Therefore S=S', and this contradicts our assumption that each S_n is at least http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif away from S in some coordinate.