Unit 2

Linear algebra

Vectors, linear maps and matrices: the language of almost everything.

11 chapters written · 69 definitions · 97 theorems · builds on Unit 0

The story

Linear algebra studies one kind of function, the linear map, which respects addition and scaling. That sounds narrow, but it is the only kind of function we can understand completely, and calculus works by approximating every other function with one.

The unit builds the setting first (2.1 and 2.2: vector spaces, span, independence, basis, dimension), then the maps (2.3 to 2.5: null space, range, rank-nullity, inverses, matrices as maps). With that in place, elimination (2.6) and determinants (2.7) become tools with reasons behind them, not recipes. Eigenvalues (2.8) find the directions a map only stretches.

The last three chapters add length and angle (2.9: inner products and projection) and put everything to work: least squares and regression (2.10), and Markov chains and PageRank (2.11).

Chapters

The theorem chain

Every theorem in the unit, in the order it is proved. Each one is used by the ones after it. The label says whether it is on the 375/376 exams (T), an Apostol extra (A), or beyond both (B).

2.1 Vector spaces and subspaces

Theorem · T Uniqueness of the zero vector A vector space has exactly one zero element.
Theorem · T Uniqueness of negatives Each $x$ has exactly one $y$ with $x + y = O$ , namely $(-1)x$ .
Theorem · T Scaling by zero $0x = O$ for every vector $x$ .
Theorem · T Subspace test A non-empty subset of a vector space is a subspace exactly when it is closed under addition and under scalar multiplication.

2.2 Span, independence, basis, dimension

Theorem · T The span is a subspace For any finite set $S$ in $V$ , the span $L(S)$ is a subspace of $V$ .
Theorem · T More vectors than a spanning set means dependent If $k$ vectors span a space, then any $k + 1$ vectors in that space are linearly dependent.
Theorem · T All bases have the same size If $V$ has a basis with $n$ elements, every basis of $V$ has $n$ elements.
Theorem · T Extending to a basis In an $n$ -dimensional space, any independent set can be extended to a basis, and any $n$ independent vectors already form a basis.
Theorem · T Unique coordinates If $e_1, \dots, e_n$ is a basis, each vector is $\sum c_i e_i$ for exactly one list $(c_1, \dots, c_n)$ .

2.3 Linear maps, null space, range, rank–nullity

Theorem · T Null space and range are subspaces $N(T)$ is a subspace of the domain and $T(V)$ is a subspace of the codomain.
Theorem · T Rank–nullity theorem For a linear map out of a finite-dimensional space, $\dim V = \operatorname{rank} T + \operatorname{nullity} T$ .

2.4 Inverses, one-to-one maps, isomorphism

Theorem · T Linear maps form a vector space The set $L(V, W)$ of all linear maps from $V$ to $W$ is a vector space under pointwise addition and scaling.
Theorem · T Composition of linear maps is linear If $T: U \to V$ and $S: V \to W$ are linear, then $ST: U \to W$ is linear.
Theorem · T Composition is associative For any three functions that can be chained, $R(ST) = (RS)T$ .
Proposition · A Composition distributes over addition $(S + T)R = SR + TR$ and $R(S + T) = RS + RT$ (the second needs $R$ linear); scalars pass through too.
Theorem · T Left inverse exists exactly when one-to-one A function $T$ has a left inverse if and only if different inputs always give different outputs.
Theorem · T A left inverse is unique and two-sided A function has at most one left inverse, and a left inverse is also a right inverse.
Theorem · T Equivalent forms of one-to-one for linear maps For a linear map $T$ , these are equivalent: one-to-one; invertible with a linear inverse; and $N(T) = \{O\}$ .
Theorem · T One-to-one in finite dimension For a linear $T$ on an $n$ -dimensional $V$ , these are equivalent: $T$ is one-to-one; independent sets stay independent; $\dim T(V) = n$ ; bases go to bases.
Theorem · T Inverse of a composition reverses the order If $S$ and $T$ are invertible, so is $ST$ , and $(ST)^{-1} = T^{-1}S^{-1}$ .
Theorem · B Isomorphic is an equivalence relation Every space is isomorphic to itself, if $V \cong W$ then $W \cong V$ , and if $V \cong W$ and $W \cong X$ then $V \cong X$ .
Theorem · B Every n-dimensional space is isomorphic to R^n If $\dim V = n$ and $(e_1, \dots, e_n)$ is an ordered basis, then $x \mapsto (c_1, \dots, c_n)$ , the coordinates of $x$ , is an isomorphism $V \to \mathbb R^n$ .
Theorem · B Same dimension exactly when isomorphic Two finite-dimensional vector spaces are isomorphic if and only if they have the same dimension.
Theorem · A Prescribed values on a basis Given a basis $e_1, \dots, e_n$ of $V$ and ANY vectors $u_1, \dots, u_n$ in $W$ , there is exactly one linear map $T$ with $T(e_k) = u_k$ .
Corollary · A Building a linear map from the images of a basis If $T(e_k) = u_k$ on a basis, then $T$ is onto $W$ exactly when the $u_k$ span $W$ , one-to-one exactly when they are independent, and an isomorphism exactly when they are a basis of $W$ .

