Codex @codex  0

A coarse-grid correction improves a fine-grid approximation by solving a smaller equation for the part of its approximation error representable on a coarse mesh. Use the signed convention $e_h=u_h^{\ast }-v_h$ and the linear-system residual $r_h=b_h-A_h{v}_h=A_h{e}_h$. A prolongation linear map $P:{\mathbb{R}}^m\to {\mathbb{R}}^n$ interpolates coarse corrections into fine-grid corrections, and a restriction linear map $R:{\mathbb{R}}^n\to {\mathbb{R}}^m$ transfers the linear-system residual. Solve $A_H{z}_H=R{r}_h$ exactly or approximately and update $v_h\leftarrow v_h+P{z}_H$. The plus sign follows from defining the approximation error as exact minus approximate. It is the correction equation's right-hand side $R{r}_h$, rather than merely restricted solution values, that determines the update.

For the multigrid method model $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$, take $n=2m+1$, so $H=2h$ and the coarse nodes coincide with every second fine node. Use linear interpolation with zero boundary corrections $z_0=z_{m+1}=0$:Use full-weighting restriction for the interior linear-system residual:Here $P^T$ is the matrix transpose in ordinary unweighted coordinates. With these specific transfers, the Galerkin coarse-grid operator isThus it equals the rediscretized Poisson equation operator on this constant-coefficient one-dimensional mesh. The equality is special to the stated model and transfers. In particular, dropping $h^{-2}$ from the fine matrix while using $H^{-2}$ on the coarse mesh changes the correction unless the right-hand sides and transfers are rescaled consistently.

Take seven interior points, $h=1/8$, three coarse unknowns, and the deliberately constructed approximation errorFor example, choose $b_h=0$, so $u_h^{\ast }=0$ and $v_h=-e_h$. Direct matrix multiplication givesThe exact coarse solve returns $z_H=z$, so adding $P{z}_H$ removes the entire chosen approximation error. A broad triangular error can have a sharply localized linear-system residual: the latter measures discrete curvature, not error height. This is why the two should not be confused. A smooth sine mode instead has linear-system residual ${\lambda }_k(A_h)e_h$, so interpreting its magnitude also requires the eigenvalue and the equation's scaling.

The algebra explains the exact cancellation beyond this example. Assume $P$ has linearly independent columns and choose an invertible Galerkin coarse-grid operator $A_H=R{A}_{h}P$. With an exact coarse solve, the iteration matrix for the remaining approximation error isThe short proof is to substitute $R{A}_{h}P=A_H$. Thus every vector in the column space of $P$ is eliminated, and the corrected linear-system residual restricts to zero. These are exact projection identities, not a statement that every visually smooth vector belongs to that column space. If $A_h$ is a symmetric matrix and a positive-definite matrix, and $R=c{P}^T$ with $c>0$, then $A_H$ is also a positive-definite matrix. Moreover $P^T{A}_{h}C{e}_h=0$: $C$ is an orthogonal projection onto the complement of the column space of $P$ in the energy norm $\Vert q{\Vert }_{A_h}=\sqrt{q^T{A}_{h}q}$. Equivalently, the added correction is the best approximation to $e_h$ from that column space in this energy norm. Without these symmetry and transfer assumptions, the projection need not be orthogonal.^[ref]

For an approximate coarse solve represented by a fixed linear map $B_H$, replace $A_H^{-1}$ by $B_H$. ThenThere is no exact cancellation of coarse-representable approximation error unless $B_H{A}_H=I$ on the relevant directions. For the triangular example, deliberately returning half the exact correction, $B_H=\frac{1}{2}{A}_H^{-1}$, leaves $e_h/2$, as the figure shows. This controlled mathematical comparison illustrates an incomplete coarse solve; it is not a measured performance result or a prescription for a geometric multigrid V-cycle. More generally, if $z_H^{\ast }=A_H^{-1}R{r}_h$, then an approximate $z_H$ leaves $C{e}_h+P(z_H^{\ast }-z_H)$, separating the nonrepresentable remainder from the coarse-solve defect.

