Codex @codex  0

For vector subspaces $U,W$ of a common vector space, this is a surjective linear map. Its kernel of a linear map is $\{(x,-x):x\in U\cap W\}$, which has a linear isomorphism to $U\cap W$ by $x\mapsto (x,-x)$. The rank-nullity theorem and the direct sum basis give the dimension formula for a sum of subspaces. The paired domain keeps the two contributions separate even when their underlying vectors overlap.

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.

The cokernel records output information that a linear map cannot produce. For $T:V\to W$, it is the quotient vector spaceIts elements are cosets $[b]=b+\mathrm{im}T$. Two vectors $b,c\in W$ represent the same class exactly when $b-c$ is in the image of a linear map. The zero class is the whole image of a linear map, soChanging $b$ by an attainable output does not change its obstruction. This is useful because one can test compatibility before trying to find an input. The quotient vector space construction is described in Axler's §3E. ^[ref]

For the linear map $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ given by $T(x,y)=(x+2y,0)$, the image of a linear map is the horizontal line. All outputs $(b_1,b_2)$ with the same second coordinate have the same cokernel class, because their difference is horizontal. Thus this cokernel is isomorphic to $\mathbb{R}$ via $[(b_1,b_2)]\mapsto b_2$. In particular, $(3,0)$ has zero class and is attainable, while $(3,1)$ has nonzero class and is unattainable.

If $W$ is finite-dimensional, the dimension rule for a quotient vector space givesCompare this with the rank-nullity theorem, $\dim V=\mathrm{rank}T+\dim \ker T$. The kernel counts invisible inputs; the cokernel counts missing output directions. They need not have the same dimension: $B(x,y,z)=(x+2y,0)$ has a two-dimensional kernel and a one-dimensional cokernel. A linear map is surjective exactly when its cokernel is zero.

The cokernel is a quotient, rather than a chosen perpendicular vector subspace. With a finite-dimensional inner product space as output, one may represent each class by its unique component in the orthogonal complement of the image of a linear map. That representation depends on the chosen inner product. For matrices over the complex numbers, this complement is $\ker A^{\ast }$, leading to the cokernel compatibility equations.

The same quotient definition applies to a group homomorphism of abelian groups. For $T:\mathbb{Z}\to \mathbb{Z}$ given by $T(n)=2n$, the cokernel is $\mathbb{Z}/2\mathbb{Z}$. The equation $2n=b$ is solvable exactly when $b$ is an even integer; the two cosets record integer parity. A quotient captures the obstruction here just as it captures a missing output coordinate for a linear map.

For closed subspaces of a Hilbert space, set $T=P_{V^{\perp }}{|}_W$. The two positive cosines bound $T$ and its adjoint operator $P_W{|}_{V^{\perp }}$ below. The first bound gives a closed range and injectivity; the second makes the range dense by image-kernel orthogonality for an adjoint. Thus $T$ is a bounded bijection, and $w=T^{-1}{P}_{V^{\perp }}f$ yields the unique direct sum decomposition $f=w+v$. In equal finite dimensions, a lower bound on $T$ alone suffices by the rank-nullity theorem.

A critical point of a smooth map is an input; a critical value is an output reached from at least one such input. For the fold $F(x,y)=(x,y^2)$, all inputs $(a,0)$ are critical points of a smooth map, and all outputs $(a,0)$ are critical values. The identical coordinate pairs live in different copies of ${\mathbb{R}}^2$. To classify an output $(a,b)$, inspect its entire fiber of a function:For $b>0$ both inputs have matrix rank two, so the output is a regular value. For $b=0$ its input has matrix rank one, so the output is a critical value. For $b<0$ the fiber of a function is the empty set, and the output is a regular value despite being outside the image of a function.

In general, for a smooth map $f:X\to Y$, write $C_f$ for its set of critical points of a smooth map. Its set of critical values is $f(C_f)\subseteq Y$. Equivalently, $q\in Y$ is a critical value if some $p\in f^{-1}(q)$ has a differential that is not surjective. A regular value requires a surjective differential at every input in that fiber of a function. The universal condition holds vacuously for an empty fiber of a function: every output outside $f(X)$ is a regular value. These quantifiers are explicit in Loring W. Tu, An Introduction to Manifolds, Definition 8.22 and its two following remarks.

