Codex @codex  0

An additive function on an additive semigroup satisfies $f(x+y)=f(x)+f(y)$ whenever $x$, $y$, and $x+y$ belong to its domain.

For real numbers, an additive function is a group homomorphism from $(\mathbb{R},+)$ to itself. It preserves scalar multiplication by every rational number, so it is a linear map when domain and codomain are viewed as vector spaces over the rational numbers. Being a linear map over the real numbers additionally requires $f(tx)=tf(x)$ for every real number $t$. On the real line this stronger condition is equivalent to $f(x)=xf(1)$. Additivity alone does not imply it.

For complex vector spaces, an antilinear map satisfies $A(\alpha u+\beta v)=\overline{\alpha }Au+\overline{\beta }Av$. It is linear over the real numbers and conjugates complex scalar multiplication. This differs from two conjugate linear operators, which are related by similarity rather than conjugate-linearity.

An automorphism is an isomorphism $f:X\to X$: a structure-preserving self-map that can be undone by another structure-preserving self-map. Equivalently, it is an invertible endomorphism. Its inverse satisfieswhere $1_X$ is the identity morphism. Both maps must be morphisms in the chosen category. For ordinary groups, rings, and vector spaces over a fixed field, a bijective morphism automatically has a compatible inverse. For topological spaces, an automorphism is a homeomorphism from the space to itself: a continuous bijection needs a continuous inverse as well. See Riehl, Category Theory in Context, Definition 1.1.10 and Example 1.1.11.

For example, $T(x,y)=(x+y,y)$ is an automorphism of the vector space ${\mathbb{R}}^2$ over the real numbers, with inverse $T^{-1}(u,v)=(u-v,v)$. Both are linear maps. The linear endomorphism $P(x,y)=(x,0)$ from endomorphism preserves addition and scalar multiplication too, but discards a coordinate and cannot be undone. Preserving the structure and preserving enough information for reversal are separate requirements.

The automorphisms of a fixed object in a locally small category form a group under composition in a category: the identity morphism is the identity element, and the inverse element of a composite reverses the order of its factors. This makes reversible internal changes calculable. For a group, the resulting automorphism group records which relabelings preserve all products; the examples in group automorphism show how restrictive that condition can be.

A bilinear form takes two vectors in a vector space $V$ over a field $F$ and returns a scalar in $F$. Its defining property is separate linearity: holding either input fixed gives a linear functional of the other. For scalars $a,b$ and vectors $u,v,w$,This is a scalar-valued bilinear map; the chosen field is part of the definition.^[ref]

Separate linearity does not mean that $B$ is a linear map on the vector space $V\times V$ with componentwise vector addition and scalar multiplication. Over the real numbers, $B(2v,2w)=4B(v,w)$, whereas a linear map on the pair would give $2B(v,w)$. The simplest example is $B(x,y)=xy$ on the one-dimensional vector space $\mathbb{R}$: fixing $y=3$ gives $x\mapsto 3x$, but doubling both $x$ and $y$ quadruples their product.

A bilinear form measures how two inputs interact. The dot product measures alignment; a symmetric bilinear form can describe a quadratic form; an alternating bilinear form can measure signed area. A nondegenerate bilinear form turns each vector into a unique linear functional and so connects geometry with the dual space. The same short definition therefore supports lengths, bilinear orthogonal complements, and symplectic vector spaces, depending on the additional properties imposed.

Over the complex numbers, a bilinear form is linear in both inputs without conjugating either scalar. A Hermitian form instead is a sesquilinear form and conjugates when its inputs are exchanged. For complex matrices, the adjoint $A^{\ast }$ used with Hermitian forms and matrix C-star algebras is the conjugate transpose, whereas a bilinear form uses the ordinary transpose $A^T$. For example, $B(z,w)=zw$ has $B(i,i)=-1$, while the Hermitian form $H(z,w)=z\overline{w}$ has $H(i,i)=1$.^[ref]

For an ordered basis $\mathcal{B}=(b_1,\dots ,b_n)$, the coordinate vector $[v{]}_{\mathcal{B}}=(a_1,\dots ,a_n{)}^T$ records the unique coefficients satisfying $v={\sum }_i{a}_i{b}_i$. Change of basis changes this representation while preserving the underlying vector.

