§ Discriminant and Resultant

I had always seen the definition of a discriminant of a polynomial $p(x)$ as:
While it is clear why this tracks if a polynomial has repeated roots or not, I could never motivate to myself or remember this definition.
I learnt that in fact, this comes from a more general object, the resultant of two polynomials $P(x), Q(x)$, which provides a new polynomial $Res(P(x), Q(x)$ which is zero iff $P, Q$ share a common root. Then, the discriminant is defined as the resultant of a polynomial and its derivative. This makes far more sense:

• If a polynomial has a repeated root $r$, then its factorization will be of the form $p(x) = (x - r)^2 q(x)$. The derivative of the polynomial will have an $(x-r)$ term that can be factored out.

• On the contrary, if a polynomial only has a root of degree 1, then the factorization will be $p(x) = (x - r) q(x)$, where $q(x)$ is not divisible by $(x-r)$. Then, the derivative will be $p'(x) = 1 \cdot q(x) + (x - r) q'(x)$. We cannot take $(x - r)$ common from this, since $q(x)$ is not divisible by $(x-r)$.

This cleared up a lot of the mystery for me.

§ How did I run into this? Elimination theory.

I was trying to learn how elimination theory works: Given a variety $V = \{ (x, y) : Z(x, y) = 0 \}$, how does one find a rational parametrization $(p(t), q(t))$ such that $Z(p(t), q(t)) = 0$, and $p(t), q(t)$ are rational functions? That is, how do we find a rational parametrization of the locus of a polynomial $Z(x, y)$? The answer is: use resultants!

• We have two univariate polynomials $p(a; x), p(b; x)$, where the notation $p(a; x)$ means that we have a polynomial $p(a; x) \equiv \sum_i a[i] x^i$. The resultant isa polynomial $Res(a; b)$ which is equal to $0$ when $p(a; x)$ and $p(b; x)$ share a common root.

• We can use this to eliminate variables. We can treat a bivariate polynomial $p(x, y)$as a univariate polynomial $p'(y)$ over the ring $R[X]$. This way, given two bivariate polynomial $p(a; x, y)$, $q(b; x, y)$, we can compute their resultant, giving us conditions to detect for which values of $a, b, x$, there exists a common $y$ such that $p(a; x, y)$ and $(q, x, y)$ share a root. If $(a, b)$are constants, then we get a polynomial $Res(x)$ that tracks whether $p(a; x, y)$and $q(a; x, y)$ share a root.

• We can treat the implicit equation above as two equations, $x - p(t) = 0$, $y - q(t) = 0$. We can apply the method of resultants to project out $t$from the equations.

§ 5 minute intro to elimination theory.

Recall that when we have a linear system $Ax = 0$, the system has a non-trivial solution iff $|A| = 0$. Formally: $x \neq 0 \iff |A| = 0$. Also, the ratio of solutions is given by:

If we have two polynomials $p(a; x) = a_0 + a_1 x + a_2 x^2$, and $q(b; x) = b_0 + b_1x + b_2 x^2$, then the system $p(a; x)$, $q(b; x)$ has a simeltaneous zero iff:

§ Big idea

The matrix is setup in such a way that any solution vector $v$ such that $Qv = 0$ will be of the form $v = (\alpha^3, \alpha^2, \alpha, 1)$. That is, the solution vector is a polynomial , such that $Qv = 0$. Since $Qv = 0$, we have that $a_2 \alpha^2 + a_1 \alpha + a_0 = 0$, and $b_2 \alpha^2 + b_1 \alpha + b_0 = 0$.

§ Proof

• Necessity is clear. If we have some non trivial vector $v \neq 0$ such that $Qv = 0$, then we need $|Q| = 0$.

• Sufficiency : Since $|Q| = 0$, there is some vector $v = (w, x, y, z)$such that $Qv = 0$. We need to show that this $v$ is non-trivial. If the polynomials $p(a;x)$, $q(b;x)$ are not equal, then we have that the rows which have coefficients from $p$ and $q$ are linearly independent. So, the pair of rows $(1, 3)$, and the pair $(2, 4)$ are linearly independent. This means that the linear system:

Similarly:

Since the coefficients of the two systems are the same, we must have that $(w, x, y)$ and $(x, y, z)$ are linearly dependent. That is:

We can take $z = 1$ arbitrarily, giving us a vector of the form $(w, x, y, z) = (\alpha^3, \alpha^2, \alpha, 1)$, which is the structure of the solution we are looking for!

§ References

• CMU lectures on Math Fundamentals for Robotics