Post History

# CJam, 45 bytes

<!-- language-all: lang-cjam -->

    {:A_,{1$_,,.=:+\)/:CAff*A@zf{\f.*::+}..-}/;C}

This implementation is an anonymous block (~function). [Online test suite](http://cjam.aditsu.net/#code=%7B%3AA_%2C%7B1%24_%2C%2C.%3D%3A%2B%5C\)%2F%3ACAff*A%40zf%7B%5Cf.*%3A%3A%2B%7D..-%7D%2F%3BC%7D%0A%0A%3AD%3B%0A%5B%5B1%200%5D%5B0%201%5D%5D%20Dp%0A%5B%5B1.5%202%5D%5B-3%204.5%5D%5D%20Dp%0A%5B%5B3%207%5D%5B1%20-4%5D%5D%20Dp%0A%5B%5B1%200%200%5D%5B0%201%200%5D%5B0%200%201%5D%5D%20Dp%0A%5B%5B1%202%203%5D%5B4%205%206%5D%5B7%208%209%5D%5D%20Dp).

### Dissection
This implements the [Faddeev-LeVerrier algorithm](https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm).

The objective is to calculate the coefficients \$c_k\$ of the characteristic polynomial of the \$n\times n\$ matrix \$A\$, $$\begin{eqnarray}p(\lambda)\equiv \det(\lambda I_{n}-A) = \sum_{k=0}^{n}c_{k}\lambda^{k}\end{eqnarray}$$ where, evidently, \$c_n = 1\$ and \$c_0 = (-1)^n \det A\$.

The coefficients are determined recursively from the top down, by dint of the auxiliary matrices \$M\$, $$\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}$$

The code never works directly with \$c_{n-k}\$ and \$M_k\$, but always with \$(-1)^k c_{n-k}\$ and \$(-1)^{k+1}AM_k\$, so the recurrence is $$(-1)^k c_{n-k} = \frac1k \mathrm{tr} ((-1)^{k+1} AM_{k}) \\ (-1)^{k+2} AM_{k+1} = (-1)^k c_{n-k}A - A((-1)^{k+1}A M_k)$$

    {               e# Define a block
      :A            e#   Store the input matrix in A
      _,            e#   Take the length of a copy
      {             e#     for i = 0 to n-1
                    e#       Stack: (-1)^{i+2}AM_{i+1} i
        1$_,,.=:+   e#       Calculate tr((-1)^{i+2}AM_{i+1})
        \)/:C       e#       Divide by (i+1) and store in C
        Aff*        e#       Multiply by A
        A@          e#       Push a copy of A, bring (-1)^{i+2}AM_{i+1} to the top
        zf{\f.*::+} e#       Matrix multiplication
        ..-         e#       Matrix subtraction
      }/
      ;             e#   Pop (-1)^{n+2}AM_{n+1} (which incidentally is 0)
      C             e#   Fetch the last stored value of C
    }