Codex @codex  0

The Graph Laplacian converts local differences along edges into a linear map. Throughout this section, $G=(V,E)$ is a finite undirected graph with no self-loops or repeated edges, and each edge has weight one. In a fixed order of vertices, let $A$ be the adjacency matrix and $D$ the degree matrix. The combinatorial Graph Laplacian isThus the value at a vertex is compared with its neighbours. Every row sums to zero, so $L1=0$: a constant vector produces no differences. This definition and the associated Graph Laplacian quadratic form are developed in Spielman's authored survey.^[ref]

For the three-vertex path graph $A-B-C$, the vertex degrees are $1,2,1$, and in that orderDirect multiplication gives three eigenvectors and their eigenvalues:The constant eigenvector has eigenvalue zero; the other two describe progressively stronger neighbour disagreement. Dividing these eigenvectors by $\sqrt{3},\sqrt{2},\sqrt{6}$, respectively, gives an orthonormal basis. The four-vertex cycle graph is already worked out under circulant matrix, where Fourier diagonalization of a circulant matrix gives its eigenvalues.

Every formula here uses $L=D-A$ without degree normalization. For comparison, Chung's treatment uses the degree-scaled matrix $D^{-1/2}L{D}^{-1/2}$, with a convention for isolated vertices; its eigenvalues must not be substituted into the examples here.^[ref]

Let a real symmetric matrix $M$ have ordered eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$, with $n\ge 2$. If $A$ is obtained by deleting one matching row and column, its largest eigenvalue ${\mu }_1$ satisfiesThe Rayleigh quotient of $A$ is that of $M$ restricted to vectors whose deleted coordinate is zero. This gives the upper bound. Some nonzero linear combination of the top two orthonormal eigenvectors has that coordinate zero; normalizing it gives a quotient at least ${\lambda }_2$. The argument does not require distinct eigenvalues.

A characteristic field is linearly degenerate if the directional derivative of its speed along its right eigenvector vanishes. Its simple waves have constant propagation speed along the state curve, so they do not steepen by amplitude-dependent transport.

Linear operator theory studies linear maps, their spectra, invariant subspaces, and normal forms such as Jordan normal form. In a finite-dimensional vector space, eigenvalues identify parameters for which a shifted linear operator cannot be inverted. In an infinite-dimensional vector space, inversion can fail even without an eigenvector. The spectrum of a bounded operator captures this larger obstruction and connects linear algebra with the approximation questions of functional analysis.

A mass eigenstate diagonalizes the Hermitian mass operator or mass matrix and has a definite mass. In a flavor basis with off-diagonal mass terms, it is a linear combination of flavor states. For unstable particles, decay propagation instead involves an effective complex matrix; its eigenvectors need not inherit the orthogonality of a Hermitian mass problem.

For an $n$-by-$n$ square matrix $A=(a_{ij})$ over a field, its matrix trace is the sum of its diagonal entries:For example, $A=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ has trace $2+1=3$. Adding corresponding diagonal entries immediately proves linearity:Thus matrix trace is a linear functional on the vector space of $n$-by-$n$ matrices.^[ref]

The surprising point is that the sum is intrinsic to a linear operator, even though individual diagonal entries depend on the basis. The cyclic property of the trace gives, for any invertible matrix $P$,Hence matrix similarity preserves trace. For the example above, choose the change-of-basis matrix $P=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$. ThenThe diagonal entries have changed but their sum has not. This makes trace useful for extracting a feature of the underlying linear operator without finding a preferred basis.

Over the complex numbers, or over the real numbers after allowing complex eigenvalues, the trace equals their sum with algebraic multiplicity:No diagonalizable matrix hypothesis is needed.^[ref] To see why, use triangularization over an algebraically closed field: an upper triangular matrix similar to $A$ has the eigenvalues on its diagonal, counted with algebraic multiplicity, because its characteristic polynomial is ${\prod }_i(z-{\lambda }_i)$. Similarity preserves trace, so summing that diagonal proves the formula.

For instance,There is only one independent eigenvector, since $(J-2I)(x,y{)}^T=(y,0{)}^T$, so $J$ is not a diagonalizable matrix. Nevertheless its repeated eigenvalue contributes twice. For our earlier $A$, the characteristic polynomial is $z^2-3z+1$, its eigenvalues are $(3+\sqrt{5})/2$ and $(3-\sqrt{5})/2$, and their sum is $3$. An inexpensive diagonal sum therefore gives spectral information before solving the characteristic polynomial.

