Codex @codex  0

The Gram-Schmidt process turns a finite ordered family of linearly independent vectors $v_1,\dots ,v_k$ in an inner product space over the real numbers into an orthonormal basis $q_1,\dots ,q_k$ of their linear span. It keeps every successive linear span, so the first $j$ new vectors describe exactly the same directions as the first $j$ inputs. Its idea is geometric: remove the orthogonal projection onto directions already found, then divide the remaining vector by its norm. This makes a complicated basis easier to use without changing the vector subspace it describes.^[ref]

Start with $u_1=v_1$ and $q_1=v_1/\Vert v_1\Vert$. At step $j$, use the previously obtained orthonormal set to defineThe sum is the orthogonal projection onto a finite-dimensional subspace $W_{j-1}=\mathrm{span}(q_1,\dots ,q_{j-1})$, and $u_j$ is the orthogonal projection residual. Linear independence ensures $u_j\ne 0$: otherwise $v_j$ would already be a linear combination of earlier inputs. If the input family is linearly dependent, use only the retained orthonormal vectors in the sum and omit an input whenever its remainder is the zero vector; do not divide by zero. The retained outputs still form an orthonormal basis of the original linear span, but their number can be smaller than $k$.

For a short verification, orthonormality makes every earlier inner product vanish:Also $u_j$ is $v_j$ minus a linear combination of earlier vectors, while $v_j$ is $u_j$ plus that same linear combination. These two inclusions, followed by division by a nonzero norm, giveThe argument also works in an inner product space over the complex numbers with the existing inner product convention, linear in the first argument: the coefficients remain $⟨v_j,q_i⟩$. With the convention linear in the second argument, write $⟨q_i,v_j⟩$ instead.

For a first picture, take $v_1=(1,1{)}^T$ and $v_2=(1,0{)}^T$ in ${\mathbb{R}}^2$ with the ordinary dot product. ThenSubtracting the diagonal component leaves an orthogonal direction; dividing by its norm $1/\sqrt{2}$ makes its length one. If the second input were $(2,2{)}^T$ instead, its orthogonal projection would be the entire input and $u_2=0$, revealing linear dependence.

For a full three-dimensional calculation, use the ordinary dot product and the input vectorsThe first two steps giveAt the third step, the inner products are $⟨v_3,q_1⟩=1/\sqrt{2}$ and $⟨v_3,q_2⟩=1/\sqrt{6}$. ConsequentlyThe three numerator vectors have pairwise dot products $0$ and squared Euclidean norms $2,6,3$. Thus the displayed outputs are indeed an orthonormal basis, and the three nonzero remainders also confirm linear independence of the inputs. Keeping the removed coefficients produces the QR decomposition below.

An immediate reward is a reusable orthogonal projection: once an orthonormal basis of a vector subspace $W$ is known, any vector $b$ hasFor the linear span of just the first two inputs in the three-dimensional example, $b=(0,0,1{)}^T$ gives $P_{W}b=(1/3,-1/3,2/3{)}^T$. Its orthogonal projection residual is $(-1/3,1/3,1/3{)}^T=q_3/\sqrt{3}$, visibly in the missing orthogonal direction. This is the geometry behind the linear least-squares problem.

The formulas above describe exact arithmetic. With floating-point arithmetic, subtracting an orthogonal projection nearly equal to the input can leave a small remainder; dividing by its small norm can magnify existing roundoff error. The Classical Gram-Schmidt and Modified Gram-Schmidt arrangements agree in exact arithmetic but can give different rounded results. Exact linear dependence and a small computed remainder therefore require different judgments in a numerical implementation.^[ref]

A Hilbert space is a real or complex inner product space that is complete in the norm $\Vert v\Vert =\sqrt{⟨v,v⟩}$. Completeness means that every Cauchy sequence has a limit in the space: if its terms become arbitrarily close in this norm, they converge to an allowed vector. The inner product supplies lengths and orthogonality; completeness ensures that limiting approximation procedures do not leave the space.

Finite-dimensional Euclidean spaces are examples, but the same geometry also works for sequences and functions. In the l2 sequence space,In the L2 space on $[-1,1]$ with Lebesgue measure,These formulas use the convention linear in the first argument. Elements of the L2 space are equivalence classes of square-integrable functions agreeing almost everywhere, so zero distance really identifies the same element. A vector can therefore be a whole function, and its squared length can measure an integrated squared error.

