Codex @codex  0

The finite element method replaces an infinite-dimensional weak formulation by finitely many unknowns attached to a finite element mesh. Simple local functions, often piecewise polynomial functions, join to form a global approximation. The attraction is that each finite element can be integrated separately, while the assembled equations enforce a global balance. A piecewise-linear hat function only meets its immediate neighbors, so a large problem can have a sparse matrix rather than a dense one. Gilbert Strang's MIT lecture develops this connection from the one-dimensional weak formulation through local hats to the stiffness matrix and load integrals.^[ref]

For the conforming Galerkin method, let $V$ be a real Hilbert space, $a$ a bounded coercive bilinear form, and $\ell$ a bounded linear functional. Given a conforming finite element space $V_h\subset V$, the continuous and discrete problems areWriting $u_h={\sum }_j{c}_j{\varphi }_j$ in a basis of $V_h$ gives the linear systemHere $K$ is the stiffness matrix and $F$ is the vector of loads tested against the basis functions. The Galerkin method uses the same trial and test space in this construction. Finite element methods also use the Petrov-Galerkin method, with different trial and test spaces; testing against the trial space is therefore a property of this construction, rather than a definition of every finite element method.

The finite element solution of the one-dimensional Poisson equation below gives every entry explicitly. Refining the finite element mesh then improves the approximation by adding local degrees of freedom. For a symmetric coercive bilinear form, Galerkin orthogonality makes the discrete solution the best approximation in the energy norm; the geometry of orthogonal projection explains why this local construction yields a globally meaningful answer.

Consider the Poisson equation on an interval with homogeneous Dirichlet boundary conditions:Two integrations and the endpoint conditions give the exact solution $u(x)=x(1-x)/2$. To approximate it, multiply by a test function $v$ that vanishes at both endpoints. Integration by parts givesThe boundary term is zero. Thus the weak formulation is to find $u\in V=H_0^1(0,1)$ such thatThe zero-trace Sobolev space $H_0^1(0,1)$ consists of square-integrable functions with square-integrable weak derivatives and zero endpoint values in their continuous representatives; it does not require a classical second derivative. This is why continuous piecewise linear functions are admissible despite corners. The Poincaré inequality makes $a$ a coercive bilinear form on $V$. Strang derives this one-dimensional weak formulation, the piecewise-linear hat functions, and their load and derivative-product integrals in the cited lecture; its endpoint example uses a free left endpoint, while both endpoints here are fixed.^[ref]

Take the uniform finite element mesh $x_j=jh$, $j=0,\dots ,n$, with $h=1/n$. The continuous $P_1$ trial space isHere $P_1$ means polynomials of degree at most one on each interval. This is a conforming finite element space in $V$, with $n-1$ interior piecewise-linear hat functions ${\varphi }_i$ as a basis. Their endpoint values enforce the Dirichlet boundary conditions automatically. Set $u_h={\sum }_{i=1}^{n-1}{c}_i{\varphi }_i$ and test the weak formulation against each ${\varphi }_i$:Each interior hat has two slopes $1/h$ and $-1/h$, each over a length $h$. Its squared derivative therefore integrates to $2/h$. Adjacent hats have opposite slopes on their one shared interval, giving $-1/h$. All other derivative products vanish. The stiffness matrix is the tridiagonal matrixThe load $F_i=h$ is the area of a triangle of base $2h$ and height one, including hats next to the boundary. Boundary hats are omitted because the boundary values are prescribed. The piecewise-linear hat function article explains how the same entries arise by adding local two-node contributions.

With four mesh intervals, $h=1/4$, there are three unknowns:For example, the first row gives $8(3/32)-4(1/8)=1/4$ and the middle gives $-4(3/32)+8(1/8)-4(3/32)=1/4$. The coefficients are the nodal values $u_h(x_i)=c_i$. At $x=3/8$, linear interpolation gives $u_h(3/8)=7/64=0.109375$, whereas $u(3/8)=15/128=0.1171875$: exactness at the nodes still leaves a visible error between them.

