Matrices spaces and linear maps

A matrix has two roles. It is a data array on which we perform arithmetic, and it represents a linear transformation after bases have been chosen. Understanding the second role explains why multiplication has its particular formula, why rank measures information, and why changing coordinates does not change the transformation itself.

1 Arithmetic that represents composition

For $A\in\mathbb R^{m\times n}$ and $B\in\mathbb R^{n\times p}$, define $(AB)_{ij}=\sum_{k=1}^n a_{ik}b_{kj}$. Then $(AB)x=A(Bx)$ by rearranging finite sums. Matrix multiplication is associative and distributive but generally not commutative. The identity $I_n$ leaves vectors unchanged. The transpose $A^T$ exchanges row and column indices and satisfies $(AB)^T=B^TA^T$.

For instance, $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ and $B=\begin{pmatrix}2&0\\0&1\end{pmatrix}$ give $AB=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ but $BA=\begin{pmatrix}2&2\\0&1\end{pmatrix}$. Scaling before a shear differs from scaling after it.

Gaussian elimination uses reversible row operations on $[A\mid b]$. Pivot columns determine pivot variables; the remaining variables are free. A row $[0\cdots0\mid c]$, $c\ne0$, proves inconsistency. If no contradictory row appears, free variables may be chosen and pivot variables recovered by back substitution. The same operations on $[A\mid I]$ compute $A^{-1}$ when the left block reduces to $I$.

Example. For

$$A=\begin{pmatrix}1&2&1\\0&1&1\end{pmatrix},\qquad b=\binom43,$$

the equations give $y=3-z$, $x=-2+z$. Thus all solutions are $(-2,3,0)+t(1,-1,1)$. The null direction measures information the two observations cannot recover.

Finite elimination terminates and preserves the solution set

Let $A\in\mathbb R^{m\times n}$, $b\in\mathbb R^m$, with positive finite integers $m,n$. The permitted row operations are an exchange of two distinct rows, multiplication of a row by a nonzero scalar, and addition of a scalar multiple of one row to a different row. Their inverses are respectively the same exchange, multiplication by the reciprocal, and subtraction of that multiple. Applying an operation to the entire augmented array therefore preserves exactly the solutions of $Ax=b$: the new equations are consequences of the old, and its inverse gives the reverse implication. Each operation is also multiplication on the left by the result of applying it to the identity matrix, an invertible elementary matrix.

Scan the coefficient columns from left to right, maintaining the next unused row. If the current column has a nonzero entry in an unused row, exchange that row into the next position, divide by its nonzero pivot, and subtract multiples of it from every other row to clear that column. Advance the unused-row index. If every unused entry in the column is zero, skip the column. Previously chosen pivot columns remain unit columns: the current unused rows have zeros in them, so the new pivot row and every subsequent subtraction preserve those zeros and earlier pivots. There are only $n$ column scans and at most $\min(m,n)$ pivots, each with finitely many row operations. Thus the algorithm terminates. At its end, the nonzero coefficient rows have increasing pivot columns and zeros below and above each pivot; any remaining coefficient row is zero. This proves the reduced echelon form used below, without assuming it will eventually appear.

Classification and the homogeneous freedom

Write $r$ for the number of pivots in the coefficient part. A zero coefficient row with a nonzero transformed right side is the impossible equation $0=c$, so the system has no solution. Otherwise assign arbitrary real values to all $n-r$ nonpivot variables. In each pivot row, its pivot variable equals the transformed right side minus the displayed linear combination of these free variables; no other pivot variable occurs. These formulas both construct a solution and recover every solution. If $r=n$ the solution is unique. If $r<n$, changing a free variable changes the vector, giving infinitely many solutions.

For $Az=0$ the free variables can all be zero, giving the zero solution. If $r<n$, set one free variable to one and the others to zero, and use the pivot formulas. This constructs a nonzero homogeneous solution. If $r=n$, the formulas force every homogeneous variable to zero. For a consistent system, fixing one solution $x_p$, subtraction proves that every solution has the form $x_p+z$ with $Az=0$, and substitution proves the converse.

For square $A$, if every column has a pivot, the coefficient form is $I$. The product $E$ of the finitely many elementary matrices satisfies $EA=I$. Since $E$ is invertible, $A=E^{-1}$ and therefore also $AE=I$: $E$ is a two-sided inverse. If a pivot is missing, the nonzero homogeneous solution constructed above rules out any inverse. This also justifies applying the same row operations to $[A\mid I]$ to obtain $[I\mid A^{-1}]$ in the invertible case.

2 Vector spaces basis and dimension

A real vector space has addition and scalar multiplication satisfying the usual distributive, associative, identity and inverse rules. Examples include $\mathbb R^n$, polynomial spaces $P_d$, and matrix spaces. A subspace is a subset containing zero and closed under linear combinations. A basis is an independent spanning list; its length is the dimension. A point set such as $\{(x,y):x+y=1\}$ is not a subspace because it omits zero.

In $P_2$, the list $(1,t,t^2)$ is a basis. The list $(1,1+t,t+t^2)$ is another: a polynomial $a+bt+ct^2$ has coordinates $(a-b+c,b-c,c)$ in that list. Coordinates depend on the basis even though the polynomial does not.

