LU factorisation and nullity of composed maps
Introduced| English | Meaning |
|---|---|
| nullity/ˈnʌlɪti/ | The dimension of the null space of a matrix: how many free variables the equation Ax = 0 has. |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | Solving a lower-triangular system from the first row downward. |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | Solving an upper-triangular system from the last row upward. |
One machine, many loads
- A fixed network can face many demand vectors $b$. In a linear model $Ax=b$, factor the same matrix once, then solve quickly for each new demand.
- A second question asks which inputs a chain of linear maps loses. Its nullity 零度 counts independent input directions sent to zero; it does not count the number of zero entries.
Fix the factorisation convention
- For the solve, take an invertible $n\times n$ matrix and write $PA=LU$. Here $P$ permutes rows, $L$ is lower triangular with diagonal entries $1$, and $U$ is upper triangular with nonzero diagonal entries.
- Write $d=Pb$ and $y=Ux$. Then solve $Ly=d$ first and $Ux=y$ second. If $P=I$, this reduces to $A=LU$; no explicit matrix inverse is needed.
Elimination stores its multipliers
- For $A=\begin{pmatrix}2&1\\6&4\end{pmatrix}$, subtract $3$ times row 1 from row 2. This gives $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ and stores the multiplier in $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$. Multiplication checks $LU=A$.
- With $b=(2,7)$, first solve $Ly=b$: $y_1=2$ and $y_2=7-3(2)=1$. Then $x_2=1$ and $x_1=(2-1)/2=1/2$. Substitution in $Ax=b$ checks both equations.
Let $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$, $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ and $b=(2,7)$. Solve $LUx=b$; give $x_1$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Forward substitution gives $y=(2,1)$. Then $x_2=1$ and $x_1=(2-1)/2=1/2$. The product $LU=\begin{pmatrix}2&1\\6&4\end{pmatrix}$ checks the original system.
Forward through the lower triangle
- Forward substitution 前代 solves each row using entries already found above it. With unit-diagonal $L$, use $y_i=d_i-\sum_{j<i}l_{ij}y_j$. A non-unit diagonal instead requires division by $l_{ii}\ne0$.
- In the original three-row example, $L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}$ and $d=(-1,-1,12)$. Thus $y_1=-1$, $y_2=-1-2(-1)=1$ and $y_3=12+(-1)-3(1)=8$.
Solve $Ly=d$ for $L=\begin{pmatrix}2&0\\3&1\end{pmatrix}$ and $d=(4,7)$. Give $y_2$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Divide by $l_{11}=2$: $y_1=2$. Then $y_2=7-3(2)=1$. Assuming $y_1=d_1$ would be wrong for this non-unit L.
Back through the upper triangle
- Back substitution 回代 starts at the bottom: $x_i=(y_i-\sum_{j>i}u_{ij}x_j)/u_{ii}$. The division is valid because each diagonal pivot is nonzero.
- For $U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix}$ and $y=(-1,1,8)$, obtain $x_3=2$, $x_2=(1-4)/3=-1$ and $x_1=(-1+1+2)/2=1$. Hence $x=(1,-1,2)$; $Ux=y$ and $Ly=b$ verify the original system.
A row swap must move the right side
- Take $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$ and $b=(4,7)$. Swap the rows: $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ gives $PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}=U$ and $L=I$. The new right side is $Pb=(7,4)$.
- Solve $y=(7,4)$, then $x_2=2$ and $x_1=7-3(2)=1$. The original equations give $2x_2=4$ and $x_1+3x_2=7$. Using the old $b$ with $PA$ would solve a different system.
For an invertible square matrix with $PA=LU$, put the steps for solving $Ax=b$ in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
$PAx=LUx=Pb$. Set $y=Ux$, solve the lower-triangular system first, then the upper-triangular system, and check $Ax=b$.
For $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, $b=(4,7)$ and the row-swap matrix $P$, which pair gives $Pb$ and the solution $x$?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Swap the right side with the rows. Back substitution in $\begin{pmatrix}1&3\\0&2\end{pmatrix}x=(7,4)$ gives $x_2=2$, then $x_1=1$.
Invertibility does not promise unpivoted LU
- The previous $A$ is invertible, since its determinant is $-2$. But a unit-lower $L$ would give $a_{11}=u_{11}=0$ and $a_{21}=l_{21}u_{11}=0$, contradicting $a_{21}=1$. So this matrix has no unpivoted $A=LU$ of that form.
- In exact arithmetic, every invertible square matrix admits $PA=LU$ with suitable row swaps. A nonzero leading entry alone does not guarantee every later pivot is nonzero. In numerical work, swaps can also avoid small pivots that amplify rounding error.
Some invertible square matrices require a row exchange before a factorisation with unit-lower L and upper-triangular U exists.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
True. For $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, an unpivoted unit-lower factorisation would force $a_{21}=0$. A row swap gives $PA=U$ and $L=I$.
For $A=\begin{pmatrix}0&1\\2&3\end{pmatrix}$ and $b=(2,8)$, exhibit $PA=LU$, solve $Ax=b$ and check the original equations. Explain why unit-lower unpivoted LU fails.
Compare the intermediate steps, map order and assumptions with the model response.
A zero diagonal needs a different decision
- A singular matrix can still have an LU factorisation: $L=I$ and $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ are an example. A zero diagonal prevents the unique-solution division rule; it does not by itself prove that no solution exists.
- For this $U$, right side $(2,0)$ gives infinitely many solutions $x_1=2-t$, $x_2=t$. Right side $(2,1)$ gives no solution, since the last row would say $0=1$. Check consistency and free variables instead of dividing by zero.
For $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$, how many solutions do $Ux=(2,0)$ and $Ux=(2,1)$ have, in that order?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first system leaves $x_2$ free. The second requires $0=1$. A zero pivot does not allow a unique-solution division step.
Reuse the factors, not the old solution
- For a general dense $n\times n$ matrix, standard elimination costs $O(n^3)$ arithmetic operations. Each triangular solve costs $O(n^2)$, so $k$ right sides cost $O(n^3+kn^2)$ when the same $P,L,U$ are reused.
- Recompute $Pb$, $y$ and $x$ for each right side. Check the residual $b-Ax$ in the original row order; exact zero verifies an exact solution. A small numerical residual alone does not guarantee a small solution error when $A$ is ill-conditioned.
Which phase of the solve?
Separate permutation, forward solve, backward solve and verification for invertible 3x3 PA=LU with unit-diagonal L.
Using standard dense LU, what is the total arithmetic cost for $k$ right sides of the same invertible $n\times n$ matrix, reusing its factors?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Factor once at cubic cost, then perform two quadratic-cost triangular solves for each right side. This is a general dense estimate.
Track the spaces before the dimensions
- Now let $B:V\to W$ and $A:W\to Z$ be linear maps between finite-dimensional spaces over the same field. The product $AB=A\circ B$ applies $B$ first. Write $\dim V=n$, $\dim W=m$, $\operatorname{rank}B=r$ and $\dim\ker A=s$.
- Since $Bv=0$ implies $A(Bv)=0$, $\ker B\subseteq\ker(AB)$. The extra lost directions arise when $Bv$ is nonzero but lies in $\ker A$. The intersection $\operatorname{im}B\cap\ker A$ lives in $W$.
Derive the composition identity
- Restrict $B$ to $T:\ker(AB)\to\operatorname{im}B\cap\ker A$. This map is onto: if $w=Bv$ and $Aw=0$, then $ABv=0$. Its kernel is exactly $\ker B$.
- Rank–nullity for $T$ therefore gives $\dim\ker(AB)=\dim\ker B+t$, where $t=\dim(\operatorname{im}B\cap\ker A)$. Equivalently, $\operatorname{rank}(AB)=r-t$: only directions actually reached by $B$ can be lost at the second map.
For linear maps $B:V\to W$ and $A:W\to Z$, suppose rank $B=4$ and rank $AB=2$. Give $\dim(\operatorname{im}B\cap\ker A)$.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Rank $AB=r-t$, so $t=4-2=2$.
Bound the intersection in the middle space
- For subspaces $S,K\subseteq W$ with dimensions $r,s$, write $t=\dim(S\cap K)$. The identity $\dim(S+K)=r+s-t\le m$ gives $t\ge r+s-m$. Also $0\le t\le\min(r,s)$.
- The lower bound for $t$ is $\max(0,r+s-m)$; the upper bound is $\min(r,s)$. Add $\dim\ker B=n-r$ for nullity bounds, or subtract $t$ from $r$ for rank bounds. The ambient dimension is $m$, which need not equal $n$.
Both ends of the six-dimensional range occur
- For endomorphisms of $\mathbb R^6$, suppose nullity $A=2$ and nullity $B=3$. Then $r=3$, $s=2$, $m=6$, so $0\le t\le2$ and $3\le\dim\ker(AB)\le5$.
- Choose $A=\operatorname{diag}(1,1,1,1,0,0)$. Let $B$ send its first three basis vectors to $(e_1,e_2,e_3)$, $(e_1,e_2,e_5)$ or $(e_1,e_5,e_6)$, and the last three to zero. These choices give $t=0,1,2$ and nullities $3,4,5$, respectively.
On $\mathbb R^4$, let $A=\operatorname{diag}(1,1,0,0)$ and let $B$ have nullity $2$. Find every possible nullity of $AB$, and construct B for each value.
Compare the intermediate steps, map order and assumptions with the model response.
Work the original five-dimensional bounds
- For $A,B:\mathbb R^5\to\mathbb R^5$ with nullities $1,2$, rank $B=3$ and $0\le t\le1$. Hence the smallest possible nullity of $AB$ is $2$, and the largest is $3$.
- Fix $A=\operatorname{diag}(1,1,1,1,0)$. Taking $B=\operatorname{diag}(1,1,1,0,0)$ gives $t=0$; taking $B=\operatorname{diag}(1,1,0,0,1)$ gives $t=1$. Thus both bounds occur. Adding the two nullities always gives the wrong answer in the first case.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ and $2$, respectively. What is the largest possible nullity of $AB$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Rank $B=3$. The image of $B$ can contain the one-dimensional kernel of $A$, giving nullity $AB=2+1=3$.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ and $2$, respectively. What is the smallest possible nullity of $AB$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The intersection can have dimension $\max(0,3+1-5)=0$. Thus the minimum is $2+0=2$, attained by the two diagonal maps in the lesson.
Different domain sizes can force overlap
- Let $\dim V=7$, $\dim W=4$, $\dim Z=3$, nullity $B=4$ and nullity $A=2$. Then $r=3$, $s=2$ and $1\le t\le2$. So nullity $AB$ ranges from $5$ to $6$, and $1≤\operatorname{rank}(AB)≤2$.
- To realise the bounds, let $A(w_1,w_2,w_3,w_4)=(w_1,w_2,0)$. Map the first three basis vectors of $V$ to $(e_1,e_2,e_3)$ for $t=1$, or $(e_1,e_3,e_4)$ for $t=2$; map the other four to zero. The middle space has dimension $4$, not $7$.
Let $\dim V=7$, $\dim W=4$, nullity $B=4$ and nullity $A=2$ for $B:V\to W$, $A:W\to\mathbb R^3$. What is the smallest possible nullity of $AB$?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Rank $B=3$. The intersection in the four-dimensional middle space has dimension at least $3+2-4=1$, so the minimum nullity is $4+1=5$.
Let $B:\mathbb R^6\to\mathbb R^3$ have nullity $4$, and $A:\mathbb R^3\to\mathbb R^2$ have nullity $2$. Find the sharp bounds for nullity $AB$ and give maps attaining both.
Compare the intermediate steps, map order and assumptions with the model response.
Reversing the maps changes the problem
- Even for square matrices, $AB$ and $BA$ need not have the same nullity. Take $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ and $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$. Then $AB=B$ has rank $1$ and nullity $1$, while $BA=0$ has nullity $2$.
- The identity for $BA$ uses $\operatorname{im}A\cap\ker B$ and adds nullity $A$. Keep the actual map order. For rectangular maps, $AB$ and $BA$ may even have different domain dimensions, or one product may be undefined.
Two square matrices always give the same nullity for AB and BA.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
False. With $A=\operatorname{diag}(1,0)$ and $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $AB=B$ has nullity $1$ but $BA=0$ has nullity $2$.
Read equality cases from the image
- If $\operatorname{im}B\cap\ker A=\{0\}$, then $\ker(AB)=\ker B$: $A$ is injective on the image reached by $B$. An invertible $A$ guarantees this, but is not necessary. If $\operatorname{im}B\subseteq\ker A$, then $AB=0$ and nullity $AB=\dim V$.
- If $B$ is an isomorphism, it carries $\ker(AB)$ bijectively onto $\ker A$, so their dimensions agree. Their kernels need not be the same subspace. In general, nullity $A$ alone says nothing about which of its lost directions $B$ reaches.
What does the map information guarantee?
Use finite-dimensional compatible B then A, with nullity B=k, dim V=n and t=dim(im B intersect ker A).
Let $A=\operatorname{diag}(1,0)$ on $\mathbb R^2$ and $B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Find $\ker A$ and $\ker(AB)$. Explain why their dimensions agree but their subspaces differ.
Compare the intermediate steps, map order and assumptions with the model response.
Recap
- With $PA=LU$, permute the right side, solve $Ly=Pb$, then solve $Ux=y$. Check nonzero pivots before using division, and verify $Ax=b$.
- For $B:V\to W$ followed by $A:W\to Z$, add nullity $B$ to the image–kernel overlap dimension. Bound that overlap in $W$, and check whether the requested result is a minimum, maximum or fixed value.
- nullity: The dimension of the kernel of a linear map.
- forward substitution: Solving a lower-triangular system from the first row downward.
- back substitution: Solving an upper-triangular system from the last row upward.