# Expressing adj(A) as a polynomial in A?

Suppose $A\in R^{n\times n}$, where $R$ is a commutative ring. Let $p_i \in R$ be the coefficients of the characteristic polynomial of $A$: $\mathop{\mathrm{det}}(A-xI) = p_0 + p_1x + \dots + p_n x^n$.

I am looking for a proof that: $-\mathop{\mathrm{adj}}(A) = p_1 I + p_2 A + \dots + p_n A^{n-1}$.
In the case where $\mathop{\mathrm{det}}(A)$ is a unit, $A$ is invertible, and the proof follows from the Cayley-Hamilton theorem. But what about the case where $A$ is not invertible?

-
This is a polynomial identity in n^2 variables A_{ij} with integer coefficients, so it holds over any commutative ring R if and only if it holds over a dense subset of C, so the invertible case is already enough. –  Qiaochu Yuan Jul 16 '10 at 8:47
In my humble opinion Qiaochu Yuan's answer is more convincing than Martin's. All you need to know (I think) is that $\mathbb Z[X_1,...,X_k]$ is a domain. I don't think things like the existence of algebraic closure, the density of diagonal matrices, Zariski's topology, ..., are necessary (or even helpful) in this context. I don't even think Qiaochu Yuan had to invoke complex numbers. I believe the statement is truly elementary, and can be (easily) proved by considering only countable sets. –  Pierre-Yves Gaillard Jul 16 '10 at 11:40
Pierre-Yves, I agree! See mathoverflow.net/questions/29271/…, where this was discussed $\textit{ad nausem}$ and Martin finally made a concession that it's not the most natural approach, but it's awesome (to him). –  Victor Protsak Jul 17 '10 at 5:46
@Qiaochu: How can your intuition be "model theoretic" (I assume it means "true over an arbitrary commutative ring") and be "about diagonalizable matrices and their eigenvalues" (which makes sense only when the ground ring is a field) $\textit{at the same time}?$ For matrix identities (and polynomial identities more generally), the right kind of intuition does $\textit{not}$ come from eigenvalues or complex numbers. See Bill's remark at the end of his answer and my comment. –  Victor Protsak Jul 18 '10 at 9:04
What I meant is that there are these results of the form "if a first-order sentence is true in X, it must also be true in Y, Z, W...." and my intuition about proving a polynomial identity (with coefficients in Z) by proving it for C^n is that it is a statement of this sort. Maybe this is not a good way to think about things; in any case I appreciate the clarification. –  Qiaochu Yuan Jul 18 '10 at 16:24

Here is a direct proof along the lines of the standard proof of the Cayley–Hamilton theorem. [This works universally, i.e. over the commutative ring $R=\mathbb{Z}[a_{ij}]$ generated by the entries of a generic matrix $A$.]

The following lemma combining Abel's summation and Bezout's polynomial remainder theorem is immediate.

Lemma Let $A(\lambda)$ and $B(\lambda)$ be matrix polynomials over a (noncommutative) ring $S.$ Then $A(\lambda)B(\lambda)-A(0)B(0)=\lambda q(\lambda)$ for a polynomial $q(\lambda)\in S[\lambda]$ that can be expressed as

$$q(\lambda)=A(\lambda)\frac{B(\lambda)-B(0)}{\lambda}+\frac{A(\lambda)-A(0)}{\lambda}B(0)=A(\lambda)b(\lambda)+a(\lambda)B(0) \qquad (*)$$

with $a(\lambda),b(\lambda)\in S[\lambda].$

Let $A(\lambda)=A-\lambda I_n$ and $B(\lambda)=\operatorname{adj} A(\lambda)$ [viewed as elements of $S[\lambda]$ with $S=M_n(R)$], then

$$A(\lambda)B(\lambda)=\det A(\lambda)=p_A(\lambda)=p_0+p_1\lambda+\ldots+p_n\lambda^n$$ is the characteristic polynomial of $A$ and $$A(0)B(0)=p_0 \text{ and } q(\lambda)=p_1+\ldots+p_n\lambda^{n-1}$$

