Polynomial Substitution Maps in Coefficient Bases

Substitution as a Map on Polynomial Coefficients

A substitution changes the input of a polynomial, but its effect can also be described by a matrix acting on the polynomial’s coefficients. The key is to use an ordered basis and keep track of which coefficients appear in the image of each basis polynomial. This makes the matrix columns—not its rows—the natural place to record the results.

For \(n\geq 0\), let \(P_n(\mathbb{R})\) be the real vector space of polynomials of degree at most \(n\), together with the zero polynomial. Its ordered monomial basis is \(\mathcal{B}_n=(1,x,\dots,x^n)\). If \(p(x)=c_0+c_1x+\cdots+c_nx^n\), its coordinate vector in this basis is \([p]_{\mathcal{B}_n}=(c_0,c_1,\dots,c_n)^{\top}\). The order matters: the first entry is the constant coefficient, followed by the coefficients of \(x\) through \(x^n\).

The map has the stated codomain because substituting a linear polynomial into a polynomial of degree at most \(n\) produces a polynomial of degree at most \(n\). The map is linear: for polynomials \(p,q\) and scalars \(a,b\), substitution gives \((ap+bq)(\alpha x+\beta)=a\,p(\alpha x+\beta)+b\,q(\alpha x+\beta)\). We can therefore represent it by a matrix in the chosen basis.

Finding the Matrix from Monomial Images

To construct a matrix in a domain basis and codomain basis, compute the image of each domain basis vector and write that image in codomain coordinates. Here the domain and codomain are both \(P_n(\mathbb{R})\), with the same ordered basis. The binomial expansion gives the image of each monomial:

We use the convention \(t^0=1\), including when \(t=0\). In the coefficient formula below, \(i\) numbers the degree, starting at zero, and \(j\) numbers the input monomial degree, also starting at zero.

Proof. The \(j+1\)-st basis vector is \(x^j\). By the definition of the substitution, its image is \((\alpha x+\beta)^j\). The binomial expansion writes this image as a sum of monomials \(x^i\), with coefficient \(\binom{j}{i}\alpha^i\beta^{j-i}\) for \(0\leq i\leq j\); there are no terms of degree greater than \(j\). Therefore the coordinates of this image form column \(j+1\), with the stated entries in rows \(i+1\) and zeros in rows below degree \(j\). To verify that these columns represent the map on every polynomial, write \(p=\sum_{j=0}^{n}c_jx^j\). Linearity gives \(S_{\alpha,\beta}(p)=\sum_{j=0}^{n}c_jS_{\alpha,\beta}(x^j)\), so its coordinate vector is the matrix with those columns multiplied by \((c_0,\dots,c_n)^{\top}\). This is precisely the matrix representation in the basis \(\mathcal{B}_n\). \(\square\)

For the translation \(p(x)\mapsto p(x+1)\), take \(\alpha=1\) and \(\beta=1\). The matrix is upper triangular: entries below the diagonal are zero because the image of \(x^j\) has degree at most \(j\). Its diagonal entries are all \(1\), because the coefficient of \(x^j\) in \((x+1)^j\) is \(1\).

Affine Substitution with Other Parameters

The same method applies when the input is \(\alpha x+\beta\) rather than just \(x+1\). The entries can be read from the binomial expansion, but building the columns directly is often the safest way to avoid confusing the order of the coefficients or the basis vectors.

The affine substitution matrix need not have diagonal entries equal to \(1\). In this example, the diagonal entries are \(1,2,4\), corresponding to the leading coefficients in the images of \(1,x,x^2\). For a general affine substitution, the diagonal entry in degree \(j\) is \(\alpha^j\). If \(\alpha=0\), all positive-degree terms become constant; the formula still applies and reflects that loss of degree.

Translation Preserves All Polynomial Coefficients

Translation has a useful additional property: it gives a bijection from \(P_n(\mathbb{R})\) to itself. This can be seen directly from substitution, without solving a system of equations involving its matrix.

Proof. The matrix statement follows from the affine substitution matrix formula: entries below the diagonal have row degree \(i\) greater than column degree \(j\), so they are zero, and each diagonal entry has \(i=j\), giving \(\binom{j}{j}1^j1^0=1\) (with the degree-zero entry also equal to \(1\)). For bijectivity, define \(U:P_n(\mathbb{R})\to P_n(\mathbb{R})\) by \(U(q)(x)=q(x-1)\). This map also takes \(P_n(\mathbb{R})\) into itself because replacing \(x\) by \(x-1\) does not increase degree. For every \(p\in P_n(\mathbb{R})\), \(U(S_{1,1}(p))(x)=S_{1,1}(p)(x-1)=p((x-1)+1)=p(x)\). For every \(q\in P_n(\mathbb{R})\), \(S_{1,1}(U(q))(x)=U(q)(x+1)=q((x+1)-1)=q(x)\). Thus each map undoes the other: every polynomial in the codomain is attained, and two polynomials with the same translated image must be equal. Hence \(S_{1,1}\) is both onto and one-to-one, and therefore bijective. \(\square\)

Choosing a Polynomial Space That Fits

A substitution does not always map \(P_n(\mathbb{R})\) back into \(P_n(\mathbb{R})\). The declared codomain must contain the substituted outputs. For example, replacing \(x\) by \(x^2\) in a polynomial of degree at most \(2\) can produce a polynomial of degree \(4\). In that case, the natural map has a larger codomain, and its matrix is rectangular.

Common Mistakes and a Reliable Check

Putting basis images in rows instead of columns. For translation on \(P_2(\mathbb{R})\), the image of the basis vector \(x\) is \(x+1\), whose coordinate vector is \((1,1,0)^{\top}\). A common wrong calculation places the three basis-image vectors as rows, producing the transpose of the correct matrix:

This incorrectly says that \(x\) maps to \(x+2x^2\). The correction is to put each basis image in a column, because multiplying by the coordinate vector \((0,1,0)^{\top}\) must select the second column. With the correct matrix, that column is \((1,1,0)^{\top}\), representing \(1+x\).

Using a codomain that is too small. The substitution \(p(x)\mapsto p(x^2)\) cannot be treated as a map \(P_2(\mathbb{R})\to P_2(\mathbb{R})\): the input \(p(x)=x^2\) produces \(x^4\). Choosing \(P_4(\mathbb{R})\) as the codomain fixes the issue and gives a well-defined matrix with five rows and three columns.

A reliable procedure is to state the domain, codomain, and ordered bases first; compute the image of each domain basis vector; write its coordinates in the codomain basis as a column; and finally test the matrix on a polynomial by comparing its output with direct substitution. These checks catch both basis-order errors and mistakes about the degree of the output.