Describe spaces through linear measurements

Try

A sensor measuring x−2y on a vector (x,y) is a linear functional: it turns a vector into a scalar while respecting addition and scaling. Two independent sensors can describe a vector completely. For the basis b₁=(1,1), b₂=(1,−1), solve (x,y)=a b₁+b b₂ to obtain a=(x+y)/2 and b=(x−y)/2. These two coordinate measurements form the dual basis. Evaluate each measurement on both basis vectors before introducing any abstract notation.

Predict

Predict the measurements that vanish on the line U=span((1,1)). A functional ax+by vanishes on every (t,t) precisely when a+b=0. Thus every such functional is a multiple of x−y. The line of invisible vectors and the line of measurements annihilating it live in different spaces. Without an inner product, drawing both as arrows and calling them perpendicular introduces extra structure that has not been given.

Experiment

Make a table with columns b₁,b₂ and rows f₁=(x+y)/2,f₂=(x−y)/2. The four entries are 1,0,0,1. Change the vector to (6,2), whose measurement pair is (4,2), and reconstruct it as 4b₁+2b₂. Now discard the second measurement. Describe the full set of vectors consistent with f₁=4. This exercise connects a dual coordinate with information loss: one scalar measurement leaves an affine family of possible vectors.

Understand

The algebraic dual V* is the vector space of linear maps V→F. Given a basis v₁,…,vₙ, its dual basis f₁,…,fₙ is defined by fᵢ(vⱼ)=δᵢⱼ, where δ is one for equal indices and zero otherwise. Every functional f equals the sum of f(vᵢ)fᵢ, because both sides agree on a basis. Therefore dim V*=dim V in finite dimension. For U⊆V, the annihilator U⁰ consists of functionals vanishing on U. Extend a basis of U to V; the dual functionals associated with the added vectors form a basis of U⁰. This proves dim U⁰=dim V−dim U without using orthogonality.

Apply

A map T:V→W pulls measurements backward: its dual map T*:W*→V* sends f to f∘T. If A represents T in chosen bases, Aᵀ represents this map in the corresponding dual bases. Check the entry identity by evaluating a pulled-back coordinate functional on a domain basis vector. Furthermore, ker T*=(im T)⁰, since a pulled-back functional is zero precisely when it vanishes on all outputs. Hence rank T*=rank T by rank-nullity and the annihilator formula. This is a conceptual proof of equality of row and column rank. For complex spaces the transpose here remains ordinary transpose: the functionals are linear, and conjugation has not entered.

As a second annihilator example in R³, let U be the plane x+2y−z=0. Its annihilator is the line spanned by the functional x+2y−z. Check that any other functional vanishing on U is its scalar multiple by solving for z=x+2y and substituting. This calculation gives an explicit algebraic alternative to an orthogonal-vector picture.

More measurements than polynomial coefficients

Six observations at nodes 0,1,2,3,4,5 claim values 0,1,4,9,16,26. Could they come from a quadratic? The first three determine p(x)=x², which predicts25 at the last node. A dual certificate gives a second explanation without solving every coefficient: weights (−6,15,−10,0,0,1) annihilate the values of 1, x and x² at these nodes. They therefore annihilate every quadratic evaluation vector. Applied to the claimed values they give1, proving incompatibility. This functional lives in the dual of the observation space; it does not need an inner product.

Too many observations: find the inconsistent relation

Predict which observation cannot match a degree-bounded polynomial. Fit only the first d+1 values, then test every extra observation with an annihilating linear functional. The proposed repair preserves those first observations; it is not a least-squares fit.

Observation count 468 Degree cap d 0123 Original observations j²0, 1 alternating Added last-observation fault 01

Rank 3; annihilator dimension 3. A nonzero certificate proves these observations are outside the image. Showing the original observed vector.

Prefix Newton coefficients Δᵏy₀: 0, 1, 2. These multiply the polynomials binomial(x,k), not monomials.

Node	Original value	Displayed value	Prefix prediction
0	0	0	0
1	1	1	1
2	4	4	4
3	9	9	9
4	16	16	16
5	26	26	25

Extra node	Integer certificate row	Monomial moments	Observed residual
3	-1, 3, -3, 1, 0, 0	0, 0, 0	0
4	-3, 8, -6, 0, 1, 0	0, 0, 0	0
5	-6, 15, -10, 0, 0, 1	0, 0, 0	1

Use prefix-polynomial repair Reset

