Codex @codex  0

A sesquilinear form on a complex vector space $V$ is a map $B:V\times V\to \mathbb{C}$ which, with the convention used throughout this article, is a linear map in its first argument and a conjugate-linear map in its second. For vectors $u,v,w$ and complex numbers $\alpha ,\beta$, the defining identities areThe bars denote complex conjugation. No symmetry or positivity is required. Some authors choose the opposite convention; every formula here keeps the first argument linear.^[ref]

For a basis $e_1,\dots ,e_n$ of a finite-dimensional vector space, write $u={\sum }_i{x}_i{e}_i$, $v={\sum }_j{y}_j{e}_j$, and $A_{ij}=B(e_i,e_j)$. Expanding by the two identities givesEvery complex matrix $A$ gives a sesquilinear form this way. The superscript $T$ means transpose, not conjugate transpose. Equivalently, the scalar is $y^{\ast }{A}^{T}x$, where $y^{\ast }={\overline{y}}^T$. This is the convention used for the matrix of a Hermitian form when symmetry is imposed. The coordinate formula follows directly by expanding the basis coefficients.^[ref]

For a concrete example on ${\mathbb{C}}^2$, let $B(z,w)=z_1\overline{w_2}$. Its matrix is $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$: $B(e_1,e_2)=1$ but $B(e_2,e_1)=0$, so it is not a Hermitian form. Also $B((1,i),(1,i))=-i$, so even real diagonal values cannot be assumed for an arbitrary sesquilinear form. By comparison, the bilinear form $F(z,w)=z_1{w}_1+z_2{w}_2$ satisfies $F(iz,w)=F(z,iw)=iF(z,w)$ and has $F((i,0),(i,0))=-1$; it cannot supply positive squared lengths on this complex vector space.

The effect of changing the complex argument of a multiplier is particularly revealing. For real numbers $\theta ,\varphi$, sesquilinear forms satisfyThus a common change of complex argument cancels from the diagonal, whereas the two arguments rotate the output in opposite directions. Conjugating one argument is what replaces the ${\alpha }^2$ scaling of a bilinear form by the nonnegative $|\alpha {|}^2$ scaling needed for a Hermitian inner product. This mechanism also works in function spaces: for complex continuous functions on $[0,1]$, $B(f,g)={\int }_0^{1}f(t)\overline{g(t)}dt$ obeys the same identities, letting integration measure overlap rather than merely multiply coefficients.

The Sherman–Morrison formula computes the matrix inverse after a rank-one matrix update. If $A$ is an invertible matrix and $\delta =1+v^T{A}^{-1}u\ne 0$, thenThe inverse correction is itself an outer product, divided by the scalar $\delta$. The matrix determinant lemma shows that the nonzero-denominator condition is exactly the condition that the updated matrix remains an invertible matrix.

For $A=I$, $u=(1,2{)}^T$, and $v=(3,-1{)}^T$, we have $\delta =2$. Thus the computed inverse isMultiplication in either order gives the identity matrix. The result reuses the original inverse $I$ and the same correction vectors, rather than solving independently for all four inverse entries.

Often only the solution of an updated linear system is needed. If $A{x}_0=b$ and $Az=u$, thenprovided $1+v^{T}z\ne 0$. The two solves use the same LU decomposition of $A$. This expresses the computational benefit without requiring an explicitly stored matrix inverse. Strang's Lecture 14, transcript pp. 9–10 explains this reuse of the original factorization.

To see why the inverse correction works, first consider $A=I$ and put $s=v^{T}u$. The rank-one matrix $R=u{v}^T$ satisfies $R^2=sR$. Expandingalso works in the reverse order. The general case follows by factoring out $A$ and replacing $u$ by $A^{-1}u$. A matrix identity has reduced to cancellation of scalar coefficients.

Historically, Jack Sherman and Winifred J. Morrison studied updating an inverse when a single matrix entry changes in their ^[ref]. Such an entry change is the special rank-one matrix update $\alpha e_i{e}_j^T$, with standard basis vectors $e_i,e_j$. The reference and the earlier 1949 abstract on row or column changes are recorded in Henderson and Searle, On Deriving the Inverse of a Sum of Matrices (1981), references 40–41. This distinguishes the specific original setting from the more general $u{v}^T$ formula used here.

