Linear Maps on Polynomials and Matrices, linear algebra I lesson

The curves $p(t) = 2 + 3t - t^2$ and $q(t) = 2 + 2t$ are different, yet both have height $2$ at $t = 0$ and height $4$ at $t = 1$ . A device that records only those two heights cannot tell them apart. What exactly does such a measurement lose, and which readings can it produce? This lesson writes the measurement as a linear map, builds its matrix from basis images, finds its kernel and image, and then does the same for the trace of a matrix.

Key terms

Evaluation map

Definition A map $T$ from a vector space $V$ to a vector space $W$ is linear when $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$ and $T(c\mathbf{u}) = cT(\mathbf{u})$ for all $\mathbf{u}, \mathbf{v}$ in $V$ and all real $c$ . Fix real numbers $s_1, \dots, s_k$ , called sample points. The evaluation map $E$ from $P_2$ to $\mathbb{R}^k$ sends a polynomial to its values at these points,

E(p) = \begin{bmatrix} p(s_1) \\ \vdots \\ p(s_k) \end{bmatrix}.

It is linear, because $(p + q)(s_i) = p(s_i) + q(s_i)$ and $(cp)(s_i) = c\,p(s_i)$ at each fixed $s_i$ . The main example below uses the sample points $0$ and $1$ , so $E(p) = (p(0), p(1))$ .

In plain words The map is a measuring device that records the height of the graph at a few fixed inputs. The inputs stay put while the polynomial changes, and at a fixed input the value of a sum is the sum of the values, so the readings of a sum are the sums of the readings.

Example On this page a tuple written inline, such as $(2, 4)$ , stands for a column vector. For $p(t) = 2 + 3t - t^2$ the readings are $p(0) = 2$ and $p(1) = 2 + 3 - 1 = 4$ , so $E(p) = (2, 4)$ , and $q(t) = 2 + 2t$ also gives $E(q) = (2, 4)$ . Linearity then says $E(q - p) = (0, 0)$ , and indeed $q - p = t^2 - t$ vanishes at $0$ and at $1$ . Not every rule built from values is linear. The rule $S(p) = p(0)\,p(1)$ gives $S(1) = 1$ for the constant polynomial $1$ , but $S(2) = 4$ for the constant polynomial $2$ , not $2S(1) = 2$ , so it fails the scaling condition.

Linear map determined by basis images

Definition Let $V$ be a finite-dimensional vector space with ordered basis $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ , let $W$ be a vector space, and let $\mathbf{w}_1, \dots, \mathbf{w}_n$ be any vectors in $W$ , with repeats and dependence allowed. Then there is exactly one linear map $T$ from $V$ to $W$ with $T(\mathbf{v}_j) = \mathbf{w}_j$ for every $j$ . For all real numbers $c_1, \dots, c_n$ it is given by

\begin{aligned} &T(c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n) \\[0.4em] &\quad = c_1\mathbf{w}_1 + \cdots + c_n\mathbf{w}_n. \end{aligned}

Any linear map with these basis images must obey this formula, which gives uniqueness. The formula is well defined because each vector has unique coordinates in the basis, and it is linear because coordinates add and scale, which gives existence.

In plain words A linear map is known as soon as you know what it does to a basis. Those images can be chosen freely, and linearity fills in everything else.

Example The evaluation map is pinned down by $E(1) = (1, 1)$ , $E(t) = (0, 1)$ and $E(t^2) = (0, 1)$ , since then

\begin{aligned} &E(a + bt + ct^2) \\[0.4em] &\quad = a\begin{bmatrix} 1 \\ 1 \end{bmatrix} + b\begin{bmatrix} 0 \\ 1 \end{bmatrix} + c\begin{bmatrix} 0 \\ 1 \end{bmatrix} \\[0.4em] &\quad = \begin{bmatrix} a \\ a + b + c \end{bmatrix}. \end{aligned}

Two basis vectors may share an image, as $t$ and $t^2$ do here. For a second example, choose $T(1) = 0$ , $T(t) = 1$ and $T(t^2) = 2t$ in $P_2$ . The only linear map from $P_2$ to $P_2$ with these images is $T(a + bt + ct^2) = b + 2ct$ , so $T(2 + 3t - t^2) = 3 - 2t$ . This happens to be the derivative, but the construction uses only the three chosen images.

Matrix of a map in a polynomial basis

