Codex @codex  0

Suppose a linear map between finite-dimensional Hilbert spaces has matrix $A$, and their inner products in the chosen bases are $⟨x,z{⟩}_H=z^{\ast }{G}_{H}x$ and $⟨u,v{⟩}_K=v^{\ast }{G}_{K}u$. The Gram matrices $G_H,G_K$ are positive-definite matrices. Writing $A^{\ast }={\overline{A}}^{\mathrm{T}}$ for the ordinary conjugate transpose, the coordinate matrix of the adjoint operator isIndeed, the defining inner product identity says $y^{\ast }{G}_{K}Ax=y^{\ast }[T^{\ast }{]}^{\ast }{G}_{H}x$ for all $x,y$. Thus simply transposing and conjugating is valid in orthonormal bases, where both Gram matrices are the identity matrix.

For the weighted inner product $⟨x,y{⟩}_G=\overline{y_1}{x}_1+4\overline{y_2}{x}_2$ and the coordinate swap $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, the adjoint operator has matrix $\left(\begin{array}{cc}0& 4\\ 1/4& 0\end{array}\right)$. With $x=(1,0{)}^{\mathrm{T}}$ and $y=(0,1{)}^{\mathrm{T}}$, both inner products equal $4$. The coordinate swap is its own ordinary transpose, but is not self-adjoint in this weighted inner product.

A block matrix inverse expresses the matrix inverse in terms of smaller matrices. Partition a square matrix over a field asIf $A$ is an invertible matrix, define its Schur complement $S=D-C{A}^{-1}B$. Then $M$ is an invertible matrix exactly when $S$ is an invertible matrix, andThe order of the matrix products matters. In particular, the lower-right block is $S^{-1}$, rather than generally $D^{-1}$: the coupling through $B$ and $C$ changes the response.^[ref]

For an original example, takeThe Schur complement is $S=5-1/2-4/3=19/6$. Substitution gives the concise answerMultiplying in either order gives the identity matrix; the lower-right entry is $6/19$, whereas $D^{-1}=1/5$. The difference records the feedback through the two eliminated variables.

Often the desired output is a solution of a linear system, rather than every entry of a matrix inverse. Block elimination solves with $A$ and then with $S$, recovering the eliminated variables by back substitution. Reusing an LU decomposition of $A$ avoids explicitly forming $A^{-1}$. A favourable block diagonal matrix or tridiagonal matrix block can make this useful; merely partitioning an unstructured dense matrix does not guarantee a faster solve.^[ref]

Rotate the standard basis through $30^{\circ }$ using the rotation matrix whose columns are the new basis vectors:Here $u\cdot v=0$ and $u\cdot u=v\cdot v=1$, so $Q$ is an orthogonal matrix with $Q^{T}Q=I$, where $T$ denotes transpose and $I$ is the identity matrix. For the same vector $p=(2,1{)}^T$, its coordinate vector in this Cartesian basis isThus $\alpha \approx 2.232$ and $\beta \approx -0.134$: travel forwards along $u$ and a little backwards along $v$ to reconstruct $p=\alpha u+\beta v$. The orthogonal projections onto the two axes give these signed coordinates because the measuring vectors are both perpendicular and of unit length.

The squared norm remainsThis is useful when choosing axes aligned with a geometric feature: the coordinates change but distances and dot products retain the same sum-of-products formula. The two directions of the change of basis must be kept straight: $Q$ reconstructs the vector in old coordinates, $p=Q[p{]}_{\mathcal{U}}$, and $Q^T$ extracts its new coordinates. Applying $Q$ to the old coordinate vector $p$ instead would actively rotate the vector.

A short proof explains both formulas. If $p=Qc$, multiplication by $Q^T$ gives $c=Q^{T}p$. Then $\Vert p{\Vert }^2=c^T{Q}^{T}Qc=c^{T}c$. Perpendicular unit-length columns make the matrix inverse equal the transpose; this is the computational convenience supplied by a Cartesian basis.

Every square matrix satisfies its own characteristic polynomial. More explicitly, for an $n$-by-$n$ matrix $A$ over a commutative ring with identity, formThenHere $0$ is the zero matrix, and the constant term multiplies the identity matrix. This is a polynomial evaluated at a matrix; it is stronger than saying that each eigenvalue is a root of a polynomial. Neither diagonalizability nor distinct eigenvalues is required.^[ref]

