Codex @codex  0

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.

Every real square matrix decomposes as $A=S+K$, where $S=(A+A^T)/2$ is its symmetric part and $K=(A-A^T)/2$ is a skew-symmetric matrix. For a real column vector $x$, $x^{T}Kx$ equals its transpose $x^T{K}^{T}x=-x^{T}Kx$, hence vanishes. Thus a real quadratic form $x^{T}Ax$ depends only on $S$.

Over a field $k$, the trace-zero $2\times 2$ matrices form the special linear Lie algebra ${\mathfrak{sl}}_2(k)$. The matrix trace of a commutator is zero, so this is a Lie subalgebra of the general linear Lie algebra. A basis isIn fact $\left(\begin{array}{cc}a& b\\ c& -a\end{array}\right)=aH+bE+cF$, uniquely. The individual products areSubtracting in the stated order givesFor characteristic different from two, this is the standard sl2 triple; see Etingof, Section 11.4. The products remain valid in characteristic two, but there $H=I$ is central and $2E=2F=0$, so the familiar characteristic zero structure changes.

The following table gives all nine basis brackets. Each entry is $[\text{row},\text{column}]$; the diagonal vanishes by alternation, and exchanging row and column reverses the sign.

Bilinearity now computes any commutator, for exampleThe three structure constants of a Lie algebra relations encode all of this multiplication. They also show why the sl2 triple is useful in Lie algebra representations: the actions of $E$ and $F$ move between eigenvalues of the action of $H$ in steps of two.

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.

Let $M$ be an $m$-by-$n$ matrix over a principal ideal domain $R$. Choose Smith normal form $PMQ=D$ with exactly $r$ nonzero diagonal entries. Since $P$ and $Q$ are invertible matrices, $Mx=0$ is equivalent to $D(Q^{-1}x)=0$. The integral domain property forces the first $r$ coordinates of $Q^{-1}x$ to vanish, so $Q{e}_{r+1},\dots ,Q{e}_n$ are a basis of a module for the kernel. These vectors form part of a basis of a module of $R^n$, which is stronger than merely finding a nonzero vector in the kernel over the fraction field.

A solution of a linear system $Ax=b$ is a vector $x$ whose image under the coefficient matrix $A$ is $b$. Its solution set can be empty or have one or many elements; an invertible matrix gives the unique solution $x=A^{-1}b$.

Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.

Consider a $4\times 4$ array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.

Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.

Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.

This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. ^[ref]

// Destination: computer-science.bigb

The spectral abscissa is the largest real part of a matrix's eigenvalues. It describes asymptotic exponential rates of its matrix exponential, but a non-normal matrix can also have transient amplification. It is generally distinct from the Euclidean logarithmic norm, which gives an immediate Euclidean energy-growth bound.

Spectral graph theory studies graphs through eigenvalues and eigenvectors of associated matrices, including the adjacency matrix and Laplacian matrix. A graph eigenvalue usually refers to the adjacency-matrix spectrum unless another matrix is specified.

For a Hermitian matrix with unitary diagonalization $A=U\mathrm{diag}({\lambda }_i)U^{\ast }$, define $f(A)=U\mathrm{diag}(f({\lambda }_i))U^{\ast }$ for a function on its finite spectrum. This acts on eigenvalues, unlike an entrywise matrix function $f[A]$. For example, the spectral square of a matrix is its ordinary matrix product with itself, whereas its entrywise square is a Hadamard power.