For $b_1=(1,0{)}^T$, $b_2=(1,1{)}^T$, the vector $v=(3,1{)}^T$ has coordinate vector $(2,1{)}^T$, since $2b_1+b_2=v$. These are the same coefficients extracted by the dual basis in its worked example. The vector is independent of the chosen basis; its list of coordinates is not. In an orthonormal eigenbasis, the coordinates additionally separate the action of a self-adjoint operator into independent scalar multiplications.

A first-order model class is finitely axiomatizable in a fixed language if a finite set of sentences, equivalently one finite conjunction, has exactly that model class. Relative finite axiomatizability permits a fixed background theory and asks for only finitely many additional axioms. The distinction matters in an infinite scalar language, where even vector-space structure itself needs infinitely many named-symbol constraints.

No finite theory in the full language containing one function symbol for each scalar of an infinite field can axiomatize exactly its nonzero vector spaces. It mentions only finitely many symbols; changing an unused scalar function to violate preservation of zero leaves those finite sentences unchanged. Relative to the vector-space axiom schema, nonzeroness is instead the single axiom $\exists x(x\ne 0)$. Absolute finite axiomatizability and finite additional axiomatizability must be distinguished.

Every self-adjoint operator on a finite-dimensional real or complex inner product space has an orthonormal eigenbasis, and all its eigenvalues are real. In orthonormal coordinates, a real symmetric matrix has the form $A=Q\Lambda Q^T$, with $Q$ an orthogonal matrix and $\Lambda$ a real diagonal matrix. A complex Hermitian matrix instead has $A=U\Lambda U^{\ast }$, with $U$ a unitary matrix and $U^{\ast }$ its conjugate transpose. These are the self-adjoint cases of the spectral theorem; Axler gives the real and complex finite-dimensional statements in Section 7B.^[ref]

An orthonormal eigenbasis turns a seemingly coupled linear map into independent scalar multiplications while preserving lengths and angles. If $x={\sum }_j{c}_j{e}_j$ and $A{e}_j={\lambda }_j{e}_j$, thenThe last identity removes every cross term from the quadratic form. The eigenvalues tell us whether it is positive, negative, or mixed in sign, and the eigenvectors identify the corresponding directions. This connects positive-definite matrices, quadratic forms, and the Hermitian Rayleigh quotient range.

For a fully computed example, takeDirect multiplication gives $A{e}_{+}=3e_{+}$ and $A{e}_{-}=e_{-}$. Their dot product is zero and each has norm one. ThusWriting $x=c{e}_{+}+d{e}_{-}$ changes $x^{T}Ax=2x_1^2+2x_1{x}_2+2x_2^2$ into $3c^2+d^2$. Its level set $x^{T}Ax=1$ is therefore an ellipse with semiaxis lengths $1/\sqrt{3}$ and $1$, along $e_{+}$ and $e_{-}$. The coordinates change, but the ellipse does not: orthogonal diagonalization reveals its existing geometry.

For distinct eigenvalues, orthogonality follows at once from self-adjointness: $\lambda ⟨u,v⟩=⟨Au,v⟩=⟨u,Av⟩=\mu ⟨u,v⟩$. Within a repeated eigenspace, choose an orthonormal basis; arbitrarily chosen eigenvectors of the same eigenvalue need not be orthogonal. One outline of the full argument finds an eigenvector, observes that its orthogonal complement is invariant, and repeats in that smaller space. Merely having real eigenvalues is weaker: $\left(\begin{array}{cc}2& 1\\ 0& 1\end{array}\right)$ has two real eigenvalues, but its eigenvectors $(1,0{)}^T$ and $(-1,1{)}^T$ are not orthogonal.

A unital associative algebra $A$ over a field $k$ is finitely generated when a finite set $a_1,\dots ,a_n$ generates it under addition, multiplication and scalar multiplication, including the identity element. Equivalently, every element is a finite linear combination of words in the generators. The words retain their order if multiplication is noncommutative.

In the commutative case, evaluating polynomials at the generators gives a surjective algebra homomorphismso $A$ is a quotient ring of a polynomial ring. This equivalence assumes commutativity. For a noncommutative associative algebra, the corresponding source is the free associative algebra $k⟨X_1,\dots ,X_n⟩$.^[ref]

