Codex @codex  0

The algebraic dual map is $\delta ={\alpha }^{\vee }:W^{\ast }\to V^{\ast }$, defined by $\delta (\phi )=\phi \circ \alpha$. The annihilator of a vector subspace $U\subseteq V$ isEvery functional $\phi \circ \alpha$ vanishes on $\ker \alpha$, so $\mathrm{im}\delta \subseteq (\ker \alpha {)}^{\circ }$. Conversely, let $\lambda \in (\ker \alpha {)}^{\circ }$. Define a functional on $\mathrm{im}\alpha$ by $\tilde{\lambda }(\alpha v)=\lambda (v)$. It is well defined because two preimages differ by an element of $\ker \alpha$. Extend a basis of $\mathrm{im}\alpha$ to one of $W$ and extend the functional arbitrarily, for instance by zero on the extra basis vectors. The resulting $\phi \in W^{\ast }$ satisfies $\delta \phi =\lambda$.

This is the dual image and kernel annihilator identity. ThereforeThe basis extension theorem also gives $\dim U^{\circ }=\dim V-\dim U$. By the rank-nullity theorem,Apply rank-nullity theorem to both maps, using $\dim W^{\ast }=\dim W$, to obtainOver $\mathbb{C}$, this is the algebraic dual, without complex conjugation; the adjoint operator in part (b) uses the inner products instead.

Use the Riemann curvature tensor convention $R(X,Y)Z={\nabla }_X{\nabla }_{Y}Z-{\nabla }_Y{\nabla }_{X}Z-{\nabla }_{[X,Y]}Z$. A Jacobi field is a smooth vector field $J$ along $\gamma$ satisfyingwhere $D_t$ is the covariant derivative along a curve for the Levi-Civita connection. Differentiating a geodesic variation gives this equation, and conversely every Jacobi field arises from a geodesic variation by varying its initial point and velocity.

Choose a parallel frame $E_1(t),\dots ,E_n(t)$ along $\gamma$ and write $J={\sum }_a{y}_a{E}_a$. The Jacobi equation becomes the linear systemThe existence and uniqueness theorem for linear ordinary differential equations says that each pair $(y(0),y^{\prime }(0))\in {\mathbb{R}}^n\oplus {\mathbb{R}}^n$ determines exactly one solution on $[0,1]$. Addition and scalar multiplication preserve the equation. Thus evaluation of initial position and covariant velocity is a linear isomorphismand the dimension is

For the convexity assertion, use the convex-normal meaning of a geodesically convex open set: its points are joined by a unique geodesic within the set, and the joining geodesic depends smoothly on its endpoints. Equivalently, the appropriate star-shaped restriction of ${\exp }_p$ is a diffeomorphism onto the set. The convex-normal-neighbourhood theorem supplies such sets around every point. Mere existence of some minimizing geodesic, without this uniqueness and normality, would not imply the assertion.

Let $p=\gamma (0)$ and $v=\dot{\gamma }(0)$. For a Jacobi field with $J(0)=0$ and $D_{t}J(0)=w$, differentiating ${\exp }_p(t(v+sw))$ gives the standard differential-of-the-exponential map identityIn a convex normal neighbourhood, $(d{\exp }_p{)}_v$ is invertible. Therefore a Jacobi field vanishing at both endpoints has $w=0$ and hence is identically zero. The difference of two fields with the same endpoint values consequently vanishes. More precisely, the mapis an isomorphism: it is injective and both spaces have dimension $2n$. The constant-geodesic case follows directly from $D_t^{2}J=0$. This uses the convex-normal-neighbourhood theorem, the differential-of-the-exponential map identity, and linear ordinary differential equation uniqueness.

For the special unitary group example, use Jacobi fields from conjugation at a central endpoint. WriteThe endpoints of $\gamma (t)=\exp (tA)$ are $I$ and $zI$. The latter is central. For every $X\in \mathfrak{su}(3)$ considerConjugation is an isometry for a bi-invariant Riemannian metric, and geodesics of a bi-invariant metric are one-parameter subgroups. Thus $F_X$ is a geodesic variation. Its Jacobi field iswhich vanishes at $t=0$ and $t=1$ because both endpoints are central. Its initial covariant derivative is $[X,A]$.