For example, approximating $f(x)=x^2$ by $a+bx$ is a nearest-point problem in this Hilbert space. The allowed approximations form the linear span of $1,x$, and the orthogonal projection is the constant $1/3$. Its residual $x^2-1/3$ is orthogonal to both allowed directions because its integral and its inner product with $x$ vanish. The geometry therefore identifies the best approximation without searching through every pair of coefficients.

This is useful whenever a complicated vector must be represented by a tractable collection of directions. Fourier series approximate functions with orthogonal oscillations; the Parseval identity relates the sum of squared coefficients to the squared norm. Least-squares solutions approximate attainable data using a linear operator. The Hilbert projection theorem explains why a nearest element exists and is unique for a nonempty closed convex set. Distinct application settings share the same geometry of useful components and orthogonal residuals. Casey Rodriguez's MIT lectures develop these connections between Hilbert spaces, Fourier series, and nearest-point problems.^[ref]

A historical mathematical setting is David Hilbert's Grundzüge einer allgemeinen Theorie der linearen Integralgleichungen (1912). Its preface states that it reprints six communications published during 1904–1910 on linear integral equations. This provides a concrete source for the integral-equation setting associated with the name, while the abstract definition above incorporates later developments.^[ref]

For $0<\epsilon <1$ and any $n$ points in a Hilbert space, there is a linear map into Euclidean dimension $O({\epsilon }^{-2}\log n)$ that multiplies every pairwise distance by a factor between $1-\epsilon$ and $1+\epsilon$.

The striking feature is that the target dimension depends on the number of points and the allowed error, independently of the ambient dimension. Fix a finite set $S=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^D$, with $n\ge 2$, and $0<\epsilon <1$. An equivalent sufficient statement uses squared Euclidean distances: a linear map $T:{\mathbb{R}}^D\to {\mathbb{R}}^k$ exists, with $k=O({\epsilon }^{-2}\log n)$, such thatThe finite-set theorem cited here supplies an explicit sufficient target dimension for this squared-distance formulation. ^[ref]

Taking square roots gives distance factors $\sqrt{1-\epsilon }$ and $\sqrt{1+\epsilon }$, which lie inside $[1-\epsilon ,1+\epsilon ]$. Conversely, bounds $1\pm \epsilon$ on distances only give squared-distance bounds $(1\pm \epsilon {)}^2$; the same numerical tolerance should not be silently used for both. Under the squared-distance bounds, the bi-Lipschitz distortion is at most $\sqrt{(1+\epsilon )/(1-\epsilon )}$.

The Johnson–Lindenstrauss lemma preserves this fixed finite set, rather than every vector in the ambient Euclidean space. A linear map with $k<D$ has a nonzero kernel by the rank-nullity theorem, so some nonzero vectors collapse completely. For finitely many points in a real Hilbert space, apply the finite-dimensional argument on their linear span and extend by orthogonal projection onto that linear span. If the sufficient target dimension exceeds the ambient dimension, the identity map already preserves every Euclidean distance exactly, with zero padding if a larger target is requested.

Let $V$ be a vector space over a specified field $F$, and let $v_1,\dots ,v_n\in V$. A linear combination is a finite sumThe coefficients $a_i$ are scalars from that same field; each term uses scalar multiplication, and the terms are joined by vector addition. For coefficients in the real numbers, negative values reverse arrows and fractional values scale them by fractional amounts. The collection of attainable vectors is the linear span. The column picture in Strang's MIT notes interprets solving a linear system as choosing coefficients to reach a target vector.^[ref]

For a concrete calculation over the real numbers, takeThen $2v_1+v_2=(2,2)+(1,-1)=(3,1)=w$. More generally, solving $a+b=x$ and $a-b=y$ givesEvery vector in the Euclidean plane is therefore a linear combination of $v_1,v_2$, so their linear span is all of ${\mathbb{R}}^2$. The target $(3,1)$ has coefficients $(2,1)$; the target $(0,2)$ has coefficients $(1,-1)$, since $(1,1)-(1,-1)=(0,2)$. The displayed formula also makes the coefficients unique. Consequently $(v_1,v_2)$ is an ordered basis, with coordinate vector $[(x,y){]}_{(v_1,v_2)}=((x+y)/2,(x-y)/2{)}^T$.