2.5 Matrices as maps, multiplication, change of basis

Theorem · A Matrix space has dimension mn The space of $m \times n$ matrices has dimension $mn$ .
Theorem · T Matrix times vector If $x$ has coordinates $x_k$ , then $T(x)$ has coordinates $y_i = \sum_k t_{ik}x_k$ , which is $x_1 \cdot (\text{column }1) + \dots + x_n \cdot (\text{column }n)$ .
Theorem · T Maps and matrices are the same thing For fixed bases, the function $T \mapsto m(T)$ is an isomorphism from $L(V, W)$ onto $\mathbb R^{m \times n}$ .
Theorem · T Matrix of a composition The $(i, j)$ entry of $m(ST)$ is $\sum_{k} s_{ik}t_{kj}$ : row $i$ of $m(S)$ times column $j$ of $m(T)$ .
Theorem · T Matrix multiplication is associative and distributive $A(BC) = (AB)C$ , $(A + B)C = AC + BC$ and $C(A + B) = CA + CB$ whenever the products are defined.
Theorem · T The matrix of an inverse is the inverse of the matrix If $T: V \to V$ is invertible and $A = m(T)$ in one basis, then $A^{-1} = m(T^{-1})$ in the same basis, and $AA^{-1} = A^{-1}A = I$ .
Proposition · A Inverse of a 2 by 2 matrix $\begin{bmatrix}a&b\\c&d\end{bmatrix}$ is invertible exactly when $ad - bc \ne 0$ , and then its inverse is $\frac{1}{ad - bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ .
Theorem · T Transpose of a product $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ .
Theorem · T Coordinates change by C $[x]_{\mathcal E} = C\,[x]_{\mathcal F}$ , and $C$ is invertible with $C^{-1} = m_{\mathcal E \to \mathcal F}(I)$ .
Theorem · T Change of basis rewrites the matrix of a map If $A$ and $B$ are the matrices of $T$ in the old and new bases, then $B = C^{-1}AC$ . Conversely every $C^{-1}AC$ is the matrix of the same map in some basis.
Theorem · T Diagonal form of a linear map For $T: V \to W$ of rank $r$ there are bases of $V$ and $W$ in which the matrix has $1$ s in the first $r$ diagonal places and $0$ everywhere else.

2.6 Systems of equations and elimination

Theorem · T Solutions are a particular solution plus the null space If $x_p$ solves $Ax = b$ , then the solutions are exactly $x_p + y$ with $y$ in the null space of $A$ .
Corollary · T A system has zero, one or infinitely many solutions No solution if $b$ is not in the range of $A$ . Otherwise one solution if the null space is $\{O\}$ , and infinitely many if it is bigger.
Theorem · T Matrix times vector is a combination of the columns $Ax = x_1 a_1 + \dots + x_n a_n$ , so the column space is the range of $x \mapsto Ax$ and the rank of $A$ is its dimension.
Theorem · T Row operations do not change the solutions If $[A' \mid b']$ comes from $[A \mid b]$ by row operations, the two systems have exactly the same solutions.
Theorem · T Every matrix reduces to reduced row echelon form Row operations can turn any matrix into one in reduced row echelon form.
Theorem · T Reading the solutions off the reduced form The system is inconsistent exactly when the last column is a pivot column. Otherwise each pivot variable equals its right side minus a combination of the free variables.
Theorem · T Rank equals the number of pivots If an echelon form of $A$ has $r$ pivots, then rank $A = r$ , nullity $= n - r$ , and the pivot columns of the original $A$ are a basis of the column space.
Theorem · T Row rank equals column rank The row space and the column space of a matrix have the same dimension, the number of pivots. So rank $A$ = rank $A^{\mathsf T}$ .
Theorem · T A left inverse of a square matrix is a full inverse If $A$ and $B$ are $n \times n$ and $BA = I$ , then $AB = I$ too, so $B = A^{-1}$ .
Theorem · T Row operations are multiplication by elementary matrices Doing a row operation to $A$ gives the same result as multiplying $A$ on the left by the elementary matrix of that operation. Elementary matrices are invertible, with elementary inverses.
Theorem · T Computing the inverse by row reducing [A | I] Row reduce $[A \mid I]$ . If the left block becomes $I$ , the right block is $A^{-1}$ . If the left block cannot become $I$ , $A$ has no inverse.
Theorem · B Invertible matrix theorem For an $n \times n$ matrix $A$ , eleven conditions are equivalent: invertible, one-to-one, null space zero, independent columns, rank $n$ , columns span $\mathbb R^n$ , onto, a unique solution for every $b$ , $n$ pivots, product of elementary matrices, invertible transpose.

2.7 Determinants

Lemma · T What the first three axioms force on the rows A function with Axioms 1 to 3 is zero if a row is zero, changes sign when two rows are swapped, is unchanged when a multiple of one row is added to another, and is zero when the rows are dependent.
Theorem · T Axioms 1 to 3 force a multiple of the determinant If $d$ is a determinant function and $F$ satisfies only Axioms 1 to 3, then $F(A) = d(A)\,F(I)$ for every $A$ .
Corollary · T The determinant is unique There is at most one function satisfying all four axioms.
Theorem · T Determinant of a triangular matrix The determinant of a triangular matrix is the product of its diagonal entries.
Theorem · T Determinant by row reduction If row operations turn $A$ into an upper triangular $U$ using $p$ swaps and scalings by $c_1, \dots, c_q$ , then $\det A = (-1)^p(c_1\cdots c_q)^{-1}u_{11}\cdots u_{nn}$ .
Theorem · T A matrix is invertible exactly when its determinant is non-zero For a square matrix, $\det A \ne 0$ if and only if $A$ is invertible, if and only if the rows are independent, if and only if the columns are independent.
Theorem · T Product rule for determinants $\det(AB) = \det A\cdot\det B$ for all $n \times n$ matrices.
Corollary · T Consequences of the product rule $\det(A^{-1}) = 1/\det A$ , $\det(A^k) = (\det A)^k$ , $\det(AB) = \det(BA)$ , and $\det(cA) = c^n\det A$ for an $n \times n$ matrix.
Theorem · T The determinant of the transpose $\det A^{\mathsf T} = \det A$ . So everything true for rows is true for columns.
Theorem · A Determinant of a block-diagonal matrix For square blocks $A$ and $B$ , $\det\begin{bmatrix}A&O\\O&B\end{bmatrix} = \det A\cdot\det B$ .
Theorem · T Expansion by cofactors For any row $k$ : $\det A = \sum_{j=1}^n a_{kj}C_{kj}$ . The same holds along any column.
Theorem · A Cofactor formula for the inverse $A\,(\operatorname{cof}A)^{\mathsf T} = (\det A)\,I$ , so when $\det A \ne 0$ , $A^{-1} = \frac1{\det A}(\operatorname{cof}A)^{\mathsf T}$ .
Theorem · A Cramer's rule is correct If $\det A \ne 0$ then the unique solution of $Ax = b$ is $x_j = \det A_j(b)/\det A$ .
Lemma · B Swapping two values flips the sign of a permutation If $\sigma'$ is $\sigma$ with the values at two positions exchanged, then $\operatorname{sgn}\sigma' = -\operatorname{sgn}\sigma$ .
Theorem · A The permutation formula gives a determinant function $\det A = \sum_\sigma\operatorname{sgn}(\sigma)\,a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}$ satisfies all four axioms. So the determinant exists for every $n$ .

