Matrix Powers and Polynomial Functions

Definition Let $A \in \mathbb{F}^{n \times n}$ and let $p(t) = a_0 + a_1 t + \cdots + a_d t^d$ be a polynomial with coefficients in $\mathbb{F}$. The matrix $p(A)$ is

with $A^0 = I$. The same recipe defines $p(T)$ for a linear operator $T \colon V \to V$ on a finite-dimensional space, where a power means repeated composition. Evaluation respects the algebra of polynomials, so $(p + q)(A) = p(A) + q(A)$, $(cp)(A) = c\,p(A)$ and $(pq)(A) = p(A)\,q(A)$. In particular any two polynomials in the same matrix commute. Evaluation also respects similarity. If $B = P^{-1}AP$ with $P \in \mathbb{F}^{n \times n}$ invertible, the adjacent factors $PP^{-1}$ cancel, and induction on $k$ gives

for every $k \ge 0$. A linear combination of these identities gives $p(B) = P^{-1}p(A)P$. So a polynomial of an operator can be computed in any convenient basis and converted back. Watch for this. The matrix $p(A)$ is not obtained by applying $p$ to each entry of $A$.

Definition Let $A \in \mathbb{F}^{n \times n}$ have minimal polynomial $\mu_A$, the monic polynomial of least degree $m$ with $\mu_A(A) = 0$. Every polynomial that annihilates $A$ is a multiple of $\mu_A$. For a polynomial $p$ over $\mathbb{F}$, division with remainder gives unique polynomials $q$ and $r$ with

and then $p(A) = q(A)\,\mu_A(A) + r(A) = r(A)$. Three consequences follow.

1. Two polynomials give the same matrix, $p(A) = s(A)$, exactly when $\mu_A$ divides $p - s$. If $\mu_A$ has no repeated root in $\mathbb{C}$, it suffices that $p$ and $s$ agree at every root of $\mu_A$ in $\mathbb{C}$, that is at every eigenvalue of $A$ viewed as a complex matrix. For a real matrix the nonreal roots count too. The quarter turn $R$ with rows $(0, -1)$ and $(1, 0)$ has $\mu_R(t) = t^2 + 1$ and no real eigenvalue, yet the polynomials $t$ and $0$ give different matrices. When $\mu_A$ has a repeated root, even agreement at every root in $\mathbb{C}$ no longer guarantees $p(A) = s(A)$.

2. The matrices $I, A, \dots, A^{m-1}$ are linearly independent, because a nontrivial relation among them would be a nonzero polynomial of degree less than $m$ that annihilates $A$. So each power $A^k$ is a combination of these $m$ matrices with uniquely determined coefficients, the coefficients of the remainder of $t^k$.

3. Every orbit satisfies a recurrence. If $\mu_A(t) = t^m + c_{m-1}t^{m-1} + \cdots + c_0$ and $x_k = A^k x$, multiplying $\mu_A(A) = 0$ by $A^k$ and applying it to $x$ gives, for all $k \ge 0$,

   $$\begin{aligned} x_{k+m} &= -c_{m-1}\,x_{k+m-1} \\[0.4em] &\quad - \cdots - c_0\,x_k. \end{aligned}$$

   Applying a linear functional to both sides gives the same scalar recurrence for the measured numbers. A particular starting vector may satisfy a shorter recurrence. An eigenvector with eigenvalue $\lambda$ already satisfies $x_{k+1} = \lambda x_k$.

Definition A matrix $N \in \mathbb{F}^{n \times n}$ is nilpotent if $N^s = 0$ for some integer $s \ge 1$. Let $A = S + N$ with $S, N \in \mathbb{F}^{n \times n}$, where $S$ and $N$ commute, $SN = NS$, and $N^s = 0$. Then for every integer $k \ge 0$

The proof is induction on $k$, and the case $k = 0$ reads $I = I$. Without the cutoff at $s - 1$, the formula for $k$ is the full binomial sum over $0 \le j \le k$. Multiply it by $S + N$ on the right. Because $N^j S = S N^j$, one part keeps each power of $N$ and raises the power of $S$ by one, and the other part raises the power of $N$ by one. The coefficient of $S^{k+1-j}N^j$ becomes $\binom{k}{j} + \binom{k}{j-1} = \binom{k+1}{j}$ by Pascal’s identity, which is the full sum for $k + 1$. Finally every term with $j \ge s$ contains $N^s = 0$ and drops out. The upper limit $j \le k$ also keeps every exponent of $S$ nonnegative, which matters when $S$ is not invertible. The usual case is $S = \lambda I$, which commutes with every $N$.