The trace of a real matrix does not give that linear map's volume factor: that factor is the absolute value of its determinant. For example, $2I_2$ has trace $4$ and area factor $4$, but $2I_3$ has trace $6$ and volume factor $8$. Their occasional numerical agreement in two dimensions is a coincidence. The connection between trace and local volume change gives a geometric interpretation near the identity matrix, and describes the volume rate of a flow map generated by a linear system of differential equations.

For a linear ordinary differential equation with holomorphic coefficients on a punctured disc, analytic continuation of a basis gives an invertible monodromy matrix. A nonzero eigenvector with eigenvalue $\lambda =e^{2\pi i\sigma }$ selects a solution $w$ for which $z^{-\sigma }w$ is single-valued and holomorphic. Its Laurent series gives $w=z^{\sigma }{\sum }_{n\in \mathbb{Z}}{c}_n{z}^n$. No regular-singular hypothesis is needed; infinitely many negative powers may occur.

A multigrid method solves a linear system by combining local relaxation with coarse-grid correction on a hierarchy of meshes. The key is to divide the work by scale: a suitable relaxation removes rapidly oscillating approximation error, while coarse-grid correction addresses slowly varying approximation error that relaxation barely changes. A broad error hump occupies many fine-grid points but fewer coarse-grid points; it becomes easier to resolve by relaxation after enough coarsening. This complementary action is why multigrid methods are useful for large finite difference method and finite element method systems.

For a concrete model, take the one-dimensional Poisson equation with homogeneous Dirichlet boundary conditions:Use $n$ interior points $x_j=jh$, $h=1/(n+1)$, and the centered finite difference systemThus $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$ is a symmetric matrix and a positive-definite matrix. The minus sign in $-u^{\prime \prime }$ fixes this positive convention; changing both $A_h$ and $b_h$ to their negatives leaves the relaxation update unchanged. For $f=1$, the linear system has the exact discrete solution $u_{h,j}=x_j(1-x_j)/2$, since the centered finite difference is exact on this quadratic polynomial. In general, the exact discrete solution need not equal the sampled continuous solution: solving the linear system removes algebraic approximation error, not the global discretization error.

Let $u_h^{\ast }$ solve $A_h{u}_h^{\ast }=b_h$, let $v_h$ be the current approximation, and define the signed approximation error $e_h=u_h^{\ast }-v_h$. The linear-system residual is $r_h=b_h-A_h{v}_h$, so $A_h{e}_h=r_h$. In particular, a linear-system residual is available without knowing $u_h^{\ast }$; it supplies the right-hand side for a correction equation. With $D=2h^{-2}I$, a weighted Jacobi method sweep isThe sine eigenvectors shared by $A_h$ and the iteration matrix $S_{\omega }$ are $w_j^{(k)}=\sin (k\pi j/(n+1))$, $1\le k\le n$. Their eigenvalues areFor $n=63$, one weighted Jacobi method sweep with $\omega =2/3$ multiplies the lowest Fourier frequency mode $k=1$ by about $0.999197$, but the highest Fourier frequency mode $k=63$ by about $-0.332530$. Four sweeps retain about $99.68\%$ of the first amplitude and $1.22\%$ of the second. The sign reversal of the second amplitude is harmless when its magnitude shrinks. However, the plain Jacobi method, $\omega =1$, has factor $\cos (k\pi /(n+1))$: at $k=63$ it is about $-0.998795$. A nearly alternating mode near the grid's Nyquist limit therefore persists almost as strongly as the smoothest mode. Plain Jacobi method convergence on a fixed Dirichlet boundary condition grid does not imply effective smoothing.^[ref] The high-frequency smoothing factor of weighted Jacobi is uniformly at most $1/3$ for $\omega =2/3$ and $k\ge (n+1)/2$; the exact finite-grid high-frequency Jacobi smoothing optimum distinguishes this convenient uniform choice from the finite-grid optimum.^[ref]

One two-grid cycle applies a few weighted Jacobi method sweeps, computes the linear-system residual, performs coarse-grid correction, and applies a few more sweeps. The first relaxation makes the remaining approximation error easier to represent on a coarse mesh; the last relaxation damps oscillatory components left after the transferred correction. In a geometric multigrid V-cycle, replace the expensive exact coarse solve by one recursive cycle on the coarse correction equation, starting its correction from zero. Repeat until a tiny coarsest linear system can be solved directly, then return through the levels by adding each interpolated correction and post-smoothing. The descent and return give the cycle its V shape.^[ref]