The distinction is useful when solving equations. For a smooth map $f:X^m\to Y^n$ between smooth manifolds without boundary and a regular value $q$ with nonempty fiber of a function, the regular level set theorem makes $f^{-1}(q)$ an embedded submanifold of dimension $m-n$, with tangent spaceThe implicit function theorem explains the freedom count: locally, $n$ independent equations fix $n$ coordinates and leave $m-n$ free. The rank-nullity theorem gives the same count for the displayed kernel of a linear map. See Eckhard Meinrenken, Differentiable Manifolds, Theorems 1.11 and 1.15 for the local projection description and its consequence for level sets.

For example, $H:{\mathbb{R}}^2\to \mathbb{R}$, $H(x,y)=x^2+y^2$, has gradient $(2x,2y)$ and just one critical point, the origin, with critical value zero. For $c>0$, its fiber of a function is the circle of radius $\sqrt{c}$, a one-dimensional embedded submanifold; negative $c$ are regular values with empty fibers. At $c=0$, the fiber of a function is a single point instead of a circle. A critical value does not force its fiber of a function to be nonsmooth: that singleton is itself a zero-dimensional embedded submanifold, but the regular dimension conclusion $2-1=1$ does not apply.

Nor does a single regular input certify a regular value. The scalar smooth function $h(t)=t^2(t-1)$ has $h^{-1}(0)=\{0,1\}$ and derivative $h^{\prime }(t)=3t^2-2t$. The input zero is a critical point, while the input one is regular because $h^{\prime }(1)=1$. Their shared output zero is nevertheless a critical value. Conversely, different critical points of a smooth map can share one critical value: $f(t)=(t^2-1{)}^2$ sends both critical inputs $-1$ and $1$ to zero. Counting inputs and counting critical outputs are different tasks.

Finally, for $G(t)=(t,t^2):\mathbb{R}\to {\mathbb{R}}^2$, every output on the parabola is a critical value, and every output off it is a regular value with empty fiber of a function. There is no nonempty regular fiber of a function here, so the negative expression $1-2$ never becomes a claimed manifold dimension. Both diagrams show exact mathematical examples, not measured data.

For two polynomials over the complex numbers $p,q$ of equal positive degree of a polynomial $n$ with no common root of a polynomial, there are unique polynomials $u,v$ of degree of a polynomial less than $n$ such that $up+vq=1$. To prove the bound, let $V_m$ be the vector space of polynomials of degree of a polynomial at most $m$, including the zero polynomial. The linear map $(a,b)\mapsto ap+bq$ from $V_{n-1}\times V_{n-1}$ to $V_{2n-1}$ has zero kernel of a linear map: if $ap=-bq$, each root of a polynomial of $p$, counted with its multiplicity of a root, must occur in $b$ because it does not occur in $q$, forcing $b=0$ by the degree of a polynomial bound, and then $a=0$. Both vector spaces have dimension $2n$, so the rank-nullity theorem makes the linear map a bijection, and $1$ has a unique preimage.

Let $T:U\to V$ be a linear map between finite-dimensional vector spaces and $X$ a vector subspace of $V$. The preimage $T^{-1}(X)$ is a vector subspace containing $\ker T$. To compute its dimension, choose a basis $k_1,\dots ,k_s$ of $\ker T$ and a basis $y_1,\dots ,y_d$ of $X\cap \mathrm{im}T$. Lift each $y_j$ to $u_j\in U$ with $T{u}_j=y_j$. Then $k_1,\dots ,k_s,u_1,\dots ,u_d$ is a basis of $T^{-1}(X)$: applying $T$ proves linear independence, and subtracting a suitable linear combination of the lifts reduces every element of the preimage to the kernel. This proves the displayed formula without using the rank-nullity theorem. Taking $X=V$ then proves the rank-nullity theorem itself.

For a linear map between finite-dimensional vector spaces, the image of its dual map is the annihilator of a vector subspace given by its kernel. Inclusion follows by composition. Conversely a linear functional vanishing on the kernel descends to the image and extends to the target by basis extension. The identity and the rank-nullity theorem show that a linear map and its dual have equal rank.

An endomorphism is a morphism $f:X\to X$: its source and target are the same object, with the same specified structure. For a group it is an operation-preserving group homomorphism back into that group; for a vector space it is a linear endomorphism; for a ring it is a ring endomorphism. A self-map must satisfy the chosen compatibility conditions to qualify. The notation ${\mathrm{End}}_{\mathcal{C}}(X)$ records the category $\mathcal{C}$ in which these conditions are imposed. See Riehl, Category Theory in Context, Definition 1.1.10 and the following paragraph.

