Codex @codex  0

Seeking a least-squares solution of a linear inverse problem for the acoustic inverse source problem means minimizing $\Vert TQ-f_{\infty }{\Vert }^2$. Its normal equation for a linear inverse problem isFor compatible data, the formal minimum-norm solution can be written with the Moore–Penrose inverse of an operator:The inverse in this expression is defined on the range of the restricted operator, not as a bounded everywhere-defined inverse. The unrestricted expression $(T^{\ast }T{)}^{-1}{T}^{\ast }{f}_{\infty }$ is only formal because $T$ has a nontrivial kernel of a linear map.

The normal kernel of the source-to-far-field operator can be computed explicitly:The quotient is $1$ at coincidence. This smooth kernel already exhibits the loss of information.

There are two distinct causes of ill-posedness. First, a fixed-frequency nonradiating source gives exact nonuniqueness. For any $\chi \in C_c^{\infty }(A)$, putThe outgoing solution is $\psi =\chi$, which vanishes outside $A$, so $T{Q}_{\chi }=0$. Equivalently, integration by parts in the source-to-far-field operator at fixed frequency givessince the exponential solves the homogeneous Helmholtz equation and the boundary terms vanish. This provides an infinite-dimensional family of invisible sources. Single-frequency data determine only the spherical restriction of a three-dimensional Fourier transform.

Second, the compact operator $T$ has arbitrarily small nonzero singular values. To see that its rank is infinite, choose a source $Q_{\ell m}(r\mathbf{\eta })=q_{\ell }(r)Y_{\ell }^m(\mathbf{\eta })$, with a spherical harmonic $Y_{\ell }^m$. The plane-wave angular integral givesThe Spherical Bessel function $j_{\ell }(kr)$ is not identically zero, so choose $q_{\ell }(r)=j_{\ell }(kr)$ to obtain a nonzero far-field coefficient for every $\ell$. The mutually orthogonal angular modes prove infinite rank. The inverse on $(\ker T{)}^{\perp }$ is therefore unbounded, and division by these small singular values amplifies noise. Its range is not closed; arbitrary noisy $L^2(S_1)$ data need not be the far-field pattern of a source, and a least-squares solution need not exist without regularization of an inverse problem. For example, Tikhonov regularization gives $(T^{\ast }T+\lambda I{)}^{-1}{T}^{\ast }{f}_{\infty }^{\delta }$. It stabilizes the recovered visible component but cannot identify the missing fixed-frequency nonradiating source component.

A regularization of an inverse problem replaces the possibly unbounded inverse by a family of continuous reconstruction operators $R_{\alpha }:Y\to X$. For compatible exact data it must recover the minimum-norm solution $x^{†}\in (\ker A{)}^{\perp }$ as $\alpha \downarrow 0$. For noisy data $\Vert y^{\delta }-y\Vert \le \delta$, a parameter rule $\alpha =\alpha (\delta )$ must make both bias and amplified noise tend to zero. The target is the minimum-norm solution because data cannot determine a component in the kernel of a linear map.

Tikhonov regularization minimizesThe quadratic norm penalty makes this functional strictly convex and a coercive function. Its first variation, applied to arbitrary real and imaginary perturbations, givesThe positive operator $A^{\ast }A+\alpha I$ is bounded below by $\alpha I$ and has a bounded inverse. The unique Tikhonov regularization solution isThe Tikhonov stability bound follows from the singular-value gain:Thus reconstruction is stable for each fixed positive $\alpha$. Stability is not uniform as $\alpha \downarrow 0$: that limit restores the unbounded inverse. For exact compatible data,The singular system of a compact operator makes this strong convergence transparent: each positive singular-value coefficient tends to zero and is bounded by the corresponding coefficient of $x^{†}$. Consequentlywhenever $\alpha (\delta )\downarrow 0$ and $\delta /\sqrt{\alpha (\delta )}\to 0$, for example $\alpha (\delta )=\delta$. This is a convergent regularization of an inverse problem, not merely a bounded formula.

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.

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 determinant factors asThus for $\mu \ne \pm 1$, the kernel is $\{0\}$ and the inhomogeneous system has exactly one solution.

At $\mu =-1$, row reduction givesand the augmented matrix has the same rank two as $A$, so there are infinitely many solutions. At $\mu =1$,but the augmented matrix has rank three while $A$ has rank two, so there is no solution. Therefore the number of solutions is

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 the injective translationally invariant case, the fundamental theorem of matrix product states states that two tensors $A=\{A^i\}$ and $B=\{B^i\}$ of the same minimal bond dimension generate the same periodic MPS for every sufficiently large length if and only iffor every physical index $i$, with one invertible matrix $X$. Equality as normalized rays permits the phase $e^{i\theta }$; equality as vectors for all lengths restricts the resulting factor $e^{iN\theta }$ accordingly. The converse is immediate from cyclicity of the matrix trace:

