Matrix inverse Created 2026-09-24 Updated 2026-10-14
For an -by- square matrix over a field, its matrix inverse is an -by- matrix satisfying both identitieswhere is the identity matrix. It exists exactly when is an invertible matrix, equivalently when its matrix rank is or its determinant is nonzero. It reverses the linear map: applying and then recovers the input, while applying and then recovers the output.[ref]
https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-3-multiplication-and-inverse-matrices/. Strang, MIT 18.06 Lecture 3: the two inverse identities
The matrix inverse is unique. If and both satisfy the identities, then . Although the definition is two-sided, for finite square matrices either identity alone suffices: forces a trivial kernel, whereas forces surjectivity; either makes an invertible matrix by the rank-nullity theorem. Rectangular matrices may have only one of these properties.
For a concrete example, takeDirect matrix multiplication givesConsequently the vector follows a reversible journey:The columns and are the images of the standard basis vectors. They turn the unit square into a parallelogram; the matrix inverse restores both the square and its surrounding grid. Since , this example changes shape while preserving area, illustrating that invertibility does not require preserving lengths or angles.
For comparison, the singular matrixcannot have a matrix inverse: the output cannot specify which of the two inputs occurred. Their difference belongs to its kernel. Indeed collapses the plane to a line, its matrix rank is one, and its determinant is zero. No subsequent function of the output alone can reconstruct every input.
An important use of the matrix inverse is describing the unique solution of a linear system:For , the preceding computation solves and , giving . In computation, usually solve the linear system using Gaussian elimination and a factorization such as an LU decomposition, rather than forming every entry of the matrix inverse. The inverse formula specifies the answer; a factorization provides a reusable way to compute it for each right-hand side.[ref]
https://www.mit.edu/~18.06/Spring17/final-sol.pdf. MIT 18.06, Spring 2017 final solutions, problem 5(b): solve with triangular factors rather than computing inverses
Here the LU decomposition is especially simple:Solve by forward substitution in a triangular system: and . Then solve by backward substitution in a triangular system: and . The same factors work when changes. If the whole matrix inverse is actually needed, its th column is the solution of , where is the th standard basis vector.
Reversing several operations means undoing the last one first. For invertible matrices of the same size,because , and the product in the other order is also . This is why a change-of-basis matrix uses its matrix inverse to reverse the direction of coordinate conversion.
Numerical linear algebra Created 2026-09-24 Updated 2026-11-05
Numerical linear algebra develops algorithms for linear systems, least squares, eigenvalue problems and other matrix computations, with attention to roundoff error, cost and storage. A mathematically equivalent formula can behave very differently in floating-point arithmetic: solving through an LU decomposition avoids forming an explicit matrix inverse, while a QR decomposition gives an orthogonal route to least squares.
The central distinction is between accuracy of the computed answer and accuracy of the problem it solves. For , an approximate vector has linear-system residual . A small linear-system residual need not imply a small forward error when the condition number is large. For the exact examplethe solution is , whereas has Euclidean norm residual but Euclidean norm error . Here the condition number in the spectral norm is . The lost component barely changes the equations because its coefficient is tiny.
Direct linear solvers such as Gaussian elimination factor a matrix; iterative methods such as conjugate gradient successively improve a vector. For a large sparse matrix, fill-in and matrix preconditioning can matter as much as arithmetic count. The task is to preserve the structure that makes a computation accurate and affordable.
Numerical method Created 2026-10-14 Updated 2026-10-18
A numerical method is an algorithm for computing an exact or approximate solution to a mathematical problem through finitely many arithmetic operations and other prescribed steps. For example, Gaussian elimination solves a linear system exactly in exact arithmetic, whereas finite precision can introduce roundoff error.
Each run of Simon's algorithm uses one oracle call and returns one uniform sample from . Collect samples as rows of a matrix and solve over the two-element field using Gaussian elimination. Once the rows have matrix rank , the kernel is , so the promised nonzero vector is uniquely determined. Dependent samples, including , must be allowed for; exactly runs need not suffice.
For a rough quantitative estimate, put . When the existing samples span an -dimensional vector subspace of , the next sample increases the matrix rank with probability . The random spanning of a binary vector space estimate givesAlternatively, samples fail to span with probability less than : failure means some nonzero linear functional on the -dimensional space vanishes on every sample, and a union bound gives . ConsequentlyThe Gaussian elimination requires only a polynomial amount of classical work, for example bit operations for samples. The degenerate case needs no calls because the promise already specifies .
Classically, distinct inputs with equal function values reveal . Uniformly sampling distinct inputs finds such a function collision after roughly calls, by the birthday square-root scale. For sampled inputs, the expected number of colliding pairs is . The usual randomized classical query complexity of Simon's problem is therefore exponential in , on the scaleA straightforward exhaustive classical search instead uses calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.
Past exam of the mathematical methods I course of the University of Oxford 2017 resit 5 a Solution 2026-10-25
Gaussian elimination of the first two equations gives and . The third then reduces to . HenceIn the infinite family , and , for . This makes the distinction between an inconsistent linear system and a free parameter explicit; its coefficient matrix has determinant .
Past exam of the mathematical methods I course of the University of Oxford 2018 6 Solution 2026-10-25
The characteristic polynomial factors as . Thus in algebraic multiplicity. An orthonormal basis of corresponding eigenvectors isDirect multiplication verifies , , . Their mutual Hermitian inner products vanish and each has norm one, which proves linear independence. For the repeated eigenvalue, Gaussian elimination givesHence . The second equality follows from the rank-nullity theorem and agrees with the two-dimensional eigenspace. A repeated eigenvalue alone would not imply a two-dimensional eigenspace for an arbitrary matrix; here the Hermitian matrix is diagonalizable.
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 31 3 Solution 2026-10-14
A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.
First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program with , , and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as again. Put andUse nonnegative variables and , with a temporary unrestricted multiplier . Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by , and substitute in the other equations. Because has full row rank, is equivalent to these conditions. For no remaining equality rows, simply omit and its empty equations.
Let and . Collect these substituted equations into , impose , and let select the coordinate . The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 57 4 Solution Created 2026-10-03 Updated 2026-10-14
Use the undirected graph of the symmetric off-diagonal sparsity pattern. Reading the original matrix gives the edgesThis connected nine-vertex, eight-edge graph is a tree. A leaf-removal perfect elimination ordering isThe corresponding lists of remaining neighbors are, in order, . Thus simultaneous row and column permutation to this ordering allows Gaussian elimination without fill-in.
Here are the precise facts that justify the procedure. First, eliminating index makes the remaining entriesOnly pairs of remaining neighbors of can acquire a new nonzero entry. Consequently a vertex whose remaining neighbors form a clique can be eliminated without structural fill. Such a vertex is simplicial. An ordering in which each successive vertex is simplicial is a perfect elimination ordering. The graph characterization says that a graph admits such an ordering if and only if it is a chordal graph, meaning every cycle of length at least four has a chord. A tree has no cycles; more concretely, every nontrivial finite tree has a leaf, and removing a leaf leaves a forest. These statements explain why successive leaf removal works here without having to find a general-purpose chordal ordering.
Second, for a symmetric positive-definite matrix, every diagonal pivot and every successive Schur complement is positive definite. For example, if the first pivot is and its coupling column is , then for any nonzero remaining vector ,Thus no zero pivot requires abandoning the proposed ordering. Since each eliminated vertex here has at most one remaining neighbor, its Schur update changes only a diagonal entry. This proves the claimed fill-free LDL decomposition or Cholesky decomposition for every positive-definite matrix with the given pattern, including cases with additional accidental zeros. It is leaf elimination of a tree-pattern positive-definite matrix.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 17 4 Solution Created 2026-10-03 Updated 2026-10-14
Use finitely generated right projective modules throughout. The group K0 of a ring is the Grothendieck group of their direct-sum monoid, with . The group K1 of a ring is , equivalently the abelianization of the stable general linear group. Stabilization is ; is generated by elementary transvections. The stable elementary subgroup is the commutator subgroup: elementary transvections are commutators using a third index, and stable block interchange and elementary row identities make the quotient abelian.
Write for the lower-right ring, printed as in the source. A Milnor square has unital commuting maps, is a pullbackand has at least one of surjective. Interchange the two sides if necessary so that is surjective.
We first establish the patching fact used in the proof. For projective and an isomorphism , setFor free modules denote the result by . The block matrix identityexpresses as elementary matrices. Their entries lift through , and their elementary lifts remain invertible. A change of basis on the first side then trivializes this gluing. Thus , proving that is finitely generated projective. Notice that we lifted elementary matrices, not arbitrary invertible matrices.
For general , choose and . The reductions of and are isomorphic: insert the common reduced and reorder the two complements. Patch them by such an isomorphism. The sum with now patches two free modules of equal size, so is projective by the free case, making each summand projective. The same free change of basis followed by these direct-summand projections shows that extension to recovers . Conversely, write an -projective as the image of an idempotent over a finite free module. Since matrices over the pullback are compatible pairs of matrices, applying the compatible idempotents to the free pullback reconstructs this projective from its two reductions. Compatible module isomorphisms patch as well. This proves Milnor patching of projective modules in the form needed below.
The diagonal maps in the sequence are extension of scalars; the two maps to are differences . Define the connecting map byIt is unchanged by stabilization or elementary multiplication: an elementary factor lifts through and changes a free basis in the gluing. The identity and the preceding elementary factorization show after matching sizes. Thus is an additive homomorphism on .
Exactness at . If the two reduced classes agree, choose stabilized representatives of the same size. Their reductions differ by an elementary matrix over . Lift to an elementary matrix over and adjust without changing its class. Its reduction now equals that of . The compatible pair and its compatible inverse give an invertible matrix over , so the original pair of classes is in the diagonal image. The reverse containment follows from commutativity of the square.
Exactness at . A gluing obtained from a change of basis over either upper ring patches a free module, so the difference-map image is killed by . Conversely, means that becomes free after adding a common projective summand. Add a complement of that summand to obtain an actual isomorphism . Its two local bases express . Therefore , which lies in the image of the difference map. This uses stable equality of projective classes, not cancellation of arbitrary projectives.
Exactness at . Connecting classes reduce to zero on both sides. Conversely, write a class in the kernel as by adding a complement to its negative projective term. Its reductions have the same classes as . Equality in becomes an isomorphism after a finite common free summand, by taking a complement to the auxiliary projective. Use one sufficiently large free summand on both sides. The stabilized is then locally free with gluing , so the original class is .
Exactness at . Write a kernel pair as , using complements and padding to make the free sizes equal. Their reduced positive classes agree. Adding a common finite free summand makes those reductions isomorphic. Patch the resulting projectives, and subtract the matching free -module. Its restrictions are the desired pair. The reverse containment is immediate because both reductions to agree.
These arguments prove the Mayer-Vietoris sequence in algebraic K-theoryNo zero is inserted at either end; this fragment does not assert injectivity at the first term or surjectivity at the last.
For the group ring of the cyclic group, take the cyclotomic Milnor squareThe maps send the cyclic generator to and to ; the lower map sets , and the right map reduces modulo . Since , . To verify the pullback, represent an element by a polynomial of degree at most . If both evaluations vanish, it is a constant multiple of the minimal polynomial of an algebraic element , and evaluation at one forces that constant to be zero. Conversely, represent by of degree below . For a compatible integer , is divisible by ; replacing by yields the pair . The right map is surjective, so this is a Milnor square.
The hinted cyclotomic units are . If with , the geometric sum is their inverse, because . Their residues are , covering every unit of the common field. Gaussian elimination identifies with by determinant. Thus is surjective, and the connecting map vanishes.
The remaining exact sequence injects into , with image . Here , and reduction of a projective over the integral domain has dimension its rank: localize at , where the projective is free, and compare its residue-field dimension with its fraction-field dimension. Projection onto the second factor is therefore a bijection on this kernel. Hence extension along the cyclotomic evaluation givesThe essential step is reduction of cyclotomic units at the ramified prime; surjectivity of a ring map alone would not imply surjectivity on .
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 53 2 5 Solution 2026-10-14
Each independent run uses one oracle call and gives a uniformly sampled equation . Collect linearly independent equations and use Gaussian elimination over . Their solution space has dimension one and consists of , so the promised nonzero solution identifies uniquely.
To quantify the expected query count for Simon sampling, write . If the existing equations have rank , their span contains of the possible samples. A fresh equation raises the rank with probability . The mean waiting time is the corresponding geometric distribution mean, givingThe last sum is less than : its first term is and its remaining terms are bounded by . Hence the expected number of quantum queries is . For a fixed high-confidence budget, use samples. Failure to span means that a nonzero linear functional on the -dimensional sampling space annihilates every sample. Each such functional has probability , so the union bound gives failure probability at most . Thus queries suffice for failure probability at most . For , the nonzero string is known already and no samples are needed.
Classically, a collision between distinct queried arguments immediately yields . Random queries produce this collision after order calls, by the birthday problem. Conversely, choose the nonzero period uniformly and label the fibres randomly. Before a collision, queries can exclude at most periods, their pairwise argument differences; every remaining period has the same no-collision transcript distribution. When , those exclusions occupy a vanishing fraction of the candidate periods, and neither collision discovery nor guessing a remaining period has a constant success probability. More quantitatively, conditioned on no previous collision, the next query tests at most of at least remaining periods; summing these conditional probabilities proves the same square-root lower bound. Therefore the optimal bounded-error classical query count is , exponentially larger in than the quantum count.
Past exam of the mathematics course of the University of Cambridge 2006 ib Paper 1 6D b Solution Created 2026-09-24 Updated 2026-10-14
At the first step of Gaussian elimination, the first column of a nonsingular matrix cannot be zero. Choose a nonzero pivot there using a row interchange and eliminate below it. The resulting matrix has block formElementary elimination and row permutations preserve nonsingularity, so and the trailing matrix is nonsingular. Its first column again has a nonzero entry. Repeating this argument inductively provides a nonzero pivot at every step and produces an upper-triangular factor. The recorded elimination multipliers, with previous entries permuted when necessary, form the unit lower-triangular factor. Every nonsingular square matrix admits under columnwise partial pivoting.
For the column-interchange convention from part (a), use the same induction with a nonzero entry in the first row of each nonsingular trailing matrix. Column interchanges put it in the pivot position, and elimination gives . These existence statements are in exact arithmetic; they do not assert that all choices have equally good numerical stability.
Past exam of the mathematics course of the University of Cambridge 2007 ia Paper 1 2B i Solution Created 2026-09-24 Updated 2026-10-14
The coefficient matrix has determinantA square linear system has a unique solution for every right-hand side precisely when its coefficient matrix is an invertible matrix. Here a unique solution exists exactly when , for every real .
For an explicit Gaussian elimination, subtract twice the second equation from the third, then use the second equation, obtaining and . The first equation determinesand the preceding formulas determine . When this last coefficient vanishes; the next parts determine compatibility rather than dividing by zero.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 7 3 iii Solution Created 2026-10-03 Updated 2026-10-14
Write for . For these are transvections, and for they are the identity. Left multiplication by adds times row to row . We show that these elementary transvection matrices generate the special linear group.
Apply Gaussian elimination using only row additions. If a pivot is zero, invertibility ensures some lower entry in its column is nonzero; adding that row produces a nonzero pivot without interchanging or scaling rows. Clear entries below each pivot, and then above pivots in reverse order. This reduces any invertible matrix to a diagonal matrix , with all , preserving determinant throughout. For a determinant-one matrix, .
A two-coordinate diagonal block is itself a product of elementary transvection matrices. On those two coordinates putThis formula is valid in characteristic two as well. For , multiply the diagonal blocks with entries on coordinates for . Their product is , because its last entry is . Thus and the original matrix lie in the subgroup generated by transvections. Conversely every transvection has determinant one by part ii. HenceFor , both the special linear group and the subgroup generated by the degenerate identity transvection are trivial. The argument also establishes transvections generate the special linear group over any field.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 2 4 Solution Created 2026-10-03 Updated 2026-10-14
The special linear group over a finite field consists of the determinant-one invertible matrices over . Counting an ordered basis givesThe determinant map is onto , soA transvection has the form , where , the linear functional is nonzero and . It has determinant one, fixes the hyperplane pointwise, and its displacement has image the line . In particular for is an elementary transvection when .
Row addition is multiplication by such a matrix. Gaussian elimination reduces a determinant-one matrix to diagonal form using row additions and determinant-one pivot exchanges. The latter, and all remaining diagonal factors, are themselves products of transvections: within two coordinates,A diagonal matrix with product of entries one is a product of these two-coordinate diagonal matrices. Thus transvections generate . This generation statement actually holds for every and every finite field; the exclusions in the question are needed for the subsequent simplicity assertion.
Commuting with all elementary matrices forces the group center to consist of scalar matrices with , so its order is . The projective quotient acts faithfully on the one-dimensional subspaces. Its action is two-transitive: send an ordered pair of independent representative vectors to any other pair and adjust the determinant by rescaling a representative without changing its line. Therefore it is primitive.
The Iwasawa simplicity lemma says that in a faithful primitive action, if a point stabilizer has an abelian normal subgroup whose conjugates generate the group, every nontrivial normal subgroup contains the derived subgroup. In particular a nontrivial perfect group satisfying these conditions is simple. No proof of the lemma is required here.
For the point , the subgroupis abelian, is normal in the line stabilizer, and its conjugates contain all transvections. Its image in the projective quotient has the same properties. Perfectness follows explicitly from elementary commutators. If , choose a third index to obtainIf , choose with and set . ThenEvery upper transvection is a commutator, and conjugation gives the lower ones. The group and its projective quotient are perfect. Iwasawa's simplicity lemma now proves
The order of is . Its faithful projective-line action has degree five, so its image is an index-two subgroup of , necessarily . Thus .
For the order is . We construct a faithful degree-five action. In takeThey satisfy and . Their quaternion subgroup projects to a Sylow 2-subgroup . Its projective centralizer is : a lift of a centralizing element conjugates each of to itself or its negative. In the matrix basis , those four sign choices each leave a one-dimensional space, and determinant one leaves just its two quaternion representatives. The matrixhas order three and cyclically permutes the three nonidentity elements of . The normalizer quotient embeds in and has order dividing both and , so it has order exactly three. Hence and there are five Sylow 2-subgroups. Their conjugation action is nontrivial and transitive, and simplicity makes it faithful. Its image again has order in , proving
Finally,In characteristic two an involutory matrix has form with . Its Jordan blocks have size at most two. A projective involution in has a unique involutory lift to : its square is central, and squaring is an automorphism of the scalar center of order three, allowing a unique scalar adjustment. The nonidentity Jordan form in dimension three is only . This GL-class remains a single SL-class, since the centralizer contains of every determinant . Thus has one involution class.
In there are two forms, and , so there are two involution classes. More concretely, the first group's single class has elements, counting image line, kernel plane through it and nonzero map between the quotient and image. The rank-one class in dimension four over has elements; the rank-two class has . Isomorphisms preserve conjugacy classes, so
Past exam of the mathematics course of the University of Cambridge 2016 ia Paper 1 8C a Solution Created 2026-09-24 Updated 2026-10-06
Adding the three equations for gives the necessary solvability condition . Conversely, subtraction of the first two and use of the third forceIf , these values also satisfy the first two equations: for example,The analogous calculation gives . Thus existence and uniqueness hold exactly under the stated compatibility condition:
For the three-variable system the matrix and data vector arePerform Gaussian elimination on the augmented matrix. The operations and giveEach operation is an invertible row scaling followed by a row addition, so the solution set is preserved. Next givesBack substitution now yieldsand thenAll three pivots are nonzero. Thus the solution exists uniquely for every , the matrix rank is , and the kernel of a linear map represented by is . The general rank-nullity theorem for a matrix with columns ishere .
Finally, reverse the viewpoint and regard as prescribed. The necessary and sufficient condition already proved applies with , , . Their sum is . Consequently can be recovered exactly whenWhen this holds, their unique values are and . The allowable triples form an affine plane, not all of .
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 2 1E Solution Created 2026-09-24 Updated 2026-10-03
The dual vector space is , the vector space of all linear functionals on . For a vector subspace , its annihilator of a vector subspace is
Given a basis , define by and extend linearly. If , evaluation at gives , so the are linearly independent. Every satisfiesso they also span and therefore form its dual basis.
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 4 8D Solution Created 2026-09-24 Updated 2026-10-03
For , forward substitution in a triangular system in gives . Consistency of requires . backward substitution in a triangular system then gives
Past exam of the mathematics course of the University of Cambridge 2019 ib Paper 4 8C Solution Created 2026-09-24 Updated 2026-09-29
Gaussian elimination without row exchanges gives the LU decompositionBecause has unit diagonal and is upper triangular,
Past exam of the mathematics course of the University of Cambridge 2020 ib Paper 1 5C a Solution Created 2026-09-24 Updated 2026-09-29
Gaussian elimination gives the LU decompositionThe prescribed diagonal entries of are visible, and direct multiplication gives .
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 1 5B Solution Created 2026-09-24 Updated 2026-09-25
Apply symmetric Gaussian elimination without row exchanges. At step , let be the leading diagonal entry of the remaining symmetric Schur complement. If , stop and report that is not positive definite. If , use it to eliminate the rest of its row and column. If all steps succeed, this constructs an LDL decompositionwhere is unit lower triangular and has positive diagonal.
The test is correct from first principles. If all , then for every nonzero ,because is invertible. Conversely, if is positive definite, its first pivot is , and completing the square givesChoosing shows that the Schur complement is positive definite. Induction forces every pivot to be positive. This is also Sylvester's criterion.
At step , updating the remaining matrix costs arithmetic operations. Hence the total iswhich proves the existence of the required algorithm.
