Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a monic polynomial $p(t) = t^n + ... + c_1 t + c_0$ with integer (or rational) coefficients and with roots $a_1, \dots a_n$, we can compute its discriminant, which is defined to be $\prod_{i< j}(a_i - a_j)^2$.

In my case, I have a polynomial which is the characteristic polynomial of some invertible matrix $T$. It is palindromic -- i.e., $c_{n-i} = c_i$ for all $0 \leq i \leq n$ -- so the roots come in inverse pairs $a$ and $\frac{1}{a}$. There are no repeated roots, so the discriminant is non-zero.

My question is: is there any way of knowing which primes divide this discriminant, i.e. from the coefficients of the polynomial or from the matrix $T$?

share|improve this question
    
Does the matrix have integer coefficients? –  Qiaochu Yuan Jan 15 '10 at 16:47
    
Did you mean to remove the requirement that T be symmetric? –  Qiaochu Yuan Jan 15 '10 at 20:45
    
@Qiaochu: Yes, the matrix is not supposed to be symmetric: see JCollins' answer below. He didn't say that it was, but the language that he used might suggest that on a first reading. So I clarified it. –  Pete L. Clark Jan 15 '10 at 23:54
    
@Pete. From a post in meta, it seems that JCollis has "she" as the approriate third person pronoun, and not "he". –  Anweshi Jan 16 '10 at 0:57
    
@Anweshi -- OK. I normally use s/he for someone whose name does not give a reasonable guess at his/her gender; looks like I slipped up here. (Probably someone who does not include their first name does not have strong feelings about the matter. Probably.) –  Pete L. Clark Jan 16 '10 at 4:16

4 Answers 4