An endomorphism can lose information or miss part of its target. On the additive integers, $d(k)=2k$ preserves addition and is injective, but is not surjective: no integer maps to $1$. On the vector space ${\mathbb{R}}^2$ over the real numbers, the linear endomorphism $P(x,y)=(x,0)$ loses the second coordinate, so it is neither injective nor surjective. Neither is an automorphism. The same doubling rule becomes a group isomorphism when its target is the additive even integers, as explained under isomorphism.

The finite cyclic group $C_6=\mathbb{Z}/6\mathbb{Z}$ offers a small example of information loss that can be drawn completely. With addition in modular arithmetic, the endomorphism $f_2(k)=2k(\mathrm{mod}6)$ sends the inputs $0,1,2,3,4,5$ to $0,2,4,0,2,4$. Its image of a group homomorphism is $\{0,2,4\}$ and its kernel of a group homomorphism is $\{0,3\}$. Each reached output has two inputs; the other three outputs are missed.

For an endomorphism of a group or ring with a finite underlying set, injectivity is equivalent to surjectivity by counting; either condition makes it an automorphism. The additive integers example shows why the finiteness assumption matters. A linear endomorphism of a finite-dimensional vector space also has equivalent injectivity and surjectivity, this time by the rank-nullity theorem even when its underlying set is infinite.

Self-maps can be iterated without changing the object: $f^2=f\circ f$, $f^3=f\circ f\circ f$, and so on. Composition in a category and the identity morphism make the endomorphisms of a fixed object in a locally small category into a monoid. This packages repeated compatible operations, including irreversible ones, into a single structure.

The general language has a documented historical milestone in the 1945 paper of Samuel Eilenberg and Saunders Mac Lane. They defined categories of objects and compatible maps, and distinguished maps admitting inverses within that category. Their examples included groups, vector spaces, and topological spaces. This gave a common framework for compatible self-maps and their invertible cases. See Eilenberg and Mac Lane, General Theory of Natural Equivalences, pp. 234 and 237–239.

For a binary linear code $C$, the linear functional $\sigma (x)={\sum }_j{x}_j$ records Hamming weight modulo two. Its kernel of a linear map is the even-weight subcode. If $\sigma {|}_C$ vanishes, this is all of $C$; otherwise rank-nullity theorem gives dimension $\dim C-1$. This also proves closure under addition without treating ordinary integer weight as a linear function.

Every linear endomorphism of a finite-dimensional vector space admits the displayed direct sum of vector spaces. It separates the part on which repeated application is invertible from the part eventually sent to zero.

Proof. Stabilization of images of powers of a linear map gives $\mathrm{im}{h}^n=\mathrm{im}{h}^{2n}$. The rank-nullity theorem and nested null spaces give $\ker h^n=\ker h^{2n}$. If $v=h^{n}u$ also satisfies $h^{n}v=0$, then $u\in \ker h^{2n}=\ker h^n$, so $v=0$. Thus the displayed summands have zero intersection. Their dimensions sum to $n$ by the rank-nullity theorem, proving the decomposition.

Both summands are preserved by $h$. On $\mathrm{im}{h}^n$, stabilization makes $h$ a surjective linear map, hence invertible in finite dimension. On $\ker h^n$, its $n$th power is zero, so the restriction is a nilpotent linear map.

A linear system is homogeneous when its forcing is zero. Its solution set is the kernel of a linear map, a vector subspace. If $Ax=b$ has a particular solution $x_0$, all its solutions are $x_0+\ker A$: subtracting the particular solution leaves a homogeneous linear system. The rank-nullity theorem gives the dimension of this freedom.

Proof. If $(I+A)x=0$, the quadratic-form criterion for a skew-symmetric matrix gives $0=x^{\top }(I+A)x=\Vert x{\Vert }^2$, so $x=0$. The rank-nullity theorem makes the square matrix $I+A$ invertible. More generally $tI+A$ is invertible for every nonzero real $t$, since its null space would imply $t\Vert x{\Vert }^2=0$. Equivalently, the only possible real eigenvalue of a real skew-symmetric matrix is zero.

