## Symmetric Matrices

For a real symmetric matrix all the eigenvalues are real. If only the dominant eigenvalue is wanted, then the Rayleigh method maybe used or the Rayleigh quotient method maybe used. The Rayleigh methods may fail however if the dominant eigenvalue is not unique. If all the eigenvalues are wanted but not the eigenvectors then Given's bisection algorithm can be used after first tridiagonalizing the symmetric matrix. If all the eigenvalues and corresponding eigenvectors are wanted then Jacobi's cyclic method can be used or if the matrix is tridiagonal then the QL algorithm as presented below may be applied.### Function List

- int Eigenvalue_Rayleigh_Method( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

Rayleigh's method is a variant of the power method for estimating the dominant eigenvalue of a symmetric matrix. The process may not converge if the dominant eigenvalue is not unique. Given the*n×n*real symmetric matrix**A**and an initial estimate of the eigenvector,*x0*, the method then normalizes*x0*, calculates*x*=**A***x0*and sets*µ*=*x*. The process is then repeated after setting^{T}x0*x0*=*x*until the relative absolute change in*µ*is less than the preassigned*tolerance*at which time the process terminates successfully or until the number of attempts exceeds*max_tries*at which time the process terminates unsuccessfully.

The function Eigenvalue_Rayleigh_Method is used if the matrix**A**is stored as a full symmetric matrix, the function Eigenvalue_Rayleigh_Method_lt is used if the matrix**A**is stored in lower triangular form and the function Eigenvalue_Rayleigh_Method_ut is used if the matrix**A**is stored in upper triangular form.

The function returns the number of iterations performed if successful and -1 if more than max_tries iterations are necessary, -2 if the initial vector or subsequent vector is 0 and -3 if the estimate for the dominant eigenvalue is 0.

- int Eigenvalue_Rayleigh_Method_lt( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

This routine is the same as Eigenvalue_Rayleigh_Method( ), described above, with the exception that the matrix*A*is stored in lower triangular form.

- int Eigenvalue_Rayleigh_Method_ut( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

This routine is the same as Eigenvalue_Rayleigh_Method( ), described above, with the exception that the matrix*A*is stored in upper triangular form.

- int Rayleigh_Quotient_Method( double *A, int n, double *eigenvalue, double x0[ ], double tolerance, int max_tries )

Rayleigh's quotient method is a variant of the inverse power method for estimating the dominant eigenvalue of a symmetric matrix. The process may not converge if the dominant eigenvalue is not unique. Given the*n × n*real symmetric matrix**A**and an initial estimate of the eigenvector,*x*, the method then normalizes_{0}*x*, calculates_{0}

*µ*=*x*_{0}^{T}**A***x*and solves (_{0}**A**-*µ***I**)*x*=*x*for_{0}*x*. The process is then repeated after setting*x*=_{0}*x*until the relative absolute change in*µ*is less than the preassigned*tolerance*at which time the process terminates successfully or until the number of attempts exceeds*max_tries*at which time the process terminates unsuccessfully. This routine has better convergence properties than that of the Rayleigh method and is usually used after the Rayleigh method has obtained a close estimate of the dominant eigenvalue and corresponding eigenvector.

The function returns the number of iterations performed if successful and -1 if more than max_tries iterations are necessary, -2 if the initial vector or subsequent vector is 0, -3 if the estimate for the dominant eigenvalue is 0 and -4 if there is not enough memory available for working storage.

- int Givens_Bisection_Method( double diagonal[ ], double off_diagonal[ ], double eigenvalues[ ], double relative_tolerance, int n )

Given the*n×n*real tridiagonal symmetric matrix**A**with diagonal,*diagonal*, and off-diagonals,*off_diagonal*, the routine Givens_Bisection_Method uses Gerschgorin's theorem to obtain bounds for the eigenvalues and then the bisection method to estimate the eigenvalues within the user specified relative tolerance,*relative_tolerance*. The off-diagonal elements begin at*off_diagonal[1]*,*off_diagonal[0]*is set to 0. The results are returned in the array*eigenvalues*. The function returns 0 if successful and -1 if there is not enough memory for working storage.

- int QL_Tridiagonal_Symmetric_Matrix( double diagonal[ ], double off_diagonal[ ], double *U, int n, int max_iteration_count )

Given the*n×n*real tridiagonal symmetric matrix**A**with diagonal,*diagonal*, and off-diagonals,*off_diagonal*, the routine QL_Tridiagonal_Symmetric_Matrix uses QL algorithm with implicit shifts of the origin to estimate the eigenvalues and eigenvectors. The off-diagonal elements begin at*off_diagonal[1]*,*off_diagonal[0]*is set to 0. The eigenvalues are returned in the array*diagonal*. The*n×n*matrix**U**should be set to the transformation matrix if the original matrix was tridiagonalized or set to the identity matrix if the original matrix is tridiagonal. Upon return,**U**contains the eigenvectors of the original matrix, the*i*column being the eigenvector corresponding the the^{th}*i*eigenvalue,^{th}*diagonal[i]*. The function returns a 0 if successful and a -1 if the process failed to converge within*max_iteration_count*iterations.

- void Jacobi_Cyclic_Method( double eigenvalues[ ], double *eigenvectors, double *A, int n )

Given the*n × n*real symmetric matrix**A**, the routine Jacobi_Cyclic_Method calculates the eigenvalues and eigenvectors of**A**by successively sweeping through the matrix**A**annihilating off-diagonal non-zero elements by a rotation of the row and column in which the non-zero element occurs. The input matrix**A**is modified during the process. The eigenvalues are returned in the array*eigenvalues*which should be dimensioned at least*n*in the calling routine. The eigenvectors are returned in the*n×n*matrix*eigenvectors*, the*i*column being the eigenvector corresponding the the^{th}*i*eigenvalue,^{th}*eigenvalue[i]*.

*C* Source Code

- The file, eigen_rayleigh_method.c, contains the routine Eigenvalue_Rayleigh_Method( ).

- The file, eigen_rayleigh_method_lt.c, contains the routine Eigenvalue_Rayleigh_Method_lt( ).

- The file, eigen_rayleigh_method_ut.c, contains the routine Eigenvalue_Rayleigh_Method_ut( ).

- The file, rayleigh_quotient_method.c, contains the routine Rayleigh_Quotient_Method( ).

- The file, givens_bisection.c, contains the routine Givens_Bisection_Method( ).

- The file, ql_tridiagonal_symmetric_matrix.c, contains the routine QL_Tridiagonal_Symmetric_Matrix( ).

- The file, jacobi_cyclic_method.c, contains the routine Jacobi_Cyclic_Method( ).