6
$\begingroup$

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.

  • 1
    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.2012-09-07

1 Answers 1

1

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.