Applying $(*),$ we get

$$q(\lambda)=(A-\lambda I)b(\lambda)-\operatorname{adj} A \qquad (**)$$

for some matrix polynomial $b(\lambda)$ commuting with $A.$ Specializing $\lambda$ to $A$ in $(**),$ we conclude that

$$q(A)=-\operatorname{adj} A\qquad \square$$

-
Looks like "hints" are more popular than full proofs. Why bother doing mathematics honestly if you can blog and handwave? –  Victor Protsak Jul 18 '10 at 8:12
Dear Victor, one of your lines is too long for my browser, which makes your answer almost unreadable. I was wondering if you couldn't break this line. –  Pierre-Yves Gaillard Jul 18 '10 at 8:22
Dear Pierre-Yves: Thank you for letting me know. I have shortened the display (*) and broken several other lines by displaying the formulas. If you continue to experience difficulties, please, state specifically which lines cause them. –  Victor Protsak Jul 18 '10 at 8:56
Dear Victor: It's much better! But Line (*) is still a tiny bit too long for my browser. If I were you, I'd break it just before the second equal sign. (But it's a detail.) Thank you very much! –  Pierre-Yves Gaillard Jul 18 '10 at 9:37
It's perfect now!!! –  Pierre-Yves Gaillard Jul 18 '10 at 10:54

HINT $\;$ Work "generically", i.e. let the entries $\;\rm a_{i,j}$ of $\rm A\;$ be indeterminates and work in the matrix ring $\rm M = M_n(R)\;$ over $\;\rm R = {\mathbb Z}[a_{i,j}\:]. \;$ We wish to prove $\rm B = C$ from $\rm d\: B = d\: C$ for $\rm d = det\: A \in R, \;\; B,C \in M.$ But this is equivalent to $\rm d\: b_{i,j} = d\: c_{i,j}$ in the domain $\rm R = {\mathbb Z}[a_{i,j}\:]$ where $\;\rm d = det\: A \ne 0$, so $\rm d$ is cancelable, yielding $\;\rm b_{i,j} = c_{i,j}\;$ hence $\rm B = C$. This identity remains true over every commutative ring $\rm S$ since, by the universality of polynomial rings, there exists an eval homomorphism that evaluates $\;\rm a_{i,j}\;$ at any $\;\rm s_{i,j}\in S$.

Notice that the crucial insight is that $\;\rm b_{i,j}\:, \; c_{i,j}\:,\; d\;$ have polynomial form in $\;\rm a_{i,j}\:$, i.e. they are elts of the polynomial ring $\;\rm R = {\mathbb Z}[a_{i,j}\:] = {\mathbb Z}[a_{1,1},\cdots,a_{n,n}\:]$ which, being a domain, enjoys cancelation of elts $\ne 0$. Working generically allows us to cancel $\rm d$ and deduce the identity before any evaluation where $\rm d\mapsto 0.$

Such proofs by way of universal polynomial identities emphasize the power of the abstraction of a formal polynomial (vs. polynomial function). Alas, many algebra textbooks fail to explicitly emphasize this universal viewpoint. As a result, many students cannot easily resist the obvious topological temptations and instead derive hairier proofs employing density arguments (e.g see elswhere in this thread).

Analogously, the same generic method of proof works for many other polynomial identities, e.g.

$\rm\quad\; det(I-AB) = det(I-BA)\;\:$ by taking $\;\rm det\;$ of $\;\;\rm (I-AB)\;A = A\;(I-BA)\;$ then canceling $\;\rm det \:A$

$\rm\quad\quad det(adj \:A) = (det \:A)^{n-1}\quad$ by taking $\;\rm det\;$ of $\;\rm\quad A\;(adj\: A) = (det\: A) \;I\quad\;\;$ then canceling $\;\rm det \:A$

Now, for our pièce de résistance of topology, we derive the polynomial derivative purely formally.

For $\rm f(x) \in R[x]$ define $\rm D f(x) = f_0(x,x)$ where $\rm f_0(x,y) = \frac{f(x)-f(y)}{x-y}.$ Note that the existence and uniqueness of this derivative follows from the Factor Theorem, i.e. $\;\rm x-y \; | \; f(x)-f(y)\;$ in $\;\rm R[x,y],\;$ and, from the cancelation law $\;\rm (x-y) g = (x-y) h \implies g = h$ for $\rm g,h \in R[x,y].$ It's clear this agrees on polynomials with the analytic derivative definition since it is linear and it takes the same value on the basis monomials $\rm x^n$. Resisting limits again, we get the product rule rule for derivatives from the trivial difference product rule

$$\rm f(x)g(x) - f(y)g(y)\; = \;(f(x)-f(y)) g(x) + f(y) (g(x)-g(y))$$

$\quad\quad\quad\quad\rm\quad\quad\quad \Longrightarrow \quad\quad\quad\quad\quad\; D(fg)\quad = \quad (Df) \; g \; + \; f \; (Dg)$

by canceling $\rm x-y$ in the first equation, then evaluating at $\rm y = x$, i.e. specialize the difference "quotient" from the product rule for differences. Here the formal cancelation of the factor $\;\rm x-y\;$ before evaluation at $\;\rm y = x\;$ is precisely analogous to the formal cancelation of $\;\rm det \:A\;$ in all of the examples given above.

-
Yes, this is probably what Quiaochu had in mind. A couple of points: (1) There is some work left in showing that Cayley-Hamilton holds universally, which some books fail to emphasize (hence many people are unaware how to prove it, in line with your last comment); and (2) The usual proof of CH relies on factorization $\det(A-\lambda)=(A-\lambda)\operatorname{adj}(A-\lambda)$ and this is needed again in the "black box" proof you've presented in the form $\det A=A\operatorname{adj} A$ (hence after unwinding the argument, it ends up being applied twice). That's why I prefer a direct argument. –  Victor Protsak Jul 18 '10 at 8:30
@Victor: but Quiaochu's hint employs a density argument, not polynomial universality - which is the essence of the matter in my approach. Yes, I presume Cayley-Hamilton for commutative rings but this is so widely known it is even in Wikipedia, besides Jacobson BA1, etc. (not to mention Nakayama inspired generalizations, e.g. Atiyah & Macdonald) –  Bill Dubuque Jul 18 '10 at 15:16
"Density argument" is ambiguous: I interpreted "the invertible case is already enough" in the first comment as "$\{A:\det A\ne 0\}$ is a Zariski dense subset of the affine space of $n\times n$ matrices" (over $C$, as it were), which is exactly your "working generically allows us to cancel $d$". As you can see, I am not happy with handwaving in such matters: I often found that it masks incomplete understanding (cf the link I gave above to discussion of what constitutes a proof of CH itself). This is typically manifested in starting an answer with "Hint" :) –  Victor Protsak Jul 18 '10 at 16:04
Here is a question that you might answer. As you say, CH is widely known, but what about the OP's identity? I have a feeling that this is something that once upon a time was equally standard (early 20th century, when Kronecker-Weierstrass-Frobenius methods were widely employed), but I can't remember seeing it stated explicitly in any recent texts. Do you know the history of this identity? When did this transition from "polynomial universality" to "eigenvalues and density" approach (also evident in the current treatment of Jordan normal form without developing elementary divisors) occur? –  Victor Protsak Jul 18 '10 at 16:12
@Victor: to ensure there is no confusion, I remark that my use of "generic" above is not intended to denote anything topological or geometrical. Rather, it is meant to be understood as exploiting the universality of a free objects. The proof I gave does not require any knowledge of topology or (algebraic) geometry. I'm not saying that imposing other such viewpoints isn't interesting or useful - just that such is not required for problems of this sort. Further doing so adds complexity to what is - at the heart - trivial (yet elegant) algebra. –  Bill Dubuque Jul 18 '10 at 22:36

