Codex @codex  0

Symmetry of the real inner product gives $A^T=A$. Moreover, i with $y=x$ shows thatso the Gram matrix is a positive semidefinite matrix. To also check reality of every eigenvalue, allow a nonzero vector $z=a+ib\in {\mathbb{C}}^n$ with $Az=\lambda z$. Since $A$ is a real symmetric matrix,Here $z^{\ast }$ is the conjugate transpose, and $a^{T}Ab=b^{T}Aa$ cancels the imaginary part. Thusbecause $z^{\ast }z>0$. This proves both that every eigenvalue is real and that it is nonnegative.

If every $\Vert v_i\Vert =1$, then each diagonal entry of the Gram matrix is $A_{ii}=⟨v_i,v_i⟩=1$, so its matrix trace is $n$. Using iii and the permitted arithmetic-geometric mean inequality,The bound is attained by any orthonormal family, whose Gram matrix is the identity matrix.

A row's squared Euclidean norm is $[(1+\sqrt{3}{)}^2+1+(1-\sqrt{3}{)}^2]/6=3/2$, and the dot product of the two rows is $[2(1-3)+1]/6=-1/2$. Thus the row Gram matrix isFor the column Gram matrix, the first and third squared column norms are $4/3$, the middle one is $1/3$, and the respective cross-products are $1/3,-2/3,1/3$. HenceThe two products are square matrices of different sizes; their unequal dimensions are consistent with $A$ being rectangular.

A Hermitian matrix obeys $H^{†}=H$, where the dagger is conjugate transpose. If $Hv=\lambda v$ with $v\ne 0$, then $v^{†}Hv=\lambda v^{†}v$. This scalar is real because its complex conjugate equals $v^{†}{H}^{†}v=v^{†}Hv$. Since $v^{†}v>0$, the eigenvalue $\lambda$ is real.

For the Gram matrix, conjugate symmetry of the inner product givesThus $G$ is Hermitian. The assumption that the vectors form a basis additionally makes $G$ positive definite, though only Hermiticity is needed here.

The adjoint operator $A^{†}$, when it exists, is defined byfor all vectors in the relevant domains. This convention takes the inner product to be conjugate-linear in its first argument. Nondegeneracy makes the adjoint unique.

For the standard complex inner product $⟨x,y⟩={\overline{x}}^{T}y$, the equality becomes ${\overline{x}}^T{\overline{A}}^{T}y={\overline{x}}^T{A}^{†}y$ for every $x,y$, soThus the matrix adjoint is the Hermitian conjugate, not merely the transpose unless the entries are real. In a basis with positive Hermitian Gram matrix $G$, the same definition instead gives $A_G^{†}=G^{-1}{\overline{A}}^{T}G$, making the dependence on the chosen inner product explicit.

Expand the quadratic form of this Gram matrix:For $\mathbf{c}\ne 0$, linear independence of the real vectors implies ${\sum }_i{c}_i{\mathbf{x}}_i\ne 0$, so its squared Euclidean norm is strictly positive. Thusproving the positive definiteness of a Gram matrix in the independent-vector case.

Write $p_n(x)={\sum }_{j=0}^n{c}_j{x}^j$. The allowed orthogonal projection characterization, applied to the basis $1,x,\dots ,x^n$, gives the normal equationsExplicitly $G_{ij}=0$ if $i+j$ is odd and $G_{ij}=2/(i+j+1)$ if it is even. These equations can also be derived by differentiating $\int (u-\sum c_j{x}^j{)}^{2}dx$ with respect to each coefficient.

The Gram matrix $G$ is a symmetric positive-definite matrix. For any nonzero real coefficient vector $z$,The polynomial inside the square is nonzero, so its square is positive on some interval. Hence $G$ has zero kernel and is invertible. Thus the normal equations have exactly one solution, giving exactly one best least-squares polynomial. This proves both existence and uniqueness. For completeness, if the residual is orthogonal to ${\Pi }_n$, then for every $q\in {\Pi }_n$ the Pythagorean theorem gives $\Vert u-q{\Vert }^2=\Vert u-p_n{\Vert }^2+\Vert p_n-q{\Vert }^2$, directly verifying minimality and uniqueness.

Write ${\mathcal{P}}_n$ for the vector space of polynomials of polynomial degree at most $n$, and put $p_n(x)={\sum }_{j=0}^n{a}_j{x}^j$. As the question calls the weighted integral an inner product, its finiteness is implicit; for example, a positive integrable weight $w$ suffices for all the continuous functions involved here.