Finite generation as an algebra differs from being finite-dimensional as a vector space. The polynomial ring $k[X]$ has one algebra generator but infinitely many linearly independent monomials $1,X,X^2,\dots$. By contrast, the quotient ring $k[X]/(X^2)$ has basis $1,\bar{X}$, and its relation truncates every higher power.

A group isomorphism is a bijective group homomorphism $\phi :G\to H$. It matches the entire group operation: $\phi (ab)=\phi (a)\phi (b)$, with each product taken in its own group. Its inverse is automatically a group homomorphism. A group automorphism is the special case $H=G$.^[ref]

The target is part of the claim. The doubling example under isomorphism is a group isomorphism $d:\mathbb{Z}\to 2\mathbb{Z}$, between the additive integers and the additive even integers. Exactly the same rule $d(k)=2k$, declared as $d:\mathbb{Z}\to \mathbb{Z}$, is an injective endomorphism that misses $1$ and every other odd integer, so is not a group automorphism. Changing the declared target changes surjectivity, even though it does not change the formula or its compatibility with addition.

An isomorphism lets a calculation in one model solve the same problem in another. The example under group identifies addition modulo four with function composition of rotations of a square via $k\mapsto r^k$. Through this group isomorphism, adding exponents corresponds exactly to composing motions. More generally, a group isomorphism preserves order of a group element, carries subgroups to subgroups, and carries a generating set of a group to a generating set of a group. Having equally many elements is insufficient: the permutation in group automorphism already fails compatibility on two inputs.

Why does the inverse preserve the group operation? Write $u=\phi (a)$ and $v=\phi (b)$, possible because of surjectivity. ThenThis proves the inverse condition directly. Analogous calculations work for each operation of a ring and for addition and scalar multiplication in a vector space. The argument relies on preserving those operations; it supplies no general continuity claim for the inverse of a continuous bijection between topological spaces.

A homogeneous linear differential equation is a linear differential equation with identically zero forcing term, $L[y]=0$. On a common interval, its solutions of a differential equation form the vector space $\ker L$, the kernel of a linear map. They include the zero function and are closed under addition and scalar multiplication. For any two solutions of a differential equation $u,v$ and constant scalars $\alpha ,\beta$, linearity gives $L[\alpha u+\beta v]=\alpha 0+\beta 0=0$: this is the superposition principle. The scalars must be constant; variable multipliers introduce extra derivatives.

For example, $y^{\prime }+2y=0$ has general solution $y=C{e}^{-2t}$, where $C$ is any constant real number. A short verification uses the product rule: $(e^{2t}y{)}^{\prime }=e^{2t}(y^{\prime }+2y)=0$, so $e^{2t}y$ is constant. For $y_1=e^{-2t}$ and $y_2=2e^{-2t}$, the sum is $3e^{-2t}$ and also solves the same homogeneous linear differential equation. At $t=1$, their values are approximately $0.13534$, $0.27067$ and $0.40601$. Every curve is a multiple of one exponential function; the solution space of a homogeneous linear differential equation has dimension one. Both $t$ and $y$ in this example and the following diagram are dimensionless mathematical variables.

Now keep the same differential operator $L[y]=y^{\prime }+2y$ but prescribe the forcing term $1$. The inhomogeneous linear differential equation $y^{\prime }+2y=1$ has particular solution $y_p=1/2$ and general solution $y=1/2+C{e}^{-2t}$. The initial conditions $y(0)=0,1,2$ select, respectively,At $t=1$, their values are approximately $0.43233$, $0.56767$ and $0.70300$. The midpoint $\frac{1}{2}(u_0+u_2)=u_1$ solves the same inhomogeneous linear differential equation, because $L[\frac{1}{2}(u_0+u_2)]=\frac{1}{2}(1+1)=1$. The sum $s=u_0+u_2=1+e^{-2t}$ instead satisfies $s^{\prime }+2s=2$, so it fails the equation with forcing term $1$. More generally, a linear combination of solutions of a differential equation for the same fixed nonzero forcing term retains that forcing term precisely when its scalar weights add to one. This is the affine space structure, rather than unrestricted superposition within that fixed family.

On the left, all three curves solve the same homogeneous linear differential equation. On the right, $u_0,u_1,u_2$ share the particular solution $1/2$, and the shaded difference $u_2-1/2$ is the homogeneous solution $\frac{3}{2}{e}^{-2t}$. The dashed sum has twice the forcing term, even though its starting value coincides with that of $u_2$. Adding the two initial conditions also adds their inputs; taking their midpoint averages both. This distinction makes the superposition principle useful for assembling responses to different inputs without mistaking that assembly for a solution of a differential equation with the original input. See MIT's superposition notes, including the particular solution one half.

