Codex @codex  0

Consider the linear map $A:{\mathbb{R}}^3\to {\mathbb{R}}^2$ represented by the rectangular matrixTo compute its kernel, solve the homogeneous linear system $x+2y=0$, $y+z=0$. Taking $y=t$ gives $x=-2t$, $z=-t$, soThus $v$ represents a null direction of a linear map: decreasing the first input by two, increasing the second by one, and decreasing the third by one changes neither output. Solving the homogeneous linear system is the concrete computation behind a kernel; the column space instead decides which outputs are attainable.^[ref]

Now prescribe the nonzero output $b=(3,2{)}^T$. The linear system $Au=b$ becomes $x+2y=3$, $y+z=2$. Again take $y=t$:Direct substitution gives $A{u}_0=(3,2{)}^T$, and $A(u_0+tv)=A{u}_0+tAv=b$. Conversely, the two linear equations force exactly this form, so no solutions have been omitted. This fiber is an affine subspace of dimension one in the three-dimensional input vector space. It is parallel to the kernel, but does not pass through the origin. For instance, $u_0=(3,0,2{)}^T$ and $u_1=(1,1,1{)}^T$ both give $b$, while their difference $u_1-u_0=v$ gives zero. Adding $u_0$ and $u_1$ gives output $2b$, which is another way to see that this nonzero-output fiber is not a vector subspace.

The first and third columns of $A$ are $(1,0{)}^T$ and $(0,1{)}^T$, a basis of the output vector space. Hence $A$ has matrix rank two and reaches every output. The rank-nullity theorem predicts nullity $3-2=1$ before we solve any linear system. It provides a useful completeness check: one nonzero kernel vector already forms a basis here, so a second independent null direction of a linear map would signal a calculation error. In general, matrix rank $r$ for an $m\times n$ matrix leaves $n-r$ independent kernel directions, rather than $m-r$.^[ref]

The row space of a matrix is the span of its rows, and its column space is the span of its columns. Both have dimension equal to the matrix rank, though they lie in different ambient coordinate spaces for a rectangular matrix.

A two-way analysis of variance with the full interaction and one observation in each observed factor cell has one independently varying fitted cell mean per observation. A cell-indicator design matrix has full row matrix rank, even when some combinations are missing, so the model is a saturated statistical model. Its residual sum of squares is zero and its residual degrees of freedom are zero. Missing combinations make some coefficients nonidentifiable; they do not restore a pure-error estimate. Standard errors and an ordinary residual-based F-test for interactions therefore cannot be recovered merely by fitting this larger model.

In a two-factor tensor product over a field, a pure tensor is also called a separable or decomposable tensor: it can be expressed as one product $v\otimes w$. Every tensor is a finite sum of pure tensors, but a sum need not itself be a pure tensor.^[ref]

For finite-dimensional vector spaces, the tensor-product coefficient matrix gives a decisive test: a nonzero tensor is a pure tensor exactly when its matrix rank is one. Indeed, every column of $v{w}^T$ is a scalar multiple of $v$. Conversely, if all columns of a nonzero matrix are multiples of one nonzero column $v$, collect their multipliers in $w$ to obtain $C=v{w}^T$. The zero tensor is also a pure tensor, for example $0\otimes w$, but its matrix rank is zero.

In ${\mathbb{R}}^2{\otimes }_{\mathbb{R}}{\mathbb{R}}^2$, the tensoris nonseparable: its matrix rank is two and its determinant is one, whereas $\det (v{w}^T)=0$. Directly, trying $t=(a{e}_1+b{e}_2)\otimes (c{f}_1+d{f}_2)$ requires $ac=bd=1$ and $ad=bc=0$. The first two equations force all four scalars nonzero, contradicting the others. In contrast, products sharing a factor do combine: $e_1\otimes f_1+e_1\otimes f_2=e_1\otimes (f_1+f_2)$. Thus being written as two summands alone does not establish nonseparability.

Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$, and samples vectors $y$ satisfying $y\cdot p=0$ over ${\mathbb{F}}_2$. Repeated samples and Gaussian elimination recover $p$ with $O(n)$ oracle queries and polynomial computation.

To solve Simon's problem, prepare a uniform quantum superposition, evaluate the function coherently into a second quantum register, and perform Simon Fourier sampling on the first. Each run produces a uniform binary string $z$ with $z\cdot s=0$ over the two-element field. Once the observed rows have matrix rank $n-1$, Gaussian elimination recovers $s$ as the unique nonzero element of their kernel. The random spanning of a binary vector space bounds the required number of runs.