I guess it is worth giving a fuller answer, and then Victor can tell me more precisely where I am missing some subtlety. As I said, the definition I know of the adjugate is that it is a matrix whose entries are polynomials in the entries $a_{ij}$ of $A$ and which satisfies $A \text{ adj}(A) = I \det A$ identically, e.g. over $\mathbb{Z}[a_{ij}]$. Assuming Cayley-Hamilton, we know that $p_0 I + p_1 A + ... + p_n A^n = 0$ identically and that $p_0 = \det A$, where $p_k \in \mathbb{Z}[a_{ij}]$ as well.

Specializing now to $a_{ij} \in \mathbb{C}$ and supposing that $A$ is invertible, we conclude that

$$A \text{ adj}(A) = - p_1 A - p_2 A^2 - ... - p_n A^n$$

implies

$$\text{adj}(A) = - p_1 I - p_2 A - ... - p_n A^{n-1},$$

as you say.

Lemma: The invertible $n \times n$ matrices are dense in the $n \times n$ matrices with the operator norm topology.

Proof. Let $A$ be a non-invertible $n \times n$ matrix, hence $\det A = 0$. The polynomial $\det(A - xI)$ has leading term $(-1)^n x^n$, hence cannot be identically zero, so in any neighborhood of $A$ there exists $x$ such that $A - xI$ is invertible.

