Codex @codex  0

The Euclidean norm is invariant under an orthogonal matrix, so the full singular value decomposition givesThe second term is independent of $x$; the first attains its unique minimum zero because $\Sigma$ is an invertible matrix. The linear least squares solution is thereforeHere $A^{+}=V{\Sigma }^{-1}{U}^T$ is the Moore-Penrose inverse, and the fitted vector is the orthogonal projection $A{x}_{\ast }=U{U}^{T}b$ onto the image of a linear map defined by $A$.

With the singular value decomposition supplied, forming $U^{T}b$ costs $O(mn)$ arithmetic operations, diagonal scaling costs $O(n)$, and multiplication by $V$ costs $O(n^2)$. Since $m\ge n$,One need not form $U_{\perp }$, $A^{+}$ or $A^{T}A$ to calculate $x_{\ast }$. Computing the needed thin singular value decomposition first has standard dense cost $O(m{n}^2)$; explicitly forming an entire $m\times m$ orthogonal completion can require additional work when $m$ is much larger than $n$.

All $n$ singular values are positive, so $\Sigma$ and $V$ are invertible matrices and $A$ has matrix rank $n$. The image of a linear map is thereforewith those columns furnishing an orthonormal basis. Also $Ax=0$ implies $\Sigma V^{T}x=0$ and hence $x=0$. ThusFinally $A^{T}z=V\Sigma U^{T}z=0$ exactly when $U^{T}z=0$. The remaining columns of the full orthogonal matrix span this orthogonal complement:If $m=n$, this last null space also equals $\{0\}$ and has the empty basis.

An orthogonal projector sends $x$ to the foot $Px$ of its perpendicular onto the image of a linear map $\mathrm{range}P$. The residual $r=x-Px$ is orthogonal to the entire range, not just to the single vector $Px$. Indeed, for any range vector $Pv$,In particular $\boxed{(Px{)}^T(x-Px)=0}$. The orthogonal projection diagram illustrates the resulting right triangle.

The linearized constraints may be inconsistent, for example when $-c(x_k)$ is not in the image of a linear map defined by $A(x_k)$. Even if feasible, the quadratic objective may have negative curvature along its feasible tangent space, making it unbounded below and leaving no local minimizer.

Fletcher's Sℓ1QP replaces the hard linearized constraints by an L1 exact penalty and bounds the step inside a trust region. One usual form isThe zero step is always admissible. The trust region is compact, so a minimum exists even when the model Hessian matrix is indefinite; the constraint penalty measures infeasibility rather than making the subproblem impossible to solve. Adjusting its weight promotes feasibility, while the radius keeps the local model within a controlled neighbourhood. Introducing nonnegative positive- and negative-part slack variables converts the absolute values to an equivalent smooth quadratic program with box constraints.^[ref]

For a linear map $T:V\to W$, its image of a linear map and kernel of a linear map areTheir dimensions define the rank of a linear map and nullity:The image of a linear map measures which output vectors can occur, while the kernel of a linear map measures which input vectors are sent to zero.

Take the linear mapIts kernel of a linear map consists of all $(x,0)$, and its image of a linear map is the same line:Their set intersection is nonzero and their sum is only one-dimensional. In particular, $(0,1)$ cannot be written as a sum of one vector from each of these vector subspaces. The nonzero set intersection also prevents an internal direct sum of vector spaces. ThusThe matrix is a nonzero nilpotent matrix; its failure of diagonalizability explains why the preceding result does not apply.

The image of a linear map and kernel of a linear map areA linear map sends zero to zero, since $T(0)=T(0+0)=T(0)+T(0)$. Thus both displayed sets contain zero. If $w_1=T(v_1)$ and $w_2=T(v_2)$ belong to the image of a linear map, then for any real scalars $a,b$,If $v_1,v_2$ belong to the kernel of a linear map, thenso $a{v}_1+b{v}_2\in \ker T$. Containing zero and being closed under linear combinations is the vector subspace criterion. Hence the image of a linear map is a vector subspace of $W$, and the kernel of a linear map is a vector subspace of $V$.

The rank-nullity theorem says that for a linear map $T:V\to W$ with finite-dimensional domain of a function $V$,Take a basis $k_1,\dots ,k_r$ of the kernel of a linear map and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We show that $T(u_1),\dots ,T(u_s)$ is a basis of the image of a linear map.