With pre- and post-relaxation iteration matrices $S_{\mathrm{pre}}$ and $S_{\mathrm{post}}$, a two-grid error step has iteration matrix $E=S_{\mathrm{post}}{C}_B{S}_{\mathrm{pre}}$. A geometric multigrid V-cycle supplies $B_H$ by one recursive coarse cycle from zero, with a direct solve only at the bottom. Effective smoothing, a coarse column space that approximates the surviving approximation error, and a sufficiently accurate coarse correction must work together. Coarsening alone supplies no convergence guarantee, and correcting an arbitrary fine-grid vector exactly would require a coarse column space large enough to contain it.

The column rank of a matrix is the dimension of its image of a linear map, equivalently the dimension of the linear span of its columns. Multiplication on the left by an invertible matrix preserves all column linear relations, and elementary column operations preserve their linear span. In row echelon form the pivot columns form a basis of the column space. Its dimension equals the number of nonzero rows, and hence the row rank.

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$.

If an $m\times n$ matrix has columns $c_1,\dots ,c_n$, then matrix multiplication gives $Ax=x_1{c}_1+\cdots +x_n{c}_n$. Thus its column space consists of exactly the attainable output vectors in ${\mathbb{F}}^m$, and $Ax=b$ has a solution exactly when $b$ belongs to this column space. Its dimension is the matrix rank; the kernel instead describes input vectors in ${\mathbb{F}}^n$ whose contributions cancel.^[ref]

For $T>0$ and the constant matrices over the real numbers in the Kalman rank criterion, the finite-time Controllability Gramian accumulates the influence of all command times. Its column space equals that of the controllability matrix, and $W_T$ is a symmetric positive-definite matrix exactly when the controllability matrix has rank of a matrix $n$. If so, put $\delta =x_1-e^{AT}{x}_0$. Among square-integrable functions steering $x_0$ to $x_1$ at $T$, the commandminimizes ${\int }_0^T\Vert u(t){\Vert }^{2}dt$, with value ${\delta }^T{W}_T^{-1}\delta$. Here $T$ in a matrix superscript denotes transpose. This cost is a squared input norm, not necessarily physical energy, and the optimizing command need not satisfy an amplitude bound. ^[ref]

For the double integrator, $e^{As}B=(s,1{)}^T$, so direct integration givesFor a rest-to-rest distance $d$, $u_{\ast }(t)=6d/T^2-12dt/T^3$ and the minimum squared input norm is $12d^2/T^3$. Compare the two constant commands in the double integrator example, whose cost is $16d^2/T^3$: both attain the target, but the smooth command costs less. At $T=2$, $d=1$, however, $u_{\ast }$ peaks at $3/2$, so it violates $|u|\le 1$ while the two constant commands remain admissible. Controllability, optimal control, and constrained reachability in control theory answer different questions.

For the linear time-invariant system $\dot{x}=Ax+Bu$, with $A\in {\mathbb{R}}^{n\times n}$ and $B\in {\mathbb{R}}^{n\times m}$, the controllability matrix has $n$ rows and $nm$ columns. The columns of $B$ are directions influenced directly by the control inputs; $AB,A^{2}B,\dots$ account for how the dynamics carry their influence into further directions. The column space of the controllability matrix is the zero-state reachable set for any $T>0$ when inputs are unrestricted. ^[ref]

Fitted values are the predictions at the predictor values used to fit a regression model. In linear regression with an explicit regression intercept,Here $X$ is the slope design matrix, and $r$ is the regression residual vector. The fitted values estimate the regression function at the observed predictors; they need not equal the observed responses, which may also contain random errors. Prediction at a new predictor vector $x_{\ast }$ uses $\hat{\alpha }+x_{\ast }^T\hat{\beta }$ with the same centering and scaling used in fitting. A prediction interval addresses uncertainty in a new response rather than just displaying this point prediction.

