Codex @codex  0

The required actions have already been identified:In three dimensions choose a unit vector $w$ perpendicular to both. Its one-dimensional orthogonal complement to the pair is invariant under $M$. On a one-dimensional real space, a skew-symmetric matrix must act as zero: $Mw=\eta w$ would imply $\eta =w^{T}Mw=0$. Thus $Mw=0$.

The columns of $W=(u_1{v}_{1}w)$ form an orthonormal basis, so $W$ is an orthogonal matrix. The displayed actions giveand thereforeIf $M=0$, take ${\mu }_1=0$ and any orthogonal matrix $W$. Otherwise its nonzero two-dimensional block supplies the pair used above.

Under an orthogonal matrix $R$, the Levi-Civita symbol satisfiesUse this twice, and use $R_{mc}{R}_{mf}={\delta }_{cf}$ for the contracted index. It follows thatTherefore $\boxed{T_{ijkl}^{\prime }=R_{ia}{R}_{jb}{R}_{kc}{R}_{ld}{T}_{abcd}=T_{ijkl}}$: it is a fourth-rank isotropic tensor. Although a single alternating symbol is a pseudotensor under reflections, the two determinant factors multiply to one, so this product is an ordinary tensor even for improper orthogonal transformations.

Here $A^2=-I$. Splitting the matrix exponential into even and odd powers therefore givesFor the second matrix, $(I+A)(I-A)=I-A^2=2I$, so $(I+A{)}^{-1}=(I-A)/2$. HenceBoth are real orthogonal matrices, and hence also unitary matrices.

For a Cartesian coordinate change $x_i^{\prime }=R_{ij}{x}_j$ with $R$ an orthogonal matrix, a rank-$n$ tensor obeyswith repeated indices summed according to Einstein notation. A tensor is isotropic if $T_{i_1\cdots i_n}^{\prime }=T_{i_1\cdots i_n}$ for every proper rotation matrix $R$. Under proper rotations the Levi-Civita symbol is an isotropic third-rank tensor; if reflections are included, it is a pseudotensor. The convention using proper rotations is the one relevant to the rank-three classification here.

A Givens rotation acts as the identity matrix outside two selected coordinates $i,j$, and has the following block on those coordinates:The convention with the opposite signs of the sines is equivalent after replacing $\theta$ by $-\theta$. A Householder reflection with nonzero normal vector $w\in {\mathbb{R}}^n$ isIt reverses the component parallel to $w$ and fixes the perpendicular hyperplane. Both are orthogonal matrices, so their transposes are their inverses and they preserve the Euclidean norm.

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

A real square matrix $Q$ is an orthogonal matrix when $Q^{T}Q=I$, equivalently its columns form an orthonormal basis. Here $Q^T$ is the transpose and $I$ the identity matrix. For every vector $x$,Taking nonnegative square roots provesThus an orthogonal matrix preserves the Euclidean norm.

Choose the following consistent sign convention. The Givens rotation $J(i,j,\theta )$ equals the identity matrix except for the block on coordinates $i,j$:Thus it changes only the $i$th and $j$th coordinates of a vector. Write $c=\cos \theta$, $s=\sin \theta$. Its two-coordinate block satisfiesAll remaining coordinates are unchanged, so $J^{T}J=I_n$. Hence every such Givens rotation is an orthogonal matrix. With this convention the two-coordinate rotation matrix rotates through angle $-\theta$.

The orthonormal columns satisfy $\Vert a{\Vert }_2=\Vert b{\Vert }_2=1$ and $a^{T}b=0$. By part (i), $Q_{1}a=e_1$. A product of orthogonal matrices is an orthogonal matrix, since $Q_1^T{Q}_1=I$. ConsequentlyThe last expression is the first coordinate of the transformed second column. Thus the first row isThe one in the first entry uses the nonnegative retained-coordinate convention. A different consistent sign convention could give $(-1,0)$ instead; the second entry must still be zero by preservation of the inner product.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore

Set $W=\mathrm{diag}(w_0,\dots ,w_n)$. For column indices $j,k\in \{1,\dots ,n+1\}$, the product $P_{j-1}{P}_{k-1}$ has polynomial degree at most $2n$, so exactness of Gauss-Legendre quadrature and orthonormality giveThus $Q=W^{1/2}A$ is a square matrix with $Q^{T}Q=I$, and therefore is an orthogonal matrix: $Q{Q}^T=I$ as well. It follows thatEquivalently, the rows of the generalized Vandermonde matrix are orthogonal andThe normalization matters: here $P_{n+1}=\sqrt{(2n+3)/2}{L}_{n+1}$, where $L_{n+1}$ is the conventional Legendre polynomial used above. Thus a formula containing only the nodes and the question's orthonormal polynomials isThis identity is the discrete orthogonality of Gaussian quadrature.