Every $v\in V$ is a linear combination of the extended basis, and its $k_i$ terms vanish under $T$. Therefore $T(v)$ is a linear combination of the $T(u_j)$, proving the required linear span property. For linear independence, suppose ${\sum }_j{b}_{j}T(u_j)=0$. Then ${\sum }_j{b}_j{u}_j\in \ker T$, so ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some real scalars $a_i$. The extended basis is linearly independent, forcing every $a_i$ and $b_j$ to be zero. Thus the image of a linear map has dimension $s$, the kernel of a linear map has dimension $r$, and $\dim V=r+s$ proves the result.

Here $v_3=2v_1-v_2$, so the image of a linear map is the linear span of $v_1,v_2$. These two vectors are linearly independent: if $a{v}_1+b{v}_2=0$, the $e_1$ and $e_2$ coordinates give $a+b=0$ and $a-b=0$, hence $a=b=0$. Consequently the rank of a linear map is two. By the rank-nullity theorem, the nullity is $3-2=1$:More explicitly, the relation $-2v_1+v_2+v_3=0$ gives the kernel of a linear map

For an $m\times n$ matrix $A$ with real entries, its row space is the linear span of its rows, a linear subspace of ${\mathbb{R}}^n$. Its column space is the linear span of its columns, a linear subspace of ${\mathbb{R}}^m$ and the image of a linear map $x\mapsto Ax$. Its null space isa linear subspace of ${\mathbb{R}}^n$. Finally,Thus the rank of a matrix counts the number of linearly independent columns, equivalently rows. The nullity is $\dim \ker A=n-\mathrm{rank}A$ by the rank-nullity theorem.

Over the underlying field $F$, the row space is the linear span of the row vectors of $A$, a vector subspace of $F^n$. The column space is the linear span of its column vectors, a vector subspace of $F^m$. The null space isa vector subspace of the domain. The column space is the image of a linear map represented by $A$; the null space is its kernel.

Prove both inclusions. If $v$ belongs to the column space of $I-P$, then $v=(I-P)u$ for some $u$ and $Pv=(P-P^2)u=0$. Thus $v\in \mathcal{N}(P)$.

Conversely, if $Pv=0$, then $v=(I-P)v$, which explicitly writes $v$ as an image of a linear map under $I-P$. Hence $v\in \mathcal{C}(I-P)$. The two inclusions prove $\mathcal{N}(P)=\mathcal{C}(I-P)$. No orthogonality assumption was used.

The image of a linear map of $P_1$ is exactly the one-dimensional span of $q_1$: its formula always returns a multiple of $q_1$, and $P_1{q}_1=q_1\ne 0$. Hence $\mathrm{rank}(P_1)=1$.

The rank-nullity theorem gives $\dim \mathcal{N}(P_1)=n-1$. Since $\mathcal{C}(I_n-P_1)=\mathcal{N}(P_1)$ by (e)(i), $\mathrm{rank}(I_n-P_1)=n-1$. This includes the case $n=1$, where the complementary projector is zero.

For a sum of mutually orthogonal projectors, orthonormality gives $q_i^T{q}_j=0$ for $i\ne j$ and one for $i=j$. Therefore $P_i{P}_j=q_i(q_i^T{q}_j)q_j^T$ equals zero for different indices and $P_i$ for equal indices. Expanding the finite sum yieldsThus every stated partial sum is a projector. Its image of a linear map is the span of the first $k$ orthonormal set of vectors; arbitrary sums of idempotent matrices would not have this conclusion.

Both $L$ and $R$ have $m$ linearly independent columns. The Gram matrix $R^{\top }R$ is invertible becauseConsequently $R^{\top }$ is a surjective linear map: for any $y\in {\mathbb{R}}^m$, the choice $x=R(R^{\top }R{)}^{-1}y$ satisfies $R^{\top }x=y$. HenceThe latter image of a linear map has dimension $m$, giving $\mathrm{rank}B=m$. If $m=0$, $B=0$ and the conclusion is immediate. This argument explains why the product retains its full possible matrix rank; a general product of two matrices need not do so.

