Linear Maps and Matrix Representations

A vector space specifies operations within a collection. A linear map preserves them between spaces. After studying bases, we can now state exactly when a matrix represents the whole map.

Preserving combinations

A map $T:V\to W$ is linear if

$$T(a\mathbf u+b\mathbf v) =aT(\mathbf u)+bT(\mathbf v).$$

It makes combining before processing equivalent to processing before combining. The first chapter’s response model assumes this property.

The two concepts answer different questions. A vector space specifies addition and scaling within a collection of objects. A linear map preserves those operations while mapping one space into another. Merely accepting vector inputs does not make a process linear.

A direct consequence is $T(\mathbf0)=\mathbf0$: apply additivity to $\mathbf0+\mathbf0$ and cancel one term. A fixed nonzero offset therefore prevents linearity. The map $T(\mathbf v)=\mathbf v+\mathbf c$ is instead affine. Subtracting a baseline can make a meaningful difference in modelling.

Linearity must hold for arbitrary inputs

Preserving addition and scaling means

$$T(\mathbf u+\mathbf v)=T(\mathbf u)+T(\mathbf v),\qquad T(a\mathbf v)=aT(\mathbf v).$$

Together they imply preservation of two-term linear combinations. Conversely, choosing unit coefficients or a zero vector in the combination formula recovers these laws. Either form is useful, but its quantifiers cover every input and scalar.

For $T(x,y)=(x+2y,3x-y)$, each output is a fixed linear combination of inputs, so expansion verifies linearity componentwise.

For $T(x,y)=(x,y^2)$, preserving zero is insufficient:

$$T(0,2)=(0,4)\ne2T(0,1)=(0,2).$$

One counterexample disproves linearity; a few successful inputs do not prove it.

An affine rule $T(\mathbf x)=A\mathbf x+\mathbf b$ with nonzero fixed offset fails to preserve zero. Measuring output relative to the baseline $\mathbf b$ leaves the linear rule $\mathbf x\mapsto A\mathbf x$. Subtracting a reference state can therefore change the appropriate mathematical description of a model.

Kernel, image, and solution sets

Define

$$\ker T=\{\mathbf v:T(\mathbf v)=\mathbf0\},\qquad \operatorname{im}T=\{T(\mathbf v):\mathbf v\in V\}.$$

The kernel contains changes invisible at the output; the image contains reachable outputs. Linearity makes both subspaces of their respective spaces.

Why kernel and image are subspaces

For $\mathbf u,\mathbf v\in\ker T$, linearity gives

$$T(a\mathbf u+b\mathbf v)=a\mathbf0+b\mathbf0=\mathbf0.$$

The kernel is closed under combinations and contains zero.

For image vectors $\mathbf y_1=T(\mathbf u)$ and $\mathbf y_2=T(\mathbf v)$,

$$a\mathbf y_1+b\mathbf y_2=T(a\mathbf u+b\mathbf v),$$

which is another output. The kernel belongs to the domain $V$; the image belongs to the codomain $W$. Their ambient spaces may have different dimensions.

Rank-nullity for a finite-dimensional map follows directly from bases. Extend a basis of the kernel to a basis of the domain. Images of the added vectors span the image because kernel terms vanish. Those images are independent: a nontrivial dependence would place a combination of added basis vectors in the kernel, contradicting independence of the extended basis. Hence

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

Injectivity, surjectivity, and invertibility

The map is injective exactly when $\ker T=\{\mathbf0\}$. Injectivity permits only zero to map to zero. Conversely, equal outputs imply $\mathbf u-\mathbf v\in\ker T$, so a trivial kernel forces equal inputs.

Surjectivity means $\operatorname{im}T=W$. Invertibility requires both: every output must be reachable, with exactly one preimage.

When both spaces have the same finite dimension $n$, rank-nullity makes injectivity and surjectivity equivalent. A zero-dimensional kernel gives an $n$-dimensional image, and an image equal to the codomain leaves a zero-dimensional kernel. Different dimensions break this equivalence. For example,

$$J:\mathbb R^2\to\mathbb R^3,\quad J(x,y)=(x,y,0)$$

is injective but not surjective, while

$$R:\mathbb R^3\to\mathbb R^2,\quad R(x,y,z)=(x,y)$$

is surjective but not injective: it discards the entire $z$ direction.

Computing kernel, image, and preimages

Consider

$$\begin{gathered} T:\mathbb R^3\to\mathbb R^2,\\ T(x,y,z)=(x+y,y+z). \end{gathered}$$

Setting the output to zero gives $x=-y,z=-y$, hence

$$\ker T=\operatorname{span}((-1,1,-1)).$$

Every target $(p,q)$ is reached by $(p,0,q)$, so the image is all of $\mathbb R^2$. The map is surjective, but its one-dimensional kernel makes preimages nonunique:

$$T^{-1}(\{(p,q)\}) =\{(p-t,t,q-t):t\in\mathbb R\}.$$

Here $T^{-1}$ denotes a set preimage, not an inverse function. Kernel, image, and preimage identify discarded changes, reachable outputs, and the inputs producing a specified output.

All preimages of one output

If $T(\mathbf v)=\mathbf b$ has a particular solution $\mathbf v_p$, all solutions are exactly

$$\mathbf v_p+\ker T.$$

The difference of any two solutions maps to zero, and adding any kernel element to a particular solution preserves its output. For nonzero $\mathbf b$, this solution set excludes zero and is not a linear subspace.

This is the structure behind the traffic parameterization. Later, homogeneous-plus-particular solutions of circuit differential equations will use the same argument. Nonlinear equations do not automatically admit superposition.

Why a finite-dimensional linear map is determined by a matrix

