Codex @codex  0

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

The character of a representation is its trace. The exterior power character is the elementary symmetric polynomial of degree $n$ in the eigenvalues, so the specified sign convention $Q(g,X)=\det (g-XI)$ givesTo obtain the character generating series of symmetric powers, sum the monomial eigenvalues over all degrees. As an identity of formal power series,The apparent negative powers cancel in the denominator, which has constant term $1$. Equivalently, this series is the reciprocal of ${\sum }_{j=0}^d(-1{)}^j{\chi }_{{\Lambda }^{j}V}(g)t^j$. Comparing coefficients gives ${\sum }_{j=0}^{\min (d,n)}(-1{)}^j{\chi }_{{\Lambda }^{j}V}(g){\chi }_{S^{n-j}V}(g)=0$ for $n>0$, an explicit recurrence computing the symmetric-power characters from $Q$.

The symmetric power $S^{n}V$ is the quotient of $V^{\otimes n}$ identifying tensors which differ by permutation of the factors. The exterior power ${\Lambda }^{n}V$ is the alternating quotient, with a tensor having repeated equal factors set to zero. Both quotients inherit the given group action. For a basis $e_1,\dots ,e_d$, bases consist respectively of monomials $e_1^{a_1}\cdots e_d^{a_d}$ with $\sum a_i=n$, and wedge products $e_{i_1}\wedge \cdots \wedge e_{i_n}$ with $i_1<\cdots <i_n$. Thuswith the second dimension zero for $n>d$.

A finite-order group element is diagonalizable over $\mathbb{C}$, because its minimal polynomial divides $X^m-1$, which has no repeated roots. Choose an eigenbasis with eigenvalues ${\lambda }_1,\dots ,{\lambda }_d$. The induced eigenvalues, including multiplicities, areThe zeroth powers are the one-dimensional trivial representation, with the empty product equal to $1$.

Write $V(x)=F(\pi ,x)$. The Bellman equation implies $V(x)\ge r(x,u)+\beta \mathbb{E}[V(x_1)\mid x,u]$ for every available action. Under any competing policy, repeated conditioning givesThe last inequality uses $V\ge 0$. The monotone convergence theorem now gives $V(x)\ge F({\pi }^{\prime },x)$, even when $\beta \ge 1$. If $V(x)=\infty$ the comparison is immediate; otherwise the nonnegative conditional bounds justify each finite induction step. This proves Bellman comparison with nonnegative rewards and superunit discount without a vanishing-terminal-term assumption.

For the unit-bet policy in this gambler's ruin problem, put $\beta =\sqrt{9/8}=3/(2\sqrt{2})$. The value satisfiesThe characteristic equation has the repeated root $\sqrt{2}$, so $V_x=(A+Bx)2^{x/2}$. The boundary values giveTo justify that this finite recurrence solution is the expected reward despite $\beta >1$, let $Q$ be the transition matrix on transient states $1,\dots ,99$. The matrix $\beta Q$ is diagonally similar, with diagonal factors $2^{x/2}$, to the symmetric tridiagonal matrix with off-diagonal entries $1/2$. Its eigenvalues are $\cos (j\pi /100)$, $1\le j\le 99$, with absolute value below one. Thus its Neumann series converges and yields exactly the absorbed-payoff expectation and the unique recurrence solution.

When $p_2=1/4$, at wealth $2$ bet $2$ once and then follow the unit-bet policy. Its expected value is $\beta V_4/4=\beta V_2>V_2$, since $V_4=4V_2$. Therefore the unit-bet policy is not optimal.

The linearized perturbation obeys $\dot{\eta }=D\mathbf{f}(\mathbf{X}(t))\eta$, so its fundamental matrix satisfiesThe Floquet multipliers are the eigenvalues of the monodromy matrix $\Phi (T)$. Differentiating the orbit equation shows that $\dot{\mathbf{X}}(t)=\mathbf{f}(\mathbf{X}(t))$ is a solution of the variational equation. For a nonconstant periodic orbit this tangent solution is nonzero and periodic, giving one multiplier equal to $1$.

The Liouville formula for a fundamental matrix gives $(\det \Phi {)}^{\prime }=(\mathrm{tr}D\mathbf{f})\det \Phi$. Since $\det \Phi (0)=1$, the product of the two multipliers is $\exp ({\int }_0^T\nabla \cdot \mathbf{f}(\mathbf{X}(t))dt)$. The other multiplier is therefore exactly this exponential.

