4

Answers to this question describe how, if we square an order-$m$ polynomial with coefficients $a_k$,

$$ p(x) = \left( \sum_{k=0}^{m} a_k x^k \right)^2 = \sum_{k=0}^{2m} c_k x^k $$

the coefficients $c_k$ of the resulting order-$2m$ polynomial can be calculated as

$$ c_k = \sum_{j=0}^{k} a_j a_{k-j} $$

provided we take $a_j = 0$ in cases where $j \notin \{ 0, \dots, m\}$.

Question:

If we let $\mathbf{c}$ be a length $2m+1$ vector containing all the $c_k$, and $\mathbf{a}$ be a length $m+1$ vector containing all the $a_k$, is it possible to express $\mathbf{c}$ as a matrix product of $\mathbf{a}$ with other matrices?

I've been thinking about constructing some matrices to pad the $\mathbf{a}$ with zeros up to the length of $\mathbf{c}$, then making a reversed copy, but haven't been able to get any further. Thanks!

Rodrigo de Azevedo
  • 1
CBowman
  • 499
  • 3
  • 15
  • I think you would need something like a circulant matrix built from $\bf a$ (but one that didn't wrap around at the ends), which isn't exactly expressible as a matrix product. – Greg Martin Jan 01 '17 at 02:37
  • 1
    You asked if $c$ depends linearly on $a$, which is in general not the case. – user251257 Jan 01 '17 at 03:21
  • But you might interested in the connection of Convolution and (Fast) Fourier Transform (which is well known) – user251257 Jan 01 '17 at 03:23
  • I have read this three times and I still forget the main question by the time I get my paper out. Bravo. – The Count Jan 01 '17 at 03:49
  • Having reread it, @user251257 is correct that the relation is not linear, so a matrix in general will not work, although you can surely find situations where one does the job. – The Count Jan 01 '17 at 03:51

2 Answers2

0

This squaring transformation could be viewed as $$\begin{array}{llll} &\begin{bmatrix}a_0\end{bmatrix}&&\xrightarrow{\square}&&&\begin{bmatrix}a_0^2\end{bmatrix}\\ &\begin{bmatrix}a_0\\a_1\end{bmatrix}&&\xrightarrow{\square}&&&\begin{bmatrix}a_0^2\\2a_0a_1\\a_1^2\end{bmatrix}\\ &\begin{bmatrix}a_0\\a_1\\a_2\end{bmatrix}&&\xrightarrow{\square}&&&\begin{bmatrix}a_0^2\\2a_0a_1\\a_1^2+2a_0a_2\\2a_1a_2\\a_2^2\end{bmatrix}\\ &\begin{bmatrix}a_0\\a_1\\a_2\\a_3\end{bmatrix}&&\xrightarrow{\square}&&&\begin{bmatrix}a_0^2\\2a_0a_1\\a_1^2+2a_0a_2\\2a_0a_3+2a_1a_2\\a_2^2+2a_1a_3\\2a_2a_3\\a_3^2\end{bmatrix}\\ \end{array}$$ and so on...

Left multiplication involves a $\quad (2m+1) \times (m+1)\quad$ sized matrix of the following step down pattern: $$\begin{bmatrix}a_0&0\\a_1&a_0\\0&a_1\end{bmatrix}\begin{bmatrix}a_0\\a_1\end{bmatrix}=\begin{bmatrix}a_0^2\\2a_0a_1\\a_1^2\end{bmatrix}$$

$$\begin{bmatrix}a_0&0&0\\a_1&a_0&0\\a_2&a_1&a_0\\0&a_2&a_1\\0&0&a_2\end{bmatrix}\begin{bmatrix}a_0\\a_1\\a_2\end{bmatrix}=\begin{bmatrix}a_0^2\\2a_0a_1\\a_1^2+2a_0a_2\\2a_1a_2\\a_2^2\end{bmatrix}$$ and so on... so if there were a matrix that answered this OP's question, it could be of this type: $$\begin{bmatrix}a_0&0&0&\cdots&0\\a_1&a_0&0&\cdots&0\\a_2&a_1&a_0&\cdots&0\\\vdots&\vdots&\vdots&\ddots\\a_m&a_{m-1}&a_{m-2}&\cdots&a_0\\0&a_m&a_{m-1}&\cdots&a_1\\0&0&a_m&\cdots&\vdots\\0&0&0&\ddots\\ \vdots&\vdots&\vdots&\cdots&\vdots\\0&0&0&\cdots&a_m\end{bmatrix}$$ where each column has $\quad m+1\quad$ entries that make up the components of $\quad \mathbf{a}\quad$ and $\quad m\quad$ more zeros, just graduated down

SideProj314
  • 43
0

Let us consider the squaring of quadratic polynomials, i.e., the case where $m=2$. Let

$$ {\bf B}_0 := \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad\quad {\bf B}_1 := \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad\quad {\bf B}_2 := \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}, \\ \, \\ \, \\ {\bf B}_3 := \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \quad\quad {\bf B}_4 := \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

Note that ${\bf B}_2$ is the $3 \times 3$ reversal matrix. Note also that matrices ${\bf B}_0, {\bf B}_1, {\bf B}_2, {\bf B}_3, {\bf B}_4$ form the "natural" basis for the subspace of $3 \times 3$ Hankel matrices, i.e.,

$$ \begin{bmatrix} h_0 & h_1 & h_2 \\ h_1 & h_2 & h_3 \\ h_2 & h_3 & h_4 \end{bmatrix} = \sum_{k=0}^4 h_k {\bf B}_k $$

A quadratic (univariate) polynomial $q$ can be written as follows

$$ q (x) = \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix}^\top \underbrace{\begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}}_{=: {\bf v} (x)} = {\bf a}^\top {\bf v} (x) $$

Squaring $q$,

$$ q^2 (x) = {\bf v}^\top (x) \, {\bf a} \, {\bf a}^\top \, {\bf v} (x) = \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^\top \begin{bmatrix} a_0^2 & a_0 a_1 & a_0 a_2 \\ a_1 a_0 & a_1^2 & a_1 a_2 \\ a_2 a_0 & a_2 a_1 & a_2^2 \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} $$

Note that the $1 + 2m = 5$ coefficients of the polynomial $q^2$ are given by the sums of the entries in the $1 + 2m = 5$ anti-diagonals of the rank-$1$ matrix ${\bf a} \, {\bf a}^\top$. The $k$-th coefficient is given by

$$ \boxed{c_k = \langle {\bf B}_k , {\bf a} \, {\bf a}^\top \rangle = \color{blue}{{\bf a}^\top {\bf B}_k \, {\bf a}}} $$

where $\langle \cdot \, , \cdot \rangle$ denotes the Frobenius inner product. If $m > 2$, the coefficients can be found in a similar manner. Note that this is convoluted way of writing the convolution of $\bf a$ with itself.

Rodrigo de Azevedo
  • 1