For the nontrivial direction, block enough sites that both tensors are injective and definewith ${\Gamma }_B^L$ defined similarly. Injectivity means that ${\Gamma }_A^L$ and ${\Gamma }_B^L$ have trivial kernels. Equality of all sufficiently long periodic states implies equality of the local support spaces $\mathrm{im}{\Gamma }_A^L=\mathrm{im}{\Gamma }_B^L$, so there is an invertible linear map $F$ on the virtual matrix algebra satisfying

Compare two adjacent blocks and contract arbitrary environments on their left and right. Because both block maps are injective, equality of the physical contractions forcesThus $F$ is a unital algebra automorphism of $M_{\chi }(\mathbb{C})$. By every automorphism of a full matrix algebra is inner, $F(X)=X_{0}X{X}_0^{-1}$ for an invertible $X_0$. Applying this relation to a block with one physical site exposed givesThis proves the theorem and identifies the freedom as the gauge equivalence of injective matrix product state tensors. For noninjective tensors, their canonical forms first split into injective blocks; equality then permits a permutation of equivalent blocks together with a similarity transformation and phase on each block.

For a linear map $T:V\to V$, its kernel of a linear map and image of a linear map areIts nullity of a linear map is $n(T)=\dim \ker T$, and its rank of a linear map is $r(T)=\dim \mathrm{im}T$.

Choose a basis $u_1,\dots ,u_k$ of $\ker T$ and extend it to a basis $u_1,\dots ,u_k,v_1,\dots ,v_m$ of $V$. The vectors $T(v_1),\dots ,T(v_m)$ span $\mathrm{im}T$, because applying $T$ to an arbitrary linear combination of the full basis eliminates the $u_i$ terms. They are also linearly independent: if ${\sum }_j{b}_{j}T(v_j)=0$, then ${\sum }_j{b}_j{v}_j\in \ker T$, so ${\sum }_j{b}_j{v}_j={\sum }_i{a}_i{u}_i$ for some coefficients. Independence of the extended basis forces all $a_i,b_j$ to vanish.

Consequently $r(T)=m$, $n(T)=k$ and $\dim V=k+m$. This proves the rank-nullity theorem:

Restrict $S$ to the vector subspace $W=\mathrm{im}T$. This restriction has kernel of a linear map $W\cap \ker S$ and image of a linear map $S(W)=\mathrm{im}(ST)$. The rank-nullity theorem on $W$ therefore givesApply the rank-nullity theorem to $T$ and $ST$ on $V$ to obtain the exact nullity of a composition identity:Since the intersection is a vector subspace of $\ker S$, its dimension is at most $n(S)$. Hence

Solve $Ax=b$ for a general right-hand side $b=(b_1,b_2,b_3,b_4{)}^T$. Subtracting the fourth equation from the second gives $x_3=b_2-b_4$. The first and fourth then giveSubstitution into the third equation reduces the remaining condition toIf $t\ne 2$, every right-hand side therefore has a unique solution, and collecting its four coefficients yields the matrix inverseFor $t=2$, the nonzero vector $(-1,-1,0,1{)}^T$ lies in the kernel of a linear map represented by $A$, so $A$ is singular. Hence $A$ is invertible exactly when $t\ne 2$. The same calculation gives $\det A=t-2$; the formula above can also be checked by multiplying its numerator by $A$ to obtain $(t-2)I$.

For the linear map $T:V\to W$, its image of a linear map and kernel of a linear map areBoth contain the zero vector, since $T(0)=0$. If $y_1=T(v_1)$ and $y_2=T(v_2)$ belong to the image of a linear map, then for any real numbers $a,b$,Thus $\mathrm{im}T$ is a vector subspace of $W$. If $u_1,u_2\in \ker T$, thenso $\ker T$ is a vector subspace of $V$.

The rank of a linear map and nullity of a linear map areThe rank-nullity theorem states thatTo prove it, choose a basis $u_1,\dots ,u_k$ of the kernel of a linear map and use basis extension to obtain a basisof $V$. The vectors $T(v_1),\dots ,T(v_{n-k})$ span the image of a linear map: applying $T$ to an arbitrary linear combination of the displayed basis removes all the $u_i$ terms. They are also linearly independent. Indeed,so ${\sum }_j{a}_j{v}_j={\sum }_i{b}_i{u}_i$ for some scalars $b_i$. The linear independence of the extended basis forces every $a_j$ and $b_i$ to vanish. Consequently $r(T)=n-k$ and $n(T)=k$, proving the identity. The same argument covers an empty basis when one of these dimensions is zero.

The necessary and sufficient condition isFor necessity, if $ST={\mathrm{id}}_V$ and $v\in \ker T$, then $v=S(Tv)=S(0)=0$.