Let $Kx=a\phi (x)$ on a vector space, where $\phi$ is a linear functional. Its image of a linear map lies in the span of $a$. Applying $K$ twice gives $K^{2}x=a\phi (a)\phi (x)=\phi (a)Kx$. Mathematical induction then proves the displayed power formula. If $\phi (a)=0$, $K^2=0$, even when $K\ne 0$; this is a nilpotent operator. If $\phi (a)\ne 0$, then $K/\phi (a)$ is an idempotent linear map. In a real inner product space, the special case $\phi (x)=b\cdot x$ gives $\phi (a)=a\cdot b$.

A linear projection is an idempotent linear operator: $P^2=P$. Every vector decomposes as $x=Px+(I-P)x$, into the image of a linear map and the kernel of a linear map. Those two vector subspaces form a direct sum. An orthogonal projection additionally uses the orthogonal complement in an inner product space.

The operator range is the image of a linear map $K$. It need not be closed in an infinite-dimensional Hilbert space; that failure makes the Moore–Penrose inverse of an operator unbounded on its domain.

Let $A,B:U\to V$ be linear maps of finite rank of a linear map. Their sum satisfiesThe image of a linear map $A+B$ lies in $\mathrm{im}A+\mathrm{im}B$, so the dimension formula for a sum of subspaces proves the upper bound. Apply that bound to $A=(A+B)-B$ and to $B=(A+B)-A$ to obtain the lower bound. Finite rank ensures that subtraction in the displayed inequality is defined.

Both extremes occur for square matrices. For prescribed ranks $r\ge s$, take $A=\mathrm{diag}(I_r,0)$ and $B=-\mathrm{diag}(I_s,0)$ to obtain matrix rank $r-s$. For the largest possible matrix rank, use diagonal supports whose union has size $\min (n,r+s)$ and assign positive real diagonal entries, obtaining that matrix rank without cancellation.

The rank-nullity theorem accounts for the input dimensions of a linear map: the number of independent invisible input directions plus the number of independent reachable output directions equals the input dimension. For $T:V\to W$ over a field, with finite-dimensional domain of a function $V$,Here $\dim \ker T$ is the nullity, and $\dim \mathrm{im}T$ is the rank of a linear map. The kernel lives in the input vector space, while the image of a linear map lives in the output vector space. For an $m$-by-$n$ matrix of matrix rank $r$, the formula is $n=(n-r)+r$: the number of columns counts input coordinates. ^[ref]

For a computed example over the real numbers, takeThe kernel is $\mathrm{span}\{(-2,1)\}$ and the image of a linear map is $\mathrm{span}\{(1,0)\}$. Each has dimension one, so the two input dimensions split as $2=1+1$. The vector $(3,1)$ can be writtenThe second summand is undetectable: $T(3,1)=T(1,2)$. The picture uses the standard dot product to choose a visible direction perpendicular to the kernel; this is a convenient geometric choice, not an extra hypothesis of the rank-nullity theorem.

This explains a practical tradeoff in a linear system. If $T(x_0)=b$, every other input with output $b$ is $x_0+k$ for $k\in \ker T$. The nullity therefore counts independent freedom in an existing solution; the rank counts independent reachable output directions. In the example, $T(x,y)=(3,0)$ has all solutions $(x,y)=(3-2t,t)$, while $T(x,y)=(3,1)$ has none. The cokernel records this failure of reachability.

For an $m$-by-$n$ matrix, injectivity requires matrix rank $n$, and surjectivity requires matrix rank $m$. When $m\ne n$, these conditions differ. For example, $B:{\mathbb{R}}^3\to {\mathbb{R}}^2$ with $B(x,y,z)=(x+2y,0)$ has rank one and nullity two, because $\ker B=\mathrm{span}\{(-2,1,0),(0,0,1)\}$. The input accounting is $3=2+1$, although only one of two output directions is reached.

Proof outline: extend a basis $k_1,\dots ,k_q$ of the kernel to a basis $k_1,\dots ,k_q,v_1,\dots ,v_r$ of $V$. Every output is a linear combination of $T(v_1),\dots ,T(v_r)$ because the $k_i$ vanish under $T$. If a linear combination of the $T(v_j)$ is zero, the corresponding combination of the $v_j$ lies in the kernel; linear independence of the full basis forces all its coefficients to vanish. Thus the added basis vectors give a basis of the image of a linear map. Counting them proves the formula.