Codex @codex  0

Interpret the high-success formulation as completeness at least $1-\delta (n)$ and soundness at most $\delta (n)$, where $\delta (n)\le 1/p(n)$ for a growing polynomial $p$. This is the standard error-reduction claim. Literally placing $O$ around a success probability approaching one supplies no useful lower bound; it is the failure probability that must be inverse-polynomially small.

Let $M_x$ be the quantum verifier acceptance operator acting on one witness register:Acceptance on $\rho$ is $\mathrm{Tr}(M_x\rho )$. On a NO instance, $\Vert M_x\Vert \le 1/3$; on a YES instance, an honest witness has acceptance at least $2/3$.

Ask for $r$ witness registers, with $r$ odd, run $V_x$ independently on each register with fresh ancillas, and accept a strict majority. The QMA parallel repetition with entangled witnesses acceptance operator isDiagonalize $M_x$. In the tensor-product eigenbasis, an eigenvalue of $M_x^{(r)}$ is the majority probability for independent Bernoulli random variables with parameters equal to the selected eigenvalues of $M_x$. On a NO instance every parameter is at most $1/3$. Coupling these variables using independent uniform random numbers shows that their upper majority tail is bounded by the tail with every parameter $1/3$. This bounds the operator norm and therefore covers every supplied witness, including a witness entangled across the registers. No independence assumption about a dishonest witness is being made.

For a valid Chernoff bound, if $S$ is a sum of $r$ independent Bernoulli variables of parameter at most $1/3$, Markov's inequality applied to $2^S$ yieldsAn honest product witness on a YES instance gives independent trials with rejection probability at most $1/3$, so its failure probability has the same bound. The printed concentration bound is not valid as stated: for five trials at parameter $1/3$, the upper-majority probability is $17/81>e^{-5/3}$. The valid bound above suffices for a rigorous proof.

Choose the next odd integer above $c^{-1}\ln p(n)$. ThenThe witness length and circuit size increase by only $O(\log p(n))$; the majority calculation has polynomial overhead. Conversely, inverse-polynomial failure probability is at most $1/3$ for all sufficiently large input lengths. Finitely many smaller lengths can be handled by hard-wired verifiers, giving the usual constants. Hence the two definitions give the same class QMA. The same QMA error reduction argument also yields exponentially small failure with polynomially many copies.

Use an $n$-qubit state as the witness. Uniformly choose a term $h_j$ and perform the two-outcome positive operator-valued measure $\{I-h_j,h_j\}$. Regard the second outcome as an energy flag. For witness $\rho$, its probability isThis is an efficient local-energy measurement verification: a unitary operator on the $k$ relevant qubits and one ancilla qubit can implement the measurement using the isometryThe local dimension is constant; the term matrices and the measurement can be approximated to inverse-polynomial accuracy. Uniform choice of $j$ and the classical threshold comparison also have polynomial overhead.

SetIn the nontrivial case $0\le a<b\le M$, $\delta$ is inverse-polynomial. Cases outside this energy range are decided directly from $0\le H\le MI$.

Ask for $r$ witness registers, measure an independently sampled local term on each, and accept if the mean number of energy flags is at most $\theta$. An honest product ground state on a YES instance has flag probability at most $p_{\mathrm{y}}$. The Hoeffding inequality gives failure at most $e^{-r{\delta }^2/2}$. For completeness, the required Bernoulli concentration estimate follows by bounding the centered log moment-generating function $f(\lambda )=\ln \mathbb{E}{e}^{\lambda (Y-p)}$: $f(0)=f^{\prime }(0)=0$ and $f^{\prime \prime }(\lambda )$ is a tilted Bernoulli variance, at most $1/4$. Hence $f(\lambda )\le {\lambda }^2/8$; exponential Markov's inequality optimized at $\lambda =4u$ yields $\mathrm{Pr}(\overline{Y}-p\ge u)\le e^{-2r{u}^2}$, and the lower-tail version follows in the same way.

Soundness must also cover entangled witness registers. The averaged flag effect is $R=H/M$. All its eigenvalues are at least $p_{\mathrm{n}}$ on a NO instance. The repeated verifier's acceptance effect is a polynomial in the commuting tensor-factor operators $R_j$ and $I-R_j$. In their product eigenbasis its eigenvalues are lower-tail probabilities of independent Bernoulli variables whose parameters are each at least $p_{\mathrm{n}}$. Their lower tail is bounded by the identical-parameter tail at $p_{\mathrm{n}}$, using the same uniform-variable coupling as in QMA parallel repetition with entangled witnesses. Therefore its operator norm is at most $e^{-r{\delta }^2/2}$, which bounds acceptance for any entangled witness.

