Cayley-Hamilton revisited Let $(A_i)_i$ be $n\times n$ matrices with entries in a field $K$ with characteristic $0$. We consider the equation (1) $f(X)=A_kX^k+\cdots+A_1X+A_0=0_n$ where $X\in\mathcal{M}_n(K)$ is unknown. Let $g = \det(\lambda^kA_k+\cdots+\lambda A_1+A_0)\in K[\lambda]$.
Question: is it true that, if $B$ is a solution of (1) ($f(B)=0_n$), then $g(B)=0$ ?
i) In 1884, Sylvester seemed to think that it is true, but, without proof (as often with him).
ii) This result is "proved" in: K. Kanwar. A generalization of the Cayley-Hamilton Theorem. Advances in PURE mathematics.2013. Yet, the proof is obviously false !! Recall that this journal has already been the subject of a scandal:
http://boingboing.net/2012/10/19/math-journal-accepts-computer.html 
So the problem seems not settled.
 A: To convince people that this is true, let me add a quick proof that works in the special case in which $B$ is diagonalizable with distinct eigenvalues. 
By changing bases, we can assume it is in fact diagonal and equal to $\operatorname{diag}(\lambda_1,\lambda_2,\dots,\lambda_n)$. We have $0=\sum A_i B^i e_j=\sum A_i\lambda_j^i e_j$ for the $j$-th vector of the canonical basis $e_j$. Hence for each $\lambda_j$ the matrix $\sum A_i \lambda_j^i$  is singular, so the $\lambda_j$ are all roots of $g(\lambda)=\det p(\lambda)$. In particular, this means that $g(B)=0$.
More care is necessary if $B$ has multiple eigenvalues and Jordan blocks, of course.
A: Yes, this is precisely Theorem 4 in Chapter VIII, $\S$5 of F. R. Gantmacher, The Theory of Matrices, Vol. 1. The proof seems to be essentially that in darij grinberg's answer.
A: Yes, this follows from known facts on matrix polynomials. There is a full characterization of spectral divisors of matrix polynomials in Gohberg, Lancaster, Rodman, Matrix Polynomials. They treat monic polynomials (i.e., $A_k=1$), but this is not a restriction, since one can make a Möbius transform to enforce it unless $g(\lambda)\equiv 0$.
They introduce so-called standard pairs of a matrix polynomial $A(\lambda)$, which are in some sense a generalization of the companion matrix. Then they prove (Thm 3.12) that if a polynomial $Q(\lambda)$ is a right divisor of $P(\lambda)$ then the standard pair of $Q$ is a restriction of that of $P$; translating it to companion matrices, it would mean that the companion matrix of $Q$ can be obtained as a restriction of that of $P$ to an invariant subspace.
We apply that to $\lambda I - B$ (for which the "companion matrix" is $B$ itself) and $P(\lambda)=\sum_{i=0}^k A_i \lambda^i$. In particular, this means that the Jordan structure of $B$ is a substructure of that of the companion matrix of $P(\lambda)$, hence the algebraic multiplicities of the eigenvalues of $B$ are less or equal than those of $P(\lambda)$, that is, the characteristic polynomial of $B$ is a divisor of your $g(\lambda)$.
Not sure how much of this is understandable -- I must admit that book has not the reputation for being an easy-to-read one in the community. A more self-contained approach to these topics is in: I. Gohberg, M.A. Kaashoek and P. Lancaster,
General theory of regular matrix polynomials and band Toeplitz operators.
A: Am I missing something or is Ilya Bogdanov's elimination of $A_0$ trick more or less a proof in itself?
Assume that $f\left(B\right) = 0_n$. Then, $0_n = f\left(B\right) = A_kB^k + A_{k-1}B^{k-1} + ... + A_0 = \sum\limits_{i=0}^k A_iB^i$. But
$\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0 = \sum\limits_{i=0}^k \lambda^i A_i = \sum\limits_{i=0}^k \lambda^i A_i - \sum\limits_{i=0}^k A_iB^i$ (since $0 = \sum\limits_{i=0}^k A_iB^i$)
$= \sum\limits_{i=0}^k A_i \left(\lambda^i-B^i\right)$.
This polynomial is divisible by $\lambda-B$ on the right (because $\lambda^i-B^i$ is divisible by $\lambda-B$ for every $i$). Hence,
$\det\left(\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0\right)$ is divisible by $\det\left(\lambda-B\right)$.
In other words, $g\left(\lambda\right)$ is divisible by $\det\left(\lambda-B\right)$ (since $\det\left(\lambda^k A_k + \lambda^{k-1}A_{k-1} + ... + A_0\right) = g\left(\lambda\right)$). Since $B$ is a root of the polynomial $\det\left(\lambda-B\right)$ (by the usual Cayley-Hamilton theorem), this yields that $B$ is a root of $g\left(\lambda\right)$, so that $g\left(B\right) = 0$, and we are done.
I agree with Yazdegerd III that the characteristic-$0$ assumption shouldn't be there. Even if my proof would use it, Ilya's observation that the result is a polynomial identity in the entries of $A_k$, $A_{k-1}$, ..., $A_1$ and $B$ should make it clear that it holds over any commutative ring.
A: Thanks for Federico for pointing out my stupid matlab typo :-) the counterexample below is false, so am deleting it.

I must be missing something or doing something silly, because I think it is false. Here is an explicit counterexample:
Let $k=2$. Let $A_2=I$, $A_1=\left(
\begin{array}{cc}
 -1 & -6 \\
 2 & -9
\end{array}
\right)$, and $A_0=\left(
\begin{array}{cc}
 0 & 12 \\
 -2 & 14
\end{array}
\right)$. Verify that
$B^2+A_1B+A_0=0$ for $B=\left(
\begin{array}{cc}
 1 & 0 \\
 0 & 2
\end{array}
\right)$.
Also, note that $\det(\lambda^2 I_2 + \lambda A_1+A_0) = 24-50 \lambda +35 \lambda ^2-10 \lambda ^3+\lambda ^4$. But,
\begin{equation*}
24-50B + 35B^2 -10B^3 + B^4 = \left(
\begin{array}{cc}
 0 & 24 \\
 24 & 0
\end{array}
\right).
\end{equation*}
A: Essentially darij grinberg's nice proof can be stated, without using cayley hamilton, and over any commutative ring K, briefly as follows: It suffices by the non commutative root factor theorem to show that f divides g from the right. But polynomials with matrix coefficients are isomorphic to matrices with polynomial entries, and the matrix corresponding to f does divide the matrix corresponding to g from the right (and from the left) by cramers rule. QED
