A vector x is called an eigenvector of a matrix #{A} with an eigenvalue #{λ}, if #{Ax=λx}. Matrix diagonalization means finding all eigenvalues λ_i and (optionally) eigenvectors x_i of the matrix #{A}. If #{A} is hermitian then its eigenvalues are real and its eigenvectors #{X={x₁,...,x_n}} form a full basis in which the matrix #{A} is diagonal #{X^TAX=diag{λ₁,...,λ_n}}.

Orthogonal transformations #{A→Q^TAQ}, where #{Q^TQ=1}, preserve eigenvalues and eigenvectors. Therefore one of the strategies is to apply a sequence of orthogonal transformations which (iteratively) eliminate nondiagonal elements.

QR/QL algorithm. If we know QR (or QL) decomposition of real symmetric matrix A, then the orthogonal transformation #{A~→~Q^TAQ=RQ} partly turns the matrix A into diagonal form. Successive iterations eventually make it diagonal. If there are degenerate eigenvalues there will be a corresponding block-diagonal sub-matrix. For convergence properties it is better to use shifts: instead of QR[A] we do QR[A-s1] and then A~→~RQ+s1. The shift #{s} can be chosen as A_nn. As soon as an eigenvalue is found the matrix is deflated, that is the corresponding row and column are crossed out.

Tridiagonalization. Each iteration of the QR/QL is an #{O(n³)} operation. On a tridiagonal matrix it is only #{O(n)}. Therefore the effective strategy is first to make the matrix tridiagonal and then apply the QR/QL algorithm. Tridiagonalization of a matrix is a non-iterative operation with a fixed number of steps.

Problems

1. The spring constant (fjederkonstant) is to be determined from an experiment where measuerd were the periods of harmonic oscillations of different masses hung on the spring. The masses were m={0.0698, 0.0743, 0.1194}±0.0001~kg, the corresponding periods were T={0.78,0.80,1.00}±0.01~s. Estimate the spring constant (with the error, of course).
2. Implement QR/QL algorithm with shifts and deflation for real symmetric matrices.
3. Diagonalise the matrix A=[[1,2,3,4];[2,1,5,6];[3,5,1,7];[4,6,7,1]].