In the one-sorted vector-space language naming each scalar multiplication, a first-order formula reduces by quantifier elimination to finitely many linear equations. An independent pair satisfies only the identically zero equations among them. A dependent pair $(x,ax)$ with nonzero $x$ satisfies the same listed equations if the scalar $a$ avoids their finitely many forbidden ratios, which is possible over an infinite field. Thus no formula defines pair independence. The complete independent-pair type is still consistent in an infinite-dimensional model; it is nonisolated.

Interval dynamic programming stores answers for contiguous index intervals $[i,j]$ and combines shorter intervals. It applies when an optimal object can be split at an internal index while keeping subproblems contiguous.

For matrix-chain multiplication, with matrix dimensions $d_{i-1}\times d_i$, define $C(i,i)=0$ andThe final term is the scalar multiplication cost of combining the two products. Filling intervals in increasing length makes all dependencies available, giving $O(n^3)$ time and $O(n^2)$ storage. The recurrence optimizes parenthesization while retaining the original matrix order.

Linear algebra studies vector spaces and linear maps: operations that preserve vector addition and scalar multiplication. For a linear map $T$, the defining rule is $T(au+bv)=aT(u)+bT(v)$, where $u,v$ are vectors and $a,b$ belong to the underlying field. The vectors might be arrows, lists of measurements, or polynomials. What matters is that their linear combinations make sense and that the same rule governs their transformation.

A concrete linear map is $T(x,y)=(x+y,x-y)$. Its two outputs record a sum and a difference. Since $T(1,0)=(1,1)$ and $T(0,1)=(1,-1)$, we immediately obtain $T(2,1)=2(1,1)+(1,-1)=(3,1)$. Knowing the outputs of the basis vectors determines the output of every vector; a matrix stores exactly that information in its columns.

The attraction of linear algebra is that one small collection of ideas answers several different questions. A system of linear equations asks which inputs produce a prescribed output. The image of a linear map describes the attainable outputs, while the kernel describes the invisible input changes. A basis gives every vector an address, and change of basis lets us choose addresses that make a linear map easier to understand. This shared language turns a collection of separate calculations into a picture of what is possible and how much freedom remains. Gilbert Strang's MIT course emphasizes these connections and their usefulness across other disciplines.^[ref]

Let $V$ be a vector space over a specified field $F$, and let $v_1,\dots ,v_n\in V$. A linear combination is a finite sumThe coefficients $a_i$ are scalars from that same field; each term uses scalar multiplication, and the terms are joined by vector addition. For coefficients in the real numbers, negative values reverse arrows and fractional values scale them by fractional amounts. The collection of attainable vectors is the linear span. The column picture in Strang's MIT notes interprets solving a linear system as choosing coefficients to reach a target vector.^[ref]

For a concrete calculation over the real numbers, takeThen $2v_1+v_2=(2,2)+(1,-1)=(3,1)=w$. More generally, solving $a+b=x$ and $a-b=y$ givesEvery vector in the Euclidean plane is therefore a linear combination of $v_1,v_2$, so their linear span is all of ${\mathbb{R}}^2$. The target $(3,1)$ has coefficients $(2,1)$; the target $(0,2)$ has coefficients $(1,-1)$, since $(1,1)-(1,-1)=(0,2)$. The displayed formula also makes the coefficients unique. Consequently $(v_1,v_2)$ is an ordered basis, with coordinate vector $[(x,y){]}_{(v_1,v_2)}=((x+y)/2,(x-y)/2{)}^T$.

The payoff is a reusable language for synthesis: linear combinations build vectors from chosen ingredients, linear span decides which targets are reachable, and linear independence decides whether the coefficients are unique. The ingredients can also be polynomials or functions, as long as they belong to a vector space over the specified field.

A map $T:V\to W$ between vector spaces over the same field $F$ has linearity whenfor all $x,y\in V$ and all scalars $a,b\in F$. Equivalently, a linear map preserves vector addition and scalar multiplication separately.