For the five constructed observations in linear regression, ordinary least squares gives fitted values $(4/5,9/5,14/5,19/5,24/5)$. The ridge regression fit at $\lambda =10$ instead gives $(9/5,23/10,14/5,33/10,19/5)$. Both fitted vectors have sample mean $14/5$ because the regression intercept is unpenalized; their regression residuals differ and their residual sums of squares are $4/5$ and $33/10$, respectively.

For ordinary least squares, the fitted values are the orthogonal projection of $Y$ onto the column space of the complete design matrix, including its regression intercept column. They remain unique even in rank-deficient ordinary least squares, although the regression coefficients can be nonunique. The regression residuals are then orthogonal to every column.^[ref] With centered slopes, ridge regression instead satisfies $X_c^{T}r=\lambda {\hat{\beta }}_{\lambda }$, so the regression residuals need not be orthogonal to the slope columns. Their sum is still zero because the regression intercept remains free.

For fixed predictors and scales and a fixed positive penalty, ridge regression gives a linear smoother,For $\lambda >0$ with at least one nonzero slope direction, this matrix is not an orthogonal projection matrix: applying it twice shrinks that direction again. Its effective degrees of freedom are $1+{\sum }_{j=1}^r{d}_j^2/(d_j^2+\lambda )$, where $d_j$ are the positive singular values of $X_c$; the extra $1$ counts the free regression intercept. If the penalty is selected using $Y$, the resulting fitting rule need not be a linear smoother, since its chosen $H_{\lambda }$ also depends on $Y$.

An $m\times n$ matrix has full column rank when its matrix rank is $n$, equivalently when its columns are linearly independent vectors. This requires $n\le m$. Its kernel is $\{0\}$, so the represented linear map is injective and every solvable linear system $Ax=b$ has a unique solution. It need not reach every output.^[ref]

For example,has full column rank two, but its column space is the plane $b_3=b_1+b_2$ in ${\mathbb{R}}^3$. An attainable output fixes the input uniquely as $(b_1,b_2{)}^T$; an output outside this plane has no preimage.

An $m\times n$ matrix has full row rank when its matrix rank is $m$, equivalently when its rows are linearly independent vectors. This requires $m\le n$. Its column space is all of ${\mathbb{F}}^m$, so the represented linear map is surjective and every linear system $Ax=b$ is solvable. If $n>m$, its nullity is $n-m>0$, so solutions are not unique.^[ref]

For example, the matrix transpose of the matrix in full column rank isIt has full row rank two. Every output $(p,q{)}^T$ has solutions $(p-t,q-t,t{)}^T$, with $t\in \mathbb{R}$. A square matrix of size $n$ has full row rank and full column rank together exactly when its matrix rank is $n$; then it is an invertible matrix. A nonsquare matrix cannot have both properties, and has no two-sided inverse: such an inverse would make its linear map a linear isomorphism between vector spaces of different dimensions.

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.

Linear regression models a response's conditional expectation as a linear combination of specified predictors. In matrix form,where the design matrix $X$ describes the observations, $\beta$ contains the regression coefficients, and $\epsilon$ contains the errors. The fitted values $X\hat{\beta }$ estimate the response means. The model is linear in its regression coefficients; its columns may include powers, interactions, or other transformed predictors, so polynomial regression can fit curved relationships using the same machinery.

For a concrete example, take five constructed observationsAn ordinary least squares fit with an intercept gives the line $\hat{y}=0.8+x$. Its regression residuals are $(0.2,0.2,-0.8,0.2,0.2)$ and its residual sum of squares is $0.8$. A one-unit increase in the predictor corresponds to a one-unit increase in the fitted response. This is a description of this fitted association; interpreting a change as a causal effect requires the assumptions of a causal inference problem.

The geometric reason for the fit is simple. The possible mean vectors $X\beta$ form the column space of $X$. Ordinary least squares chooses the orthogonal projection of the data vector onto that vector subspace, so the remaining regression residual is orthogonal to every permitted fitted direction. The least-squares normal equations express this orthogonality as $X^T(Y-X\hat{\beta })=0$. The data's explained component and unexplained component are therefore separated by the same geometry used in a Hilbert space.

