# [Maxima] charpoly very, very slow

andre maute andre.maute at gmx.de
Fri May 23 12:06:18 CDT 2008

```On Friday 23 May 2008, Oliver Kullmann wrote:
> M;
> (%o6)
> matrix([0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4],[1,0,2,1,2,1,3,2,2,1,3,2,3,2,4,3],
> [1,2,0,1,2,3,1,2,2,3,1,2,3,4,2,3],[2,1,1,0,3,2,2,1,3,2,2,1,4,3,3,2],
> [1,2,2,3,0,1,1,2,2,3,3,4,1,2,2,3],[2,1,3,2,1,0,2,1,3,2,4,3,2,1,3,2],
> [2,3,1,2,1,2,0,1,3,4,2,3,2,3,1,2],[3,2,2,1,2,1,1,0,4,3,3,2,3,2,2,1],
> [1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3],[2,1,3,2,3,2,4,3,1,0,2,1,2,1,3,2],
> [2,3,1,2,3,4,2,3,1,2,0,1,2,3,1,2],[3,2,2,1,4,3,3,2,2,1,1,0,3,2,2,1],
> [2,3,3,4,1,2,2,3,1,2,2,3,0,1,1,2],[3,2,4,3,2,1,3,2,2,1,3,2,1,0,2,1],
> [3,4,2,3,2,3,1,2,2,3,1,2,1,2,0,1],[4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0])

> This runs now already for a day!
>
> Computing the characteristic polynomial is somewhat more expensive than
> Gaussian elimination, but not too much, and so I believe something is wrong
> here.

with GAP 4.4.8
--------------------------------------------------------
M := [
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4],
[1,0,2,1,2,1,3,2,2,1,3,2,3,2,4,3],
[1,2,0,1,2,3,1,2,2,3,1,2,3,4,2,3],
[2,1,1,0,3,2,2,1,3,2,2,1,4,3,3,2],
[1,2,2,3,0,1,1,2,2,3,3,4,1,2,2,3],
[2,1,3,2,1,0,2,1,3,2,4,3,2,1,3,2],
[2,3,1,2,1,2,0,1,3,4,2,3,2,3,1,2],
[3,2,2,1,2,1,1,0,4,3,3,2,3,2,2,1],
[1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3],
[2,1,3,2,3,2,4,3,1,0,2,1,2,1,3,2],
[2,3,1,2,3,4,2,3,1,2,0,1,2,3,1,2],
[3,2,2,1,4,3,3,2,2,1,1,0,3,2,2,1],
[2,3,3,4,1,2,2,3,1,2,2,3,0,1,1,2],
[3,2,4,3,2,1,3,2,2,1,3,2,1,0,2,1],
[3,4,2,3,2,3,1,2,2,3,1,2,1,2,0,1],
[4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0]
];

Print(CharacteristicPolynomial(M));
Print("\n");

QUIT;
--------------------------------------------------------
I get nearly instantly

x_1^16-640*x_1^14-10240*x_1^13-61440*x_1^12-131072*x_1^11

Andre
```