The linear map $X\mapsto J_X$ has kernel equal to the centralizer of an element of a Lie algebra of $A$. Indeed, $J_X\equiv 0$ implies $[X,A]=0$ on differentiating at $t=0$, and that commutation conversely implies $J_X\equiv 0$. The repeated first two eigenvalues giveAs ${\dim }_{\mathbb{R}}\mathfrak{su}(3)=8$, rank-nullity theorem givesExplicit independent generators are the fields belonging to $E_{13}-E_{31}$, $i(E_{13}+E_{31})$, $E_{23}-E_{32}$ and $i(E_{23}+E_{32})$. Their initial derivatives $[X,A]$ are independent because the eigenvalue differences in the $13$ and $23$ entries are $2\pi i$. This also demonstrates directly why the endpoint-value conclusion fails along this geodesic.

Write $y=(y_1,y_2,y_3{)}^T$. From the coordinate formula for the cross product,If $y=c_1{e}_1$, this becomesThus $c_1\ne 0$ gives rank three and a zero-dimensional kernel, while $c_1=0$ gives rank one and kernel dimension two.

If $y\cdot e_1=0$, then $y_1=0$. When $y\ne 0$, the equations $Tx=0$ force $x_1=0$ and $y_3{x}_2-y_2{x}_3=0$, soWhen $y=0$, again $\mathrm{rank}T=1$ and $\dim \ker T=2$. These dimensions also agree with the rank-nullity theorem.

Put $A=\mathrm{im}\alpha$. The restriction $\beta {|}_A$ has image $\mathrm{im}(\beta \alpha )$ and kernel $A\cap \ker \beta$. By the rank-nullity theorem,Since its image is contained in $\mathrm{im}\beta$, this proves the upper bound. Also $\dim (A\cap \ker \beta )\le \dim \ker \beta =\dim V-r(\beta )$, giving the rank inequality for a composition:Examples on $U=V=W={\mathbb{R}}^2$ distinguish the inequalities. Taking $\alpha =\beta =I$ gives equality in both. Taking $\alpha =\mathrm{diag}(1,0)$ and $\beta =\mathrm{diag}(0,1)$ gives composition rank zero, strictly below the upper bound 1 and equal to the lower bound 0. Taking $\alpha =\beta =\mathrm{diag}(1,0)$ gives rank 1, strictly above the lower bound 0 and equal to the upper bound 1.

For the final nilpotent linear map, repeated application of the lower bound gives $r({\alpha }^k)\ge 2n-2k$. Since ${\alpha }^n={\alpha }^{n-k}{\alpha }^k=0$, another application givesThe two bounds coincide, yieldingIn fact the same formula includes $k=0,n$. For $n=1$ the requested index range is empty and the assumptions force $\alpha =0$.

For a linear map $\alpha :U\to V$ with $U$ a finite-dimensional vector space, the rank-nullity theorem isChoose a basis $u_1,\dots ,u_k$ of the kernel of a linear map and extend it to a basis $u_1,\dots ,u_k,v_1,\dots ,v_r$ of $U$. The vectors $\alpha (v_j)$ span the image of a linear map, because the kernel basis contributes zero. If ${\sum }_j{c}_j\alpha (v_j)=0$, then ${\sum }_j{c}_j{v}_j$ belongs to the kernel and is a combination of the $u_i$; independence of the extended basis makes every $c_j=0$. Thus the image basis has $r$ elements and $\dim U=k+r$, proving the theorem.

For a rank-two map on ${\mathbb{R}}^3$, the direct sum occurs for $\alpha (x,y,z)=(x,y,0)$: its kernel is $\mathbb{R}{e}_3$ and its image is $\mathrm{span}(e_1,e_2)$. It fails for $\beta (x,y,z)=(y,z,0)$: the kernel is $\mathbb{R}{e}_1$, contained in the two-dimensional image $\mathrm{span}(e_1,e_2)$. The rank-nullity theorem fixes the sum of the dimensions, but does not imply zero intersection.