Choosinggives completeness at least $2/3$ and soundness at most $1/3$. A slightly larger constant absorbs implementation errors; for example, approximate each flag effect in norm to at most $\delta /8$, retain a gap at least $3\delta /4$, and increase $r$ by a constant factor. The total witness length $rn$ and circuit size are polynomial. Thus

Here is a finite-dimensional form of the Kitaev geometrical lemma. Let $A,B$ be positive operators, with nullspaces $S_A,S_B$ and all positive eigenvalues at least $\gamma >0$. First assume $S_A\cap S_B=\{0\}$. Let $P,Q$ be the orthogonal projections onto those nullspaces, and define their smallest angle between two subspaces byIf either nullspace is zero, set $\cos \vartheta =0$. Then

To prove it, spectral decomposition gives $A\ge \gamma (I-P)$ and $B\ge \gamma (I-Q)$. Write $C=P+Q$ and $c=\cos \vartheta$. For every vector $z$,Thus $C^2\le (1+c)C$. Since $C$ is positive semidefinite, each of its eigenvalues lies in $[0,1+c]$, so $2I-C\ge (1-c)I$. Consequentlyas claimed.

If there is a common nullspace $S=S_A\cap S_B$, restrict to $S^{\perp }$ and define the angle between $S_A\cap S^{\perp }$ and $S_B\cap S^{\perp }$ there. The same proof bounds the smallest positive eigenvalue of $A+B$ by $2\gamma {\sin }^2(\vartheta /2)$, while $S$ is its zero-energy subspace. This version gives a spectral gap above a possibly degenerate ground state space.

Set $h_x=1/(N+1)$ and $J=2N+1$. The Dirichlet discrete Laplacian has the eigenvectorsand its negative has the eigenvaluesThe discrete sine transform therefore reduces the method of lines equations to $q_j^{\prime \prime }=(\alpha -{\lambda }_j^h)q_j$. Each coefficient is an oscillator, a linear function, or a hyperbolic function according to the sign of ${\lambda }_j^h-\alpha$. A finite collection of oscillators is bounded in every fixed-grid norm. A zero-frequency mode can grow linearly, and a negative-frequency-square mode can grow exponentially. Consequently,is necessary and sufficient for all-time boundedness of a semidiscrete reaction wave equation on this grid. Equality allows bounded displacement only when the initial velocity has zero projection onto the first eigenvector; above it, the growing components must be absent in every unstable mode. A strictly positive spectral gap also gives a time-independent displacement bound uniform over grids whose gaps are bounded below.

The discrete threshold is strictly smaller than ${\pi }^2/4$, because $\sin s<s$ for $s>0$, and tends to ${\pi }^2/4$ as $N\to \infty$. A coarse grid can therefore introduce long-time growth into a continuum problem with $\alpha <{\pi }^2/4$. This is distinct from displacement stability of a symmetric semidiscrete wave equation on fixed finite time intervals. As in part (a), if existence of the printed limit is required for every initial datum, no $\alpha$ qualifies: any one mode admits oscillatory, secular, or growing initial data, depending on its coefficient.

The original PDF has $u_m^{n+1}$ on the left of the update; the converted TeX omits its $+1$. Use the Forward Euler method with $k=\Delta t\ge 0$ and $\mu =k/h_x^2$. The explicit time stepping for bounded reaction diffusion update matrix isWhen $0\le \mu \le 1/2$, the heat update $H_h$ has nonnegative stencil weights $\mu ,1-2\mu ,\mu$ and row sums at most one. Hence its induced maximum operator norm is at most one. It is also a symmetric matrix with eigenvaluesall in $[-1,1]$, so its discrete L2 norm operator bound is at most one too. Let $A_{\ast }=\max (|a_0|,|a_{+}|)$. In either of these norms,Iteration gives the mesh-uniform stability estimateThe same estimate applies to differences of solutions. Adding a per-step defect $k{r}^n$ gives $\Vert e^n\Vert \le e^{A_{\ast }T}(\Vert e^0\Vert +k{\sum }_{j<n}\Vert r^j\Vert )$.