Under power iteration convergence for a diagonalizable matrix, take $v_1=u_1$ to be a unit vector. The displayed formula describes both the dominant eigenvector direction and its rotating complex unit factor. With real data and a positive dominant eigenvalue, $x_k$ converges to $u_1$ or $-u_1$ according to the sign of $c_1$. With a negative dominant eigenvalue, consecutive vectors approach opposite signs even though their power iteration direction error tends to zero.

For complex data write ${\lambda }_1=|{\lambda }_1|e^{i\varphi }$, where $\varphi$ is its complex argument. The leading factor turns by $e^{i\varphi }$ per step, so the vectors generally do not converge. For example, $A=\mathrm{diag}(2i,1)$ and $x_0=(1,1{)}^T/\sqrt{2}$ give $A^k{x}_0=((2i{)}^k,1{)}^T/\sqrt{2}$: the first component cycles through four phases while the ratio of component moduli tends to zero. Its power iteration direction error is $2^{-k}/\sqrt{1+2^{-2k}}$. Multiplying $x_k$ by $e^{-i(\arg c_1+k\varphi )}$ gives a sequence converging to $u_1$.

A stopping rule based only on $\Vert x_{k+1}-x_k{\Vert }_2$ therefore rejects successful sign-alternating iterations. A comparison invariant under complex unit factors isEven this comparison can be small for a slowly changing wrong mixture; the eigenpair residual supplies a separate diagnostic.

Signed swept area counts the area traversed by a position vector, positively or negatively according to its direction of turning. For a continuously differentiable planar trajectory, its accumulated value relative to $t_0$ is the line integralA short segment contributes the oriented triangle area $\frac{1}{2}\mathbf{n}\cdot (\mathbf{r}\times d\mathbf{r})$; taking its time derivative gives areal velocity. Repeated turns count repeated area; a reversal subtracts it. Thus this quantity need not equal the area of the union of all previously swept regions. The origin matters: the relevant origin for Kepler's second law is the attracting focus of the ellipse, rather than its geometric centre.

If $T^2=T$, every vector splits as $v=(v-Tv)+Tv$ in $\ker T\oplus \mathrm{im}T$. On these summands $T$ is respectively zero and the identity. Its matrix in an adapted basis is therefore $\mathrm{diag}(0,I_r)$, where $r$ is its rank of a linear map. Two idempotent linear maps on the same finite-dimensional vector space are similar matrices exactly when their ranks agree.

A similarity transformation replaces a square matrix by a similar matrix. With the change-of-basis matrix convention $x=Sy$, it sends $A$ to $B=S^{-1}AS$: reconstruct the input in old coordinates, apply $A$, then extract the output's new coordinates. These three operations explain the order of the factors.

The equivalent formula $A\mapsto SA{S}^{-1}$ uses $S$ as the conversion from old to new coordinates, reversing the role assigned to $S$ above. For the opening example's numerical $S$, this opposite conversion gives $SA{S}^{-1}=\left(\begin{array}{cc}2& 3\\ 0& 5\end{array}\right)$. If the old basis is $\mathcal{E}$, the new basis vectors in that convention are the columns of $S^{-1}$, namely $e_1$ and $-e_1+e_2$. Both formulas are similarity transformations; the direction of the coordinate conversion decides which one describes a specified basis.

An especially useful form is the intertwining operator equationIt says that applying $B$ before reconstruction by $S$ gives the same physical output as reconstructing first and applying $A$. Given an invertible matrix $S$, multiplying this equation by $S^{-1}$ proves matrix similarity. Without invertibility, the equation alone does not prove matrix similarity.

A simple bivector can be expressed as one exterior product of two vectors. Changing the pair need not change its area element: $u\wedge (v+cu)=u\wedge v$ for every scalar $c$, by bilinearity and $u\wedge u=0$. This operation shears the represented parallelogram while preserving its oriented area.