A map $T:V\to W$ is linear when $T(av+bw)=aT(v)+bT(w)$. Its kernel is $\{v:T(v)=0\}$ and its image is $\{T(v):v\in V\}$. Both are subspaces. Kernel zero is equivalent to injectivity: $T(v)=T(w)$ exactly when $v-w$ is in the kernel.

Finite basis existence and extension, without a counting assumption

Let $V$ be a real vector space supplied with a finite spanning list $t_1,\ldots,t_N$. First prove that every independent list $u_1,\ldots,u_k$ has length at most $N$. After $j$ insertions, maintain a spanning list consisting of $u_1,\ldots,u_j$ and $N-j$ surviving old vectors. Expand $u_{j+1}$ in this list. Some coefficient on a surviving old vector is nonzero; otherwise $u_{j+1}$ would be in the span of the earlier $u_i$, contradicting independence. Solve for that old vector and replace it by $u_{j+1}$. The new list spans the same space and keeps every earlier insertion. If $k>N$, after $N$ steps the first $N$ independent vectors already span $V$, contradicting independence of $u_{N+1}$. This proves the bound, including $N=0$.

Every subspace $W$ has a finite basis. Start with the empty independent list. If its current span is not $W$, choose one vector of $W$ outside that span. A relation with nonzero coefficient on the new vector would express it in the old span, so the enlarged list remains independent. The proved bound permits at most $N$ additions; therefore the process stops with an independent spanning list for $W$. If $W=\{0\}$, it stops immediately with the empty basis. Starting instead with any given independent list in $W$ proves that list extends to a basis of $W$. Only a bounded finite selection is used. Finally, if two bases have sizes $p,q$, use each as the finite spanning list in the bound to obtain $p\le q$ and $q\le p$. Thus basis size, called dimension, is well-defined. This supplies the existence, extension and dimension facts used in rank–nullity.

3 Rank nullity and matrix representation

Let $V$ be finite-dimensional over $\mathbb R$ and let $T:V\to W$ be linear.

A map $T:V\to W$ is linear if $T(\alpha v+\beta u)=\alpha Tv+\beta Tu$. Its kernel and image are subspaces. Choose a basis $k_1,\ldots,k_r$ of $\ker T$ and extend to a basis with $v_1,\ldots,v_s$. Then $Tv_1,\ldots,Tv_s$ form a basis of $\operatorname{im}T$: spanning follows by expanding any input; a dependence among these images places the corresponding input combination in the kernel, and independence of the extended basis makes all coefficients zero. Thus

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

This is rank–nullity. In equal finite dimensions, injectivity and surjectivity are equivalent, but the equivalence can fail in infinite-dimensional spaces.

For differentiation $D:P_2\to P_1$, the kernel consists of constant polynomials and has dimension 1; the image is all of $P_1$ and has dimension 2. Relative to bases $(1,t,t^2)$ and $(1,t)$, its matrix is

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

Each column is the coordinate vector of the image of one domain basis element. This construction, not a memorized array, defines matrix representation.

If $P$ has new basis vectors as columns in old coordinates, then $[v]_{\rm old}=P[v]_{\rm new}$. For an operator $T:V\to V$ with old matrix $A$, its new matrix is $P^{-1}AP$. Multiplying in the wrong order confuses changing input coordinates with applying the transformation.

4 Graded practice

E1 Foundation. Solve $x+y+z=2$, $2x+y+3z=5$. Give a particular solution and a null-space basis.

E2 Representation. For $T:P_2\to P_2$ defined by $T(p)=p+p'$, find its matrix in $(1,t,t^2)$. Is it invertible?

E3 Coordinates. Let $A=\operatorname{diag}(2,3)$ and new basis $u=(1,1)$, $v=(1,-1)$. Compute $P^{-1}AP$ and check its first column directly.

E4 Proof. If $V$ and $W$ have the same finite dimension, prove a linear map $T:V\to W$ is injective if and only if it is surjective.

5 Full solutions

S1. Subtract twice the first equation from the second: $-y+z=1$, so $y=z-1$ and $x=3-2z$. All solutions are $(3,-1,0)+t(-2,1,1)$. The null space is spanned by $(-2,1,1)$.

S2. Images are $1$, $1+t$, and $2t+t^2$. Thus $[T]=\begin{pmatrix}1&1&0\\0&1&2\\0&0&1\end{pmatrix}$. Back substitution solves uniquely for every output, so it is invertible. Its kernel is zero, also proving this by rank-nullity.

S3. $P=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$, $P^{-1}=P/2$, giving $\begin{pmatrix}5/2&-1/2\\-1/2&5/2\end{pmatrix}$. Directly, $T(u)=(2,3)=(5/2)u-(1/2)v$, the first column.

S4. If the shared dimension is $n$, rank-nullity gives $\dim\operatorname{im}T=n-\dim\ker T$. Kernel zero is equivalent to image dimension $n$, and a subspace of $W$ with dimension $n$ is all of $W$. The finite and equal-dimension assumptions are essential.

Summary

Matrix multiplication represents composition. Bases convert abstract vectors and maps into coordinates. Kernels measure lost information, images measure possible outputs, and rank-nullity balances the two. Similar matrices represent the same operator in different bases.