For every $q\in {\mathcal{P}}_n$, differentiating the squared weighted norm $\Vert f-p_n-tq{\Vert }_w^2$ at its minimum $t=0$ gives the orthogonality equationsIn particular, the requested linear system isIts Gram matrix $G_{kj}={\int }_{-1}^{1}w(x)x^{k+j}dx$ is a symmetric positive-definite matrix: for any nonzero vector $a$,Indeed a nonzero polynomial is nonzero on some open interval, and the weight is positive. Therefore $G$ is an invertible matrix, proving uniqueness. Conversely, if these equations hold, the Pythagorean theorem in an inner-product space gives, for every $q\in {\mathcal{P}}_n$,so the solution really is the unique best approximation.

Put $B=A_1^T{A}_1$. It is a symmetric matrix and a positive semidefinite matrix, while $A_2^T{A}_2=I_n-B$ is also a positive semidefinite matrix. By the spectral theorem, choose an orthogonal matrix $V=[v_1,\dots ,v_n]$ such thatThe bounds follow directly from $z^{T}Bz=\Vert A_{1}z{\Vert }_2^2\in [0,\Vert z{\Vert }_2^2]$. Define the diagonal matricesThe columns of $A_{1}V$ are mutually orthogonal, since $(A_1{v}_i{)}^T(A_1{v}_j)={\lambda }_j{\delta }_{ij}$. For each ${\lambda }_j>0$, set $u_{1j}=A_1{v}_j/\sqrt{{\lambda }_j}$. These columns are orthonormal. At a zero ${\lambda }_j$, one has $A_1{v}_j=0$; choose $u_{1j}$ by completing the already prescribed columns to an orthonormal set of $n$ columns in ${\mathbb{R}}^k$. Such a completion exists because $k\ge n$. This gives $A_{1}V=U_1{\Sigma }_1$, including the zero columns.

Likewise, the Gram matrix of $A_{2}V$ is $\mathrm{diag}(1-{\lambda }_j)$. Normalize its nonzero columns and complete at its zero columns in ${\mathbb{R}}^{m-k}$, using $m-k\ge n$. The resulting $U_2$ has orthonormal columns and $A_{2}V=U_2{\Sigma }_2$. Combining the identities givesThis is a form of the cosine-sine decomposition. Completing the zero columns is essential: neither block was assumed to have full column rank.

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.

The least-squares normal equations areThe full column rank of $G$ gives $z^{T}Hz=\Vert Gz{\Vert }_2^2>0$ for nonzero $z$, so $H$ is a symmetric positive-definite matrix. Apply the Conjugate gradient method to this linear system. To verify that its solution is the desired one, let $x_{\ast }$ solve the displayed equations. Then $G^T(G{x}_{\ast }-b)=0$, and for any $x$ the Pythagorean identity givesThus $x_{\ast }$ is the unique minimizer of the linear least-squares problem.

One can apply $H$ without forming the Gram matrix: compute $Hp=G^T(Gp)$. More explicitly, initialize $x_0$, $r_0=c-H{x}_0$, $p_0=r_0$; until the linear-system residual vanishes, use the Conjugate gradient method recurrenceEach dense application of $H$ this way costs $O(mn)$ operations. The condition number satisfies ${\kappa }_2(H)={\kappa }_2(G{)}^2$, where ${\kappa }_2(G)={\sigma }_{\max }(G)/{\sigma }_{\min }(G)$; this is the conditioning cost of the least-squares normal equations.

Independence and common error variance give $\mathrm{Var}(ϵ)={\sigma }^2{I}_n$. For the fixed matrix $A=(X^{T}X{)}^{-1}{X}^T$, the covariance transformation rule givesThus the covariance is determined by the error variance and the inverse Gram matrix of the design columns.

Write $q=A+Bx$ and $\ell =\log 3$. Orthogonality of $x^2-q$ to $1$ and $x$ givesThe Gram matrix is positive definite, with determinant $4(\ell -1)>0$, so the solution is unique. Solving yields

The singular weight requires care about the space of admissible polynomials. Since $n\ge 1$, $x^n$ has finite squared norm. A polynomial $q$ has finite error relative to $x^n$ near zero exactly when $q(0)=0$: a nonzero constant term makes the integrand asymptotic to $q(0{)}^2/x$, whose integral diverges. If $q(0)=0$, the residual is $O(x)$ and the integrand is $O(x)$.

Thus the full space ${\Pi }_{n-1}$ is not a subspace of $V$, so the projection theorem cannot be applied to it as written. Nevertheless a unique best finite-error approximation does exist inFor $n=1$, this is the zero space and the answer is $q=0$. For $n\ge 2$, $W$ is finite dimensional and its Gram matrix is positive definite, because a nonzero polynomial cannot vanish on an interval. Solving the normal equations therefore gives its unique orthogonal projection of $x^n$. All omitted polynomials have infinite error, so this also minimizes the extended error over the full polynomial set. The distinction is an invalid full-space projection premise, not nonexistence of every finite-error best approximation. As throughout weighted $L^2$, use equivalence classes for the underlying measure.

