Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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. –  Sasha Sep 7 '12 at 18:18

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.