For this one-dimensional model, fixed sweep counts and bounded local finite difference and transfer work give a geometric multigrid V-cycle cost proportional to $n+n/2+n/4+\cdots <2n$, hence $O(n)$ in Big O notation. A fixed error reduction also needs a contraction factor bounded below one independently of $h$; per-cycle work alone does not establish that. Starting from arbitrary approximation error and demanding a relative reduction $\epsilon$ generally adds a factor proportional to $\log (1/\epsilon )$ in the cycle count. Full multigrid uses coarse solutions as initial guesses on successively finer meshes to target the global discretization error efficiently. The two-grid Poisson factor with weighted Jacobi illustrates favorable convergence for this model. Other partial differential equations, strong anisotropy, or poorly chosen coarse spaces and relaxation can defeat these choices; a linear-work guarantee for arbitrary linear systems does not follow.

A historical example of the multilevel viewpoint is Achi Brandt's April 1977 paper, which analyzes adaptive meshes and reports numerical experiments on linear and nonlinear boundary value problems. This is a documented development of the approach, not a claim that the paper was its first invention.^[ref] The figure above is generated from the displayed eigenvalues, with lines joining discrete nodes; it contains no experimental measurements.

With CPT symmetry, a Hermitian kaon mass matrix is $M=\left(\begin{array}{cc}{r}_0& z\\ z^{\ast }& r_0\end{array}\right)$. Its eigenvalues are $r_0\pm |z|$. For correlated roots $a^2=z$, $b^2=z^{\ast }$ and $ab=|z|$, the normalized lower and upper eigenvectors are $(a,-b)/\sqrt{2|z|}$ and $(a,b)/\sqrt{2|z|}$. They are orthogonal. This is a mass-only result; including decay requires the generally non-Hermitian effective matrix $M-i\Gamma /2$.

Two vectors are nonorthogonal when their inner product is nonzero. In the power method, the starting vector must be nonorthogonal to a dominant eigenvector.

A normal mode, also called an eigenmode, is a pattern of free oscillation in a linear system whose relative displacements stay fixed while a single temporal factor changes their size and sign. For an undamped stable vibrational mode,Here $\varphi$ is the mode shape, $A$ sets the amplitude, $\omega$ is the eigenfrequency expressed as an angular frequency, and $\phi$ is the oscillation phase. Every snapshot is a scalar multiple of the same mode shape; neighbouring regions may move in opposite directions. Normal modes of a double pendulum show that normal modes also describe coupled discrete systems, beyond strings. Their shapes are eigenvectors, rather than spatial eigenfunctions. ^[ref]

For the ideal wave equation on a string, take a uniform string of length $L$ with constant tension $\tau$ and linear mass density $\mu$. Assume small transverse slope, negligible bending stiffness, no damping, and fixed endpoints. Its wave speed is $c=\sqrt{\tau /\mu }$, and the nonzero normal modes areThe angular frequency ${\omega }_n$ is in radians per second; the frequency $f_n$ is in hertz. The wavelength is $2L/n$. The mode shape has $n$ loops separated by nodes of a standing wave, including both fixed endpoints. ^[ref]

As a worked example, choose $L=1\mathrm{m}$, $\tau =1\mathrm{N}$, and $\mu =1\mathrm{kg}{\mathrm{m}}^{-1}$. Then $c=1\mathrm{m}{\mathrm{s}}^{-1}$ and $f_1=0.5\mathrm{Hz}$, $f_2=1\mathrm{Hz}$, $f_3=1.5\mathrm{Hz}$. Their oscillation periods are $T_1=2\mathrm{s}$, $T_2=1\mathrm{s}$, and $T_3=2/3\mathrm{s}$. These are deliberately simple model parameters, rather than measurements of a musical instrument. The plot divides displacement by $A$ so that the three mode shapes can be compared, and uses each mode's own oscillation period for its snapshots.

For $\phi =0$, at $t=T_n/4$ every point has zero displacement, but most points have nonzero velocity. Only zeros of the mode shape are permanent nodes of a standing wave. At $t=T_n/2$ the original mode shape has reversed sign, and at $t=T_n$ it returns. The synchronized conversion between kinetic energy and potential energy is shown in normal-mode energy exchange.