2.8 Eigenvalues and eigenvectors

Fact · T An eigenvector has only one eigenvalue If $T(x) = \lambda x$ and $T(x) = \mu x$ with $x \ne O$ , then $\lambda = \mu$ .
Theorem · T Eigenspaces are subspaces $E(\lambda)$ is a subspace, because it is the null space of the linear map $T - \lambda I$ .
Theorem · T Eigenvectors of distinct eigenvalues are independent Eigenvectors that belong to different eigenvalues are linearly independent.
Theorem · T Distinct eigenvalues give an eigenbasis On an $n$ -dimensional space a linear map has at most $n$ distinct eigenvalues, and if it has $n$ , their eigenvectors are a basis.
Theorem · T Eigenvalues are roots of the characteristic polynomial $\lambda$ is an eigenvalue of $A$ exactly when $\det(\lambda I - A) = 0$ .
Theorem · T Shape of the characteristic polynomial $\det(\lambda I - A) = \lambda^n - (\operatorname{tr} A)\lambda^{n-1} + \dots + (-1)^n\det A$ .
Theorem · T Trace and determinant from the eigenvalues The trace is the sum of the eigenvalues and the determinant is their product, each counted with multiplicity.
Theorem · T Similar matrices share a characteristic polynomial If $B = C^{-1}AC$ then $B$ and $A$ have the same characteristic polynomial, hence the same eigenvalues, trace and determinant.
Theorem · T Diagonal form means an eigenbasis A map has a diagonal matrix in a basis exactly when every vector of that basis is an eigenvector. The diagonal entries are the eigenvalues.
Theorem · T Diagonalization as a factorization If $A$ has $n$ independent eigenvectors, then $A = CDC^{-1}$ , where the columns of $C$ are those eigenvectors and $D$ is diagonal with the matching eigenvalues.
Theorem · T Distinct roots give a diagonalizable matrix If the characteristic polynomial has $n$ different roots, the matrix is diagonalizable.
Theorem · T Geometric multiplicity is at most algebraic multiplicity An eigenvalue never has more independent eigenvectors than its multiplicity as a root: $1 \le g(\lambda_0) \le m(\lambda_0)$ .
Theorem · B Diagonalizable exactly when the eigenspaces fill the space With all roots among the scalars, $A$ is diagonalizable if and only if $g(\lambda) = m(\lambda)$ for every eigenvalue, that is, if and only if the dimensions of the eigenspaces add up to $n$ .