This proof only requires $\mu \le 1/2$ and bounded reaction coefficients. It does not assume the full update $E_h$ is nonnegative: a negative $a_m$ can make its middle stencil weight negative when $\mu =1/2$. Nor does it claim contractivity or an all-time bound for every coefficient. The required stability is a bound uniform in the discretization on fixed finite intervals.

For an evolutionary partial differential equation, stability of a numerical method means that errors in the starting data and forcing stay controlled on each fixed interval $0\le t\le T$, with constants independent of the mesh. Fourier stability analysis is especially effective for a constant-coefficient finite difference method on a uniform infinite or periodic grid: translation invariance makes different Fourier modes evolve independently.

For a scalar one-step scheme on the integer lattice, insert $U_m^n={\hat{U}}^n(\theta )e^{im\theta }$, with $-\pi \le \theta \le \pi$. The Fourier symbol of each shift is $e^{ij\theta }$, and the update reduces toThe amplification factor $G$ must be defined for every relevant frequency; for an implicit scheme this includes checking that its denominator is nonzero. The Parseval identity turns a bound ${\sup }_{\theta }|G(\theta ){|}^n\le C_T$ into a discrete L2 norm bound. Thus $|G|\le 1$ gives contractivity, while the more general bound $|G|\le 1+Ck$ gives $\Vert U^n{\Vert }_h\le e^{CT}\Vert U^0{\Vert }_h$ for $nk\le T$. Conversely, frequencies with amplification uniformly greater than one produce unstable wave packets or periodic Fourier modes under refinement.

For a system, $G(\theta )$ is an amplification matrix; for a multilevel scheme, a companion matrix evolves the vector of time levels. The actual requirement is a uniform bound on matrix powers, not just their spectral radius. A nontrivial Jordan block at a unit-modulus eigenvalue creates polynomial growth in the time index. Even simple eigenvalues inside the unit disk can fail to give a uniform bound if the eigenvector matrices become ill-conditioned as the mesh changes. Uniformly controlled diagonalization of a matrix, or a suitable quadratic energy estimate, resolves this issue. The power boundedness of a two-level Fourier scheme illustrates why root multiplicities and conditioning matter.

For the heat equation, put $\mu =k/h_x^2$. Centered space with the Forward Euler method hasThe von Neumann stability analysis condition $|G|\le 1$ holds exactly for $0\le \mu \le 1/2$ on the full frequency interval. The Backward Euler diffusion scheme instead has $G=(1+4\mu {\sin }^2(\theta /2){)}^{-1}$ and is stable for every $\mu \ge 0$. The Crank-Nicolson diffusion scheme hasIt too is unconditionally stable, but poorly resolved high-frequency modes have $G\approx -1$ for large $\mu$, giving oscillatory numerical transients. A-stability therefore does not guarantee strong damping; L-stability distinguishes the damping of the Backward Euler method.

For the advection equation $u_t+c{u}_x=0$, let $\nu =ck/h_x$. Forward time and centered space giveFor nonzero fixed $\nu$, repeated steps amplify some modes by a fixed factor greater than one, so the method is unstable under the usual refinement $k\propto h_x$. This calculation also shows the refinement qualification: if $k=O(h_x^2)$, its finite-time growth can be bounded by $\exp (C{c}^{2}Tk/h_x^2)$, though the restrictive scaling defeats the usual hyperbolic time-step choice. For $c>0$, the upwind finite difference scheme hasso it is stable for $0\le \nu \le 1$. The Lax-Wendroff advection scheme instead hasgiving $|\nu |\le 1$. These examples separate the effects of the spatial stencil, temporal approximation and Courant number; a higher order of a numerical method by itself does not establish stability.

A periodic boundary condition is ideal for this analysis. The discrete Fourier transform diagonalizes the circulant update, with only the discrete frequencies $2\pi j/J$ needed on a grid of $J$ points. A bound on all $\theta$ is a convenient guarantee over every such grid. On the whole line, the Fourier transform uses a continuous frequency interval and the Parseval identity proves the corresponding square-summable-data estimate.