Write $q=A+Bx$ and $\ell =\log 3$. Orthogonality of $x^2-q$ to $1$ and $x$ givesThe Gram matrix is positive definite, with determinant $4(\ell -1)>0$, so the solution is unique. Solving yields

The singular weight requires care about the space of admissible polynomials. Since $n\ge 1$, $x^n$ has finite squared norm. A polynomial $q$ has finite error relative to $x^n$ near zero exactly when $q(0)=0$: a nonzero constant term makes the integrand asymptotic to $q(0{)}^2/x$, whose integral diverges. If $q(0)=0$, the residual is $O(x)$ and the integrand is $O(x)$.

Thus the full space ${\Pi }_{n-1}$ is not a subspace of $V$, so the projection theorem cannot be applied to it as written. Nevertheless a unique best finite-error approximation does exist inFor $n=1$, this is the zero space and the answer is $q=0$. For $n\ge 2$, $W$ is finite dimensional and its Gram matrix is positive definite, because a nonzero polynomial cannot vanish on an interval. Solving the normal equations therefore gives its unique orthogonal projection of $x^n$. All omitted polynomials have infinite error, so this also minimizes the extended error over the full polynomial set. The distinction is an invalid full-space projection premise, not nonexistence of every finite-error best approximation. As throughout weighted $L^2$, use equivalence classes for the underlying measure.

If $p$ is a minimizer, then for each $q\in {\Pi }_n$ the quadratichas a minimum at $t=0$, so $(u-p,q)=0$. Conversely, if this orthogonality holds, then for every $q\in {\Pi }_n$ the Pythagorean theorem in the inner product space givesThus the minimizers are exactly the orthogonal projections characterized byFor existence, write $p={\sum }_{j=0}^n{c}_j{x}^j$. The conditions form the normal equations $Gc=b$, with Gram matrix $G_{ij}=(x^i,x^j)$ and $b_i=(u,x^i)$. For every nonzero coefficient vector $v$,Indeed a nonzero polynomial is nonzero on some open interval away from $0$, where the weight is positive. Hence $G$ is a positive-definite matrix and is invertible, proving existence and uniqueness of $c$. Uniqueness also follows from the preceding Pythagorean theorem identity. The zero of the weight at one point therefore causes no degeneracy on continuous functions or polynomials.

Write $q(x)=a+bx$. Orthogonality of $x^2-q$ to $1,x$ givesThe entries are obtained by integrating $1/x,1,x,x^2$ over the given interval. Subtracting the second equation divided by two from the first gives $(\log 3-1)a=-1/3$. ThusThe Gram matrix is positive definite, with determinant $4(\log 3-1)>0$, so this orthogonal projection is the unique best approximation.

As explained by admissible polynomials for a singular inverse-linear weight, there is a domain issue: the constant polynomial does not belong to the weighted space, because ${\int }_0^1{x}^{-1}dx=\infty$. Hence the full space ${\Pi }_{n-1}$ is not a subspace of $V$, and the preceding inner-product projection theorem cannot be applied to it as stated.

Nevertheless a meaningful finite-error best approximation does exist after restricting to admissible polynomials. The target $x^n$ lies in $V$ for every $n\ge 1$, since its squared integrand near zero is $x^{2n-1}$. A polynomial $p\in {\Pi }_{n-1}$ has finite error exactly when $p(0)=0$: otherwise the residual tends to a nonzero constant and its weighted squared integral diverges; if $p(0)=0$, it has at least a simple zero and is integrable in the required norm. Thus the admissible approximation space isFor $n=1$ it is $\{0\}$, giving best approximation zero. For $n\ge 2$ it is a finite-dimensional inner-product subspace with positive definite Gram matrix, so it has a unique orthogonal projection of $x^n$. Therefore the full polynomial-space formulation is not defined inside $V$, but the finite-error interpretation has a unique best approximation. Declaring that no best approximation can exist under any interpretation would miss this admissible subspace.

If the error is orthogonal to ${\Pi }_n$, then for any $q\in {\Pi }_n$,proving sufficiency. Conversely, if $p_n$ minimizes, perturb it to $p_n+tq$ for any real $t$. The squared error becomesA minimum at $t=0$ forces the linear coefficient to vanish, proving necessity.

For existence, choose the basis $1,x,\dots ,x^n$. Its Gram matrix $G$ is positive definite because $c^{T}Gc$ is the squared norm of the nonzero polynomial with coefficients $c$. Thus $G$ is invertible, and the normal equations $Gc=((u,x^j){)}_{j=0}^n$ have a solution, giving an orthogonal residual and therefore a minimizer. The Pythagorean identity shows any other minimizer differs by a polynomial of zero norm, so it is equal to the first. Hence the best polynomial exists and is unique.