Codex @codex  0

A QR decomposition of an $m\times n$ matrix, $m\ge n$, is $A=QR$, where $Q$ is an $m\times m$ orthogonal matrix and $R$ is $m\times n$ and upper trapezoidal: $R_{ij}=0$ for $i>j$. In particular its bottom $m-n$ rows vanish.

Successive left Givens rotations annihilate the entries below the diagonal, column by column. When working on column $j$, rotate rows $j$ and $i>j$; their earlier columns are already zero, so the earlier eliminations persist. If $G_k\cdots G_{1}A=R$, thenA product of orthogonal matrices is orthogonal. The construction remains valid for a rank-deficient matrix, although uniqueness is not asserted. This is QR decomposition by Givens rotations.

First rotate rows $2,3$ with $c=4/5$, $s=3/5$. The second column pair $(4,3)$ becomes $(5,0)$ and the corresponding third column pair $(1,2)$ becomes $(2,1)$. Next rotate rows $3,4$ with $c=4/5$, $s=3/5$, sending the third column pair $(1,3/4)$ to $(5/4,0)$. Thus $R=G_{34}{G}_{23}A$ and $Q=G_{23}^T{G}_{34}^T$. One exact QR decomposition isThe construction proves $Q^{T}Q=I$, and direct multiplication checks $QR=A$.

The linear least-squares problem is to minimize $\Vert Ax-b{\Vert }_2^2$ over $x\in {\mathbb{R}}^n$, allowing an overdetermined system to have a nonzero residual. For a full QR decomposition, $Q$ is $m\times m$ orthogonal and $R$ is $m\times n$ with an upper-triangular top block. Orthogonal transformations preserve the Euclidean norm, soIf $A$ has full column rank, the top triangular block is nonsingular; setting its residual to zero gives the unique minimizer, while the remaining residual is independent of $x$. Without full column rank, minimizers still exist but need not be unique.

For the specified matrix, one Householder reflection already produces an upper-triangular matrix. Take $v=(-1,1,1,1{)}^T$, the difference between the first column and $2e_1$, and setThe formula gives $H^T=H$, $H^2=I$. Direct multiplication yields the Householder QR decompositionAll subdiagonal entries in the remaining columns are already zero, so no further reflection is needed. For the supplied right-hand side, $Q^{T}b=(2,0,2,-2{)}^T$. Back substitution gives $x_3=1$, $x_2=-1$, $x_1=2$, henceThe residual $A{x}^{\ast }-b=(1,-1,-1,1{)}^T$ is orthogonal to every column of $A$, independently confirming the normal equations $A^T(A{x}^{\ast }-b)=0$.

Let $W=\mathrm{span}\{\mathbf{v},\mathbf{w}\}=\mathrm{col}V$. Since the two columns are linearly independent, the leading $2\times 2$ block $R_1$ inis invertible. Hence $S(W)=\mathrm{span}\{{\mathbf{e}}^{(1)},{\mathbf{e}}^{(2)}\}$. The hypothesis that $W$ is an invariant subspace of $A$ implies that this coordinate plane is invariant under $\hat{A}=SA{S}^{-1}$. Consequently the first two columns of $\hat{A}$ have no entries below row two, andwhere $B$ is the top-left $2\times 2$ block and $D$ is the bottom-right $(n-2)\times (n-2)$ block. Eigenvalue deflation by an invariant subspace now givessoagain counting algebraic multiplicities.

For the required orthogonal reduction, take a thin QR decomposition $V=Q_1{R}_1$, extend the two orthonormal columns of $Q_1$ to an orthogonal matrix $Q$, and set $S=Q^T$. ThenEquivalently, apply one Householder transformation to annihilate entries $2,\dots ,n$ of $\mathbf{v}$, followed by a second Householder transformation acting only on coordinates $2,\dots ,n$ to annihilate entries $3,\dots ,n$ of the transformed $\mathbf{w}$.

The linear least-squares problem is to choose $x\in {\mathbb{R}}^n$ minimizing the Euclidean norm of the residual:For a QR decomposition $A=QR$, orthogonality of $Q$ gives $\Vert Ax-b{\Vert }_2=\Vert Rx-Q^{T}b{\Vert }_2$. If $A$ has full column rank and $R=\left(\genfrac{}{}{0ex}{}{R_1}{0}\right)$ is in standard form with invertible upper-triangular $R_1\in {\mathbb{R}}^{n\times n}$, the minimizer solves $R_{1}x=(Q^{T}b{)}_{1:n}$.

