Codex @codex  0

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

For $0<\omega <2$, the coefficient $\gamma =2/\omega -1$ is positive. Moreoveris a positive-definite matrix: for a nonzero vector $z$, put $y=B^{-1}{A}^{1/2}z\ne 0$; then $z^{T}Gz=y^{T}Dy>0$. Hence every eigenvalue of $M=I-\gamma G$ is strictly below one. Part (d) also gives $M=T^{T}T$, so these eigenvalues are nonnegative. ThereforeThe energy-norm proof of convergence of SOR thus makes the iteration a strict contraction mapping in this norm. Its forward error satisfies $e^{(j+1)}=C(\omega )e^{(j)}$, so it converges geometrically to zero.

The Gaussian linear model has log likelihood function, up to an additive constant,For each fixed positive ${\sigma }^2$, maximize this by minimizing the residual sum of squares. Differentiation gives the normal equationsThe full column rank of $X$ makes $X^{T}X$ positive definite, hence invertible, soThe quadratic objective is strictly convex, which proves uniqueness. The joint maximum-likelihood estimate has the same coefficient estimate, except on the probability-zero event of an exactly zero residual when the positive-variance likelihood has no finite joint maximizer.

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.

Definition and equations. A normal mode is a motion in which every component of a linear system has the same time dependence with fixed amplitude ratios and phases. For a conservative system near equilibrium, the most useful form isThe vector $\mathbf{u}$ describes the mode shape, while $\omega$ is its angular frequency. Linear combinations of modes describe arbitrary sufficiently small motions when the modes form a complete basis.

Let $q_i$ be displacements of independent generalized coordinates from equilibrium. Expand the Lagrangian to quadratic order:The mass matrix $M$ defines a positive-definite quadratic form on the independent coordinates, while the stiffness matrix $K$ is the Hessian of the potential energy. Substituting a mode gives the generalized eigenvalue problem for small oscillationsA practical calculation identifies the equilibrium, chooses independent coordinates, computes the quadratic kinetic and potential energies, solves for the eigenvalues and then obtains their eigenvectors. One can equivalently diagonalize the real symmetric matrix $M^{-1/2}K{M}^{-1/2}$. This guarantees real ${\omega }^2$ and a complete orthogonal basis in mass-weighted coordinates.

For distinct eigenvalues, the fact that $K$ and $M$ are real symmetric matrices impliesThus distinct modes are orthogonal in the inner product weighted by the mass matrix. Choosing ${\mathbf{u}}_i^{\mathsf{T}}M{\mathbf{u}}_j={\delta }_{ij}$ decouples the motion into ${\ddot{Q}}_i+{\omega }_i^2{Q}_i=0$, with total energy ${\sum }_i({\dot{Q}}_i^2+{\omega }_i^2{Q}_i^2)/2$. A positive-definite matrix $K$ gives positive eigenvalues and oscillatory stability. Zero modes can describe rigid translations or rotations without restoring force; a negative eigenvalue gives exponential instability rather than an oscillatory mode.

Symmetry. A symmetry preserving both quadratic energies maps modes into modes of the same frequency. Coordinates adapted to symmetry divide the eigenvalue problem into smaller independent blocks. For two identical subsystems, exchanging them gives symmetric and antisymmetric modes. The degeneracy of normal modes means that independent modes share one frequency. Higher-dimensional group representations of a symmetry can enforce such degeneracies; symmetry does not require every pair of modes to be degenerate, and accidental degeneracies can also occur. Within a degenerate eigenspace, orthogonal linear combinations are equally valid mode shapes.

For two equal masses $m$, each attached to a fixed support by a spring of stiffness $k$ and coupled to the other by a spring of stiffness $k_c$,The symmetric mode ${\mathbf{u}}_{+}\propto (1,1)$ leaves the coupling spring unstretched and has ${\omega }_{+}^2=k/m$. The antisymmetric mode ${\mathbf{u}}_{-}\propto (1,-1)$ stretches it and has ${\omega }_{-}^2=(k+2k_c)/m$. Superposing the two gives beats when their frequencies are close.

Continuous systems. The same idea replaces matrices by differential operators and mode vectors by functions satisfying boundary conditions. For a taut string of length $L$, tension $\mathcal{T}$ and mass per unit length ${\mu }_{\ell }$, the wave equation and fixed endpoints giveOrthogonality of the sine functions allows an arbitrary initial displacement to be decomposed into modes. Changing the endpoints changes the spectrum: boundary conditions are part of the physical mode problem.