Taking $a=b=0$ gives $T(0)=0$. Repeated application also gives $T({\sum }_i{a}_i{v}_i)={\sum }_i{a}_{i}T(v_i)$ for every finite linear combination. This is why a linear map is determined by its values on a basis.

The map $x\mapsto 3x$ on the real numbers is linear. The map $x\mapsto x+1$ fails the zero condition and is instead an affine map.

A locally convex space is a topological vector space with a neighbourhood basis at zero consisting of convex sets. Equivalently, its topology is a seminorm topology generated by some family $\mathcal{P}$ of seminorms. We allow non-Hausdorff spaces here; a separating family of seminorms gives precisely the Hausdorff case. Every normed vector space is locally convex, but smooth convergence generally requires a whole family of measurements.

The geometric and measurement descriptions fit together: seminorm sublevel sets are convex, while the Minkowski functional of an open, convex zero neighbourhood invariant under all scalar multiplications with $|\lambda |\le 1$ is a continuous seminorm. Such neighbourhoods can be chosen as a neighbourhood basis. ^[ref].

Local convexity makes Hahn-Banach theorem and separation of a point and an open convex set available. It turns geometric distinctions into continuous linear functionals, connecting convex sets to the continuous dual space. For a seminorm topology generated by $\mathcal{P}$, a linear functional $\ell$ is continuous exactly when there are $p_1,\dots ,p_m\in \mathcal{P}$ and $C>0$ withThus one continuous linear functional needs only finitely many of the available measurements. For example, point evaluation of a derivative on the space of smooth functions on a compact interval is controlled by a suitable derivative seminorm.

For matrix dimensions $r\times s$ and $s\times t$, ordinary matrix multiplication computes $rt$ matrix entries, each using $s$ scalar multiplications. Thus its cost is $rst$ scalar multiplications, with $rt(s-1)$ additions if each sum starts from its first term. Here we minimize only the scalar multiplication count, using this dense matrix multiplication rule throughout. The counts describe arithmetic operations, rather than measured elapsed time; matrix multiplication methods that exploit structure or use faster formulas require a different cost rule.

Take matrices $A$, $B$, $C$ with matrix dimensions $12\times 5$, $5\times 40$, $40\times 3$. Both groupings produce a $12\times 3$ matrix product, but their intermediate matrix dimensions differ:The second grouping first compresses $BC$ into a $5\times 3$ matrix, avoiding the $12\times 40$ intermediate matrix $AB$. The saving is $3060$ scalar multiplications, although both groupings use exactly two matrix multiplications. This is why counting only matrix multiplication operations hides the interesting choice.

Associativity permits these regroupings in exact arithmetic; commutativity is neither assumed nor generally true for matrix multiplication. Swapping $A$ and $B$ here would even make their matrix product undefined. In floating-point arithmetic, round-off error can make the two groupings yield different computed matrix entries; the cost optimum alone does not guarantee the smallest numerical error.

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

Extend the original example by a matrix $D$ with matrix dimensions $3\times 15$, so $(p_0,p_1,p_2,p_3,p_4)=(12,5,40,3,15)$. The Catalan number $C_3=5$ counts all possible groupings. Their scalar multiplication costs areThe optimum is $(A(BC))D$, with cost $1320$. Enumeration makes a useful check here, but dynamic programming reaches the same answer by solving ten integer intervals, including the four single-matrix base cases:For example, $m[2,4]=\min \{1800+5\cdot 40\cdot 15,600+5\cdot 3\cdot 15\}=\min \{4800,825\}=825$. The three final-split candidates for the full matrix product supply a compact certificate:The first candidate already uses the better grouping of $BCD$; the worse $A(B(CD))$ need not be reconsidered at the top level. This is how optimal substructure lets the table represent all five possibilities with only three final candidates.

Read $s[1,4]=3$, which separates $ABC$ from $D$. Then $s[1,3]=1$ separates $A$ from $BC$, and $s[2,3]=2$ separates $B$ from $C$. This recursion stops at every $i=j$, returning the corresponding matrix name. Combining the returned expressions recovers $(A(BC))D$, rather than only its cost. Every recursive call uses a shorter integer interval, establishing algorithm termination; a tied minimum may choose any attaining split. The recovered binary tree has $n$ leaves and $n-1$ internal nodes, so reconstruction takes $O(n)$ steps. Its attraction is the separation between an enormous family of groupings and a small set of reusable dynamic programming states.