An $n\times n$ square matrix $A$ over a field, with $n\ge 1$, is singular when it has no matrix inverse. Geometrically, its linear map loses at least one input direction: some nonzero vector $v$ satisfies $Av=0$, so $A(x+v)=Ax$. Over the real numbers, the following family makes that loss visible:

For this diagonal matrix, $\det A(t)=t$. Whenever $t\ne 0$, the input can be recovered as $(x,y)=(b_1,b_2/t)$ and the kernel is $\{0\}$. At $t=0$, the kernel becomes $\mathrm{span}\{(0,1)\}$: the entire second coordinate is forgotten. Consequently $A(0)x=(b_1,b_2)$ has no solution if $b_2\ne 0$, and has the solution straight line $x=(b_1,s)$, $s\in \mathbb{R}$, if $b_2=0$. A singular matrix therefore need not make a particular linear system inconsistent; it prevents unique recovery when that linear system is consistent.

For an $n\times n$ square matrix, all these tests describe the same failure:Here $\mathbb{F}$ is the field of scalars. Equivalently, the columns are linearly dependent, the linear map is neither injective nor surjective, and some outputs cannot be reached. See the invertible matrix equivalences and Strang's MIT 18.06SC lecture summary, Multiplication and inverse matrices, p. 2. Over an infinite field, every consistent linear system for a singular matrix has infinitely many solutions; over a finite field with $q$ elements and nullity $d$, it has exactly $q^d$ solutions. This follows by adding each kernel vector to one solution.

The square hypothesis is essential. For an $m\times n$ matrix, injectivity means matrix rank $n$ (full column rank), whereas surjectivity means matrix rank $m$ (full row rank). A rectangular matrix can satisfy one condition without the other; its kernel and image of a linear map give the useful tests without calling it a singular matrix.

Exact singularity also differs from sensitivity. For $0<|t|\le 1$, $A(t)$ is an invertible matrix, but its smallest singular value is $|t|$ and its condition number in Euclidean norm is $1/|t|$. A change $\delta b=(0,\epsilon )$ changes the recovered input by $\delta x=(0,\epsilon /t)$: with $t=1/100$ and $\epsilon =1/1000$, an output change of $0.001$ causes an input change of $0.1$. These are exact toy values, not measurements. The condition number quantifies this sensitivity before a direction is lost; see Steve Marschner, Condition numbers, §2. A small determinant alone is not a reliable sensitivity test: $\epsilon I_2$ has determinant ${\epsilon }^2$ yet condition number one for every nonzero real $\epsilon$, since both singular values shrink equally.

The singular values of a matrix measure stretching of Euclidean norm. They are the nonnegative square roots of the eigenvalues of $A^{\ast }A$, counting the $\min (m,n)$ diagonal slots of the singular value decomposition; when $n>m$, $A^{\ast }A$ has additional zero eigenvalues. Nonnegativity follows from $x^{\ast }{A}^{\ast }Ax=\Vert Ax{\Vert }_2^2\ge 0$, so $A^{\ast }A$ is a positive semidefinite matrix. For the preceding $2\times 2$ matrix,Both have eigenvalues $25,1$, giving singular values $5,1$. In particular,Here the operator norm uses Euclidean norm: no unit vector stretches more than fivefold. Zero singular values identify lost directions; the number of positive singular values equals the matrix rank. This summarizes both amplification and information loss with nonnegative numbers.^[ref]

Small positive singular values also explain sensitivity in an inverse problem. For a square invertible matrix, the matrix inverse sends $u_j$ to $v_j/{\sigma }_j$: a weak forward response becomes strong inverse amplification. The condition number for Euclidean norm is ${\sigma }_1/{\sigma }_n$, equal to $5$ in our example. To see a larger effect, keep the same right singular vectors but change the second singular value to $\epsilon =0.01$:The output perturbation has Euclidean norm $0.001$, but the recovered input changes by $0.1$. Its hundredfold amplification follows from the direction of the perturbation, not just its size. The condition number is now $500$; it measures the disparity between the strongest and weakest responses.^[ref]

The singular value decomposition separates any matrix into input directions, stretching factors, and output directions. Every $m\times n$ complex matrix admitsHere $U,V$ are unitary matrices, $V^{\ast }=V^{†}$ is the conjugate transpose, and $\Sigma$ is a rectangular diagonal matrix. Its $p=\min (m,n)$ diagonal entries are the singular values, ordered ${\sigma }_1\ge \cdots \ge {\sigma }_p\ge 0$. We use the conventional letters: $V$ contains the right singular vectors $v_j$, while $U$ contains the left singular vectors $u_j$. Writing $A=V\Sigma U^{†}$ instead merely swaps these two matrix names; it requires swapping their roles consistently. For real matrices, choose orthogonal matrices and replace the conjugate transpose with the transpose.^[ref]

