Codex @codex  0

For unit $u$, put $A=I-2u{u}^T$. Then $A^T=A$ and $A^2=I$, so $A$ is an orthogonal matrix. The affine reflection in a hyperplane is $R(x)=Ax+2cu$. Hence $R(x)-R(y)=A(x-y)$ preserves the Euclidean norm and distance, and $R(x)=x$ whenever $u\cdot x=c$. Thus it is an Euclidean isometry fixing the hyperplane pointwise.

For $p\ne q$, any reflection exchanging them must have normal parallel to $p-q$, and its fixed hyperplane must contain their midpoint. These requirements determine the perpendicular bisector uniquely:Changing both signs of $u,c$ leaves the same reflection. It belongs to the orthogonal group $O(n)$ exactly when its translation term vanishes, that is, $c=0$. Since $c=(\Vert p{\Vert }^2-\Vert q{\Vert }^2)/(2\Vert p-q\Vert )$,To prove the finite reflection decomposition of a Euclidean isometry, first note that a distance-preserving map $g$ fixing zero preserves inner products by the polarization identity. Its values on an orthonormal basis $e_i$ form an orthonormal basis, and $g(x)\cdot g(e_i)=x_i$ shows $g(x)={\sum }_i{x}_{i}g(e_i)$. Thus $g$ is orthogonal.

Every orthogonal transformation is a product of at most $n$ linear reflections: if $g(e_1)\ne e_1$, reflect $g(e_1)$ to $e_1$ using the hyperplane normal $g(e_1)-e_1$, which passes through zero. The resulting orthogonal transformation fixes $e_1$, and its restriction to $e_1^{\perp }$ is handled inductively in dimension $n-1$. If $g(e_1)=e_1$, no initial reflection is necessary. Reflections on the complement extend by fixing $e_1$; the induction starts in dimension zero.

For an arbitrary isometry $f$, if $f(0)\ne 0$, first reflect $f(0)$ to zero across its perpendicular bisector with zero. Composing this one affine reflection with $f$ gives an orthogonal transformation. If $f(0)=0$, skip the initial reflection. ThereforeThe glide reflection $(x,y)\mapsto (x+1,-y)$ cannot use fewer than three: its determinant sign is negative, excluding zero or two reflections, while absence of fixed points excludes a single reflection. Three suffice by reflecting successively in $x=0$, $x=1/2$, and $y=0$.

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

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.

Let $A$ be the interior-grid matrix representing ${\Gamma }_9$, with zero boundary error. It is real symmetric and has the stated sine eigenbasis. Put $s={\sin }^2(k\pi h/2)$ and $t={\sin }^2(\ell \pi h/2)$; the negative of its eigenvalue isThis increases in each variable on $[0,1{]}^2$. With $s_1={\sin }^2(\pi h/2)\ge h^2$, the smallest absolute eigenvalue is at least $8s_1-(8/3)s_1^2\ge (16/3)h^2$. Hence its Euclidean norm operator norm satisfiesThe corrected scheme has an unscaled residual $r$ whose individual entries are uniformly $O(h^6)$. There are $m^2$ entries and $m<h^{-1}$, so $\Vert r{\Vert }_2=O(h^5)$. Subtracting the exact nodal equations from the numerical equations gives $Ae=-r$ (with sign depending on the residual convention), and thereforeChoose a constant slightly larger than the resulting bound to obtain the requested strict $\Vert e\Vert <c{h}^3$ for all sufficiently small $h$. Uniform smoothness is needed for an $h$-independent constant; unspecified smoothness only in the interior would not by itself guarantee it.

Let $L=\mathrm{tridiag}(1,-2,1)$. The zero Dirichlet boundary values introduce no forcing terms, so the scheme isThe common orthogonal sine eigenvectors have $L$-eigenvalues $-4{\sin }^2[\pi j/(2(M+1))]$. Thus $B$ is invertible for every $\mu >0$, and each amplification eigenvalue isThe matrix $B^{-1}C$ is orthogonally diagonalizable, so its powers have Euclidean norm at most one, uniformly in the mesh and time step. Therefore Crank-Nicolson diffusion scheme is stable for every $\mu >0$. Negative amplification factors at large $\mu$ can create temporal sign oscillations, which do not contradict this norm stability.