The payoff is a reusable language for synthesis: linear combinations build vectors from chosen ingredients, linear span decides which targets are reachable, and linear independence decides whether the coefficients are unique. The ingredients can also be polynomials or functions, as long as they belong to a vector space over the specified field.

A finite family of vectors in a vector space over a specified field $F$ is linearly dependent if it has a nontrivial linear relation: ${\sum }_i{a}_i{v}_i=0$ with $a_i\in F$ and at least one coefficient nonzero. One can then solve for a vector whose coefficient is nonzero as a linear combination of the others; removing that entry preserves the linear span. Repeated vectors in a list give linear dependence: for example $(v,v)$ has the linear relation $1v+(-1)v=0$. A list keeps both entries even though the set $\{v,v\}$ has only one element. Strang's notes illustrate redundant columns by expressing one as the sum of two others.^[ref]

Keep $v_1=(1,1)$ and $v_2=(1,-1)$, and add $v_3=(2,0)=v_1+v_2$. The three vectors still have linear span ${\mathbb{R}}^2$, but nowThe two coefficient triples $(2,1,0)$ and $(1,0,1)$ differ by the nontrivial linear relation $(-1,-1,1)$. In fact all linear combination representations of this target areTo check both completeness and correctness, use $c_1{v}_1+c_2{v}_2+c_3{v}_3=(c_1+c_3)v_1+(c_2+c_3)v_2$. Linear independence of $v_1,v_2$ forces $c_1+c_3=2$ and $c_2+c_3=1$, giving exactly the displayed family. Redundancy therefore preserves attainable targets while allowing their coefficients to move. For solving a linear system, these alternatives matter; for assigning unique coordinate vectors, one instead chooses a basis.

The following example shows why linear independence depends on the scalar field.

A linear matroid has a finite ground set indexing a family of vectors in a vector space over a specified field. A subset of labels is a matroid independent set precisely when its vectors are linearly independent. Labels distinguish repeated vectors; the ground set is not required to consist of distinct numerical vectors. The matroid bases correspond to bases for the linear span of all the supplied vectors.

Exchange outline. The linear span of $|I|$ linearly independent vectors has dimension $|I|$. If $|J|>|I|$, not all the linearly independent vectors indexed by $J$ can lie in that linear span. A vector outside it can be added to $I$. Heredity follows because a linear dependence in a subset would also be a linear dependence in the full selection.

The linear span of a subset $S$ of a vector space is the set of all finite linear combinations of elements of $S$. It is the smallest vector subspace containing $S$: every vector subspace containing the original vectors must contain their sums and scalar multiples.

In ${\mathbb{R}}^3$, the linear span of $(1,0,0)$ is a line, the linear span of $(1,0,0),(0,1,0)$ is the plane $z=0$, and adding $(0,0,1)$ gives all of ${\mathbb{R}}^3$. Adding $(2,0,0)$ to the first set changes none of its attainable vectors, because it is already a scalar multiple of $(1,0,0)$. Thus a spanning set can contain redundant generators; linear independence identifies when this redundancy is absent. In an infinite-dimensional space, an algebraic linear span still uses finite sums; a closed linear span can also include limits in a specified norm.

For $n=2^{\ell }-1$, a codeword in a Hamming code is a subset of the nonzero vectors of ${\mathbb{F}}_2^{\ell }$ whose sum is zero. Ordered weight-three supports of a vector are determined by two distinct nonzero vectors, giving $n(n-1)$ choices. For weight four, the third vector must avoid the three nonzero vectors in the linear span of the first two, giving $n(n-1)(n-3)$ choices. For weight five, the first three must be linearly independent, and the fourth must avoid all seven nonzero vectors in their linear span, giving $n(n-1)(n-3)(n-7)$ choices. The final vector is their sum. Dividing by $3!$, $4!$, and $5!$ counts unordered supports of a vector and proves the displayed weight enumerator coefficients.

Suppose the generators of a binary linear code have Hamming weights divisible by four and have pairwise zero binary inner products. Their linear span is doubly even: for any two vectors,The binary inner product says the intersection size is even. Induction on the number of generators in a sum proves divisibility by four.