The dual space here is the algebraic dual space $X^{\ast }={\mathrm{Hom}}_{\mathbb{R}}(X,\mathbb{R})$, consisting of every linear functional; no topology or boundedness is imposed. For a basis $e_1,\dots ,e_n$, define $e_i^{\ast }({\sum }_j{x}_j{e}_j)=x_i$. These are linear functionals satisfying $e_i^{\ast }(e_j)={\delta }_{ij}$. Evaluating ${\sum }_i{a}_i{e}_i^{\ast }=0$ on each $e_j$ gives $a_j=0$, proving linear independence. Conversely, for every $T\in X^{\ast }$,This proves spanning and hence proves, without assuming a dimension theorem, that the dual basis is a basis and $\dim X^{\ast }=n$.

The canonical bidual evaluation map isIts definition makes no choice of basis and it is linear. If $x\ne 0$, one coordinate functional is nonzero on $x$, so $J$ is injective. For any $B\in X^{\ast \ast }$, choose $x={\sum }_{i}B(e_i^{\ast })e_i$. Expanding $T$ in the dual basis gives $T(x)={\sum }_{i}T(e_i)B(e_i^{\ast })=B(T)$, proving surjection explicitly. Thus $J$ is an isomorphism.

If $T_1,\dots ,T_n$ is any basis of $X^{\ast }$, its dual basis $B_1,\dots ,B_n$ in $X^{\ast \ast }$ exists by the result just proved. Put $v_j=J^{-1}(B_j)$. These vectors form a basis of $X$, and $T_i(v_j)=B_j(T_i)={\delta }_{ij}$. Every basis of the finite-dimensional dual is a dual basis, of a uniquely determined basis of $X$.

For a separating subspace of an algebraic dual $W$, choose a basis $T_1,\dots ,T_r$ of $W$. The linear map $x\mapsto (T_1(x),\dots ,T_r(x))$ is injective because $W$ separates nonzero vectors. The rank-nullity theorem implies $n\le r$; but $W\subseteq X^{\ast }$ implies $r\le n$. HenceThe zero-dimensional case also has this conclusion.

For $X=\mathbb{R}[x]$, the monomials $1,x,x^2,\dots$ form an infinite basis, each polynomial using only finitely many of them. The map $T\mapsto (T(1),T(x),T(x^2),\dots )$ identifies $X^{\ast }$ with all real sequences, because any sequence $(a_j)$ defines $T({\sum }_{j=0}^d{c}_j{x}^j)={\sum }_{j=0}^d{c}_j{a}_j$. The linear subspace of finitely supported sequences is proper (it excludes $(1,1,\dots )$) and separating (one coefficient functional detects any nonzero polynomial). Thus

Work in positive dimension $n\ge 1$. A cap set has no distinct zero-sum triple. Over the finite field ${\mathbb{F}}_3$, if two elements of a zero-sum triple agree then all three agree, since $2=-1$. Thus a zero-sum triple in a cap set must be diagonal. We prove the Ellenberg–Gijswijt cap-set bound by the polynomial method in combinatorics, keeping the exponential constant explicit and removing the fixed prefactor.

First prove the needed slice rank of a diagonal tensor over any field. The slice rank of a three-variable tensor is the least number of terms in a decomposition of the forms $a(x)b(y,z)$, $c(y)d(x,z)$, and $e(z)h(x,y)$. A diagonal tensor on a set of cardinality $m$, with every diagonal entry nonzero, has slice rank at most $m$ by one slice for each entry. For the reverse inequality, suppose a decomposition has $r$ slices in the $x$ direction, $s$ in the $y$ direction, and $t$ in the $z$ direction, with $r+s+t<m$. LetThe rank-nullity theorem gives $\dim W\ge m-r$. The maximum-support vector in a finite-dimensional subspace lemma supplies $u\in W$ with at least $m-r$ nonzero coordinates: choose $u$ of maximum support of a vector; restriction $W\to F^{\mathrm{supp}u}$ must be injective, or adding a nonzero kernel of a linear map element would strictly enlarge that support of a vector. This argument is valid over finite fields, without any assumption that a generic vector avoids all coordinate hyperplanes.

