How can we explicitly find the maximum eigenvalue of a tridiagonal matrix? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:09:19Z http://mathoverflow.net/feeds/question/26207 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26207/how-can-we-explicitly-find-the-maximum-eigenvalue-of-a-tridiagonal-matrix How can we explicitly find the maximum eigenvalue of a tridiagonal matrix? unknown (google) 2010-05-27T23:02:44Z 2010-05-28T13:34:30Z <p>I just came across a matrix of the form <code>$A:=\begin{pmatrix} 0&amp;-\frac{c_0}{b_0}&amp;0&amp;\cdots&amp;0\\-\frac{a_1}{b_1}&amp;0&amp;-\frac{c_1}{b_1}&amp;\cdots&amp;0\\0&amp;-\frac{a_2}{b_2}&amp;0&amp;\cdots&amp;0\\ \vdots&amp;\vdots&amp;\ddots&amp;\ddots&amp;-\frac{a_{N-1}}{b_{N-1}}\\0&amp;\cdots&amp;\cdots&amp;-\frac{a_N}{b_N}&amp;0 \end{pmatrix}$</code> for some N$\in \mathbb{Z}^+$ where <code>$a_n=-\frac{1}{2}\alpha(\beta^2n^2-rn), \ b_n=1+\alpha(\beta^2n^2+r), and \ c_n=-\frac{1}{2}\alpha(\beta^2n^2+rn)\$</code>such that $\alpha, \beta,r$ are known real constants.</p> <p>From the Gershgorin circle theorem, I know that its maximum eigenvalue must lie in the Gershgorin discs. However, despite it being quite sparse, I could not get an explicit formula for its maximum eigenvalue. </p> <p>I have tried solving the Av=$\lambda$v equation, where v is an eigenvector and $\lambda$ is an eigenvalue, in which I obtain a recurrence relation, but I didn't have an initial boundary condition. The equation det($\lambda$I-A)=0, where I is the identity matrix, also gives me a complicated equation that I can't solve.</p> <p>Can anyone tell me what I have missed or is this an impossible-to-solve problem?</p> http://mathoverflow.net/questions/26207/how-can-we-explicitly-find-the-maximum-eigenvalue-of-a-tridiagonal-matrix/26216#26216 Answer by Wadim Zudilin for How can we explicitly find the maximum eigenvalue of a tridiagonal matrix? Wadim Zudilin 2010-05-28T01:18:44Z 2010-05-28T01:33:41Z <p>Let me try to expand a little bit the problem (so it's too long for a usual comment). </p> <p>Consider the determinant $D_N=D_N(\lambda;a_1,\dots,a_{N-1};b_1,\dots,c_{N-1})$ of the corresponding matrix $\lambda-A$. Expanding the determinant along the first row gives $$D_N(\lambda;a_1,\dots,a_{N-1};b_1,\dots,b_{N-1}) =\lambda D_{N-1}(\lambda;a_2,\dots,a_{N-1};b_2,\dots,b_{N-1}) -a_1b_1D_{N-2}(\lambda;a_3,\dots,a_{N-1};b_3,\dots,b_{N-1});$$ in other words, $$D_N/D_{N-1}=\lambda-\frac{a_1b_1}{D_{N-1}/D_{N-2}} =\dots =\lambda-\frac{a_1b_1}{\lambda-\dfrac{a_2b_2}{\lambda-\dfrac{a_3b_3}{\dots -\dfrac{a_{N-1}b_{N-1}}{\lambda}}}}.$$ In order to get some information about the asymptotics of the zero(s) of $D_N(\lambda)/D_{N-1}(\lambda)$ one really have to have some knowledge about the $a_ib_i$, $i=1,2,\dots$. This reduces the problem to a problem for the related family of orthogonal polynomials and even Deift's book is too advanced, it is the best source on this.</p> http://mathoverflow.net/questions/26207/how-can-we-explicitly-find-the-maximum-eigenvalue-of-a-tridiagonal-matrix/26262#26262 Answer by alext87 for How can we explicitly find the maximum eigenvalue of a tridiagonal matrix? alext87 2010-05-28T13:34:30Z 2010-05-28T13:34:30Z <p>This matrix is not symmetric but it looks like the entries $\frac{c_i}{b_i}$ and $\frac{a_i}{b_i}$ are of the same sign. This matrix can then be made symmetric by a similarity transformation. A really clear explanation of the details are in: <a href="http://digilander.libero.it/foxes/matrix/convert_unsym_trid_to_sym.pdf" rel="nofollow">http://digilander.libero.it/foxes/matrix/convert_unsym_trid_to_sym.pdf</a></p> <p>So we may suppose that your tridiagonal matrix is in fact symmetric of degree n+1. But then there is an easy recursive relation between the characteristic equation of the degree n+1 matrix and lower dimensional ones. See: <a href="http://www.physics.arizona.edu/~restrepo/475A/Notes/sourcea/node59.html" rel="nofollow">http://www.physics.arizona.edu/~restrepo/475A/Notes/sourcea/node59.html</a></p> <p>Solving this recursive equation should give you the characteristic equation of the symmetric tridiagonal matrix. Working out the roots of this equation should then give you all the eigenvalues for the original matrix as they are similar. </p> <p>I leave you to work through the details. </p> <p>Hope that helps. </p>