In this model the Galerkin method solution equals the nodal approximation $I_{h}u$ obtained by linear interpolation on any finite element mesh. Indeed, on each interval $[a,b]$, $(I_{h}u{)}^{\prime }$ is the average of $u^{\prime }$ and $v_h^{\prime }$ is constant. Therefore ${\int }_a^b(u^{\prime }-(I_{h}u{)}^{\prime })v_h^{\prime }dx=0$. Summing proves Galerkin orthogonality for $I_{h}u$, and uniqueness gives $u_h=I_{h}u$. This argument relies on the constant diffusion coefficient, conformity and exact integration; nodal exactness is not a general promise for finite element methods with other operators or integration rules.

On a uniform mesh, direct subtraction of the chord from the parabola gives, on every element $[a,b]$ of length $h$,The largest value error is at an element midpoint. Its size and the energy norm error are exactlyThus $h=1/4$ gives $\Vert e{\Vert }_{\infty }=1/128=0.0078125$ and $\Vert e{\Vert }_a=1/(4\sqrt{12})\approx 0.0721688$. With eight elements, $h=1/8$, these become $1/512=0.001953125$ and $1/(8\sqrt{12})\approx 0.0360844$. Halving the mesh spacing quarters the maximum value error but only halves the energy norm error: values and slopes converge at different rates. The figure shows the small value error at its own scale, where the four-to-one reduction becomes clear.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

A flag is a strictly nested chain of vector subspaces of a fixed vector space. A complete flag contains a subspace of every possible dimension. For an action by linear maps, an invariant flag means that each of its vector subspaces is an invariant subspace. A basis adapted to an invariant complete flag makes all these maps upper triangular, connecting complete flags to simultaneous triangularization of a Lie algebra representation.

Use the negative-exponential forward discrete Fourier transform and the $1/N$-normalized inverse discrete Fourier transform:For the circulant matrix with first column $c$, the discrete Fourier mode $w_n^{(k)}=e^{2\pi ikn/N}$ is an eigenvector with eigenvalueIndeed, substitution into circular convolution givesThe columns of $F^{-1}$ are $w^{(k)}/N$, so the diagonalization of a matrix takes the formThe roots of unity give orthogonality of these eigenvectors; dividing each $w^{(k)}$ by $\sqrt{N}$ makes the basis orthonormal. Consequently, every complex circulant matrix is a normal matrix, including ones that are not Hermitian matrices.

The sign convention matters. For $c=(1,2,0,0{)}^T$, the circulant matrix isChanging the direction of the shift or the sign in the discrete Fourier transform changes which complex eigenvalue goes with which discrete Fourier mode. A real symmetric example alone would conceal that distinction.

For a linear system $Cx=b$, put $\hat{x}=Fx$ and $\hat{b}=Fb$. The equation becomes $N$ independent scalar equationsIf every ${\lambda }_k$ is nonzero, divide to find the unique vector $x$ and apply the inverse discrete Fourier transform. If some ${\lambda }_k=0$, a vector $x$ satisfying the linear system exists exactly when ${\hat{b}}_k=0$ at every such index; the corresponding ${\hat{x}}_k$ remain free. This is a concrete version of the Fredholm alternative in a finite-dimensional setting.

With an appropriate Fast Fourier transform, multiplication or a compatible solve takes $O(N\log N)$ arithmetic operations, instead of forming a dense matrix and applying general Gaussian elimination. The gain comes from the periodic structure; an arbitrary matrix does not have this shared basis of discrete Fourier modes.^[ref]

A free module is a module with a basis of a module $(e_i{)}_{i\in I}$: every element has exactly one expression $m={\sum }_{i\in I}{r}_i{e}_i$ with $r_i\in R$ and only finitely many $r_i$ nonzero. Equivalently, the coefficient map ${⨁}_{i\in I}R\to M$ is a module isomorphism. Existence means generation; uniqueness means linear independence in a module. For finite $I$ of size $n$, this says $M\cong R^n$, a finite free module. See Neil Strickland's Rings, Modules and Linear Algebra, section 11.

