Proofs and Problem Solving

Definition Let $V$ be a vector space over $\mathbb{F}$, let $W$ be a subspace and let $q \colon V \to V/W$, $q(v) = v + W$, be the quotient map. A functional $\ell \in V^{\vee}$ descends to $V/W$ if $\ell = \varphi \circ q$ for some $\varphi \in (V/W)^{\vee}$, that is, if the rule $\varphi(v + W) = \ell(v)$ defines a functional on the quotient. The theorem says that the dual map

is injective and that its image is the annihilator $W^{0}$. So a functional descends exactly when it vanishes on $W$, and

The dual map is linear. It is injective because $q$ is onto, so $\varphi \circ q = 0$ forces $\varphi$ to vanish on every coset. Its image lies in $W^{0}$ because $q(w) = 0 + W$ for $w \in W$. It reaches all of $W^{0}$ because a functional $\ell$ that vanishes on $W$ satisfies $\ell(v + w) = \ell(v)$ for every $w \in W$, so $\varphi(v + W) = \ell(v)$ does not depend on the representative. This $\varphi$ is linear because the quotient operations are computed on representatives, and $\varphi \circ q = \ell$. No finite dimension and no inner product are used. When $V$ is finite-dimensional, $\dim (V/W)^{\vee} = \dim V - \dim W$. The identification is with functionals that vanish on $W$, not with vectors perpendicular to $W$, which would need an inner product.

Definition A matrix $A \in \mathbb{C}^{n \times n}$ is normal if

The complex spectral theorem says that $\mathbb{C}^n$ has an orthonormal basis of eigenvectors of $A$, equivalently $A = QDQ^{*}$ with $Q$ unitary and $D$ diagonal, exactly when $A$ is normal. The normality test computes both products before the theorem is used. If they differ, no orthonormal eigenbasis exists, although $A$ may still have an eigenbasis that is not orthogonal. That second question is decided separately. The matrix $A$ is diagonalizable over $\mathbb{C}$ exactly when the dimensions of its eigenspaces add up to $n$, equivalently when $\mu_A$ has no repeated roots. Schur’s theorem gives every complex square matrix a unitary triangularization $A = QTQ^{*}$ with $T$ upper triangular, but $T$ is diagonal only when $A$ is normal. Hermitian, skew-Hermitian and unitary matrices are normal. For a real matrix and a real orthonormal eigenbasis the condition is $A^{\mathsf{T}} = A$.

Definition Let $A \in \mathbb{F}^{n \times n}$ and suppose $\chi_A$ splits into linear factors over $\mathbb{F}$, which always holds for $\mathbb{F} = \mathbb{C}$. A Jordan chain for an eigenvalue $\lambda$, listed bottom first, is a list $p_1, \dots, p_k$ with $p_1 \ne 0$ and

To verify a proposed Jordan matrix $J$ with change of basis matrix $P = \begin{bmatrix} p_1 & \cdots & p_n \end{bmatrix}$, do two checks.

1. Check that $P$ is invertible, for instance that $\det P \ne 0$.
2. Check $AP = PJ$ one column at a time. A column that starts a Jordan block for the eigenvalue $\lambda$ must satisfy $Ap_i = \lambda p_i$, and a later column of that block must satisfy $Ap_i = \lambda p_i + p_{i-1}$.

Together they give $P^{-1}AP = J$. Invariants supply cross-checks. For each eigenvalue the number of blocks equals $\dim \ker(A - \lambda I)$, the block sizes add up to the algebraic multiplicity, and the largest size is the exponent of $t - \lambda$ in $\mu_A$. The matrix $J$ is unique up to the order of its blocks, while $P$ is not unique.

Definition Let $V$ be a finite-dimensional inner product space over $\mathbb{F}$ and let $P \colon V \to V$ be linear and idempotent, $P^2 = P$. Then $V = \operatorname{im} P \oplus \ker P$, and $P$ is the projection onto $\operatorname{im} P$ along $\ker P$. The theorem says that $P$ is the orthogonal projection onto $\operatorname{im} P$, meaning $\ker P = (\operatorname{im} P)^{\perp}$, exactly when