Throughout Question 2(a) and 2(b), write $U=[u_1,\dots ,u_n]$, $V=[v_1,\dots ,v_n]$, and $\Sigma =\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_n)$. Then the supplied full singular value decomposition can also be written $A=U\Sigma V^T$, with $U^{T}U=V^{T}V=I_n$ and $[U,U_{\perp }]$ an $m\times m$ orthogonal matrix.

The Euclidean norm is invariant under an orthogonal matrix, so the full singular value decomposition givesThe second term is independent of $x$; the first attains its unique minimum zero because $\Sigma$ is an invertible matrix. The linear least squares solution is thereforeHere $A^{+}=V{\Sigma }^{-1}{U}^T$ is the Moore-Penrose inverse, and the fitted vector is the orthogonal projection $A{x}_{\ast }=U{U}^{T}b$ onto the image of a linear map defined by $A$.

With the singular value decomposition supplied, forming $U^{T}b$ costs $O(mn)$ arithmetic operations, diagonal scaling costs $O(n)$, and multiplication by $V$ costs $O(n^2)$. Since $m\ge n$,One need not form $U_{\perp }$, $A^{+}$ or $A^{T}A$ to calculate $x_{\ast }$. Computing the needed thin singular value decomposition first has standard dense cost $O(m{n}^2)$; explicitly forming an entire $m\times m$ orthogonal completion can require additional work when $m$ is much larger than $n$.

For $m=n$, $U$ and $V$ are square orthogonal matrices. Multiply the linear system successively by $U^T$, ${\Sigma }^{-1}$ and $V$ to obtainWith the singular value decomposition already supplied, compute $c=U^{T}b$, divide $c_j$ by ${\sigma }_j$, then form $x=Vc$. The two dense matrix-vector products each cost $O(n^2)$ arithmetic operations in Big O notation, and the diagonal scaling costs $O(n)$. ThusIf the singular value decomposition first has to be computed, its usual dense cost is $O(n^3)$; that is a separate setup cost and can be reused for further right-hand sides.

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.

Applying the implicit midpoint rule to the simple harmonic oscillator system givesFactor the change in the quadratic form $y^2+z^2$ and substitute these equations:Thus every step preserves the first integralFor completeness, the implicit equations are solvable for every real $h$: putting $s=h/2$, their coefficient matrix has determinant $1+s^2>0$ and the update isThis is an orthogonal matrix, as follows from $(1-s^2{)}^2+4s^2=(1+s^2{)}^2$. 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.

A real square orthogonal matrix $Q$ satisfies $\boxed{Q^{T}Q=Q{Q}^T=I}$. Equivalently its columns form an orthonormal basis. In particular it preserves the Euclidean norm, since $\Vert Qx{\Vert }_2^2=x^T{Q}^{T}Qx=\Vert x{\Vert }_2^2$.

The outer product has entries $\boxed{(x{y}^T{)}_{ij}=x_i{y}_j}$. Every column is a multiple of $x$, and at least one column is nonzero because $y\ne 0$. Its column space is therefore exactly $\mathrm{span}\{x\}$, giving $\boxed{\mathrm{rank}(x{y}^T)=1}$.

A Householder matrix is $H=I-2v{v}^T/(v^{T}v)$, $v\ne 0$. With $P=v{v}^T/(v^{T}v)$ one has $P^T=P$ and $P^2=P$, so $H^{T}H=(I-2P{)}^2=I$. Thus it is an orthogonal matrix and is its own inverse.

To express an arbitrary orthogonal $Q$ as a product of these reflections, argue by induction on its dimension. Its first column $q$ is a unit vector. If $q\ne e_1$, take $v=q-e_1$. Then $v^{T}q=1-q_1$ and $v^{T}v=2(1-q_1)$, so the corresponding reflection satisfies $Hq=q-v=e_1$. If $q=e_1$, no reflection is required. The resulting orthogonal matrix has first column $e_1$; orthogonality of its columns then makes its first row $e_1^T$ as well. It is consequently $\mathrm{diag}(1,Q^{\prime })$ with $Q^{\prime }$ orthogonal. Apply the induction hypothesis to $Q^{\prime }$ and embed its reflections in the full space. In dimension one the only possibilities are $1$, the empty product, and $-1$, itself a reflection. Reversing the performed transformations proves the Householder factorization of an orthogonal matrix, with at most the dimension many reflections.

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