Reading from right to left, $V^{\ast }$ expresses the input in an orthonormal basis, $\Sigma$ stretches or annihilates those coordinates, and $U$ assembles the output in another orthonormal basis. Unlike matrix similarity, the input and output bases can differ, and even have different sizes. A $3\times 2$ matrix has full factors of sizes $3\times 3$, $3\times 2$, and $2\times 2$. If its matrix rank is $2$, one can retain only the active columns, giving sizes $3\times 2$, $2\times 2$, and $2\times 2$ for $U_r,{\Sigma }_r,V_r^{\ast }$; the full $U$ additionally describes an unused output direction.

For a fully computed nonsymmetric example, takeMultiplication gives $U\Sigma V^T=A$. The right singular vectors are $v_1=(3,4{)}^T/5$ and $v_2=(-4,3{)}^T/5$; their images are $A{v}_1=(5,0{)}^T$ and $A{v}_2=(0,1{)}^T$. Thus, parametrizing the unit circle by $x=v_1\cos t+v_2\sin t$ gives $Ax=(5\cos t,\sin t{)}^T$. Its image is the ellipse $y_1^2/25+y_2^2=1$. The two singular values are its semiaxis lengths, and the left singular vectors point along its axes. The singular value decomposition finds precisely the perpendicular input directions whose images stay perpendicular.

For compression, write the matrix as a sum of outer products and retain the largest terms:where $r$ is the matrix rank. Among all matrices of matrix rank at most $k$, $A_k$ minimizes the Frobenius norm error; this is the Eckart-Young-Mirsky theorem. The operator norm error is ${\sigma }_{k+1}$ for $k<r$. These statements concern specified norms, rather than guaranteeing that discarded details are visually or scientifically unimportant.^[ref]

Consider an $8\times 10$ brightness matrix $B=p{q}^T+a{b}^T/2$, withand $a_i=(-1{)}^{i-1}$, $b_j=(-1{)}^{j-1}$. The broad bright patch $p{q}^T$ and alternating checkerboard $a{b}^T/2$ have orthogonal row and column directions: $p^{T}a=q^{T}b=0$. Their singular values are $\sqrt{60\cdot 110}=\sqrt{6600}$ and $\sqrt{8\cdot 10}/2=\sqrt{20}$. This low-rank approximation keeps the first outer product, giving $B_1=p{q}^T$, with Frobenius norm error $\sqrt{20}\approx 4.472$ and relative error $\sqrt{20/6620}\approx 5.50\%$. For example, $B_{11}=1.5$ becomes $1$, and $B_{12}=1.5$ becomes $2$: every entry changes by $0.5$ in magnitude. The discarded pattern is small but entirely lost.

For this illustrative image compression, storing one normalized left singular vector, one normalized right singular vector, and one singular value requires $8+10+1=19$ scalars instead of $80$. This counts scalars at equal precision, before storage overhead. In general, $k(m+n+1)$ scalars beat $mn$ only for sufficiently small $k$, and small error requires a small discarded sum of squared singular values. The usefulness comes from measuring the tradeoff before throwing information away.^[ref]

For equally sized matrices, corresponding ordered singular values differ by at most the spectral norm of the perturbation. Indeed, let $B_{j-1}$ be a best approximation of matrix rank at most $j-1$. The Eckart-Young-Mirsky theorem and the triangle inequality give ${\sigma }_j(A)\le \Vert A-B_{j-1}{\Vert }_2\le \Vert A-B{\Vert }_2+{\sigma }_j(B)$. Interchanging $A,B$ proves the bound.

For a nonzero matrix $A$, the operator norm induced by the Euclidean norm satisfies $\Vert A^{+}{\Vert }_2=1/{\sigma }_{\min ,+}$, where ${\sigma }_{\min ,+}$ is its smallest positive singular value. The singular value decomposition makes the danger visible: a small nonzero stretch becomes a large amplification of errors when inverted.

For instance, when $\epsilon >0$,A data perturbation $(0,\eta {)}^T$ changes the reconstructed input by $(0,\eta /\epsilon {)}^T$. At $\epsilon =0$, however, the pseudoinverse is $\mathrm{diag}(1,0)$: exactly zero and merely small are different cases. Thus the pseudoinverse need not be continuous across a change of matrix rank. With uncertain data, truncated singular value decomposition or Tikhonov regularization can trade exact inversion of weak directions for stability; the cutoff or penalty adds a modelling choice.

