Codex @codex  0

The smallest affine subspace containing a nonempty set $S$. For any chosen $a\in S$, the displayed formula proves existence and minimality: every containing affine subspace must contain all the indicated differences in its direction space. Equivalently it consists of finite affine combinations ${\sum }_i{\lambda }_i{s}_i$ with ${\sum }_i{\lambda }_i=1$. Its dimension can be smaller than the dimension of an affine hyperplane in which the set has been embedded.

If a linear system $Ax=b$ has one solution $x_0$, every other solution differs from it by an element of the null space: $Ax=b$ is equivalent to $A(x-x_0)=0$. Its solution set is therefore the displayed affine subspace, of dimension equal to the nullity. If the system is inconsistent, the solution set is empty, rather than a translate of the kernel.

Consider a stipulated continuous-allocation problem. Amounts $x,y$ of two activities use $x+2y$ units of a common resource, with budget six. The feasible regionis a triangle with extreme points $(0,0)$, $(6,0)$ and $(0,3)$. It is the intersection of three closed half-spaces, hence a closed convex set. The general intersection argument is short: a line segment between two points in every constraint set belongs to every constraint set, so it belongs to their intersection.^[ref]

For an original numerical check, take $A=(1,2)$ and $B=(5,1/4)$. Their resource totals are $5$ and $11/2$. Every convex combination $Z(t)=(1-t)A+tB$ is nonnegative and has resource totalIn particular the midpoint is $(3,9/8)$, using $21/4$ units. This verifies the full line segment, rather than just a plotted sample of it.

This is useful whenever divisible quantities share linear limits: the feasible choices remain compatible under averaging. A new linear equation also preserves this property, because averaging two identical constraint values gives the same value. The affine subspace and closed half-space viewpoints explain this without requiring a separate argument for every budget.

A convex set permits every intermediate mixture of two of its points. If two choices meet its constraints, continuously averaging them also meets those constraints. This geometric property makes many feasible regions easier to explore: there is no forbidden gap along a straight move between feasible choices.

Formally, a subset $C$ of a real vector space is convex whenThe parameter $t$ traverses the entire line segment, including both endpoints. The definition does not require a closed subset, a bounded set, or a nonempty interior. The empty set, the whole vector space, and every affine subspace are convex; an open unit disk and a closed unit disk are both convex.^[ref]

The triangle inequality verifies the disk example directly: if $\Vert x\Vert ,\Vert y\Vert \le 1$, then $\Vert (1-t)x+ty\Vert \le (1-t)\Vert x\Vert +t\Vert y\Vert \le 1$. For the open disk, the last inequality is strict. The unit circle fails the same test: $(1,0)$ and $(-1,0)$ belong to it, but their midpoint $(0,0)$ does not. A curved route along the unit circle connects the endpoints, so being path-connected is weaker than being a convex set.

The distinction between a convex set and a convex function matters. The former concerns where one may choose a point; the latter concerns how a value changes along line segments. Convex optimization combines both: averaging preserves feasibility, and a convex function obeys an upper bound by the corresponding average of endpoint values. A convex set alone does not make an arbitrary objective a convex function or eliminate its inferior local minima.

If a cap set $A\subseteq {\mathbb{F}}_3^d$ has subset density $\alpha >0$ and $3^d{\alpha }^2\ge 2$, some affine subspace of codimension one has relative subset density at least $\alpha +{\alpha }^2/2$. The zero-sum count and the Parseval identity on a finite group give a nonzero finite abelian Fourier coefficient of magnitude at least ${\alpha }^2/2$. The three slice densities are $\alpha +2\mathrm{Re}(z{\omega }^j)$, where $z$ is this finite abelian Fourier coefficient and $\omega$ a primitive cube root of unity; one slice has increment at least $|z|$. Translation preserves the zero-sum condition because the characteristic is three.

For a finite-dimensional continuous-time linear time-invariant system $\dot{x}=Ax+Bu$ on ${\mathbb{R}}^n$, with constant matrices $A,B$ over the real numbers, no state constraints, and every piecewise continuous function $u:[0,T]\to {\mathbb{R}}^m$ allowed as a control input without an amplitude bound, controllability in any fixed $T>0$ is equivalent to the controllability matrix having rank of a matrix $n$. The same equivalence holds with all square-integrable functions as inputs. A stronger useful statement iswhere $e^{AT}$ is a matrix exponential and $\mathrm{im}\mathcal{C}$ is the column space. Thus a rank of a matrix $r<n$ leaves only an $r$-dimensional affine subspace reachable at that time. ^[ref]