Applying the Gram-Schmidt process to the columns of the given matrix yieldsIndeed, $Q$ is an orthogonal matrix and $A=QR$. Moreover,Back substitution in the leading triangular system givesso the unique least-squares solution isThe unused final transformed residual component is $1$, so the minimum residual norm is $1$.

Each QR decomposition $A_k=Q_k{R}_k$ givesInduction therefore yields the first Accumulated QR factorization identity:

We next prove the corresponding factorization of a matrix power. The case $k=0$ is just $A=Q_0{R}_0$. Ifthen the similarity formula above impliesConsequently,The product ${\overline{Q}}_k$ is orthogonal, and the product ${\overline{R}}_k$ is upper triangular. Henceis a QR decomposition.

Let the columns of $A$ be $a_1,a_2,a_3$. The Gram-Schmidt process givesNext,soFor the final column,andThus $q_3=\frac{1}{2}(-1,-1,1,-1{)}^T$ and $r_{33}=2$. The reduced QR decomposition isThe columns of $Q$ are orthonormal, and direct multiplication gives $QR=A$.

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$.

Direct solution usually uses a pivoted LU decomposition $PA=LU$: solve $Lz=Pb$ by forward substitution, then $Ux=z$ by back substitution. For a symmetric positive-definite matrix, the Cholesky decomposition iswith $C$ lower triangular and positive diagonal. It exploits symmetry, requiring about $n^3/3$ arithmetic operations rather than the leading $2n^3/3$ for general elimination.

If $A$ has full column rank and its reduced QR decomposition is $A=QR$, $Q^{T}Q=I$, thenChoose the signs of $Q,R$ so that $R$ has positive diagonal. Then $R$ is precisely the upper Cholesky factor of the normal-equation matrix $A^{T}A$, or $R^T$ is its lower factor. This identifies the factors; in computation, obtaining $R$ directly by QR decomposition avoids explicitly forming the normal equations, which square the condition number.

Every point in the affine search space is uniquely $x_k=x_0+V_{k}y$, since the columns of $V_k$ form a basis. Its linear-system residual is $r_k=r_0-A{V}_{k}y$, so minimizing the residual is exactly the linear least-squares problem ${\min }_y\Vert r_0-A{V}_{k}y{\Vert }_2$.

Use the standard starting choice $v_1=r_0/\Vert r_0{\Vert }_2$ and an orthonormal extended basis $V_{k+1}$. If $A{V}_k=V_{k+1}{L}_k$, then $r_0=V_{k+1}(\Vert r_0{\Vert }_2{e}_1)$ and orthonormality givesThe starting-vector choice is needed for this particular $e_1$ representation; an arbitrary orthonormal basis need not have those initial coordinates.

The Arnoldi iteration constructs the basis. At column $j$, orthogonalize $A{v}_j$ against $v_1,\dots ,v_j$, recording coefficients $h_{ij}=v_i^{T}A{v}_j$; normalize the remaining vector with $h_{j+1,j}$ to get $v_{j+1}$. This makes $L_k$ an upper Hessenberg matrix of size $(k+1)\times k$. The resulting GMRES algorithm starts from $x_0,r_0$, grows this Arnoldi basis, solves the small least-squares problem, and sets $x_k=x_0+V_{k}y$. Its small residual norm provides the stopping test. Incremental Givens rotations efficiently update the small QR decomposition instead of solving it anew. Zero initial residual means the system is already solved; Arnoldi breakdown gives an invariant subspace and, for nonsingular $A$, permits exact solution within it.

A real square orthogonal matrix satisfies $Q^{T}Q=Q{Q}^T=I$, so it preserves the Euclidean norm. The columns of $Z_h$ are orthonormal, hence $\Vert Z_{h}v{\Vert }_2=\Vert v{\Vert }_2$. The induced matrix norm therefore givesFor the left truncation, $\Vert Q_{\ell }^{T}A{\Vert }_2\le \Vert A{\Vert }_2$, and equality is guaranteed for arbitrary $A$ only when $\boxed{\ell =m}$. Indeed, if $\ell <m$, take $A=q_{\ell +1}{e}_1^T$, where $q_{\ell +1}$ is an omitted column of $Q$. Then $\Vert A{\Vert }_2=1$ but $Q_{\ell }^{T}A=0$. Merely taking $\ell \ge n$ does not guarantee preservation for an arbitrary $A$.

