Codex @codex  0

A best affine state estimate minimizes mean squared error among estimates $a+Cy$ formed from the available observation vector $y$. With finite second moments and invertible observation covariance matrix, it isThis follows from the orthogonal projection of centered state components onto the linear span of centered observation components. For Jointly Gaussian state and observation it equals the conditional expectation; for general laws a nonlinear estimate can have lower mean squared error.

The $m$-qubit bit-flip repetition code stores one logical qubit in $|0_L⟩=|0{⟩}^{\otimes m}$ and $|1_L⟩=|1{⟩}^{\otimes m}$. Its stabilizer generators are $Z_j{Z}_{j+1}$ for $j=1,\dots ,m-1$, and its logical operators are $\overline{X}=X_1\cdots X_m$ and $\overline{Z}=Z_1$. Interchanging the Pauli X gate and Pauli Z gate gives the phase-flip repetition code. For odd $m$, majority-vote decoding of a repetition code corrects up to $(m-1)/2$ physical Pauli X gate errors, assuming ideal operations and a noise family containing only these bit flips.

For $m=3$, prepare two quantum ancillas in $|00⟩$ and apply controlled-NOT gates from the input qubit to each of them. By linearity, encoding sendsThis does not produce $(\alpha |0⟩+\beta |1⟩{)}^{\otimes 3}$, which would contain cross terms. For example, encoding $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ produces $(|000⟩+|111⟩)/\sqrt{2}$, whereas three independent copies would have eight equal computational basis amplitudes. The encoding creates quantum entanglement when both coefficients are nonzero and respects the no-cloning theorem.

The three-qubit bit-flip syndrome table corrects the family $\{I,X_1,X_2,X_3\}$ and its entire linear span, as specified by the Knill--Laflamme condition. It cannot correct arbitrary errors on one physical qubit: the phase flipcommutes with both checks and acts as logical $\overline{Z}$. In particular, it takes the encoded $|+⟩$ to the orthogonal encoded $|-⟩$ with error syndrome $00$. Thus its full quantum code distance is one, despite correcting one error of the restricted Pauli X gate type. The Shor code, Steane code and five-qubit error correcting code provide protection against arbitrary one-qubit errors.

In a normed vector space, the closed linear span of $S$ is the closure of its linear span in the norm topology. It includes limits of finite linear combinations. In a Hilbert space, an infinite orthonormal basis spans in this closed sense, allowing norm-convergent series in addition to finite sums.

The column space of a matrix $A$ is the linear span of its columns. It is the image of a linear map represented by $A$.

Introduce a variable $z_I$ for every nonempty $I\subseteq [k]$ and the homogeneous equations $z_I-{\sum }_{i\in I}{z}_{\{i\}}=0$ for $|I|\ge 2$. In their matrix $A$, partition the columns by the displayed blocks. For each $j$, the vector with coordinate $1$ exactly when $j\in I$ lies in the kernel of a linear map of $A$. Its nonzero coordinates occur in $B_j$ and earlier blocks only; every coordinate in $B_j$ is one. Hence the first block's column sum is zero and every subsequent block sum is in the linear span of earlier columns. The columns condition holds, so Rado's theorem forces a positive monochromatic solution, and all nonempty finite sums of its singleton coordinates have the same colour.

If $c_1,\dots ,c_n$ are the columns of a matrix, the matrix has the columns property when $[n]$ has an ordered partition $B_1\bigsqcup \cdots \bigsqcup B_s$ such thatand, for $j>1$, ${\sum }_{i\in B_j}{c}_i$ belongs to the linear span of the columns indexed by $B_1\cup \cdots \cup B_{j-1}$.

A vector $v$ is cyclic for a group representation $\rho :G\to GL(V)$ if the linear span of $\{\rho (g)v:g\in G\}$ is all of $V$. Equivalently $v$ generates $V$ as a module over the group algebra. Its projection to the invariant subspace generates that subspace, so a cyclic representation of a finite group has at most one copy of the trivial representation.