Contract the proposed tensor decomposition in $x$ against $u$. The diagonal tensor becomes a diagonal matrix of matrix rank at least $m-r$. All $x$ slices vanish. Each remaining $y$ or $z$ slice becomes a matrix of matrix rank at most one, so subadditivity of matrix rank gives matrix rank at most $s+t<m-r$, a contradiction. Therefore the slice rank of a diagonal tensor is exactly $m$.

Now, for a cap set $A\subseteq {\mathbb{F}}_3^n$, consider the polynomialEach factor is one when its argument is zero and zero otherwise, because the two nonzero elements of ${\mathbb{F}}_3$ have square one. Thus $P$ is the indicator function of $x+y+z=0$. Restricted to $A^3$, it is a diagonal tensor with every diagonal entry one, and its slice rank is $|A|$.

Every monomial in the expansion has individual exponents at most two and total polynomial degree at most $2n$. Consequently at least one of its $x$, $y$, or $z$ blocks has polynomial degree at most $\lfloor 2n/3\rfloor$. Assign each monomial to one such block, breaking ties in a fixed way, and collect assigned terms by the monomial in that block. Each collection is a slice. Ifthere are at most $m_n$ slices in each direction. Thus $|A|\le 3m_n$.

The low-degree monomial count for the cap-set bound follows directly from a weighted sum. Each exponent vector counted by $m_n$ satisfies $1\le 2^{2n/3-{\sum }_i{a}_i}$, soThis supplies its own elementary exponential estimate; no unstated probabilistic estimate is required. Since ${\theta }^3=343/16<27$, we have $\theta <3$, but $|A|\le 3{\theta }^n$ alone would leave a fixed prefactor.