Homogeneous Dirichlet boundary conditions do not admit arbitrary complex exponential Fourier modes. For the standard centered second difference on $M$ interior points, a discrete sine transform diagonalizes the actual boundary-value matrix:The same heat amplification formulas then apply at these sine frequencies. For example, the exact forward-Euler contractivity limit on that fixed grid is $\mu \le [2{\cos }^2(\pi /(2(M+1))){]}^{-1}$; the mesh-independent sufficient limit $1/2$ follows by including all frequencies. Homogeneous Neumann boundary conditions can similarly permit a discrete cosine transform, provided the endpoint discretization and its weighted inner product are chosen consistently. The constant mode is then present, reflecting conservation of the heat equation's spatial mean. For inhomogeneous boundary conditions, subtract a suitable lifting of the prescribed boundary data and estimate the induced source using the homogeneous evolution's bound and a Duhamel principle estimate. Bounds for the lifting and source must themselves be uniform in the mesh.

General boundary conditions require separate boundary stability of a finite-difference method. For an advection equation, incoming data are prescribed at the inflow boundary, while an outflow closure must respect the outgoing characteristics. An interior periodic Fourier symbol cannot detect a growing mode confined near a boundary. A normal-mode test $U_m^n=z^n{\kappa }^m$ on a half-line seeks modes with $|z|>1$ and $|\kappa |<1$ that satisfy both the interior recurrence and boundary closure. Their existence proves instability, and uniform control requires more than merely excluding isolated growing roots; the Uniform Kreiss--Lopatinskii condition addresses boundary resolvent bounds. Alternatively, a direct energy method using summation by parts can include the boundary terms and establish the required estimate.

Variable coefficients and nonuniform meshes usually destroy exact Fourier transform diagonalization. Frozen-coefficient Fourier stability analysis is then a useful diagnostic, but it is not automatically a proof for the full variable-coefficient boundary problem. The mesh-uniform energy method in question 5 is an example of a direct proof. Also, an L2 norm proof is not automatically a mesh-uniform maximum-norm proof: finite-dimensional norm-equivalence constants may grow with the number of grid points.

Finally, stability measures error propagation; consistency of a numerical method measures the defect of inserting the exact solution. For a well-posed linear initial-value problem in the chosen norm, the Lax equivalence theorem says that a consistent approximation is convergent exactly when it is stable. Boundary discretization and starting data must be included in that assertion. A Fourier calculation proves convergence only after consistency, well-posedness and the actual boundary treatment have also been checked.

Let $q_0$ be the stationary point and let $H=D^2\beta (q_0)$ be its real symmetric Hessian matrix. First suppose the stationary point is interior and nondegenerate, the oscillatory integral amplitude and oscillatory integral phase are sufficiently smooth, and boundary contributions are absent or smaller than the stationary contribution. Diagonalize $H$ by an orthogonal change of coordinates, with eigenvalues $h_1,h_2$. Locally,Scaling each principal coordinate by ${\lambda }^{-1/2}$ and evaluating its Fresnel integral gives the two-dimensional stationary-phase formula:Here $\mathrm{sgn}H$ is the number of positive eigenvalues minus the number of negative ones: $2$, $0$ or $-2$. The formula gives the leading nonzero term when $\alpha (q_0)\ne 0$. A partition of unity isolates this neighbourhood; integration by parts away from stationary points makes the remaining interior contribution smaller. For a smooth compactly supported oscillatory integral amplitude the local error is $O({\lambda }^{-2})$.

The printed assumption of a single stationary point alone is insufficient for an unconditional answer. A degenerate oscillatory integral phase $\beta =x^4+y^2$ with a smooth oscillatory integral amplitude supported near the origin has only one stationary point, but scales as ${\lambda }^{-3/4}$. Boundary terms can also contribute at order ${\lambda }^{-1}$: on the unit disk with oscillatory integral amplitude one and $\beta =x^2+y^2$,whose stationary contribution is $i\pi /\lambda$ and whose boundary contribution is $-i\pi e^{i\lambda }/\lambda$. Thus the boxed formula is the standard nondegenerate interior stationary contribution, with the stated hypotheses; the data as printed do not determine all possible leading behaviours.

