PolynomialMultiplication - crowlogic/arb4j GitHub Wiki

When the multiplication of a polynomial

$$P(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$

by $x$ is represented as a vector

$$\mathbf{v} = [a_0, a_1, a_2, \ldots, a_n]$$

the result is

$$xP(x) = a_0x + a_1x^2 + a_2x^3 + \ldots + a_nx^{n+1}$$

In terms of vector operations, this is equivalent to applying a linear transformation that shifts each element of $\mathbf{v}$ one position to the right, and introduces a zero at the start of the new vector

$$\mathbf{v'} = [0, a_0, a_1, \ldots, a_n]$$

This transformation can be represented by a matrix $A$, where $A$ is an $(n+1) \times (n+1)$ matrix with 1's on the subdiagonal and 0's elsewhere:

A = \begin{pmatrix} 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix}

Then, the multiplication $xP(x)$ corresponds to the matrix-vector product $A\mathbf{v}$, which yields $\mathbf{v'}$ and provides a representation of the shift operation in linear algebraic terms.