The optimization definition makes sense for any observed data. Quantifying the uncertainty of the regression coefficients needs additional assumptions about the sampling and errors. With fixed $X$ of full column rank and mean-zero errors with covariance matrix ${\sigma }^{2}I$, ordinary least squares is unbiased and has covariance ${\sigma }^2(X^{T}X{)}^{-1}$; the Gauss-Markov theorem compares it with other linear unbiased estimators. A normal linear model additionally makes Student t-distribution intervals and tests exact in finite samples. Model adequacy and predictive assessment remain relevant even when these calculations are available.

Two historical settings help explain the subject's appeal. Adrien-Marie Legendre's Nouvelles méthodes pour la détermination des orbites des comètes (1805) includes an appendix on the method of least squares: observations give more equations than unknowns, and squared errors provide a criterion for reconciling them. Its astronomical setting shows the motivation for combining imperfect measurements. ^[ref] Francis Galton's Regression Towards Mediocrity in Hereditary Stature (1886) examines the association between parental and offspring heights and the tendency of group averages toward the population average. This is a historical use of the regression name; the modern linear model is a general statistical formulation. ^[ref]

A low-rank approximation replaces an $m\times n$ matrix $A$ by a matrix $B$ of matrix rank at most a chosen integer $r$, with $0\le r\le \min (m,n)$, while making an explicitly chosen error norm small. The point is to describe many entries using a few shared patterns: an image compression may retain broad brightness patterns while discarding finer ones. The approximation is useful when the saved storage or computation justifies the lost detail. A small matrix rank alone says nothing about the error.

The compact representation is a sum of outer products, equivalently a product of two thin matrices:Here $x_j,y_j$ are the columns of $X,Y$, and the star denotes the conjugate transpose; over the real numbers use the transpose. The rank bound for a matrix product gives $\mathrm{rank}B\le r$. Conversely, choose a basis of the column space of $B$ as the columns of $X$, and put the coordinates of each column of $B$ into $Y^{\ast }$; pad with zero columns if the matrix rank is smaller than $r$. Each nonzero outer product is a rank-one matrix: it repeats a single column pattern at different strengths across the columns.

Keeping the two factors stores $r(m+n)$ scalars instead of $mn$. This saves space only when $r(m+n)<mn$. The usual singular value decomposition representation stores $r(m+n+1)$ scalars because it keeps the $r$ singular values separately; absorbing them into one factor removes that extra array. These are representation sizes at equal scalar precision, before file overhead. See Uschmajew and Vandereycken, §9.2: thin factors and their storage, and Illinois CS 357, Low-rank approximation: storing singular vectors and values.

The factors also give $Bz=X(Y^{\ast }z)$ without forming the full matrix $B$. Direct evaluation uses $nr+mr$ scalar multiplications, compared with $mn$ for a dense matrix applied to a vector. For $m=1000,n=800,r=10$, the two factors contain $18,000$ scalars rather than $800,000$, and the same counts describe these multiplication costs. Constructing the factors is a separate cost. Moreover, a low-rank approximation need not be a sparse matrix: the constant $8\times 8$ matrix whose entries are all $1$ has matrix rank $1$ despite having no zero entries.

For the standard unweighted problem, write a singular value decomposition with $p=\min (m,n)$ and singular values ${\sigma }_1\ge \cdots \ge {\sigma }_p\ge 0$. Retain the first $r$ paired left singular vectors and right singular vectors:The Eckart-Young-Mirsky theorem says that this same $A_r$ minimizes both of the following error norms over all matrices with matrix rank at most $r$:where ${\sigma }_{p+1}=0$ and an empty sum is zero. Here the Frobenius norm is $\Vert E{\Vert }_F=({\sum }_{i,j}|E_{ij}{|}^2{)}^{1/2}$, whereas the operator norm is specifically induced by the Euclidean norm, $\Vert E{\Vert }_2={\max }_{\Vert z{\Vert }_2=1}\Vert Ez{\Vert }_2$. The first aggregates errors in all entries; the second bounds the worst output error for a unit vector input. These formulas apply to real and complex matrices. ^[ref]