Every bivector in a real vector space of dimension at most three is simple, but this fails in dimension four. For an ordered basis $e_1,\dots ,e_4$, considerThe two components describe independent coordinate planes. Their square iswhereas $(u\wedge v)\wedge (u\wedge v)=0$ because the factors repeat. Thus this $B$ cannot be one simple bivector. Over the real numbers in dimension four, the converse also holds: a nonzero bivector with $B\wedge B=0$ is simple. The nonzero factor two is important; that criterion cannot be applied unchanged in characteristic two.

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 uniform rigid body disk of mass $m$ and radius $a$ moves in a frictionless plane. Let $N\ge 3$ identical springs attach equally spaced rim points to fixed anchors in their radial directions. The equilibrium spring length is $l$, natural length $l_0<l$, and spring constant $k$. Write the small centre displacement as $\mathbf{q}$ and the rotation as $\theta$. For a spring with radial and tangential unit vectors $\mathbf{n},\mathbf{t}$, its length isThis follows by a second-order Taylor series for the distance between $\mathbf{q}+aR(\theta )\mathbf{n}$ and $(a+l)\mathbf{n}$. In the elastic potential energy $k(s-l_0{)}^2/2$, the equilibrium tension $k\tau$ multiplies the second-order change of length. Thus it contributes to the linearized stiffness even though the displacement is small.

The equally spaced directions satisfy $\sum \mathbf{n}=\sum \mathbf{t}=0$ and $\sum \mathbf{n}{\mathbf{n}}^T=\sum \mathbf{t}{\mathbf{t}}^T=(N/2)I$. Summing the spring energies givesThe kinetic energy is $m|\dot{\mathbf{q}}{|}^2/2+m{a}^2{\dot{\theta }}^2/4$, using the moment of inertia of a uniform disc. The Euler-Lagrange equations give the displayed squared angular frequencies. The translational normal modes are degenerate; rotation is independent. At zero prestretch the rotational frequency vanishes at quadratic order, and finite-angle spring stretching first contributes at higher order.

Use the cross-product Lie algebra convention $X=\widehat{e_1}$, $Y=\widehat{e_2}$, $Z=\widehat{e_3}$, so $[X,Y]=Z$. Put $R_x(t)=\exp (tX)$ and $R_y(t)=\exp (tY)$, using the matrix exponential. The finite group commutator isHere $\epsilon \to 0$ and big O notation refers to any fixed matrix norm. Active rotation matrices act on column vectors from right to left: first rotate about $y$ by $-\epsilon$, then about $x$ by $-\epsilon$, then about $y$ by $+\epsilon$, and finally about $x$ by $+\epsilon$. Swapping $x$ and $y$ replaces the product by its inverse and changes the leading Lie bracket to $-Z$.

Writing $c=\cos \epsilon$ and $s=\sin \epsilon$, direct matrix multiplication givesFor $\epsilon =0.1$ radians, $C_{\epsilon }{e}_1\approx (0.999950208,0.009966462,0.000501230)$, whereas $e_1+{\epsilon }^{2}Z{e}_1=(1,0.01,0)$. Thus the residual is a positive rotation about $z$ to leading order; at finite $\epsilon$ it also has smaller components. The Lie bracket captures the leading effect of the four moves rather than their entire finite motion. See Etingof, Section 7.2, Proposition 7.11.

The left panel projects the actual four arcs onto the $yz$-plane for $\epsilon =0.25$; the start and endpoint are close but distinct. The right panel divides the residual coordinates by ${\epsilon }^2$, making the limit $(\Delta y/{\epsilon }^2,\Delta z/{\epsilon }^2)\to (1,0)$ visible. This is a numerical picture of $[X,Y]=Z$ in the SO(3) Lie algebra.

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

For a consistent linear system $Ax=b$, choose one solution $x_0$. By linearity, $Ax=b$ if and only if $A(x-x_0)=0$, so its solution set is the translate $x_0+\ker A$ of the kernel. Over the real numbers, this gives exactly one solution when the kernel is zero and infinitely many when the kernel contains a nonzero vector: $x_0+tz$ is a distinct solution for each real $t$ if $z\ne 0$ lies in the kernel. An inconsistent linear system has an empty solution set. The dimension of a nonempty solution set, regarded as an affine space, is the nullity of $A$.

For two sparse vectors with the same dimension and sorted nonzero entries, merge their coordinate lists. Equal indices contribute their product and advance both cursors. If one index is smaller, advance only that cursor: the other vector has zero at that coordinate, because all its smaller indices have already been processed and all remaining indices are larger. This proves a loop invariant consisting of the accumulated inner product over settled indices. Every iteration consumes at least one stored entry, giving time complexity $O(k_x+k_y+1)$ and constant auxiliary space for $k_x,k_y$ nonzero entries. The method avoids work proportional to the ambient dimension. Its floating-point arithmetic error remains distinct from its exact algorithm correctness.