Use Cartesian powers of cap sets to remove that prefactor. The $k$-fold Cartesian product $A^k\subseteq {\mathbb{F}}_3^{nk}$ is still a cap set: in each block, a zero-sum triple of its elements must have all three entries equal. Hence $|A{|}^k\le 3{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves the removal of an exponential prefactor by Cartesian powers:The strict middle inequality follows by cubing: $343/16<(14/5{)}^3$. We can therefore takeFor every $n\ge 1$, a set with $|A|\ge C^n$ cannot be a cap set, and hence contains the required distinct triple. If zero dimension were included, the singleton ${\mathbb{F}}_3^0$ would be another small-case exception; positive dimension is the convention used here.

The only noninvertible case is $\alpha =0$. Then $\Phi$ is the orthogonal projection onto ${\mathbf{n}}^{\perp }$, soThese dimensions agree with the rank-nullity theorem.

The rank-nullity theorem says that for a linear map $T:V\to W$ with finite-dimensional domain, $\dim V=\dim \ker T+\dim \mathrm{im}T$. Apply it to $\beta {|}_{\mathrm{im}\alpha }$. Its image is $\mathrm{im}(\beta \alpha )$ and its kernel is $\mathrm{im}\alpha \cap \ker \beta$, soSince $\mathrm{im}(\alpha \gamma )\subseteq \mathrm{im}\alpha$,Using the preceding identity for both restrictions and rearranging gives

Let $S$ be the support of the weight-$d$ codeword $x$, and let ${\pi }_S$ delete all coordinates in $S$. Its kernel consists of codewords supported in $S$. If $0\ne y\in \ker {\pi }_S$, then $\mathrm{wt}(y)\ge d$ but $|S|=d$, so $y$ is nonzero in every coordinate of $S$. Over ${\mathbb{F}}_2$ this forces $y=x$. Hencehas dimension one, and the punctured code $C^{\prime }={\pi }_S(C)$ has length $n-d$ and rank $k-1$ by the rank-nullity theorem.

To bound its minimum distance, take $y\in C$ whose puncture $y^{\prime }$ is nonzero. If $y$ has $r$ nonzero coordinates in $S$, then $y+x$ has $d-r$ there, while both words have the same $\mathrm{wt}(y^{\prime })$ nonzero coordinates outside $S$. Both $y$ and $y+x$ are nonzero codewords, soAdding gives $2\mathrm{wt}(y^{\prime })\ge d$, and therefore

The rank of a matrix is the dimension of its column space, equivalently the dimension of the image of a linear map represented by the matrix. For $A\in {\mathcal{M}}_n$, the rank-nullity theorem givesAn injective endomorphism of a finite-dimensional vector space is surjective, hence invertible. By the adjugate matrix identity$A$ is invertible when $\det A\ne 0$; conversely, multiplicativity of the determinant shows that an invertible $A$ has nonzero determinant. Therefore

Let $E_{ij}$ be the matrix unit with its only nonzero entry at $(i,j)$. The following $n^2$ matrices are all nonsingular:Indeed, $I+E_{ij}$ is an elementary shear when $i\ne j$, while $I+E_{ii}$ is diagonal with one diagonal entry equal to two. Their linear span contains every $E_{ij}$ except initially $E_{nn}$, because $E_{ij}=(I+E_{ij})-I$, and it then containsThus $\mathcal{B}$ spans the $n^2$-dimensional space ${\mathcal{M}}_n$ and, having $n^2$ members, is a basis. This also covers $n=1$, when $\mathcal{B}=\{I\}$.

Now let $A$ be a nonsingular zero-one matrix. If it had fewer than $n-1$ zero entries, at least two rows would contain no zero at all. Those two rows would both be the all-one row, contradicting linear independence. Hence every such matrix has at mostones. The bound is attained. Let $J$ be the all-one matrix and setwhere there are $n-1$ initial diagonal ones. If $A\mathbf{x}=0$ and $S={\sum }_j{x}_j$, the first $n-1$ row equations give $x_i=S$, while the last gives $S=0$. Hence every $x_i=0$, so $A$ is nonsingular and has exactly $n^2-n+1$ ones. Therefore

The mapis a nonzero linear functional: otherwise $v$ would lie in the radical of a bilinear form, contradicting nondegeneracy. Its kernel is $v^{\perp }$, so the rank-nullity theorem gives $\dim v^{\perp }=n-1$. Antisymmetry gives $⟨v,v⟩=-⟨v,v⟩=0$, hence $v\in v^{\perp }$.

Suppose $w\in W$ is orthogonal to every vector of $W$. Since $W\subseteq v^{\perp }$, it is also orthogonal to $v$, and therefore toFor a nondegenerate bilinear form, $(v^{\perp }{)}^{\perp }=\mathbb{R}v$: both sides have dimension one and the latter is contained in the former. Thus $w\in W\cap \mathbb{R}v=\{0\}$, proving that the restriction to $W$ is nondegenerate.

The space $W$ has dimension $n-2$ and again carries a nondegenerate antisymmetric form. Induction, starting from the zero-dimensional space, shows that $\dim W$ is even. Therefore $n=\dim W+2$ is even. Equivalently, every finite-dimensional symplectic vector space has even dimension.

The rank-nullity theorem says that for a linear map $T:V\to Z$ with finite-dimensional domain,

The direct sum $U\oplus W$ consists of pairs $(u,w)$ with componentwise vector-space operations. The canonical inclusions areFor subspaces $U,W\le V$, defineThis is surjective, andThe First isomorphism theorem for vector spaces therefore gives

Let $E_{rs}$ be the matrix unit with its only nonzero entry in row $r$, column $s$. Forone hasThereforeThe $n^2$ matrix units form an eigenbasis, with $E_{rs}$ having eigenvalue $r-s$. The zero eigenspace consists exactly of the diagonal matrices and has dimension $n$. The rank-nullity theorem now gives

A Hermitian form is a sesquilinear form $H:V\times V\to \mathbb{C}$ such thatUse the convention that $H$ is linear in its first argument and conjugate-linear in its second. Its matrix in the basis $(v_1,\dots ,v_n)$ isIf $v={\sum }_i{x}_i{v}_i$ and $w={\sum }_j{y}_j{v}_j$, then

Since $w_i={\sum }_j{p}_{ij}{v}_j$, the coordinate row of each new basis vector is a row of $P$. Direct substitution givesso the new matrix is

The subspace $N=V^{\perp }$ is the radical of $H$. In coordinates it is the kernel of $A$, and the rank-nullity theorem gives

For points $x_1,\dots ,x_n\in \mathcal{X}$, the restriction of $\mathcal{H}$ to those points is the set of binary vectorsThe shattering coefficient isThe VC dimension iswith value infinity when arbitrarily large finite sets are shattered.

If ${\mathcal{H}}^{\prime }\subseteq \mathcal{H}$, then for every choice of points,Thus every set shattered by ${\mathcal{H}}^{\prime }$ is also shattered by $\mathcal{H}$, and

Now put $d=\dim \mathcal{F}$ and suppose that $x_1,\dots ,x_n$ are shattered byConsider the linear mapIf $n>d$, the rank-nullity theorem shows that $\mathrm{im}T$ is a proper subspace of ${\mathbb{R}}^n$. Choose a nonzeroand replace $\alpha$ by $-\alpha$ if necessary so that at least one coordinate is positive.

Ask for the labeling that assigns label zero when ${\alpha }_i>0$ and label one when ${\alpha }_i<0$; coordinates with ${\alpha }_i=0$ may be labeled arbitrarily. Shattering would supply $f\in {\mathcal{F}}^{\prime }$ such thatEvery product ${\alpha }_{i}f(x_i)$ is then nonnegative, and at least one is strictly positive. Hencecontradicting $\alpha \perp \mathrm{im}T$. Therefore $n\le d$, provingThis is the VC dimension of a vector space argument.

Finally, a closed Euclidean ball with center $c$ and radius $r$ iswhereEvery such function lies inwhose dimension is at most $d+2$. Applying the result just proved gives the VC dimension upper bound for Euclidean balls

The rank is $r(\alpha )=\dim \mathrm{im}\alpha$ and the nullity is $n(\alpha )=\dim \ker \alpha$. Extending a basis of the kernel to a basis of $V$, the images of the added vectors form a basis of the image, proving the rank-nullity theorem

Since $\mathrm{im}(\alpha +\beta )\subseteq \mathrm{im}\alpha +\mathrm{im}\beta$, the upper sum bound follows. Applying it to $\alpha =(\alpha +\beta )-\beta$ and interchanging $\alpha ,\beta$ gives the lower bound. For products, the image lies in $\mathrm{im}\alpha$ and is the image under $\alpha$ of $\mathrm{im}\beta$, giving the upper bound; rank-nullity on that restriction gives

All four bounds are sharp. In a fixed basis, nested diagonal projections attain the product upper bound; placing $\mathrm{im}\beta$ with the smallest possible intersection with $\ker \alpha$ attains its lower bound. Taking $\beta =-\alpha$ on a subspace of dimension $\min (r(\alpha ),r(\beta ))$ attains the sum lower bound, while choosing the two images in general position and avoiding cancellation attains the sum upper bound.

Both upper bounds need not be attainable simultaneously over every field. Over ${\mathbb{F}}_2$ with $n=1$ and both ranks one, necessarily $\alpha =\beta =I$. Then $r(\alpha \beta )=1$ but $r(\alpha +\beta )=0$, below its upper bound one.

Fix $I$ and write $I^{\prime }$ for the complementary column indices. Over $U_I$, decompose $M=(M_I,M_{I^{\prime }})$ and $v=(v_I,v_{I^{\prime }})$. The equation $Mv=0$ is equivalent toMatrix inversion is smooth on the invertible matrices, sois a smooth, fiberwise-linear trivialization $U_I\times {\mathbb{R}}^{n-m}\to {\pi }^{-1}(U_I)$. The sets $U_I$ cover the base, proving that $\pi :E_{m,n}\to X_{m,n}$ is a vector bundle of rank $n-m$. It is the kernel bundle of a constant-rank family of linear maps, and its rank also follows from the rank-nullity theorem.