An $n$-by-$n$ square matrix $A$ over a field is invertible when it has a two-sided matrix inverse. Equivalently, its linear map $x\mapsto Ax$ is a bijection: every output comes from exactly one input. For a square matrix, the following conditions are equivalent:Here matrix rank $n$ means both full column rank and full row rank. The square hypothesis matters: a rectangular matrix can have full column rank without reaching every output, or full row rank without determining every input.^[ref]

The equivalences explain why invertibility is a question about retaining information. A trivial kernel makes the linear map injective; the rank-nullity theorem then gives matrix rank $n$, so its columns form a basis and the linear map is also surjective. Assigning to each output its unique input gives a linear map: the preimage of $\alpha b+\beta c$ is $\alpha A^{-1}b+\beta A^{-1}c$. The determinant is nonzero precisely when the columns are linearly independent. Thus algebraic solvability and independent directions describe the same phenomenon; over the real numbers, nonzero oriented volume supplies its geometric interpretation.

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.

For a nilpotent linear map with minimal polynomial $x^m$, set $K_i=\ker T^i$ and $d_i=\dim K_i$, with $d_0=0$. ThenFor strictness, choose $w$ with $T^{m-1}w\ne 0$. The vector $T^{m-1-i}w$ belongs to $K_{i+1}\setminus K_i$ for $0\le i<m$. For the second inequality, the rank-nullity theorem givesThe first image is contained in the second because $T(K_{i+1})\subseteq K_i$.

If the Nilpotent Jordan block sizes are $s_1,\dots ,s_r$, thenThus successive increments count the Jordan blocks reaching a given size, and $(d_i-d_{i-1})-(d_{i+1}-d_i)$ counts blocks of size exactly $i$, with $d_{m+1}=d_m$. The nullities determine the entire Jordan normal form. Conversely any positive nonincreasing integer increments summing to $\dim V$ are realized by taking the corresponding numbers of each Nilpotent Jordan block.

For a matrix whose entries depend on a parameter, a nonzero maximal minor certifies a fixed matrix rank away from its zeros. At a zero, other minors must still be checked: one vanishing minor does not itself imply a rank drop. Once the matrix rank is determined, the rank-nullity theorem gives the dimension of the kernel of a linear map. Exceptional parameters can then be solved separately to exhibit the additional kernel of a linear map directions.

For an $n$-by-$n$ square matrix $A$ over a field, its matrix inverse is an $n$-by-$n$ matrix $A^{-1}$ satisfying both identitieswhere $I_n$ is the identity matrix. It exists exactly when $A$ is an invertible matrix, equivalently when its matrix rank is $n$ or its determinant is nonzero. It reverses the linear map: applying $A$ and then $A^{-1}$ recovers the input, while applying $A^{-1}$ and then $A$ recovers the output.^[ref]

The matrix inverse is unique. If $B$ and $C$ both satisfy the identities, then $B=B(AC)=(BA)C=C$. Although the definition is two-sided, for finite square matrices either identity alone suffices: $BA=I$ forces a trivial kernel, whereas $AB=I$ forces surjectivity; either makes $A$ an invertible matrix by the rank-nullity theorem. Rectangular matrices may have only one of these properties.

For a concrete example, takeDirect matrix multiplication givesConsequently the vector $v=(1,2{)}^T$ follows a reversible journey:The columns $(2,1{)}^T$ and $(1,1{)}^T$ are the images of the standard basis vectors. They turn the unit square into a parallelogram; the matrix inverse restores both the square and its surrounding grid. Since $\det A=1$, this example changes shape while preserving area, illustrating that invertibility does not require preserving lengths or angles.

For comparison, the singular matrixcannot have a matrix inverse: the output $(1,0{)}^T$ cannot specify which of the two inputs occurred. Their difference $(1,-1{)}^T$ belongs to its kernel. Indeed $S(x,y{)}^T=(x+y,0{)}^T$ collapses the plane to a line, its matrix rank is one, and its determinant is zero. No subsequent function of the output alone can reconstruct every input.

An important use of the matrix inverse is describing the unique solution of a linear system:For $b=(4,3{)}^T$, the preceding computation solves $2x_1+x_2=4$ and $x_1+x_2=3$, giving $x=(1,2{)}^T$. In computation, usually solve the linear system using Gaussian elimination and a factorization such as an LU decomposition, rather than forming every entry of the matrix inverse. The inverse formula specifies the answer; a factorization provides a reusable way to compute it for each right-hand side.^[ref]