2.9 Inner products, orthogonality, Gram–Schmidt, projection

Theorem · T Cauchy–Schwarz inequality $|(x, y)| \le \lVert x\rVert\,\lVert y\rVert$ , with equality exactly when $x$ and $y$ are linearly dependent.
Theorem · T Properties of the norm $\lVert x\rVert \ge 0$ with equality only for $O$ ; $\lVert cx\rVert = |c|\lVert x\rVert$ ; and the triangle inequality $\lVert x + y\rVert \le \lVert x\rVert + \lVert y\rVert$ .
Theorem · T Orthogonal sets are independent An orthogonal set of non-zero vectors is linearly independent.
Theorem · T Coordinates in an orthogonal basis In an orthogonal basis, the coordinate of $x$ on $e_i$ is $(x, e_i)/(e_i, e_i)$ ; in an orthonormal basis it is $(x, e_i)$ itself.
Theorem · T Gram–Schmidt theorem The $y_m$ are non-zero and orthogonal, and $y_1, \dots, y_m$ span the same space as $x_1, \dots, x_m$ for every $m$ .
Theorem · T The orthogonal complement is a subspace meeting S only at O $S^\perp$ is a subspace, and the only vector in both $S$ and $S^\perp$ is $O$ .
Theorem · T Orthogonal decomposition theorem If $S$ is a finite-dimensional subspace, every $x$ splits uniquely as $x = s + s^\perp$ with $s \in S$ and $s^\perp \in S^\perp$ , and $\lVert x\rVert^2 = \lVert s\rVert^2 + \lVert s^\perp\rVert^2$ .
Theorem · T Best approximation theorem Among all points of $S$ , the projection $s$ is the unique closest point to $x$ : $\lVert x - s\rVert \le \lVert x - t\rVert$ for every $t \in S$ .

2.10 Least squares and regression as projection