The image of the linear map $A+B$ is contained in the sum of the images of $A$ and $B$. Since the dimension of a vector space of this sum is at most the sum of their dimensions, matrix rank is subadditive. Iteration shows that a sum of $r$ matrices of matrix rank at most one has matrix rank at most $r$, over any field.

A system of linear equations imposes several linear equations on the same unknowns. In the compact form $Ax=b$, the matrix $A$ contains their coefficients, the vector $x$ contains the unknowns, and the vector $b$ contains the required outputs. Over the real numbers, the following examples exhibit the three possible outcomes: one solution, infinitely many solutions, or no solution.

For $x+y=3$ and $x-y=1$, adding the two linear equations gives $2x=4$, hence $x=2$ and $y=1$. Each linear equation describes a line in the plane; the two lines meet only at $(2,1)$. Substitution checks both requirements: $2+1=3$ and $2-1=1$. The two measurements together determine both unknowns.

Keeping only $x+y=3$ leaves a whole line of solutions:For instance, $t=0,1,3$ gives $(3,0),(2,1),(0,3)$. The direction $(-1,1)$ belongs to the kernel of the linear map $(x,y)\mapsto x+y$: its two contributions cancel. Moving in that direction changes the unknowns without changing their measured sum. The solution line is an affine space, translated away from the origin.

For $x+y=3$ and $2x+2y=7$, the second linear equation instead demands $x+y=3.5$. The parallel lines never meet. In the augmented matrix, subtracting twice the first row from the second is an elementary row operation that exposes the contradiction:The last row says $0=1$. A zero row of coefficients is harmless only when its appended entry is also zero.

The column viewpoint unifies these pictures. If $a_j$ are the columns of $A$, then $Ax={\sum }_j{x}_j{a}_j$: a linear combination of those columns. A linear system is consistent precisely when $b$ lies in the column space, the image of a linear map represented by $A$. Once one solution $x_0$ is known, every solution is $x_0+h$ with $h\in \ker A$, since $A(x_0+h)=b+0$. Conversely, subtracting any two solutions gives an element of the kernel. Thus the kernel measures freedom, while the image of a linear map decides existence. A consistent linear system has a unique solution exactly when its kernel is $\{0\}$.^[ref]

Counting linear equations alone does not tell us how much information is present. If the second requirement were $2x+2y=6$, it would repeat $x+y=3$, so the two linear equations would still leave the same solution line. The matrix rank counts independent requirements. For a consistent linear system with $n$ unknowns and matrix rank $r$, the rank-nullity theorem gives $n-r$ as the dimension of the kernel. This is the number of independent directions in which a solution can move. In the single-measurement example, one measured combination leaves one direction of freedom; in the sum-and-difference example, neither unknown can change without changing an output.

For an embedded regular surface $M\subseteq {\mathbb{R}}^3$ and $p\in M$, the affine tangent plane isIt is a set of points through $p$, whereas the tangent space $T_{p}M$ is a vector space of displacements with zero vector. Some texts also call that two-dimensional tangent space the tangent plane; here the translation by $p$ distinguishes the two uses. For a regular parametric surface $X(u,v)$ with $p=X(u_0,v_0)$,where the partial derivatives are evaluated at $(u_0,v_0)$. Regularity means that these tangent vectors are linearly independent, equivalently $X_u\times X_v\ne 0$. Their cross product is a normal vector. ^[ref]

For an implicit regular surface $F(x,y,z)=0$, require a smooth function $F$ with $\nabla F(p)\ne 0$. ThenDifferentiating $F(\gamma (t))=0$ proves that every surface velocity lies in the displayed kernel of a linear map; the implicit function theorem gives a local graph with two independent coordinates, proving equality. The gradient is the normal vector with respect to the ambient dot product. ^[ref]

For the sphere $F(r)=r\cdot r-R^2$, $\nabla F(p)=2p\ne 0$, and the affine tangent plane has equation $p\cdot r=R^2$. At the unit sphere's north pole $p=(0,0,1)$, compare the plane $z=1$ with the displacement tangent space $v_z=0$. The regular parametric surface $X(u,v)=(u,v,\sqrt{1-u^2-v^2})$, for $u^2+v^2<1$, gives $X_u(0,0)=(1,0,0)$ and $X_v(0,0)=(0,1,0)$, confirming the same answer.