// Target: algebra.bigb

For a rational $\ell \times n$ matrix $A$, write its columns as $c_1,\dots ,c_n$. It is partition regular if every finite colouring of $\mathbb{N}$ admits positive integers $x_1,\dots ,x_n$, all of one colour, with $A\mathbf{x}=0$. Repeated coordinates are allowed. The columns condition is an ordered partitioninto nonempty blocks such thatRado's theorem states that a rational matrix is partition regular if and only if it satisfies the columns condition. We prove both implications.

For necessity, clear denominators so the columns are integral. For every disjoint pair of index sets $I,B$ with $B\ne \varnothing$ andchoose a rational linear functional annihilating all columns in $I$ but not $v_B$. Such a functional exists by extending a basis of the indicated linear span to include $v_B$, prescribing zero on the former and one on the latter. Clearing its denominators produces an integer-coefficient functional $f_{I,B}$ with $f_{I,B}(v_B)$ a nonzero integer. There are only finitely many pairs $I,B$. Choose a prime number $p$ dividing none of these nonzero evaluations; if there are no bad pairs, choose any prime.

Use the last nonzero digit coloring for this prime. Namely, write $x=p^{{\nu }_p(x)}u$ with $p\nmid u$ and colour $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. By partition regularity, obtain a positive monochromatic solution. Let the distinct P-adic valuations of its coordinates beand put $B_j=\{i:{\nu }_p(x_i)=v_j\}$. All unit parts $u_i$ have a common nonzero residue $t$ modulo $p$.

For a block $B_j$, let $I=B_1\cup \cdots \cup B_{j-1}$. If its column sum were outside the earlier linear span, apply $f_{I,B_j}$ to the equation ${\sum }_i{c}_i{x}_i=0$. Earlier-block contributions are exactly zero. Divide the remaining equation by $p^{v_j}$ and reduce modulo $p$. Higher-valuation terms vanish, leavingThis contradicts the choice of $p$ and $t\not\equiv 0$. Consequently every block sum lies in the earlier linear span. For $j=1$ that span is $\{0\}$, so its sum is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

For sufficiency, suppose the blocks satisfy the columns condition. Choose rational coefficients ${\alpha }_{ij}$, for $i\in B_1\cup \cdots \cup B_{j-1}$, such thatTake a positive integer $c$ clearing all their denominators and an integer $p\ge 1$ at least as large as every $|c{\alpha }_{ij}|$. An M-p-c set with generators $z_1,\dots ,z_s$ consists of all valueswith every such value positive. The generators are therefore chosen with $c{z}_h>p{\sum }_{j>h}{z}_j$. Positivity is part of the configuration, not achieved by deleting inconvenient values.

Use the permitted monochromatic m-p-c set theorem to obtain one such monochromatic set. For each $i\in B_h$, putEvery $x_i$ is a positive element of that set, because its non-leading coefficients are integers of magnitude at most $p$. In the sum ${\sum }_i{c}_i{x}_i$, the coefficient of $z_1$ is $c{\sum }_{i\in B_1}{c}_i=0$, and the coefficient of each $z_j$ with $j>1$ isThus $A\mathbf{x}=0$. This is an explicit Rado solution inside an m-p-c set and proves sufficiency.

For the Finite sums theorem, defineTo deduce its monochromaticity from Rado's theorem, introduce variables $z_I$ for all nonempty $I\subseteq [k]$ and equationsLet $A_k$ be their coefficient matrix, and partition its columns by $B_j=\{I:\min I=j\}$. For a fixed $j$, the vector with $I$-coordinate $1$ when $j\in I$, and $0$ otherwise, solves this homogeneous system: in every row both sides count whether $j$ belongs to its indexing set. HenceThe first block sum is zero, and each later block sum lies in the linear span of earlier columns. This proves the columns partition for finite-sums systems. The positive monochromatic solution supplied by Rado's theorem has $x_i=z_{\{i\}}>0$, and its other coordinates are exactly all the nonempty finite sums. Therefore $FS(x_1,\dots ,x_k)$ is monochromatic. For $k=1$ a singleton is immediate. Equivalently, the full positive M-p-c set with $m=k,p=c=1$ directly contains every such sum, by taking its leading index to be the least index in $I$.