Different Representation of Product of Polynomial

91 Views Asked by At

Suppose $f=\sum_{i=0}^m f_i\cdot x^i$ and $g=\sum_{j=0}^ng_j\cdot x^j$. Then $f\cdot g$ $=\sum_{s=0}^{m+n}(f\cdot g)_{s}\cdot x^s$ $=\sum_{s=0}^{m+n}(\sum_{r=0}^s f_r\cdot g_{s-r})\cdot x^s$. The reader should verify, in the special case $f=c\cdot x^m$, $g=d\cdot x^n$ with $c,d$ in $F$, that reduces to $(c\cdot x^m)\cdot (d\cdot x^n)$ $=(c\cdot d)\cdot x^{m+n}$. From this fact and the distributive law in $F[x]$, it follows that the product $f\cdot g$ is also given by $\sum_{i,j}(f_i \cdot g_j)\cdot x^{i+j}$, where the sum is extended over all integer pairs $i, j$ such that $0\leq i \leq m$, and $0\leq j \leq n$. It can also be written as $\sum_{i=0}^m \sum_{j=0}^n (f_i \cdot g_j)\cdot x^{i+j}$.

I don’t really understand following step: From $(c\cdot x^m)\cdot (d\cdot x^n)$ $=(c\cdot d)\cdot x^{m+n}$ fact and the distributive law in $F[x]$, it follows that the product $f\cdot g$ is also given by $\sum_{i,j}(f_i \cdot g_j)\cdot x^{i+j}$. I have made only partial progress. By distributive law in $F[x]$ and above fact, we have $\sum_{s=0}^{m+n}(\sum_{r=0}^s f_r\cdot g_{s-r})\cdot x^s$ $=\sum_{s=0}^{m+n}(\sum_{r=0}^s (f_r\cdot g_{s-r})\cdot x^s)$ $=\sum_{s=0}^{m+n}\sum_{r=0}^s (f_r\cdot x^r)\cdot (g_{s-r}\cdot x^{s-r})$.

2

There are 2 best solutions below

5
On BEST ANSWER

For matrix $a_{i,j},$ $0\le i\le n$, $0\le j\le m$ we have $$\sum_{i=0}^n\sum_{j=0}^m a_{i,j}=\sum_{s=0}^{m+n}\sum_{r=0}^s a_{r,s-r} \quad (*)$$ with convention $a_{r,s-r}=0$ if $r>n$ or $s-r>m.$

The formula describes two different ways of summing the entries of the matrix. The first way is to sum the entries in each row and then add the results. The second way is to sum the entries along the lines perpendicular to the line $i=j$, and add the results. If $n=m$, i.e. we have a square matrix, the line $i=j$ describes the diagonal of the matrix.

In the special case $a_{i,j}=b_ic_j$ the first way gives $$\sum_{i=0}^n\sum_{j=0}^m b_ic_j=\left (\sum_{i=0}^nb_i\right )\left (\sum_{j=0}^mc_j\right )\qquad (**)$$ In our case we have $a_{ij}=f_ig_jx^ix^j$ so $b_i=f_ix^i,$ $c_j=g_jx^j,$ and $a_{r,s-r}=f_rg_{s-r}x^s.$ Hence applying $(*)$ we get $$\left (\sum_{i=0}^nf_ix^i\right )\left (\sum_{j=0}^m g_{j}x^j\right )=\sum_{s=0}^{m+n}\sum_{r=0}^s f_rg_{s-r}x^s (***)$$

The question can be explained also in the following way. We want to multiply two polynomials $\sum_{i=0}^nf_ix^i,$ $\sum_{j=0}^mg_jx^j,$ and then represent the product as a new polynomial. We multiply polynomials term by term obtaining $(n+1)(m+1)$ terms of the form $f_ig_jx^{i+j}.$ Now we collect the terms corresponding to the same power of $x,$ i.e. with the same value $i+j.$ The quantity $i+j$ ranges from $0$ up to $n+m.$ Denote $s=i+j$ and $r=i.$ Then $j=s-r$ and $f_ig_jx^{i+j} =f_rg_{s-r}x^s.$ Now we collect the terms corresponding to the power $s$ of $x,$ obtaining $$\sum_{r=0}^sf_rg_{s-r}x^s$$ Finally we sum up over all possible $s$ and get $$\sum_{s=0}^{m+n}\sum_{r=0}^s f_rg_{s-r}x^s$$

0
On

$f\cdot g$ $= (\sum_{i=0}^mf_ix^i)\cdot(\sum_{j=0}^n g_jx^j)$ $= \sum_{i=0}^m ((f_ix^i)\cdot\sum_{j=0}^n g_jx^j)$ $= \sum_{i=0}^m (\sum_{j=0}^n (f_ix^i)\cdot (g_jx^j))$ $= \sum_{i,j} f_ig_jx^{i+j}$