Take the 2-minute tour ×
  1. Given 2 polynomials $p(x)=\prod_{i=1}^{r}(x-r_i), q(x)=\prod_{j=1}^{s}(x-r'_j)$, what is the name of the operation that constructs $f\#g(x) = \prod_{i=1}^{r}_{j=1}^{s} (x-r_i r'_j)$ from $p$ and $q$?

  2. Let's say $p, q \in \mathbb{Z}[x]$. Is there an algorithm for computing the monic polynomial in $\mathbb{Z}[x]$ of least degree such that it vanishes on the set $\{ r_i r'_j \}_{i,j}$? I know that $p\# q$ has integral coefficients (by symmetric polynomials arguments), but I have examples where some elements occur more than once in the multiset $\{r_i r'_j \}$, and I guess it may effect the degree of the polynomial I seek.

The case $p=q$ is of big interest to me.

Motivation: given 2 linear recurrence (with integer coefficients) sequences $\{ a_n\}, \{b_n \}$, their Hadamarad product $\{a_n b_n \}$ also satisfies a linear recurrence with integer coefficients. Specifically, if $a_n$ satisfies a linear recurrence with characteristic polynomial $p(x)$ and $b_n$ with $q(x)$, then $\{a_n b_n \}$ satisfies a linear recurrence with characteristic polynomial $p \# q$ - but it may not be the minimal one, and that's why I am investigating.

share|improve this question
Re: 2, why not just divide $p\#q$ by the greatest common divisor of $p\#q$ and $(p\#q)'$? Multiple root elimination –  user31373 Jun 19 '12 at 16:42
add comment

1 Answer

up vote 0 down vote accepted
  1. I don't know if there is a widely accepted name, but I would call it the Kronecker product. The reason is that if $M, N$ are two matrices with eigenvalues $m_i, n_i$ then their Kronecker product $M \otimes N$ has eigenvalues $m_i n_j$.

  2. Let $M, N$ be the companion matrices of your polynomials. Compute the characteristic polynomial of $M \otimes N$, then divide it by the gcd with its formal derivative as Leonid says in the comments. This is divisible by the polynomial you want and from here I think you just have to factor it.

If your actual goal is to compute Hadamard products of rational functions, there is another way to do this using complex analysis. This is described in this blog post.

share|improve this answer
add comment

Your Answer


