Prepare , query the oracle, and measure or discard the output register. For , the input register becomes the coset state
Apply , the quantum Fourier transform over . The two amplitudes interfere destructively unless the binary inner product satisfies
and every vector in this orthogonal subspace is sampled uniformly. Repeat until independent equations have been collected, then use Gaussian elimination over to find their one-dimensional null space; its nonzero vector is . This is Simon's algorithm. It uses oracle queries with high probability and polynomial classical work. When , the function is injective and the samples eventually span all of , which distinguishes that case with arbitrarily high probability.
Choose finite generating sets and , using the Hilbert basis theorem. The assumed inclusion says that each vanishes on . By the Strong Hilbert Nullstellensatz, for every there is an exponent such that
The coefficients in an expression solve a finite system of linear equations with rational coefficients. Since it has a complex solution, Gaussian elimination gives a rational solution. Clearing the finitely many denominators produces a nonzero integer such that
for every .
For any prime , reduce these identities modulo . At a common zero of in the algebraic closure , they give , hence , for all . Therefore
for every prime except the finitely many divisors of . This is the spreading out of an affine zero-set inclusion.
Use Gaussian elimination. The last equation gives , and the second then gives . Substitute these into the first equation to obtain . Back-substitution yields
The linear system has matrix form
The coefficients of the arbitrary right-hand side in the solved expressions are the rows of the matrix inverse. Therefore
Multiplying the original matrix by this candidate gives the identity matrix; its determinant is , so the solution is unique for every .
Use Gaussian elimination on the augmented matrix. First take and , then :
By back substitution, the last row gives , the second gives and hence , and the first gives . Thus
The right-hand side has been transformed in every row operation, preserving the solution set.
Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.
For elimination without row exchanges, let . At step , provided the pivot element is nonzero, form the elimination multipliers
and perform , applying the same operation to the right-hand side. More explicitly the resulting entries satisfy for , .
Let , where are the standard basis vectors. Then
The matrix is a unit lower triangular matrix storing the elimination multipliers, while is an upper triangular matrix:
Solving becomes followed by . If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce with a permutation matrix ; then solve , .
At elimination column , let be the size of the remaining trailing block. Computing its multipliers costs divisions; updating all entries costs floating-point operations, one multiplication and one subtraction per entry. Thus the dominant count is
Updating the right side and back substitution add only floating-point operations. Pivot searches involve comparisons and row exchanges, without changing the leading arithmetic count. Hence Gaussian elimination with pivoting has the requested asymptotic cost.
Solving the unrelated shifted systems by separate Gaussian elimination costs floating-point operations.
Instead compute once in work. For each shift, solve
The shift changes only the diagonal, so remains an upper Hessenberg matrix. In each elimination column only the entry immediately below the pivot needs removal. With partial pivoting the only possible nonzero candidate rows are the current row and the next, and each update touches entries. Factorization therefore costs per shift; the triangular solve and both orthogonal-vector transformations also cost each.
Thus shifted solves plus the initial Hessenberg reduction cost in total. Pivoting is still needed in general: nonsingularity excludes a singular system but does not by itself guarantee that every unpivoted elimination pivot is nonzero.
Use Gaussian elimination with partial pivoting, choosing a largest absolute entry in the uneliminated part of each pivot column. The first pivot is two in row one, with multipliers for rows two, three and four. The second-column candidates are then , so row two stays as pivot and the remaining nonzero multiplier is for row four. The augmented matrix at this stage is
The third pivot is three, so swap rows three and four. The final multiplier is , leaving last pivot . Carrying that swap through the previously stored multipliers gives
The transformed right side is . Back substitution gives , , and , hence .
For the eigenvalue claim, put . It is invertible because a permutation matrix and a unit lower triangular matrix are invertible. The factorization gives , so
Similar matrices have the same characteristic polynomial and therefore the same eigenvalues with algebraic multiplicities. This proves the claim without changing the prescribed elimination method.
The first pivot is two. Gaussian elimination without partial pivoting uses and , giving
The second pivot is one; gives the upper triangular matrix
Both pivots used for division are nonzero, so no row exchange is needed.
The elimination multipliers are , , and . The unit lower triangular matrix in the LU factorization is therefore
Direct multiplication checks
The positive signs in undo the row subtractions used during Gaussian elimination.
Use Gaussian elimination with partial pivoting, choosing the largest absolute available entry in the current pivot column. The first pivot is 2, with multipliers . After eliminating that column, the augmented system is
The second pivot is , already largest in its remaining column. Its multipliers are zero and , giving row four . In column three, partial pivoting now requires exchanging rows three and four, since . The final elimination multiplier is . Thus
Back substitution gives .
The permutation and recorded multipliers, with the earlier multiplier rows swapped at the third pivot, are
Direct multiplication verifies . Since is invertible and ,
The two matrices are similar, and similar matrices have the same characteristic polynomial and eigenvalues.
If a square matrix is an invertible matrix, multiplicativity of the determinant gives
so .
Conversely, suppose . Use Gaussian elimination to reduce to row echelon form . Each elementary row operation multiplies the determinant by a nonzero factor, so . If this square matrix had fewer than pivots, its row echelon form would have a zero row and hence zero determinant, a contradiction. Therefore it has a pivot in every row and column, and further elementary row operations reduce it to .
Each elementary row operation is multiplication on the left by an invertible matrix, its inverse being the reverse operation. Thus implies , a product of invertible matrices. Hence
Use Gaussian elimination. Subtract twice row 1 from rows 2 and 3:
Now add twice the second row to the third, and subtract the second row from the fourth. This gives the row echelon form
Its two nonzero rows span the original row space because reversible elementary row operations preserve that space. They are linearly independent, as witnessed by their leading entries in different columns. Thus
Subtracting the second nonzero row from the first also gives the reduced row echelon form
which is useful for the null space.
Perform the elementary row operations and , then :
These operations preserve the row space. The two nonzero rows of this row echelon form are linearly independent: only the first has a nonzero first entry, and the second is nonzero. Hence
Further Gaussian elimination gives the reduced row echelon form
which will also identify the free variables in the null space calculation.
Use Gaussian elimination without row exchanges. First apply and ; then apply :
The elimination multipliers are , and . Put them below the diagonal of a unit lower triangular matrix:
To see why these multipliers reconstruct the rows, row 2 of is three times row 1 of plus row 2 of , giving . Row 3 of is twice row 1 plus row 2 plus row 3 of , giving . This directly verifies the LU factorization.
Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank .
Conversely, if , Gaussian elimination has a pivot in every column and reduces to the identity. Writing the successive row operations as left multiplication gives . Hence , a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.
Gaussian elimination gives
The first two original columns form an image basis:
Their independence follows already from their third and first coordinates. The third column is twice the first plus the second, and the fourth is the first plus twice the second, so they span every output of .
Gaussian elimination gives the row operations , , , producing the lower three rows , , . Subtract the new row two from row three and add three times row two to row four; the remaining nonzero row is . Move it above the zero row and finish elimination to obtain
The pivot columns are one, two and three. Row operations preserve the linear dependence relations among columns, so the corresponding columns of the original matrix form a basis for the column space, which is the image of the linear map:
In particular, the matrix rank is three. Columns of the reduced matrix itself would generally give a different subspace, so the original columns must be used.
Use banded Gaussian elimination followed by back substitution. To distinguish the right-hand side from the upper-diagonal coefficients , write it as . If the modified pivot elements are nonzero, the tridiagonal elimination recurrences are
They eliminate just the one entry below each pivot element. Solve the resulting upper bidiagonal matrix system by
There is a bounded number of arithmetic operations per row in each sweep, giving arithmetic operations and storage. The unpivoted recurrences cost arithmetic operations under the usual scalar-operation count.
For a general tridiagonal matrix, nonsingularity alone does not guarantee these pivot elements. If a zero or unsafe pivot element occurs, use partial pivoting between the current row and the next row. These are the only possible nonzero candidates in the current column; adjacent row swaps introduce at most a second upper diagonal. Tracking that fill-in keeps both Gaussian elimination and back substitution at arithmetic operations. For example, is invertible but requires a row swap. If the input is singular, report a zero final pivot element; a unique solution cannot be promised, and compatibility or free-variable analysis is a separate issue. No nonsingularity or safe-pivot assumption is silently inferred from the word tridiagonal.