The integer lattice ${\mathbb{Z}}^2$ in the opening diagram is a free module over $\mathbb{Z}$ with basis of a module $e_1=(1,0)$, $e_2=(0,1)$. For example, $(3,2)=3e_1+2e_2$, and comparing the two coordinates makes the coefficients unique. A different basis of a module is $u=(1,0)$, $v=(1,1)$, because $(a,b)=(a-b)u+bv$; in particular $(3,2)=u+2v$.

By contrast, $w_1=(2,0)$ and $w_2=(0,1)$ are linearly independent in a module, but generate only the submodule $2\mathbb{Z}\times \mathbb{Z}$. They miss $(1,0)$ because $2a=1$ has no integer solution. They would form a basis over the rational numbers. Even generation need not let one extract a basis of a module: the elements $2,3$ generate $\mathbb{Z}$, since $1=3-2$, but neither singleton generates it, and $3\cdot 2-2\cdot 3=0$ is a nontrivial linear relation between them. These are concrete failures of the usual vector space argument that divides by any nonzero coefficient.

The cyclic module $\mathbb{Z}/6\mathbb{Z}$ has no basis of a module over $\mathbb{Z}$: every element has the nontrivial relation $6m=0$, so no nonempty subset is linearly independent in a module, while the empty subset cannot generate this nonzero module. Specifying the scalar ring is essential: over $R=\mathbb{Z}/6\mathbb{Z}$, the same additive object is a free module with the one-element basis of a module $\{\overline{1}\}$, since each coefficient is itself a unique class in $R$.

For a system of linear differential equations $u^{\prime }=A(t)u$, a fundamental matrix has columns forming a basis of its solution space. It solves $X^{\prime }=A(t)X$ and is invertible at every time in its interval. Every solution is $u(t)=X(t)c$ for a constant vector $c$: differentiating $X^{-1}u$ gives zero. Invertibility at one time implies invertibility throughout the interval by uniqueness of the initial value problem. This notion is distinct from a Markov-chain fundamental matrix or the projective-geometric matrix used in stereo vision.

Every finite-dimensional complex Lie algebra representation of a nilpotent Lie algebra decomposes into invariant generalized weight spaces. The nilpotence assumption is essential: a general solvable action can have extensions between distinct weights.

Here is a proof. For $h,k\in H$, nilpotence gives $(\mathrm{ad}h{)}^{N}k=0$, hence $(\mathrm{ad}\rho (h){)}^N\rho (k)=0$. By the nilpotent commutator preserves generalized eigenspaces lemma, every generalized eigenspace of $\rho (h)$ is invariant under every $\rho (k)$. Split successively by the acting operators of a basis of $H$. Each resulting block is invariant under $H$, and each basis operator has only one eigenvalue on it. The Lie theorem triangularizes the action on each block; its diagonal entries therefore give one and the same linear functional $\lambda$ on every basis vector of that block. Every $\rho (h)-\lambda (h)I$ is strictly upper triangular there, proving that the block is $V^{\lambda }$. Distinct blocks have distinct weights, so this is a direct sum. On the zero generalized weight space, every acting operator is a nilpotent endomorphism, so the Engel theorem supplies a nonzero common annihilated vector whenever that space is nonzero.

The Gram-Schmidt process turns a finite ordered family of linearly independent vectors $v_1,\dots ,v_k$ in an inner product space over the real numbers into an orthonormal basis $q_1,\dots ,q_k$ of their linear span. It keeps every successive linear span, so the first $j$ new vectors describe exactly the same directions as the first $j$ inputs. Its idea is geometric: remove the orthogonal projection onto directions already found, then divide the remaining vector by its norm. This makes a complicated basis easier to use without changing the vector subspace it describes.^[ref]