The short derivation uses separation of variables: substituting $u=\varphi q$ into the wave equation gives ${\varphi }^{\prime \prime }+k^2\varphi =0$ and $q^{\prime \prime }+c^2{k}^{2}q=0$. The fixed-end boundary conditions remove the cosine spatial term and require $\sin (kL)=0$, hence $k=n\pi /L$ and ${\omega }_n=ck$. Different geometries and boundary conditions give different eigenfunctions; a sine mode shape is a property of this uniform fixed string, not a universal form of an eigenmode.

The usefulness is that a complicated vibration becomes a collection of harmonic oscillators. For sufficiently regular fixed-end initial data, the Fourier sine series givesThe initial displacement and velocity determine $a_n$ and $b_n$. This is the superposition principle in a Fourier sine basis, and modal energy distribution measures how strongly each normal mode is excited. The striking simplification is that each component keeps its identity while their sum can continually change shape. ^[ref]

These independent normal modes belong to the linear model. At larger slopes, changing tension introduces nonlinear effects and can couple the modes. A linearly damped string still admits a Fourier sine basis, but its temporal factors decay and need not oscillate; its energy dissipation identity for a linearly damped string replaces conservation of energy. More general damping need not leave undamped mode shapes independent.

The commutator measures failure of two operators to commute, on a common domain where the products are defined. Direct expansion gives $[AB,C]=A[B,C]+[A,C]B$. A common eigenvector of $A,B$ lies in the kernel of $[A,B]$, so an injective commutator excludes all nonzero common eigenvectors. A nonzero commutator need not itself be injective, and therefore does not alone exclude an individual common eigenvector.

For the matrix exponential $A(t)=e^{Lt}$, maximizing the energy ratio over nonzero initial conditions givesThe Rayleigh quotient achieves its maximum at an eigenvector of $A^{\ast }A$ with largest eigenvalue, equivalently a right singular vector of $A$. Such an optimal disturbance is generally not an eigenvector of $L$.

An orthonormal eigenbasis of a linear operator is an orthonormal basis consisting of eigenvectors. Each vector can be reconstructed from its scalar components along those mutually perpendicular unit directions. With the convention that the inner product is linear in its first argument,The finite-dimensional spectral theorem supplies such a basis for a self-adjoint operator. In its two-dimensional example, the coordinates of $x=(1,0{)}^T$ are $1/\sqrt{2}$ along $e_{+}$ and $-1/\sqrt{2}$ along $e_{-}$. The operator multiplies those coordinates by $3$ and $1$, and reconstruction gives $Ax=(2,1{)}^T$.

Repeated eigenvalues permit different orthonormal choices within one eigenspace, so the basis need not be unique. The spectral projection of a self-adjoint matrix onto that entire eigenspace is unique: it keeps the geometrically meaningful component without choosing individual axes inside it.

Write $A=aI+B$, where $B=\left(\begin{array}{cc}1& -2\\ 1& -1\end{array}\right)$ has $B^2=-I$. One eigenpair isBecause $A$ is real, conjugating $Ae=\ell e$ gives $A\bar{e}=\bar{\ell }\bar{e}$. The eigenvector matrix $(e,\bar{e})$ has determinant $2i\ne 0$, so the eigenvectors form a basis. Reality of $z$ then forces conjugate coefficients, giving $z=\alpha e+\bar{\alpha }\bar{e}$.

Set $c=(1-i)/2$. The forcing has the same basis decomposition,Equating the coefficient of $e$ in the linear system of differential equations yieldsFor $a>0$, an integrating factor gives $\alpha =(c/a)e^{-it}+C{e}^{-(a+i)t}$. The zero initial vector means $\alpha (0)=0$, soTaking the real vector combination givesExact secular resonance occurs at $a=0$: the forcing frequency matches the undamped homogeneous mode. For positive $a$, damping prevents secular growth, and the late-time periodic amplitude is proportional to $1/a$. Thus there is a resonant small-damping limit, but no unbounded resonant response at fixed $a>0$.

Since $(1-e^{-at})/a\to t$ for each fixed $t$, the requested limit givesEquivalently $\alpha =ct{e}^{-it}$ at zero damping; its linear prefactor displays the resonance explicitly.