The channel is prismatic: its width depends on height, not on $x$. A layer of depth $h$ has cross-sectional area $A={\int }_0^h\beta zdz=\beta h^2/2$. Volume conservation gives $A_t+(Au{)}_x=0$. With $g^{\prime }=G\varphi$, the integrated excess hydrostatic pressure force isThus the streamwise momentum balance is $(Au{)}_t+(A{u}^2+G\varphi \beta h^3/6{)}_x=0$. Under the specified vertical-settling approximation, the horizontal projection of the depositional boundary has width $\beta h$, so the particle balance is $(A\varphi {)}_t+(Au\varphi {)}_x=-\beta hw\varphi$, where $w=w_{0}f(\varphi )>0$ is the downward speed magnitude. The prismatic triangular-channel shallow water equations are thereforeThe pressure coefficient $h/3$ is the section-weighted mean of $h-z$. The factor two in deposition comes from top width divided by area. There is no streamwise widening term, because $\beta$ is constant along the channel.

Define the positive characteristic speed scale $c=\sqrt{G\varphi h/2}$. In variables $(u,\varphi ,c)$ the equations becomeThe coefficient matrix of this hyperbolic system has eigenvalues $u,u+c,u-c$. Hence the three characteristic families areAlong $dx/dt=u$, the concentration equation is the ordinary differential equation $d\varphi /dt=-2w\varphi /h$. Along $dx/dt=u\pm c$, the left eigenvectors $(1,\mp 4c/(3\varphi ),\pm 4)$ give the sedimenting triangular-channel characteristic compatibility equationsHere every derivative in a given equation follows that characteristic family, and $h=2c^2/(G\varphi )$. These three compatibility equations form the characteristic description; they are not three independent closed equations for all fields on any one curve. In particular, $u\pm 4c$ are not conserved Riemann invariants when the concentration varies: its differential and the deposition source must both be retained. The description assumes $h,\varphi >0$; the dry or zero-buoyancy limit is degenerate.

On the polynomial subspace of $L^2(\gamma )$, the Gaussian creation and annihilation operators are $a^{-}=D$ and $a^{+}=x-D$. Gaussian integration by parts makes them adjoints there and gives $[a^{-},a^{+}]=I$. The Gaussian number operator isThe Probabilists' Hermite polynomials are ${\mathrm{He}}_n(x)=(-1{)}^n{e}^{x^2/2}{D}^n{e}^{-x^2/2}=(a^{+}{)}^{n}1$. Their generating function is $e^{sx-s^2/2}={\sum }_n{\mathrm{He}}_n(x)s^n/n!$, giving $D{\mathrm{He}}_n=n{\mathrm{He}}_{n-1}$. The commutator also yieldsThe orthogonality follows by repeated integration by parts; the leading coefficient is one, so these polynomials span every polynomial. By the allowed density assumption $h_n={\mathrm{He}}_n/\sqrt{n!}$ is an orthonormal basis. Define the closed number operator by $N\sum c_n{h}_n=\sum n{c}_n{h}_n$ on $\sum n^2|c_n{|}^2<\infty$. This diagonal multiplication operator is self-adjoint and positive semidefinite; polynomial truncations show it is the closure of the polynomial operator.

The Ornstein-Uhlenbeck semigroup is $P_t=e^{-tN}$, or $P_{t}f={\sum }_n{e}^{-nt}{c}_n{h}_n$. It also has the Mehler formula for the Ornstein-Uhlenbeck semigroupTo verify the formula, apply its right side to $e^{sx-s^2/2}$: the Gaussian moment-generating function makes the result $e^{s{e}^{-t}x-s^2{e}^{-2t}/2}$, proving the eigenvalue identity on every Hermite polynomial. Positivity and invariance of Gaussian measure give $L^2$ contraction by Jensen inequality, so polynomial density extends the equality to all $L^2(\gamma )$. The coefficient expansion givesFor continuously differentiable $f$ with bounded derivative, differentiate the Mehler expectation by the dominated convergence theorem to get the Ornstein-Uhlenbeck gradient commutation identityThe same identity extends to the Gaussian Sobolev form domain. Mehler's formula also gives pointwise convergence to the Gaussian mean for such $f$, since bounded derivative permits at most linear growth.

The Gaussian Dirichlet energy is the energy form of $N$:For polynomials this follows from $N=(a^{-}{)}^{\ast }{a}^{-}$, and closure extends it to the form domain. For the given continuously differentiable $f$, Gaussian integration by parts yields $⟨f^{\prime },h_{n-1}⟩=\sqrt{n}{c}_n$, so Parseval identity proves the derivative-energy equality directly. Bounded derivative puts $f$ in the Gaussian Sobolev space, hence in that form domain; it need not be in the full operator domain, so $⟨f,Nf⟩$ is not always a legitimate initial definition.

