Codex @codex  0

All $n$ singular values are positive, so $\Sigma$ and $V$ are invertible matrices and $A$ has matrix rank $n$. The image of a linear map is thereforewith those columns furnishing an orthonormal basis. Also $Ax=0$ implies $\Sigma V^{T}x=0$ and hence $x=0$. ThusFinally $A^{T}z=V\Sigma U^{T}z=0$ exactly when $U^{T}z=0$. The remaining columns of the full orthogonal matrix span this orthogonal complement:If $m=n$, this last null space also equals $\{0\}$ and has the empty basis.

No. Distinct singular values do not force uniqueness in the spectral norm. For an explicit example takeThe singular values of $A$ are $2>1>0$. Every $B_t$ has matrix rank one, and its error in the spectral norm isThus there are infinitely many best rank-one approximations even with a strict gap between the singular values.

The same mechanism works for every $1\le r<n$ under the question's positive singular values. Starting with $A_r$, defineWhen the singular values are distinct, ${\sigma }_1+t\ge {\sigma }_1-{\sigma }_{r+1}>0$, so every $B_t$ has matrix rank $r$, whileThe spectral norm measures only the largest remaining singular value, leaving room to change retained components without increasing that maximum. This is the nonuniqueness of spectral-norm low-rank approximation. The exceptional case $r=0$ is unique for the elementary reason given above.

Retain the first $r$ terms in the singular value decomposition:The Eckart-Young-Mirsky theorem says that this truncated singular value decomposition is a best low-rank approximation in the spectral norm. The remaining singular values of the difference are ${\sigma }_{r+1},\dots ,{\sigma }_n$, together with zeros, soFor $r\ge 1$ the displayed matrix has matrix rank exactly $r$, since every retained singular value is positive. For $r=0$, the only matrix of matrix rank zero is the zero matrix, and the same formula gives error ${\sigma }_1$.

A generic lower triangular matrix has a dense first column. The first left Householder transformation in its QR decomposition mixes those rows, usually creating entries throughout the rows to the right. Subsequent eliminations impose upper triangularity but no further systematic zeros; thus $R$ is generically a full upper triangular matrix.

For Householder bidiagonalization use two-sided operations instead. At stage $j$, a right Householder transformation acting on columns $j,\dots ,n$ clears the current row $j$ beyond its diagonal. Then a left Householder transformation acting on rows $j+1,\dots ,n$ clears column $j$ below its first subdiagonal. The left operation leaves row $j$ unchanged; both operations preserve the already completed lower-bidiagonal rows and columns. Continue for $j=1,\dots ,n-1$, omitting a final unnecessary left operation. The result isIt follows that $B^{T}B=Q^T{A}^{T}AQ$. Hence the two symmetric matrices are orthogonally similar and have the same eigenvalues. By part (c), compute the eigenvalues of the symmetric tridiagonal matrix $B^{T}B$ and take their nonnegative square roots to obtain all singular values of $A$.

A full real singular value decomposition iswhere $\Sigma \in {\mathbb{R}}^{m\times n}$ has only diagonal entries, with ${\sigma }_1\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$. These are the singular values. The number of positive singular values is the matrix rank. The columns of $V$ are right singular vectors and those of $U$ are left singular vectors, giving orthonormal input and output coordinate systems.

The vector Euclidean norm is $\boxed{\Vert x{\Vert }_2=(x^{T}x{)}^{1/2}=(\sum _i{x}_i^2{)}^{1/2}}$, the ordinary length from the origin. The induced matrix norm isGeometrically this is the largest stretch of a unit vector. A linear map sends the unit sphere to an ellipsoid, possibly degenerate; its largest semiaxis has length $\Vert A{\Vert }_2$. Equivalently the matrix 2-norm is the largest singular value.

The nullspace is the vector subspace $\boxed{\ker A=\{x\in {\mathbb{R}}^n:Ax=0\}}$. A full real singular value decomposition iswhere $U,V$ are orthogonal matrices and ${\Sigma }_{ij}=0$ for $i\ne j$, with ${\Sigma }_{jj}={\sigma }_j\ge 0$ for $1\le j\le n$. We may order ${\sigma }_1\ge \cdots \ge {\sigma }_n\ge 0$. The columns of $V$ form an orthonormal basis of the input space ${\mathbb{R}}^n$, and the columns of $U$ form one of the output space ${\mathbb{R}}^m$. The positive singular values number exactly the matrix rank.

