LU factorisation and nullity of composed maps
| English | Français |
|---|---|
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | forward substitution |
| nullity/ˈnʌlɪti/ | nullity |
A decision before an answer
- Factor a matrix once, then solve many systems with different right sides. The benefit comes from two triangular solves; reversing their order gives the wrong result.
- Your goal: Solve a factored linear system by forward and backward substitution.
Read the relationship
- 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.
- Apply row permutations consistently when pivoting is required.
For the stated unit-diagonal L and b=(−1,−1,12), what is the second coordinate of y solving Ly=b?
y₁=−1 and the second row is 2y₁+y₂=−1. Therefore y₂=1.
Use the defining rule
- 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.
- Bound the kernel dimension of a composition using image-kernel intersections.
A,B are maps R⁶→R⁶ with nullity A=2 and nullity B=3. What range is possible for nullity of A∘B?
Nullity B contributes 3, and im B∩ker A has dimension from 0 to 2 in this ambient space.
Check the conditions
- 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.
- Bound the kernel dimension of a composition using image-kernel intersections.
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.
In the example, the last U equation is 4x₃=8. The value of x₃ is ____.
Back substitution begins with the last row, giving x₃=8/4=2.
Apply the task format
- 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.
- Bound the kernel dimension of a composition using image-kernel intersections.
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.
Which answer fits this case?
Solve a factored linear system by forward and backward substitution
Every invertible matrix has an LU factorisation with unit lower triangular L without row exchanges.
The invertible matrix [[0,1],[1,0]] has a zero first pivot and cannot have that no-exchange unit-lower LU form. A row permutation repairs the pivot order.
Keep the distinctions
- forward substitution 前代 — Solving a lower triangular system from its first equation downward.
- nullity 零度 — The dimension of the kernel of a linear map.
- 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.
Match each term with its precise meaning in this lesson.
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
The order follows the stated process; check each stage before the next.