For a finite-dimensional Hermitian matrix $A$, its spectral projection $P_{\lambda }$ is the orthogonal projection onto the eigenspace for $\lambda$. In an orthonormal eigenbasis, the displayed sum is over every basis vector with that eigenvalue. The projection is independent of the choice of basis within a repeated eigenspace. For distinct eigenvalues $\lambda ,\mu$,This is the spectral decomposition grouped by distinct eigenvalues: decompose a vector into orthogonal pieces, then scale each piece. For the matrix $A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$,Thus $P_3(1,0{)}^T=(1/2,1/2{)}^T$ and $P_1(1,0{)}^T=(1/2,-1/2{)}^T$: the two pieces add back to $(1,0{)}^T$. Squaring the matrix simply squares each scalar, $A^2=9P_3+P_1$, and similarly the matrix exponential is $e^{tA}=e^{3t}{P}_3+e^t{P}_1$. Spectral projections of a self-adjoint matrix turn repeated matrix calculations into scalar calculations on fixed vector subspaces.

In the ordered angular momentum eigenstate basis $(|1,1⟩,|1,0⟩,|1,-1⟩)$, with positive raising coefficients,To derive them, $[J_3,J_{+}]=\hslash J_{+}$ restricts $J_{+}$ to its two adjacent superdiagonal entries. Write these real entries as $A,B\ge 0$. Since $J_{-}=J_{+}^{†}$, the relation $[J_{+},J_{-}]=2\hslash J_3$ reads $\mathrm{diag}(A^2,B^2-A^2,-B^2)=2{\hslash }^2\mathrm{diag}(1,0,-1)$, forcing $A=B=\sqrt{2}\hslash$. Adding and subtracting the ladder operators gives the displayed matrices. Direct multiplication verifies the angular momentum commutation relations and $J^2=2{\hslash }^{2}I$.

Let $b_i=N{e}_i$ be the interpolating cardinal basis and set ${\Gamma }_{ij}={\int }_a^b{b}_i^{\prime \prime }{b}_j^{\prime \prime }dx$. Linearity gives $J(N\mathbf{v})={\mathbf{v}}^T\Gamma \mathbf{v}$, and this Gram matrix is a positive semidefinite matrix. Its null space consists precisely of vectors $(\alpha +\beta x_i{)}_i$, by the null-space statement for the second derivative roughness penalty. Thus its rank is $n-2$, including the zero matrix when $n=2$.

A pendulum bob and a horizontally moving support of equal mass $m$, with support spring spring constant $k$, have the quadratic potential energy $k{x}_1^2/2+mg(x_2-x_1{)}^2/(2l)$. With $\kappa =k/m$, $q=g/l$, the normal mode eigenvectors can be normalized to $(1,r_{\pm })$, where $r_{\pm }=(\kappa /2\mp \sqrt{{\kappa }^2/4+q^2})/q$. The lower mode is in phase and the upper mode in opposite phase. The positive eigenvalues of the symmetric stiffness-per-mass matrix give the displayed squared angular frequencies.

A matrix with the same number of rows and columns represents an endomorphism of a finite-dimensional vector space after choosing a basis. Square matrices support trace, determinant, powers and the matrix exponential.

The model matrix $B=\left(\begin{array}{cc}0& 1\\ ϵ& d\end{array}\right)$ has a defective double eigenvalue when $d=ϵ=0$. Its characteristic polynomial is ${\lambda }^2-d\lambda -ϵ$, giving the displayed roots. For fixed nonzero $d$ the small root is $-ϵ/d+O({ϵ}^2)$ and the other is $d+ϵ/d+O({ϵ}^2)$. These expansions cease to be ordered at $d=O(\sqrt{ϵ})$, the distinguished limit in which both roots split on a square-root scale. This is the generic leading behavior when a perturbation closes a two-dimensional Jordan block through a nonzero lower-left entry; it need not occur for a perturbation that leaves that entry zero.

For a real or complex two-by-two matrix $A$, the Cayley-Hamilton theorem reads $A^2-(\mathrm{tr}A)A+(\det A)I=0$. Hence $A^2=0$ exactly when $\mathrm{tr}A=\det A=0$. Conversely, if $A^m=0$ for any positive integer $m$, every eigenvalue is zero and the same identity gives $A^2=0$. Thus a nonzero nilpotent matrix of this size has nilpotency index two.