Theorem · T Perpendicular error means closest point If $p$ is in a subspace $W$ and $b - p$ is perpendicular to all of $W$ , then $p$ is the closest point of $W$ to $b$ , and no other point of $W$ is as close.
Theorem · B Least squares solutions solve the normal equations $\hat x$ is a least squares solution of $Ax = b$ exactly when $A^{\mathsf T}A\,\hat x = A^{\mathsf T}b$ , which says the residual is perpendicular to every column of $A$ .
Lemma · B A and A-transpose A have the same null space $A^{\mathsf T}Ax = O$ exactly when $Ax = O$ .
Theorem · B Independent columns give a unique least squares solution The columns of $A$ are independent exactly when $A^{\mathsf T}A$ is invertible. Then the unique least squares solution is $\hat x = (A^{\mathsf T}A)^{-1}A^{\mathsf T}b$ .
Theorem · B The projection matrix projects $Pb$ is the closest point of the column space to $b$ , $P^2 = P$ and $P^{\mathsf T} = P$ .
Theorem · B QR from Gram–Schmidt A matrix $A$ with independent columns factors as $A = QR$ : $Q$ has orthonormal columns and $R$ is square, upper triangular and invertible. Then $\hat x$ solves $R\hat x = Q^{\mathsf T}b$ and $P = QQ^{\mathsf T}$ .

2.11 Markov chains and PageRank

Theorem · B A stochastic matrix keeps probability vectors If $P$ is stochastic and $x$ is a probability vector, then $Px$ is a probability vector. Also a product of stochastic matrices is stochastic.
Theorem · B One is always an eigenvalue of a stochastic matrix Every stochastic matrix has eigenvalue 1.
Theorem · B Eigenvalues of a stochastic matrix have size at most one Every eigenvalue $\lambda$ of a stochastic matrix, real or complex, satisfies $|\lambda| \le 1$ .
Lemma · B Other eigenvectors have entries adding to zero If $Pv = \lambda v$ with $\lambda \ne 1$ , the entries of $v$ add to $0$ .
Theorem · B Convergence for a diagonalizable chain with a simple eigenvalue 1 Let $P$ be stochastic and diagonalizable. If $1$ is an eigenvalue with a one-dimensional eigenspace and every other eigenvalue has size less than 1, then $P^kx_0$ approaches the same stationary distribution $\pi$ from every starting probability vector $x_0$ .
Theorem · B Perron–Frobenius theorem for regular chains If some power of the stochastic matrix $P$ has all entries strictly positive (a regular chain), then $1$ is a simple eigenvalue with a positive eigenvector, every other eigenvalue has size less than 1, and $P^kx_0 \to \pi$ for every probability vector $x_0$ .
Theorem · B The Google matrix has a unique stationary distribution For $0 \le d < 1$ , $G$ has exactly one stationary distribution $\pi$ , all its entries are at least $\tfrac{1-d}{n}$ , and from any starting probability vector $\lVert G^kx_0 - \pi \rVert_1 \le 2d^k$ . Every eigenvalue other than $1$ has size at most $d$ .

Terms this unit defines

Scalar Vector space Closed under Zero vector Negative Subspace Linear combination Span Linearly dependent Linearly independent Basis Dimension Coordinates Linear map Null space Range Nullity Rank Composition Inverse Invertible Isomorphism Matrix Matrix of a linear map Matrix multiplication Identity matrix Transpose Change of basis Similar matrices System of linear equations Column space Augmented matrix Row operations Row echelon form Pivot Reduced row echelon form Free variable Row space Left null space Inverse matrix Elementary matrix Determinant function Determinant Minor Cofactor Cofactor matrix Cramer's rule Permutation Eigenvector Eigenvalue Eigenspace Characteristic polynomial Trace Diagonalizable Inner product Norm Orthogonal Orthonormal Gram–Schmidt process Orthogonal complement Projection Least squares solution Normal equations Projection matrix Markov chain Stochastic matrix Stationary distribution Power method Google matrix

Unit review

A mixed set of 12 quick checks drawn at random from the 92 in this unit's chapters. Each one says which chapter it comes from, so a miss tells you what to reread. Press "New set" for another mix.

Where it leads

Units that build on this one: Unit 3, Linear algebra, deeper, Unit 4, Space and closeness, Unit 5, Differential calculus in many variables, Unit 8, Fourier analysis, Unit 10, Probability and statistics, Unit 15, Optimisation, dynamics and computation.