I disagree with the definition of the discriminant as the resultant of $P$ and $P'$. When $P$ is a polynomial with integer coefficients, then a prime $q$ should divide the discriminant of $P$ if and only if the reduction of $P$ modulo $q$ has a multiple root (possibly at infinity, when the degree decreases by at least 2 under reduction). But now consider $P=2X^2+ 3X+1$. The resultant of $P$ and $P'$ is $-2$, and the reduction of $P$ modulo 2 has no multiple root. In this case, the well known discriminant $b^2-4ac$ is actually 1. The correct relation between the discriminant and the resultant for a polynomial $P(t)=a_nt^n+\cdots+a_1t+a_0$ is $\mathrm{disc}(P)= (-1)^{n(n-1)/2}\mathrm{res}(P,P')/a_n$.

share|improve this answer
    
While you are correct regarding the relationship between the discriminant and the resultant, the OP assumed that the polynomial was monic (hence a_n=1) and that he was only interested in the discriminant up to sign. –  Ben Linowitz Jan 15 '10 at 21:14
    
I refer to the answer of Pete L. Clark, who is not assuming the polynomial to be monic. Moreover, if the polynomial has rational coefficients, then it is sensible to multiply it by an integer in order to obtain a polynomial with integer coefficients and content 1 before asking the question of which primes divide the discriminant. –  Michel Coste Jan 15 '10 at 21:25
    
Point taken. I have edited my answer accordingly. –  Pete L. Clark Jan 16 '10 at 0:53

First, when you say "it is symmetric", you probably mean that the polynomial $P(t) = a_n t^n + ... + a_1 t + a_0$ satisfies $a_{n-i} = a_i$ for all $0 \leq i \leq n$, not that the matrix is symmetric, since it is the former condition which implies that the set of roots is invariant under taking reciprocals (and also that $0$ is not a root). Such a polynomial is more commonly called palindromic.

The connection with the matrix seems unhelpful, because every polynomial is the characteristic polynomial of some matrix, e.g. its companion matrix. (It could possibly become helpful if you had some additional information about the matrix.)

You ask whether one can tell which primes divide the discriminant from the coefficients of the polynomial. The answer is a resounding yes, although perhaps not in a way which will be satisfying to you: you can compute the discriminant directly from the coefficients of the polynomial and then you can factor it! The formula you gave is actually not very good for computing the discriminant: for that it is better to use

$\operatorname{disc}(P) = (-1)^{\frac{(n)(n-1)}{2}} \frac{\operatorname{Res}(P,P')}{a_n}$,

where $P'(t)$ is the derivative and $\operatorname{Res}$ is the resultant, computed using its interpretation as the determinant of the Sylvester matrix.

[Thanks to Michel Coste for pointing out that the discriminant is not quite equal to the resultant of $P$ and $P'$ when $P$ is not monic.]

share|improve this answer
    
Actually, complexity-wise, for a polynomial of degree d, approximating the roots and then calculating $Res(P,P')=\prod P'(\alpha_i)$ directly, would be a soft-oh of d, rather than $d^3$ for the Sylvester. –  Dror Speiser Jan 15 '10 at 20:31

I see that Pete beat me to the Resultant response, so I'll give a slightly different answer. For more on this, see page 21 of Ribbenboim's Classical Theory of Algebraic Numbers.

Let $p(x)=x^n+a_1x^{n-1}+\cdots + a_n$. We'd like to find the discriminant $D(p)$ of $p(x)$ using the coefficients only (i.e. without knowing the roots).

Set $p_k=\alpha_1^k + \cdots + \alpha_n^k$, where the $\alpha_i$ are the roots of $p(x)$ and $k=0,1,2,...$. Now for the amazing part. We can find all of the $p_i$ without actually computing any of the $\alpha_i$!

Explicitly, $p_0=n$, $p_1=-a_1$ and $p_i$ for $i>1$ can be computed recursively using the Newton Formulas.

Then

$D(p)=\displaystyle\det\begin{bmatrix} p_0 & p_1 & \cdots & p_{n-1} \newline p_1 & p_2 & \cdots & p_n \newline \vdots &\vdots & &\vdots\newline p_{n-1}&p_n &\cdots &p_{2n-2} \end{bmatrix}$

share|improve this answer
    
@Ben. What is a good source for learning all these "classical algebra" topics? I see a little bit in Lang, but this is not enough. –  Anweshi Jan 16 '10 at 1:11
    
I'm far from being an expert myself, but I've found Volume II of Jacobson's Basic Algebra to be full of neat results that most texts don't cover. You'd also be wise to bookmark the expository section of Keith Conrad's website: math.uconn.edu/~kconrad/blurbs –  Ben Linowitz Jan 16 '10 at 1:23
    
You are always able to answer when some such algebra topic comes up. So you are indeed a kind of expert. That is why I asked you. Yes, Jacobson is also useful. Still, there are many things I keep wondering about. –  Anweshi Jan 16 '10 at 1:27
    
Thanks a lot for the link to Keith Conrad webpage. It is very useful. –  Anweshi Jan 16 '10 at 1:36

(I haven't worked out how to leave comments on here rather than answers - help!)

The matrix has rational coefficients but is usually not symmetric. It is indeed only the polynomial which is symmetric in its coefficients, as you say.

Not every integer/rational polynomial is the characteristic polynomial of a rational matrix (see here), so I hope that this extra information may be of some help.

I appreciate that I can simply compute the discriminant in particular cases and see what happens, but I was hoping that there would be a general theorem to say something about the prime divisors. So far I can't seem to figure anything out, even using the resultant.

share|improve this answer
    
@JCollins: "Not every integer/rational polynomial is the characteristic polynomial of a rational matrix". Yes, it is! Please follow the link I gave you to see what the companion matrix is and look more carefully at the link you provided to see why it does not assert what you said it does. –  Pete L. Clark Jan 15 '10 at 18:24
    
P.S.: You need at least 50 rep to leave comments. Until you get there, it's fine to leave comments in an answer like this. –  Pete L. Clark Jan 15 '10 at 18:27
    
Sorry, you are right about the companion matrix. Thanks for the link. Thank you also to Ben for the Newton Identities and the determinant formula. Looks tricky to compute but may turn out to help. (I am having issues with Mathoverflow so that the 'me' who asked the question is not the 'me' who is commenting here; thus I have no reputation and cannot comment on my own question! Argh.) –  JCollins Jan 15 '10 at 18:37
    
@Pete L.Clark: Thanks for fixing my question, but if you are going to use $a_i$ for the coefficients of my polynomial, please call the roots something else, like $\alpha_i$. –  JCollins Jan 15 '10 at 18:45
    
@JCollins: Done. –  Pete L. Clark Jan 15 '10 at 20:23

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.