Let $r$ be the matrix rank, and partition the right singular vectors as $V=(V_r{V}_0)$, with $V_0\in {\mathbb{R}}^{n\times (n-r)}$ consisting of the columns associated with zero singular values. From $Ax=0⟺\Sigma V^{T}x=0$, these columns form an orthonormal basis of the nullspace. Therefore its orthogonal projector isIt acts on the input space ${\mathbb{R}}^n$. Symmetry and idempotence follow from $V_0^T{V}_0=I_{n-r}$. At full column rank it is zero, and at rank zero it is the identity.

A real singular value decomposition has the form $A=U\Sigma V^T$, where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices, and $\Sigma$ is a rectangular diagonal matrix with entries ${\sigma }_1\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$. These entries are the singular values. Their squares are the eigenvalues of $A^{T}A$, omitting the additional zero eigenvalues when $n>m$. The positive singular values number exactly the matrix rank.

Let $u_j$ and $v_j$ be the columns of the orthogonal matrices $U$ and $V$ in the singular value decomposition. Multiplying by the rectangular diagonal matrix retains its $r$ nonzero diagonal entries:The families $(u_j)$ and $(v_j)$ are orthonormal, hence in particular orthogonal. Each summand is a rank-one outer product, and the remaining terms vanish because their singular values are zero.

The two columns are orthogonal, with lengths one and two; equivalently $A^{T}A=\mathrm{diag}(1,4)$. Ordering the singular values decreasingly requires swapping the right coordinate directions. One full singular value decomposition isBoth $U$ and $V$ are orthogonal matrices, and direct matrix multiplication gives $U\Sigma V^T=A$. Hence

An error of order $ϵ$ in a squared singular value can become an error of order $\sqrt{ϵ}$ after taking its square root. To keep $A$ nonsingular as required, take $0<ϵ<1/2$ andThen $\Vert A{\Vert }_2=1$, 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 $\hat{U}=I_2$ giveswhich has no uniform $O(ϵ)$ 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 $A\hat{V}{\hat{\Sigma }}^{-1}$ exactly for these perturbed factors gives $\mathrm{diag}(1,ϵ/\sqrt{{ϵ}^2+ϵ})$, whose second column has length tending to zero. Its product with $\hat{\Sigma }{\hat{V}}^T$ equals $A$, 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.

Let $\tilde{A}=\hat{U}\hat{\Sigma }{\hat{V}}^T$. Interpret the diagonal of $\hat{\Sigma }$ 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 ${\sigma }_j(\tilde{A})$.

For completeness, the singular value perturbation bound follows from the Eckart-Young-Mirsky theorem. If $B_{j-1}$ is the truncated singular value decomposition of a matrix $B$, the triangle inequality givesExchange $A$ and $B$ to get $|{\sigma }_j(A)-{\sigma }_j(B)|\le \Vert A-B{\Vert }_2$. Applying this to $B=\tilde{A}$ 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.

Because $r<n$, choose a unit vector $v$ in the null space of $X^T$, so that $v^{T}X=0$. Let $J\in {\mathbb{R}}^{m\times n}$ have orthonormal columns, for example the first $n$ columns of $I_m$, and choose a real number $\alpha >1$. SetIts singular value along $v$ is $\alpha$, and its other singular values are $1$. Thus ${\sigma }_1(A)=\alpha >1={\sigma }_2(A)$. Meanwhile $AX=JX$. If $X$ has full column rank, the column space of the thin QR decomposition is exactly $\mathrm{range}(JX)$, which is orthogonal to $Jv$. Hence $PJv=0$ for $P=Q{Q}^T$, andConversely, an orthogonal projection is a contraction in the Euclidean norm, so $\Vert (I_m-P)A{\Vert }_2\le \Vert A{\Vert }_2=\alpha$. ThereforeIf $X$ is rank deficient, complete the QR decomposition within $J(v^{\perp })$: this space has dimension $n-1\ge r$ and contains all columns of $JX$, so the required orthonormal completion exists there. The same proof applies. For rank-deficient data the choice of unused columns of $Q$ matters; the construction specifies a valid choice. If $Q$ instead contains only a basis of $\mathrm{range}(AX)$, the conclusion holds without any completion. A fixed sampling matrix can thus miss the unique largest singular value completely.