Order the interior grid values into a vector. The coefficient matrix has diagonal $4+c{h}^2$ and off-diagonal entries $-1$ at horizontal and vertical neighbours, with boundary values already zero. Every row is strictly diagonally dominant because $c>0$. The standard convergence theorem for strict diagonal dominance gives convergence of both the Jacobi method and the Gauss-Seidel method. The matrix is also symmetric positive definite.

For $D=(4+c{h}^2)I$, the weighted Jacobi method is $u^{(r+1)}=u^{(r)}+\omega D^{-1}(b-A{u}^{(r)})$, with iteration matrix $H_{\omega }=I-\omega D^{-1}A$. The sine-product grid eigenvectors giveThese weighted Jacobi eigenvalues for a square Dirichlet grid determine convergence. All eigenvalues of $A$ are positive. Thus for fixed $h$ convergence requires $0<\omega <2(4+c{h}^2)/a_{\max }$, where $a_{\max }=8{\cos }^2(\pi h/2)+c{h}^2$. As $h\downarrow 0$, this upper bound tends to $1$ from above. Any fixed $\omega >1$ therefore fails on sufficiently fine grids; $\omega \le 0$ also fails. Consequently $0<\omega \le 1$ is necessary for all mesh sizes, and it is sufficient, since $a_{\max }<2(4+c{h}^2)$ for every finite grid.

A multigrid method combines a fine-grid smoother with a coarse-grid correction. Starting with $u_h$, apply a few smoothing iterations, compute $r_h=b_h-A_h{u}_h$, restrict this residual to a coarser grid, and approximately solve $A_H{e}_H=R{r}_h$. Prolong the coarse error and update $u_h\leftarrow u_h+P{e}_H$, then post-smooth. The coarse solve is itself performed recursively, with a direct solve at the coarsest level; visiting each coarser level once gives a V-cycle. The smoother damps rapidly varying error, while error smooth on the fine grid is efficiently represented and corrected on the coarse grid.

For ordinary Jacobi, $\omega =1$, the highest-frequency sine-product error has eigenvalue approaching $-1$, not zero. In particular for the discrete Poisson equation it is $-\cos (\pi h)$, whose magnitude approaches one. This nearly alternating error changes sign between sweeps but is barely damped, and ordinary coarse-grid restriction does not represent it well. Thus with the standard point-Jacobi smoother and coarse-grid transfers one chooses $\omega \ne 1$, usually $0<\omega <1$, for fast multigrid convergence. For example $\omega =2/3$ makes the extreme high-frequency eigenvalue approach $-1/3$. Convergence of Jacobi as a standalone iteration is therefore insufficient to guarantee that it is an effective smoother. This conclusion concerns that standard multigrid choice; other smoothers or specially designed transfers can change it.

At a positive spatially homogeneous equilibrium point, $v=u^2$ and $2+u-v=0$. Hence $(u,v)=(2,4)$. The reaction Jacobian matrix there isThe two-dimensional Routh-Hurwitz stability criterion gives strict linear asymptotic stability for $a>2$, and instability for $0<a<2$.

For a spatial mode with $s=k^2$, the reaction-diffusion linearization is $J_s=J-\mathrm{diag}(s,ds)$. When $a>2$, its trace is negative for every $s\ge 0$, whileA growing mode exists precisely when this quadratic is negative at some $s>0$. Its minimum must occur at positive $s$, and must be strictly negative, givingWith $z=d/a$, the latter inequality becomes $4z^2-28z+1>0$. Selecting the root compatible with $2d>a$ yields the Turing instability thresholdThe unstable band isOn a bounded domain a boundary condition must permit a mode in this band. Equality at the threshold gives a neutral mode, not positive growth.