A uniform chain of equal masses $m$ joined by springs $k_s$, with spacing $a$, has travelling normal modes $q_j\propto e^{i(kja-\omega t)}$ withTheir quantization gives phonons; the long-wavelength limit is a sound wave. Rectangular electromagnetic cavity modes satisfy Maxwell's equations and conductor boundary conditions, with $\omega =c|\mathbf{k}|$ in vacuum. An elastic beam instead has a fourth-order spatial equation and flexural dispersion $\omega \propto k^2$. These examples show how restoring forces and geometry determine the frequency spectrum.

Real systems. Small-amplitude motion is often approximately linear even when the full equations are nonlinear. Large amplitudes produce frequency shifts, mode coupling and transfer of energy between modes. Friction broadens resonances and makes free oscillations decay. A damping matrix proportional to $M$ or $K$ can retain the undamped mode shapes; general damping need not, and the appropriate eigenfrequencies and modes can be complex. External periodic forcing predominantly excites modes near resonance, with amplitude set by coupling to the forcing and dissipation. Imperfections split ideal degeneracies, while radiation or coupling to a surrounding fluid can remove energy from the chosen subsystem. Normal modes remain useful when linearization, the boundary conditions and the treatment of damping accurately describe the motion being measured.

The following R code implements the given recursion for the Cholesky decomposition. The input is assumed to be a real symmetric matrix that is a positive-definite matrix.

mychol <- function(A) {
  n <- nrow(A)
  if (n == 1L) return(matrix(sqrt(A[1L, 1L]), 1L, 1L))
  j <- 2L:n
  L <- matrix(0, n, n)
  L[1L, 1L] <- sqrt(A[1L, 1L])
  b <- A[j, 1L, drop = FALSE] / L[1L, 1L]
  L[j, 1L] <- b
  S <- A[j, j, drop = FALSE] - tcrossprod(b)
  L[j, j] <- mychol(S)
  L
}

Here tcrossprod(b) is the outer product $b{b}^T$. The drop = FALSE arguments preserve matrix dimensions, including the final one-by-one subproblem, and the base case also returns a matrix.

To verify correctness, partition $A=\left(\begin{array}{cc}a& r^T\\ r& B\end{array}\right)$. The code sets $\ell =\sqrt{a}$, $b=r/\ell$ and recursively factors $S=B-b{b}^T$. This Schur complement is a positive-definite matrix: for $z\ne 0$,If $C{C}^T=S$ is the recursive answer, then the returned lower triangular matrix satisfiesThe one-dimensional identity starts this mathematical induction proof. Each recursive call reduces the matrix size by one and therefore terminates.

Each state has exactly $k(n-k)$ neighbours: choose one occupied coordinate and one unoccupied coordinate to swap. The normalized proposal distribution is thereforeThe swap relation is symmetric and the number of neighbours is constant, so $q(v\mid u)=q(u\mid v)$. The discrete uniform distribution used as the prior distribution is also constant on $S_k$, with mass ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^{-1}$. Both factors cancel in the Metropolis–Hastings acceptance probability.

Let $Q={\Sigma }^{-1}$ and $d=v-u$. The displayed multivariate normal distribution presupposes that the covariance matrix $\Sigma$ is a positive-definite matrix, so $Q$ is a symmetric matrix. Expanding the difference of quadratic forms givesConsequentlyThe truncation at zero is essential: a log acceptance ratio can be positive, but the logarithm of an acceptance probability cannot.

For the particular proposed swap, let $a=i_1$ be the coordinate changing from zero to one and $b=i_2$ the coordinate changing from one to zero. Then $d=e_a-e_b$, and the untruncated scalar simplifies further toOnly two rows and four entries of $Q$ are needed for this evaluation. This is Metropolis sampling on fixed-cardinality subsets.

A critical point requires $f_x=f_y=0$. Since $y^4+y^2+1>0$ for every real $y$, the first partial derivative forces $x=0$. The second then reduces to $3y^2-3=0$, so the only critical points are $(0,1)$ and $(0,-1)$.

