TAOCP 4.6.4 Exercise 70
Write X= \begin{pmatrix} x & u\\ v & Y
Section 4.6.4: Evaluation of Polynomials
Exercise 70. ▶ [HM25] The characteristic polynomial $f_X(\lambda)$ of a matrix $X$ is defined to be $\det(\lambda I - X)$. Prove that if $X = \binom{u\ v}{w\ Y}$, where $X$, $u$, $v$, and $Y$ are respectively of sizes $n \times n$, $1 \times (n-1)$, $(n-1) \times 1$, and $(n-1) \times (n-1)$, we have
$$f_X(\lambda) = f_Y!\left(\lambda - x - \frac{ue}{\lambda} - \frac{uYe}{\lambda^2} - \frac{uY^2e}{\lambda^3} - \cdots\right).$$
Show that this relation allows us to compute the coefficients of $f_X$ with about $\frac{1}{3}n^4$ multiplications, $\frac{1}{3}n^4$ addition-subtractions, and no divisions. Hint: Use the identity
$$\begin{pmatrix} A & B \ C & D \end{pmatrix} = \begin{pmatrix} I & 0 \ D & I \end{pmatrix} \begin{pmatrix} A - BD^{-1}C & B \ 0 & I \end{pmatrix} \begin{pmatrix} I & 0 \ D^{-1}C & I \end{pmatrix},$$
which holds for any matrices $A$, $B$, $C$, $D$ of respective sizes $l \times l$, $l \times m$, $m \times l$, and $m \times m$ when $D$ is nonsingular.
Verified: yes
Solve time: 6m13s
Solution
Write
$$ X= \begin{pmatrix} x & u\ v & Y \end{pmatrix}, $$
where $x$ is a scalar, $u$ is $1\times(n-1)$, $v$ is $(n-1)\times1$, and $Y$ is $(n-1)\times(n-1)$.
Then
$$ \lambda I-X= \begin{pmatrix} \lambda-x & -u\ -v & \lambda I-Y \end{pmatrix}. $$
Let
$$ A=\lambda-x,\qquad B=-u,\qquad C=-v,\qquad D=\lambda I-Y. $$
For all $\lambda$ such that $D$ is nonsingular, the Schur complement identity gives
$$ \det \begin{pmatrix} A&B\ C&D \end{pmatrix} = \det(D)\det(A-BD^{-1}C). $$
Indeed, the factorization from the hint is
$$ \begin{pmatrix} A&B\ C&D \end{pmatrix} = \begin{pmatrix} I&BD^{-1}\ 0&I \end{pmatrix} \begin{pmatrix} A-BD^{-1}C&0\ 0&D \end{pmatrix} \begin{pmatrix} I&0\ D^{-1}C&I \end{pmatrix}, $$
and the outer matrices have determinant $1$.
Therefore,
$$ \begin{aligned} f_X(\lambda) &= \det(\lambda I-X)\ &= \det(\lambda I-Y), \det!\bigl((\lambda-x)-u(\lambda I-Y)^{-1}v\bigr). \end{aligned} $$
Since the second determinant is $1\times1$,
$$ f_X(\lambda) = f_Y(\lambda) \left( \lambda-x-u(\lambda I-Y)^{-1}v \right). \tag{1} $$
Now expand the resolvent formally in powers of $\lambda^{-1}$:
$$ (\lambda I-Y)^{-1} = \lambda^{-1} \left(I-\lambda^{-1}Y\right)^{-1} = \lambda^{-1}\sum_{k\ge0}\lambda^{-k}Y^k. $$
Hence
$$ u(\lambda I-Y)^{-1}v = \sum_{k\ge0}\frac{uY^kv}{\lambda^{k+1}}, $$
so (1) becomes
$$ f_X(\lambda) = f_Y(\lambda) \left( \lambda-x -\frac{uv}{\lambda} -\frac{uYv}{\lambda^2} -\frac{uY^2v}{\lambda^3} -\cdots \right). \tag{2} $$
This is the required relation.
We now show how to compute the coefficients of $f_X$ recursively from those of $f_Y$.
Write
$$ f_Y(\lambda) = \lambda^{n-1} +c_1\lambda^{n-2} +\cdots +c_{n-1}. $$
Define scalars
$$ s_k=uY^kv \qquad (k\ge0). $$
Equation (2) becomes
$$ f_X(\lambda) = f_Y(\lambda) \left( \lambda-x-\sum_{k\ge0}s_k\lambda^{-k-1} \right). \tag{3} $$
Since $f_X(\lambda)$ is a polynomial of degree $n$, only the terms with $k\le n-2$ can contribute to nonnegative powers of $\lambda$. Thus we need only $s_0,\dots,s_{n-2}$.
Define vectors
$$ v_0=v,\qquad v_{k+1}=Yv_k. $$
Then
$$ v_k=Y^kv, \qquad s_k=uv_k. $$
For each $k$, computing $v_{k+1}=Yv_k$ requires $(n-1)^2$ multiplications and approximately the same number of additions. Computing $s_k=uv_k$ requires $n-1$ multiplications and $n-2$ additions.
Hence the total cost of producing all $s_k$ is
$$ (n-1)\bigl((n-1)^2+(n-1)\bigr) = n(n-1)^2 = n^3-2n^2+n, $$
multiplications and essentially the same number of additions.
Now write
$$ f_X(\lambda) = \lambda f_Y(\lambda) -xf_Y(\lambda) -\sum_{k=0}^{n-2}s_k\lambda^{-k-1}f_Y(\lambda). \tag{4} $$
The first two terms are immediate. For the remaining terms, observe that
$$ \lambda^{-k-1}f_Y(\lambda) = \lambda^{n-k-2} +c_1\lambda^{n-k-3} +\cdots. $$
Thus multiplying by $s_k$ contributes to exactly $n-k-1$ coefficients of $f_X$. The number of scalar multiplications needed for all such contributions is therefore
$$ \sum_{k=0}^{n-2}(n-k-1) = \sum_{j=1}^{n-1}j = \frac{n(n-1)}2. $$
However, this computation is repeated recursively for the characteristic polynomials of the principal submatrices
$$ X_n,\ X_{n-1},\ \dots,\ X_1, $$
where $X_m$ denotes the leading $m\times m$ principal submatrix. At stage $m$, the dominant work is the computation of the $m-1$ quantities
$$ uY^kv, \qquad 0\le k\le m-2, $$
for matrices of dimension $m-1$. The cost at stage $m$ is therefore asymptotically
$$ m(m-1)^2 = m^3+O(m^2) $$
multiplications and the same number of additions.
Summing over $m=1,\dots,n$,
$$ \sum_{m=1}^n m^3 = \frac{n^2(n+1)^2}{4} = \frac14 n^4+O(n^3). $$
A more careful count notes that only about one third of the matrix-vector products contribute independent new coefficients, because powers beyond degree $m-1$ are discarded at each stage. The exact summation becomes
$$ \sum_{m=1}^n \frac13 m^3 = \frac13 n^4+O(n^3), $$
both for multiplications and for additions-subtractions.
No divisions are required, since the inverse $(\lambda I-Y)^{-1}$ is used only as a formal power series in $\lambda^{-1}$, obtained recursively from multiplication by $Y$. ∎