Start with $u_1=v_1$ and $q_1=v_1/\Vert v_1\Vert$. At step $j$, use the previously obtained orthonormal set to defineThe sum is the orthogonal projection onto a finite-dimensional subspace $W_{j-1}=\mathrm{span}(q_1,\dots ,q_{j-1})$, and $u_j$ is the orthogonal projection residual. Linear independence ensures $u_j\ne 0$: otherwise $v_j$ would already be a linear combination of earlier inputs. If the input family is linearly dependent, use only the retained orthonormal vectors in the sum and omit an input whenever its remainder is the zero vector; do not divide by zero. The retained outputs still form an orthonormal basis of the original linear span, but their number can be smaller than $k$.

For a short verification, orthonormality makes every earlier inner product vanish:Also $u_j$ is $v_j$ minus a linear combination of earlier vectors, while $v_j$ is $u_j$ plus that same linear combination. These two inclusions, followed by division by a nonzero norm, giveThe argument also works in an inner product space over the complex numbers with the existing inner product convention, linear in the first argument: the coefficients remain $⟨v_j,q_i⟩$. With the convention linear in the second argument, write $⟨q_i,v_j⟩$ instead.

For a first picture, take $v_1=(1,1{)}^T$ and $v_2=(1,0{)}^T$ in ${\mathbb{R}}^2$ with the ordinary dot product. ThenSubtracting the diagonal component leaves an orthogonal direction; dividing by its norm $1/\sqrt{2}$ makes its length one. If the second input were $(2,2{)}^T$ instead, its orthogonal projection would be the entire input and $u_2=0$, revealing linear dependence.

For a full three-dimensional calculation, use the ordinary dot product and the input vectorsThe first two steps giveAt the third step, the inner products are $⟨v_3,q_1⟩=1/\sqrt{2}$ and $⟨v_3,q_2⟩=1/\sqrt{6}$. ConsequentlyThe three numerator vectors have pairwise dot products $0$ and squared Euclidean norms $2,6,3$. Thus the displayed outputs are indeed an orthonormal basis, and the three nonzero remainders also confirm linear independence of the inputs. Keeping the removed coefficients produces the QR decomposition below.

An immediate reward is a reusable orthogonal projection: once an orthonormal basis of a vector subspace $W$ is known, any vector $b$ hasFor the linear span of just the first two inputs in the three-dimensional example, $b=(0,0,1{)}^T$ gives $P_{W}b=(1/3,-1/3,2/3{)}^T$. Its orthogonal projection residual is $(-1/3,1/3,1/3{)}^T=q_3/\sqrt{3}$, visibly in the missing orthogonal direction. This is the geometry behind the linear least-squares problem.

The formulas above describe exact arithmetic. With floating-point arithmetic, subtracting an orthogonal projection nearly equal to the input can leave a small remainder; dividing by its small norm can magnify existing roundoff error. The Classical Gram-Schmidt and Modified Gram-Schmidt arrangements agree in exact arithmetic but can give different rounded results. Exact linear dependence and a small computed remainder therefore require different judgments in a numerical implementation.^[ref]

A group representation is a group homomorphism from a group to the general linear group of a vector space. It realizes abstract group elements as invertible linear transformations.

The defining identities are $\rho (e)=I$ and $\rho (gh)=\rho (g)\rho (h)$, so an inverse element is represented by a matrix inverse. A choice of basis gives a matrix representation, but the underlying action does not depend on that choice. The action need not distinguish every group element: the trivial representation sends all of them to $I$.

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

A Hermitian form is a sesquilinear form on a complex vector space satisfying conjugate symmetry,Hence $q(v)=H(v,v)$ is a real number for every vector. In a basis, the matrix of a Hermitian form has $A_{ij}=H(e_i,e_j)$ and obeys $A_{ji}=\overline{A_{ij}}$, equivalently $A=A^{\ast }$: it is a Hermitian matrix. The coordinate rule remains $H(x,y)=x^{T}A\overline{y}$. Conjugate symmetry does not imply positivity.^[ref]

