Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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
3  
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 1

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

 
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.