Definition The Jordan block of size $s$ with eigenvalue $\lambda \in \mathbb{F}$ is $J_s(\lambda) = \lambda I + N$, where $N \in \mathbb{F}^{s \times s}$ has ones directly above the diagonal and zeros elsewhere. The matrix $N$ sends $e_1$ to $0$ and $e_j$ to $e_{j-1}$ for $j \ge 2$, so $N^j$ has ones on the $j$th diagonal above the main one, $N^{s-1} \ne 0$ and $N^s = 0$. Since $\lambda I$ commutes with $N$, the binomial expansion gives, for every $k \ge 0$,

So $J_s(\lambda)^k$ is upper triangular and constant along each diagonal. Its entry in position $(i, i + j)$ is $\binom{k}{j}\lambda^{k-j}$ for $j \le k$ and $0$ for $j > k$. For $\lambda = 0$ read $\lambda^0 = 1$, and the formula gives $J_s(0)^k = N^k$, which is $0$ for $k \ge s$. No negative power of $\lambda$ ever appears. If $A = PJP^{-1}$ where $J$ is a Jordan form, block diagonal with Jordan blocks, then $A^k = PJ^kP^{-1}$ and $J^k$ is computed one block at a time. Every matrix in $\mathbb{C}^{n \times n}$ has a Jordan form, and a real matrix has a real one when all its eigenvalues are real.

Definition A Jordan chain of length $s$ for an eigenvalue $\lambda$ of $A \in \mathbb{F}^{n \times n}$ is a list of nonzero vectors $v_1, \dots, v_s$ with $(A - \lambda I)v_1 = 0$ and $(A - \lambda I)v_j = v_{j-1}$ for $2 \le j \le s$. Write $A = \lambda I + (A - \lambda I)$, two commuting parts. Since $(A - \lambda I)^j v_s = v_{s-j}$ for $j < s$ and $(A - \lambda I)^s v_s = 0$, the binomial expansion gives

For $k \ge s - 1$ the coefficient of the eigenvector $v_1$ is $\binom{k}{s-1}\lambda^{k-s+1}$. When $\lambda \ne 0$ this is $\lambda^k$ times a polynomial in $k$ of degree $s - 1$. This controls the long-run behavior of powers. Let $A \in \mathbb{C}^{n \times n}$, where a real matrix is included with its complex eigenvalues.

1. The powers $A^k$ tend to $0$ as $k \to \infty$ exactly when every eigenvalue satisfies $\lvert \lambda \rvert < 1$.
2. The powers $A^k$ for $k \ge 0$ are bounded exactly when every eigenvalue satisfies $\lvert \lambda \rvert \le 1$ and every eigenvalue with $\lvert \lambda \rvert = 1$ has only Jordan blocks of size $1$.

For the proof, write $A = PJP^{-1}$ with $J$ a Jordan form. The identities $A^k = PJ^kP^{-1}$ and $J^k = P^{-1}A^kP$ with $P$ fixed show that $A^k$ is bounded, or tends to $0$, exactly when $J^k$ does. For $0 < \lvert \lambda \rvert < 1$ each entry of a block power has absolute value at most $k^j \rho^{k-j}$ with $\rho = \lvert \lambda \rvert$. The ratio of consecutive terms of $k^j\rho^k$ tends to $\rho$, so from some $k$ on it stays below a fixed $q < 1$, and the sequence is dominated by a decaying geometric sequence. Blocks with $\lambda = 0$ vanish after $s$ steps. A block of size at least $2$ with $\lvert \lambda \rvert = 1$ has entry $k\lambda^{k-1}$ in position $(1, 2)$, of absolute value $k$, and an eigenvalue with $\lvert \lambda \rvert > 1$ puts $\lambda^k$ on the diagonal. Watch for this. Decay is an eventual statement. A long chain, a large entry above the diagonal or an ill-conditioned basis $P$ can make early powers large.