At $a=2$, the homogeneous linearization has purely imaginary eigenvalues, so it is not strictly linearly asymptotically stable. If “stable” is read as nonlinear stability, the boundary deserves attention. Put $x=u-2$, $y=(v-4-x)/\sqrt{3}$, and $x=r\cos \theta$, $y=r\sin \theta$. The exact equations give $\dot{r}=r^{2}F(\theta )$, $\dot{\theta }=\omega +rG(\theta )$, where $\omega =2\sqrt{3}$,Expanding $dr/d\theta$ through cubic order, ${\int }_0^{2\pi }F=0$ cancels the quadratic displacement. The correction from the quadratic change in $r$ also integrates to zero, because it is proportional to $(\int F{)}^2$. Since ${\int }_0^{2\pi }FG=\pi /(2\sqrt{3})$, the Poincaré return map isThis cubic return-map stability of a weak focus shows that $a=2$ is a weak attracting focus. The strict linear range used in the Turing instability calculation is $a>2$; the positive homogeneous equilibrium is also nonlinearly asymptotically stable at the boundary $a=2$. For that boundary, $\mathrm{tr}{J}_s=-(1+d)s<0$ for every nonzero spatial mode. The same strict Turing instability threshold and unstable band therefore also apply there, with the homogeneous mode understood through nonlinear stability.

Let the distinct eigenvalues be ${\lambda }_1,\dots ,{\lambda }_{s^{\prime }}$. Distinct-eigenvalue eigenvectors are independent. A relation ${\sum }_{k=0}^{m-1}{a}_k{A}^{k}v=0$ becomes ${\sum }_i{c}_{i}p({\lambda }_i)w_i=0$, with $p(z)={\sum }_{k<m}{a}_k{z}^k$. Since every $c_i\ne 0$, it requires $p({\lambda }_i)=0$ for every $i$. No nonzero polynomial of degree below $s^{\prime }$ has that many distinct roots. Thus the first $s^{\prime }$ powers are independent, while ${\prod }_i(A-{\lambda }_{i}I)v=0$ gives the next dependence. Hence $\boxed{s=s^{\prime }}$. Equivalently the coefficients of these powers form a full-rank Vandermonde matrix through this index.

The linear-system residual at an approximate solution $x_m$ is $r_m=b-A{x}_m$. For symmetric positive definite $A$, the Conjugate gradient method has $x_m\in x_0+K_m(A,r_0)$ and minimizes the squared $A$-norm of the error over that affine space; its residual is orthogonal to $K_m(A,r_0)$.

If $A$ has $t$ distinct eigenvalues, interpolate $q(\lambda )=1/\lambda$ on them with a polynomial of degree at most $t-1$. The finite-dimensional spectral theorem gives $A^{-1}=q(A)$, so the exact correction $x_{\ast }-x_0=A^{-1}{r}_0$ lies in $K_t(A,r_0)$. The minimum possible error at step $t$ is therefore zero. Thus $\boxed{\text{CG terminates in at most }t\text{ steps}}$ in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If $r_0=0$, it terminates immediately.

A symmetric positive definite matrix preconditioner $M$ changes the system to $M^{-1/2}A{M}^{-1/2}z=M^{-1/2}b$, with $x=M^{-1/2}z$; practical preconditioned CG applies solves with $M$. It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.

Choosing $\boxed{M=A}$ makes the transformed matrix $I$, so one step suffices. But applying $M^{-1}$ already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.

For the reality of the eigenvalues, one may initially allow a nonzero complex eigenvector $\mathbf{v}$ with $M\mathbf{v}=\lambda \mathbf{v}$. Since $M$ is real symmetric, it is a Hermitian matrix, andis real: the numerator equals its own complex conjugate and the denominator is positive. Once $\lambda$ is real, a nonzero real or imaginary part of $\mathbf{v}$ supplies a real eigenvector. We work with the real unit eigenvectors of the problem.

For two such eigenvectors, symmetry givesDistinct eigenvalues therefore give zero dot product. Together with the prescribed unit lengths,These $n$ vectors form an orthonormal basis of ${\mathbb{R}}^n$.

Expand a real unit vector as $\mathbf{x}={\sum }_a{c}_a{\mathbf{e}}_a$. Then ${\sum }_a{c}_a^2=1$, and its Rayleigh quotient isMoreover,Every coefficient on the right is strictly positive, so equality forces $c_a=0$ for $a\ge 2$. Equality occurs precisely along the top eigendirection:

