Codex @codex  0

Algebraic number theory studies integer factorization, divisibility, prime ideals, and units after extending the rational numbers to a number field. Its basic objects are a number field $K$ and its ring of integers ${\mathcal{O}}_K$: the counterparts of $\mathbb{Q}$ and $\mathbb{Z}$. The field norm turns multiplication in $K$ into multiplication of rational numbers, and takes algebraic integers to integers. These connections let linear algebra and Euclidean geometry answer arithmetic questions.^[ref]

A first example is $K=\mathbb{Q}(\sqrt{2})$ with ring of integers $\mathbb{Z}[\sqrt{2}]$. The integer $7$ acquires the factorizationEach factor has field norm $7$. Neither is a unit, and each is an irreducible element: any factorization into two nonunits would factor the prime number $7$ into two integers of absolute value greater than one. Arithmetic in a larger ring thus reveals structure invisible in ordinary integer factorization.

There is also a complication: unique factorization of elements can fail, as in the failure of unique factorization in the ring of integers generated by square root of minus five. The general replacement is prime ideal factorization. The ideal class group measures the obstruction to making every ideal a principal ideal.

The historical motivation is visible in Richard Dedekind's original 1877 exposition: he begins with ordinary integer factorization, passes to Gaussian integers, and then uses a quadratic example to explain why ideals are needed. His later section establishes unique factorization of ideals in a number field. This is a direct record of the development of the theory, rather than a claim that all its ideas originated in one year.^[ref][ref]

The Born rule connects a quantum state to measurement probabilities. Let $\{|j⟩\}$ be a complete orthonormal basis, finite or countably infinite, for a Hilbert space, and letAn ideal measurement distinguishing these basis vectors returns label $j$ with probabilityThis assignment is a physical measurement rule. Its compatibility with total probability one follows from orthonormality and normalization:The probabilities are the squared moduli, not the amplitudes themselves or the squares $a_j^2$. ^[ref].

If the basis is an eigenbasis of an observable, the reported numerical value is its eigenvalue. Several vectors can share one eigenvalue; the probability of that value is then the sum over the corresponding basis labels. More generally, a projective measurement with orthogonal projections $P_r$ assignsfor a pure state and a general density matrix $\rho$, respectively. This also covers mixed states and degenerate eigenspaces. The Born rule determines outcome statistics; the ideal conditional state change is specified separately by the Lüders rule. See projective measurement for that formulation and its assumptions. ^[ref].

For a worked example, take the normalized qubit quantum stateThe squared moduli add to $3/4+1/4=1$. A computational-basis measurement, equivalently a measurement of the $Z$ Pauli matrix, hasThese probabilities do not depend on the relative quantum phase $\varphi$. Now choose the Hadamard basiswhose vectors are eigenstates of the $X$ Pauli matrix, also used by the Pauli X gate. The new probability amplitudes and probabilities areBoth probabilities are nonnegative and their sum is one. The relative quantum phase becomes visible because the two probability amplitudes add before their squared modulus is taken:

A Hadamard gate followed by a computational-basis measurement realizes these $X$ statistics, since $H|\pm ⟩=|0⟩,|1⟩$, respectively. Compare the two bases using fresh, identically prepared copies: a preceding measurement may change the state. The quantum superposition section shows why replacing the preparation by the mixed state $\mathrm{diag}(3/4,1/4)$ keeps the $Z$ statistics but gives $p_{+}=p_{-}=1/2$ for every $\varphi$.

The usefulness of the Born rule is this conversion from linear algebra to experimental predictions: calculate overlaps in the basis actually measured, then take squared moduli. Its appealing geometry is that changing basis redistributes probability while preserving total squared norm. The same rule relates an energy eigenstate expansion to an energy measurement and a position wavefunction to a probability density.

Born's 1926 paper on quantum scattering interpreted the outgoing-wave coefficients in terms of the probabilities of collision outcomes; a corrective footnote specified proportionality to the square of the amplitude. This is a historical scattering formulation, rather than the general density matrix formula above. ^[ref]; ^[ref].