The dot product and Euclidean norm are $\mathbf{x}\cdot \mathbf{y}={\sum }_i{x}_i{y}_i$ and $|\mathbf{x}|=\sqrt{\mathbf{x}\cdot \mathbf{x}}$. For every real $t$,Its quadratic discriminant is nonpositive, proving the Cauchy-Schwarz inequality $|\mathbf{x}\cdot \mathbf{y}|\le |\mathbf{x}||\mathbf{y}|$. In the inequality asked for, equality holds exactly when $\mathbf{x}$ is a positive scalar multiple of $\mathbf{y}$, and

Using the Levi-Civita symbol and its contraction identity,

Put $T=\mathbf{a}\cdot (\mathbf{b}\times \mathbf{c})$, the scalar triple product. Cyclic symmetry gives $\mathbf{m}\cdot \mathbf{a}=\mathbf{m}\cdot \mathbf{b}=\mathbf{m}\cdot \mathbf{c}=T$, so each requested angle $\varphi$ satisfies $\cos \varphi =T/|\mathbf{m}|$. If every pairwise angle is $\theta$ and $t=\cos \theta$, the preceding identity givesand therefore $|\mathbf{m}|=\sqrt{3}(1-\cos \theta )$. This is $0$ when $\theta =0$; for a right-handed orthonormal basis and $\theta =\pi /2$, $\mathbf{m}=\mathbf{a}+\mathbf{b}+\mathbf{c}$ has norm $\sqrt{3}$.

The three planes have equations $\mathbf{a}\cdot \mathbf{x}=\mathbf{a}\cdot \mathbf{p}$, $\mathbf{b}\cdot \mathbf{x}=\mathbf{b}\cdot \mathbf{q}$, and $\mathbf{c}\cdot \mathbf{x}=\mathbf{c}\cdot \mathbf{r}$. They meet at one point exactly when $\Delta =\mathbf{a}\cdot (\mathbf{b}\times \mathbf{c})\ne 0$, meaning their normals are linearly independent vectors. The point is

Two norms $N_1,N_2$ are equivalent norms when constants $c,C>0$ satisfyfor every $v$.

For $x,y\in {\mathbb{R}}^n$, the reverse triangle inequality givesby the Cauchy-Schwarz inequality. Hence $g$ is Lipschitz continuous, and therefore continuous.

On the compact Euclidean unit sphere, $g$ is positive and continuous, so the extreme value theorem gives $0<m\le g\le M<\infty$. Homogeneity then yieldsThus every norm on a finite-dimensional vector space is equivalent to the Euclidean norm; comparing two such bounds proves any two norms on $V$ are Lipschitz equivalent.

The relevant norm is the operator norm induced by the complex Euclidean norm, also called the matrix 2-norm:The maximum exists because the unit sphere in finite dimensions is compact. It obeys $\Vert Bq{\Vert }_2\le \Vert B{\Vert }_2\Vert q{\Vert }_2$ and is the norm relevant to the specified perturbation energy. Other matrix norms do not in general give this gain.

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

The spectral norm is the operator norm induced by the Euclidean norm:The Pauli operators $X_1$ and $Z_2$ act on different qubits, and each is a unitary operator. Their product is therefore unitary and preserves the norm of every vector. Hence

Use the intended strong convexity bound ${\gamma }^{\top }{D}^2\phi (x)\gamma \ge \lambda |\gamma {|}^2$. The original PDF omits $|\gamma {|}^2$ on the right. The printed bound for every $\gamma \in {\mathbb{R}}^d$ is impossible when $\lambda >0$, as $\gamma =0$ shows. Equivalently, the intended bound is stated for unit vectors. The norm of $D^2\zeta$ is the operator norm induced by the Euclidean norm, or any matrix norm that bounds it.