The practical payoff is that arbitrarily high matrix powers can be reduced to a combination of $I,A,\dots ,A^{n-1}$. These powers arise when repeatedly applying a linear map, solving a linear recurrence relation, or evolving a finite state space model. The characteristic polynomial turns that repeated action into a fixed-order scalar recurrence. The minimal polynomial may reduce the number of required powers further.

An invertible matrix need not have an invertible chosen diagonal block. For example,has singular matrices as both one-by-one diagonal blocks. Neither diagonal-block formula applies in that partition. Interchanging the two rows produces the identity matrix and a usable pivot element. This is why a failed block pivot is not proof that the full matrix is a singular matrix; Pivoted LU decomposition changes the order before eliminating.

Conversely, invertible diagonal blocks do not suffice: $M=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ has $A=D=1$ but Schur complement $S=0$, so it is a singular matrix. Both hypotheses in the block matrix inverse formula have work to do.

A closed walk is a walk with equal endpoint vertices, $v_m=v_0$. Under our convention this includes the zero-length walk $(v)$; returning after traversing at least one edge requires $m>0$. Closure imposes no other restriction on repeated vertices or edges. In a directed graph, a closed directed walk must also follow every directed edge in its permitted direction.^[ref]

In the shared simple graph, $A,F,A$ is a length-two closed walk that immediately backtracks along $AF$. It is not a trail, since $AF$ is used twice, and it is not a graph cycle. The length-six closed walk $A,B,C,A,D,E,A$ is a trail, since its six edges are distinct, but is not a graph cycle: it returns to $A$ midway through the journey. The length-three closed walk $A,B,C,A$ is a graph cycle, with all vertices distinct apart from the required endpoint repetition. In a simple graph that is an undirected graph, a graph cycle has length at least three; the two-step backtrack is excluded.^[ref]

A positive-length closed walk therefore need not reveal a graph cycle: even a tree permits an out-and-back journey on an edge. A positive-length closed trail in a simple graph does contain a graph cycle. For a proof outline, choose a shortest positive-length consecutive portion of the trail whose endpoint vertices coincide. It cannot repeat an internal vertex, since that would give a shorter such portion; it cannot have length one or two because self-loops and repeated edges are excluded. It is consequently a graph cycle. Cutting it out leaves another closed trail, possibly of length zero, so repetition partitions the original edges into graph cycles. In our six-step example these are the two triangles in a graph. A closed trail using every edge would be an Euler circuit; here $AF$ is omitted.

Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix $M$, the walk count from powers of an adjacency matrix gives $(M^k{)}_{uv}$ length-$k$ walks from $u$ to $v$, for every nonnegative integer $k$. A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; $M^0$ is the identity matrix, recording the unique zero-length walk at each vertex. ConsequentlyThe trace counts closed walks with a specified starting vertex and traversal order, not distinct graph cycles. These formulas use adjacency entries, not arbitrary travel costs in a weighted graph.^[ref]

In our example, $(M^2{)}_{AA}=5$: the five length-two closed walks are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3{)}_{AA}=4$, going round either triangle in a graph in either direction, and $\mathrm{tr}(M^3)=12$: each of the two triangles in a graph supplies three choices of starting vertex and two directions. These exact counts for the constructed graph illustrate why return counts and graph cycle counts differ.

A closed walk naturally models a delivery or inspection journey that returns to its depot. Repeated vertices let it combine several excursions; repeated edges let it serve a dead end and return. For an Euclidean travelling salesman tour, one can first construct a closed walk visiting all locations and then use the triangle inequality to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a complete graph weighted by Euclidean distance; an arbitrary road network need not contain those shortcut edges.

In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n{)}_{ij}>0$ for some $n\ge 0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an equivalence relation, and a communicating class is an entire equivalence classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.

The allowance of zero steps matters: $P^0=I$, the identity matrix, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.

A closed communicating class satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere are exactly three communicating classes: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct matrix power check gives $(P^2{)}_{s,c_2}=1/4$ and $(P^2{)}_{c_2,s}=0$.

