# Obtaining the discriminant of the characteristic polynomial directly from the matrix

Let $M \in \mathbb{Z}_{n \times n}$ be a square matrix with integer coefficients. Let $P(x)$ be its characteristic polynomial $$P(x) = \det\left(x \cdot \mathbb{I}_{n \times n}- M\right)$$ I would like to compute the discriminant of $P(x)$, and I am wondering if it can be obtained from $M$ directly.

The intent is to determine whether $M$ has distinct eigenvalues.

I am looking for references, ideas, algorithms. Thank you.

-
What do you mean by "directly"? Why don't you want to just compute $\gcd(P(x), P'(x))$? – Qiaochu Yuan Sep 7 '12 at 16:41
@QiaochuYuan Getting characteristic polynomial from a matrix is costly. I am trying to avoid computing the polynomial, and see if it is possible to find the discriminant by means of linear algebra operations on matrix $M$. Sorry for not being clear. – Sasha Sep 7 '12 at 16:48
Is it? What goes wrong when you row reduce $xI - M$ over $\mathbb{Q}(x)$? – Qiaochu Yuan Sep 7 '12 at 18:09
Computing characteristic polynomial $P(x)$ and $\gcd(P(x),P^\prime(x))$ has its computation cost, and can be merrily done just like you describe. It may well be the most efficient algorithm, but I am asking if it can also be done another way, say as a determinant of some matrix, constructed from $M$. My hope is that it may lead to a faster algorithm, but I am not certain. Besides, I am not aware of this alternative construction. If there is one, I would like to know about it. – Sasha Sep 7 '12 at 18:18

Every polynomial $p \in \mathbb{Z}[x]$ has a corresponding companion matrix, whose characteristic polynomial is $p(x)$. A companion matrix of $M$ is naturally similar to $M$ itself.

The companion matrix of $M$ can be found by bringing $M$ to its Frobenius normal form, which can be done in the field $\mathbb{Q}$. Characteristic polynomial of $M$ is readily obtained by the Frobenius normal form (which is block-diagonal matrix of companion matrices), and its discriminant is then computed as $\gcd(p(x),p^\prime(x))$.

See "Faster Algorithms for characteristic polynomial" by A. Storjohann and C. Pernet.

-