From vector of polynomials to matrix multiplication

abstract-algebramatricesmatrix-calculuspolynomials

Imagine that I have two vectors of polynomials $\mathbf{v}, \mathbf{u}$ where $\mathbf{v} = (f_1, f_2, \dots, f_m)$ and $\mathbf{u} = (g_1, g_2, \dots, g_m)$ with $f_i,g_i \in\mathbb{Z}_q[x] / \langle x^n+1\rangle$ for $i \in [m]$. Recall that, when $n$ is a power of $2$, $\mathbb{Z}_q[x] / \langle x^n+1\rangle$ is the ring of polynomials with degree at most $n-1$ with coefficients from $\mathbb{Z}_q = \{0, 1, \dots, q-1\}$ for a prime $q$. Hence, each $f \in \mathbb{Z}_q[x] / \langle x^n+1\rangle$ has the form $$f = a_0 + a_1x + \dots + a_{n-1}x^{n-1}.$$

My objective is to perform the operation (I represent vectors as column vectors) $$\mathbf{u}^T \cdot \mathbf{v}= h\in \mathbb{Z}_q[x] / \langle x^n+1\rangle$$ but in matrix form, i.e., I would like to somehow represent these vectors as matrices with coefficients in $\mathbb{Z}_q$ such that their product gives a vector $\mathbf{h} = (h_0, h_1, \dots, h_{n-1}) \in \mathbb{Z}_q^n$ such that $$h = h_0 + h_1x + \dots + h_{n-1}x^{n-1}.$$ This is the natural embedding of vectors in polynomials and vice-versa.

I am not sure how to do it. Any help will be appreciated.

Best Answer

If $P$ denotes the permutation matrix $$ P = \pmatrix{&&&-1\\ 1\\ &\ddots \\ &&1}, $$ then the map to the circulant matrices defined by $f \mapsto f(P)$ is an isomorphism of rings. With that established, $u^Tv$ can be calculated with the block-matrix product $$ (u^Tv)(P) = \pmatrix{g_1(P) & \cdots & g_m(P)} \pmatrix{f_1(P) \\ \vdots \\ f_m(P)}. $$

Related Solutions

Linear Algebra – Lagrange Basis Functions in Polynomial Space

Here is very easy method to show that they are linearly independent.

Suppose that $$b_1g_1(x)+b_2g_2(x)+...+b_ng_n(x)=0$$ To show linear independence, it suffices to show that $$b_1=b_2=...=b_n=0$$ Evaluate $$b_1g_1(x)+b_2g_2(x)+...+b_ng_n(x)=0$$ at $$x=a_i\;\;\;\;\forall i\le n$$

You can notice that $$g_i(a_j)=\begin{cases}0&i\neq j \\ 1 & i=j\end{cases}$$

It follows that $$b_1=b_2=b_3=...=b_n=0$$

To see that the coordinates are given as such, consider a general polynomial as above $$f(x)=c_1g_1(x)+c_2g_2(x)+...+c_ng_n(x)=0$$

Follow same thing as above, start substituting $x=a_i$, you will see that $$c_1=f(a_1)$$ and so on.

Best of luck. I hope I could help.

Coefficients such that linear combination lies in an ideal

Suppose $I = \langle f_1, \ldots, f_r\rangle$ and consider the map $R^r \oplus R^m \twoheadrightarrow I + J$ that sends $(b,c) \mapsto \sum_j b_j f_j + \sum_i c_i g_i$.

Its kernel $K$ is the first module of syzygies for $I+J$. The projection of $K$ to $R^m$ is exactly the $R$-module $T$ that you want.

Proof. The projection of $K$ to $R^m$ consists of those $c \in R^m$ for which there exists $b$ such that $\sum c_i g_i = -\sum b_j f_j \in I$, and for every $c \in R^m$ with $\sum c_i g_i \in I$ there exists such a $b$.

So the algorithm is: calculate the first module of syzygies for $I+J$ and project to $R^m$.

Example: $I = \langle f \rangle = \langle x^2 + y^2 - 1\rangle$ and $J = \langle \frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\rangle = \langle 2x, 2y \rangle$. In SageMath:

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: I = R.ideal(x^2+y^2-1)
sage: J = R.ideal(2*x, 2*y)
sage: T = (I+J).syzygy_module()[:,len(I.gens()):]; T
[           -y             x]
[          x*y       y^2 - 1]
[x^2 + y^2 - 1             0]

Here the projection to $R^m$ is achieved by slicing the matrix of generators of $K$.

The rows of the resulting matrix are generators of $T$.

In the example we see that $x\frac{\partial}{\partial y}-y\frac{\partial}{\partial x}$ is a polynomial vector field on the circle and furthermore $IR^m \subset T$.

One might be more interested in a (smaller) set of generators for the quotient $T/IR^m$.

To this end we can find the module of syzygies for $T + IR^m$ and project to the space of coefficients for generators of $T$; these are syzygies for $T$ modulo $IR^m$. For every such syzygy modulo $IR^m$ where one of the coefficients is an invertible constant, remove the respective generator (because it can be expressed in terms of the others, modulo $IR^m$).

Continuing the example in Singular:

> ring r=0,(x,y),dp;
> module n = [-y, x], [xy, y2-1], [x2+y2-1,0], [x2+y2-1,0], [0,x2+y2-1]; // T + IR^m
> LIB "matrix.lib";
...
> print(submat(transpose(syz(n)),1..3,1..3));
0,   0, -1,
x,   1, 0, 
y2-1,-x,y

Here we see that columns two and three contain invertible constants, so the second and third generators can be removed.

So in this example $T/IR^m$ is generated by $(-y, x)$.

For completeness, the calculation above can be achieved (in general) through the SageMath interface to Singular:

sage: import itertools
sage: m = len(J.gens())
sage: IRm = matrix([[i if j == b else 0 for j in range(0,m)]
                    for (i,b) in itertools.product(I.gens(),range(0, m))])
sage: r = R._singular_()
sage: n = singular(map(list, list(T) + list(IRm)), type='module') # T + IR^m
sage: singular('transpose(syz(%s))' % n.name(), type='matrix').sage()[:,0:T.nrows()]
[      0       0      -1]
[      x       1       0]
[y^2 - 1      -x       y]

A final useful remark is that the set of $\sum c_i g_i$, where $c$ ranges over the generators of $T$, is a set of generators for $I \cap J$. In SageMath:

sage: R.ideal([sum(map(prod,zip(t,J.gens()))) for t in T]) == I.intersection(J)
True

The proof attempt in the question was an attempt to reverse this process.

Best Answer

Related Solutions

Linear Algebra – Lagrange Basis Functions in Polynomial Space

Coefficients such that linear combination lies in an ideal

Related Question