Sum-Check as an Algebraic Tensor Reduction: Part III - ZK/SEC Quarterly

Back to all posts

This article is the third in a series. The previous two chapters are required reading for this post and can be found here (Part I) and here (Part II).

In Part II, we introduced rings and modules as the first pieces of mathematical vocabulary needed to view sum-check through the lens of algebraic tensor reductions. In this post, we continue building that toolkit by studying maps between modules: linear maps, isomorphisms, and bilinear maps. As promised, the goal is not to make you memorize every definition, but to build a useful reference for the later parts of the series. Let’s dive right in, shall we?

Linear Maps

Definition

Consider a ring $R$ and two $R$-modules $M$ and $N$. A linear map (or $R$-linear map, or module homomorphism) from $M$ to $N$ is a function $f:M\to N$ that satisfies the following conditions for all $m,m^\prime\in M$ and all $r\in R$:

$f(m+m^\prime)=f(m)+f(m^\prime)$.

$f(r\cdot m)=r\cdot f(m)$.

If $f:M\to N$ is a linear map between $R$-modules $M$ and $N$, we also write $f\in \text{hom}_R(M,N)$ or simply $f\in \text{hom}(M,N)$.

Note

One can show that the set $\text{hom}(M,N)$ of $R$-linear maps from $M$ to $N$ itself forms a module over $R$. Proving this is actually quite simple, but beyond the scope of this blog post series.

Examples

The identity map $\text{id}_M:M\to M,\hspace{5pt}m\mapsto m$ is an $R$-linear map for every $R$-module $M$.

The zero map $0:M\to N, \hspace{5pt}m\mapsto 0$ is an $R$-linear map for any two $R$-modules $M$ and $N$.

Consider the $R$-module $R^n$. For any fixed scalars $a_1,...,a_n\in R$, the map<br>$$<br>f:R^n\to R, \hspace{5pt} (x_1,...,x_n)\mapsto a_1x_1+\cdots+a_nx_n<br>$$<br>is an $R$-linear map. Notice that this linear map can also be viewed as matrix-multiplying a $(1\times n)$-matrix $A=(a_1,...,a_n)$ with a given vector $(x_1,...,x_n)^\top$ (viewed as an $(n\times 1)$-matrix).

More generally, any $(m\times n)$-matrix $A\in \mathcal{M}_{m\times n}(R)$ defines an $R$-linear map $f_A:R^n\to R^{m}, \hspace{5pt}x\mapsto Ax$. Conversely, every $R$-linear map $f\in \text{hom}(R^n,R^m)$ can be represented via an $(m\times n)$-matrix.

The differentiation map $D:R[x]\to R[x], \hspace{5pt} f(x)\mapsto f^\prime(x)$ for univariate polynomials is an $R$-linear map. Indeed, differentiation is additive and satisfies $(r\cdot f)^\prime=r\cdot f^\prime$ for all $r\in R$ and all $f\in R[x]$.

A univariate polynomial $p(x)=ax\in R[x]$ of degree $1$ and without constant term defines a linear map $p:R\to R,\hspace{5pt}x\mapsto ax$, where $a\in R$ is $p$’s only coefficient.

On the contrary, the univariate degree-$1$ polynomial $p(x)=x+1$, which we can also write as $p:R\to R,\hspace{5pt}x\mapsto x+1$, does not define a linear map. In particular, “linear” polynomials (in the sense that they are degree-$1$) do generally not define linear maps. To see this in the example $p(x)=x+1$, consider the second condition of our definition above. Fix $m=0$ and let $r\in R$ be an arbitrary element of $R$ with the only restriction that $r\neq 1$. Then, we have $p(r\cdot m)\neq r\cdot p(m)$ because<br>$$<br>p(r\cdot m)=p(r\cdot 0)=p(0)=1\neq r =r\cdot (0+1)=r\cdot p(0)=r\cdot p(m),<br>$$<br>violating the second condition of our definition of linear maps.

Intuition

A linear map is a function that preserves the module structure in the sense that it respects the two basic operations that make a module a module: addition of elements and multiplication by scalars.

Notice that our definition here is almost equivalent to the definition of linear maps between vector spaces. The only difference is that we now allow scalars to come from a ring rather than a field.

Of all the above examples, keep Example 3 in mind, as it is the linear map that will be most relevant throughout the rest of this blog post series.

Isomorphisms

Definition

Consider a ring $R$ and two $R$-modules $M$ and $N$. An isomorphism from $M$ to $N$ is a linear map $f:M\to N$ for which there exists another linear map $g:N\to M$ such that the two equations

$g\circ f=\text{id}_M$

$f\circ g=\text{id}_N$

hold, where $\text{id}_X$ denotes the identity map on a given $R$-module $X$. In other words, applying $f$ and then $g$ gives us back the original element of $M$, and applying $g$ and then $f$ gives us back the original element of $N$.

If there exists an isomorphism $f:M\to N$, we say that $M$ and $N$ are isomorphic and write $M\cong N$.

The map $g:N\to M$ is called the inverse of $f$, usually denoted by $f^{-1}$.

Equivalently, an isomorphism is a linear map that is bijective, meaning that it is both injective and surjective.

Examples

The identity map $\text{id}_M:M\to M,\hspace{5pt}m\mapsto m$ is an isomorphism for every $R$-module $M$. Its inverse is itself.

Consider the $R$-module $R^2$. The map$f:R^2\to R^2,\hspace{5pt}(x,y)\mapsto(y,x)$ is an isomorphism. Indeed, it is linear, and applying it twice gives back the original input:...