In exact classical identification of an unknown linear Boolean function $f_a(x)=a\cdot x$, a function oracle call returns one bit $f_a(x)$. The query complexity is exactly $n$ for $n\ge 1$. Queries on the standard basis inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ decision tree has at most $2^k$ answer histories and must distinguish $2^n$ hidden binary strings; hence $k\ge n$, even with adaptive inputs. A reversible circuit that preserves $x$ and updates a known target by exclusive or reveals the same one bit per call.

There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix $M$ over the two-element finite field, and the replies specify $Ma$. If there are $k<n$ queries, the rank-nullity theorem gives a nonzero vector $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

Controllability asks whether the available control inputs can move a dynamical system between every pair of states in its declared state space. Fixing a duration $T>0$ gives the precise condition ${\mathcal{R}}_T(x_0)=X$ for every $x_0\in X$, where $X$ is the state space and ${\mathcal{R}}_T(x_0)$ its reachable set. With freely chosen duration, every pair must instead be connectable in some permitted finite time, which may depend on the pair. Always specify admissible control inputs, deadlines and any constraints along the path. ^[ref]

The surprising part is that one control input can control several state variables by acting at different times. For the double integrator, acceleration changes velocity directly, while the accumulated velocity changes position. Starting from rest, accelerate during the first half of the journey and brake during the second: the final velocity can vanish although the final position has changed. The figure is an analytic mathematical example in dimensionless quantities, with no experimental measurements.

Controllability is useful before trying to design a controller: a requested endpoint outside the reachable set cannot be attained by clever choice of feedback control. The Kalman rank criterion makes this an exact linear algebra calculation for the stated linear time-invariant system model. It concerns whole states, so attaining one plant output is not enough to establish controllability. In quantum control, the declared state space may be an orbit constrained by conservation laws; see quantum controllability and unitary orbit of a density operator.

For two projective triangles in a projective plane over a field, perspectivity from a point implies perspectivity from a line. The usual nondegenerate form assumes that the corresponding-side intersections are well defined and distinct. Its dual is the converse, by point-line duality. The result holds in the real projective plane; it is not an axiom valid in every abstract incidence plane.

One linear algebra proof explains the collinearity. Choose a representative $o$ of the center. Rescale the paired representatives to $p^{\prime }=p+\alpha o$, $q^{\prime }=q+\beta o$, and $r^{\prime }=r+\gamma o$, with nonzero coefficients in a nondegenerate configuration whose vertices differ from the center. The first corresponding-side intersection is represented by $x=\beta p-\alpha q=\beta p^{\prime }-\alpha q^{\prime }$. Similarly choose $y=\gamma q-\beta r$ and $z=\alpha r-\gamma p$. Then $\gamma x+\alpha y+\beta z=0$, so the three representatives are linearly dependent. Their projective points are consequently collinear.

Primary source: Released examination archive, member 4224-1.pdf. The original nine-page scan identifies the University of Oxford Preliminary Examination in computer science on 14 June 2013. Questions 1–3 cover digital electronics, the datapath and file systems; Questions 4–6 cover linear algebra; Questions 7–8 use the supplied natural deduction rules on printed p. 9. The original p. 8 repeats Question 8(a)(i) as Question 8(a)(iii), and has a redundant closing parenthesis in Question 7(d)(i).

Primary source: Released examination archive, member 4224.pdf. The original nine-page cover identifies the Preliminary Examination in Computer Science, Trinity Term 2014, Friday 20 June. Questions 1–3 cover digital counters, the MIPS architecture and file systems; Questions 4–6 cover linear algebra; Questions 7–8 use the supplied natural deduction rules in Figures 1–3 on printed page 9.

Examination paper of the University of Oxford, Preliminary Examination in Computer Science, Trinity Term 2015, dated 19 June 2015. The original has seven pages; the last contains the prescribed natural deduction rules. Released archive: Lawrence Attachment.zip, member 2015-cs4.pdf. The paper's printed section order is linear algebra, digital electronics, and introduction to formal proof, despite the different ordering in its cover title.

