Diagonalization and Powers of a Matrix

19.1 Diagonalization of a Matrix

Suppose for a given matrix \(A\), we have \(n\) linearlly independent eigenvectros and we put them in a matrix \(S\). Then \(AS = A \begin{bmatrix} x_1 & x_2 & ... & x_n \end{bmatrix}\), where each \(x_i\) is the eigenvector. But for each of the eigenvectors, \(Ax_i = \lambda_ix_i\). Hence, \(AS = A \begin{bmatrix} x_1 & x_2 & ... & x_n \end{bmatrix} = \begin{bmatrix} \lambda_1x_1 & \lambda_2x_2 & ... & \lambda_nx_n \end{bmatrix} = \begin{bmatrix} x_1 & x_2 & ... & x_n \end{bmatrix}diag(\lambda_i) = S\Lambda\). Hence, \(AS = S\Lambda\), where \(\Lambda\) is a diagonal matrix containing eigenvalues and \(S\) is the matrix of eigenvectors as the columns. If \(S\) is invertible, i.e. the eigenvectors are independent, the equation can be rewritten as \(S^{-1}AS = \Lambda\) or \(A = S \Lambda S^{-1}\).

19.2 Powers of a Matrix

Suppose the eigenvalues and eigenvectors of the matrix \(A\) are \(\lambda\) and \(x\), i.e. \(Ax = \lambda x\). Then, \(A^2x = A\lambda x = \lambda Ax = \lambda\lambda x = \lambda^2 x\). Using the equation \(A = S\Lambda S^{-1}\), we derive at the same conclusion, \(A^2 = (S\Lambda S^{-1})^2 = S\Lambda S^{-1}S\Lambda S^{-1} = S \Lambda^2 S^{-1}\). Hence, \(A^k = S \Lambda^k S^{-1}\).

Theorem: \(A^k \to 0\) as \(k \to \infty\) if all \(|\lambda_i| < 1\). The proof follows from the equation \(A^k = S \Lambda^k S^{-1}\). As \(K \to \infty\), \(|\lambda_i|^k \to 0\). Hence, \(\Lambda^k \to 0 \implies A^k \to 0\). This holds true only if the eigenvectors of \(A\) are independent.

One thing to note is: \(A\) is sure to have \(n\) independent eigenvectors if all of it’s eigenvalues are different. For repeated eigenvalues, we may or may not have \(n\) independent eigenvectors.

19.3 Solution of Difference Equation (\(u_{k+1} = Au_k\))

Let us start with a vector \(u_0\), then \(u_1 = Au_0, u_2 = A^2u_1, ... ,u_k = A^ku_0\). Let us represent \(u_0\) as the combinations of eigenvectors, i.e. \(u_0 = c_1x_1 + c_2x_2 + ... + c_nx_n = Sc\). Then \(Au_0 = c_1Ax_1 + c_2Ax_2 + ... + c_nAx_n = c_1\lambda_1x_1 + c_2\lambda_2x_2 + ... + c_n\lambda_nx_n = \Lambda Sc\). Similarly, \(A^ku_0 = c_1\lambda_1^kx_1 + c_2\lambda_2^kx_2 + ... + c_n\lambda_n^kx_n = \Lambda^kSc\).

Example: Let us take an example of Fibonacci Number. They follow a second order difference equation \(F_{k+2} = F_{k+1} + F_{k}\), where \(F_0=0;F_1=1\). Let \(u_k = \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}\). If we consider two equations: \(F_{k+2} = F_{k+1} + F_{k}\) and \(F_{k+1} = F_{k+1}\), these two equations can be transformed as \(u_{k+1} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}u_k\). This transforms the problem into a first order difference equation.

For \(A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\), \(|A - \lambda I| = \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix} = \lambda^2 - \lambda - 1\). Hence, \(\lambda = \frac{1 \pm \sqrt{5}}{2}\), i.e. \(\lambda_1 = \frac{1 + \sqrt{5}}{2} \approx 1.618; \lambda_2 = \frac{1 - \sqrt{5}}{2} \approx -0.618\). The sequence of Fibonacci number is: 0,1,1,2,3,5,8,13,…, it should be noted that they are growing by a factor of the larger eigenvalue. The eigenvectors are: \(x_1 = \begin{bmatrix} \lambda_1 \\ 1 \end{bmatrix}; x_2 = \begin{bmatrix} \lambda_2 \\ 1 \end{bmatrix}\). The starting vector \(u_0\) can be given as \(u_0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\). The vector \(c\) can be found by solving \(u_0 = c_1x_1 + c_2x_2\).