Definition Let $T$ be a linear map from $V$ to $W$ , let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be an ordered basis of $V$ , and let $\mathcal{C}$ be an ordered basis of $W$ , where $\dim W = m$ . The matrix of $T$ relative to $\mathcal{B}$ and $\mathcal{C}$ is the $m \times n$ matrix whose $j$ th column is the coordinate column of $T(\mathbf{v}_j)$ in $\mathcal{C}$ ,

\begin{aligned} &[T]_{\mathcal{C} \leftarrow \mathcal{B}} \\[0.4em] &= \begin{bmatrix} [T(\mathbf{v}_1)]_{\mathcal{C}} & \cdots & [T(\mathbf{v}_n)]_{\mathcal{C}} \end{bmatrix}. \end{aligned}

It is the only matrix that satisfies

[T(\mathbf{v})]_{\mathcal{C}} = [T]_{\mathcal{C} \leftarrow \mathcal{B}}\,[\mathbf{v}]_{\mathcal{B}}

for every $\mathbf{v}$ in $V$ . When $V = P_2$ with the basis $(1, t, t^2)$ , the columns record the images of $1$ , $t$ and $t^2$ in output coordinates.

In plain words Push each input basis vector through the map, describe each result in the output basis, and place those descriptions side by side in the order of the input basis. Multiplying by the matrix then does the work of the map on coordinates.

Example For $E(p) = (p(0), p(1))$ , with input basis $(1, t, t^2)$ and the standard basis of $\mathbb{R}^2$ , the columns are $E(1) = (1, 1)$ , $E(t) = (0, 1)$ and $E(t^2) = (0, 1)$ . Calling this matrix $A$ ,

\begin{gathered} A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}, \\[0.4em] A\begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} a \\ a + b + c \end{bmatrix}, \end{gathered}

which matches substituting $0$ and $1$ into $a + bt + ct^2$ . For $p(t) = 2 + 3t - t^2$ , the coordinate column $(2, 3, -1)$ gives $(2, 2 + 3 - 1) = (2, 4)$ , the same as direct substitution.

Kernel and image of an evaluation map

Definition For a linear map $T$ from $V$ to $W$ , the kernel $\ker T$ is the set of all $\mathbf{v}$ in $V$ with $T(\mathbf{v}) = \mathbf{0}$ , and the image $\operatorname{im} T$ is the set of all outputs $T(\mathbf{v})$ . The kernel is a subspace of $V$ and the image is a subspace of $W$ . When $V$ is finite-dimensional, the rank-nullity theorem says

\dim \ker T + \dim \operatorname{im} T = \dim V.

For an evaluation map $E$ on $P_2$ , the kernel consists of the polynomials in $P_2$ that are zero at every sample point, and the image is the set of value lists that some polynomial in $P_2$ attains. If $E(p_0) = \mathbf{y}$ , then the polynomials $p$ with $E(p) = \mathbf{y}$ are exactly those of the form $p_0 + h$ with $h$ in $\ker E$ .

In plain words The kernel holds the changes to a polynomial that the readings cannot see, and the image holds every list of readings that can occur. A kernel polynomial need not be the zero function. It is invisible to these readings, and a reading at any point where it is nonzero detects it.

Example For $E(p) = (p(0), p(1))$ and $p = a + bt + ct^2$ , the kernel requires $a = 0$ and $a + b + c = 0$ , so $b = -c$ and $p = c(t^2 - t)$ . Thus $\ker E = \operatorname{span}\{t^2 - t\}$ and the nullity is $1$ . The polynomial $t^2 - t$ is not the zero function, since its value at $t = \frac{1}{2}$ is $-\frac{1}{4}$ . Every pair $(y_0, y_1)$ is reached, by the polynomial $y_0 + (y_1 - y_0)t$ , so $\operatorname{im} E = \mathbb{R}^2$ and the rank is $2$ . The count $1 + 2 = 3 = \dim P_2$ agrees with rank-nullity. The polynomials with readings $(2, 4)$ are $2 + 2t + c(t^2 - t)$ , and $c = -1$ gives back $2 + 3t - t^2$ . So $E$ is surjective but not injective. Restricted to polynomials of degree at most one it becomes injective, since $a = y_0$ and $b = y_1 - y_0$ are then forced.

Trace of a matrix

Definition The trace of an $n \times n$ matrix $X$ with entries $x_{ij}$ is the sum of its diagonal entries,

\operatorname{tr} X = x_{11} + x_{22} + \cdots + x_{nn}.

The trace map from $M_{n \times n}$ to $\mathbb{R}$ is linear, because the diagonal entries of $X + Y$ are the sums of those of $X$ and $Y$ , and the diagonal entries of $cX$ are $c$ times those of $X$ . On $M_{2 \times 2}$ ,

