A.7 · LU factorisation and nullity of composed maps

Undergraduate GRE preparation. Local objectives within the reviewed ETS scope; this is original teaching, not an official test or score predictor.

Prerequisites: Row operations, triangular systems and rank-nullity.

• Solve a factored linear system by forward and backward substitution
• Apply row permutations consistently when pivoting is required
• Bound the kernel dimension of a composition using image-kernel intersections

forward substitution 前代: Solving a lower triangular system from its first equation downward.

nullity 零度: The dimension of the kernel of a linear map.

A factorisation A=LU expresses a square matrix as lower triangular L and upper triangular U. With unit diagonal L, forward substitution is especially simple. An invertible matrix need not admit this form without row exchanges: a zero leading pivot can require a permutation. For PA=LU, solve Ly=Pb, then Ux=y. The permutation acts on the right side as well as the coefficient matrix. Nonzero leading principal pivots justify the usual no-exchange elimination, not invertibility alone.

In Ly=b, compute y from top to bottom, subtracting terms already known; divide by the current diagonal unless it is one. In Ux=y, compute x from bottom to top. For each equation substitute back into the original row as a check. Reusing LU for many right sides avoids repeating the elimination: dense factorisation takes cubic-order work in dimension, while each triangular solve takes quadratic-order work. Exact arithmetic can check small examples; numerical pivoting reduces some roundoff problems but cannot remove inherent ill-conditioning.

For B:V→W and A:W→Z, ker B is contained in ker(A∘B), but the latter can be larger. Extra vectors are those mapped by B into ker A. Restrict B to ker(A∘B): its image is im B∩ker A and its kernel is ker B. Rank-nullity on this restricted map gives dim ker(A∘B)=dim ker B+dim(im B∩ker A). The intersection, not the whole kernel of A, determines the extra nullity.

For endomorphisms of R⁶ with nullity A=2 and nullity B=3, rank B=3 and the intersection dimension can range from 0 to 2. Thus nullity of A∘B ranges from 3 to 5. Bounds depend on the common intermediate space: for subspaces of dimensions r and s in an m-dimensional space, their intersection has dimension between max(0,r+s−m) and min(r,s). Reversing the composition can change its nullity, even though AB and BA are both defined. Choose compatible spaces before applying these formulas.

Let L=[[1,0,0],[2,1,0],[−1,3,1]], U=[[2,1,−1],[0,3,2],[0,0,4]], and b=(−1,−1,12). Forward substitution gives y=(−1,1,8). Back substitution gives x₃=2, x₂=(1−4)/3=−1, and x₁=(−1−(−1)+2)/2=1. Therefore x=(1,−1,2). Multiplying Ux gives y and multiplying Ly gives b, independently checking the factor order.

Solve with L first and U second, and permute b if PA=LU. A composition’s nullity is not automatically the sum of the two nullities; only the image-kernel intersection adds to nullity B.

Let $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$, $U=\begin{pmatrix}3&1\\0&2\end{pmatrix}$ and $b=(5,12)^T$. Solve LUx=b and verify in the multiplied matrix. For PA=LU, where does P act when solving Ax=b?

Worked solution

First solve Ly=b: $y_1=5$, $2y_1+y_2=12$, so $y_2=2$. Then Ux=y gives $x_2=1$ and $3x_1+1=5$, hence $x_1=4/3$. The product matrix is $A=\begin{pmatrix}3&1\\6&4\end{pmatrix}$; applying it to $(4/3,1)^T$ gives $(5,12)^T$. If PA=LU, multiply the original equation by P and solve Ly=Pb, followed by Ux=y. Omitting P on b solves a different system.

Let A and B be endomorphisms of $\mathbb R^5$ with nullities two and three, respectively. Find all possible nullities of AB, and justify both the bound and attainability.

Check after attempting

Rank B is two. Restrict B to $\ker(AB)$ to get

The two subspaces in the intersection both have dimension two in five dimensions, so intersection dimension may be zero, one or two. Thus nullity is 3, 4 or 5. To realise each, take $\ker A=\operatorname{span}(e_1,e_2)$ and image B respectively $\operatorname{span}(e_3,e_4)$, $\operatorname{span}(e_1,e_3)$ or $\operatorname{span}(e_1,e_2)$. Choose any rank-two B onto that image. These constructions prove attainability rather than only a loose interval bound.