If $P^{*} = P$, then for $y = Pu$ in the image and $z$ in the kernel, $\langle y, z \rangle = \langle Pu, z \rangle = \langle u, Pz \rangle = 0$, and the kernel fills $(\operatorname{im} P)^{\perp}$ because both have dimension $\dim V - \dim \operatorname{im} P$. Conversely, if the image and the kernel are orthogonal, then $v - Pv$ and $w - Pw$ lie in the kernel for all $v, w \in V$, so

which says $P^{*} = P$. In $\mathbb{F}^n$ with the standard inner product the condition reads $P^{\mathsf{T}} = P$ for a real matrix and $P^{*} = P$ for a complex one. In a basis with Gram matrix $G$ it reads $M^{*}G = GM$ for the coordinate matrix $M$ of $P$. An orthogonal projector never lengthens a vector, because $\lVert v \rVert^2 = \lVert Pv \rVert^2 + \lVert v - Pv \rVert^2$.

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$ and $d \ge 1$. The forward difference operator on $\mathcal{P}_d$ is

It is linear and sends every constant to $0$. For $k \ge 1$ the binomial theorem gives

of degree exactly $k - 1$ with leading coefficient $k$. So $\Delta$ maps $\mathcal{P}_d$ into $\mathcal{P}_{d-1}$, $\Delta^{d+1} = 0$ and $\Delta^{d}(t^d) = d! \ne 0$. Hence $\Delta$ is nilpotent with minimal polynomial $\mu_{\Delta}(z) = z^{d+1}$, where $z$ is the variable of operator polynomials and $t$ stays the variable of the polynomials in $\mathcal{P}_d$. Its kernel is the line of constants, so its Jordan form is a single block of size $d + 1$ for the eigenvalue $0$. A Jordan chain, listed bottom first, is $1, t, \binom{t}{2}, \dots, \binom{t}{d}$ with

because $\Delta \binom{t}{k} = \binom{t}{k-1}$. This is Pascal’s rule, which holds as an identity of polynomials because it holds at every integer $t \ge k$. The constants $W = \mathcal{P}_0$ form an invariant subspace, so $\Delta$ induces the map $p + W \mapsto \Delta p + W$ on $\mathcal{P}_d / W$. It is well defined because changing $p$ by a constant leaves $\Delta p$ unchanged.

Definition Let $A \in \mathbb{F}^{m \times n}$ have a full SVD $A = U\Sigma V^{*}$ with rank $r$, let the data be $b = Ax_{\text{true}} + e$, and let $\delta$ be a stated noise scale, the size that the component $u_j^{*}e$ of the noise along one singular direction may reasonably have. When the noise is equally large in every direction, this is the error level of a single data coordinate. A defensible choice among the pseudoinverse, truncated SVD and Tikhonov regularization follows four steps.

1. Write the data in singular coordinates $\beta_j = u_j^{*}b$ and compare each $\lvert \beta_j \rvert$ with $\delta$.
2. For each method compute the reconstruction, its residual $b - Ax$ and its gains $\varphi_j / \sigma_j$, where $\varphi_j$ are the filter factors. A data error of size $\delta$ along $u_j$ moves the coefficient along $v_j$ by $(\varphi_j / \sigma_j)\delta$.
3. Keep the full gain in a direction only when that movement is small next to the coefficient it produces. Truncate or damp the other directions, and tie $\tau$ or $\lambda$ to $\delta$, for instance by asking that the residual be about as large as the expected noise.
4. State what no method determines, namely the component of $x_{\text{true}}$ in $\ker A$, and the part $(I - AA^{+})b$ of the data that stays in every residual.

No method is best for every input. The choice rests on the noise model and on the purpose of the reconstruction, and a small residual is evidence of a good fit, not of recovery.