\operatorname{tr}\begin{bmatrix} a & b \\ c & d \end{bmatrix} = a + d,

so in the ordered basis $(E_{11}, E_{12}, E_{21}, E_{22})$ of $M_{2 \times 2}$ and the basis $(1)$ of $\mathbb{R}$ the trace has the $1 \times 4$ matrix $\begin{bmatrix} 1 & 0 & 0 & 1 \end{bmatrix}$ .

In plain words The trace reads only the diagonal. It is a one-number measurement of a matrix, and every off-diagonal entry is invisible to it.

Example For

X = \begin{bmatrix} 2 & -1 \\ 3 & 4 \end{bmatrix}

the trace is $2 + 4 = 6$ . A matrix in $M_{2 \times 2}$ has trace zero exactly when $d = -a$ , and then

\begin{aligned} \begin{bmatrix} a & b \\ c & -a \end{bmatrix} &= a(E_{11} - E_{22}) \\[0.4em] &\quad + bE_{12} + cE_{21}. \end{aligned}

The matrices $E_{11} - E_{22}$ , $E_{12}$ and $E_{21}$ have trace zero and span the kernel. They are independent, because the $(1,1)$ , $(1,2)$ and $(2,1)$ entries of the combination are $a$ , $b$ and $c$ . So the nullity is $3$ . Every real number $r$ is a trace, for example of $rE_{11}$ , so the image is $\mathbb{R}$ and the rank is $1$ . Again $3 + 1 = 4 = \dim M_{2 \times 2}$ .

Check yourself

For $E(p) = (p(0), p(1))$ on $P_2$ , find the coordinates of $t - t^2$ in the basis $(1, t, t^2)$ and compute $E(t - t^2)$ . Does the result mean that $t - t^2$ is the zero polynomial?

Show the answer

The coordinate column is $(0, 1, -1)$ , and the matrix $A$ gives $(0, 0 + 1 - 1) = (0, 0)$ . So $t - t^2$ lies in $\ker E$ . It is not the zero polynomial, since its coefficients are not all zero, and at $t = \frac{1}{2}$ its value is $\frac{1}{4}$ . The two readings simply cannot tell it apart from $0$ .

Let $F(p) = (p(-1), p(1))$ on $P_2$ . Find the matrix of $F$ in the basis $(1, t, t^2)$ and the standard basis of $\mathbb{R}^2$ , a basis of $\ker F$ , and every $p$ with $F(p) = (2, 6)$ .

Show the answer

For $p = a + bt + ct^2$ the readings are $p(-1) = a - b + c$ and $p(1) = a + b + c$ . The images of $1$ , $t$ and $t^2$ are $(1, 1)$ , $(-1, 1)$ and $(1, 1)$ , so the matrix is

\begin{bmatrix} 1 & -1 & 1 \\ 1 & 1 & 1 \end{bmatrix}.

For the kernel, subtracting the two equations gives $2b = 0$ , so $b = 0$ and $a = -c$ . Every kernel polynomial is $c(t^2 - 1)$ , so $t^2 - 1$ is a basis and the nullity is $1$ . For the target, subtracting gives $2b = 4$ , so $b = 2$ , and adding gives $2a + 2c = 8$ , so $a = 4 - c$ . The solutions are the polynomials

p(t) = 4 + 2t + c(t^2 - 1)

with $c$ any real number. Check that $4 + 2t$ gives $2$ at $-1$ and $6$ at $1$ , and that $t^2 - 1$ is zero at both points.

Let $H(p) = (p(0), p(0))$ , which measures at $0$ twice. Find its matrix in the same bases, its rank, a basis of its kernel, and decide whether some $p$ in $P_2$ has $H(p) = (2, 6)$ .

Show the answer

For $p = a + bt + ct^2$ we get $H(p) = (a, a)$ , so the matrix is

\begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}.

The image is the line of pairs with equal entries, so the rank is $1$ . The kernel is given by $a = 0$ , with basis $(t, t^2)$ , so the nullity is $2$ , and $1 + 2 = 3$ as rank-nullity requires. No polynomial gives $(2, 6)$ , because every output has equal entries. Two readings at the same point carry only one independent piece of information.

Linear Maps on Polynomials and Matrices

Key terms

Evaluation map

Linear map determined by basis images

Matrix of a map in a polynomial basis

Kernel and image of an evaluation map

Trace of a matrix

Check yourself

How this lesson connects

Builds on

Used later in