The diagonal contains more information than might be expected. For any complex sesquilinear form $B$, put $q(v)=B(v,v)$. Expanding four expressions gives the complex polarization identity in the linear-first convention:This is an algebraic identity, with no positivity assumption. If every $q(v)$ is real, interchanging $u,v$ preserves the first difference and negates the second: use $q(\alpha v)=|\alpha {|}^{2}q(v)$ for $\alpha =-1,i$. The identity then gives $B(v,u)=\overline{B(u,v)}$. Thus a complex sesquilinear form is a Hermitian form if and only if all its diagonal values are real. Testing only the basis vectors is insufficient: the off-diagonal example in sesquilinear form has zero diagonal entries in its matrix but a nonreal value at $(1,i)$.

Consider the indefinite Hermitian formIts values at $e_1,e_2$ are $1,-1$. Moreover $u=(1,1)$ and $v=(1,-1)$ are nonzero isotropic vectors: $q_{-}(u)=q_{-}(v)=0$, yet $H_{-}(u,v)=2$. These vectors do not belong to the radical of a Hermitian form, and the usual Cauchy-Schwarz inequality would incorrectly require $4\le 0$. An indefinite Hermitian form records signed geometry rather than defining a norm by $\sqrt{H(v,v)}$.

There is a separate boundary case: $H_0(z,w)=z_1\overline{w_1}$ is a positive semidefinite Hermitian form, since $H_0(z,z)=|z_1{|}^2\ge 0$, but $H_0(e_2,e_2)=0$. Its radical of a Hermitian form is the entire second coordinate line. Positive definiteness is exactly the additional condition in a Hermitian inner product. The three examples below show why these distinctions matter: on the real slice $z=(x,y)\in {\mathbb{R}}^2\subset {\mathbb{C}}^2$, $q_{+}(z)=|z_1{|}^2+2|z_2{|}^2$ has an ellipse as its unit level, $q_{-}$ has hyperbolas, and $q_0$ has two parallel lines. These are slices of the complex examples, not drawings of their full four-dimensional domains.

Hyperbolic functions combine the exponential function to describe a hyperbola much as trigonometric functions describe a circle. Their two basic members are the hyperbolic cosine and hyperbolic sine, defined for every real number $t$ byTheir derivatives exchange the two functions:These formulas follow by applying differentiation to the exponential function definitions. ^[ref]

Adding and subtracting gives $\cosh t+\sinh t=e^t$ and $\cosh t-\sinh t=e^{-t}$. Multiplying these equalities proves the hyperbolic Pythagorean identity:Consequently the parametric equation $(x,y)=(\cosh t,\sinh t)$ traverses the entire right branch of the unit hyperbola $x^2-y^2=1$, where $x\ge 1$. For example, $t=0$ gives $(1,0)$, while $t=\pm 1$ gives approximately $(1.543,\pm 1.175)$. Compare $(\cos \theta ,\sin \theta )$ on the unit circle, where the squared coordinates add to one. The minus sign changes the geometry from a closed circle to an unbounded hyperbola.

The other members are ratios and reciprocals: hyperbolic tangent is $\tanh t=\sinh t/\cosh t$, hyperbolic cotangent is $\coth t=\cosh t/\sinh t$, and hyperbolic secant is $\mathrm{sech}t=1/\cosh t$; denominators must be nonzero. The hyperbolic sine and hyperbolic cosine both solve the second-order linear differential equation $f^{\prime \prime }=f$. In fact $f(t)=A\cosh t+B\sinh t$ has $f(0)=A$ and $f^{\prime }(0)=B$, making this basis convenient for an initial value problem. Their geometry also makes hyperbolic substitution useful for integrals containing $\sqrt{1+u^2}$, and the hyperbolic cosine gives the physical catenary of a hanging chain.

A hyperbolic plane is a two-dimensional vector space with a quadratic form and a basis $e,f$ satisfying $q(e)=q(f)=0$ and $B(e,f)=1$, where $B$ is the polar bilinear form of a quadratic form. Equivalently, $q(xe+yf)=xy$. This definition also applies in characteristic two. Over the real numbers, the identity $xy=((x+y)/2{)}^2-((x-y)/2{)}^2$ gives one positive and one negative square, hence signature zero. The signature statement is specific to real quadratic forms.