At most eight nodes, four polynomial coefficients and seven integer certificate rows are used. All certificate arithmetic is exact for these bounded integers. State is temporary and awards no mastery.

Construct a complete family of certificates

Let r distinct field nodes x₁,…,xᵣ be sampled, and let 0≤d<r. Evaluation E:P_d→Fʳ is injective: a nonzero degree-at-most-d polynomial cannot have d+1 distinct roots. Thus rank E=d+1 and its image annihilator has dimension r−d−1. The earlier interpolation lesson covers the complementary regime with enough polynomial coefficients to hit arbitrary data. Here extra observations impose genuine constraints.

For any d+2 chosen nodes, define cᵢ=1 divided by the product of xᵢ−xⱼ over the other chosen nodes. Every denominator is nonzero. Lagrange interpolation at these nodes represents a polynomial p of degree at most d as a sum of p(xᵢ) times degree-d+1 Lagrange basis polynomials. Compare the coefficient of x^(d+1): the left side has zero coefficient, while the right side has Σcᵢp(xᵢ). Therefore this linear combination is zero. Multiplying all cᵢ by a common nonzero scalar preserves the certificate; the inspector clears denominators to small integer rows.

To obtain every constraint, fix the first d+1 nodes as anchors. For each additional node, use those anchors and that node to make one certificate, putting zero weights at all other observations. These r−d−1 rows are independent: each has a nonzero coefficient at its own extra node and zero at the other extra nodes. By the dimension formula they form a basis of the image annihilator. There is also a constructive sufficiency proof. Let p be the unique degree-at-most-d interpolant through the anchors. Subtract its evaluation vector from the observed vector. The anchor differences vanish, so each certificate reduces to a nonzero multiple of its own extra-node discrepancy. All certificates vanish exactly when every discrepancy is zero. Thus they decide image membership, rather than merely supplying some necessary conditions.

If r=d+1, there are no extra constraints and interpolation reaches every observation vector. A successful fit then does not establish a lower-degree mechanism or validate a noisy measurement model. Choosing a prefix repair also differs from least squares: it deliberately preserves the anchor data and replaces the remaining values.

Why alternating real data force high degree

For r≥2 real increasing nodes with values alternating 0 and 1, p−1/2 changes sign between every consecutive pair. The intermediate value theorem supplies a distinct root in each of the r−1 disjoint open gaps, so degree p≥r−1. Lagrange interpolation achieves degree at most r−1, proving that the minimum degree is exactly r−1. This sign argument is specific to ordered real nodes; do not transfer it to arbitrary fields.

On equally spaced integer nodes the same obstruction is visible in forward differences. Define Δyⱼ=yⱼ₊₁−yⱼ. The Newton basis binomial(x,k)=x(x−1)…(x−k+1)/k! satisfies Δ binomial(x,k)=binomial(x,k−1) for k≥1, with Δ1=0. The degree-d prefix interpolant is Σ from k=0 to d of Δᵏy₀ times binomial(x,k): applying successive differences at zero identifies these coefficients, and the triangular evaluation matrix has diagonal ones. Consequently degree-d data have vanishing differences of order d+1. For alternating values beginning with zero, Δᵏy₀=(−1)^(k+1)2^(k−1) for k≥1, never zero over R. The general-node certificate and the equally spaced difference test are two forms of the same missing-image information.

For a nearby changed case, use nodes0,1,3,4 and degree two. The certificate row (−1,2,−2,1) annihilates the three monomials. Data0,1,9,17 give residual1 and cannot be quadratic; changing the last value to16 repairs them. Uniform-grid forward-difference weights would be inappropriate here, even though the polynomial degree is unchanged.

Return to polynomial evaluation kernels and interpolation fibers for the factor theorem and Lagrange construction. Record the certificate’s zero monomial moments before interpreting its observed residual. A nonzero residual proves exact incompatibility, not which physical sensor is wrong or what statistical correction is best.

Continue

An inner product will later identify vectors with certain functionals and define an adjoint. Keep those constructions distinct from the algebraic dual. In this unit the star in this lesson denotes the dual map; later an explicitly named adjoint uses the same conventional symbol with a different domain and additional structure. The next lesson returns to endomorphisms, maps V→V, and asks which subspaces retain their identity under repeated application. All dimension arguments here assume finite dimension.

Review Linear Algebra I when a prerequisite needs practice. Continue to Read an operator through preserved subspaces.