For $A\ne 0$, a relative Frobenius norm tolerance $\epsilon$ is met precisely when the discarded squared singular values sum to at most ${\epsilon }^2{\sum }_j{\sigma }_j^2$. Thus one can choose the smallest suitable $r$ before reconstructing the matrix. Many individually small discarded singular values can still have a large combined error. An operator norm tolerance instead tests only the largest discarded singular value, ${\sigma }_{r+1}$. The two questions can therefore select different ranks.

The following stipulated $8\times 8$ matrix makes the tradeoff visible. Define four real vectors of length $8$:The vectors $h_j/\sqrt{8}$ are orthonormal, so this is already a singular value decomposition written as outer products, with positive singular values $8,3,1,1/2$. All entries lie between $7/16$ and $25/16$ and can be displayed as brightnesses. The first component is uniform brightness, the second distinguishes broad blocks, and the last two supply finer alternating patterns. This is a designed arithmetic example, not measured image data.

Here $A_1=h_0{h}_0^T$ has every entry equal to $1$, while $A_2=h_0{h}_0^T+3h_1{h}_1^T/8$ has entries $11/8$ within the two diagonal blocks and $5/8$ in the other two blocks. For instance, $A_{11}=25/16$ becomes $(A_2{)}_{11}=11/8$: its error is $3/16$. The full residual is $h_2{h}_2^T/8+h_3{h}_3^T/16$, whose Frobenius norm is $\sqrt{1+(1/2{)}^2}=\sqrt{5}/2$ and whose operator norm is $1$. Since $\Vert A{\Vert }_F=\sqrt{297}/2$, the relative Frobenius norm error is $\sqrt{5/297}\approx 12.97\%$. Two thin factors use $32$ scalars, or $34$ if the normalized left singular vectors, right singular vectors, and singular values are stored separately, instead of $64$ dense entries.

Retaining three components reduces the Frobenius norm error to $1/2$ while using $48$ scalars in two factors. Retaining all four reconstructs $A$ exactly but uses $64$ scalars, giving no saving in this generic representation; keeping the singular values separately uses $68$. Our particular sign patterns could be encoded more economically, but that would exploit an additional structure beyond the general low-rank approximation. The striking feature is that numerical error and storage can both be read from the decomposition, rather than judged only by how smooth the picture looks.

The constraint is deliberately matrix rank at most $r$. The truncation has $\mathrm{rank}{A}_r=\min (r,\mathrm{rank}A)$. If $\mathrm{rank}A<r$, the best approximation is $A$ itself, with zero error. Requiring matrix rank exactly $r$ can destroy attainment: for $A=\mathrm{diag}(1,0)$ and $r=2$, the matrices $B_{\delta }=\mathrm{diag}(1,\delta )$ have matrix rank $2$ for $\delta >0$, and both error norms equal $\delta$. Their error has infimum zero, but no rank-two matrix attains it. If $r\le \mathrm{rank}A$, the displayed $A_r$ does have matrix rank exactly $r$ and attains the same minimum under either constraint.

Optimality also does not always mean uniqueness. For $0<r<\mathrm{rank}A$, the best Frobenius norm approximation is unique when ${\sigma }_r>{\sigma }_{r+1}$. ^[ref] A positive tie across the cutoff permits different choices: for $A=\mathrm{diag}(3,3,1)$ and $r=1$, both $\mathrm{diag}(3,0,0)$ and $\mathrm{diag}(0,3,0)$ have Frobenius norm error $\sqrt{10}$ and operator norm error $3$. More generally, $3w{w}^T$ is optimal for every real unit vector $w$ in the first two coordinate directions. Rotating which tied direction is kept changes the approximation. Repeated singular values entirely inside the retained group do not change its sum of outer products. At $r=0$ the only feasible matrix is zero; at $r\ge \mathrm{rank}A$ the unique zero-error approximation is $A$, even if some singular values are tied at zero.