Let $V$ have ordered basis $\mathcal B=(\mathbf b_1,\ldots,\mathbf b_n)$ and $W$ have ordered basis $\mathcal C=(\mathbf c_1,\ldots,\mathbf c_m)$. Knowing the images of basis vectors determines every output:

$$\mathbf v=\sum_j x_j\mathbf b_j \quad\Longrightarrow\quad T(\mathbf v)=\sum_j x_jT(\mathbf b_j).$$

Put the $\mathcal C$-coordinates of $T(\mathbf b_j)$ in column $j$ of $A$. Then

$$[T(\mathbf v)]_{\mathcal C}=A[\mathbf v]_{\mathcal B}.$$

The left side is the output’s coordinate vector. The matrix itself is not an element of $V$.

The representation is unique: equal matrices give equal images of basis vectors, hence equal images of every input. Conversely, any $m\times n$ matrix defines a linear map through this formula. Thus matrices and linear maps correspond bijectively when both spaces are finite-dimensional and both bases are fixed.

Differentiation can have a matrix representation

On the space $\mathcal P_2$ of polynomials of degree at most two, choose basis $(1,t,t^2)$. Differentiation satisfies

$$D(1)=0,\qquad D(t)=1,\qquad D(t^2)=2t.$$

Collect output coordinates as columns:

$$[D]_{\mathcal B\leftarrow\mathcal B} =\begin{pmatrix}0&1&0\\0&0&2\\0&0&0\end{pmatrix}.$$

The coefficient column $(a,b,c)^{\mathsf T}$ becomes $(b,2c,0)^{\mathsf T}$, representing $(a+bt+ct^2)'=b+2ct$. Cubing the matrix gives zero because three derivatives annihilate every such polynomial.

This uses a finite-dimensional space closed under differentiation. The space of all polynomials is infinite-dimensional, so this fixed-size matrix cannot represent differentiation on the whole space. General function spaces require the same care.

A change of basis changes the matrix, not the map

For simplicity, consider $T:V\to V$. Let $A$ represent it in the old basis, and let columns of $S$ contain the new basis vectors in old coordinates. Then

$$[\mathbf v]_{\mathrm{old}}=S[\mathbf v]_{\mathrm{new}}.$$

Convert the input to old coordinates, apply $A$, then convert the output back:

$$A_{\mathrm{new}}=S^{-1}AS.$$

For $A=\operatorname{diag}(2,1)$ and new basis $(1,1),(1,-1)$,

$$S=\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad A_{\mathrm{new}}=\begin{pmatrix}3/2&1/2\\1/2&3/2\end{pmatrix}.$$

The first column says that $(1,1)$ maps to $(2,1)$, whose new coordinates are $(3/2,1/2)$. The operation still doubles the first old coordinate; only its description changes.

Different bases at the two ends

A general map $T:V\to W$ need not have the same domain and codomain. Suppose its old matrix is $A$. Let $S$ contain new domain basis vectors in old coordinates, and let $R$ contain new codomain basis vectors in old coordinates. Then

$$A_{\mathrm{new}}=R^{-1}AS.$$

The right factor converts input coordinates; the left factor converts outputs back. The formula becomes $S^{-1}AS$ only when the same basis change applies at both ends.

For the identity map on $\mathbb R^2$, use domain basis $(1,1),(1,-1)$ and the standard codomain basis. Its matrix is

$$[I]_{\mathrm{standard}\leftarrow\mathrm{new}} =\begin{pmatrix}1&1\\1&-1\end{pmatrix}.$$

It is not the identity matrix because the coordinate systems differ. Input coordinates $(1,0)$ represent the vector $(1,1)$, whose standard output coordinates are $(1,1)$. The identity map has identity matrix only when both ends use the same basis.

Compositions require matching intermediate coordinates

If $T:U\to V$ has matrix $A$ and $S:V\to W$ has matrix $B$, using the same basis for intermediate space $V$, then $S\circ T$ has matrix $BA$.

If one output uses old coordinates and the next input expects new coordinates, a change-of-basis matrix must be inserted. Matching array dimensions alone does not establish matching coordinate meanings.

Exercises

ExerciseDoes preserving zero guarantee linearity?

Let $T(x,y)=(x,y^2)$. It satisfies $T(0,0)=(0,0)$. Is it linear?

Solution

No. For $\mathbf v=(0,1)$, we have $T(2\mathbf v)=(0,4)$ but $2T(\mathbf v)=(0,2)$. Scaling is not preserved. Mapping zero to zero is necessary for linearity, but not sufficient.

ExerciseMapping a function to a number

For real-valued functions on the reals, define $E(f)=f(0)$. Prove that $E$ is a linear map to $\mathbb R$, and explain why it cannot uniquely recover the original function.

Solution

Pointwise operations give

$$E(af+bg)=a f(0)+b g(0)=aE(f)+bE(g).$$

Thus $E$ is linear. But the zero function and $f(t)=t$ both map to zero, so the map is not injective. Preserving combinations and preserving all information are different requirements.

ExerciseWhat sampling discards

On $\mathcal P_2$, define $E(p)=(p(0),p(1))$. Find a kernel basis and determine whether it is surjective.

Solution

For $p(t)=a+bt+ct^2$, the kernel conditions are $a=0,b+c=0$, so $t(t-1)$ is a basis. Any pair $(u,v)$ is reached by $p(t)=u+(v-u)t$. The map is surjective but not injective.

ExerciseThe order of a basis matters

Swap the first two domain basis vectors while keeping the codomain basis fixed. What happens to the matrix?

Solution

Columns are the images of domain basis vectors, so swap the first two columns only. Output coordinates have not changed. This differs from simultaneously relabelling both ends of a graph adjacency matrix.