Reference

Glossary

Every technical word in the course and what it means in plain language, with flashcards for practice.

Every technical term in the course, with a plain-language meaning. On every page these words are marked with a dotted underline: hover or tap one to see its meaning. The “Used in” links point to the sections where each term appears.

Flashcards — term ⇄ meaning
Ch 1 · Calculus of Several Variables
TermMeaningUsed in
absolute extremumThe largest or smallest value of $f$ on its whole domain or a given set. A continuous function on a closed bounded set attains both; they occur at interior critical points, at points of non-differentiability, or on the boundary.1.2 4.1
bordered HessianThe Hessian of the Lagrangian $f-\lambda g$ bordered by the gradient of the constraint. For two variables and one constraint: $\det\bar H\gt0$ gives a constrained local maximum, $\det\bar H\lt0$ a constrained local minimum.1.2
centroidThe average position of the points of a region: $\bar x=\frac1{\operatorname{Area}(D)}\iint_Dx\,dA$ and similarly for the other coordinates — the centre of mass when the density is constant.1.3 2.2
critical pointA point where $f$ is differentiable and $\nabla f=0$. Every interior local extremum of a differentiable function is a critical point, but not conversely.1.2 3.3 5.2 5.3
cylindrical coordinatesCoordinates $(r,\theta,z)$ with $x=r\cos\theta$, $y=r\sin\theta$, $z=z$; the volume element is $dV=r\,dr\,d\theta\,dz$.1.3
degenerate critical pointA critical point at which the Hessian is singular ($\det H_f=0$). Unless the Hessian is indefinite (then the point is a saddle), the second derivative test is silent there; the nature of the point must be found from higher-order terms or a direct sign argument.
directional derivativeThe rate of change of $f$ at $a$ in the direction of a unit vector $u$: $D_uf(a)=\lim_{t\to0}\frac{f(a+tu)-f(a)}{t}$. If $f$ is differentiable, $D_uf(a)=\nabla f(a)\cdot u$; a direction given by a non-unit vector must be normalised first.1.1 2.1
Fubini's theoremIf $f$ is integrable on a rectangle and the inner integrals exist (for instance, if $f$ is continuous), the double integral equals either iterated integral; on type I and type II regions it justifies changing the order of integration.1.3 2.2 10.3
Gaussian integral$\int_{-\infty}^\infty e^{-x^2}dx=\sqrt\pi$, proved by squaring it into a double integral over the plane and using polar coordinates; hence $\Gamma(\frac12)=\sqrt\pi$.1.3 10.3
Hessian matrixThe symmetric matrix $H_f=[\partial^2f/\partial x_i\partial x_j]$ of second partial derivatives. At a critical point: positive definite gives a strict local minimum, negative definite a strict local maximum, indefinite a saddle; a singular semidefinite Hessian decides nothing.1.2
homogeneous functionA function with $f(tx)=t^kf(x)$ for all $t\gt0$ (degree $k$). Euler's theorem: then $x\cdot\nabla f=kf$ and, for $C^2$ functions, $\sum x_ix_j\,\partial_i\partial_jf=k(k-1)f$.1.1 6.1 10.1 10.2
implicit function theoremIf $F$ is $C^1$, $F(a,b)=0$ and $F_y(a,b)\ne0$, then near $(a,b)$ the equation $F(x,y)=0$ defines a unique $C^1$ function $y=g(x)$, with $g'=-F_x/F_y$; for systems the condition is a nonzero Jacobian with respect to the unknowns being solved for.1.1 1.2 1.3 2.1
inverse function theoremIf $F$ is $C^1$ near $a$ and $\det J_F(a)\ne0$, then $F$ has a $C^1$ inverse near $F(a)$, with $J_{F^{-1}}(F(x))=J_F(x)^{-1}$. The conclusion is only local.1.1 1.3 5.3 10.1
iterated integralAn integral computed one variable at a time, such as $\int_a^b\left(\int_{g_1(x)}^{g_2(x)}f(x,y)\,dy\right)dx$. For integrable $f$ it equals the double integral (Fubini); for non-integrable $f$ the two orders can give different values.1.3
iterated limitA limit taken one variable at a time, such as $\lim_{x\to a}\lim_{y\to b}f(x,y)$. If the double limit exists and the inner limits exist, the iterated limit equals it; two different iterated limits show that the double limit does not exist.1.1
JacobianFor $f:\mathbb{R}^n\to\mathbb{R}^m$, the $m\times n$ matrix $J_f=[\partial f_i/\partial x_j]$ of first partial derivatives; for $m=n$ also its determinant $\frac{\partial(f_1,\dots,f_n)}{\partial(x_1,\dots,x_n)}$. Jacobians of composite maps multiply.1.1 1.2 1.3 2.2
Lagrange multiplierA number $\lambda$ with $\nabla f(a)=\lambda\nabla g(a)$ at an extremum of $f$ subject to $g=0$ (one for each constraint). It exists when the constraint gradients are linearly independent, and it measures the rate of change of the optimal value as the constraint level changes.1.2 3.3
mixed partial derivativeA second (or higher) partial derivative taken with respect to different variables, such as $f_{xy}=(f_x)_y$. By Schwarz's theorem $f_{xy}=f_{yx}$ when one of them is continuous; without continuity they can differ.1.1 2.1 5.1 6.1
polar coordinatesCoordinates $(r,\theta)$ with $x=r\cos\theta$, $y=r\sin\theta$; the Jacobian is $r$, so $dA=r\,dr\,d\theta$.1.3 2.2 5.1 6.3
saddle pointA critical point that is not a local extremum: every neighbourhood contains points where $f$ is larger and points where $f$ is smaller. An indefinite Hessian (in two variables $f_{xx}f_{yy}-f_{xy}^2\lt0$) gives a saddle point.1.2
spherical coordinatesCoordinates $(\rho,\varphi,\theta)$ with $x=\rho\sin\varphi\cos\theta$, $y=\rho\sin\varphi\sin\theta$, $z=\rho\cos\varphi$, $0\le\varphi\le\pi$ measured from the positive $z$-axis; $dV=\rho^2\sin\varphi\,d\rho\,d\varphi\,d\theta$.1.3 6.3
total derivativeThe linear map $Df(a)$ with $f(a+h)=f(a)+Df(a)h+o(\|h\|)$ — the best linear approximation of $f$ near $a$. Its existence is what 'differentiable' means in several variables; its matrix is the Jacobian matrix.1.1 2.1
type I regionA type I region is $\{a\le x\le b,\ g_1(x)\le y\le g_2(x)\}$ (bounded by vertical strips), a type II region is $\{c\le y\le d,\ h_1(y)\le x\le h_2(y)\}$ (horizontal strips), with continuous boundary functions.1.3 2.2
zero areaA set of zero area can be covered by finitely many rectangles of arbitrarily small total area — finite sets, segments, graphs of continuous functions. Changing a function on such a set does not change its double integral.1.3 2.2
Ch 2 · Vector Calculus
TermMeaningUsed in
conservative fieldA vector field that is the gradient $\nabla f$ of a scalar potential $f$. Equivalently, its line integrals depend only on the end points of the path, and its circulation around every closed path is $0$.2.1
curlFor $\mathbf{F}=(P,Q,R)$, the vector field $\nabla\times\mathbf{F}=(R_y-Q_z,\,P_z-R_x,\,Q_x-P_y)$. Its component along a unit vector $\mathbf{n}$ is the circulation of $\mathbf{F}$ per unit area around small circles normal to $\mathbf{n}$; for a rigid rotation it is twice the angular velocity.2.1 2.2
divergenceFor a vector field $\mathbf{F}=(P,Q,R)$, the scalar field $\nabla\cdot\mathbf{F}=P_x+Q_y+R_z$: the net outflow of $\mathbf{F}$ per unit volume at a point (positive at a source, negative at a sink).2.1 2.2 5.2 6.4
divergence theoremFor a bounded solid $E$ with outward-oriented boundary surface and a $C^1$ field $\mathbf{F}$ near $E$: $\iint_{\partial E}\mathbf{F}\cdot\mathbf{n}\,dS=\iiint_E\nabla\cdot\mathbf{F}\,dV$ (Gauss–Ostrogradsky).2.1 2.2 10.2
fluxThe flux of $\mathbf{F}$ through an oriented surface is $\iint_S\mathbf{F}\cdot\mathbf{n}\,dS$ — for a fluid velocity, the volume crossing $S$ per unit time; across a plane curve, $\int_C\mathbf{F}\cdot\mathbf{n}\,ds$.2.1 2.2 10.1 10.3
gradientFor a scalar field $f$, the vector field $\nabla f=(f_x,f_y,f_z)$. It points in the direction of fastest increase of $f$, its length is that maximum rate, and it is normal to the level sets of $f$ wherever it is nonzero.1.1 1.2 2.1 2.2
Green's theoremFor a plane region $D$ with positively oriented boundary and $C^1$ functions $P,Q$ on a neighbourhood of $D$: $\oint_{\partial D}P\,dx+Q\,dy=\iint_D(Q_x-P_y)\,dA$.2.1 2.2 5.1 6.4
irrotationalA vector field is irrotational (curl-free) on a region if $\nabla\times\mathbf{F}=\mathbf{0}$ there. Every gradient is irrotational; on a simply connected domain every irrotational $C^1$ field is a gradient.2.1 2.2
line integralAn integral along a curve $C$: $\int_Cf\,ds=\int_a^bf(\mathbf{r}(t))|\mathbf{r}'(t)|\,dt$ for a scalar field, or $\int_C\mathbf{F}\cdot d\mathbf{r}=\int_a^b\mathbf{F}(\mathbf{r}(t))\cdot\mathbf{r}'(t)\,dt$ (work, circulation) for a vector field.2.1 2.2 6.3
orientable surfaceA surface that carries a continuous unit normal field $\mathbf{n}$ (a choice of 'side'). Spheres, planes and graphs are orientable; the Möbius strip is not.2.2 11.1
positive orientationThe boundary of a plane region is positively oriented when it is traversed with the region on the left: the outer curve counterclockwise, the curves around holes clockwise.2.2 5.1 5.2
simply connectedA domain in which every closed path can be shrunk continuously to a point without leaving the domain — in the plane, a domain without holes. $\mathbb{R}^3\setminus\{0\}$ is simply connected; $\mathbb{R}^2\setminus\{0\}$ and $\mathbb{R}^3$ minus a line are not.2.1 2.2 5.1 5.3
solenoidalA vector field is solenoidal (divergence-free) on a region if $\nabla\cdot\mathbf{F}=0$ there. Every curl $\nabla\times\mathbf{G}$ is solenoidal.2.1
Stokes' theoremFor an oriented surface $S$ with boundary $\partial S$ (induced orientation, right-hand rule) and a $C^1$ field $\mathbf{F}$: $\oint_{\partial S}\mathbf{F}\cdot d\mathbf{r}=\iint_S(\nabla\times\mathbf{F})\cdot\mathbf{n}\,dS$.2.1 2.2
surface integralAn integral over a surface $S=\mathbf{r}(D)$: $\iint_Sf\,dS=\iint_Df(\mathbf{r})\,|\mathbf{r}_u\times\mathbf{r}_v|\,du\,dv$, where $dS$ is the element of surface area.1.3 2.1 2.2
vector fieldA rule $\mathbf{F}$ that attaches a vector $\mathbf{F}(\mathbf{x})$ to every point $\mathbf{x}$ of a region, such as the velocity of a fluid or a force field; in $\mathbb{R}^3$ it has three component functions, $\mathbf{F}=(P,Q,R)$.2.1 2.2 10.1
Ch 3 · Linear Algebra
TermMeaningUsed in
algebraic multiplicityThe multiplicity $a(\lambda)$ of $\lambda$ as a root of the characteristic polynomial — the total size of the Jordan blocks for $\lambda$. Always $a(\lambda)\ge g(\lambda)$.3.2 3.3
Cauchy–Schwarz inequalityIn any inner product space, $|\langle x,y\rangle|\le\|x\|\,\|y\|$, with equality exactly when $x$ and $y$ are linearly dependent.1.2 2.1 3.3 4.2
Cayley–Hamilton theoremEvery square matrix satisfies its characteristic polynomial: $p_A(A)=0$. Used to express $A^{-1}$ and high powers of $A$ as polynomials of degree $\lt n$ in $A$.3.2 6.4
characteristic polynomial$p_A(x)=\det(xI-A)$, monic of degree $n$: $x^n-(\operatorname{tr}A)x^{n-1}+\cdots+(-1)^n\det A$. Its roots are the eigenvalues; similar matrices have the same one.1.2 3.1 3.2 3.3
congruent matricesSymmetric matrices with $A'=P^{\mathsf T}AP$ for an invertible $P$; they represent the same quadratic form in different coordinates, and over $\mathbb{R}$ they are congruent iff they have the same inertia.3.3
diagonalisableA square matrix $A$ is diagonalisable if $P^{-1}AP$ is diagonal for some invertible $P$ — iff there is a basis of eigenvectors, iff $g(\lambda)=a(\lambda)$ for all eigenvalues (with $p_A$ split), iff the minimal polynomial has distinct linear factors.3.1 3.2 3.3 6.4
dimensionThe number of vectors in any basis of a vector space (all bases have the same size). For a subspace cut out by $k$ independent linear conditions in an $n$-dimensional space, the dimension is $n-k$.1.1 1.2 1.3 2.2
eigenvalueA scalar $\lambda$ with $Av=\lambda v$ for some nonzero vector $v$ (an eigenvector); equivalently a root of the characteristic polynomial $\det(xI-A)$. The eigenvalues add up to the trace and multiply to the determinant.1.2 3.1 3.2 3.3
eigenvectorA nonzero vector $v$ that a linear map only stretches: $Av=\lambda v$. Eigenvectors for distinct eigenvalues are linearly independent; together with $0$, the eigenvectors for $\lambda$ form the eigenspace $N(A-\lambda I)$.1.2 3.2 3.3 4.1
Gaussian binomial coefficientThe number $\binom nk_q$ of $k$-dimensional subspaces of an $n$-dimensional space over $\mathbb{F}_q$: $\prod_{i=0}^{k-1}\frac{q^n-q^i}{q^k-q^i}$.3.1
geometric multiplicityThe dimension $g(\lambda)=n-\operatorname{rank}(A-\lambda I)$ of the eigenspace — the number of independent eigenvectors for $\lambda$, and the number of Jordan blocks for $\lambda$.3.2 6.4
Gram–Schmidt processThe procedure that turns linearly independent vectors $v_1,\dots,v_k$ into orthonormal ones with the same successive spans, by subtracting from each $v_j$ its projections onto the earlier vectors and normalising.3.3 8.3
Hermitian matrixA complex square matrix equal to its conjugate transpose, $A^*=A$; its eigenvalues are real and eigenvectors for distinct eigenvalues are orthogonal. A real Hermitian matrix is a symmetric matrix.3.1 3.2 3.3 8.3
Jordan blockThe $k\times k$ matrix $J_k(\lambda)$ with $\lambda$ on the diagonal and $1$ just above it. Its only eigenvalue is $\lambda$, with a single eigenvector, and its minimal polynomial is $(x-\lambda)^k$.3.1 3.2 6.4 9.1
Jordan canonical formThe block diagonal matrix of Jordan blocks to which a complex square matrix is similar, unique up to the order of blocks. For each $\lambda$, the number of blocks of size $\ge k$ is $\operatorname{rank}(A-\lambda I)^{k-1}-\operatorname{rank}(A-\lambda I)^k$.3.1 3.2 6.4 9.1
linear mapA map $T:V\to W$ between vector spaces with $T(u+v)=Tu+Tv$ and $T(cv)=cTv$. It is determined by its values on a basis, and once bases are fixed it is a matrix whose $j$-th column is the image of the $j$-th basis vector.1.1 1.3 3.1 4.1
minimal polynomialThe monic polynomial of least degree that vanishes at a given object. For a square matrix, $m_A$ is the least-degree monic polynomial with $m_A(A)=0$; it divides every polynomial that annihilates $A$ (in particular $p_A$) and has the same roots as $p_A$. In field theory the same name is used for an algebraic element $\alpha$: the monic polynomial of least degree with root $\alpha$.3.2 7.3
normal matrixA square matrix that commutes with its conjugate transpose, $A^*A=AA^*$. By the spectral theorem, these are exactly the matrices that a unitary matrix diagonalises.3.2 3.3
null spaceThe set $N(A)=\{x:Ax=0\}$ of solutions of the homogeneous system (for a linear map, its kernel). Its dimension is the nullity, $n-\operatorname{rank}A$ for an $m\times n$ matrix.3.1 3.2
positive definite matrixA real symmetric (or Hermitian) matrix with $x^*Ax\gt0$ for every $x\ne0$; equivalently, all eigenvalues are positive, or all leading principal minors are positive (Sylvester's criterion).1.2 1.3 3.3 6.4
quadratic formA homogeneous polynomial of degree two, $q(x)=x^{\mathsf T}Ax$ with $A$ real symmetric; the coefficient of $x_ix_j$ ($i\ne j$) is $2a_{ij}$.1.2 3.2 3.3 6.4
rank–nullity theoremFor a linear map $T$ on a finite-dimensional space $V$: $\operatorname{rank}T+\operatorname{nullity}T=\dim V$, i.e. $\dim\operatorname{im}T+\dim\ker T=\dim V$.3.1
reduced row echelon formThe unique matrix obtained by Gauss–Jordan elimination in which every nonzero row starts with a pivot $1$, each pivot is to the right of the one above and is the only nonzero entry of its column. The number of pivots is the rank.3.1
Rouché–Capelli theoremA linear system $Ax=b$ is consistent iff $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]$; its solutions then form $x_p+N(A)$, with $n-\operatorname{rank}A$ free parameters.3.1
signatureFor a real quadratic form with $n_+$ positive and $n_-$ negative squares in a diagonal form, the number $n_+-n_-$ (some texts call the pair $(n_+,n_-)$ the signature).3.3 9.2
similar matricesSquare matrices $A,B$ with $B=P^{-1}AP$ for an invertible $P$ — the matrices of one operator in two bases. They share rank, trace, determinant, characteristic and minimal polynomials and the Jordan form.3.1 3.2 3.3 9.1
Sylvester's law of inertiaHowever a real quadratic form is reduced to a sum $\sum d_iz_i^2$ by an invertible change of variables, the numbers of positive, negative and zero coefficients are always the same.3.3
transition matrixFor two bases $\mathcal{B},\mathcal{B}'$ of $V$, the invertible matrix $P$ whose columns are the new basis vectors written in the old basis; $[v]_{\mathcal{B}}=P[v]_{\mathcal{B}'}$ and $[T]_{\mathcal{B}'}=P^{-1}[T]_{\mathcal{B}}P$. (In probability the same words mean the matrix of a Markov chain.)3.1
unitary matrixA complex square matrix with $U^*U=I$: its columns are orthonormal, it preserves lengths and inner products, and its eigenvalues have modulus $1$. A real unitary matrix is an orthogonal matrix.3.3
Ch 4 · Real Analysis
TermMeaningUsed in
almost everywhereA property holds almost everywhere (a.e.) if the set of points where it fails is a null set; for example $\mathbf 1_{\mathbb{Q}}=0$ a.e.4.3 6.2 8.1 10.3
Arzelà–Ascoli theoremOn a compact metric space $K$, a family in $C(K)$ has compact closure for the sup metric if and only if it is uniformly bounded and equicontinuous; then every sequence in it has a uniformly convergent subsequence.4.2 6.1 8.4
Bernstein polynomial$B_nf(x)=\sum_{k=0}^nf(k/n)\binom nkx^k(1-x)^{n-k}$, a binomial average of samples of $f$; $B_nf\rightrightarrows f$ for every continuous $f$ on $[0,1]$.4.2
Cauchy sequenceA sequence whose terms eventually stay arbitrarily close to each other: for every $\varepsilon\gt0$ there is $N$ with $d(x_m,x_n)\lt\varepsilon$ for all $m,n\ge N$.4.1 8.1 8.2
complete metric spaceA metric space in which every Cauchy sequence converges to a point of the space, e.g. $\mathbb{R}^n$ and $(C[a,b],d_\infty)$, but not $\mathbb{Q}$, $(0,1)$ or $(C[0,1],d_1)$.4.1 8.2
contraction mapping principleA map $T$ with $d(Tx,Ty)\le k\,d(x,y)$, $k\lt1$, on a nonempty complete metric space has exactly one fixed point, and the iterates $T^nx_0$ converge to it from every starting point.1.1 4.1 6.1 9.1
Dini's theoremA monotone sequence of continuous functions on a compact set converging pointwise to a continuous limit converges uniformly.4.2
dominated convergence theoremIf $f_n\to f$ a.e. and $|f_n|\le g$ for one integrable $g$, then $f$ is integrable and $\int|f_n-f|\to0$, so $\int f_n\to\int f$.4.3 10.3
equicontinuousA family of functions for which one $\delta$ serves every member: $|f(x)-f(y)|\lt\varepsilon$ for all $f$ in the family whenever $d(x,y)\lt\delta$. A common Lipschitz constant is the usual test.4.2 8.4
Fatou's lemmaFor non-negative measurable $f_n$, $\int\liminf f_n\le\liminf\int f_n$; the inequality may be strict (mass can escape).4.3
Heine–Borel theoremA subset of $\mathbb{R}^n$ is compact if and only if it is closed and bounded. It fails in infinite-dimensional spaces such as $\ell^2$ and $C[0,1]$.1.2 4.1 4.3 8.4
Lebesgue measurable setA set $E$ that splits every set additively: $m^*(A)=m^*(A\cap E)+m^*(A\setminus E)$ for all $A$. Measurable sets form a σ-algebra containing all Borel sets and all null sets, and on it Lebesgue measure $m$ is countably additive.4.3
Lebesgue numberFor an open cover of a compact metric space, a number $\delta\gt0$ such that every ball of radius $\delta$ lies inside a single member of the cover.4.1
Lebesgue outer measureFor any $A\subseteq\mathbb{R}$, $m^*(A)$ is the infimum of the total lengths $\sum\ell(I_k)$ of countable covers of $A$ by open intervals. It is defined for every set, monotone and countably subadditive, but not additive on all sets.4.3
measurable functionA function $f$ on a measurable set $E$ such that $\{x:f(x)\gt a\}$ is measurable for every real $a$. Sums, products, suprema and pointwise limits of measurable functions are measurable.4.3 8.1
metric spaceA set $X$ with a distance $d(x,y)\ge0$ that is zero only when $x=y$, symmetric, and satisfies the triangle inequality $d(x,z)\le d(x,y)+d(y,z)$.4.1 4.2 8.1 8.2
monotone convergence theoremIf $0\le f_1\le f_2\le\cdots$ are measurable and $f_n\to f$ a.e., then $\int f_n\to\int f$ (the value may be $\infty$).4.3 8.1
null setA set of (outer) measure $0$: it can be covered by intervals of arbitrarily small total length. Countable sets are null, but so is the uncountable Cantor set.4.3 8.1 8.2
path-connectedA space in which any two points can be joined by a continuous path $\gamma:[0,1]\to X$. Path-connected spaces are connected; the topologist's sine curve shows the converse fails.2.1 4.1 11.2
pointwise convergence$f_n\to f$ pointwise on $D$ if $f_n(x)\to f(x)$ for each $x\in D$ separately; the speed may depend on $x$, and continuity, integrals and derivatives can be lost in the limit.4.2 4.3 8.2 10.2
radius of convergenceFor a power series $\sum a_n(x-c)^n$ (real or complex): the number $R=1/\limsup|a_n|^{1/n}\in[0,\infty]$ such that the series converges absolutely for $|x-c|\lt R$ and diverges for $|x-c|\gt R$; on the boundary anything can happen. In the complex plane the disc of convergence reaches out to the nearest singularity of the sum (§5.2).4.2 5.2 6.3 8.4
sequentially compactA set in which every sequence has a subsequence converging to a point of the set; in metric spaces this is equivalent to compactness.4.1
simple functionA measurable function with finitely many values, $\varphi=\sum a_i\mathbf 1_{E_i}$; its integral is $\sum a_i\,m(E_i)$. Every non-negative measurable function is an increasing limit of simple functions.4.3
topologist's sine curveThe graph of $\sin(1/x)$ for $0\lt x\le1$ together with the segment $\{0\}\times[-1,1]$: connected but not path-connected.4.1 11.2
totally boundedA set that can be covered by finitely many balls of radius $\varepsilon$ for every $\varepsilon\gt0$. A metric space is compact exactly when it is complete and totally bounded.4.1 4.2
uniform convergence$f_n\rightrightarrows f$ on $D$ if $\sup_{x\in D}|f_n(x)-f(x)|\to0$: one $N$ works for all $x$. Uniform limits of continuous functions are continuous, and integrals pass to the limit.4.1 4.2 4.3 5.2
Weierstrass approximation theoremEvery continuous function on a compact interval $[a,b]$ is a uniform limit of polynomials; Stone–Weierstrass extends this to algebras of functions on compact spaces.4.2 6.2 8.3 11.2
Weierstrass M-testIf $|u_n(x)|\le M_n$ on $D$ and $\sum M_n\lt\infty$, then $\sum u_n$ converges absolutely and uniformly on $D$.4.2 5.2 6.1 10.2
σ-algebraA family of sets containing $\varnothing$ and closed under complements and countable unions (hence countable intersections). The Borel σ-algebra is the smallest one containing the open sets.4.3
Ch 5 · Complex Analysis
TermMeaningUsed in
analytic functionA function that is complex differentiable at every point of an open set. Analytic at a point means analytic on some disc about it. Analytic functions are infinitely differentiable and equal their Taylor series locally.5.1 5.2 5.3 6.3
argument principleFor $f$ meromorphic inside and on a simple closed contour, with no zeros or poles on it: $\frac1{2\pi i}\oint\frac{f'}{f}dz=Z-P$, the winding number of the image curve about $0$.5.2
Cauchy's integral formulaFor $f$ analytic on and inside a positively oriented simple closed contour $\gamma$ and $a$ inside: $f^{(n)}(a)=\frac{n!}{2\pi i}\oint_\gamma\frac{f(z)}{(z-a)^{n+1}}dz$.5.1 5.2 10.2
Cauchy–Riemann equationsThe equations $u_x=v_y$, $u_y=-v_x$ for $f=u+iv$. They hold wherever $f$ is complex differentiable; together with real differentiability of $u$ and $v$ (e.g. continuous partials) they are also sufficient.5.1 5.3
Cayley transformThe Möbius map $z\mapsto\frac{z-i}{z+i}$, a conformal map of the upper half-plane onto the unit disc sending $i$ to $0$ and the real line onto the unit circle.3.3 5.3
conformal mapA bijective analytic map of one domain onto another (its inverse is then analytic). An analytic map is conformal at a point — it preserves the size and orientation of angles — wherever its derivative is nonzero.5.1 5.3
contour integral$\int_\gamma f(z)\,dz=\int_\alpha^\beta f(\gamma(t))\gamma'(t)\,dt$ along a piecewise smooth path $\gamma$; bounded by $M\cdot L(\gamma)$ when $|f|\le M$ on $\gamma$ (the ML-inequality).5.1 5.2
cross-ratioFor distinct $z_1,z_2,z_3$, $(z,z_1,z_2,z_3)=\frac{(z-z_1)(z_2-z_3)}{(z-z_3)(z_2-z_1)}$: the Möbius map sending $z_1,z_2,z_3$ to $0,1,\infty$. It is invariant under Möbius maps, and four points are concyclic iff their cross-ratio is real.5.3
entire functionA function analytic on the whole complex plane, such as a polynomial, $e^z$, $\sin z$ or $\cos z$.5.1 5.2 5.3 8.4
essential singularityAn isolated singularity whose Laurent series has infinitely many negative powers, such as $0$ for $e^{1/z}$. Near it $f$ comes arbitrarily close to every complex value (Casorati–Weierstrass).5.2 5.3
generalised circleA circle in the plane, or a straight line together with the point $\infty$. Möbius transformations map generalised circles onto generalised circles; the image is a line exactly when the curve passes through the pole.5.3
harmonic conjugateA real function $v$ such that $u+iv$ is analytic. On a simply connected domain every harmonic $u$ has one, unique up to an additive constant.5.1 5.3
harmonic functionA real $C^2$ function satisfying Laplace's equation $u_{xx}+u_{yy}=0$. Real and imaginary parts of analytic functions are harmonic.5.1 5.3 10.2
identity theoremTwo analytic functions on a domain that agree on a set with a limit point in the domain agree everywhere; zeros of a nonzero analytic function are isolated.5.1 5.2
Joukowski mapThe map $J(z)=\frac12\left(z+\frac1z\right)$. It maps the punctured unit disc, and also the exterior of the unit circle, conformally onto the plane minus the segment $[-1,1]$, and circles $|z|=r$ onto ellipses with foci $\pm1$.5.1 5.3
Laurent seriesAn expansion $\sum_{n=-\infty}^\infty c_n(z-a)^n$ of a function analytic on an annulus about $a$; different annuli give different series. The negative powers form the principal part.5.1 5.2 8.4
Liouville's theoremA bounded entire function is constant; more generally, an entire function with $|f(z)|\le A+B|z|^k$ is a polynomial of degree at most $k$.5.1 5.3 7.3 8.4
maximum modulus principleA nonconstant analytic function on a domain has no local maximum of $|f|$; on a bounded domain, with $f$ continuous up to the boundary, $\max|f|$ is attained on the boundary.5.1 5.3
meromorphic functionA function analytic on an open set except at isolated poles, such as a rational function or $\tan z$.5.2 5.3
Morera's theoremA continuous function whose integral round the boundary of every triangle in a domain is zero is analytic there — the converse of Cauchy's theorem.5.1 5.2
Möbius transformationA map $z\mapsto\frac{az+b}{cz+d}$ of the extended plane with $ad-bc\ne0$. Möbius transformations form a group, send generalised circles to generalised circles, and are determined by the images of three points.5.3
poleAn isolated singularity where the Laurent series has finitely many (and at least one) negative powers; the highest negative power is its order. Equivalently $|f(z)|\to\infty$ at the point.5.2 6.3
removable singularityAn isolated singularity with no negative powers in the Laurent series; equivalently $f$ is bounded near the point, and $f$ extends analytically to it.5.2 5.3
residueThe coefficient $c_{-1}$ of $\frac1{z-a}$ in the Laurent series of $f$ on a punctured disc about $a$; equal to $\frac{1}{2\pi i}\oint f\,dz$ round a small circle about $a$.5.1 5.2 6.2 7.1
Riemann mapping theoremEvery simply connected domain other than $\mathbb{C}$ itself is conformally equivalent to the unit disc; the map is unique once one point is sent to $0$ with positive derivative there.5.3
Rouché's theoremIf $|g|\lt|f|$ on a simple closed contour and both are analytic on and inside it, then $f$ and $f+g$ have the same number of zeros inside, counted with multiplicity.5.2
Schwarz lemmaIf $f$ is analytic on the unit disc with $|f|\le1$ and $f(0)=0$, then $|f(z)|\le|z|$ and $|f'(0)|\le1$; equality at one point $z\ne0$, or $|f'(0)|=1$, forces $f(z)=e^{i\theta}z$.5.1 5.3
Schwarz–Pick lemmaThe invariant form of the Schwarz lemma: an analytic $f:\mathbb{D}\to\mathbb{D}$ does not increase the pseudo-hyperbolic distance $\left|\frac{z-w}{1-\bar wz}\right|$, and $|f'(z)|\le\frac{1-|f(z)|^2}{1-|z|^2}$, with equality only for automorphisms of the disc.5.3
symmetric pointsPoints $z,z^*$ that are mirror images in a line, or inverse points $z^*=a+\frac{R^2}{\overline{z-a}}$ for the circle $|z-a|=R$ (for the unit circle, $z^*=1/\bar z$). Möbius maps carry symmetric points to symmetric points.5.3
Ch 6 · Ordinary Differential Equations
TermMeaningUsed in
Abel's formulaFor solutions of $y^{(n)}+p_{n-1}y^{(n-1)}+\dots+p_0y=0$: $W(x)=W(x_0)\exp\left(-\int_{x_0}^x p_{n-1}\right)$.6.1 6.3
asymptotically stableAn equilibrium is asymptotically stable if it is stable (nearby solutions stay nearby) and nearby solutions also tend to it as $t\to\infty$. For $x'=Ax$: all eigenvalues have negative real part.6.4
Bernoulli equationAn equation $y'+P(x)y=Q(x)y^n$ with $n\ne0,1$; the substitution $v=y^{1-n}$ makes it linear.6.1
Bessel function$J_\nu(x)=\sum_m\frac{(-1)^m}{m!\,\Gamma(m+\nu+1)}(x/2)^{2m+\nu}$, a solution of $x^2y''+xy'+(x^2-\nu^2)y=0$. It oscillates with infinitely many simple zeros whose spacing tends to $\pi$; $J_{1/2}=\sqrt{2/(\pi x)}\sin x$.6.2 6.3
Cauchy–Euler equationAn equation $x^ny^{(n)}+a_{n-1}x^{n-1}y^{(n-1)}+\dots+a_0y=f(x)$ with constant $a_k$; the substitution $x=e^t$ turns it into a constant-coefficient equation, and $y=x^r$ solves the homogeneous one when $r$ is a root of the indicial equation.6.1 6.3 10.2
convolution$(f*g)(t)=\int_0^tf(\tau)g(t-\tau)\,d\tau$. The convolution theorem says $\mathcal{L}\{f*g\}=F\,G$.6.2 10.3
Dirac deltaThe idealised unit impulse $\delta(t-a)$: the limit of pulses of area $1$ concentrated near $t=a$. Not a function; it is used through $\int g(t)\delta(t-a)\,dt=g(a)$ and $\mathcal{L}\{\delta(t-a)\}=e^{-as}$.6.2
exact equationAn equation $M\,dx+N\,dy=0$ that is the differential $dF$ of a function $F$ (a potential); its solutions are the level curves $F(x,y)=c$. On a rectangle it is exact exactly when $M_y=N_x$.6.1
exponential order$f$ is of exponential order $\alpha$ if $|f(t)|\le Ke^{\alpha t}$ for all large $t$. Together with piecewise continuity it guarantees that $\mathcal{L}\{f\}(s)$ exists for $s\gt\alpha$.6.2
Frobenius methodSeeking a solution $x^r\sum a_kx^k$ ($a_0\ne0$) near a regular singular point. It gives one solution always and a second one unless the exponents are equal or differ by an integer, when a $\log x$ term may be needed.6.3
fundamental matrixAn $n\times n$ matrix whose columns are $n$ linearly independent solutions of $x'=A(t)x$; every solution is $\Phi(t)c$. For constant $A$, $e^{tA}$ is the one equal to $I$ at $t=0$.6.4
Hartman–Grobman theoremNear a hyperbolic equilibrium, the orbits of $x'=f(x)$ are carried onto those of the linearisation $u'=Df(x^*)u$ by a homeomorphism preserving time direction. It fails at centres and zero eigenvalues.6.4
hyperbolic equilibriumAn equilibrium where no eigenvalue of the Jacobian has zero real part. There the linearisation decides stability and, by Hartman–Grobman, the local phase portrait.6.4
impulse response$h=\mathcal{L}^{-1}\{H\}$, the response of a linear system with zero initial data to a unit impulse $\delta(t)$; the response to any input $f$ is $h*f$.6.2
indicial equationAt a regular singular point $0$, the quadratic $r(r-1)+p_0r+q_0=0$ with $p_0=\lim xP$ and $q_0=\lim x^2Q$. Its roots (the exponents) are the possible leading powers $x^r$ of Frobenius solutions.6.1 6.3
integrating factorA nowhere-zero function $\mu$ such that $\mu M\,dx+\mu N\,dy=0$ is exact. For $y'+P(x)y=Q(x)$ it is $\mu=e^{\int P\,dx}$.6.1
Laplace transform$F(s)=\mathcal{L}\{f\}(s)=\int_0^\infty e^{-st}f(t)\,dt$. It turns differentiation into multiplication by $s$ (with initial values), delays into factors $e^{-as}$ and convolutions into products.6.2 6.4 10.3
Legendre polynomialThe polynomial solution $P_n$ of $(1-x^2)y''-2xy'+n(n+1)y=0$ with $P_n(1)=1$; $P_n=\frac{1}{2^nn!}\frac{d^n}{dx^n}(x^2-1)^n$, and $\int_{-1}^1P_mP_n\,dx=\frac{2}{2n+1}\delta_{mn}$.6.3 8.3
limit cycleAn isolated periodic orbit of a planar system — a self-sustained oscillation of fixed amplitude, e.g. $r=1$ for $r'=r(1-r^2)$, $\theta'=1$. Excluded by the Bendixson–Dulac criterion, found with the Poincaré–Bendixson theorem.6.4
Lipschitz condition$|f(x,y_1)-f(x,y_2)|\le L|y_1-y_2|$ for all relevant points: $f$ changes at most linearly in $y$. It holds when $|\partial f/\partial y|\le L$ on a rectangle or strip, and it is the hypothesis that gives uniqueness.4.1 4.2 6.1 9.3
Lyapunov functionA $C^1$ function $V$, positive definite near an equilibrium, whose orbital derivative $\dot V=\nabla V\cdot f$ is $\le0$. It proves stability; if $\dot V$ is negative definite, asymptotic stability — without solving the system.6.4
matrix exponential$e^{M}=\sum_{k\ge0}M^k/k!$. The matrix $e^{tA}$ solves $\Phi'=A\Phi$, $\Phi(0)=I$, so $x(t)=e^{tA}x_0$; $e^{A+B}=e^Ae^B$ when $AB=BA$, and $\det e^{tA}=e^{t\operatorname{tr}A}$.6.4
ordinary pointA point $x_0$ where the coefficients $P,Q$ of $y''+Py'+Qy=0$ are analytic. There every solution is a power series in $x-x_0$, converging at least up to the nearest (possibly complex) singular point.6.3
phase portraitThe picture of the orbits of an autonomous system $x'=f(x)$ in the state space, with arrows for the direction of motion; equilibria and their type (node, saddle, spiral, centre) organise it.6.4
Picard iteratesThe functions $\varphi_0\equiv y_0$, $\varphi_{n+1}(x)=y_0+\int_{x_0}^x f(t,\varphi_n(t))\,dt$, which converge uniformly to the solution of $y'=f(x,y)$, $y(x_0)=y_0$ under the Picard–Lindelöf hypotheses.4.1 4.2 6.1 8.2
Picard–Lindelöf theoremIf $f$ is continuous and Lipschitz in $y$ on $|x-x_0|\le a$, $|y-y_0|\le b$, the IVP $y'=f(x,y)$, $y(x_0)=y_0$ has exactly one solution on $|x-x_0|\le\min(a,b/M)$, $M=\max|f|$.4.1 6.1 9.3 10.1
regular singular pointA singular point $x_0$ of $y''+Py'+Qy=0$ at which $(x-x_0)P$ and $(x-x_0)^2Q$ are analytic, i.e. $P$ has at worst a simple pole and $Q$ at worst a double pole. The Frobenius method applies there.6.3
Rodrigues' formulaThe closed form $P_n(x)=\frac{1}{2^nn!}\frac{d^n}{dx^n}(x^2-1)^n$ of the Legendre polynomials; integrating by parts with it gives orthogonality and the norm $\frac{2}{2n+1}$.6.3
Sturm–Liouville problemAn eigenvalue problem $(py')'+qy+\lambda ry=0$ on $[a,b]$ with $p,r\gt0$ and separated boundary conditions. Its eigenvalues are real, simple and increase to $\infty$; eigenfunctions are orthogonal with weight $r$, and the $n$-th has $n-1$ interior zeros.6.3 8.4 10.2
transfer functionFor $ay''+by'+cy=f$ it is $H(s)=1/(as^2+bs+c)$: the ratio $Y/F$ of output to input transforms when the initial data are zero.5.2 6.2
unit step function$u(t-a)$, equal to $0$ for $t\lt a$ and $1$ for $t\ge a$; it switches a signal on at time $a$, and $\mathcal{L}\{f(t-a)u(t-a)\}=e^{-as}F(s)$.6.2 10.3
variation of parametersA method for a particular solution of a linear equation in normal form: $y_p=u_1y_1+u_2y_2$ with $u_1'=-y_2f/W$, $u_2'=y_1f/W$, where $y_1,y_2$ is a fundamental set.6.1 6.2 6.3 10.3
WronskianThe determinant of the matrix whose rows are $y_1,\dots,y_n$ and their first $n-1$ derivatives. For solutions of one normal linear equation it is either never zero (independent solutions) or identically zero (dependent).6.1 6.3 8.4
Ch 7 · Algebra
TermMeaningUsed in
algebraic extensionAn element is algebraic over $F$ if it is a root of a nonzero polynomial with coefficients in $F$; an extension is algebraic if all its elements are. Finite extensions are algebraic, but not conversely: the algebraic numbers have infinite degree over $\mathbb{Q}$.7.3
algebraically closed fieldA field in which every nonconstant polynomial has a root, so every polynomial splits into linear factors; examples are $\mathbb{C}$ and the field $\overline{\mathbb{Q}}$ of algebraic numbers. Such fields are infinite. An algebraic closure of $F$ is an algebraic extension of $F$ that is algebraically closed.7.3
automorphismAn isomorphism of a group (or ring) onto itself. The automorphisms of $G$ form a group $\operatorname{Aut}(G)$; for example $\operatorname{Aut}(\mathbb{Z}_n)\cong U(n)$ has order $\varphi(n)$.5.3 7.1 7.3
centraliserThe centraliser of $a$ in $G$ is the subgroup $C(a)=\{g\in G:ga=ag\}$. The size of the conjugacy class of $a$ is $[G:C(a)]$.7.1
class equation$|G|=|Z(G)|+\sum[G:C(x_i)]$, summing over representatives $x_i$ of the conjugacy classes with more than one element; each term is a divisor of $|G|$.7.1
cyclic groupA group generated by a single element $g$: every element is a power $g^k$. A finite cyclic group of order $n$ is isomorphic to $\mathbb{Z}_n$ and has exactly one subgroup of each order dividing $n$.7.1 7.2 7.3
Eisenstein's criterionIf a prime $p$ divides every coefficient of $f\in\mathbb{Z}[x]$ except the leading one, and $p^2$ does not divide the constant term, then $f$ is irreducible over $\mathbb{Q}$.7.2
Euclidean domainAn integral domain with a function $\delta$ allowing division with remainder, $a=qb+r$ with $r=0$ or $\delta(r)\lt\delta(b)$: $\mathbb{Z}$, $F[x]$, $\mathbb{Z}[i]$. Every Euclidean domain is a PID.7.2 7.3
field extensionA pair of fields $F\subseteq K$ (written $K/F$). Then $K$ is a vector space over $F$, and its dimension $[K:F]$ is the degree of the extension; for example $[\mathbb{C}:\mathbb{R}]=2$ and $[\mathbb{R}:\mathbb{Q}]=\infty$.7.3
finite fieldA field with finitely many elements. It has $p^n$ elements for a prime $p$; for each prime power $q$ there is exactly one up to isomorphism, $\mathbb{F}_q$, the splitting field of $x^q-x$ over $\mathbb{F}_p$. Its multiplicative group is cyclic of order $q-1$.3.1 7.2 7.3
Frobenius automorphismThe map $a\mapsto a^p$ on a field of characteristic $p$; it respects sums because $(a+b)^p=a^p+b^p$. On $\mathbb{F}_{p^n}$ it is an automorphism of order $n$ that generates the whole automorphism group and fixes exactly $\mathbb{F}_p$.7.3
group actionA rule $(g,x)\mapsto g\cdot x$ by which a group $G$ permutes a set $X$, with $e\cdot x=x$ and $g\cdot(h\cdot x)=(gh)\cdot x$; equivalently a homomorphism $G\to\operatorname{Sym}(X)$.7.1
integral domainA commutative ring with $1\ne0$ and no zero divisors, such as $\mathbb{Z}$, $\mathbb{Z}[i]$ or $F[x]$. Cancellation holds, and a finite integral domain is a field.7.2 7.3
Lagrange's theoremFor a subgroup $H$ of a finite group $G$, $|G|=[G:H]\,|H|$; so the order of a subgroup, and of an element, divides $|G|$. Its converse is false ($A_4$ has no subgroup of order $6$).1.2 7.1 10.1
maximal idealA proper ideal $M$ with no ideal strictly between $M$ and $R$; equivalently $R/M$ is a field. Every maximal ideal is prime.7.2
normal subgroupA subgroup $N$ with $gNg^{-1}=N$ for every $g\in G$ (left and right cosets agree). Exactly the subgroups that are kernels of homomorphisms; they are the ones that can be divided out to form $G/N$.7.1
orbit–stabiliser theoremFor a finite group $G$ acting on a set, the orbit of $x$ has $[G:G_x]=|G|/|G_x|$ elements, where $G_x$ is the stabiliser of $x$.7.1
prime idealA proper ideal $P$ such that $ab\in P$ implies $a\in P$ or $b\in P$; equivalently $R/P$ is an integral domain.7.2
prime subfieldThe smallest subfield of a field $F$, the intersection of all its subfields. It is $\mathbb{Q}$ when the characteristic is $0$ and $\mathbb{F}_p$ when the characteristic is $p$.7.3
primitive elementIn a finite field $\mathbb{F}_q$, a generator of the cyclic group $\mathbb{F}_q^\times$, i.e. an element of order $q-1$; there are $\varphi(q-1)$ of them. (More generally, an element $\alpha$ with $K=F(\alpha)$ is called a primitive element of the extension $K/F$.)7.3
primitive polynomialA polynomial in $\mathbb{Z}[x]$ (or $R[x]$, $R$ a UFD) whose coefficients have no common prime factor. By Gauss's lemma a product of primitive polynomials is primitive.7.2 7.3
principal ideal domainAn integral domain in which every ideal is generated by one element. In a PID irreducible elements are prime and nonzero prime ideals are maximal; every PID is a UFD.7.2 7.3
quotient groupFor a normal subgroup $N$ of $G$, the set $G/N$ of cosets $aN$ with product $(aN)(bN)=abN$; its order is the index $[G:N]$.7.1
quotient ringFor an ideal $I$ of $R$, the ring $R/I$ of cosets $a+I$ with $(a+I)(b+I)=ab+I$; e.g. $\mathbb{Z}[x]/\langle x^2+1\rangle\cong\mathbb{Z}[i]$.7.2 7.3
splitting fieldThe smallest extension of $F$ over which a polynomial $f$ factors into linear factors — the field generated over $F$ by all roots of $f$. It exists, is unique up to isomorphism, and has degree at most $(\deg f)!$; e.g. $x^3-2$ has splitting field $\mathbb{Q}(\sqrt[3]2,\omega)$ of degree $6$.7.3
Sylow subgroupIf $|G|=p^am$ with $p$ prime and $p\nmid m$, a Sylow $p$-subgroup is a subgroup of order $p^a$. They exist, are all conjugate, and their number $n_p$ divides $m$ and is $\equiv1\pmod p$.7.1
tower lawFor fields $F\subseteq K\subseteq L$: $[L:F]=[L:K]\,[K:F]$. Consequently the degree of every element and of every intermediate field divides the degree of a finite extension.7.3
transcendental numberA complex number (or element of an extension) that is not a root of any nonzero polynomial with rational (resp. base-field) coefficients, such as $e$ and $\pi$. If $\alpha$ is transcendental over $F$, then $F(\alpha)$ is isomorphic to the field of rational functions $F(x)$.7.3
unique factorisation domainAn integral domain in which every nonzero non-unit factors into irreducibles uniquely up to order and units. $\mathbb{Z}[x]$ is a UFD but not a PID; $\mathbb{Z}[\sqrt{-5}]$ is not a UFD.7.2 7.3
zero divisorA nonzero element $a$ of a commutative ring with $ab=0$ for some nonzero $b$; e.g. $2$ and $3$ in $\mathbb{Z}_6$. In a finite commutative ring every nonzero element is a unit or a zero divisor.7.2 7.3
Ch 8 · Functional Analysis
TermMeaningUsed in
adjoint operatorFor $T\in B(H,K)$, the operator $T^*\in B(K,H)$ with $\langle Tx,y\rangle=\langle x,T^*y\rangle$; $\|T^*\|=\|T\|$ and $\|T^*T\|=\|T\|^2$. For matrices it is the conjugate transpose.8.3 8.4
Banach spaceA normed space that is complete: every Cauchy sequence converges. Examples: $\ell^p$, $c_0$, $C[a,b]$ with the sup norm, $L^p[a,b]$; non-examples: $c_{00}$, $(C[0,1],\|\cdot\|_1)$.4.1 4.2 8.1 8.2
Bessel's inequalityFor an orthonormal set $\{e_\alpha\}$, $\sum_\alpha|\langle x,e_\alpha\rangle|^2\le\|x\|^2$.3.3 8.3 8.4
bounded linear operatorA linear map $T:X\to Y$ between normed spaces with $\|Tx\|\le C\|x\|$ for some constant $C$; for linear maps this is the same as being continuous.8.1 8.2 8.3 8.4
closed operatorA linear map whose graph $\{(x,Tx)\}$ is closed: $x_n\to x$ and $Tx_n\to y$ imply $Tx=y$. Everywhere defined closed operators between Banach spaces are bounded (closed graph theorem).8.2
compact operatorA linear map sending bounded sets to sets with compact closure: every bounded sequence $(x_n)$ has $(Tx_n)$ with a convergent subsequence. On a Hilbert space, exactly the norm limits of finite-rank operators.4.2 8.2 8.4
conjugate exponentFor $1\le p\le\infty$, the number $q$ with $\tfrac1p+\tfrac1q=1$ ($q=\infty$ when $p=1$); it appears in Hölder's inequality and in the duality $(\ell^p)^*=\ell^q$.8.1
dual spaceThe space $X^*$ of bounded linear functionals on a normed space $X$, with $\|f\|=\sup_{\|x\|\le1}|f(x)|$; always a Banach space. For example $(\ell^p)^*=\ell^q$ for $1\le p\lt\infty$ and $c_0^*=\ell^1$.3.1 8.1
finite-rank operatorA bounded operator whose range is finite-dimensional, e.g. $Tx=\sum_{i=1}^r\langle x,a_i\rangle b_i$; an integral operator with a degenerate kernel $\sum a_i(x)b_i(t)$.8.4
Fredholm alternativeFor compact $T$ and $\mu\ne0$: either $(T-\mu)u=f$ has exactly one solution for every $f$, or $\mu$ is an eigenvalue; for self-adjoint $T$, it is then solvable iff $f\perp\ker(T-\mu)$.8.4
graph normFor a linear map $T$, the norm $\|x\|+\|Tx\|$ on its domain; $T$ is closed iff the domain is complete in this norm.8.2
Hilbert spaceAn inner-product space that is complete in the induced norm, such as $\mathbb{F}^n$, $\ell^2$ and $L^2[a,b]$.8.1 8.3 8.4
Hilbert–Schmidt operatorAn operator with $\sum_n\|Te_n\|^2\lt\infty$ for an orthonormal basis $(e_n)$; integral operators with $K\in L^2$ are of this type, with $\|T\|_{HS}=\|K\|_{L^2}$. They are compact.8.4
inner-product spaceA vector space with an inner product $\langle x,y\rangle$ (linear in $x$, conjugate symmetric, positive); its norm is $\|x\|=\sqrt{\langle x,x\rangle}$. Example: $C[0,1]$ with $\int_0^1f\bar g$, which is not complete.3.3 8.3
Lebesgue constantThe norm of an approximation operator on $C$, e.g. $L_n=\frac1{2\pi}\int_{-\pi}^{\pi}|D_n|$ for Fourier partial sums; $L_n\to\infty$ like $\frac4{\pi^2}\log n$, which forces divergence for some continuous function.8.2
meagre setA countable union of nowhere dense sets (a set of the first category), e.g. $\mathbb{Q}$ in $\mathbb{R}$. By Baire's theorem a complete metric space is not meagre in itself.8.2
Minkowski functionalFor a convex set $C$ with $0$ in its interior, $p_C(x)=\inf\{t\gt0:x\in tC\}$; a sublinear functional with $C$ open equal to $\{p_C\lt1\}$, used to prove the separation theorems.8.1
normed spaceA vector space $X$ with a norm $\|\cdot\|$: a length function that is zero only at $0$, satisfies $\|\lambda x\|=|\lambda|\,\|x\|$ and the triangle inequality. It is a metric space with $d(x,y)=\|x-y\|$.4.1 4.2 4.3 8.1
nowhere dense setA subset of a metric space whose closure has empty interior, such as $\mathbb{Z}$ or the Cantor set in $\mathbb{R}$, or a proper closed subspace of a normed space.4.3 8.2
open mapA map sending open sets to open sets. A bounded linear surjection between Banach spaces is always open (open mapping theorem).4.1 5.1 5.3 8.2
operator norm$\|T\|=\sup_{\|x\|\le1}\|Tx\|$, the smallest constant $C$ with $\|Tx\|\le C\|x\|$ for all $x$; it makes $B(X,Y)$ a normed space, complete when $Y$ is.6.4 8.1
orthogonal complementFor a set $S$, $S^\perp=\{x:\langle x,s\rangle=0\ \forall s\in S\}$, always a closed subspace; $S^{\perp\perp}$ is the closed linear span of $S$.3.3 8.3 8.4
orthonormal basisIn a Hilbert space, a maximal orthonormal set; equivalently one with dense linear span, so that $x=\sum\langle x,e_\alpha\rangle e_\alpha$ for every $x$. It is not a Hamel basis in infinite dimensions.3.3 8.2 8.3 8.4
parallelogram law$\|x+y\|^2+\|x-y\|^2=2\|x\|^2+2\|y\|^2$. A norm comes from an inner product exactly when it satisfies this identity (Jordan–von Neumann).3.3 8.3 8.4
Parseval's identity$\|x\|^2=\sum_\alpha|\langle x,e_\alpha\rangle|^2$ for every $x$; it holds exactly when $\{e_\alpha\}$ is an orthonormal basis. For Fourier series: $\frac1{2\pi}\int_{-\pi}^{\pi}|f|^2=\sum_k|\hat f(k)|^2$.3.3 8.3 10.3
projection theoremIf $M$ is a closed subspace of a Hilbert space $H$, then $H=M\oplus M^\perp$; the component $P_Mx$ in $M$ is the unique closest point of $M$ to $x$.8.3 8.4
Rayleigh quotient$R(x)=\langle Tx,x\rangle/\|x\|^2$ for a self-adjoint $T$; its maximum is the largest point of the spectrum, attained at an eigenvector when $T$ is compact.3.3 6.3 8.1 8.4
reflexive spaceA normed space $X$ for which the canonical isometry $J:X\to X^{**}$, $(Jx)(f)=f(x)$, is onto. $\ell^p$ and $L^p$ ($1\lt p\lt\infty$) and Hilbert spaces are reflexive; $\ell^1$, $c_0$, $C[a,b]$ are not.8.1
residual setA set whose complement is meagre; in a complete metric space every residual set is dense. The irrationals form a residual subset of $\mathbb{R}$.8.2
resolvent setThe set $\rho(T)=\mathbb{C}\setminus\sigma(T)$ of $\lambda$ for which $T-\lambda I$ is a bijection (with bounded inverse); it is open.8.4
Riesz representation theoremEvery bounded linear functional on a Hilbert space is $f(x)=\langle x,y_f\rangle$ for a unique vector $y_f$, and $\|f\|=\|y_f\|$.8.3
self-adjoint operatorA bounded operator with $T^*=T$, i.e. $\langle Tx,y\rangle=\langle x,Ty\rangle$; its spectrum is real and $\|T\|=\sup_{\|x\|=1}|\langle Tx,x\rangle|$.8.3 8.4
spectral radius$r(T)=\max\{|\lambda|:\lambda\in\sigma(T)\}=\lim\|T^n\|^{1/n}\le\|T\|$, with equality for self-adjoint (normal) operators.8.1 8.4 9.1
spectrumFor a bounded operator $T$, the set $\sigma(T)$ of $\lambda$ for which $T-\lambda I$ has no bounded inverse: a nonempty compact set containing the eigenvalues, but possibly much more.3.2 3.3 8.4 9.2
sublinear functionalA real function $p$ on a real vector space with $p(x+y)\le p(x)+p(y)$ and $p(tx)=tp(x)$ for $t\ge0$; the dominating function in the Hahn–Banach theorem.8.1
uniform boundedness principleIf a family of bounded operators on a Banach space satisfies $\sup_\alpha\|T_\alpha x\|\lt\infty$ for every $x$, then $\sup_\alpha\|T_\alpha\|\lt\infty$ (also called the Banach–Steinhaus theorem).8.2
Ch 9 · Numerical Analysis
TermMeaningUsed in
A-stableA method is A-stable if its region of absolute stability contains the whole left half-plane $\operatorname{Re}z\lt0$. Backward Euler and the trapezoidal rule are; no explicit Runge–Kutta method is.9.3
backward Euler methodThe implicit method $y_{n+1}=y_n+hf(x_{n+1},y_{n+1})$; order 1, stability function $\tfrac1{1-z}$, A-stable.9.3
Cholesky factorisationA factorisation $A=LL^{\mathsf T}$ of a real symmetric matrix with $L$ lower triangular and positive diagonal. It exists (and is unique) iff $A$ is positive definite.9.1
degree of precisionThe largest $d$ such that a quadrature rule integrates every polynomial of degree $\le d$ exactly. Trapezoidal and midpoint rules: $1$; Simpson's 1/3 and 3/8 rules: $3$.9.2
diagonally dominantA matrix is strictly diagonally dominant (by rows) if $|a_{ii}|\gt\sum_{j\ne i}|a_{ij}|$ for every row $i$. Such a matrix is nonsingular, and the Jacobi and Gauss–Seidel iterations converge for it.9.1
divided differenceDefined by $f[x_i]=f(x_i)$ and $f[x_i,\dots,x_{i+k}]=\dfrac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}$. The $n$-th divided difference is the leading coefficient of the interpolant and equals $f^{(n)}(\xi)/n!$ for some $\xi$.9.1 9.2
Euler's methodThe one-step method $y_{n+1}=y_n+hf(x_n,y_n)$ for $y'=f(x,y)$: follow the tangent line for one step. Local truncation error $O(h^2)$, global error $O(h)$ (order 1).6.1 9.3
fixed-point iterationThe iteration $x_{n+1}=g(x_n)$ for an equation rewritten as $x=g(x)$. Near a fixed point $\alpha$ it converges if $|g'(\alpha)|\lt1$ (linearly, with rate $|g'(\alpha)|$, if $g'(\alpha)\ne0$) and diverges if $|g'(\alpha)|\gt1$.4.1 9.1 9.3
forward differenceFor equally spaced values $f_i=f(x_0+ih)$: $\Delta f_i=f_{i+1}-f_i$ (forward) and $\nabla f_i=f_i-f_{i-1}$ (backward). For a polynomial of degree $n$ with leading coefficient $a$, $\Delta^nf=a\,n!\,h^n$ is constant.3.1 9.2
Gauss–Seidel iterationThe iterative method for $Ax=b$ that, like Jacobi, solves the $i$-th equation for $x_i$, but uses each new component as soon as it is computed: $x^{(k+1)}=-(D+L)^{-1}Ux^{(k)}+(D+L)^{-1}b$.9.1
global error$e_n=y(x_n)-y_n$, the accumulated error after $n$ steps. For a method of order $p$ with Lipschitz increment function it is $O(h^p)$.9.3
interpolating polynomialThe unique polynomial $p_n$ of degree at most $n$ with $p_n(x_i)=f(x_i)$ at $n+1$ distinct nodes. Its error is $f(x)-p_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_0)\cdots(x-x_n)$ for $f\in C^{n+1}$.8.2 9.2
Jacobi iterationThe iterative method for $Ax=b$ that solves the $i$-th equation for $x_i$ using only the previous iterate: $x^{(k+1)}=-D^{-1}(L+U)x^{(k)}+D^{-1}b$, with $A=L+D+U$.4.1 9.1
Lagrange basis polynomial$\ell_i(x)=\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j}$: the polynomial of degree $n$ that is $1$ at the node $x_i$ and $0$ at the other nodes. Lagrange's formula is $p_n=\sum_if(x_i)\ell_i$.8.2 9.2
local truncation error$T_{n+1}=y(x_{n+1})-y(x_n)-h\Phi(x_n,y(x_n);h)$: the error of one step started from the exact value. A method has order $p$ if $T_{n+1}=O(h^{p+1})$.9.3
LU factorisationA factorisation $A=LU$ with $L$ lower and $U$ upper triangular (Doolittle: unit diagonal in $L$; Crout: unit diagonal in $U$). A nonsingular matrix has one iff its leading principal minors $\Delta_1,\dots,\Delta_{n-1}$ are nonzero; otherwise $PA=LU$ after row interchanges.9.1
modified Euler methodHeun's predictor–corrector: $y^*=y_n+hf_n$, then $y_{n+1}=y_n+\tfrac h2\left[f_n+f(x_{n+1},y^*)\right]$. A two-stage Runge–Kutta method of order 2.9.3
Newton–Cotes ruleAn integration rule obtained by integrating the interpolating polynomial at equally spaced nodes: closed rules (trapezoidal, Simpson 1/3, Simpson 3/8, Boole) use the end points, open rules (such as the midpoint rule) use only interior points.9.2
Newton–Raphson methodThe iteration $x_{n+1}=x_n-f(x_n)/f'(x_n)$: the next approximation is the root of the tangent line. It converges quadratically near a simple root, but only linearly (rate $\tfrac{m-1}{m}$) at a root of multiplicity $m\ge2$.1.1 3.2 4.1 9.1
order of convergenceA sequence $x_n\to\alpha$ converges with order $p$ if $|x_{n+1}-\alpha|/|x_n-\alpha|^p$ tends to a finite nonzero limit (with the limit below $1$ when $p=1$). Order $1$ is linear, $2$ quadratic; order $p$ roughly multiplies the number of correct digits by $p$ each step.9.1 9.2
partial pivotingIn Gaussian elimination, interchanging rows at each stage so that the pivot is the entry of largest absolute value in its column (on or below the diagonal). It keeps every multiplier at most $1$ in absolute value and controls rounding errors.9.1
region of absolute stabilityThe set of $z=h\lambda\in\mathbb{C}$ with $|R(z)|\lt1$, where the numerical solution of $y'=\lambda y$ decays. Its real part is the interval of absolute stability, $(-2,0)$ for Euler and RK2.9.3
Runge's phenomenonThe divergence of polynomial interpolants at equally spaced nodes near the ends of the interval, as for $\frac1{1+25x^2}$ on $[-1,1]$, even though the function is smooth. Chebyshev nodes avoid it.8.2 9.2
Runge–Kutta methodA one-step method that evaluates $f$ at several points inside a step and combines the slopes, matching the Taylor expansion of the solution to some order without differentiating $f$. Two stages give at most order 2.9.3
secant methodThe derivative-free iteration $x_{n+1}=x_n-f(x_n)\,\dfrac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$, using the chord through the last two points. Near a simple root its order is $\tfrac{1+\sqrt5}{2}\approx1.618$.9.1
shift operatorThe operator $E$ with $Ef(x)=f(x+h)$. The difference operators are $\Delta=E-1$ and $\nabla=1-E^{-1}$, and formally $E=e^{hD}$ with $D=d/dx$.3.1 3.2 9.2
Simpson's ruleSimpson's 1/3 rule: $\int_a^bf\approx\frac h3(f_0+4f_1+f_2)$, $h=\frac{b-a}{2}$, error $-\frac{h^5}{90}f^{(4)}(\xi)$; composite error $-\frac{(b-a)h^4}{180}f^{(4)}(\xi)$ ($n$ even). The 3/8 rule uses four points and also has degree of precision $3$.1.3 9.2
stability functionThe function $R$ with $y_{n+1}=R(h\lambda)y_n$ when a method is applied to $y'=\lambda y$; e.g. $1+z$ for Euler, $1+z+\tfrac{z^2}2$ for every second-order two-stage method, $\tfrac1{1-z}$ for backward Euler.9.3
stiff equationAn equation or system with widely separated negative eigenvalues: fast components decay almost at once but force explicit methods to use $h\lt2/|\lambda_{\max}|$; implicit A-stable methods remove the restriction.3.3 6.1 9.3
trapezoidal rule$\int_a^bf\approx\frac h2(f_0+f_1)$, $h=b-a$, with error $-\frac{h^3}{12}f''(\xi)$; the composite rule with $n$ panels has error $-\frac{(b-a)h^2}{12}f''(\xi)$, of order $2$.1.3 2.1 5.1 9.2
Ch 10 · Partial Differential Equations
TermMeaningUsed in
breaking timeThe first time at which characteristics of a quasilinear equation cross and the classical solution ceases to exist (its slope becomes infinite); for Burgers' equation $y_b=-1/\inf g'$.10.1
Burgers' equationThe quasilinear equation $z_y+z\,z_x=0$ (inviscid form), whose characteristics are the lines $x=s+g(s)\,y$; smooth data with $g'\lt0$ somewhere break at $y_b=-1/\inf g'$.10.1
canonical formThe simplest form of the principal part reachable by a change of variables: $u_{\xi\eta}$ (or $u_{\alpha\alpha}-u_{\beta\beta}$) for hyperbolic, $u_{\eta\eta}$ for parabolic, $u_{\alpha\alpha}+u_{\beta\beta}$ for elliptic equations.
Cauchy problemThe problem of finding a solution of a PDE that takes prescribed values (for second-order equations: values and a derivative) along a given curve. For first-order equations it is well posed near points where the curve is transversal to the characteristics.10.1 10.3
characteristic curveFor a first-order PDE: a solution curve of $\frac{dx}{dt}=P$, $\frac{dy}{dt}=Q$, $\frac{dz}{dt}=R$, along which the PDE reduces to an ODE. For a second-order equation: a curve along which $A\,dy^2-B\,dx\,dy+C\,dx^2=0$.10.1 10.2
complementary error function$\operatorname{erf}z=\tfrac2{\sqrt\pi}\int_0^ze^{-r^2}dr$ and $\operatorname{erfc}z=1-\operatorname{erf}z$; $T_0\operatorname{erfc}\frac{x}{2\sqrt{kt}}$ is the temperature in a semi-infinite rod whose end is held at $T_0$.10.3
d'Alembert's formulaThe solution of the Cauchy problem $u_{tt}=c^2u_{xx}$, $u(x,0)=f$, $u_t(x,0)=g$ on the line: $u=\tfrac12[f(x+ct)+f(x-ct)]+\tfrac1{2c}\int_{x-ct}^{x+ct}g$, the sum of a left-moving and a right-moving wave.10.2 10.3
Dirichlet problemFind a harmonic function in a domain with prescribed values on its boundary. By the maximum principle it has at most one solution.2.2 10.2
domain of dependenceFor the wave equation, the interval $[x_0-ct_0,x_0+ct_0]$ of initial data that determines the solution at $(x_0,t_0)$; it is the base of the characteristic triangle with apex $(x_0,t_0)$.10.2 10.3
domain of influenceFor the wave equation, the set $a-ct\le x\le b+ct$ of points whose value can be affected by the initial data on $[a,b]$; outside it the solution does not feel those data.10.3
Duhamel's principleThe solution of a forced linear evolution equation with zero data is the superposition, over $\tau\in[0,t]$, of free solutions started at time $\tau$ by the force acting at that instant; for waves it gives $\tfrac1{2c}\iint_{\Delta}F$ over the characteristic triangle.6.2 6.4 10.3
elliptic equationA second-order equation with $B^2-4AC\lt0$; no real characteristics. Model: Laplace's equation $u_{xx}+u_{yy}=0$.10.2
first integralA function that is constant along every solution of a system of ODEs (here the characteristic system); for $\frac{dx}{P}=\frac{dy}{Q}=\frac{dz}{R}$ it satisfies $Pu_x+Qu_y+Ru_z=0$.5.1 6.3 10.1 10.2
Fourier seriesThe expansion $\frac{a_0}2+\sum(a_n\cos\frac{n\pi x}L+b_n\sin\frac{n\pi x}L)$ of a function on $[-L,L]$; on $[0,L]$ the sine (cosine) series is that of the odd (even) extension. For piecewise $C^1$ functions it converges to the average of the one-sided limits.4.2 8.2 8.3 8.4
Fourier transformFor integrable $f$ on $\mathbb{R}$, $\hat f(\omega)=\int f(x)e^{-i\omega x}dx$; it turns $d/dx$ into multiplication by $i\omega$ and convolution into multiplication, with inverse $f(x)=\tfrac1{2\pi}\int\hat f(\omega)e^{i\omega x}d\omega$.10.3
general integralThe family of solutions $\varphi(u,v)=0$ of $Pp+Qq=R$, where $u=c_1$, $v=c_2$ are independent first integrals and $\varphi$ is an arbitrary function (Lagrange's theorem).10.1
heat kernel$\Phi(x,t)=(4\pi kt)^{-1/2}e^{-x^2/(4kt)}$, the temperature from a unit point source; convolving it with bounded initial data gives the bounded solution of $u_t=ku_{xx}$ on the line.10.2 10.3
hyperbolic equationA second-order equation $Au_{xx}+Bu_{xy}+Cu_{yy}+\dots=0$ with discriminant $B^2-4AC\gt0$ at the point; it has two families of real characteristics. Model: the wave equation.
integral surfaceThe graph $z=z(x,y)$ of a solution of a first-order PDE. For $Pp+Qq=R$ it is a surface to which the vector field $(P,Q,R)$ is everywhere tangent.10.1
Lagrange's auxiliary equationsThe system $\dfrac{dx}{P}=\dfrac{dy}{Q}=\dfrac{dz}{R}$ attached to $Pp+Qq=R$; its solutions are the characteristic curves.10.1
Neumann problemFind a harmonic function with prescribed outward normal derivative $g$ on the boundary; solvable only if $\oint g\,ds=0$, and then unique up to an additive constant.10.2
normal modeA separated solution $\left(a\cos\frac{n\pi ct}L+b\sin\frac{n\pi ct}L\right)\sin\frac{n\pi x}L$ of the vibrating-string problem, oscillating with frequency $\frac{nc}{2L}$; every solution is a superposition of normal modes.8.4 10.2
parabolic equationA second-order equation with $B^2-4AC=0$ (and $A,B,C$ not all zero); one family of characteristics. Model: the heat equation $u_t=ku_{xx}$.10.3
Plancherel's theoremFor $f\in L^1\cap L^2(\mathbb{R})$, $\int|f|^2dx=\tfrac1{2\pi}\int|\hat f|^2d\omega$: the Fourier transform preserves energy up to the factor $2\pi$ (the integral analogue of Parseval's identity).10.3
Poisson's integral formulaThe solution of the Dirichlet problem in the disc $r\lt\rho$: $u(r,\theta)=\frac1{2\pi}\int_{-\pi}^{\pi}\frac{(\rho^2-r^2)f(\varphi)}{\rho^2-2\rho r\cos(\theta-\varphi)+r^2}\,d\varphi$.10.2
quasilinear equationA PDE that is linear in the highest-order derivatives, with coefficients that may depend on the unknown and its lower derivatives. In first order: $P(x,y,z)\,p+Q(x,y,z)\,q=R(x,y,z)$ with $p=z_x$, $q=z_y$.10.1
separation of variablesThe method of looking for solutions $u=X(x)T(t)$ (or $X(x)Y(y)$, $R(r)\Theta(\theta)$); the boundary conditions give an eigenvalue problem, and the general solution is a superposition fitted to the remaining data by Fourier coefficients.6.3 10.2 10.3
transversality conditionFor data on $(x_0(s),y_0(s))$ and the equation $Pp+Qq=R$: $J=x_0'Q-y_0'P\ne0$, i.e. the data curve is not tangent to the base characteristics. It guarantees a unique local solution of the Cauchy problem.10.1
Ch 11 · Topology
TermMeaningUsed in
basis for a topologyA family $\mathcal{B}$ of subsets covering $X$ such that every point of $B_1\cap B_2$ lies in some $B_3\subseteq B_1\cap B_2$; the open sets it generates are the unions of its members.11.1
box topologyThe topology on $\prod X_\alpha$ whose basic sets are all products $\prod U_\alpha$ of open sets; strictly finer than the product topology for infinitely many nontrivial factors.11.1 11.2
cofinite topologyOn a set $X$, the topology whose nonempty open sets are the complements of finite sets; on an infinite set any two nonempty open sets meet.11.1 11.2
compact spaceA space in which every open cover has a finite subcover; continuous images of compact spaces are compact.4.1 11.1 11.2
connected componentA maximal connected subset of a space; the components are closed, pairwise disjoint and cover the space.4.1 5.3 11.2
connected spaceA space that cannot be split into two disjoint nonempty open sets; equivalently, its only clopen subsets are $\varnothing$ and the whole space.11.2
Hausdorff spaceA space in which any two distinct points have disjoint open neighbourhoods ($T_2$); limits of sequences are unique and compact subsets are closed.4.3 11.1 11.2
homeomorphismA bijection $f$ such that $f$ and $f^{-1}$ are both continuous; homeomorphic spaces have the same topological properties.1.1 4.1 4.3 5.3
Lindelöf spaceA space in which every open cover has a countable subcover.11.2
normal spaceA $T_1$ space in which any two disjoint closed sets have disjoint open neighbourhoods ($T_4$); metric spaces and compact Hausdorff spaces are normal.11.2
order topologyThe topology on a linearly ordered set generated by the open intervals $(a,b)$ (and half-open intervals at a least or greatest element); the open rays form a subbasis.11.1 11.2
product topologyThe topology on $\prod X_\alpha$ generated by the sets $\pi_\alpha^{-1}(U)$; its basic sets restrict only finitely many coordinates. A map into the product is continuous iff every coordinate is.11.1 11.2
quotient mapA surjection $q:X\to Y$ such that $V\subseteq Y$ is open exactly when $q^{-1}(V)$ is open in $X$; the resulting topology on $Y$ is the quotient topology.3.1 11.1
second countableSecond countable: the topology has a countable basis. First countable: every point has a countable local basis. Second countable implies first countable and separable.11.1 11.2
separable spaceA space with a countable dense subset; for metric spaces this is equivalent to second countability.11.2
Sorgenfrey lineThe real line $\mathbb{R}_\ell$ with the topology generated by the half-open intervals $[a,b)$; strictly finer than the usual topology, and every $[a,b)$ is clopen.11.1 11.2
subbasisA family of subsets whose union is $X$; the topology it generates consists of all unions of finite intersections of its members.11.1
topological spaceA set $X$ with a topology: a family of subsets (the open sets) containing $\varnothing$ and $X$ and closed under arbitrary unions and finite intersections.11.1 11.2
totally disconnectedA space whose only connected subsets are single points, such as $\mathbb{Q}$, the Cantor set or the Sorgenfrey line.4.1 11.2
Urysohn's lemmaIn a normal space any two disjoint closed sets $A,B$ admit a continuous $f:X\to[0,1]$ with $f=0$ on $A$ and $f=1$ on $B$.11.1 11.2
Ch 12 · Linear Programming
TermMeaningUsed in
artificial variableA nonnegative variable added to a $\ge$ or $=$ constraint to supply a starting basis. The two-phase and Big-M methods drive all artificial variables to $0$; if this is impossible, the original problem is infeasible.12.1
assignment problemChoose a permutation $\sigma$ (worker $i$ to job $\sigma(i)$) minimising $\sum_ic_{i\sigma(i)}$. Its LP relaxation has permutation matrices as basic feasible solutions.12.1 12.2
basic feasible solutionFor $Ax=b$, $x\ge0$ with $A$ of rank $m$: the solution obtained by choosing $m$ independent columns (a basis), setting the other variables to $0$ and solving, provided it is $\ge0$. It is degenerate if some basic variable is $0$.12.1 12.2
complementary slacknessFor feasible $x$ (primal) and $y$ (dual): both are optimal iff $y_i(b-Ax)_i=0$ for every constraint and $x_j(A^{\mathsf T}y-c)_j=0$ for every variable — a positive price forces a tight constraint, a positive variable forces a tight dual constraint.12.1 12.2
dummy sourceAn extra row (or column) added to balance an unbalanced transportation or assignment problem; its supply (or demand) is the imbalance and its costs are $0$, or the storage or shortage penalties.12.2
extreme pointA point of a convex set that is not interior to any segment in the set — a corner. For $\{x:Ax=b,\ x\ge0\}$ the extreme points are exactly the basic feasible solutions.12.1
Hungarian methodThe assignment algorithm that reduces rows and columns, covers the zeros with the fewest lines, and adjusts by the smallest uncovered entry until $n$ lines are needed; then $n$ independent zeros give an optimal assignment.12.2
Kőnig's theoremIn a matrix, the largest number of independent zeros (no two in a row or column) equals the smallest number of lines covering all zeros.12.2
least-cost methodA starting rule for the transportation problem that allocates as much as possible to a cheapest remaining cell at each step.12.2
linear programmeAn optimisation problem whose objective is a linear function $c^{\mathsf T}x$ and whose constraints are finitely many linear equations and inequalities. Its feasible region is a convex polyhedron; it is infeasible, unbounded, or has an optimal solution at a corner.12.1 12.2
minimum ratio testIn a simplex pivot, the choice of the leaving variable: the smallest ratio $\bar x_{B_i}/y_{ik}$ over the rows with $y_{ik}\gt0$. If no entry of the entering column is positive, the LP is unbounded.12.1
MODI methodThe optimality test of the transportation problem: solve $u_i+v_j=c_{ij}$ on the basic cells, compute $d_{ij}=c_{ij}-u_i-v_j$; the solution is optimal if all $d_{ij}\ge0$, otherwise a cell with $d_{ij}\lt0$ enters along its loop.12.2
net evaluationFor a basis with matrix $B$, the number $\Delta_j=z_j-c_j=c_{\mathcal B}^{\mathsf T}B^{-1}a_j-c_j$. In a maximisation the current basic feasible solution is optimal when all $\Delta_j\ge0$; a negative $\Delta_j$ marks a column that can enter.12.1 12.2
north-west corner ruleA starting rule for the transportation problem: allocate as much as possible to the top-left cell of the remaining table, cross out the exhausted line, and repeat. It ignores costs.12.2
revised simplex methodThe simplex method organised around $B^{-1}$ alone: price the columns with $\pi^{\mathsf T}=c_{\mathcal B}^{\mathsf T}B^{-1}$, compute only the entering column $B^{-1}a_k$, and update $B^{-1}$ by an elementary eta matrix after each pivot.12.1
shadow priceThe optimal dual variable $y_i^*$ of a constraint, read as the rate of change of the optimal value per unit increase of the right-hand side $b_i$; valid while the optimal basis stays feasible.1.2 12.1
transportation problemMinimise $\sum c_{ij}x_{ij}$ subject to row sums $a_i$ (supplies), column sums $b_j$ (demands) and $x_{ij}\ge0$. It is balanced if $\sum a_i=\sum b_j$; its bases have $m+n-1$ cells and contain no loop.12.2
two-phase methodPhase I minimises the sum of the artificial variables; the problem is feasible iff the minimum is $0$, and Phase I then ends at a feasible basis. Phase II runs the simplex method on the real objective from that basis.12.1
Vogel's approximation methodA starting rule for the transportation problem: compute for each line the penalty (difference of its two smallest remaining costs), and allocate in the cheapest cell of the line with the largest penalty. Usually close to optimal, but not always optimal.12.2