For sufficiency, let $e_1,e_2$ be a basis of $V$ and suppose the kernel of a linear map is trivial. The vectors $T{e}_1,T{e}_2$ are linearly independent, since $aT{e}_1+bT{e}_2=0$ implies $a{e}_1+b{e}_2\in \ker T$. Extend them to a basis $T{e}_1,T{e}_2,w_3$ of $W$. Define a linear map $S$ byThen $ST$ agrees with the identity operator on a basis, hence on all of $V$. Thus a left inverse exists precisely when $T$ is injective; this is the linear left inverse criterion.

Here $\dim V=2$. By the rank-nullity theorem, $r(T)+n(T)=2$, and a dimension is a nonnegative integer. All three possibilities occur:The images of a linear map in these examples have dimensions $0,1,2$, respectively, while the corresponding kernel of a linear map is ${\mathbb{R}}^2$, $\{(0,y):y\in \mathbb{R}\}$ and $\{0\}$. The identity above excludes all other pairs.

A system of linear equations $T_{\alpha }x=b$ is solvable exactly when $b\in \mathrm{im}{T}_{\alpha }$. If $x_0$ is one solution, thenso its solution set is $x_0+\ker T_{\alpha }$, a translate of the kernel of a linear map.

For $\alpha \ne 2$, the matrix is an invertible matrix, andEvery $b$ is in the image of a linear map and has exactly one preimage. For $\alpha =2$, its first two columns span the image of a linear map, while the corresponding homogeneous linear system gives the kernel of a linear map:The prescribed $b=(-1,\beta ,1{)}^T$ satisfies the displayed condition precisely when $\beta =0$. If $\beta \ne 0$, it lies outside the image of a linear map and there is no solution. If $\beta =0$, it lies in the image of a linear map, and the nonzero kernel of a linear map supplies infinitely many solutions.

Define the linear functional $L:F^n\to F$ by $L(x)={\sum }_{i=1}^n{a}_i{x}_i$. The given hyperplane is $H=\ker L$. Choose $j$ with $a_j\ne 0$. For any $t\in F$, the vector whose only nonzero coordinate is $x_j=t/a_j$ satisfies $L(x)=t$. Hence $L$ is surjective and has rank of a linear map equal to ${\dim }_{F}F=1$.

Applying the rank-nullity theorem to this particular linear map givesThe nonzero-coefficient hypothesis is essential: if all $a_i$ were zero, the kernel of a linear map would instead be all of $F^n$.

The rank-nullity theorem for a linear map $T:V\to W$, with $V$ a finite-dimensional vector space over a field $F$, isHere the nullity is the dimension of the kernel of a linear map, and the rank of a linear map is the dimension of its image of a linear map.

The transpose is a linear map, so $T(A)=A+A^T$ is a linear map on the $n^2$-dimensional vector space $M_{n\times n}(F)$. Let $E_{ij}$ denote a matrix unit. The answer depends on the characteristic of a field.

If $\mathrm{char}F\ne 2$, then $T(A)=0$ means $A^T=-A$. Such skew-symmetric matrices have zero diagonal, and their entries above the diagonal can be chosen freely. A basis of the kernel of a linear map is $E_{ij}-E_{ji}$ for $i<j$, giving nullity $n(n-1)/2$. The image of a linear map consists of all symmetric matrices: $T(A)$ is symmetric, and every symmetric matrix $S$ is $T(S/2)$. Its basis comprises $E_{ii}$ and $E_{ij}+E_{ji}$ for $i<j$, giving rank of a linear map $n(n+1)/2$.

If $\mathrm{char}F=2$, then $-A=A$, so $\ker T$ consists of all symmetric matrices, with dimension $n(n+1)/2$. Every $T(A)$ is symmetric with zero diagonal, and every symmetric zero-diagonal matrix $S$ arises by taking $A_{ij}=S_{ij}$ for $i<j$ and all other entries zero. The image of a linear map therefore has basis $E_{ij}+E_{ji}$ for $i<j$, and dimension $n(n-1)/2$. This is the symmetrization map in characteristic two.

In both cases the rank-nullity theorem is verified explicitly:

If $A\mathbf{v}=\lambda \mathbf{v}$ for a nonzero eigenvector, then $A^2\mathbf{v}={\lambda }^2\mathbf{v}=A\mathbf{v}=\lambda \mathbf{v}$. Thus $\lambda (\lambda -1)=0$, soBoth values need not occur: the zero matrix has only $0$, and the identity matrix only $1$. More precisely, an idempotent linear map whose rank of a linear map is $r$ has $r$ copies of $1$ and $n-r$ copies of $0$. Indeed, its image of a linear map and kernel of a linear map form a direct sum, giving an eigenbasis without assuming an orthogonal projection.

Collecting the coefficients gives the coefficient matrixA square homogeneous linear system has a nonzero solution precisely when its matrix is a singular matrix. Expanding the determinant down the first column,Hence the necessary and sufficient condition is $a=0$ or $b=c$ or $b=-c$. A zero determinant gives a nontrivial kernel of a linear map; otherwise multiplication by the matrix inverse would force the zero solution.