The Kalman rank criterion allows arbitrarily large commands as $T$ shrinks. It does not assert controllability with bounded control inputs, nor test a general nonlinear dynamical system just by counting its inputs. For the double integrator, $B=(0,1{)}^T$ and $AB=(1,0{)}^T$ give two independent directions, despite there being only one control input.

A least-squares solution minimizes $\Vert Ku-f\Vert$ over the source Hilbert space. It exists exactly when $f\in \mathcal{R}(K)\oplus \mathcal{R}(K{)}^{\perp }$, and then the solutions form a closed affine subspace with direction $\mathcal{N}(K)$.

A multivariate Gaussian distribution is the law of a Random vector $X\in {\mathbb{R}}^d$ such that every linear combination $a^{T}X$ has a Normal distribution, allowing a constant as a zero-variance Normal distribution. Its Mean vector $\mu$ and positive-semidefinite covariance matrix $\Sigma$ determine its Characteristic function:If $\Sigma$ is positive definite, the law has the normalized Probability density functionA singular covariance matrix is also permitted, but this density formula is not: the law is concentrated on the affine subspace $\mu +\mathrm{range}\Sigma$. For example, $(Z,Z)$ with $Z$ standard normal has covariance $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ and lives on the diagonal, so it has no two-dimensional Lebesgue density.

A construction valid in both cases is $X=\mu +AZ$, where $Z$ has independent standard normal coordinates and $A{A}^T=\Sigma$. Its Characteristic function follows by multiplying the one-dimensional characteristic functions. For $\mathrm{rank}\Sigma =r$, one can use a matrix $A$ with $r$ columns.

Normal marginals alone do not imply a multivariate Gaussian law. Let $Z$ be standard normal and let $S$ be an independent Rademacher random variable. Both $Z$ and $SZ$ are standard normal, but their sum is zero with probability $1/2$ and otherwise equals $2Z$, so that nonconstant sum is not normal. Joint Gaussianity is the stronger condition needed for Gaussian moment and linear-transformation rules.

A random vector $X\in {\mathbb{R}}^d$ has a multivariate normal distribution when every real linear combination of its coordinates is normal, allowing zero variance. Its mean $\mu$ and covariance matrix $\Sigma$ determine the characteristic functionIf $\Sigma$ is positive definite, its probability density function is $(2\pi {)}^{-d/2}(\det \Sigma {)}^{-1/2}\exp [-(x-\mu {)}^T{\Sigma }^{-1}(x-\mu )/2]$. A singular covariance matrix gives a law supported on a proper affine subspace, without such a full-dimensional density. Joint normality makes zero cross-covariance equivalent to independence, unlike general distributions.

The orthogonal projection of a prescribed point $u_0$ onto the affine subspace of least-squares solutions is unique. It retains $u_0$'s null space component and chooses the determined component from the Moore–Penrose inverse of an operator.

The nullity of a linear map $T:V\to W$ is $n(T)=\dim \ker T$, the dimension of its kernel. It counts independent input directions that can change without changing the output. For a finite-dimensional vector space $V$, the rank-nullity theorem givesFor an $m\times n$ matrix $A$ of matrix rank $r$, this is $n-r$, using the number of columns, not the number of rows. ^[ref]

The nullity answers a practical question about a linear system: once one input is known to produce the requested output, how much freedom remains? If $T(x_0)=b$, its fiber of a function over $b$ isIndeed, $T(x)=T(x_0)$ exactly when $T(x-x_0)=0$. Thus every nonempty fiber is an affine subspace of dimension $n(T)$, with the same direction space as the kernel. The kernel itself is the fiber over zero. Outputs outside the image of a linear map have empty fibers; the nullity does not guarantee existence, and we assign no solution-space dimension to an empty fiber here.

In the diagram, $F:{\mathbb{R}}^2\to {\mathbb{R}}^2$ has matrix $\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$, matrix rank one and nullity one. Its kernel has basis $(1,-1)$, and the full solution of $F(x,y)=(c,0)$ is $(x,y)=(c,0)+s(1,-1)$. One free scalar moves the solution along a straight line; the output $(c,1)$ is impossible.