To obtain a unit vector in $S$ using just ${\mathbf{e}}_1,{\mathbf{e}}_2$, let $u=({\mathbf{e}}_1{)}_1$ and $v=({\mathbf{e}}_2{)}_1$ denote their first coordinates. If $u^2+v^2>0$, takeThen ${\alpha }_{1}u+{\alpha }_{2}v=0$ and ${\alpha }_1^2+{\alpha }_2^2=1$. Hence ${\alpha }_1{\mathbf{e}}_1+{\alpha }_2{\mathbf{e}}_2$ has first coordinate zero and unit length. If $u=v=0$, simply take ${\alpha }_1=1,{\alpha }_2=0$. In either case the Rayleigh quotient of the constructed vector isThe continuous quadratic form attains its maximum on the compact space $S$, so

For $\mathbf{x}=(0,\mathbf{y}{)}^T$, deletion of the first row and column gives ${\mathbf{x}}^{T}M\mathbf{x}={\mathbf{y}}^{T}A\mathbf{y}$, while $|\mathbf{x}|=|\mathbf{y}|$. The spectral theorem for real symmetric matrices applied to $A$ identifies its largest eigenvalue with this maximum:Combining the upper bound for every unit vector with the constructed lower bound provesThis is largest-eigenvalue interlacing for a principal submatrix: restricting a quadratic form to a coordinate hyperplane cannot exceed its old maximum, but leaves some direction in the span of the top two eigenvectors.

A matrix is a diagonalizable matrix if there is an invertible matrix $P$ for which $P^{-1}MP$ is diagonal. Its columns then form a basis of eigenvectors, and the diagonal entries are their corresponding eigenvalues.

Here the given eigenvectors form an orthonormal basis. Put them into the columns of $Q$:Define $\Lambda =Q^{T}MQ$. Its entries areThis proves the claimed diagonalization of a matrix, rather than merely guessing it:The trace follows directly from this factorization:because each column of $Q$ has unit length. Trace is the sum of the eigenvalues, with multiplicity.

For the particular matrix, $(M^2{)}_{ij}={\sum }_k{M}_{ik}{M}_{kj}$. If $i=j$, every $k\ne i$ contributes one and $k=i$ contributes zero. If $i\ne j$, precisely $k=i$ and $k=j$ contribute zero; the other $n-2$ terms contribute one. ThusApplying this identity to a nonzero eigenvector givesEvery eigenvalue is therefore $n-1$ or $-1$.

If $r$ is the multiplicity of $n-1$, the trace formula for a diagonalizable matrix and the zero diagonal giveso $r=1$. Up to ordering, the required diagonal form isFor $n=1$ this means just $(0)$. For $n\ge 2$, the eigendirections are also transparent: the all-ones vector has eigenvalue $n-1$, and the $(n-1)$-dimensional subspace whose coordinate sum is zero has eigenvalue $-1$, since $(M\mathbf{x}{)}_i={\sum }_j{x}_j-x_i$. The spectrum consists of one collective mode and $n-1$ zero-sum modes.

Write the system as ${\mathbf{x}}^{\prime }=M\mathbf{x}$, with $M=\left(\begin{array}{cc}2& 5\\ -1& -2\end{array}\right)$. Its characteristic polynomial is ${\lambda }^2+1$, so its eigenvalues are $i$ and $-i$. An eigenvector for $i$ is $v=(5,-2+i{)}^{\mathsf{T}}$. Thus $e^{it}v$ is a complex solution, and its real part and imaginary part give real solutions:Their initial vectors are $(5,-2{)}^{\mathsf{T}}$ and $(0,1{)}^{\mathsf{T}}$, with determinant $5\ne 0$. Consequently they are linearly independent and span the two-dimensional solution space.

For the real coefficients of the stated self-adjoint Sturm-Liouville problem, define the weighted inner productSince $w>0$, a nonzero eigenfunction has positive squared norm. Let $Ly=-(p{y}^{\prime }{)}^{\prime }+qy$. Integration by parts and the Dirichlet boundary conditions giveTaking $u=v$ to be an eigenfunction shows that its eigenvalue is real, since $\lambda \int w|u{|}^2=\int (p|u^{\prime }{|}^2+q|u{|}^2)$ is real. For two eigenfunctions with eigenvalues $\lambda ,\mu$, the same identity givesHence distinct eigenvalues imply orthogonality in the weighted inner product. This is the orthogonality of Sturm-Liouville eigenfunctions. The calculation assumes the regularity needed for the stated self-adjoint boundary problem, so all boundary terms and integrals are defined.