A strict gap does not guarantee uniqueness for the operator norm. For $A=\mathrm{diag}(3,1)$ and $r=1$, every $B_t=\mathrm{diag}(t,0)$ with $2\le t\le 4$ has matrix rank $1$ and error $\Vert A-B_t{\Vert }_2=\max (|3-t|,1)=1$, which is optimal. Only $t=3$ minimizes the Frobenius norm, since $\Vert A-B_t{\Vert }_F=\sqrt{(3-t{)}^2+1}$. An unchanged worst direction can hide extra error in another direction under the operator norm.

Finally, these guarantees concern the stated norms and the sole matrix rank constraint. They do not establish that a discarded pattern is noise or irrelevant to a particular task: the finer patterns in our constructed example were put there intentionally. Adding entrywise weights or restrictions on the factors changes the problem, so the Eckart-Young-Mirsky theorem above does not automatically solve it. For historical context, the original 1936 matrix problem is documented in the existing Eckart-Young-Mirsky theorem section.

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]

The Moore-Penrose inverse extends the useful part of a matrix inverse to rectangular and singular matrices. A linear system $Ax=b$ may have no exact solution, or may have many. The pseudoinverse resolves both ambiguities: $x_{\ast }=A^{+}b$ is the minimum-norm least-squares solution. First minimize the Euclidean norm $\Vert Ax-b{\Vert }_2$; among all vectors attaining that minimum, choose the one with smallest Euclidean norm $\Vert x{\Vert }_2$. It does not pretend that inconsistent equations can all be satisfied.

For $A\in {\mathbb{C}}^{m\times n}$, its Moore-Penrose inverse is the unique $n\times m$ matrix satisfying the four Penrose equations. The singular value decomposition gives a direct construction:Here $U,V$ are unitary matrices, the star is the conjugate transpose, and ${\Sigma }^{+}$ is the $n\times m$ rectangular diagonal matrix obtained by replacing each nonzero singular value ${\sigma }_j$ by $1/{\sigma }_j$ and leaving zeros at zero. Over the real numbers, use orthogonal matrices and transposes. The pseudoinverse reverses the stretches that can be reversed; it discards output components the original linear map cannot produce and does not invent an input component in its kernel. ^[ref]

The two products have especially clear meanings:They are orthogonal projection matrices: $A{A}^{+}$ selects the producible part of an output, while $A^{+}A$ selects the detectable part of an input. They are generally not identity matrices. For an invertible matrix, both are identities and $A^{+}=A^{-1}$.

This gives a useful order of operations for least-squares solutions: project the requested output onto the column space, then invert the restriction of $A$ from $(\ker A{)}^{\perp }$ to its column space. Adding a kernel vector leaves the residual unchanged but increases the squared Euclidean norm by the Pythagorean theorem in an inner-product space, because $A^{+}b$ is orthogonal to that kernel. The pseudoinverse therefore provides one canonical answer without hiding either lost information or irreconcilable data.

The name records a history with several contributors. E. H. Moore gave an earlier generalization in 1920; M. H. Pearl's 1966 paper records that work, Arne Bjerhammar's 1951 rediscovery for maximal-rank rectangular matrices, and Roger Penrose's independent 1955 treatment. ^[ref] Penrose's original paper proves existence and uniqueness from the four Penrose equations for arbitrary complex matrices, including rectangular ones. ^[ref]

Minimizing $\Vert y-X\theta {\Vert }^2$ gives the displayed equations by differentiation. Equivalently, the regression residual $r=y-X\hat{\theta }$ satisfies $X^{T}r=0$: it is orthogonal to every column of the design matrix. If $X$ has full column rank, the minimizer is unique and the fitted values are the orthogonal projection of $y$ onto its column space. A rank-deficient design matrix can give multiple coefficient vectors, while the projected fitted vector is still unique.

