Return to Answer

edited body

Source Link

edited Jan 11, 2013 at 17:30

21.5k
2
60
113

We can do it in two steps.

Step 1: show that if $A$ is a real symmetric matrix, there is an orthogonal matrix $L$ such that $A=LHL^T$, where $L$$H$ is tridiagonal and its off-diagonal entries are non-negative. (Apply Gram-Schmidt to sets of vectors of the form $\{x,Ax,\ldots,A^mx\}$, or use Householder transformations, which is the same thing.)

Step 2. We need to show that the eigenvalues of tridiagonal matrices with non-negative off-diagonal entries are real. We can reduce to the case where $H$ is indecomposable. Assume it is $n\times n$ and let $\phi_{n-r}$ the the characteristic polynomial of the matrix we get by deleting the first $r$ rows and columns of $H$. Then $$ \phi_{n-r+1} = (t-a_r)\phi_{n-r} -b_r \phi_{n-r-1}, $$ where $b>0$. Now prove by induction on $n$ that the zeros of $\phi_{n-r}$ are real and are interlaced by the zeros of $\phi_{n-r-1}$. The key here is to observe that this induction hypothesis is equivalent to the claim that all poles and zeroes of $\phi_{n-r-1}/\phi_{n-r}$ are real, and in its partial fraction expansion all numerators are positive. From this it follows that the derivative of this rational function is negative everywhere it is defined and hence, between each consecutive pair of zeros of $\phi_{n-r-1}$ there must be a real zero of $\phi_{n-r}$.

We can do it in two steps.

Step 1: show that if $A$ is a real symmetric matrix, there is an orthogonal matrix $L$ such that $A=LHL^T$, where $L$ is tridiagonal and its off-diagonal entries are non-negative. (Apply Gram-Schmidt to sets of vectors of the form $\{x,Ax,\ldots,A^mx\}$, or use Householder transformations, which is the same thing.)

Step 2. We need to show that the eigenvalues of tridiagonal matrices with non-negative off-diagonal entries are real. We can reduce to the case where $H$ is indecomposable. Assume it is $n\times n$ and let $\phi_{n-r}$ the the characteristic polynomial of the matrix we get by deleting the first $r$ rows and columns of $H$. Then $$ \phi_{n-r+1} = (t-a_r)\phi_{n-r} -b_r \phi_{n-r-1}, $$ where $b>0$. Now prove by induction on $n$ that the zeros of $\phi_{n-r}$ are real and are interlaced by the zeros of $\phi_{n-r-1}$. The key here is to observe that this induction hypothesis is equivalent to the claim that all poles and zeroes of $\phi_{n-r-1}/\phi_{n-r}$ are real, and in its partial fraction expansion all numerators are positive. From this it follows that the derivative of this rational function is negative everywhere it is defined and hence, between each consecutive pair of zeros of $\phi_{n-r-1}$ there must be a real zero of $\phi_{n-r}$.

We can do it in two steps.

Step 1: show that if $A$ is a real symmetric matrix, there is an orthogonal matrix $L$ such that $A=LHL^T$, where $H$ is tridiagonal and its off-diagonal entries are non-negative. (Apply Gram-Schmidt to sets of vectors of the form $\{x,Ax,\ldots,A^mx\}$, or use Householder transformations, which is the same thing.)

Step 2. We need to show that the eigenvalues of tridiagonal matrices with non-negative off-diagonal entries are real. We can reduce to the case where $H$ is indecomposable. Assume it is $n\times n$ and let $\phi_{n-r}$ the the characteristic polynomial of the matrix we get by deleting the first $r$ rows and columns of $H$. Then $$ \phi_{n-r+1} = (t-a_r)\phi_{n-r} -b_r \phi_{n-r-1}, $$ where $b>0$. Now prove by induction on $n$ that the zeros of $\phi_{n-r}$ are real and are interlaced by the zeros of $\phi_{n-r-1}$. The key here is to observe that this induction hypothesis is equivalent to the claim that all poles and zeroes of $\phi_{n-r-1}/\phi_{n-r}$ are real, and in its partial fraction expansion all numerators are positive. From this it follows that the derivative of this rational function is negative everywhere it is defined and hence, between each consecutive pair of zeros of $\phi_{n-r-1}$ there must be a real zero of $\phi_{n-r}$.

Source Link

created Jan 11, 2013 at 16:59

12.1k
5
37
61

We can do it in two steps.

Step 1: show that if $A$ is a real symmetric matrix, there is an orthogonal matrix $L$ such that $A=LHL^T$, where $L$ is tridiagonal and its off-diagonal entries are non-negative. (Apply Gram-Schmidt to sets of vectors of the form $\{x,Ax,\ldots,A^mx\}$, or use Householder transformations, which is the same thing.)

Step 2. We need to show that the eigenvalues of tridiagonal matrices with non-negative off-diagonal entries are real. We can reduce to the case where $H$ is indecomposable. Assume it is $n\times n$ and let $\phi_{n-r}$ the the characteristic polynomial of the matrix we get by deleting the first $r$ rows and columns of $H$. Then $$ \phi_{n-r+1} = (t-a_r)\phi_{n-r} -b_r \phi_{n-r-1}, $$ where $b>0$. Now prove by induction on $n$ that the zeros of $\phi_{n-r}$ are real and are interlaced by the zeros of $\phi_{n-r-1}$. The key here is to observe that this induction hypothesis is equivalent to the claim that all poles and zeroes of $\phi_{n-r-1}/\phi_{n-r}$ are real, and in its partial fraction expansion all numerators are positive. From this it follows that the derivative of this rational function is negative everywhere it is defined and hence, between each consecutive pair of zeros of $\phi_{n-r-1}$ there must be a real zero of $\phi_{n-r}$.