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.

  • 3
    $\begingroup$ Re: 2, why not just divide $p\#q$ by the greatest common divisor of $p\#q$ and $(p\#q)'$? Multiple root elimination $\endgroup$ – user31373 Jun 19 '12 at 16:42
  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.


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.