Euclidean geometry describes flat Euclidean space using lengths, angles, and rigid motions. A coordinate realization uses points $x,y\in {\mathbb{R}}^n$, Euclidean distanceand angles determined by the dot product. The coordinate axes are a convenience: translations and rotations change coordinates while preserving these measurements. This makes Euclidean geometry useful for comparing figures and converting measurements along different directions into a single distance.

In the Euclidean plane, through a point outside a line there is exactly one parallel line. This is a standard equivalent formulation of the parallel postulate. Euclid's fifth postulate in the Elements instead describes when two lines meet using the interior angles made by a crossing line.^[ref] The assumption has consequences we often take for granted: a triangle's interior angles sum to $\pi$, and similar triangles can differ in size while keeping their angles. Comparing with spherical geometry reveals that these are properties of a particular geometry.

As a computed example, the diagonal from $(0,0)$ to $(4,3)$ in a rectangle has length $\sqrt{4^2+3^2}=5$. The Pythagorean theorem explains why perpendicular contributions add as squares. If the directions cease to meet at a right angle, the law of cosines supplies the missing angle-dependent term. The beauty is that a single distance formula unites geometric constructions, coordinate calculations, and orthogonality in linear algebra.

Make the assumptions visible: in a Cartesian coordinate system with orthogonal axes and the same length unit on each axis, take $A=(0,0)$, $B=(4,0)$ and $C=(0,3)$. The vectors $B-A=(4,0)$ and $C-A=(0,3)$ have dot product zero, establishing a right angle at $A$ before using the Pythagorean theorem. A sketch that merely looks like a right triangle supplies no such guarantee. Likewise, an image stretched horizontally and vertically by different amounts can distort both lengths and angles; a displayed shape and the assumptions defining it must be kept separate.

For a less origin-dependent measurement, take $P=(1,2)$ and $Q=(5,5)$. Their displacement vector is $Q-P=(4,3)$, so their Euclidean distance is again $5$. Its Euclidean norm records the direct separation, whereas travelling first horizontally and then vertically covers length $4+3=7$. This connects measuring a diagonal to locating two positions from a Cartesian coordinate system. A translation changes where the positions are recorded without changing their separation; a rotation changes the component values without changing the Euclidean norm.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

Functional analysis brings linear algebra and topology together to study vector spaces of functions and the linear operators acting on them. A function space such as $C([0,1])$ has infinitely many independent directions: the monomials $1,x,x^2,\dots$ are linearly independent. Finite linear combinations alone cannot describe all its continuous functions. A useful theory must also say when approximations converge, whether their limits belong to the chosen space, and which operations preserve that norm convergence. Normed vector spaces, Banach spaces, and bounded linear operators provide these three controls.^[ref]

A bounded linear operator $T:X\to Y$ between normed vector spaces satisfies $\Vert Tf{\Vert }_Y\le M\Vert f{\Vert }_X$ for every $f$, with one finite constant $M$. The least possible constant is its operator norm. By linearity, the same estimate controls approximation errors:This is exactly continuity for a linear map between normed vector spaces; neither space needs to be complete. It turns an input accuracy guarantee into an output accuracy guarantee, even when the input has infinitely many degrees of freedom.^[ref]

For a concrete linear functional on $C([0,1])$, take the integral $F(f)={\int }_0^{1}f(x)dx$. In the supremum norm,The constant function $f=1$ attains equality, so $\Vert F\Vert =1$. For $f(x)=x^2$, the output is $F(f)=1/3$; any approximation $g$ with $\Vert g-x^2{\Vert }_{\infty }\le 0.01$ therefore has $|F(g)-1/3|\le 0.01$. The Cauchy-Schwarz inequality also gives $|F(f)|\le \Vert f{\Vert }_2\Vert 1{\Vert }_2=\Vert f{\Vert }_2$ on this interval, again with equality at $1$. Thus integration remains a bounded linear functional under the L2 norm, although point evaluation behaves very differently.

The beauty of this viewpoint is that one estimate can justify an entire approximation procedure. Once a sequence converges in the chosen norm, every bounded linear operator carries its limit along. Completeness ensures that Cauchy approximations actually describe an element of the space. The choice of norm matters: it determines which errors are small and which measurements are stable. The examples below distinguish an average, which ignores sufficiently narrow peaks, from point evaluation, which detects their full height. For applications, this decides whether reducing an overall fitting error guarantees an accurate reported measurement. A small L2 norm of the error controls its integral on this interval, while it gives no such guarantee for a single sampled value.

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.