But everything in sight is continuous in the operator norm topology, so the conclusion follows identically over $\mathbb{C}$ and hence identically.

(I should mention that this is not even my preferred method of proving matrix identities. Whenever possible, I try to prove them combinatorially by interpreting $A$ as the adjacency matrix of some graph. For example - confession time! - this is how I think about Cayley-Hamilton. This is far from the cleanest or the shortest way to do things, but my combinatorial intuition is better than my algebraic intuition and I think it's good to have as many different proofs of the basics as possible.)

-
Sure, this is a nice proof. Depending upon taste, one might want to replace the "analytic" topology with the Zariski topology. The merit of this is that the Zariski density of the invertible matrices is even easier to establish: because $\mathbb{C}[x_1,\ldots,x_{n^2}]$ is a domain, its spectrum is an irreducible topological space, so every nonempty open subset -- like the set of all matrices with nonzero determinant -- is Z-dense. –  Pete L. Clark Jul 18 '10 at 19:11
Qiaochu: Multiply your first displayed line by $\text{adj}(A),$ get $$\det A\ \text{adj}(A) = \det A(- p_1 I - p_2 A - \ldots - p_n A^{n-1})$$ and universally cancel $\det A$ per Bill's answer. The rest (specialization and density) is crud. –  Victor Protsak Jul 19 '10 at 0:14
As in it doesn't work or as in you don't like it? In any case, maybe I should present this style of argument not as "the proof," but as a way to check such results. Many matrix identities are easier to verify for A with a special form, and I think it's good to know that there exist theorems saying that this is enough. Whether one chooses to use them is a matter of taste, I think. –  Qiaochu Yuan Jul 19 '10 at 0:39
@Q The equation in Victor's comment is indeed the equation that I started with, viz. $\rm d B = d C$ for $\rm d = det A$. –  Bill Dubuque Jul 19 '10 at 1:38
Also, I forgot to mention: there is a natural (i.e. not relying on tricks and special cases) enumerative combinatorics proof of CH in Stanton-White's book. –  Victor Protsak Jul 19 '10 at 2:38

As an arithmetic geometer, I have no choice but to use topological methods hand in hand with algebraic methods. Very likely necessity has been the mother of aesthetics here, but I find proofs of linear algebra facts using genericity arguments to be beautiful and insightful.

Qiaochu has shown how to answer the OP's question using these methods [he uses the "analytic" -- i.e., usual -- topology on $\mathbb{C}^n$, but close enough] assuming the Cayley-Hamilton theorem. Here I want to show that one can also prove the Cayley-Hamilton theorem quickly by these methods.

Step 1: To prove C-H as a polynomial identity, it is enough to prove that it holds for all $n \times n$ matrices over $\mathbb{C}$.

Proof: Indeed, to say C-H holds as a polynomial identity means that it holds for the generic matrix $A = \{a_{ij}\}_{1 \leq i,j \leq n}$ whose entries are independent indeterminates over the ring $R = \mathbb{Z}[a_{ij}]$. But this ring embeds into $\mathbb{C}$ -- indeed into any field of characteristic zero and infinite absolute transcendence degree -- and two polynomials with coefficients in a domain $R$ are equal iff they are equal in some extension domain $S$.

Step 2: C-H is easy to prove for complex matrices $A$ with $n$ distinct eigenvalues $\lambda_1,\ldots,\lambda_n$.

Proof: The characteristic polynomial evaluated at $A$ is $P(A) = \prod_{i=1}^n(A-\lambda_i I_n)$. Let $e_1,\ldots,e_n$ be a basis of $\mathbb{C}^n$ such that each $e_i$ is an eigenvector for $A$ with eigenvalue $\lambda_i$. Then -- using the fact that the matrices $A - \lambda_i I_n$ all commute with each other -- we have that for all $e_i$,

$P(A)e_i = \left(\prod_{j \neq i} (A-\lambda_j I_n)\right) (A-\lambda_i I_n) e_i = 0.$

Since $P(A)$ kills each basis element, it is in fact identically zero.

Step 3: The set of complex matrices with $n$ distinct eigenvalues is a Zariski-open subset of $\mathbb{C}^n$: indeed this is the locus of nonvanishing of the discriminant of the characteristic polynomial. Since we can write down diagonal matrices with distinct entries, it is certainly nonempty. Therefore it is Zariski dense, and any polynomial identity which holds on a Zariski dense subset of $\mathbb{C}^{n^2}$ holds on all of $\mathbb{C}^{n^2}$.

-
Right. To expand on my answer, let me tell you how I prove C-H when nobody's looking. First we consider the special case when A is the adjacency matrix of the graph on {1, 2, ... n} with one edge from n to n-1 to... to 1 and c_k edges from 1 to k. The entries in powers of A count walks on this graph, which count tilings of a line where there are c_k types of tiles of size k (subject to some conditions depending on where the walk starts and ends). There is a bijective proof that A^n = c_1 A^{n-1} + c_2 A^{n-2} ... : the bijection is "delete the first tile"... –  Qiaochu Yuan Jul 18 '10 at 20:24
(cont.) which means, look at the first place the walk visits its starting vertex again, and delete that loop. On the other hand, it's not hard to show that x^n - c_1 x^{n-1} - ... is the characteristic polynomial of A. This proves C-H for all companion matrices (the combinatorial argument is "weighted," e.g. the c_k are variables) over C, hence for all diagonalizable matrices with distinct eigenvalues by conjugation, and hence for all matrices by whichever density argument you prefer. –  Qiaochu Yuan Jul 18 '10 at 20:25
Pete, so if I understand you correctly, you prefer Weil-van der Waerden style "generic point" (over a universal field) to the Grothendieck generic point (i.e. zero ideal of $R$)? There are good reasons to prove identities such as CH directly, the comparative ease being one, but let me mention another: the usual proof $$p_A(\lambda)=(A-\lambda)\operatorname{adj}(A-\lambda), \lambda\to A\implies p_A(A)=0\ \square$$ immediately leads to a proof Nakayama's lemma, whereas I see only (technical) pain and no (conceptual) gain in "reducing" it to tricks with geometric points based on eigenvalues. –  Victor Protsak Jul 18 '10 at 23:52
@VP, No, I'm not expressing any kind of systematic preference. This is just a proof that I like and find easy to remember -- no disparagement of other approaches is intended or felt. One point: in principle Zariski-density arguments are more general than genericity arguments. For instance, I believe that over any field $k$, the set of matrices which have distinct, $k$-rational eigenvalues is Zariski-dense, but the generic matrix does not have eigenvalues rational over its fraction field. However, proving this seems harder than reducing to the case of an alebraically closed field... –  Pete L. Clark Jul 19 '10 at 0:16
...over any INFINITE field, I should have said. –  Pete L. Clark Jul 19 '10 at 2:49

EDIT OF AUG. 31, 2010. The proof of the Cayley-Hamilton Theorem I like best (among the ones I know) is on page 21 (proof of Proposition 2.4) of Introduction to Commutative Algebra by Atiyah and MacDonald. The argument can be phrased as follows.

Let $K$ be a commutative ring; let $n$ be a positive integer; let $A=(a_{ij})\in M_n(K)$ be an $n$ by $n$ matrix with entries in $K$; let $\chi$ be its characteristic polynomial; define $B=(b_{ij})\in M_n(K[A])$ by $b_{ij}:=\delta_{ij}\\,A-a_{ij}$; let $(e_i)$ be the canonical basis of $K^n$; observe $$\sum_i\\ \\ b_{ij}\\ e_i=0,\quad\det B=\chi(A);$$ and write $(c_{ij})$ for the adjugate of $B$. Applying (a trivial case of) Fubini's Theorem to the double sum $\sum_{i,j}\\ c_{jk}\\ b_{ij}\\ e_i$, we get $\chi(A)=0$.

Thank you very much to darij grinberg! [I'm leaving the previous edits "for the record".] END OF EDIT OF AUG. 31, 2010.

EDIT OF DEC. 11, 2010. For a nice application of the Cayley-Hamilton Theorem, see this answer by Balazs Strenner.

PREVIOUS EDITS:

Here is a proof of the Cayley-Hamilton Theorem.

Let $K$ be a commutative ring, let $n$ be a positive integer, let $X$ be an indeterminate, let $A\in M_n(K)$ be an $n$ by $n$ matrix with coefficients in $K$, and let $\chi:=\det(X-A)$ be the characteristic polynomial. Equip $K^n$ with the $K[X]$-module structure induced by $A$. We must check $\chi K^n=0$. Form the right $M_n(K[X])$-module $$H:=\mathrm{Hom}_{K[X]}(K[X]^n,K^n).$$ Let $e\in H$ be the evaluation at $A$ (note $K[X]^n=K^n[X]$). As $e$ is surjective, it suffices to show $e\chi=0$. As $X-A$ divides $\chi$ on the left, it suffices to show $e(X-A)=0$. But this is obvious.

EDIT OF AUG. 1, 2010. Here is a diagrammatic rewriting of the argument.

EDIT OF AUG. 30, 2010. Here is a coordinate version of the above argument. [Compare with the proof of Propositon 3 page 81 of Weil's Basic Number Theory, and with the proof of Propositon 2.4 page 21 of Introduction to Commutative Algebra by Atiyah and MacDonald].

Weil's formulation. Put $$B(X)=(b_{ij}(X)):=X-A\in M_n(K[X]),$$ and let $C(X)=(c_{ij}(X))$ be the adjugate of $B(X)$. We have $$\sum_j\ c_{jk}(X)\ b_{ij}(X)=\delta_{ik}\ \chi(X)\in K[X].$$ Replacing $X$ with $A$, evaluating on $e_i$ (the $i$-th vector of the canonical basis of $K^n$), and summing over $i$ gives $$\sum_j\ c_{jk}(A)\ \sum_i\ b_{ij}(A)\ e_i=\chi(A)\ e_k\in K^n.$$ But the second sum is 0 by definition of $b_{ij}(X)$.

Atiyah-MacDonald's formulation. Put $A=(a_{ij})$ and define $B=(b_{ij})\in M_n(K[A])$ by $b_{ij}:=\delta_{ij}A-a_{ij}$; observe $$\sum_i\\ b_{ij}\\ e_i=0,\quad\det B=\chi(A);$$ and write $(c_{ij})$ for the adjugate of $B$. Computing $\sum_{i,j}\\,c_{jk}\\,b_{ij}\\,e_i$ in two ways we get $\chi(A)=0$.

-
Why is your $e$ in $H$? –  darij grinberg Jul 20 '10 at 9:58
Dear darij grinberg: Because it maps $K[X]^n$ to $K^n$ and is $K[X]$-linear. –  Pierre-Yves Gaillard Jul 20 '10 at 10:09
Why does it map $K[X]^n$ to $K^n$ ? Shouldn't it map $K[X]^n$ to $\left(\mathrm M_n\left(K\right)\right)^n$ ? –  darij grinberg Jul 20 '10 at 10:09
Dear darij grinberg: It maps $X^i v$ in $K[X]^n=K^n[X]$ to $A^i v$ in $K^n$. (Here $v$ is in $K^n$.) –  Pierre-Yves Gaillard Jul 20 '10 at 10:15
Ah, so that' what you mean by evaluation at $A$! –  darij grinberg Jul 20 '10 at 10:17

This formula can be obtained during a proof of the Cayley-Hamilton theorem, as is indicated on its Wikipedia article. The essence of the argument is that Euclidean division by a monic polynomial (on the left, say), can be performed in the polynomial ring over any (unitary) ring, not necessarily commutative; this follows directly from consideration of what Euclidean division does, or by a simple inductive argument.

Since I care about polynomials being monic, I'l define the characteristic polynomial of a matrix $A$ to be $\chi_A=\det(I_nX-A)=\sum_{i=0}^nc_iX^i$ where $c_n=1$ (and $c_0=\det(-A)$), so the result to prove becomes $\mathrm{adj}(-A)=c_1I_n+c_2A+\cdots+c_{n-1}A^{n-2}+A^{n-1}=\sum_{i=1}^nc_iA^{i-1}$

Consider the noncommutative ring $M=\mathrm{Mat}_n(R)$, and using Euclidean division in $M[X]$ (in which $R[X]$ is embedded by mapping $r$ to $rI_n$) divide $\chi_A$ on the left by $X-A$. Since we know that $(X-A)\mathrm{adj}(X-A)=\det(X-A)=\chi_A$, uniqueness of quotient and remainder in Euclidean division implies they will have to be $\mathrm{adj}(X-A)$ and $0$, respectively. Writing the quotient $\mathrm{adj}(X-A)=\sum_{i=0}^{n-1}B_iX^i$, its coefficients $B_i\in M$ are determined in the division successively as $B_{n-1}=c_n=1$ and $B_{i-1}=c_i+AB_i$ for $i=n-1,\ldots,1$ (these are just the intermediate values while computing the evaluation of $\chi_A$ at$~X=A$ using the Horner scheme), which expands to $B_{i-1}=c_iA^0+c_{i+1}A^1+\cdots+c_nA^{n-i}$. In particular the constant coefficient of the quotient $\mathrm{adj}(X-A)$ equals $B_0=\sum_{i=1}^nc_iA^{i-1}$, but this is also $\mathrm{adj}(-A)$ (by substituting $X=0$).

To retrieve the Cayley-Hamilton theorem from the formula found, multiply on the left or right by $A$ and move the left hand side to the right.

-
Having written half of that article, I may be biased, but I didn't write this part and I always liked that argument. –  Ryan Reich Nov 7 '11 at 14:50
Thank you. Indeed I did contribute that part (and another half;-) to that article, in 2008. I should say that this argument is quite close to the proof by Victor Protsak, the main difference being mention of Euclidean division: to me the right hand side just begs to be interpreted as a coefficient of a Euclidean quotient by $X-A$ (more generally Horner-scheme sub-expressions do). By the way, the Cayley-Hamilton theorem can be obtained more directly here by interpreting the fact that the remainder is 0. –  Marc van Leeuwen Nov 8 '11 at 10:35