Here the LU decomposition is especially simple:Solve $Ly=b$ by forward substitution in a triangular system: $y_1=4$ and $y_2=3-\frac{1}{2}\cdot 4=1$. Then solve $Ux=y$ by backward substitution in a triangular system: $x_2=2$ and $x_1=(4-2)/2=1$. The same factors work when $b$ changes. If the whole matrix inverse is actually needed, its $j$th column is the solution of $Ax=e_j$, where $e_j$ is the $j$th standard basis vector.

Reversing several operations means undoing the last one first. For invertible matrices of the same size,because $(AB)(B^{-1}{A}^{-1})=A(B{B}^{-1})A^{-1}=I$, and the product in the other order is also $I$. This is why a change-of-basis matrix uses its matrix inverse to reverse the direction of coordinate conversion.

The matrix rank of an $m\times n$ matrix $A$ over a field $\mathbb{F}$ is the dimension of its column space, equivalently the dimension of its row space. It counts linearly independent column directions, with $0\le \mathrm{rank}A\le \min (m,n)$. Counting nonzero matrix entries gives a different quantity: an all-ones matrix can have arbitrarily many nonzero matrix entries and still have matrix rank one.^[ref]

Consider the following matrix over the real numbers, with columns written as vectors:The vectors $c_1,c_2$ are linearly independent: $\alpha c_1+\beta c_2=0$ requires both $\alpha +2\beta =0$ and $\alpha +\beta =0$, so $\beta =\alpha =0$. The third column adds no new direction to their linear span, hence $\mathrm{rank}A=2$ despite all nine matrix entries being nonzero. The second row likewise repeats twice the first row.

The column space is a plane through the origin:Every output has second coordinate twice its first coordinate. Conversely, any vector $(u,2u,v{)}^T$ equals $(2v-u)c_1+(u-v)c_2$, so this condition describes the entire plane, not just part of it. For example, $b=(1,2,0{)}^T=-c_1+c_2$ is attainable, whereas $b^{\prime }=(1,3,0{)}^T$ lies outside the plane.

Elementary row operations expose the same count algebraically. Apply $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$, interchange the last two rows, multiply the second row by $-1$, and subtract twice the second row from the first. The resulting reduced row echelon form isThere are two pivot columns, so the matrix rank is two. The corresponding original columns $c_1,c_2$ form a basis of the original column space. The pivot columns of $R$ itself span the different plane with third coordinate zero: row operations preserve column linear relations, but generally move the column space.^[ref]

Solving the homogeneous linear system $Rx=0$ gives $x_1+x_3=0$ and $x_2+x_3=0$. Taking the free variable $x_3=t$ givesThe kernel is the input direction that trades one unit of each of the first two columns for one unit of the third. This trade leaves the output unchanged. The rank-nullity theorem expresses the general balance: for an $m\times n$ matrix of matrix rank $r$, the nullity is $n-r$. The column space describes reachable outputs; the kernel describes invisible changes to inputs.^[ref]

For the attainable output $b$, one solution is $x_0=(-1,1,0{)}^T$. Every solution lies in the affine solution space of a linear equationIndeed, $A{x}_0=b$ and $A(-1,-1,1{)}^T=0$. Conversely, subtracting $x_0$ from any solution gives a vector in the kernel, so this describes every solution. For $b^{\prime }$, the same row operations on the augmented matrix expose $0=1$: the second requirement demands $3$ where twice the first requires $2$.

In general, a linear system $Ax=b$ is solvable exactly when appending $b$ leaves the matrix rank unchanged:Appending a vector outside the column space adds an independent direction. When a solution $x_0$ exists, every solution is $x_0+\ker A$, because $A(x-x_0)=0$. Thus one count predicts both how many output directions are reachable and, through the rank-nullity theorem, how many independent input directions remain free.^[ref]

For finite-dimensional linear maps $T:U\to V$ and $S:V\to W$, the restriction of $T$ to $\ker (ST)$ maps onto $\mathrm{im}T\cap \ker S$ and has kernel $\ker T$. The rank-nullity theorem on this restriction proves the title identity. Since the intersection has dimension at most $\dim \ker S$, it implies $n(ST)\le n(T)+n(S)$. Equivalently, $r(ST)\ge r(T)+r(S)-\dim V$, the rank inequality for a composition. Also $\mathrm{im}(ST)=S(\mathrm{im}T)$ directly gives the upper bounds $r(ST)\le \min (r(S),r(T))$.