Changing a matrix entry to make it singular given the corresponding entry from U of its LU decomposition

Question

This question is from Gilbert Strang's Introduction to Linear Algebra, 2.2.30 (page 55)

If the last corner entry is $A(5,5) = 11$ and last pivot of $A$ is $U(5,5) = 4$, what different entry $A(5,5)$ would have made it singular ?

As LU decomposition is being computed, the entry $A(5,5)$ gets successively modified by the effect of multiples of rows $1,2,3,4$ in the process of obtaining $0$s below the previous pivots. How can we determine what $A(5,5)$ needs to be changed to given just the last pivot $U(5,5)=4$?

EDIT: @AlgebraicPavel gives an answer below which uses $LU$ decomposition. But this question precedes the introduction of $LU$ decomposition in the textbook. Is there a way to approach this without recourse to $LU$ decomposition ?

Answer 1

If you write $$ A=\begin{bmatrix} B & c \\ d^T & \epsilon\end{bmatrix}\in\mathbb{R}^{n\times n}, $$ where $B\in\mathbb{R}^{(n-1)\times(n-1)}$ and assume that the LU factorization of $A$ ($A=LU$) was obtained without permutations (no pivoting), then the bottom-right entry of the U-factor is simply the Schur complement $$ \epsilon-d^TB^{-1}c. $$ This can be shown simply by introducing a conforming partitioning of the factors $L$ and $U$ as $$ L=\begin{bmatrix}\tilde{L} & 0 \\ l^T & 1\end{bmatrix}, \quad U=\begin{bmatrix}\tilde{U} & u \\ 0 & \mu\end{bmatrix}, $$ which, using $A=LU$, leads to $$ B=\tilde{L}\tilde{U}, \quad u=\tilde{L}^{-1}c, \quad l=\tilde{U}^{-T}d, $$ and the relation for the bottom-right entry of $U$ in the form $$ \mu = \epsilon - l^Tu=\epsilon-d^T\tilde{U}^{-1}\tilde{L}^{-1}c=\epsilon-d^T(\tilde{L}\tilde{U})^{-1}c=\epsilon-d^TB^{-1}c. $$ So, replacing $\epsilon$ in $A$ with $d^TB^{-1}c$, that is, with $\epsilon-\mu$, makes the modified matrix $A$ singular since the bottom-right corner of the modified $U$ is $d^TB^{-1}c-d^TB^{-1}c=0$).

---

Without introducing the LU factorization, the conclusion is the same. Provided that there is no pivoting$^{\color{red}*}$ during the elimination, the question is what happens with the bottom-right entry during the elimination. If you apply a sequence of elementary operations to transform $$ A_1=\begin{bmatrix} B & c \\ d^T & \epsilon_1 \end{bmatrix} \rightarrow U_1=\begin{bmatrix} \tilde{U} & u \\ 0 & \mu_1 \end{bmatrix}, $$ the same sequence of elementary operations applied to a modified $A_1$ will give $$ A_2=\begin{bmatrix} B & c \\ d^T & \epsilon_2 \end{bmatrix} \rightarrow U_2=\begin{bmatrix} \tilde{U} & u \\ 0 & \mu_2 \end{bmatrix}, $$ where $\mu_2$ is given by $\mu_2=\mu_1+(\epsilon_2-\epsilon_1)$. This is because the sequence of operations applied to the last row of $A_2$ is exactly the same as for $A_1$ (the elementary operations are independent of the bottom-right entry of $A$). More precisely, the elementary operations on $A_1$ touch its last entry in some way to get $\mu_1=\epsilon_1+\sum_i\delta_i$, and in the same way these operations modify the corresponding entry in $A_2$, that is, $\mu_2=\epsilon_2+\sum_i\delta_i$. Hence, $\mu_2-\mu_1=\epsilon_2-\epsilon_1$.

---

$^{\color{red}*}$ This assumption can be slightly relaxed. You just need to do not replace any row during the elimination with the last row and do not replace any column with the last column. Otherwise, you can choose pivots as you like.

Answer 2

because the A(5,5) entry in the last row before the elimination (reduce to upper triangle form) is given as 11, assume the last row is

2v + 3w - 1x + 2y +11z

after the row operation it becomes to 0v + 0w + 0x + 0y + 4z

we know that 11z must be subtracted by 7z to get 4z from the row operation, so if we change the corner entry = 7, then the pivot will be 0 and hence the matrix A is singular.