A full QR decomposition of a real $m\times n$ matrix is $A=QR$, with $Q$ orthogonal and $R$ upper trapezoidal; for a square matrix, $R$ is upper triangular. Fix the following sign convention for a Givens rotation: it is the identity except for its $(i,k)$ blockThe block transpose times the block is $I_2$ because $c^2+s^2=1$, proving orthogonality. Writing $r=\sqrt{x_i^2+x_k^2}$, the choice $\boxed{c=x_i/r,s=x_k/r}$ gives $(Jx{)}_k=0$ and $(Jx{)}_i=r$. To zero the other coordinate take $\boxed{c=x_k/r,s=-x_i/r}$, giving $(Jx{)}_i=0$. If $r=0$, both entries are already zero and the identity suffices.

For a tridiagonal matrix, successively rotate adjacent row pairs $(1,2),(2,3),\dots ,(n-1,n)$, each time zeroing the current entry $(k+1,k)$. Earlier columns remain triangular because both affected rows are already zero there. The result $R=J_{n-1}\cdots J_{1}A$ is upper triangular, so $Q=J_1^T\cdots J_{n-1}^T$ gives its QR decomposition. Only $n-1$ rotations are required; the resulting $R$ has at most two superdiagonals.

For a full square matrix, process columns $j=1,\dots ,n-1$. Within column $j$, for $i=n,n-1,\dots ,j+1$, rotate rows $(i-1,i)$ to eliminate the current $(i,j)$ entry. Previously cleared columns stay clear. With $J_1,\dots ,J_s$ in application order, $s=n(n-1)/2$, one has $\boxed{R=J_s\cdots J_{1}A,Q=J_1^T\cdots J_s^T}$. This is QR decomposition by Givens rotations.

The thin QR decomposition gives $AX=QR$. Its columns already belong to the column space of $Q$, so the orthogonal projection $Q{Q}^T$ leaves them fixed:This identity uses only $AX=QR$ and $Q^{T}Q=I_r$; it remains valid if $R$ is singular, provided such a factorization with orthonormal $Q$ is used.

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.

For the small QR decomposition, each of the $k$ Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column $j$, apply the rotation to two rows in columns $j,\dots ,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. Backward substitution in a triangular system costs $O(k^2)$.

Computing $\Vert b{\Vert }_2$ costs $O(n)$ and the final dense matrix multiplication $Q_k{y}_k$ costs $O(nk)$. Thus the total, with the Arnoldi decomposition already supplied, isHere $1\le k<n$, since $Q_{k+1}$ has orthonormal columns in ${\mathbb{R}}^n$. In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp $\Theta (nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating ${\tilde{H}}_k$ as an unstructured dense matrix would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

A QR decomposition is a factorization $A=QR$ with $Q^{T}Q=I$ and $R$ upper triangular. An orthogonal transformation preserves the Euclidean norm becauseFor the basic QR algorithm, start with $A_0=A$ and repeatedly formIn a convergent diagonal form, the diagonal entries give the eigenvalues; practical symmetric-matrix implementations use shifts and deflation to obtain and isolate such convergence. The basic unshifted iteration alone need not converge diagonally for every symmetric input.

At every step, however,Thus each iterate is orthogonally similar to its predecessor. Similar matrices have the same characteristic polynomial and eigenvalues, including multiplicities, so induction proves that every iterate has exactly the original eigenvalues. Orthogonal similarity also preserves symmetry.

A QR decomposition is $\boxed{A=QR}$ with $Q$ orthogonal and $R$ upper triangular. One algorithm for computing it is Householder reflection reduction; a sequence of such reflections produces a QR factorization. The diagonal of $R$ may include zero when $A$ is singular, and no nonsingularity assumption is needed here.

For seismic source inversion, collect calibrated, consistently filtered samples from all available stations and components into a data vector $\mathbf{d}$. 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 $\mathbf{G}$ 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 ${\mathbf{C}}_d$; a justified penalty can be added for regularization. At fixed $\mathbf{q}$, solve for the six entries of $\mathbf{m}$ 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.

A QR decomposition is $A=QR$, with $Q$ orthogonal and $R$ upper triangular. Orthogonality gives $Q^{\mathsf{T}}Q=I$, and therefore $\Vert Qx{\Vert }^2=x^{\mathsf{T}}{Q}^{\mathsf{T}}Qx=x^{\mathsf{T}}x=\Vert x{\Vert }^2$, proving invariance of the Euclidean norm.

The unshifted QR algorithm starts with $A_0=A$. At step $k$, factor $A_k=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k$. ThenThus consecutive matrices are related by orthogonal similarity, so they have the same characteristic polynomial and eigenvalues. Induction proves every iterate has the original eigenvalues. Symmetry is also preserved. When the iteration converges to diagonal form, its diagonal entries are the eigenvalues; practical implementations use shifts and deflation to improve convergence.