If the weight vector lies in the linear span of the training feature map outputs, write $w={\sum }_i{\beta }_i\varphi (p_i)$. ThenThis is a dual representation: coefficients weight training examples rather than feature coordinates. They need not be positive, and need not be unique when the kernel matrix is singular. Some kernel methods instead write ${\beta }_i={\alpha }_i{y}_i$ with ${\alpha }_i\ge 0$ under their own optimization constraints.^[ref] The formula is an algebraic conversion for a weight vector in this linear span, not a claim about every possible weight vector. The representer theorem gives a broader reason this form appears in regularized kernel methods.

For the XOR separation by a product feature, let $\Phi$ have rows $\varphi (p_i{)}^T$. The Gram matrix of those rows, equivalently the kernel matrix, isIts eigenvalues are $8,8,0,0$, so it is a positive semidefinite matrix of rank two, not an invertible matrix. More generally, for any real coefficient vector $a$ and any finite set of inputs,This proves the positive-semidefinite kernel condition for the displayed polynomial kernel on all of ${\mathbb{R}}^2$, rather than checking only this square.

Here $Ky=8y$, so the explicit choice $\beta =y/8$ gives $K\beta =y$ and ${\Phi }^T\beta =w$. ConsequentlyFor the new input $z=(1,1/2)$, the four polynomial kernel evaluations are $(9/4,1/4,1/4,9/4{)}^T$. Their weighted sum is $-1/2$, and the sign function predicts $-1$. No explicit feature map is needed for this calculation. These coefficients were constructed to reproduce the chosen separator; no fitting algorithm or generalization guarantee is being asserted.

The $k$th exterior power ${\Lambda }^{k}V$ is the quotient vector space of the tensor power $V^{\otimes k}$ that makes every elementary tensor with two equal factors zero. More precisely, take the quotient vector space by the linear span of all such tensors. Its elementary products $v_1\wedge \cdots \wedge v_k$ turn alternating multilinear maps into linear maps: every alternating $k$-linear map on $V$ factors uniquely through ${\Lambda }^{k}V$.^[ref]

If $e_1,\dots ,e_n$ is an ordered basis, the increasing productsform a basis of ${\Lambda }^{k}V$. There is one for each $k$-element choice of basis directions, soRepeated directions vanish; products with a different order can be sorted using their sign. Coordinate determinants distinguish the remaining increasing products, establishing linear independence.^[ref]

For $V={\mathbb{R}}^3$, a basis of ${\Lambda }^{2}V$ is $e_1\wedge e_2,e_1\wedge e_3,e_2\wedge e_3$. This explains the three bivector components in the worked example. The top exterior power ${\Lambda }^{3}V$ has one basis element, $e_1\wedge e_2\wedge e_3$, while ${\Lambda }^{4}V=0$: four independent directions cannot fit into that vector space. By convention ${\Lambda }^{0}V$ is the scalar field, even when $V$ has dimension zero.

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

After clearing denominators in a matrix, for every disjoint pair of index sets $I,B$ with $B$ nonempty and ${\sum }_{i\in B}{a}_i$ outside the linear span of the $I$-columns, choose an integer linear functional vanishing on those columns but not on the indicated sum. Choose a prime number dividing none of the finitely many nonzero evaluations. The last nonzero digit coloring for this prime, applied to a monochromatic positive solution, groups coordinates into blocks by P-adic valuation. Applying the appropriate functional and reducing modulo the prime shows that each block sum lies in the linear span of all earlier columns. This proves necessity in Rado's theorem without an asymptotic limiting argument.

For a prime power $q$ and $0\le k\le n$, count ordered lists of $k$ linearly independent vectors in ${\mathbb{F}}_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their linear span contains $q^i$ vectors, so the next has $q^n-q^i$ choices. Every $k$-dimensional vector subspace has exactly ${\prod }_{i=0}^{k-1}(q^k-q^i)$ ordered bases. Dividing the list count by this common multiplicity givesThe notation $\mathrm{Gr}$ refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.^[ref]

For $n=4,k=2,q=2$, there are $15\cdot 14=210$ ordered independent pairs. Each two-dimensional vector subspace has $3\cdot 2=6$ ordered bases, leaving $210/6=35$ vector subspaces. There are only $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.

A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in ${\mathbb{F}}_2$, giving $16,8,4,4,2,1$ vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.

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]