Write $\ell =r/2$; the requested expression requires the positive even integer $r\ge 2$. Split the thin singular value decomposition after $\ell$ columns:Here $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}=\Vert A-A_{\ell }{\Vert }_2$. Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to $\exp (-\Vert z{\Vert }_2^2/2)$, and an orthogonal matrix preserves both $\Vert z{\Vert }_2$ and volume. Thus $V^{T}X$, where $V=[V_a,V_b]$, 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 $P=Q{Q}^T$ and suppose ${\Omega }_a$ has full row rank. Its Moore-Penrose pseudoinverse is ${\Omega }_a^{†}={\Omega }_a^T({\Omega }_a{\Omega }_a^T{)}^{-1}$, so ${\Omega }_a{\Omega }_a^{†}=I_{\ell }$. The QR decomposition implies $(I_m-P)AX=0$, henceMultiplication by ${\Omega }_a^{†}$ expresses the missed leading columns in terms of the trailing columns. Substitution into $(I_m-P)A$ gives the exact identityFor any matrix $F$, the spectral norm of $[-FI]$ is $\sqrt{1+\Vert F{\Vert }_2^2}$, because its product with its transpose is $F{F}^T+I$. Using submultiplicativity of the operator norm, the orthonormality of $U_b$, and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient $A$; if ${\sigma }_{\ell +1}=0$, its right-hand side vanishes.

Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix ${\Omega }_a^T$ of size $r\times \ell$, rather than to its wide transpose. It givesThe upper estimate for ${\Omega }_b$, transposing if necessary, givesThus, with $K=2/(1-1/\sqrt{2})$,Since $n/r>1$, 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 $1\times 1$ example would require $|Z|\le 2$ for every standard normal random variable $Z$, 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 $C$ hold almost surely for every $A$. For example, take $n=m=3$, $r=2$, $A=\mathrm{diag}(L,1,1)$ with $L>1$, and a sampling matrixAt $X_0$, the sampled column space misses the first coordinate, so $\Vert A-\hat{A}{\Vert }_2=L$, whereas $\Vert A-A_1{\Vert }_2=1$. Choose $L>C\sqrt{3/2}$. Because $A{X}_0$ has full column rank, its orthogonal projection depends continuously on $X$ near $X_0$ through $AX(X^T{A}^{T}AX{)}^{-1}{X}^T{A}^T$. The strict violation persists in an open neighborhood of $X_0$. 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.

Under the permitted singular value bounds, $m=4n$ givesFor the symmetric positive-definite matrix $H=G^{T}G$ in part (iii), its eigenvalues are the squared singular values of $G$, soApply the supplied conjugate gradient convergence bound to $H$. For $e_k=x_k-x_{\ast }$ and nonzero $e_0$, the function $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$ increases with $\kappa \ge 1$, givingThus the error in this weighted norm contracts at a guaranteed exponential factor of at most $1/2$ per iteration, up to the prefactor $2$. Here $\Vert e{\Vert }_H=\Vert Ge{\Vert }_2$. The Pythagorean identity in part (iii) also identifies $\Vert e_k{\Vert }_H^2$ with the excess squared linear least-squares problem objective, which consequently decreases by a bound proportional to $4^{-k}$. For the Euclidean norm, the same eigenvalue bounds give $\Vert e_k{\Vert }_2/\Vert e_0{\Vert }_2\le 62^{-k}$.

For relative accuracy $0<ϵ<1$ in the $H$-weighted norm, it is sufficient to takeCompute $c=G^{T}b$ once in $O(mn)$ operations. Each iteration applies $p\mapsto G^T(Gp)$ with two dense matrix multiplications and uses $O(n)$ further arithmetic operations; when $m=4n$ this costs $O(n^2)$. Hence the total cost isUsing finite termination of the conjugate gradient method in exact arithmetic refines this to $O(n^2\min \{n,\lceil {\log }_2(2/ϵ)\rceil \})$. Explicitly constructing $G^{T}G$ first would add $O(m{n}^2)=O(n^3)$ setup work and is unnecessary. These accuracy estimates concern relative error; an absolute tolerance replaces $2/ϵ$ by $2\Vert e_0{\Vert }_H/ϵ$ when $\Vert e_0{\Vert }_H>ϵ$. If $e_0=0$, the initial guess already solves the problem.

As in part 2(b)(v), the Gaussian assumption alone does not make the printed singular value interval a certainty. For example, the event that every entry of $G$ has absolute value below a sufficiently small positive number has positive probability and forces $\Vert G{\Vert }_F<\sqrt{n}$, contradicting the asserted lower endpoint. The displayed rate is therefore conditional on the singular-value bounds authorized by the paper. The cost and convergence derivation are exact under that condition; an unconditional probabilistic statement would need an additional failure-probability estimate.

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

If one retains the Euler approximation $A=I+J\delta t$, 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 $\delta t^2$ 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 $J$, the exact map is $\Phi =e^{J\Delta t}$; for a changing reference trajectory it solves $\dot{\Phi }=J(t)\Phi$, $\Phi (0)=I$.