For an intercept and one predictor, put $S_{xx}={\sum }_i(x_i-\bar{x}{)}^2$ and $S_{xy}={\sum }_i(x_i-\bar{x})(y_i-\bar{y})$. The equations give $\hat{\beta }=S_{xy}/S_{xx}$ and $\hat{\alpha }=\bar{y}-\hat{\beta }\bar{x}$, provided $S_{xx}>0$. In the five-point example in linear regression, $\bar{x}=2$, $\bar{y}=2.8$, $S_{xx}=10$ and $S_{xy}=10$, giving $\hat{\beta }=1$ and $\hat{\alpha }=0.8$.

The normal equations describe the mathematical optimum, but explicitly forming and inverting $X^{T}X$ can amplify numerical problems. A QR decomposition computes the same least-squares solution through orthogonal coordinates; a singular value decomposition also exposes nearly dependent columns. This connects statistical fitting to numerical linear algebra and the choice of a stable algorithm. ^[ref]

When ${\Lambda }_{ii}>0$, the normalized sample principal component $w_i=u_i/\sqrt{{\Lambda }_{ii}}$ has Euclidean norm one. The vectors $w_i$ form an orthonormal set spanning the column space of a full-column-rank centered design matrix.

A matrix represents a linear projection when applying it twice has the same effect as applying it once. For an orthogonal projection with the standard Hermitian inner product on ${\mathbb{C}}^m$, the additional condition is that the conjugate transpose equals the original matrix:Thus $P$ is both idempotent and a Hermitian matrix. Over the real numbers this says $P^2=P=P^T$. Its image of a linear map is the retained linear subspace, while its kernel of a linear map is the orthogonal complement: vectors in the image are unchanged, and vectors in the kernel become zero.

For a matrix $A$ with full column rank, projecting onto its column space givesThe invertibility of $A^{†}A$ follows from linear independence of the columns. If those columns are an orthonormal set, $A^{†}A=I$ and $P=A{A}^{†}$. These formulas and the conditions $P^2=P=P^T$ in the real case are developed in MIT 18.06SC, Projections onto Subspaces, pp. 1–3.

For the line spanned by $e=(1,2{)}^T$,In particular, $Pe=e$ and $P(2,-1{)}^T=0$. The eigenvalues are $1$ on the retained direction and $0$ on the removed direction. This exposes the meaning of an orthogonal projection as retaining selected components, rather than stretching them.

Symmetry refers to the specified inner product. In the real weighted setting, the formula becomes $P_M=A(A^{T}MA{)}^{-1}{A}^{T}M$ and satisfies $P_M^2=P_M$ and $P_M^{T}M=M{P}_M$. For the preceding weighted line example,It is not symmetric under the ordinary transpose, but it is an orthogonal projection for the weighted Euclidean inner product. The matrix criterion $P=P^{†}$ should therefore be used with the standard Hermitian inner product, not silently transferred to a different geometry.

A finite-dimensional linear subspace $W$ of an inner product space has a unique closest vector to any given vector $x$. This is its orthogonal projection $P_{W}x$. If $e_1,\dots ,e_d$ is an orthogonal basis of $W$, compute it one direction at a time:The inner product convention here is linear in its first argument, including over the complex numbers. For an orthonormal basis, each denominator is one. When $W$ consists only of the zero vector, the empty sum gives $P_{W}x=0$. The finite-dimensional formula is described in Francis Narcowich, Inner Products and Norms: minimization problems.

Take $W=\mathrm{span}\{(1,2{)}^T\}$ and $x=(3,1{)}^T$, using the dot product. With $e=(1,2{)}^T$,The orthogonal projection residual has $r\cdot e=2-2=0$. To verify the best approximation directly, every candidate in the line is $te$, andThe smallest squared Euclidean norm error is therefore $5$, attained only at $t=1$. The diagram connects the perpendicular residual to this one-variable quadratic polynomial.

The general mechanism is the Pythagorean theorem in an inner-product space. For any $w\in W$, the vectors $r=x-P_{W}x$ and $P_{W}x-w$ are orthogonal, soMoving away from $P_{W}x$ inside $W$ adds a nonnegative squared norm, which is zero only when $w=P_{W}x$. This proves both optimality and uniqueness.

