11
$\begingroup$

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$?

$\endgroup$
7
  • $\begingroup$ Does the matrix have integer coefficients? $\endgroup$ Jan 15, 2010 at 16:47
  • $\begingroup$ Did you mean to remove the requirement that T be symmetric? $\endgroup$ Jan 15, 2010 at 20:45
  • $\begingroup$ @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. $\endgroup$ Jan 15, 2010 at 23:54
  • $\begingroup$ @Pete. From a post in meta, it seems that JCollis has "she" as the approriate third person pronoun, and not "he". $\endgroup$
    – Anweshi
    Jan 16, 2010 at 0:57
  • $\begingroup$ @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.) $\endgroup$ Jan 16, 2010 at 4:16

3 Answers 3

5
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user1073
    Jan 15, 2010 at 21:14
  • $\begingroup$ 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. $\endgroup$ Jan 15, 2010 at 21:25
  • $\begingroup$ Point taken. I have edited my answer accordingly. $\endgroup$ Jan 16, 2010 at 0:53
4
$\begingroup$

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.]

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 15, 2010 at 20:31
1
$\begingroup$

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}$

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$
    – Anweshi
    Jan 16, 2010 at 1:11
  • $\begingroup$ 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 $\endgroup$
    – user1073
    Jan 16, 2010 at 1:23
  • $\begingroup$ 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. $\endgroup$
    – Anweshi
    Jan 16, 2010 at 1:27
  • $\begingroup$ Thanks a lot for the link to Keith Conrad webpage. It is very useful. $\endgroup$
    – Anweshi
    Jan 16, 2010 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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