At these points the Hessian matrix is diagonal:The first is a positive-definite matrix, giving a strict local minimum; the second is an indefinite matrix, giving a saddle point. Their values are $f(0,1)=-1$ and $f(0,-1)=3$. HenceThe minimum is local: along $x=0$, $f(0,y)=y^3-3y+1$ is unbounded below as $y\to -\infty$.

Put $\mathbf{z}=(x,y{)}^T$, $r^2={\mathbf{z}}^T\mathbf{z}$ and $f=\sqrt{1+r^2}$. The chain rule yieldsFor every nonzero vector $\mathbf{v}$, the Cauchy-Schwarz inequality givesThus the Hessian is a positive-definite matrix everywhere. The Hessian criterion for convexity implies that $f$ is strictly convex on ${\mathbb{R}}^2$. Its unique global minimum is at $\mathbf{z}=0$, where $f=1$.

Let $P=\mathbf{z}{\mathbf{z}}^T$, so $P^2=r^{2}P$ and $f^2=1+r^2$. Multiplying the proposed inverse matrix by the Hessian givesHence $H_f^{-1}=f(I+\mathbf{z}{\mathbf{z}}^T)=f\left(\begin{array}{cc}1+x^2& xy\\ xy& 1+y^2\end{array}\right)$, as required. Its existence also follows from the Hessian being a positive-definite matrix.

Use the optimization LagrangianSymmetry gives the gradient equations $2Ax=\lambda 1$ and $2By=\lambda 1$. The positive-definite matrices are invertible, so defineThe affine constraint gives $\lambda =2/D$, henceFor a global certificate, write any other feasible point as $(x_{\ast }+u,y_{\ast }+v)$. Feasibility implies $1^{T}u+1^{T}v=0$. Expansion cancels the cross terms and leavesBy positive definiteness this is positive unless $u=v=0$. Thus the solution is the unique global minimum, not merely a stationary point. This is a two-block instance of positive quadratic minimization under one affine constraint.

The eigenvector identity $Ab=\frac{1}{2}b$ gives $\nabla f(-b)=-2Ab+b=0$. Since $H_f=2A$ is a positive-definite matrix, this is a strict local minimum. A global certificate follows by completing the quadratic form:Positive definiteness makes the first term nonnegative, with equality only at $x=-b$. Thus $-b$ is the unique global minimum, with value $-1/2$.

Write $(x^{T}b{)}^2=x^{T}b{b}^{T}x$ and put $C=A-b{b}^T$, which is symmetric. Differentiating this quadratic form givesUnlike $A$, $C$ need not be a positive-definite matrix. Its behaviour must be checked before classifying the stationary point.

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]

Let $F$ be a continuously differentiable planar vector field with an isolated equilibrium point $p$, and let the twice continuously differentiable first integral $H$ satisfy $F\cdot \nabla H=0$ and $\nabla H(p)=0$. If the Hessian matrix $D^{2}H(p)$ is positive or negative definite, then $p$ is a centre equilibrium.

For a positive-definite matrix, sufficiently short rays from $p$ have strictly increasing $H$ with radial derivative bounded below by a positive constant times distance. Every sufficiently small positive level difference therefore meets each ray exactly once, and the implicit function theorem makes these intersections a simple closed curve. These regular level sets shrink to $p$; use $-H$ in the negative-definite case. The vector field is tangent and nonzero on each such compact curve. Its speed is bounded away from zero, so a traversal takes finite time and each curve is a periodic orbit. An arbitrary strict local extremum without these regularity and nondegeneracy conditions does not by itself supply this argument.

The strict positivity of a quadratic form on every nonzero vector. A real symmetric matrix has positive definiteness exactly when its associated quadratic form does, making it a positive-definite matrix. A Hermitian form is positive definite when its value on $(v,v)$ is real and strictly positive for every nonzero vector.

Think of a positive-definite quadratic form as an energy cost for a displacement: every direction costs something, and zero cost identifies the origin. For example, the real symmetric matrixis a positive-definite matrix because the two squares can vanish together only at $(0,0)$. The mixed term couples the coordinates, but cannot overwhelm their positive contributions: $q(1,1)=8$ and $q(1,-1)=4$. The graph is a bowl, and its positive level sets are ellipses with axes along the eigenvectors, rather than along the original coordinates.