With metric signature $(-,+,+,+)$, a nonzero vector $v$ is spacelike when its Lorentzian inner product with itself satisfies $g(v,v)>0$. In Minkowski spacetime, this means its spatial components have larger squared Euclidean length than its time component. The classification is preserved by Lorentz transformations. A timelike vector has negative squared Lorentzian inner product, and a null vector has zero squared Lorentzian inner product.

Take a star graph $G$ with center $c$ and four leaves $1,2,3,4$. Let $L_G$ be its Laplacian matrix and $I$ the identity matrix. In the order $(c,1,2,3,4)$, the original example isFor a nonzero vector $u$, its quadratic form isThus $A$ is a symmetric positive-definite matrix and either ordering below admits a Cholesky decomposition. Changing the ordering changes the work, rather than the mathematical solvability.

Center first. Eliminating $c$ with pivot element $5$ leaves the Schur complementEvery pair of leaves now has coupling $-1/5$: six new edges, hence six undirected fill-in positions. The four remaining vertices form a clique. In the Cholesky decomposition, the first column has $C_{cc}=\sqrt{5}$ and $C_{ic}=-1/\sqrt{5}$. The rest of the lower triangular matrix is dense. To check that later cancellation does not remove its entries, after $r$ leaves have also been eliminated, the active leaf block isIndeed a leaf step sends $\alpha$ to $\alpha +{\alpha }^2/(2-\alpha )$. All active off-diagonal entries remain negative. The successive pivot elements in ordinary symmetric Gaussian elimination, equivalently the squared diagonals in the Cholesky decomposition, areThe Cholesky decomposition therefore stores $5+4+3+2+1=15$ nonzero entries, including its diagonal.

Leaves first. Permute to $(1,2,3,4,c)$. Each leaf has only one remaining neighbor, so its elimination changes only the center's diagonal, reducing it by $(-1{)}^2/2=1/2$. The successive pivot elements are $2,2,2,2,3$, and the exact Cholesky decomposition isThere is no fill-in, and only $5+4=9$ nonzero entries in $C$. This is a concrete instance of leaf elimination of a tree-pattern positive-definite matrix; its general proof explains why the same idea works on every tree pattern. The minimum degree algorithm also chooses a leaf at every nontrivial stage of this particular example, but that success gives no general optimality guarantee.

The input has 13 nonzero matrix elements when both symmetric halves are counted, or nine in its lower triangle. The six added undirected edges correspond to six added positions in one triangular factor, or 12 positions if both symmetric halves of the filled pattern are displayed. Comparing all 13 input entries directly with the 15 entries of $C$ would mix counting conventions.

Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.

For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.^[ref]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.

This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.^[ref]

A linear map is injective on the class of sparse vectors of order $s$ exactly when its null space contains no nonzero vector with at most $2s$ nonzero entries. Differences of two sparse vectors have at most $2s$ active coordinates. Conversely, splitting the support of a vector of a $2s$-sparse null vector into two parts constructs two distinct $s$-sparse vectors with the same image. The strict null space property implies sparse injectivity by applying it to both parts of such a split.

Represent a finite sparse vector by a sorted doubly linked list of its nonzero coordinates. A list header stores the dimension; every ordinary linked list node stores a distinct valid coordinate index, its nonzero value, and predecessor and successor references. In a circular linked list, the endpoints connect to the header, and an all-zero vector has the header linked to itself in both directions. The representation invariant requires strictly increasing ordinary indices, valid bounds and mutually consistent forward and backward links. The abstraction function assigns zero to every coordinate absent from the list. The header is metadata, never an ordinary coordinate.

For example, $(0,3,0,0,-2,0,0,5,0)$ has dimension nine and only three stored coordinates. The header's index field can store nine even though nine is not a valid coordinate index. Keeping the header distinct is therefore essential when searching for or removing entries.

For a design matrix $X$ with $p$ columns, define ${\kappa }_m^2={\max }_{|M|=m}{\lambda }_{\max }(X_M^T{X}_M/n)$ for $1\le m\le p$. Equivalently this bounds $\Vert Xv{\Vert }_2^2/(n\Vert v{\Vert }_2^2)$ for vectors supported on at most $m$ coordinates. These quantities are nondecreasing: extend the support of a maximizing vector by zero coordinates and use the variational characterization of the largest eigenvalue. Values at $m>p$, including infinity, require a separate convention.

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.