For a complex matrix , putThe Gershgorin circle theorem states thatTo prove it, let with , and choose for which . The th coordinate of the eigenvalue equation givesThe triangle inequality, followed by division by , givesThus , proving the assertion for every eigenvalue.
The second theorem, Gershgorin eigenvalue counting, says that if a union of indexed Gershgorin discs is disjoint from the remaining Gershgorin discs, that union contains exactly eigenvalues, counted with algebraic multiplicity. In particular,Discs that touch are not disjoint; overlapping Gershgorin discs cannot individually be assigned one eigenvalue each.
The power iteration starts from , normally scaled to unit Euclidean norm, and repeatsNormalization prevents the rapidly growing or decaying magnitudes of from obscuring its direction. The iteration requires .
Because is a diagonalizable matrix, choose an eigenbasis , with corresponding eigenvalues , and expand . First suppose the dominant eigenvalue is simple and . ThenForthe sum in parentheses after is in Big O notation. Consequently the power iteration direction error is : the iterates approach the line spanned by . For a real matrix, a uniquely dominant eigenvalue is real, since otherwise its complex conjugate would have the same modulus. If , approaches one unit eigenvector; if , successive alternate signs. In either case,This is the sign and phase in power iteration qualification. Also, the necessary assumption is a nonzero coefficient in the eigenbasis, rather than merely a nonzero ordinary inner product with : those tests can differ for a nonsymmetric matrix. If , the method cannot generate the missing component.
If the dominant value has a higher-dimensional eigenspace, the same argument replaces by the nonzero sum of all starting components in that eigenspace. The limiting direction is then that of this sum, which is still an eigenvector for . The usual algorithm assumes ; a strict dominance gap guarantees this whenever another eigenvalue is present.
An estimate retaining the sign of is the Rayleigh quotientContinuity of this quotient at a nonzero eigenvector proves the limit even when is a nonsymmetric matrix. Alternatively, for a coordinate whose limiting eigenvector component is nonzero. The scaling factor alone tends only to .
The four row Gershgorin discs have centres and radii , respectively. Their real-axis intersections areNone of the Gershgorin discs contains zero, so the Gershgorin circle theorem givesThe discs centred at and are each isolated. By Gershgorin eigenvalue counting, they contain exactly one eigenvalue apiece, and both eigenvalues are simple. Each must be real: the characteristic polynomial is real, so a nonreal root would bring a distinct conjugate root into the same disc. Denote these eigenvalues by and . The remaining two eigenvalues lie in the union of the negative-centred discs.
For the shift , the distances satisfyfor either of the other eigenvalues , since its real part is at most . Thus is uniquely closest to . Once is checked not to be an eigenvalue, the natural full target-disc interval enclosure and a conservative asymptotic direction factor areAs always, inverse iteration requires a nonzero initial target component. The following calculation verifies the shift and gives sharper information.
For the tridiagonal matrix, let be the determinant of the leading block of . Expansion along the last row givesIn particular, , and . Both shifted linear systems are nonsingular. Further exact evaluations areThe intermediate value theorem gives a real root in each of , , and . As has polynomial degree four, these are all its roots and each is simple. In particular, is a diagonalizable matrix, and . The closest competitor to at the shift is , so this refinement yieldsFor the shift , the original Gershgorin discs only give and ; those bounds do not decide which is closer. The refined interval enclosures do:for the negative eigenvalues. Therefore the answer for this particular matrix is yes:Both shifts select the same eigenvector line and alternate signs because . The factor bounds concern asymptotic directional convergence, rather than a universal error reduction from the first iterate for a nonsymmetric matrix. The wider interval remains a valid full-disc enclosure for both shifts; records the stronger information obtained from the characteristic polynomial.
Clearing the denominators in the rational interpolation conditions givesThese are linear equations for unknowns. The th row of the coefficient matrix, in the order , isThis rational interpolation linearization is equivalent to the original fraction conditions only if at every interpolation node. If , the cleared equation merely forces , leaving the fraction undefined.
For , the coefficient row becomesThis is the Vandermonde matrix, whose determinant is . Equivalently, a vector in its null space would define a degree-at-most- polynomial vanishing at all distinct interpolation nodes, which is zero by the preceding uniqueness proof. Thus the cleared linear system has exactly one solution.
There is also a constructive description of that solution. Define the monic polynomialThe polynomial is monic of degree and vanishes at every interpolation node. It must therefore equal . By polynomial division, write uniquelyThe quotient is monic of degree , andis the unique coefficient solution. This does not assert that is nonzero at every interpolation node.
For a counterexample with , , choose and the specified data , so . The cleared equations reduce togiving the unique solution , . But at the quotient is . Indeed, any genuine rational interpolant of this prescribed form would need ; then forces the constant numerator to be zero. At a nonzero denominator its value at would also be zero, never one. Cancelling the common factor in the cleared candidate would merely give the identically zero rational function, which still fails the data. Hence
Applying the implicit midpoint rule to the simple harmonic oscillator system givesFactor the change in the quadratic form and substitute these equations:Thus every step preserves the first integralFor completeness, the implicit equations are solvable for every real : putting , their coefficient matrix has determinant and the update isThis is an orthogonal matrix, as follows from . It therefore preserves the Euclidean norm, explaining geometrically the exact energy conservation. This is a concrete instance of Runge-Kutta conservation of quadratic invariants. Preservation of the circle does not assert that the numerical and exact solutions have the same phase at a fixed nonzero step size.
Past exam of the numerical linear algebra course of the University of Oxford 2011 2 d Solution 2026-10-31
Apply the matrix norm induced by an energy norm and set . Multiplication givesThe bracket factors as . Because and ,Thus for the stated matrix. In particular is a positive semidefinite matrix. The Euclidean operator norm squared is the largest eigenvalue of , and all those eigenvalues are nonnegative. ConsequentlyThis identity is the algebraic step in the energy-norm proof of convergence of SOR; spectral radius equals the largest eigenvalue here because .
Past exam of the numerical linear algebra course of the University of Oxford 2025 1 b ii Solution 2026-10-25
Let . Interpret the diagonal of as nonnegative computed singular values and sort them consistently. If signed diagonal entries are used instead, take their absolute values and absorb signs into the orthonormal columns. Because the two outer factors have the stated orthonormality, these sorted numbers are exactly .
For completeness, the singular value perturbation bound follows from the Eckart-Young-Mirsky theorem. If is the truncated singular value decomposition of a matrix , the triangle inequality givesExchange and to get . Applying this to and the given backward error provesThus backward stability of the singular value decomposition gives an absolute forward error bound for every singular value, even a very small one.
Past exam of the numerical linear algebra course of the University of Oxford 2025 1 b iv Solution 2026-10-25
No uniform absolute error bound of order follows. Take the Jordan blockHere and . The exact eigenvalues of are both zero, whereasThese are admissible outputs under a backward error guarantee of size , yet their forward errors are . This is the square-root splitting of a defective double eigenvalue. More generally, eigenvalue sensitivity depends on the matrix; backward stability alone does not control it. The singular value perturbation bound used in part (ii) has no equally uniform counterpart for the eigenvalues of arbitrary nonsymmetric matrices.
Past exam of the numerical linear algebra course of the University of Oxford 2025 2 a i Solution 2026-10-25
By the Eckart-Young-Mirsky theorem, truncate the singular value decomposition:The same minimizes the spectral norm and Frobenius norm errors over matrices of matrix rank at most . This conventional meaning of rank- low-rank approximation includes the case , when .
Past exam of the numerical linear algebra course of the University of Oxford 2025 2 b iv Solution 2026-10-25
Because , choose a unit vector in the null space of , so that . Let have orthonormal columns, for example the first columns of , and choose a real number . SetIts singular value along is , and its other singular values are . Thus . Meanwhile . If has full column rank, the column space of the thin QR decomposition is exactly , which is orthogonal to . Hence for , andConversely, an orthogonal projection is a contraction in the Euclidean norm, so . ThereforeIf is rank deficient, complete the QR decomposition within : this space has dimension and contains all columns of , so the required orthonormal completion exists there. The same proof applies. For rank-deficient data the choice of unused columns of matters; the construction specifies a valid choice. If instead contains only a basis of , the conclusion holds without any completion. A fixed sampling matrix can thus miss the unique largest singular value completely.
Past exam of the numerical linear algebra course of the University of Oxford 2025 2 b v Solution 2026-10-25
Write ; the requested expression requires the positive even integer . Split the thin singular value decomposition after columns:Here . Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to , and an orthogonal matrix preserves both and volume. Thus , where , again has independent and identically distributed standard normal entries. In particular both displayed blocks have the Gaussian distributions needed below.
First prove a deterministic error bound for a randomized range finder. Put and suppose has full row rank. Its Moore-Penrose pseudoinverse is , so . The QR decomposition implies , henceMultiplication by expresses the missed leading columns in terms of the trailing columns. Substitution into gives the exact identityFor any matrix , the spectral norm of is , because its product with its transpose is . Using submultiplicativity of the operator norm, the orthonormality of , and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient ; if , its right-hand side vanishes.
Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix of size , rather than to its wide transpose. It givesThe upper estimate for , transposing if necessary, givesThus, with ,Since , the deterministic estimate yieldsThis proves the requested conclusion under the explicitly authorized estimates.
The probabilistic qualification is necessary. A Gaussian random matrix does not always have all its singular values between the two endpoints printed in the hint. Already a example would require for every standard normal random variable , which fails with positive probability. The proof above holds on the event where the two block estimates hold. In a probabilistic formulation one supplies estimates for that event, usually allowing a positive margin in both endpoints; no failure probability is specified by the paper.
Nor can the requested inequality with one universal hold almost surely for every . For example, take , , with , and a sampling matrixAt , the sampled column space misses the first coordinate, so , whereas . Choose . Because has full column rank, its orthogonal projection depends continuously on near through . The strict violation persists in an open neighborhood of . The joint Gaussian probability density function is positive there, so that neighborhood has positive probability. This identifies the missing qualification without weakening the conditional calculation.
Past exam of the numerical linear algebra course of the University of Oxford 2025 3 a iii Solution 2026-10-25
The claim is true, withIt is a symmetric positive-definite matrix: for every nonzero vector , the fact that is an invertible matrix gives . Since , every candidate satisfiesThe generalized minimal residual method therefore minimizes precisely this weighted norm of the error over the linear span of . The same matrix works for every and does not depend on .
Past exam of the numerical linear algebra course of the University of Oxford 2025 3 a ii Solution 2026-10-25
For the small QR decomposition, each of the Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column , apply the rotation to two rows in columns , costing arithmetic operations. Summing gives , and applying the rotations to the right-hand side costs . Backward substitution in a triangular system costs .
Computing costs and the final dense matrix multiplication costs . Thus the total, with the Arnoldi decomposition already supplied, isHere , since has orthonormal columns in . In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp cost. The pair above records that two-parameter bound; looser bounds such as are also possible because . Treating as an unstructured dense matrix would unnecessarily replace its factorization by an computation.
Use the fine matrix and right-hand side from part (b), with diagonal . Starting from an iterate , take weighted Jacobi smoothing stepsForm the residual . For coarse interior indices , use full-weighting restrictionThe prolongation operator matrix is linear interpolation of a coarse correction: and , with zero endpoint corrections. Thus . Choose the Galerkin coarse-grid operator , solve exactly, and correct . The entries of , and above specify every matrix in the cycle. A rediscretized coarse operator is another standard choice if used consistently.
For a nonsingular coarse operator, the fine-grid iteration matrix of this pre-smoothed two-grid cycle isThe purpose of under-relaxation is to damp fine-grid oscillations, leaving smoother error for coarse-grid correction. For the diffusion-dominated one-dimensional operator, is the usual effective choice; the high-frequency symbol then has modulus at most for . Coefficients and convection can change the best parameter, so this is a motivated choice rather than a universal optimum. Under the diagonal-dominance condition, the unweighted Jacobi matrix already has norm less than one in the maximum norm, and its convex combination with the identity remains convergent for .
The endpoint in the printed nonnegative-parameter hypothesis must be excluded. We first establish the intended result for , then describe that endpoint exactly.
Write for the two directional matrices; they commute because they act on separate tensor-product coordinates. At a limit , the intermediate vector also has a limit . Subtract the two limiting equations in the form that cancels and ; this gives . Hence for . Substitution then gives , precisely the required discrete equation.
Eliminating the intermediate vector gives the alternating direction implicit iteration matrixThe sine-product basis simultaneously diagonalizes , with eigenvalues and , whereThusFor , each factor has modulus strictly less than one. Hence , proving convergence from every starting vector to the unique discrete solution.
At the two factors are both , so . The forcing terms cancel in the composed iteration as well, and for every starting vector. An incorrect initial vector therefore remains incorrect forever, even though the sequence is constant and has a limit. This disproves both the literal fixed-point implication and the claimed general convergence-to-solution assertion at zero; strict positivity of is the necessary repair.
Let , and . Subtract the exact fixed-point equation to obtain . Hence convergence for every initial vector is equivalent to . If this holds, it holds after complexification; applying it to a complex eigenvector gives , so . Conversely, the complex Jordan normal form expresses each power as a finite sum of terms from its blocks. Every term tends to zero when all eigenvalues have modulus below one. ThusThe convergence criterion for a stationary iteration needs complex triangularization or Jordan normal form. The paper's assertion that every real matrix is similar to a real upper-triangular matrix is false when nonreal eigenvalues occur; complex triangularization supplies the intended argument. In the Gauss-Seidel method, with split into diagonal, strictly lower and strictly upper parts, .
For , eliminating the ghost values gives the symmetric pentadiagonal matrixAll other off-diagonal entries vanish. The first two equations areand the last two areFor the matrix is , for it is , and for it is because both ghost contributions meet the same unknown. The diagonal entries are positive in every case, so the lower triangular matrix is invertible and the Gauss-Seidel iteration is well defined.
An eigenvalue of makes singular. Let and be the sums of absolute lower and upper entries in row . The row's diagonal-dominance margin isInterior full rows have , , giving margin . Boundary rows have larger margins; for instance the first gives , and the second gives at least . Therefore would make a strictly diagonally dominant matrix, hence nonsingular, a contradiction.
At it is weakly diagonally dominant with strict boundary rows. Its nonzero nearest-neighbour entries make it an irreducibly diagonally dominant matrix. The nonsingularity theorem for that class again contradicts singularity. For the small matrices above all rows are already strict at this value. HenceThere is also a stronger conclusion. For ,including the overlap. Since is positive definite, is a symmetric positive-definite matrix. The Gauss-Seidel convergence from diagonal dominance and positive definiteness theorem consequently gives the stronger bound .
Let be the transmission direction. An ideal linear polarizer projects the incident electric field onto this direction, so its Jones matrix isSince , the amplitude transmitted by a sequence of polarizers is the product of the projections between successive axes. Here the four directions are . After the first polarizer the unpolarized light input has intensity and is in linear polarization along . The transmission through a sequence of linear polarizers therefore follows from successive applications of Malus's lawThe relative angle between the rotating polarizers is , not . The first factor is an ensemble average over incident polarization: unpolarized light cannot be represented by a single deterministic Jones vector. Equivalently, its coherency matrix is ; the total matrix gives the same output intensity by the trace rule. The quasistatic optical-element approximation assumes the mechanical rotation is slow compared with the optical oscillation.
Past exam of the optimisation for data science course of the University of Oxford 2023 2 b Solution 2026-10-25
For the linear least-squares problem objective function, direct expansion with givesIts gradient is , so the middle term equals .
Use the supplied thin singular value decomposition . Since , the linear map preserves the Euclidean norm. The square matrix is an orthogonal matrix, so . ConsequentlySubstitution into the expansion provesThus is a strongly convex function with modulus . This modulus is sharp: choose for an index attaining the smallest singular value. The Hessian matrix is , so the same conclusion says that its smallest eigenvalue is .
Expand at a matrix increment :The last term is in a matrix norm, so it contributes no derivative. HenceThis is a linear operator on matrix increments, not a scalar entrywise derivative.
The requested base point is the identity matrix , not the zero matrix. Since commutes with every ,The matrix power series justifies the quadratic remainder near zero. ConsequentlyAt zero the derivative would instead be ; replacing the printed base point would lose the scalar factor.