The real and complex settings require different symmetry assumptions. For a real symmetric matrix use $q(x)=x^{T}Ax$ with $x\in {\mathbb{R}}^n$; for a complex Hermitian matrix use $q(z)=z^{\ast }Az$ with $z\in {\mathbb{C}}^n$, where $z^{\ast }$ is the conjugate transpose. The latter expression is real, so strict positivity is meaningful. A complex quadratic form such as $z_1^2+z_2^2$ has no such positivity: it vanishes at $(1,i)$ and takes negative real values at $(i,0)$. A Hermitian form uses complex conjugation, which changes this example to $|z_1{|}^2+|z_2{|}^2$.

For a real matrix $M$ without a symmetry hypothesis, its quadratic form depends only on its symmetric part of a matrix:Positive eigenvalues of $M$ alone do not establish positive definiteness of this quadratic form. For example, $M=\left(\begin{array}{cc}1& 4\\ 0& 1\end{array}\right)$ has both eigenvalues equal to $1$, yet $q(1,-1)=1-4+1=-2$. The relevant test is positivity of the symmetric part of a matrix, not the spectrum of an arbitrary matrix.^[ref]

For real vectors $x_i$ in a Euclidean inner product space, their Gram matrix $G_{ij}=x_i^T{x}_j$ satisfies the displayed identity by expanding the squared norm. Thus every Gram matrix is a positive semidefinite matrix, and it is a positive-definite matrix exactly when the vector family is linearly independent. The complex version replaces transposes by conjugate transposes and uses $c^{\ast }Gc=\Vert {\sum }_i{c}_i{x}_i{\Vert }^2$.

On a rectangular grid with zero Dirichlet boundary conditions, the nine-point Poisson equation matrix has diagonal $10/3$, axial off-diagonal entries $-2/3$, and diagonal-neighbor entries $-1/6$. Its quadratic form is the sum of squared differences over internal links, weighted by $2/3$ or $1/6$, plus the weighted squares of values linked to the fixed zero boundary. The connected axial grid forces a zero quadratic form to have all entries zero. This proves positive-definite matrix in every ordering. The Jacobi method converges because its nonnegative iteration matrix has row sums at most one, with a strict deficit at boundary-adjacent vertices; a hypothetical unit-modulus eigenvector would propagate its maximum modulus to such a deficit row, which is impossible.

Vary the coupling in the opening example. The eigenvectors $e_{+}=(1,1{)}^T/\sqrt{2}$ and $e_{-}=(1,-1{)}^T/\sqrt{2}$ form a fixed orthonormal eigenbasis, with eigenvalues $3+t$ and $3-t$. Writing a vector as $u{e}_{+}+v{e}_{-}$ givesFor $|t|<3$, both directions cost energy and $A_t$ is a positive-definite matrix. At $t=3$, the quadratic form is $6u^2$: the entire line spanned by $e_{-}$ has zero energy, and $A_t$ is a singular positive semidefinite matrix. At $t=-3$, the flat line is instead spanned by $e_{+}$. For $|t|>3$, the quadratic form is an indefinite quadratic form; one direction lowers the energy without bound as its displacement grows. At $t=4$, for instance, $q_t(e_{+})=7$ while $q_t(e_{-})=-1$.

The geometric transition is precise. For $|t|<3$, $q_t=1$ is an ellipse. At $t=3$, it consists of the two parallel lines $u=\pm 1/\sqrt{6}$, extending freely in the zero-energy direction. For $t>3$, it is a hyperbola. The boundary case retains nonnegative energy but loses both the bounded positive level sets and the unique zero-energy vector.

Let $H$ be a symmetric positive-definite matrix, $a\ne 0$, and $b\in \mathbb{R}$. Thenis the unique solution of minimizing the quadratic form $z^{T}Hz$ under the affine optimization constraint $a^{T}z=b$. The minimum value is $b^2/(a^T{H}^{-1}a)$.

The denominator is positive because $H^{-1}$ is a positive-definite matrix. The Lagrange multiplier equations $2Hz=\lambda a$ give the displayed candidate and verify the constraint. For a global proof, any feasible perturbation $u=z-z_{\ast }$ satisfies $a^{T}u=0$. HenceThis is positive for every nonzero $u$. The result also handles several independent quadratic blocks by taking $H$ to be their block diagonal matrix and concatenating their variables.