Past exam of the numerical linear algebra course of the University of Oxford 2011 1 d Solution 2026-10-31
For the matrix's Euclidean operator norm, orthogonal invariance of the Euclidean norm givesTaking gives equality, so . For the Frobenius norm, the trace identity and the singular value decomposition giveConsequentlyHere the Euclidean matrix norm means the operator norm induced by the vector Euclidean norm, rather than the entrywise Euclidean length, which is the Frobenius norm.
Past exam of the numerical linear algebra course of the University of Oxford 2011 1 e Solution 2026-10-31
The two columns are orthogonal, with lengths one and two; equivalently . Ordering the singular values decreasingly requires swapping the right coordinate directions. One full singular value decomposition isBoth and are orthogonal matrices, and direct matrix multiplication gives . Hence
Past exam of the numerical linear algebra course of the University of Oxford 2025 1 b iii Solution 2026-10-25
An error of order in a squared singular value can become an error of order after taking its square root. To keep nonsingular as required, take andThen , and the computed eigendecomposition has exactly the permitted backward error:Nevertheless the second computed singular value has errorBy the singular value perturbation bound, every product with these computed singular values and exactly orthonormal outer factors has spectral norm error at least this large. In particular, even the favorable choice giveswhich has no uniform bound in big O notation. Therefore backward stability for the eigendecomposition of the Gram matrix does not imply backward stability for the singular value decomposition.
There is a related loss of orthonormality in the raw formula: evaluating exactly for these perturbed factors gives , whose second column has length tending to zero. Its product with equals , but its diagonal factors are consequently not a singular value decomposition. The paper's idealized orthonormality assumption lets us isolate the unavoidable singular value error even if this additional problem is repaired.
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 i Solution 2026-10-25
Choose the nonnegative square roots of the eigenvalues of for the diagonal entries of , in nonincreasing order. Its assumed matrix inverse exists, so these entries are positive. The eigendecomposition givesHence has orthonormal columns. AlsoTogether with the orthogonal matrix and the nonnegative diagonal matrix , these are precisely the properties of a thin singular value decomposition.
Past exam of the numerical linear algebra course of the University of Oxford 2025 2 a ii Solution 2026-10-25
Choose the first left singular vectors:Their orthonormality gives . The orthogonal projection fixes for and annihilates for . Applying it to the singular value decomposition therefore gives
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 i Solution 2026-10-25
Put . Since has columns, the rank bound for a matrix product gives . The Eckart-Young-Mirsky theorem and part (a) then giveOne can also see the lower bound directly. The restriction of to the -dimensional linear span of has a nonzero null space, because its matrix rank is at most . For a unit vector in that null space, by the singular value decomposition.
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 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 .
If one retains the Euler approximation , its exact norm matrix isThe additional term can mix the instantaneous symmetric-part eigenvectors, so they no longer generally diagonalize finite-time error amplification. However, when is material, a reliable physical propagator must itself be calculated beyond first-order Euler: a large Euler-step amplification can be a numerical artifact. For constant , the exact map is ; for a changing reference trajectory it solves , .
Use its singular value decomposition, . The initial orthonormal right singular vectors diagonalize and satisfyA singular value gives finite-time norm growth, decay, and the leading right singular vector is the initial perturbation with greatest amplification in the stated norm. The left singular vector describes the resulting final error pattern. Non-normal dynamics can give transient growth even if every Jacobian matrix eigenvalue has negative real part, so selecting observations from those eigenvalues alone is insufficient. Over a genuinely short interval, , recovering the symmetric-part result. Initial observations should target the relevant growing right singular projections, with prior covariance and observational precision included when they are not isotropic.
For seismic source inversion, collect calibrated, consistently filtered samples from all available stations and components into a data vector . For each trial source position and origin time, compute the corresponding elastodynamic Green tensor in an Earth model, including the instrument response used for the data. Write the symmetric seismic moment tensor in six independent symmetric basis tensors:Each column of is the synthetic seismogram for one basis tensor. An off-diagonal basis tensor contains both symmetric entries, so the double contraction and its factors of two remain consistent.
A suitable objective iswith noise covariance ; a justified penalty can be added for regularization. At fixed , solve for the six entries of by weighted least squares, preferably using a QR decomposition or singular value decomposition rather than explicitly inverting the matrix of the normal equations. Then search over the four nonlinear parameters using a coarse location/time grid followed by local refinement. This variable projection reduces a ten-parameter search to a four-parameter nonlinear search with an inner six-parameter linear fit. Merely having more than ten data samples does not ensure identifiability: the design matrix must have adequate rank and the network must resolve the source's radiation patterns.
Potential errors include inaccurate velocity, density, anisotropy and attenuation in the assumed Earth model; neglected finite rupture and source-time effects; timing, instrument calibration or component-orientation errors; correlated noise; uneven station coverage; and tradeoffs between depth, origin time and the moment tensor. Imposing a double-couple seismic source mechanism without evidence can hide genuine non-double-couple components. Regularization also changes the recovered source and should be reported.
Inspect residuals, singular values, recovery of synthetic sources and uncertainty under resampling or noise perturbations. Linearized covariance or a posterior distribution can quantify uncertainty within the assumed forward model, but does not automatically account for errors in that model. A good waveform fit alone is insufficient evidence that all ten parameters are uniquely recovered.
Past exam of the quantum information course of the University of Cambridge 2016 Paper 1 2 Solution 2026-10-20
Use the thin singular value decomposition , with , unitary and nonnegative. Expanding its entries givesThe columns of and of are orthonormal, establishing the Schmidt decomposition. Bob's basis uses the complex-conjugated columns of . Omitting that conjugation would not reproduce the coefficient matrix. The squared Schmidt coefficients are the eigenvalues of ; equivalently and . The two reduced density matrices are and , which have the same nonzero eigenvalues.
The printed coefficient slightly rounds a normalized state: each squared norm is . Normalize before calculating an entropy. For the two states, the resulting Gram matrices are approximatelyFor a trace-one two-dimensional Hermitian matrix with diagonal entry and off-diagonal entry , its eigenvalues areSort them decreasingly and take square roots:The Von Neumann entropy is . is more entangled: its Schmidt weights are closer to equal and its reduced-state entropy is larger. Neither state is a product state or maximally entangled on its two-dimensional support.
By Nielsen's pure-state conversion theorem, deterministic LOCC conversion requires the input vector of squared Schmidt coefficients to be majorized by the output vector. Here and both sums are one, so . Therefore is possible deterministically; is not. Entanglement can be discarded by local operations but cannot increase deterministically for these pure inputs. Probabilistic concentration is a separate question and is allowed below.[ref]
Conditions for a class of entanglement transformations by Michael A. Nielsen. 1999 primary theorem: deterministic pure-state conversion and majorization
There is a dimensional qualification in the proposed measurement. Write . The two supplied measurement operators obeyThus their effects form a POVM on the occupied support, where is the identity. Alice's full space is three-dimensional, so these two operators alone do not sum to . A full-space completion is . It has zero probability on either input, so it changes none of the requested outcomes. Strictly, the POVM consists of the effects ; the specified additionally fix a quantum instrument and therefore the conditional states.
In the appropriate Schmidt basis for either input, write . The two outcomes have probabilitiesand normalized conditional statesThese formulas give both outcomes for each state by substituting its row of the table. For example,The two inputs have different Schmidt bases; the primed measurement basis is adapted separately to the state, as the question specifies, not one common unexamined laboratory basis.
For the outcome to be a maximally entangled state, its two amplitudes must be equal. HenceThe requested numerical results areThus has the larger success probability, consistent with its greater initial entanglement. The branch cannot be balanced in the allowed angle range for either nonmaximal input: it would require .
Success probability and conditional entanglement for the specified Schmidt-basis filter
. Original calculation with normalized printed coefficients. Each marked angle makes outcome 1 maximally entangled. Curves refer to the specified two-outcome instrument, not the optimal unrestricted concentration protocol. Details.The success probabilities belong to this particular binary Schmidt filter. They are not the optimum over every possible quantum instrument. The diagonal success operator instead gives the standard single-copy entanglement concentration probability . Postselection can increase entanglement in the retained branch, while the outcome-averaged entanglement cannot increase under LOCC.
A density operator is a positive self-adjoint trace-class operator with trace one. In finite dimensions this is a positive semidefinite Hermitian matrix with . Its expectation of an observable is whenever the expectation is defined.
In the source's square-root notation, take the unique positive square root . It has Hilbert-Schmidt norm one and satisfies , soThe standard vector purification is the associated vector on a system and a chosen copy. Tracing out the copy gives ; measuring gives the same trace formula. Thus the operator square root and the purified vector are two related objects, distinguished by this vectorization.
For a general coefficient matrix , expansion of the expectation givesThus . Positivity is immediate from , and its trace is one by normalization of .
If is nonsingular, it is square and is positive definite. DefineThen , which for a square matrix also implies . Thus is unitary, , and .
In an eigenbasis of , its square root is . Hence . DefineUnitarity gives , and substitution gives the Schmidt decompositionFor singular or rectangular , the same conclusion follows on its support by a singular value decomposition; the stated nonsingular case needs only the unitary calculation above.
For the supplied Bell state, the requested matrices areThe Schmidt vectors can be chosen as , , and the two coefficients are . The square root's canonical vector purification is ; the original Bell vector is a different purification of the same reduced state, related by a unitary on the second factor. This illustrates the unitary freedom of purification.
A density operator is a positive self-adjoint trace-class operator with trace one. In finite dimensions this is a positive semidefinite Hermitian matrix with . Its expectation of an observable is whenever the expectation is defined.
In the source's square-root notation, take the unique positive square root . It has Hilbert-Schmidt norm one and satisfies , soThe standard vector purification is the associated vector on a system and a chosen copy. Tracing out the copy gives ; measuring gives the same trace formula. Thus the operator square root and the purified vector are two related objects, distinguished by this vectorization.
For a general coefficient matrix , expansion of the expectation givesThus . Positivity is immediate from , and its trace is one by normalization of .
If is nonsingular, it is square and is positive definite. DefineThen , which for a square matrix also implies . Thus is unitary, , and .
In an eigenbasis of , its square root is . Hence . DefineUnitarity gives , and substitution gives the Schmidt decompositionFor singular or rectangular , the same conclusion follows on its support by a singular value decomposition; the stated nonsingular case needs only the unitary calculation above.
For the supplied Bell state, the requested matrices areThe Schmidt vectors can be chosen as , , and the two coefficients are . The square root's canonical vector purification is ; the original Bell vector is a different purification of the same reduced state, related by a unitary on the second factor. This illustrates the unitary freedom of purification.
For a hyperelastic material . Material frame indifference of this first Piola-Kirchhoff law meansThe spatial force components rotate under a superposed rigid rotation, whereas the reference normal does not.
If , differentiate with respect to in direction to obtain , hence the displayed stress transformation. Conversely, assume that stress transformation. For fixed , the derivative of with respect to vanishes. The positive-determinant matrix domain is connected, as follows from polar decomposition and the connectedness of and of the positive-definite cone. Thus , independent of . Iterating givesThe assumed lower bound on forces : either nonzero sign would tend to minus infinity for one direction of integer . This proves the required equivalence and explains the use of the lower-bound hypothesis.
In the frame-indifferent setting, isotropy means invariance under reference rotations as well: for . The distinction matters: left rotations encode changes of observer, and right rotations encode material symmetry.
An orientation-preserving singular value decomposition is , with and . Material frame indifference and isotropy remove , leaving a function of the stretches. Permuting the stretches using signed permutation rotations does not change the value, so is symmetric. Conversely a symmetric stretch function is unchanged by both left and right rotations, in particular is isotropic.
The eigenvalues of are . Its three principal invariants areThey determine the unordered positive eigenvalues as the roots of . Therefore a symmetric stretch function defines a well-defined on the admissible invariant triples. Conversely a function of these invariants is a symmetric stretch function, proving the equivalence of all three descriptions.
The printed domain of must be , since it takes three arguments. Also isotropy alone as right invariance would not imply the spectral representation without material frame indifference: for a fixed nonscalar symmetric positive-definite is right invariant but not generally objective. The equivalence here uses the frame-indifferent constitutive setting.
For the specific energy, Newton identities for the three eigenvalues gives , while . ThusTo differentiate it, useThese follow from , the displayed trace formula for , and . The three partial derivatives of are , and . The chain rule therefore givesFinally , and . This is precisely the requested expression, with the coefficient of separated from the and cofactor terms. The positive sign of the term comes from the contribution in the energy.
The material symmetry group consists of invertible admissible reference transformations for which for every admissible . Its rotational part lies in ; a determinant-one reference convention restricts the full group to the corresponding special linear group. This right action is distinct from the spatial left action of material frame indifference.
The proper cube-rotation group has elements. Choose the image of one outward face normal in six ways, then the image of an adjacent perpendicular normal in four ways; orientation fixes the third direction. No reflections are included. For an isotropic material every proper rotation belongs to the material symmetry group.
Combine material isotropy with the physical frame-indifference condition. The singular value decomposition may be written with because . Left and right rotational invariance remove . Signed permutation rotations permit any permutation of the three diagonal stretches, soRight invariance alone, without the usual material frame indifference assumption, would not suffice to remove spatial orientation.
The strict Baker-Ericksen inequalities say that larger distinct principal stretches carry larger principal Cauchy stresses:A natural state of a hyperelastic material has zero stress. If two stretches differed, their equal zero stresses would contradict the strict inequality. Thus all three equal some , and polar decomposition gives , . A weak non-strict inequality alone would not prove this conclusion, so its strict convention is explicit here.
For the radial deformation put , , . Since ,This symmetric tensor has radial eigenvalue and the repeated tangential eigenvalue . Both are positive in the open annulus under the stated monotonicity/nonnegativity conditions. Therefore these are its principal stretches. The two cases below establish radial zero-energy rigidity by different arguments.
Take a singular value decomposition , with positive and . Such a choice is possible because . Left material frame indifference removes , and right material isotropy removes , giving .
Moreover is unchanged when the positive diagonal entries are permuted. Every permutation can be implemented by a signed permutation matrix of determinant one; the signs disappear in conjugating a diagonal matrix. Thus the energy depends only on the unordered principal stretches.
The three invariants determine precisely this unordered triple: the roots of are , and their positive square roots give the stretches. Consequently, on the set of admissible invariant triples, define to be . The preceding argument proves that this is well defined and thatNot every positive triple is realizable by three positive roots. Since the requested statement only asserts existence of a function on , extend arbitrarily on the nonrealizable triples; no choice there affects the formula for a deformation in continuum mechanics. Smooth invariant representations, where needed for differentiating the constitutive equation, are understood locally on the realizable set.
Principal component regression Created 2026-10-14 Updated 2026-10-25
Regress a response on selected principal component scores of centered predictors. If is a singular value decomposition and the first positive-singular-value components are retained, the retained score matrix is and the fitted coefficient in predictor coordinates is . The fitted centered response is : this follows by applying the least-squares normal equations to the orthogonal score columns. Truncating small singular directions limits variance amplification, but directions of large predictor variance need not be those best predicting the response; select using prediction assessment rather than explained predictor variance alone.
Ridge regression Created 2026-09-24 Updated 2026-10-14
Ridge regression fits a linear regression model while penalizing the size of its slope regression coefficients. For a fixed design matrix containing the slope predictors, observed responses , and an unpenalized regression intercept , the objective isHere is the all-ones vector, and is the squared Euclidean norm of the slopes alone. The first term is the residual sum of squares; the second implements regularization. No random-error assumption is needed to define this fit. The convention is a summed squared-error loss: writing the objective as gives the same fit when .[ref]
Modern regression 1: Ridge regression. slides 5 and 7: summed squared-error objective and unpenalized intercept
For an exact example, reuse the constructed pairs from linear regression. Their sample means are and , and the centered cross-products are and . ThusThe ordinary least squares line has slope and residual sum of squares . At , ridge regression has slope , regression intercept , and residual sum of squares ; at these become , , and . Every line passes through : the penalty reduces the slope while retaining the response sample mean.
The computational benefit is visible after predictor centering. Write for the design matrix with each column's sample mean subtracted, and . The unpenalized intercept in ridge regression gives , and the closed-form ridge regression estimator solvesFor any nonzero vector and , . This positive-definite matrix is therefore invertible even when lacks full column rank, including repeated columns or . The unique penalized slopes resolve the ambiguity of rank-deficient ordinary least squares; they do not supply evidence about slope directions absent from the data. This makes ridge regression useful for multicollinearity.[ref]
High-Dimensional Regression: Ridge. p. 1, equations (1)–(2): uniqueness for positive penalty regardless of design rank
Predictor centering and scaling serve different purposes. Centering handles the free regression intercept. Scaling determines what counts as a large slope: replacing by changes its coefficient to for the same predictions, changing its contribution to an unweighted penalty. A common convention forms standard scores using each nonconstant predictor's sample standard deviation , then penalizes slopes in those coordinates. Since , this is the weighted penalty in the original units. Constant columns have and must be removed before this scaling. Scaling is a modelling choice; equal penalties in original units and in standardized units define different fits.[ref]
Modern regression 1: Ridge regression. slide 7: center predictors, leave the intercept free and scale predictors to sample variance one
The singular value decomposition explains the shrinkage. If is the compact decomposition using the positive singular values , with columns of , thenThe principal-component shrinkage by ridge regression factors are between and : directions with small singular values are damped most. As , the fitted values approach ; the vanishing-penalty ridge limit recovers the ordinary least squares fitted vector as , even if the slope estimates at zero penalty are nonunique. The covariance and bias of a ridge regression estimator describes the resulting bias-variance tradeoff. A penalty can reduce variance of an estimator while introducing bias of an estimator; the unbounded directional risk of fixed ridge shrinkage rules out a uniform improvement for a fixed positive penalty over all possible signals.[ref]
For a second exact construction, choose a centered orthonormal set of three vectors,and set and . The squared singular values are and . At , the fitted coordinates along are , retaining and of their ordinary least squares values . At they become , retaining and . The unfittable component contributes to every residual sum of squares, giving total values , , and at penalties . These are constructed fits, not measured prediction results.
Exact synthetic ridge shrinkage retains the strong singular direction longer than the weak one
. Details. The penalty is a hyperparameter, so fitting slopes at a fixed value and selecting that value are separate tasks. Use a validation set or K-fold cross-validation to compare candidate penalties by held-out squared-error loss. In each split, compute predictor sample means and scales from that split's training data, apply the same transformation to its validation set, and refit the slopes; using held-out information in preprocessing introduces data leakage. Minimum training residual sum of squares cannot select useful shrinkage: ordinary least squares already attains the smallest possible value.[ref]
Model selection and validation 1: Cross-validation. slides 5–8 and 11–14: tuning for prediction, training error and refitting on each training fold
After model selection, refit on all training data with the selected penalty. A separate test set or nested cross-validation assesses the entire selection procedure; a low selected validation score alone is no performance guarantee.[ref]On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation by Gavin C. Cawley and others. pp. 2079–2080: selection as part of fitting and nested assessment