The useful feature is separation of preparation from evaluation. Construct an orthonormal basis once with the Gram-Schmidt process, then obtain each new best approximation using inner products instead of a fresh optimization problem. When $W$ is the column space of a matrix, this gives linear least squares; when $W$ is spanned by orthogonal polynomials, it gives a least-squares polynomial in an orthogonal-polynomial basis. The ambient inner product space need not be a Hilbert space for this finite-dimensional construction. In an infinite-dimensional target linear subspace, existence requires additional hypotheses, supplied by orthogonal decomposition by a closed subspace.

An orthogonal projection residual is the difference $r=x-P_{W}x$ between a vector and its orthogonal projection onto a linear subspace $W$. It is orthogonal to every vector in $W$, so $⟨r,w⟩=0$ for all $w\in W$. The Gram-Schmidt process uses such residuals to remove directions already represented by earlier basis vectors.

This is an optimality condition as well as a geometric description. No permitted change within $W$ can remove a further orthogonal component of $r$. In the preceding dot product example, $r=(2,-1{)}^T$ is perpendicular to the line spanned by $(1,2{)}^T$.

The selected inner product matters. Keep $x=(3,1{)}^T$ and the same line, but use the weighted Euclidean inner product with $M=\mathrm{diag}(4,1)$. The projection coefficient and residual becomeNow $4(r_M{)}_1{e}_1+(r_M{)}_2{e}_2=5-5=0$, although $r_M\cdot e=-15/4\ne 0$. The orthogonality is with respect to $M$, so it need not look perpendicular in the ordinary drawing. The squared weighted error isThe weighted optimum reduces the first-coordinate error from $2$ to $5/4$, at the cost of increasing the magnitude of the second-coordinate error from $1$ to $5/2$. The weights express which errors are more costly.

In linear least squares, residual orthogonality to the column space is expressed by the normal equations for linear least squares. With a weighted Euclidean inner product, the corresponding real-matrix equation is $A^{T}M(x-Ac)=0$. This makes the choice of error measurement part of the mathematical model, rather than merely a plotting convention.

Suppose three measurements constrain two unknowns:The linear system asks for $x_1=1$, $x_2=2$, and $x_1+x_2=6$, which are incompatible. A least-squares solution makes a balanced compromise. The matrix has full column rank, soThe fitted output and residual areThus the two direct measurements are each overshot by one, and the measured sum is undershot by one. The residual has Euclidean norm $\sqrt{3}$ and is orthogonal to the column space, the plane $z=y_1+y_2$ in output coordinates $(y_1,y_2,z)$.

For any perturbation $h\in {\mathbb{R}}^2$, the orthogonality of $r$ to $Ah$ givesSince the kernel of $A$ is trivial, every nonzero $h$ increases the residual. The least-squares solution is unique in this example. The formula using $A^{T}A$ is convenient for these small exact calculations; an actual numerical computation can use a QR decomposition or singular value decomposition to avoid the extra conditioning cost of the least-squares normal equations. For full column rank, the squared singular values of $A$ are the eigenvalues of $A^{T}A$, so its condition number in the Euclidean norm is ${\kappa }_2(A^{T}A)={\kappa }_2(A{)}^2$. ^[ref]

Let $[A\mid b]$ be the augmented matrix of the linear system. Consistency means that $b$ is in the column space of $A$, equivalently $\mathrm{rank}[A\mid b]=\mathrm{rank}A$. For a consistent system, choosing one solution $x_0$ gives every solution as $x_0+\ker A$. The rank-nullity theorem therefore gives the complete classification:

For the given equations, subtracting the first from the second and the second from the third givesIf $\lambda =0$, then $z=-1$ and the first equation gives $x=0$. If $\lambda =1$, the first reduced equation is $0=1$, so the system is inconsistent. ThusThese conclusions can also be checked from $\det A=1-\lambda$, but the row differences exhibit the inconsistency directly.