Recipe

Evaluate a polynomial at a matrix using Horner's method

Use when: you need p(T) for a specific polynomial p and operator or matrix T, and want fewer matrix multiplications than computing every power separately

Goal: the matrix p(T), computed with exactly n matrix multiplications for a degree-n polynomial

Taught in Polynomials of an operator, revisited

1. 1

   Write p(x)=c_0+c_1x+\cdots+c_nx^n as c_0+x(c_1+x(c_2+\cdots+x(c_{n-1}+xc_n)\cdots)), working from the highest power inward.

   Example

   For p(x)=x^2-x+2 (c_0=2,c_1=-1,c_2=1), the nested form is 2+x(-1+x).

   • p is already given in nested form — skip straight to the next step.
   • p is given in expanded standard form — rewrite it into nested form first, as above.

   Why: this nested form is what turns n separate powers of T into a single chain of multiply-and-add steps.

2. 2

   Start with R=c_nI, the leading coefficient times the identity matrix.

   Example

   For p(x)=x^2-x+2, R starts at c_2I=1\cdot I=I.

   Why: the identity times a scalar is what "the constant c_n, as a matrix" has to mean, since every later term is a genuine matrix.

3. 3

   Working from c_{n-1} down to c_0, replace R with TR+c_iI at each step, one coefficient at a time.

   Example

   For T=\begin{pmatrix}1&2\\0&3\end{pmatrix}: R=T\cdot I+(-1)I=\begin{pmatrix}0&2\\0&2\end{pmatrix}, then R=T\cdot R+2I=\begin{pmatrix}2&6\\0&8\end{pmatrix}.

   Why: this is Horner's method itself, and it reaches p(T) in exactly n matrix multiplications, with only one running matrix ever stored.

4. 4

   If T has a known eigenvector \mathbf v with eigenvalue \lambda, confirm p(T)\mathbf v=p(\lambda)\mathbf v as an independent check on the Horner computation above.

   Example

   T=\begin{pmatrix}1&2\\0&3\end{pmatrix} has eigenvector (1,0) with eigenvalue 1; p(T)(1,0)=(2,0), and p(1)(1,0)=2(1,0)=(2,0).

   ⚡ Shortcut

   If only one eigenvalue of p(T) is needed, not the whole matrix, skip Horner entirely: substitute that eigenvalue \lambda directly into p, since p(T) and T always share eigenvectors, with eigenvalue p(\lambda).

   Why: this uses a genuinely different, much faster fact whenever only one eigenvalue is needed, and it also catches an arithmetic slip made in the Horner steps above.