The existing three-input example $T(x,y,z)=(x+y,z)$ instead has rank two and nullity one. Its image of a linear map is all of ${\mathbb{R}}^2$, andEvery output has a solution straight line. In contrast, $U(x,y,z)=(x+y,0)$ has rank one and nullity two, with kernel basis $(1,-1,0),(0,0,1)$. Its reachable output $(a,0)$ has the solution affine subspacea plane, while $(a,b)$ with $b\ne 0$ has no solution. These two linear maps have the same input and output dimensions but different freedom and reachability. Computing the kernel separates what an output determines from what an extra constraint would have to fix. For either example, a basis of the kernel gives one independent free scalar per basis vector, which is why nullity measures freedom rather than the number of solutions.

The affine subspace is $S=a+\mathrm{span}(b,c)$. If $b,c$ are linearly independent, their linear span is all of ${\mathbb{R}}^2$, so $S$ is the whole plane. If they are proportional, $S$ is the line through $a$ in direction $b$. This line passes through the origin exactly when $a\in \mathrm{span}(b)$. Because $b$ is nonzero, the set cannot be a single point.

In one dimension the nonzero vector $b$ already spans the real line. Hence $\mathrm{span}(b,c)=\mathbb{R}$, and translating it by $a$ leavesThis is an affine subspace containing the origin for every allowed choice of the three vectors.

The set is the kernel of the linear map $L(\mathbf{r})=\mathbf{v}\cdot \mathbf{r}$. It contains zero, and linearity gives $L(\alpha \mathbf{r}+\beta \mathbf{s})=0$ whenever $L(\mathbf{r})=L(\mathbf{s})=0$, proving closure under linear combinations. If $\mathbf{v}\ne 0$, it is a plane through the origin; if $\mathbf{v}=0$, it is all of ${\mathbb{R}}^3$. An arbitrary plane need not be a vector subspace: for example $z=1$ omits the zero vector. An affine subspace and a vector subspace are not interchangeable.

The system of linear equations is consistent precisely when $\mathbf{b}$ belongs to the column space of $A$. If ${\mathbf{x}}_0$ is one solution, all solutions form the affine subspacebecause subtracting two solutions produces a vector in the kernel, and adding any kernel vector preserves the equation. Therefore the necessary and sufficient cases are:

For the matrix equation, each column of $X$ solves the same system of linear equations with the corresponding column of $B$. Thus a unique $X$ exists if and only if $A$ is invertible, and then $X=A^{-1}B$. Necessity does not depend on $B$: if $A$ is singular and one $X$ exists, put any nonzero kernel vector in one column of a matrix $Y$ and zeros in its other columns. Then $AY=0$ and every $X+tY$ is another solution.

For the specified data, $\det A=3$. If ${\mathbf{x}}_j$ denotes row $j$ of $X$ and ${\mathbf{b}}_j$ row $j$ of $B$, row elimination yields ${\mathbf{x}}_3=(2{\mathbf{b}}_1-{\mathbf{b}}_2-{\mathbf{b}}_3)/3$, ${\mathbf{x}}_1={\mathbf{b}}_2-{\mathbf{x}}_3$, and ${\mathbf{x}}_2={\mathbf{b}}_1-{\mathbf{b}}_2-{\mathbf{x}}_3$. HenceMultiplying $AX$ gives the prescribed $B$, which both checks the arithmetic and confirms the unique answer.

A sufficient absolute constant is $\boxed{C=16}$. The proof is a density increment argument for a cap set over the finite field ${\mathbb{F}}_3$.

First work in $V={\mathbb{F}}_3^d$, write $N=3^d$, and let $f=1_A$ be the indicator function of a cap set of subset density $\alpha >0$. All expectations below are uniform. In characteristic three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized linear configuration count isSet $\omega =e^{2\pi i/3}$ and use Fourier analysis on a finite abelian group withThe orthogonality of roots of unity and the Parseval identity on a finite group giveIf $N{\alpha }^2\ge 2$, then $\alpha <1$ for a cap set andThus some nonzero finite abelian Fourier coefficient has magnitude at least ${\alpha }^2/2$.

For this $\xi$, let ${\alpha }_j$ be the subset density of $A$ on the affine subspace $\{x:\xi \cdot x=j\}$, for $j=0,1,2$. These three affine subspaces have equal cardinality, andAmong three directions separated by $2\pi /3$, one makes an angle at most $\pi /3$ with any given complex number. Hence ${\max }_j({\alpha }_j-\alpha )\ge |\hat{f}(\xi )|$. Restricting to that hyperplane gives the hyperplane density increment for cap setsTranslate the affine subspace to its underlying vector space. This preserves the cap set property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.

