Diagonalization and Matrix Powers

Definition Let $A$ be a real $n \times n$ matrix. An eigenbasis of $A$ is an ordered basis $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ of $\mathbb{R}^n$ in which every vector is an eigenvector of $A$, so that $A\mathbf{v}_j = \lambda_j\mathbf{v}_j$ for real numbers $\lambda_1, \dots, \lambda_n$. The eigenvalues in this list need not be distinct. The eigenvector matrix $P = [\mathbf{v}_1 \ \cdots \ \mathbf{v}_n]$ is invertible because its columns form a basis, and $D$ denotes the diagonal matrix with $\lambda_1, \dots, \lambda_n$ on its diagonal in the same order. The coordinates of a vector $\mathbf{x}$ in this basis, its eigen-coordinates, are

A few eigenvectors are not enough. The list must contain $n$ linearly independent eigenvectors.

Definition A real $n \times n$ matrix $A$ is diagonalizable over $\mathbb{R}$ if there are an invertible real $n \times n$ matrix $P$ and a real diagonal matrix $D$ with

Such a factorization is a diagonalization of $A$. The following theorem says exactly which $P$ and $D$ work. Let $P$ be invertible with columns $\mathbf{p}_1, \dots, \mathbf{p}_n$, and let $D$ be diagonal with entries $d_1, \dots, d_n$. Then $A = PDP^{-1}$ if and only if $A\mathbf{p}_j = d_j\mathbf{p}_j$ for every $j$, that is, if and only if the columns of $P$ form an eigenbasis of $A$ with eigenvalues $d_1, \dots, d_n$ in matching order. The proof compares columns. Since $P$ is invertible, $A = PDP^{-1}$ is equivalent to $AP = PD$, and column $j$ of $AP$ is $A\mathbf{p}_j$ while column $j$ of $PD$ is $d_j\mathbf{p}_j$. So $A$ is diagonalizable over $\mathbb{R}$ exactly when $\mathbb{R}^n$ has an eigenbasis of $A$, and then $D = P^{-1}AP$ is the matrix of the map $\mathbf{x} \mapsto A\mathbf{x}$ in that eigenbasis. Allowing complex entries in $P$ and $D$ gives diagonalizability over $\mathbb{C}$, and the choice of scalars can change the answer.

Definition If $A = PDP^{-1}$ with $D$ diagonal, then for every integer $k \ge 0$

where $A^0 = I$. The reason is that neighboring factors cancel. For example $A^2 = PDP^{-1}PDP^{-1} = PD^2P^{-1}$, and each further factor of $A$ cancels one more pair $P^{-1}P$. To apply $A^k$ to a vector $\mathbf{x}$, compute its eigen-coordinates $\mathbf{c} = P^{-1}\mathbf{x}$, multiply each $c_j$ by $d_j^k$, and multiply the result by $P$. If every $d_j$ is nonzero, then $A$ is invertible with $A^{-1} = PD^{-1}P^{-1}$, and the formula holds for negative $k$ as well.

Definition A repeated linear update is a sequence of vectors $\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots$ in $\mathbb{R}^n$ produced by a fixed real $n \times n$ matrix $A$ through the rule

so that $\mathbf{x}_k = A^k\mathbf{x}_0$. Such a rule is also called a discrete linear dynamical system. Suppose $A$ has an eigenbasis $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ with eigenvalues $\lambda_1, \dots, \lambda_n$, and write the starting vector as $\mathbf{x}_0 = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n$. Then

A term with $c_j \ne 0$ grows when $\lvert \lambda_j \rvert > 1$, dies out when $\lvert \lambda_j \rvert < 1$ and stays fixed when $\lambda_j = 1$, and a negative $\lambda_j$ makes it change sign at every step.

Definition Let $A$ be a real $n \times n$ matrix whose distinct real eigenvalues are $\lambda_1, \dots, \lambda_p$, and let $E_{\lambda} = \operatorname{Null}(A - \lambda I)$ be the eigenspace of $\lambda$. Then $A$ is diagonalizable over $\mathbb{R}$ if and only if

The reason is that bases of the separate eigenspaces, listed together, always form a linearly independent list. In a linear relation among these vectors, group the terms by eigenspace. Each group adds up to a vector of its eigenspace. If some of these sums were not $\mathbf{0}$, they would be eigenvectors for distinct eigenvalues adding up to $\mathbf{0}$, which their independence rules out. So every group adds up to $\mathbf{0}$, and since each group uses the vectors of one basis, all coefficients are zero. The combined list is an eigenbasis exactly when it has $n$ vectors. Conversely, an eigenbasis has at most $\dim E_{\lambda_j}$ of its vectors in each $E_{\lambda_j}$, so when one exists the dimensions add up to at least $n$, and the independent combined list shows they never add up to more. Several consequences follow. If $A$ has $n$ distinct real eigenvalues, it is diagonalizable over $\mathbb{R}$, but this sufficient condition is not necessary, as the diagonal matrix with entries $2, 2, 3$ below shows. If the characteristic polynomial $\chi_A$ factors into real linear factors, then $A$ is diagonalizable over $\mathbb{R}$ if and only if every eigenvalue has geometric multiplicity equal to its algebraic multiplicity, since the algebraic multiplicities add up to $n$ and no geometric multiplicity exceeds its algebraic one. If $\chi_A$ has a nonreal root, then $A$ is not diagonalizable over $\mathbb{R}$. A defective matrix, one with an eigenvalue whose geometric multiplicity is smaller than its algebraic multiplicity, is not diagonalizable even when complex scalars are allowed.