The kernel trick evaluates inner products of feature map outputs through $k(x,z)=⟨\varphi (x),\varphi (z)⟩$ without explicitly constructing those vectors. An algorithm expressed entirely through these inner products can therefore operate on nonlinear derived coordinates using only evaluations of a positive-semidefinite kernel on the original inputs. A classifier linear in the derived coordinates can have a nonlinear boundary in the original coordinates.

The polynomial kernel gives a finite, fully visible example: $k(x,z)=(x^{T}z{)}^2$ corresponds to $\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2{)}^T$. The XOR separation by a product feature below makes the interaction coordinate $x_1{x}_2$ useful, while dual prediction with a kernel shows how to predict without calculating it explicitly.

An arbitrary score called a similarity need not be a positive-semidefinite kernel. Symmetry alone, even with nonnegative entries, is insufficient: the symmetric matrixhas $a^{T}Sa=-2$ for $a=(1,-1{)}^T$, so it cannot be a Gram matrix of real inner products. A positive-semidefinite kernel requires a positive semidefinite matrix for every finite choice of inputs, not just the observed training data.^[ref] The existing Moore-Aronszajn theorem connects this requirement to a Reproducing kernel Hilbert space; this example needs only finite linear algebra.

Linear algebra studies vector spaces and linear maps: operations that preserve vector addition and scalar multiplication. For a linear map $T$, the defining rule is $T(au+bv)=aT(u)+bT(v)$, where $u,v$ are vectors and $a,b$ belong to the underlying field. The vectors might be arrows, lists of measurements, or polynomials. What matters is that their linear combinations make sense and that the same rule governs their transformation.

A concrete linear map is $T(x,y)=(x+y,x-y)$. Its two outputs record a sum and a difference. Since $T(1,0)=(1,1)$ and $T(0,1)=(1,-1)$, we immediately obtain $T(2,1)=2(1,1)+(1,-1)=(3,1)$. Knowing the outputs of the basis vectors determines the output of every vector; a matrix stores exactly that information in its columns.

The attraction of linear algebra is that one small collection of ideas answers several different questions. A system of linear equations asks which inputs produce a prescribed output. The image of a linear map describes the attainable outputs, while the kernel describes the invisible input changes. A basis gives every vector an address, and change of basis lets us choose addresses that make a linear map easier to understand. This shared language turns a collection of separate calculations into a picture of what is possible and how much freedom remains. Gilbert Strang's MIT course emphasizes these connections and their usefulness across other disciplines.^[ref]

Core linear algebra paper.

Linear operator theory studies linear maps, their spectra, invariant subspaces, and normal forms such as Jordan normal form. In a finite-dimensional vector space, eigenvalues identify parameters for which a shifted linear operator cannot be inverted. In an infinite-dimensional vector space, inversion can fail even without an eigenvector. The spectrum of a bounded operator captures this larger obstruction and connects linear algebra with the approximation questions of functional analysis.

Mathematical finance uses probability theory, linear algebra and mathematical optimization to study financial markets, portfolio decisions and contingent claim prices. One question asks which portfolio best serves a specified objective; another asks what price a contingent claim must have to exclude arbitrage. The latter can have an exact answer even when future stock prices are uncertain.

The central idea is claim replication: construct a self-financing portfolio delivering the same financial payoff as a contract in every possible state. The law of one price then identifies the contract's price with the portfolio's initial cost. The binomial market makes this beautiful connection between uncertainty and linear algebra visible using just two equations. Risk-neutral pricing expresses the same cost as a discounted expectation.

The one-step example below fixes today's stock price at 100, terminal prices at 120 or 80, and the bank account's gross growth factor at 1.05. A European call option with strike price 100 pays 20 or zero. Its replicating portfolio in a binomial market costs $250/21$, independently of the physical up probability, provided both states remain possible. These are conclusions within the specified financial market model.

Linear algebra and group theory.