Use the entropy functional ${\mathrm{Ent}}_{\gamma }(h)=\int h\log hd\gamma -(\int hd\gamma )\log \int hd\gamma$. Begin with bounded smooth $h>0$ bounded away from zero, and put $h_t=P_{t}h$. Invariance and Gaussian integration by parts give the Ornstein-Uhlenbeck entropy dissipation identityThe gradient identity and the permitted weighted Cauchy-Schwarz inequality, applied with weight $h$, implyThe entropy tends to zero as $t\to \infty$ by Mehler's formula and bounded convergence. Integrating in time and using invariance yields ${\mathrm{Ent}}_{\gamma }(h)\le \frac{1}{2}\int |h^{\prime }{|}^2/hd\gamma$. Set $h=f^2$ to obtain the sharp Gaussian logarithmic Sobolev inequalityFor the stated possibly unbounded $f$, apply the argument to smooth positive clipped approximations with a common positive lower bound and uniformly bounded derivatives. They can converge pointwise together with their derivatives and have a common linear-growth bound. Since Gaussian measure integrates every polynomial moment, dominated convergence theorem passes both the entropy and the derivative energy to the limit. This also justifies use of the supplied inequality when $2f{f}^{\prime }$ itself is unbounded. The normalization $\Vert f{\Vert }_1=1$ concerns $f$, and does not imply $\int f^{2}d\gamma =1$; the second term in the entropy definition must be retained.

For noisy data, exact equality $Ax=y$ may be impossible: the data can have a component outside the operator range. A least-squares solution of a linear inverse problem instead minimizesFor any variation $h\in X$, the adjoint operator givesThus statistical homogeneity in every direction is the normal equation for a linear inverse problem, $A^{\ast }Ax=A^{\ast }y$. It is also sufficient for a global minimum: when it holds,The residual is orthogonal to the closure of the range, since it lies in $\ker A^{\ast }$. A normal-equation solution therefore fits the component of the data representable by the forward map, while leaving the perpendicular component unfitted. If there is more than one such solution, select the minimum-norm least-squares solution, which lies in $(\ker A{)}^{\perp }$.

These facts explain the formulation, but do not make the inverse problem well posed. A compact operator of infinite rank typically has nonclosed operator range, so even the least-squares infimum need not be attained. A least-squares solution exists exactly when the orthogonal projection of $y$ onto $\overline{\mathrm{Ran}A}$ belongs to $\mathrm{Ran}A$. In a singular system of a compact operator, this becomes the Picard criterion. Also, the nonzero eigenvalues of $A^{\ast }A$ are the squares of the singular values of $A$: solving the operator normal equation directly can worsen numerical conditioning. The operator normal equation expresses least squares; it does not itself regularize the inverse problem. The subsequent finite Landweber iteration and its stopping rule provide the inverse-problem regularization.

Let $A$ be the adjacency matrix of a graph, $J$ the all-ones matrix and $1$ the all-ones vector. Counting two-step walks givesBecause $b\ge 1$, any two nonadjacent vertices have a common neighbour, so the graph is connected. The eigenvalue $k$ is simple: for a real eigenvector at $k$, a maximal entry and the averaging equation force its neighbours, and then every vertex, to have the same value. Since $A$ is real symmetric, its other eigenvectors lie in $1^{\perp }$, where $J$ vanishes. Their eigenvalues are thereforeHere $d>0$ for the present incomplete connected graph. Indeed $k\ge b$; if $d=0$, then $k=b=a$, which conflicts with $a\le k-1$ for an edge. If $r,s$ have multiplicities $m_r,m_s$, dimension and zero trace give $m_r+m_s=n-1$ and $k+m_{r}r+m_{s}s=0$. ThusThese are dimensions of eigenspaces, hence integers. A multiplicity may be zero; that does not affect the conclusion.

Put $\zeta =e^{\pi i/n}$. The group representations from the preceding construction with $ϵ={\zeta }^j$, $1\le j\le n-1$, will be denoted ${\rho }_j$. Their diagonal matrices for $a$ have distinct eigenvalues. The only possible invariant lines would be these two eigenspaces, and the matrix for $b$ exchanges them. Thus each ${\rho }_j$ is irreducible. Equivalently their $a,b$ matrices do not commute, so part (a) applies. The choices $j$ and $2n-j$ give equivalent group representations by exchanging basis vectors. The displayed range contains exactly one of each pair, and distinct members have different traces at $a$ because $\cos (\pi j/n)$ is strictly decreasing there.