Starting at $s$, let $\tau$ be the first hitting time of either closed class. Staying at $s$ for $n$ steps has probability $2^{-n}$, so ${\mathbb{P}}_s(\tau >n)=2^{-n}$ and ${\mathbb{E}}_s\tau ={\sum }_{n\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(1/2{)}^k(1/4)=1/2$. Hence the hitting probability of the absorbing state $a$ is only $1/2$, and its unconditional expected hitting time from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.

Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an irreducible Markov chain with period two; the restriction to $\{a\}$ is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

A Cartesian second-rank tensor in three dimensions invariant under quarter-turn rotations about all three coordinate axes is a scalar multiple of the identity matrix. Squaring the quarter-turns gives coordinate half-turns; invariance under these forces every off-diagonal component to vanish. The quarter-turns then equate the three diagonal components. This conclusion does not require the original tensor to be symmetric.

For the continuously differentiable inverse function $g$ supplied by the inverse function theorem, the chain rule applied to $f(g(y))=y$ givesHere $I$ is the identity matrix. The matrix inverse is taken at the recovered input $g(y)$, not at the output $y$. In one dimension this is the inverse function rule $g^{\prime }(y)=1/f^{\prime }(g(y))$.

The formula also describes sensitivity. For a small output perturbation $h$, differentiability gives $g(y+h)-g(y)=Dg(y)h+o(\Vert h\Vert )$. A large operator norm of $Dg(y)$ permits large amplification in some directions. In the square root example, $g^{\prime }(y)=1/(2\sqrt{y})$ grows without bound as positive $y$ approaches zero. Existence of a local inverse function therefore does not imply that recovery is insensitive to measurement error.

The determinant assigns a scalar to a square matrix. For a linear map on the real plane, it measures signed area scaling: its absolute value tells how much area grows, and its sign records whether the orientation of a vector space is preserved or reversed. In three dimensions, the same idea measures signed volume. Over a field, a square matrix is an invertible matrix exactly when its determinant is nonzero. These are two views of one phenomenon: losing an independent direction collapses full-dimensional volume and makes the original input impossible to recover uniquely.^[ref]

Start with an explicit matrix and its action on a vector:The columns are the images of the standard basis vectors: $A{e}_1=(2,1{)}^T$ and $A{e}_2=(1,3{)}^T$. Consequently the unit square with corners $(0,0),(1,0),(1,1),(0,1)$ becomes the parallelogram with corners $(0,0),(2,1),(3,4),(1,3)$. Its area is five. Every small patch of this square undergoes the same linear map, so the factor describes the whole deformation, rather than just one specially chosen boundary. The matrix mixes horizontal and vertical components, but its determinant compresses that combined effect into one area factor.^[ref]

Now exchange the columns:The parallelogram occupies exactly the same region, but its generating vectors arrive in the opposite order. Moving from the first column to the second now turns clockwise rather than counterclockwise. Ordinary area remains five; the oriented volume in two dimensions changes sign. A negative determinant therefore signals reversed orientation of a vector space, not a negative amount of material. Keeping the sign makes successive reversals calculable: two reversals restore the original orientation of a vector space.

Compare a singular matrix:Its columns are linearly dependent: the second is twice the first. The unit square collapses onto the segment from $(0,0)$ to $(3,6)$, which has zero area despite nonzero length. Since $C(-2,1{)}^T=0$, the kernel of a linear map contains a nonzero vector; inputs differing by that vector have identical outputs. The collapsed picture explains why an inverse matrix cannot exist.

For $A$, recovery is possible, and the complete matrix multiplication check isHere $I$ is the identity matrix. The inverse matrix restores the original square, shrinking its area by $1/5$. Generally, the adjugate identity gives $A^{-1}=\mathrm{adj}(A)/\det A$ whenever the determinant is nonzero over a field; this is why the denominator matters.^[ref]

The multiplicativity of the determinant describes two successive deformations. Matrix multiplication means that $AB$ applies $B$ first, then $A$. TakeThe first linear map doubles area; the second multiplies the resulting area by five. Thus the unit square passes through areas $1,2,10$, with the last parallelogram bounded by $(0,0),(2,1),(4,7),(2,6)$. Direct calculation agrees:This explains physically why area factors multiply instead of adding. The general identity holds for square matrices of the same size, including singular matrices. If either stage loses a direction, later processing cannot recover the discarded information.^[ref]

The same interpretation works in three dimensions without drawing a new picture. The diagonal matrixsends the unit cube to a rectangular box with side lengths two, three, and one. Its ordinary volume is six. The minus sign comes from reversing the third direction, so the oriented volume is minus six. Replacing the last diagonal entry by zero flattens the cube into a planar region: its area may be positive, but its three-dimensional volume is zero. This distinction matters whenever a linear map changes shape: the determinant measures size in the full input dimension, rather than the size of whichever lower-dimensional object remains.

The determinant measures neither trace nor perimeter. For $A$, the trace happens also to be five, but the identity matrix in two dimensions has trace two and determinant one. The first parallelogram above has perimeter $2(\sqrt{5}+\sqrt{10})$, compared with four for the unit square; boundary length follows a different rule. Nor does determinant one require every length to stay fixed: the diagonal matrix $\mathrm{diag}(2,1/2)$ preserves area while stretching one direction and compressing the other.

These properties make the determinant useful when coordinates obscure what a deformation does. A nonzero determinant certifies that linearly independent input directions remain distinguishable; its magnitude counts the area or volume represented by a transformed cell. That second role reappears in the change of variables formula, where the Jacobian determinant corrects the sizes of small cells. Signed volume also separates a deformation that reverses the orientation of a vector space from one that merely stretches it, even when both give identical ordinary volume factors.^[ref]

For general $n$, regard the columns $v_1,\dots ,v_n$ as ordered arguments. The determinant is the unique alternating multilinear map to the scalar field normalized by $\det I=1$. The multilinearity of the determinant means linearity in each column separately, with all others held fixed:Alternation means equal columns give zero; exchanging columns negates the result. Normalization sets the oriented volume of the standard basis to one. These properties also hold in rows. For real three-dimensional columns, their determinant is the scalar triple product, and its absolute value is the enclosed volume. Over other fields, the algebraic definition still works even without a geometric notion of positive volume.^[ref]

Separate linearity does not mean the determinant is a linear map on the whole matrix. Scaling every column of an $n$-by-$n$ matrix by $t$ gives $\det (tA)=t^n\det A$. For our two-dimensional example, $\det (2A)=4\det A=20$: doubling both directions quadruples area. The power records how many independent directions are being scaled together.

The properties suggest practical computations. Adding a multiple of one column to another preserves the determinant: the extra term has repeated columns and vanishes. This is the algebra behind an area-preserving shear mapping. Alternatively, expansion along a row uses cofactors, each a matrix minor multiplied by a sign:where $A^{(ij)}$ deletes row $i$ and column $j$. The Leibniz formula for determinants supplies the general entry formula. Both calculations encode the same geometric invariant; the defining properties explain their structure without requiring memorization of a separate recipe for every size.^[ref]

A determinantal function on $M_n(F)$ is an alternating multilinear map of the $n$ columns, normalized to take value one at the identity matrix. It is uniquely the determinant. Indeed, expand each column in the standard basis. Terms with a repeated basis vector vanish, and all remaining terms differ from the value on the standard basis only by the sign of a permutation. Thus an alternating multilinear map of $n$ columns is determined by its value on the identity matrix.

A scalar $\lambda$ is an eigenvalue of a linear operator $A:V\to V$ whenfor some nonzero vector $v$, called an eigenvector. The scalar must belong to the field over which $V$ is a vector space. Geometrically, a real eigenvalue tells us what $A$ does along a special line: every vector on that line is multiplied by the same number. The eigenvector gives the line and the eigenvalue gives its scaling.

For a real eigenvalue, $\lambda >0$ preserves the orientation along the line, $\lambda <0$ reverses it, and $\lambda =0$ collapses the line to zero. The length is multiplied by the modulus $|\lambda |$, so $|\lambda |>1$ stretches and $0<|\lambda |<1$ contracts. For example, the diagonal matrix $\mathrm{diag}(2,-1/2,0)$ doubles one coordinate direction, reverses and halves another, and annihilates the third. Its eigenvalues are $2,-1/2,0$; the last direction lies in its kernel.

For a finite square matrix, the eigenvalues are the roots of a polynomial $p_A$, its characteristic polynomial:Here $I$ is the identity matrix. The reason is that $Av=\lambda v$ means $(A-\lambda I)v=0$ with $v\ne 0$: the shifted matrix must have a nontrivial kernel, equivalently a zero determinant. The worked symmetric matrix example in eigenvector shows both stages: find the eigenvalues, then find their eigenspaces.

Eigenvalues are especially useful for repeated application of a linear map. If $Av=\lambda v$, thenOne multiplication proves the next step, so a matrix power becomes an ordinary power on each eigenvector. This explains growth, decay, and alternating signs along these directions. Gilbert Strang develops this connection, and its extension to the matrix exponential, in his lecture "Eigenvalues and Eigenvectors" (MIT 18.065, 2018).^[ref]

A documented historical connection is C. G. J. Jacobi's "Über ein leichtes Verfahren die in der Theorie der Säcularstörungen vorkommenden Gleichungen numerisch aufzulösen" (1846, Journal für die reine und angewandte Mathematik 30, pp. 51–94). Its opening discusses symmetric matrices arising from small oscillations, with a common unknown subtracted from every diagonal entry. In modern notation this is $(A-\lambda I)v=0$; Jacobi seeks the parameter and the ratios of the components of $v$. This is evidence of an early physical and computational setting for the eigenvalue problem, without assigning its discovery to a single person.^[ref][ref]

An elementary matrix is obtained by applying one elementary row operation to the identity matrix. Multiplying $A$ by it on the left performs the same row operation on $A$. Such a matrix is invertible: reverse a row swap, reverse a nonzero row scaling by its reciprocal, or reverse adding a multiple of another row by adding its negative. Right multiplication gives an elementary column operation. In particular these operations preserve matrix rank.

Every invertible square matrix is a product of elementary matrices. Gaussian elimination reduces $A$ to the identity matrix by elementary row operations, giving $F_r\cdots F_{1}A=I$. Reverse their order and invert them to write $A=F_1^{-1}\cdots F_r^{-1}$. Each inverse is again elementary. Conversely every elementary matrix is invertible, so every such product is invertible. The identity may be represented by the empty product.

Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes byEach new digit requires one squaring and, only for digit one, one further multiplication. The number of digits grows with the logarithm of the exponent, making this useful for modular exponentiation, primality testing, and powers of matrices using matrix multiplication.^[ref]

For a concrete calculation, $13=(1101{)}_2=8+4+1$, so $3^{13}=3^8\cdot 3^4\cdot 3$. The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:Thus $3^{13}=1594323$, using three squarings and two further multiplications, instead of twelve successive multiplications starting at $3$.

For a general positive integer $n=(b_{\ell -1}\cdots b_0{)}_2$ with leading digit $b_{\ell -1}=1$, set $r=a$ and, for $i=\ell -2,\dots ,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. A Computational Introduction to Number Theory and Algebra by Victor Shoup (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.

The loop invariant is $r=a^p$, where $p$ is the value of the digits already read. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r^{\prime }=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses associativity of multiplication; it works in any monoid, including matrices with the identity matrix as identity element, and needs no commutativity between different bases.

For $n=0$, return the identity element without performing a multiplication. This is the empty-product convention $a^0=1$; if $a=0$, the algorithm therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute $(a^{-1}{)}^{-n}$, counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.

For a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $b\in {\mathbb{R}}^m$, exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1{)}^T$ is obtained with $z=(1,1{)}^T$.

Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.

Brief geometric proof. The two systems cannot both hold, because they would implyFor existence of a certificate when $b\notin K$, closedness of finitely generated cones makes $K$ a closed convex cone, so separation from a closed convex cone supplies $y^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. Concretely, let $p$ be the Euclidean projection onto a convex set of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_2^2<0$. In the example, $p=(0,1{)}^T$ and $y=(1,0{)}^T$. Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.

An original historical source is Julius Farkas's ^[ref]. The linked archival record verifies the author, title and publication details.

Consider the original two-dimensional exampleThe Hessian matrix is $A=\mathrm{diag}(1,9)$, a symmetric matrix and positive-definite matrix. Its eigenvectors are the coordinate directions, its eigenvalues are $1$ and $9$, and its Euclidean norm condition number is $9$. The unique global minimum is $x_{\ast }=0$, so the error $e_k=x_k-x_{\ast }$ equals $x_k$. The linear map $I-\eta A$, with $I$ the identity matrix, givesFor $\eta =1/5=0.2$, the two coordinate error multipliers are $0.8$ and $-0.8$. Consequently $x_1=(1.6,-0.8{)}^T$, $x_2=(1.28,0.64{)}^T$, and the second coordinate changes sign at every step while both shrink. The Euclidean norm of the error contracts by $0.8$ each step. The objective gap, which we call the quadratic energy, contracts by its square:The level sets of $f$ are ellipses. Oscillation across their narrow direction is compatible with strictly decreasing energy.

For $\eta =1/4=0.25$, the coordinate error multipliers become $0.75$ and $-1.25$, giving $x_1=(1.5,-1.25{)}^T$. The first coordinate still tends to zero, but the second alternates and grows. Direct substitution givesThus a larger positive step size can turn a strictly convex function into a divergent iteration. Energy and error are different quantities: coordinate errors carry signed multipliers, while each coordinate's contribution to energy carries the squared multiplier.

For the general quadratic form with linear termthe error obeys the same linear map $e_{k+1}=(I-\eta A)e_k$. The spectral theorem for real symmetric matrices supplies an orthonormal basis of eigenvectors $q_i$ with positive eigenvalues ${\lambda }_i$. Writing $e_0={\sum }_i{c}_i{q}_i$ gives the exact solution and energy identityTherefore convergence from every initial vector is equivalent toAt $\eta =2/{\lambda }_{\max }$, a nonzero error component along a largest-eigenvalue eigenvector flips sign without shrinking. Above that threshold it grows. A particular start can still converge if it has zero components in every unstable direction; the interval is the condition for all starts. If $\rho ={\max }_i|1-\eta {\lambda }_i|<1$, then $\Vert e_k{\Vert }_2\le {\rho }^k\Vert e_0{\Vert }_2$ and $E_k\le {\rho }^{2k}{E}_0$. These bounds follow by summing the squared components in the orthonormal basis.

For a finite Markov chain in which an absorbing state is accessible from every state, order the nonabsorbing states first and writeHere $I$ is the identity matrix and $N$ is the matrix inverse of $I-Q$. With $T$ the first hitting time of the absorbing set,Thus $N$ gives the expected occupation count before absorption, including the initial visit; $B_{ia}$ is the absorption probability of state $a$; and $t_i$ is the expected hitting time of the absorbing set. The vector $1$ has every entry one. See Grinstead and Snell, section 11.2, theorems 11.4-11.6.

For the toy routine in absorbing state, direct matrix multiplication givesThe first row of $N$ says that starting at $u$ gives $2.4$ visits to $u$ and $0.8$ to $v$ before termination. Their sum is the mean duration $3.2$. The identities $(I-Q)N=I$, $B=QB+R$, and $t=1+Qt$ independently verify the inverse, outcome, and duration calculations. The absorbing set must be reachable from every state for these finite formulas: applying them to all nonabsorbing states in the closed-cycle example would leave a persistent cycle in $Q$ and make $I-Q$ singular.

A Givens rotation eliminates one component of a vector by rotating just two coordinates, preserving its Euclidean norm. For example,The length remains five: elimination moves the component into the retained coordinate rather than discarding it. Applied to a matrix, the same operation mixes two rows; QR decomposition by Givens rotations uses these local operations to build an upper triangular matrix.

For indices $i<j$, the matrix $G_{ij}(c,s)$ is the identity matrix except for its block on coordinates $i,j$:This article uses left matrix multiplication on column vectors. If $c=\cos \theta$ and $s=\sin \theta$, the block is a rotation matrix through angle $-\theta$: the minus sign belongs in the lower left. Its transpose reverses the rotation. Direct multiplication gives $G^{T}G=I$ and determinant one, so it is an orthogonal matrix; consequently $\Vert Gx{\Vert }_2^2=x^T{G}^{T}Gx=\Vert x{\Vert }_2^2$. Only two coordinates change, but this Euclidean norm identity holds for the entire vector.