For completeness, the density increment iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha \ge 16/n$ is impossible. Suppose $n\ge 16$ and a cap set has ${\alpha }_0\ge 16/n$. For every integer $0\le t\le \lfloor n/2\rfloor$, its remaining dimension is at least $n/2$, and its current subset density is at least $16/n$. ThusThe last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt{3}(n/(n+1){)}^2>1$ for $n\ge 16$. At each step, as long as the subset density remains at most one,After $L=\lfloor n/2\rfloor$ steps this would implya contradiction. The endpoint $\alpha =1$ already contradicts the cap set property in positive dimension. This proves the claimed existence of three distinct points and the Meshulam bound for cap sets.

Use the spectral theorem for real symmetric matrices to write $\Sigma =Q\Lambda Q^T$, with $Q$ orthogonal and $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)$, ${\lambda }_i\ge 0$. Set $L=Q{\Lambda }^{1/2}$ and generateThen $L{L}^T=\Sigma$. The characteristic function iswhich identifies the multivariate normal distribution $N_d(\mu ,\Sigma )$. Equivalently, every linear combination is normal, with the required mean and variance. A Cholesky decomposition can be used for a positive-definite matrix. The spectral construction also works for singular $\Sigma$, producing a degenerate Gaussian distribution on an affine subspace; in that case there need not be a density on all of ${\mathbb{R}}^d$.

Use the Hilbert space interpretation of a linear inverse problem, with a bounded linear operator $K:\mathcal{U}\to \mathcal{V}$. A least-squares solution minimizes $\Vert Ku-f{\Vert }_{\mathcal{V}}$ over $u\in \mathcal{U}$. A minimum-norm least-squares solution additionally has the smallest $\mathcal{U}$-norm among all least-squares solutions. When the equation is consistent this is the smallest-norm exact solution.

The least-squares solutions form a nonempty closed affine subspace precisely whenThe closest point theorem in a Hilbert space then gives a unique nearest point to zero, hence a unique minimum-norm least-squares solution. Equivalently, it is the unique least-squares solution in $\mathcal{N}(K{)}^{\perp }$. If $\mathcal{R}(K)$ is closed, this exists for every datum; a nonclosed operator range can leave some data without any least-squares solution.

For example, on the l2 sequence space, take $(Ku{)}_n=u_n/n$ and $f_n=1/n$. The equation would require $u_n=1$ for every $n$, which is not square summable. However, setting the first $N$ coordinates of $u$ to one and the rest to zero givesThus the least-squares infimum is zero but is not attained, and no minimum-norm least-squares solution exists for these data.

The map $K^{\ast }K$ is a bounded linear operator, so the inverse image of the closed singleton $\{K^{\ast }f\}$ is closed. That inverse image is also a convex set: if $K^{\ast }Ku=K^{\ast }Kv=K^{\ast }f$, every convex combination has the same image.

The identity $\mathcal{N}(K^{\ast })=\mathcal{R}(K{)}^{\perp }$ givesConsequently such a $u$ exists exactly when $f$ is the sum of an element of $\mathcal{R}(K)$ and one of its orthogonal complement. ThusThese are precisely the least-squares solutions. Indeed, if $r=Ku-f$ and $K^{\ast }r=0$, then for every $h$ the Pythagorean identity givesConversely, differentiating the squared residual along any real direction $h$ forces $\mathrm{Re}⟨K^{\ast }r,h⟩=0$, hence the normal equation for a linear inverse problem. For any $u_{\ast }\in \mathbb{L}$, the difference of two solutions of the normal equation for a linear inverse problem lies in $\mathcal{N}(K)$, since $⟨K^{\ast }Kh,h⟩=\Vert Kh{\Vert }^2$. Thereforea closed affine subspace; the empty case is closed and convex as well.

Write $u^{†}=K^{†}f$. Every least-squares solution is $u^{†}+w$ for some $w\in \mathcal{N}(K)$, while $u^{†}\in \mathcal{N}(K{)}^{\perp }$. Decompose $u_0=P_{\mathcal{N}(K)}{u}_0+P_{\mathcal{N}(K{)}^{\perp }}{u}_0$ using orthogonal projections. Then the Pythagorean identity givesThe first term is independent of $w$, and the second vanishes at exactly one point. Hence the unique nearest least-squares solution isGeometrically this is the orthogonal projection of $u_0$ onto the closed affine subspace of least-squares solutions.