For a one-dimensional character of a representation, write $a\mapsto \alpha$, $b\mapsto \beta$. The conjugation relation forces ${\alpha }^2=1$, and ${\beta }^2={\alpha }^n$. Hence there are exactly four choices:For even $n$, $\beta =\pm 1$ for either $\alpha$; for odd $n$, $\alpha =1$ has $\beta =\pm 1$ and $\alpha =-1$ has $\beta =\pm i$. Finally,The sum of squares of irreducible representation dimensions proves that these four one-dimensional and $n-1$ two-dimensional group representations exhaust the irreducibles, including $n=1$ where the latter list is empty.

A Lyapunov function near an equilibrium is a continuously differentiable positive-definite function $V$, vanishing there, whose derivative along trajectories is nonpositive. The strict Second Lyapunov theorem says a negative-definite derivative implies local asymptotic stability.

For sharper bounds than the circular test $x^2+y^2$, put $z=(x,y{)}^T$, $r^2=z^{T}z$ andA direct multiplication gives $A^{T}P+PA=-2I$. Its eigenvalues are ${\lambda }_{\pm }=(13\pm \sqrt{13})/12>0$. Since the nonlinear vector field is $Az+r^{2}z$,For $0<V<1$, the derivative is strictly negative. The Lyapunov theorem proves asymptotic stability. In fact $V(0)<1$ gives $V(t)\le V(0)$ andso the solution stays bounded, exists for all positive time and converges exponentially to zero.

The ellipse $V=1$ is invariant. In polar coordinates, $\dot{\theta }=-(2{\cos }^2\theta +{\sin }^2\theta )<0$, so it is a nonconstant periodic orbit, not part of the basin. For $V(0)>1$, use $r^2\ge V/{\lambda }_{+}$ to obtain $\dot{V}\ge 2V(V-1)/{\lambda }_{+}$. This implies finite-time blow-up by comparison with the scalar equation. Thus the exact basin is $\{V<1\}$ and every point outside its closure escapes to unbounded norm within its maximal existence interval.

The largest open disc centred at zero lying in this exact basin has radiusThe smallest radius such that every point strictly outside its circle escapes is the largest radius on the invariant ellipse:These are optimal: a larger attraction disc contains a periodic-orbit point, and a smaller escape threshold leaves a periodic-orbit point in its exterior. This is an exact quadratic basin boundary.

The simpler radial derivative is $\frac{1}{2}(d/dt)r^2=r^2(r^2-1)-xy$. It only certifies attraction for $r<1/\sqrt{2}$ and strictly increasing norm for $r>\sqrt{3/2}$. Those are optimal thresholds for a sign test on that radial derivative, not for the actual attraction and escape regions. If “increases without bound” is read as requiring monotonic increase from the initial instant, the smallest such uniform radius is $\sqrt{3/2}$: at direction $x=y$, any smaller threshold permits an initially decreasing norm. The sharper $r_2$ above concerns eventual unbounded escape, which need not be monotone at every instant.

The Gershgorin circle theorem says that every eigenvalue of a square matrix lies in at least one disc centred at a diagonal entry with radius the sum of the absolute values of the off-diagonal entries in that row.

For interior unknowns write the update as $u^{n+1}=B{u}^n$. The matrix is real symmetric and tridiagonal, with diagonal $1-\mu (a_{m-1/2}+a_{m+1/2})$ and adjacent entries $\mu a_{m+1/2}$. Each Gershgorin radius is at most $\mu (a_{m-1/2}+a_{m+1/2})$. Its real interval is therefore contained inFor $0<\mu \le 1/(2a_{+})$, every eigenvalue lies in $[-1,1]$. Symmetry gives an orthogonal diagonalization, so $\Vert B^n{\Vert }_2\le 1$ for every $n$: errors in initial data cannot grow. This is stability in the discrete ${\ell }^2$ norm, also in its $h$-weighted version. One can additionally see maximum-norm stability directly: the update weights are nonnegative with row sums at most one once the zero boundary unknowns are removed. Hence $\Vert B{\Vert }_{\infty }\le 1$.