In the book "Computational Complexity of Counting and Sampling" I have found the following theorem:
It gives a recursion formula for a division-free algorithm for the determinant in $O(n^4)$. Now, we have the feeling that each trace $\mathrm{tr}(w(\cdot,\cdot,k))$ yields the $k$-th homogeneous coefficient of the characteristic polynomial. Examples up to 5 confirm this conjecture. Though, a proof is missing still.
I already tried various things. It would be good if one can show that $\mathrm{tr}(w(\cdot,\cdot,k))$ is invariant under change of basis of $M$. Then one can consider w.l.o.g. diagonal matrices. For these matrices, the proof is easy. However, an induction seems not helpful here. Moreover, when one iteratively insert the recursion, the expressions quickly get complicated.
I don't need the full proof here. A hint/direction or useful identity is already appreciated.
Here is a partial result. Denote by $c_k$ by the $k$-th homogeneous coefficient of the characteristic polynomial. Then :
$$ c_k=\sum_{i_1\lt \ldots \lt i_r, \sigma\in S(i_1,i_2,\ldots i_r)} (-1)\epsilon(\sigma) m_{i_1\sigma(i_1)}m_{i_2\sigma(i_2)}\ldots m_{i_r\sigma(i_r)} \tag{1} $$
where $\varepsilon$ denotes the signature of a permutation. Denote by $M_{\sigma}$ the $m_{i_1\sigma(i_1)}m_{i_2\sigma(i_2)}\ldots m_{i_r\sigma(i_r)}$ monomial in (1) above. I can then state :
Theorem. The terms $T_k=\sum_{i=1}^n w(i,i,k)$ and $c_k$ share the same coefficient at $M_{\sigma}$. In other words, $T_k$ can be decomposed as $c_k$ plus some other monomials, not of the form $M_{\sigma}$.
Proof : Suppose we wish to contruct a derivation showing that (some nonzero multiple, in fact it's a sign multiple of) $M_{\sigma}$ appears in $w^{k}(i,i)$. We use (3.10), which I find more convenient to rewrite as follows :
$$ w(i,i,k)=\sum_{x \lt i}w(x,x,k-1)m_{ij}-\sum_{y\gt i}w(i,y,k-1)m_{y,i} \tag{2} $$
The first step we need to make is to decide if we wish $M_{\sigma}$ to appear in the $\sum_{x \lt i}w(x,x,k-1)m_{ij}$, "left" half, or the $-\sum_{y\gt i}w(i,y,k-1)m_{y,i}$, "right" half.
And in fact, the complete procedure consists in making that decision $k$ times, in a way consistent with the rules (at this point it is not at all clear whether this is always possible).
Now, consider this truism : any path we choose will necessarily start by making the "right" choice zero or more times, followed by one "left" choice and some zero or more choices (the case where no "left" choice is made is similar and simpler). If we denote the number of those initial "right" choices by $r$, we see that $M_{\sigma}$ appears as a term in
$$ (-1)^r\sum_{x \lt i}w(x,x,k-(r+1))m_{i,y_r}m_{y_r,y_{r-1}} \ldots m_{y_2,y_1}m_{y_1,i} \tag{3} $$
where, because of the constraints in the recursion, all the $y_j$'s are $>i$. Then, (3) shows that $(i,y_1,y_2,\ldots,y_r)$ is a cycle appearing in the cycle decomposition on $\sigma$, and furthermore that $i$ is the smallest index in this cycle.
But then it is clear by induction on the number of cycles in $\sigma$ that $i$ must be the largest index among all the mins of cycles in $\sigma$ ; and that this uniquely defines any candidate for a derivation of $M_{\sigma}$ : we must necessarily follow the cycle decomposition of $\sigma$, in the order imposed by the mins in the cycles.
Conversely, it is immediate to check that this particular uniquely defined procedure does produce a multiple of $M_{\sigma}$, and in fact the multiplication coefficient is exactly what we want, $\varepsilon(\sigma)$ (because of the $(-1)^r$ coefficient in (3)). This finishes the proof.
It is likely I think that a similar argument can be made for the other monomials appearing in the $w()$ terms, although the computations will be slightly more complicated because while the $M_{\sigma}$'s appear in exactly one place, the other monomials appear in several different places and we have to show that they cancel out. I didn't have the time so far to check that it works.