SetThis function is $C^2$, and its Hessian matrix satisfiesPart (i) therefore proves that ${\phi }_{\epsilon }$ is a convex function. The perturbation can use up the entire positive lower bound defining a strongly convex function; only convexity, rather than strict positivity of the Hessian matrix, is asserted.

Define $T^{†}(0)=0$; the printed quotient is undefined at the origin, but this continuous extension changes no transport cost because $\mu (\{0\})=0$. In polar coordinates, the two probability density functions giveBoth angular distributions are uniform, with independence of angle and radius. The proposed transport map preserves the angle and sends $r$ to $s=\sqrt{r}$. Thereforeand preservation of the angle proves $(T^{†}{)}_{\#}\mu =\nu$. As a local check using the Jacobian determinant, its radial and tangential derivatives for $r>0$ are $1/(2\sqrt{r})$ and $1/\sqrt{r}$, respectively, so $\det D{T}^{†}=1/(2r)$ and $g(T^{†}(x))\det D{T}^{†}(x)=(2r/\pi )/(2r)=f(x)$.

Now use the convex functionIt is convex because the Euclidean norm is convex and $s\mapsto (2/3)s^{3/2}$ is increasing and convex on $[0,\infty )$. It is differentiable, including at zero, andIts graph transport plan lies in the graph of $\partial \Phi$, so the Knott–Smith optimality criterion proves quadratic optimality. Since that plan is induced by a map, part 1(b) proves optimality for the Monge optimal transport problem as well. The minimum provides a useful independent check:

For a fixed shift $s$ that is not an eigenvalue, inverse iteration is the power method applied to $(A-sI{)}^{-1}$. Before normalization, the $k$th vector is proportional toIf $s<{\lambda }_1$, factor out the first coefficient:Every ratio in parentheses lies strictly between zero and one. The bracket therefore tends to $w_1$, and normalization in the Euclidean norm givesThis proves the stated convergence to $w_1$ or $-w_1$ and exhibits the convergence of fixed-shift inverse iteration rate.

Now suppose ${\lambda }_m<s<{\lambda }_{m+1}$. The closest eigenvalue to $s$ is one of ${\lambda }_m$ and ${\lambda }_{m+1}$.

Finally, if ${\lambda }_n<s$, the closest eigenvalue is ${\lambda }_n$ and its inverse eigenvalue is negative. Thus the direction approaches the line spanned by $w_n$, while normalized vectors alternate between the two signs. These cases are the sign behavior of fixed-shift inverse iteration.

Fix a number $k$ of colors. For a two-point set whose points are distance $d$ apart, take the vertices of a regular simplex with $k+1$ vertices and side length $d$. The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.

For an equilateral triangle of side length $d$, take a regular simplex with $2k+1$ vertices and side length $d$. The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.

To prove the product theorem for Euclidean Ramsey sets, let $S_X$ be a finite Ramsey witness for $X$ under $k$ colors. There are at most $k^{|S_X|}$ possible color patterns on $S_X$. Choose a finite Ramsey witness $S_Y$ for $Y$ under that many colors. Given a $k$-coloring of $S_X\times S_Y$, color each $y\in S_Y$ by the complete patternThere is a copy $Y^{\prime }\cong Y$ on which this pattern is constant. The common pattern on $S_X$ contains a monochromatic copy $X^{\prime }\cong X$. Every point of $X^{\prime }\times Y^{\prime }$ then has the same original color, and the orthogonal product is congruent to $X\times Y$.

A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.

It remains to show that the collinear set $\{0,1,2\}$ behaves differently. In every ${\mathbb{R}}^m$, use the finite coloringA congruent copy has the form $a-v,a,a+v$ with $\Vert v\Vert =1$ for the Euclidean norm. The parallelogram law givesPut $n_{+}=\lfloor 2\Vert a+v{\Vert }^2\rfloor$, $n_{-}=\lfloor 2\Vert a-v{\Vert }^2\rfloor$, and $n_0=\lfloor 2\Vert a{\Vert }^2\rfloor$. The errors introduced by the three floor functions show thatIf all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.

Put $G={\max }_i\Vert a_i{\Vert }_2$. By the Cauchy-Schwarz inequality,Interchanging $x$ and $y$ proves the Lipschitz bound

The subgradient method chooses $g_k\in \partial f(x_k)$ and a step size $t_k>0$, then setsAssume, as the question's use of $\min f$ requires, that a minimizer $x_{\ast }$ exists, and write $R=\Vert x_0-x_{\ast }{\Vert }_2$. Since every subgradient here has Euclidean norm at most $G$, the standard best-iterate estimate isTaking a suitable constant step when the target accuracy is known, or a standard diminishing sequence, gives error at most $ϵ$ initerations, so the requested exponent is $p=2$.

Differentiate the squared Euclidean norm and use the skew-symmetric matrix identity $A^T=-A$:Thus $\Vert \mathbf{y}(t){\Vert }_2^2$ is constant, and continuity of the nonnegative square root gives

Let the Bravais lattice have primitive vectors $a_1,a_2,a_3$, and putThe reciprocal lattice has the basisThe scalar triple product and cross product identities giveConsequently every $q={\sum }_j{n}_j{b}_j$ satisfies $q\cdot l\in 2\pi \mathbb{Z}$ for every lattice point $l={\sum }_i{m}_i{a}_i$, and conversely these three conditions force the coefficients of $q$ in the reciprocal basis to be integers. This proves that the displayed vectors generate ${\Lambda }^{\ast }$.

In the Born approximation, suppose that the crystal potential is the sum of translates of one atomic potential $V_0$ over the finite set $S$ of lattice sites. Its Fourier transform at the momentum transfer $Q=k-k^{\prime }$ factors asThus the single-atom scattering amplitude is multiplied by the crystal lattice structure factor $\Delta (Q)$. Writingseparates the sum into three finite geometric series. For $l_i=-L_i/2,\dots ,L_i/2$ this givesWhen the $L_i$ are large, a factor has a sharp maximum when ${\alpha }_i=2\pi n_i$. All three factors are therefore simultaneously large precisely when $Q\in {\Lambda }^{\ast }$. These are the reciprocal-lattice peaks of a finite crystal.

For the stated Body-centered cubic lattice basis,the reciprocal-basis formula givesEquivalently,The shortest nonzero reciprocal vectors have squared Euclidean norm $2(2\pi /a{)}^2$, so

In elastic scattering, $|k|=|k^{\prime }|=k$. If $q=k-k^{\prime }\in {\Lambda }^{\ast }$ and $\theta$ is the angle between $k$ and $k^{\prime }$, Euclidean geometry givesThe first possible diffraction peak therefore occurs atas $ka\to \infty$, by the small-angle approximation. This is the elastic Bragg scattering condition for the shortest reciprocal-lattice vector.

For a nonzero real vector $x$, the Rayleigh quotient of the matrix $A$ isThe Rayleigh quotient iteration starts from a unit vector $v_0$. Given $v_k$, compute the shiftsolve the linear systemand normalize in the Euclidean norm:The next eigenvalue estimate is ${\mu }_{k+1}=R_A(v_{k+1})$. The process stops when the eigenpair residual is sufficiently small.

For $X_i^{\ast }=(1,X_i^T{)}^T$ and $\gamma =({\gamma }_0,{\beta }^T{)}^T$, a linear support vector machine predictsOne penalized formulation minimizes empirical hinge loss plus a squared Euclidean norm penalty:Conventions often leave the intercept unpenalized, replacing $\Vert \gamma {\Vert }_2^2$ by $\Vert \beta {\Vert }_2^2$; this does not change the role of the two terms.

By optimality and part a,Since the Euclidean norm is at most the $L^1$ norm,uniformly over all replacements of at most $n-h$ observations. The distance from the original finite estimate is therefore uniformly bounded, proving