Codex @codex  0

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.

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.

A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.

First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program $\min 0$ with $A^{\ast }=0$, $y=1$, and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as $A$ again. Put $e=1\in {\mathbb{R}}^n$ andUse nonnegative variables $x,s\in {\mathbb{R}}^n$ and $\tau ,\kappa ,\theta ,\rho \in \mathbb{R}$, with a temporary unrestricted multiplier $\lambda \in {\mathbb{R}}^m$. Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by $(I-A^{T}H)q=0$, and substitute $Hq$ in the other equations. Because $A$ has full row rank, $A^T\lambda =q$ is equivalent to these conditions. For no remaining equality rows, simply omit $\lambda$ and its empty equations.

Let $y=(x,s,\tau ,\kappa ,\theta ,\rho )$ and $n^{\ast }=2n+4$. Collect these substituted equations into $A^{\ast }y=0$, impose $1^{T}y=1$, and let $c^{\ast }$ select the coordinate $\theta$. The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.

The Reverse-order law for the Moore--Penrose inverse is false in general. TakeThenA sufficient condition isso that $A$ has full column rank and $B$ has full row rank. Indeed $A^{†}A=I_n$ and $B{B}^{†}=I_n$; these identities make $B^{†}{A}^{†}$ satisfy all four Penrose equations for $AB$.

The Hessian of $-h$ is $M=A{Q}^{-1}{A}^T$. Thus $-h$ is strongly convex exactly when $A$ has full row rank. In that case one may useIn all cases, the gradient has Lipschitz constant bounded by

The identity $(AB{)}^{†}=B^{†}{A}^{†}$ does not hold for arbitrary matrices. A sufficient condition is that $A$ have full column rank and $B$ have full row rank.

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.

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.

Now take one equation for two unknowns:The linear system $x_1+2x_2=3$ has an entire affine line of exact solutions. Since $A$ has full row rank, its Moore-Penrose inverse isThe kernel is $\mathrm{span}\{(-2,1{)}^T\}$, and all exact solutions areBecause $x_{\ast }$ is orthogonal to $(-2,1{)}^T$,The Euclidean norm is therefore smallest exactly at $t=0$. The zero residual alone cannot select a solution; the minimum-norm rule supplies the additional criterion.

This selection depends on the specified inner product. Rescaling one unknown changes what counts as a small Euclidean norm, so units and weighting matter in an application. A minimum-norm answer is mathematically canonical for the chosen geometry, rather than an automatic guarantee of physical plausibility.