Adjoint operator Created 2026-09-24 Updated 2026-10-14
For a bounded linear operator between real or complex Hilbert spaces, its adjoint is the unique bounded linear operator satisfyingThe inner product here is linear in its first argument. The adjoint operator transfers an output measurement back to the input: measuring against the vector gives exactly the same scalar as measuring against . It depends on both inner products.
In this real example,Both inner products equal . The dashed lines collect all vectors giving that same measurement: the output line becomes the input line . The adjoint operator therefore moves the direction that describes the measurement. It generally differs from the inverse matrix: here .
For an explicitly complex example, use the standard inner product on . In the standard orthonormal basis, the adjoint operator is represented by the conjugate transpose:For and , direct matrix multiplication givesand henceThe complex conjugate is essential to this agreement.
Existence follows from the Riesz representation theorem: for fixed , the bounded linear functional has a unique representing vector . The resulting adjoint operator has the same operator norm as , andMIT's lecture 18 develops the representation argument and the conjugate transpose example.[ref]
https://ocw.mit.edu/courses/18-102-introduction-to-functional-analysis-spring-2021/7f23bfc43ee2e1efd238a5384e5b9d51_MIT18_102s21_lec18.pdf. Rodriguez, notes by Andrew Lin, MIT 18.102, lecture 18, Theorem 185 and Example 186, 2021
This transfer explains the normal equation for a linear inverse problem: a least-squares solution has residual orthogonal to every attainable direction , so for every , equivalently . An output residual becomes an input condition through the same adjoint operator. All identities in this section concern bounded operators defined on the whole source Hilbert space; for a densely defined operator that is not bounded, use the adjoint of a densely defined operator and check its operator domain.
Algebra Created 2026-09-24 Updated 2026-10-13
Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.
For example, the polynomial equation over the real numbers factors as , giving roots and . The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field , the same integer coefficients reduce to , with roots and . The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.
In a ring with zero divisors, a familiar step can fail. Modulo , all four residue classes satisfy . For , the factorization holds modulo , yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.
The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.
Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written and geometric explanations for completing the square. In modern notation, gives or ; the historical treatment seeks the positive quantity . This illustrates both continuity of a computational idea and a difference in the permitted quantities. [ref]
https://en.wikisource.org/wiki/The_Compendious_Book_on_Calculation_by_Completion_and_Balancing/Compendium_on_calculating_by_completion_and_reduction. Al-Khwārizmī, Compendium on calculating by completion and reduction, Rosen's 1831 translation, pp. 5–11
Associativity of matrix multiplication 2026-10-31
For dimension-compatible matrices, . In coordinates both sides have entry ; distributing and regrouping the finite sums proves equality. This permits accumulating a product left to right even when a recursive algorithm groups the same transformations from the right. It does not permit changing factor order, because matrix multiplication is generally not commutative.
Beam transfer matrix Created 2026-10-24 Updated 2026-11-05
A beam transfer matrix is a linear small-angle approximation to transverse transport between two positions along a beamline:Here is transverse displacement and is trajectory slope. A drift of length and a focusing thin quadrupole magnet have respective matricesSuccessive elements compose by matrix multiplication, with the first element acting on the right. At fixed longitudinal momentum, ideal uncoupled transport governed by Hamiltonian mechanics preserves transverse phase space area and gives . During acceleration, the slope coordinate is not a fixed multiple of canonical transverse momentum; the corresponding area in can decrease through adiabatic damping of geometric emittance.
For a real one-cell matrix with , its eigenvalues obey . Thus gives a conjugate pair of distinct unit-modulus eigenvalues and bounded repeated-cell motion. If , one real eigenvalue has magnitude greater than one, producing an unstable direction. At equality, a nontrivial Jordan block can produce linear growth, so unit-modulus eigenvalues alone do not establish boundedness. This is a map for beam optics; the transfer matrix used in combinatorics has a different application.
Cancellation law Created 2026-10-25 Updated 2026-11-05
A binary operation has left cancellation when implies , and right cancellation when implies . The common factor must be in the same position in the two expressions. A group has both laws: multiplying by the inverse element on the appropriate side removes that factor.
Cancellation does not itself require inverse elements. The nonnegative integers under addition satisfy , but a positive integer has no additive inverse in that set. Conversely, matrix multiplication need not allow cancellation: a zero matrix multiplied by different matrices gives the same zero matrix. The finite cancellative semigroup theorem explains why adding finiteness and the associative property changes the conclusion.
Category of vector spaces 2026-11-05
For a fixed field , the category of vector spaces has -vector spaces as objects and -linear maps as morphisms. Composition is ordinary composition of linear maps, and each vector space has its identity map. The full subcategory of finite-dimensional vector spaces is often denoted ; allowing arbitrary dimensions gives the larger category.
After choosing bases, morphisms between finite-dimensional objects are matrices, and composition becomes ordered matrix multiplication. For example, over , putThen while . The order of arrows in a composite matters, although the category itself is defined without choosing bases.
The tensor product over gives a symmetric monoidal category with unit object . Its dualizable objects are exactly the finite-dimensional vector spaces.[ref] This tensor product differs from the categorical product: the product of two copies of is , of dimension two, while has dimension one. The zero vector space is both initial and terminal.
Centralizer of a diagonal matrix 2026-10-25
For a diagonal matrix over a field, matrix multiplication gives . Hence a matrix commutes with exactly when wherever . If all diagonal entries are distinct, the centralizer of a diagonal matrix consists exactly of diagonal matrices. When entries repeat, the allowed entries form unrestricted blocks on the corresponding eigenspaces.
Closed walk Created 2026-10-06 Updated 2026-10-14
A closed walk is a walk with equal endpoint vertices, . Under our convention this includes the zero-length walk ; returning after traversing at least one edge requires . 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]
Mathematics for Computer Science by Eric Lehman and others. Lehman, Leighton and Meyer, Mathematics for Computer Science, §§9.2 and 11.8.1: closed walks
Returning to : backtracking closed walk, closed trail with a repeated internal vertex, and graph cycle
. Details. In the shared simple graph, is a length-two closed walk that immediately backtracks along . It is not a trail, since is used twice, and it is not a graph cycle. The length-six closed walk is a trail, since its six edges are distinct, but is not a graph cycle: it returns to midway through the journey. The length-three closed walk 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]
Mathematics for Computer Science by Eric Lehman and others. Lehman, Leighton and Meyer, Mathematics for Computer Science, §11.8.1: cycles and backtracking
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 is omitted.
Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix , the walk count from powers of an adjacency matrix gives length- walks from to , for every nonnegative integer . A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; 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]
https://ocw.mit.edu/courses/14-15-networks-spring-2022/mit14_15s22_lec2.pdf. Alexander Wolitzky, Graph Theory and Social Networks, slides 9–10: powers of adjacency matrices
In our example, : the five length-two closed walks are , , , , and . Also , going round either triangle in a graph in either direction, and : 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.
Column space Created 2026-09-29 Updated 2026-10-18
The column space of a matrix is the linear span of its columns. It is the image of a linear map represented by .
If an matrix has columns , then matrix multiplication gives . Thus its column space consists of exactly the attainable output vectors in , and has a solution exactly when belongs to this column space. Its dimension is the matrix rank; the kernel instead describes input vectors in whose contributions cancel.[ref]
Solution Sets. Interactive Linear Algebra, §2.4.3, Solution Sets and Column Spans: attainable outputs and input solution sets occupy different spaces
Commuting elements 2026-10-14
Two elements commute when their two products in opposite orders agree. A particular pair of matrices may commute even when matrix multiplication is not a commutative operation on the whole set of matrices.
Continued-fraction matrix Created 2026-09-24 Updated 2026-11-05
A continued-fraction matrix packages the recurrences for continued fraction convergents into matrix multiplication. PutIf , with , , and , thenFor the identity is immediate. Right multiplication by replaces the first column by times the old first column plus the old second column, proving the convergent recurrences by mathematical induction.
Each factor has determinant , so . Any common divisor of and must therefore divide . Thus each continued fraction convergent is a fraction with coprime numerator and denominator.
Coordinate Hopf algebra of quantum SL2 Created 2026-10-14 Updated 2026-11-05
The generators obey , , , , , and . Matrix multiplication gives the coproduct, and the antipode matrix is . For , its quotient with , , and is the quantum Laurent-plane algebra , proving noncommutativity. The same quotient distinguishes from its flipped coproduct.
Covariance matrix Created 2026-09-24 Updated 2026-10-14
For a real random vector with finite second moments, its covariance matrix collects all pairwise covariances:The diagonal entries are variances. The covariance matrix is a symmetric matrix and a positive semidefinite matrix, because for every real vector ,Thus one matrix describes the variance of every linear combination of the coordinates. It is a positive-definite matrix exactly when no nonzero linear combination is constant almost surely. A deterministic linear relation produces a zero eigenvalue.
For example,has unit coordinate variances, covariance , and eigenvalues and . Its unit eigenvectors and describe directions of greatest and least projected variance. For a unit vector , direct multiplication gives : the variation in the sum direction is nine times that in the difference direction.
The spectral theorem supplies an orthonormal basis of these directions. This connects covariance matrices to principal component analysis: its leading eigenvector identifies the unit-direction projection with the largest variance. For a linear transformation , the transformed random vector has covariance matrix , so uncertainties propagate through a linear model by matrix multiplication.
CSS transform 2026-11-05
A CSS transform changes the coordinate mapping used to render a transformable element. Translation, scaling and rotation are examples of CSS transform functions. Their composition maps local points into the parent coordinate system; the CSS transform origin specifies the point around which the transformation is constructed.[ref]
CSS Transforms Module Level 1 by World Wide Web Consortium. §3, Transform Rendering Model; §§4–5, transform and transform-origin
For an own two-dimensional example, use an ordinary CSS box with
transform-box: border-box; transform-origin: 0 0;, no ancestor transforms, and local coordinates relative to that top-left origin. This fixes the CSS transform reference box and origin explicitly. Ignore the box's placement offset to isolate the transform itself.Using homogeneous column vectors, letThe list
transform: translate(10px, 0) scale(2); gives the product . Applied to point , the scale acts first:Reversing the list to scale(2) translate(10px, 0) gives and the result . The translation is scaled in the reversed composition. Matrix multiplication explains the order dependence.[ref]CSS Transforms Module Level 1 by World Wide Web Consortium. §3, matrix construction and local-to-parent mapping; §9.1, 2D functions
The zero origin is part of the example, not an irrelevant decoration. A different origin adds translations around the listed operations and can change the mapped point. The simple matrix computation also fixes its column-vector convention instead of relying on an ambiguous phrase such as applying functions in order.
For boxes governed by the CSS box model, a transform changes rendering without rearranging the surrounding normal-flow content. It can nevertheless extend CSS overflow, and transformed geometry affects client rectangles. The absence of normal-flow re-layout is therefore not a claim that every geometrical or scrolling quantity stays fixed.[ref]
CSS Transforms Module Level 1 by World Wide Web Consortium. §3, surrounding flow, overflow and client-rectangle effects
The same transformed bounds matter when constructing a CSS scroll snap area. A rendered border can be rotated while its axis-aligned bounding box is used for alignment geometry. Separating layout boxes, coordinate mappings and derived bounds makes these effects easier to calculate.
CSS transform function 2026-11-05
A CSS transform function specifies one coordinate mapping in a CSS transform list. Functions such as
translate(), scale(), rotate() and matrix() have defined argument types and geometrical meanings. The list is composed by matrix multiplication, with the CSS transform origin supplying the surrounding origin translations.[ref]CSS Transforms Module Level 1 by World Wide Web Consortium. §9.1, 2D transform functions; §§3 and 10, composition
For the two-dimensional function
matrix(a,b,c,d,e,f), a homogeneous column-vector convention givesIn particular, and . The six arguments do not fill the displayed matrix row by row.[ref]For an own example with zero origin,
matrix(2,0,0,3,10,-5) maps point toThis combines horizontal scaling by two, vertical scaling by three and a translation. The arguments and coordinates are chosen to isolate the mapping, not to measure a browser's glyph rendering.Order matters when composing functions. With zero origin,
translate(10px,0) scale(2) maps to , while scale(2) translate(10px,0) maps it to . In column-vector form, the first matrix product is and the second ; the translation itself is scaled in the latter.[ref]CSS Transforms Module Level 1 by World Wide Web Consortium. §3, function-list matrix construction; §10, transform lists
The CSS transform reference box is also part of interpreting arguments that use percentages. A function's spelling alone does not determine every resulting coordinate without its lengths, percentage bases, origin and ancestor mappings. The reusable mathematical description is an ordered coordinate transformation with those inputs stated explicitly.
Determinant Created 2026-09-24 Updated 2026-10-14
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]
https://www.math.ucla.edu/~rse/algebra_book.pdf#page=716. Elman, Lectures on Abstract Algebra, section 121: determinant and inverse
Start with an explicit matrix and its action on a vector:The columns are the images of the standard basis vectors: and . Consequently the unit square with corners becomes the parallelogram with corners . 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]
https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter04/section01.html. MIT calculus notes, section 4.1: determinants and area
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 to , which has zero area despite nonzero length. Since , 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 , recovery is possible, and the complete matrix multiplication check isHere is the identity matrix. The inverse matrix restores the original square, shrinking its area by . Generally, the adjugate identity gives whenever the determinant is nonzero over a field; this is why the denominator matters.[ref]
https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter04/section04.html. MIT calculus notes, section 4.4: determinant and inverse
The multiplicativity of the determinant describes two successive deformations. Matrix multiplication means that applies first, then . TakeThe first linear map doubles area; the second multiplies the resulting area by five. Thus the unit square passes through areas , with the last parallelogram bounded by . 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]
https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter32/section04.html. MIT calculus notes, section 32.4: determinant products
Successive linear maps multiply area factors: one becomes two, then ten
. Details. 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 , 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 , 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 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]
https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter24/section02.html. MIT calculus notes, section 24.2: the Jacobian area factor
For general , regard the columns as ordered arguments. The determinant is the unique alternating multilinear map to the scalar field normalized by . 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]
https://web.mit.edu/18.06/www/Spring16/lecture22.pdf. Barwick, MIT 18.06 Lecture 22: the determinant axioms
Separate linearity does not mean the determinant is a linear map on the whole matrix. Scaling every column of an -by- matrix by gives . For our two-dimensional example, : 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 deletes row and column . 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]
https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter04/section03.html. MIT calculus notes, section 4.3: cofactor expansion
Consider the original linear systemCompleting the square proves that is a symmetric positive-definite matrix:The Jacobi preconditioner has . Symmetric positive-definite preconditioning givesIts eigenvectors and have eigenvalues and . HenceThe characteristic polynomial of is . Its eigenvalues and spectral condition number of a positive-definite matrix areThe ellipse axis ratio drops from about to . The transformation multiplies the second coordinate by ten, bringing the two energy scales together.
Both panels show the same energy level sets, expressed in error coordinates and . Their coordinate axes have equal scales. The marked displacement becomes ; its energy remains . These are exact contours of the specified quadratic form.
Solving the original equations givesDirect matrix multiplication checks both linear-system residuals:By contrast, left preconditioning gives , which is visibly not a symmetric matrix, despite having the same positive eigenvalues as .
A bad scaling can reverse the benefit: the still valid symmetric positive-definite matrix gives . Its Rayleigh quotients on the coordinate unit vectors are and , so . Cheapness and positive definiteness do not guarantee improved conditioning.
Exponentiation by squaring Created 2026-10-03 Updated 2026-10-20
Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit to a prefix of value replaces by , 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]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. Section 3.4, pp. 65–66: binary-prefix recurrence and repeated-squaring algorithm; p. 67: primality-testing application
For a concrete calculation, , so . The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize from the leading digit one, then process only the remaining digits :Thus , using three squarings and two further multiplications, instead of twelve successive multiplications starting at .
For a general positive integer with leading digit , set and, for , first replace by , then multiply it by if . Return . 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 , where is the value of the digits already read. Initially and . If the next digit is , then squaring and optionally multiplying give , exactly the next prefix. At termination . 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 , return the identity element without performing a multiplication. This is the empty-product convention ; if , the algorithm therefore returns one for by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute , counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.
Farkas' lemma Created 2026-10-07 Updated 2026-10-14
For a real matrix and a vector , exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system is nonnegative; in the second system 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 as . Then is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution explains how to build from those columns. A certificate instead defines a linear functional . The condition says that its dot product with every generating column is nonnegative, and hence with every point of . But places the target strictly on the other side of the hyperplane . Thus belongs to the dual cone of and rules out every allowed conic combination at once.
A certificate that can be checked by eye. Take the identity matrixHere is the nonnegative orthant. The equation forces , violating . The certificate givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while has first coordinate . For comparison, the target is obtained with .
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 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 , closedness of finitely generated cones makes a closed convex cone, so separation from a closed convex cone supplies and for every . Testing each column gives . Concretely, let be the Euclidean projection onto a convex set of onto and set . The projection inequality gives for . Testing and gives , whence . In the example, and . Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.
Fibonacci matrix Created 2026-10-20 Updated 2026-11-05
With , , the Fibonacci matrix advances consecutive Fibonacci numbers:Multiplying by proves the formula by induction. Since matrix powers obey , their entries give Fibonacci addition formulas. Exponentiation by squaring computes with matrix multiplications, including directly in modular arithmetic. The determinant identity also makes the update invertible modulo every positive integer.