This analytical illustration shows a unit sphere and a vertical cross-section. The smooth curves ${\gamma }_1(t)=(\sin t,0,\cos t)$ and ${\gamma }_2(t)=(0,\sin t,\cos t)$ give the two displayed tangent vectors at $p$. The straight point $p+tv$ for any nonzero $v\in T_p{S}^2$ is outside the sphere when $t\ne 0$, since $\Vert p+tv{\Vert }^2=1+t^2\Vert v{\Vert }^2$. A tangent plane therefore captures first-order motion, not an exact patch of the regular surface.

The same idea makes local approximation useful. For the graph of a function $z=f(x,y)$ with $f$ a smooth function, the affine tangent plane is $z=f(a,b)+f_x(a,b)(x-a)+f_y(a,b)(y-b)$. ^[ref] With continuous second partial derivatives, the vertical error is $O((x-a{)}^2+(y-b{)}^2)$ in Big O notation. On the unit sphere near its north pole, $\sqrt{1-u^2-v^2}=1-\frac{1}{2}(u^2+v^2)+O((u^2+v^2{)}^2)$: the tangent plane loses quadratic bending while preserving all first-order velocities.

A failed regularity test needs interpretation. Replacing the sphere equation by $G(r)=(r\cdot r-1{)}^2=0$ makes $\nabla G=0$ everywhere on the same perfectly regular sphere, so this defining smooth function cannot recover its tangent plane. Similarly, the usual spherical parametric surface loses matrix rank at the poles, while the graph parametrization above remains regular there. A vanishing gradient or degenerate parametrization invalidates that calculation; it alone does not prove that the underlying geometry has no tangent plane.

A linear map $T:V\to W$ has a trivial kernel when $\ker T=\{0_V\}$: the zero vector is the only input producing the zero output. The kernel is a singleton set, not the empty set, because every linear map sends zero to zero. Equivalently, its nullity is zero and $T$ is injective. This holds even without a finite-dimensional hypothesis; see Linear Algebra Done Right by Sheldon Axler (4th edition).

The reason this zero-output test controls all outputs is linearity:With a trivial kernel, equal outputs force equal inputs. Therefore every equation $T(x)=b$ has at most one solution. Existence is a separate question: $b$ must belong to the image of a linear map. In the fiber description under nullity, $x_0+\{0\}$ is just the single point $x_0$.

For example, the linear map $J:{\mathbb{R}}^2\to {\mathbb{R}}^3$, $J(x,y)=(x,y,0)$, has trivial kernel and full column rank:The output $(3,4,0)$ comes from exactly $(3,4)$, while $(3,4,1)$ is unreachable. Conversely, $P:{\mathbb{R}}^3\to {\mathbb{R}}^2$, $P(x,y,z)=(x,y)$, is surjective and has full row rank, but its kernel is $\mathrm{span}\{(0,0,1)\}$: every output $(a,b)$ comes from the solution straight line $(a,b,s)$.

For an $m\times n$ matrix, a trivial kernel is equivalent to matrix rank $n$ and linear independence of its columns. It can therefore occur only if $n\le m$. If $m=n$, the rank-nullity theorem also forces surjectivity, giving an invertible matrix; if $m>n$, the example $J$ shows why unique recovery of reachable inputs does not imply that every output is reachable. Finally, a trivial kernel guarantees exact uniqueness without guaranteeing numerical stability: the singular matrix example $A(t)$ has trivial kernel for every $t\ne 0$, even as its condition number grows without bound when $t$ approaches zero.

The two-factor tensor rank is the smallest number of pure tensors whose sum equals $t$, with zero allowed as the empty sum. For two finite-dimensional vector spaces over the same field, it equals the matrix rank of the tensor-product coefficient matrix. A sum of $r$ outer products has column space contained in the span of their $r$ first factors, so its matrix rank is at most $r$. Conversely, choose a basis $u_1,\dots ,u_r$ for the column space, express each column in that basis, and collect the coefficients into row vectors $w_k^T$. This yields $C={\sum }_{k=1}^r{u}_k{w}_k^T$, hence a sum of $r$ pure tensors.

The pure tensor $(2,1)\otimes (-1,3)$ therefore has two-factor tensor rank one, whereas $e_1\otimes f_1+e_2\otimes f_2$ has two-factor tensor rank two. Both have two factors: the number of factors and the minimum number of product summands are different counts. Over the real numbers, the singular value decomposition supplies a useful decomposition $C={\sum }_k{\sigma }_k{u}_k{v}_k^T$, with one nonzero term per matrix rank. The two-factor rank equality does not extend to three or more factors by merely choosing one matrix layout.