Use its singular value decomposition, $\Phi =U\Sigma V^T$. The initial orthonormal right singular vectors ${\mathbf{v}}_i$ diagonalize ${\Phi }^T\Phi$ and satisfyA singular value $s_i>1$ gives finite-time norm growth, $s_i<1$ 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, $s_i^2=1+{\lambda }_i\delta t+O(\delta t^2)$, 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.

We first derive the stress and energy facts used in both parts. The Cauchy traction $s=Tn$ is force per unit area in the deformed configuration. The first Piola-Kirchhoff traction $s_R=T_{R}N$ is force per unit reference area. Their force vectors are measured in the same spatial coordinates, but the area measures and the normals used to specify the surface are different.

Parametrize a reference surface by $x=x(u,v)$. Its oriented area vector is $(x_u\times x_v)dudv$. Under deformation, the two tangents become $F{x}_u,F{x}_v$. The cross-product identitytherefore proves Nanson's formula $nda=J{F}^{-T}NdA$. Equality of the physical force on corresponding surface patches now givesSince this holds for every reference normal,The first Piola-Kirchhoff stress tensor is generally not symmetric, whereas the Cauchy stress tensor is symmetric in the absence of couple stresses.

For the stated energy on orientation-preserving gradients, differentiation givesA stress-free state satisfies $F{F}^T=J^{-1}I$. Taking determinants yields $J^2=J^{-3}$, so $J=1$ and $F{F}^T=I$: precisely $F\in SO(3)$. These states are also the global energy minimizers. If $v_i>0$ are the singular values, the arithmetic-geometric mean inequality gives $|F{|}^2\ge 3J^{2/3}$, with equality only when the singular values are equal. The function $3J^{2/3}/2+J^{-1}$ decreases up to $J=1$ and increases thereafter, with minimum $5/2$. Thus $W\ge 5\mu /2$, with equality precisely at rotations. A constant shift of the energy can set this minimum to zero without changing the stress.

For the given simple shear,For a unit normal $N$, $|T_{R}N{|}^2={\mu }^2(N_1^2+N_2^2)={\mu }^2(1-N_3^2)$. Hence every reference plane whose normal lies in the $e_1,e_2$ plane is maximizing:There is a family of maximizing planes, rather than one distinguished normal.

By the spectral theorem a symmetric positive-definite matrix $C$ has $C=Q\mathrm{diag}(c_i)Q^{\mathsf{T}}$, with $Q$ orthogonal and $c_i>0$. Define $S=Q\mathrm{diag}(\sqrt{c_i})Q^{\mathsf{T}}$. It is symmetric positive-definite and $S^2=C$. For uniqueness, any symmetric positive-definite square root $T$ commutes with $C=T^2$, hence preserves each eigenspace of $C$. On its $c$-eigenspace, $T$ is symmetric positive-definite and all its eigenvalues have square $c$, so all equal $\sqrt{c}$. Therefore $T=S$, including repeated eigenspaces.

For $\det F>0$, putThen $R^{\mathsf{T}}R=I$ and $\det R=\det F/\det U>0$, so $R\in SO(3)$; also $F=RU=VR$. Any other right polar decomposition has $F^{\mathsf{T}}F=U^2$, so uniqueness of the positive root fixes $U$ and then $R$. The left factor is consequently fixed too.

The principal stretches $v_i$ are the positive eigenvalues of $U$, equivalently the singular values of $F$. For a unit vector $N={\sum }_i{c}_i{N}_i$ in an orthonormal eigenbasis of $U$,Thus $\boxed{\underset{|N|=1}{\max }|FN|=v_{\max }}$, attained precisely by the unit vectors in the eigenspace of $U$ belonging to $v_{\max }$. With a simple largest eigenvalue these are its two opposite unit eigenvectors; degeneracy allows every unit combination within that eigenspace.

For the simple shear,A line with nonzero direction $N$ keeps its length exactly whenHence $\boxed{N_2=0\text{or}2N_1+\gamma N_2=0}$, with $N_3$ arbitrary. Every segment in the cube parallel to one of these directions preserves length; there is no restriction on its starting point other than remaining in the cube.

The two in-plane stretches are $v_{\pm }=(\sqrt{4+{\gamma }^2}\pm \gamma )/2$, and the third is one. A maximizing direction for $\gamma >0$ is $N\parallel (1,v_{+},0)$, since the $C$ eigenvalue equation gives $N_2/N_1=(v_{+}^2-1)/\gamma =v_{+}$. Therefore $\boxed{N\to \pm (1,1,0)/\sqrt{2}}$ as $\gamma \downarrow 0$. At exactly zero shear all directions tie; the limit refers to the selected maximizing direction for positive shear. These are the length-preserving directions and principal directions of simple shear.