# LU Decomposition (added coulumn and row)

$$\begin{array}{l}{\text { The regular Matrix } A \in \mathbb{R}^{n \times n} \text { with the LU decomposition } A=L R \text { gets an extra column }} \\ {\text { anr row so }} \\ {\qquad \widehat{A}=\left(\begin{array}{cc}{A} & {b} \\ {c^{T}} & {d}\end{array}\right), \quad b, c \in \mathbb{R}^{n}, \quad d \in \mathbb{R}}\end{array}$$ $$\begin{array}{l}{\text { a) State the LU-Decomposition of } \widehat{A} \text { with a matrix } \widehat{L} \text { of the form }} \\ {\qquad \widehat{L}=\left(\begin{array}{cc}{L} & {0} \\ {x^{T}} & {1}\end{array}\right), \quad x \in \mathbb{R}^{n}}\end{array}$$ $$\begin{array}{l}{\text { b) Show that } \widehat{A} \text { is only regular if } d-c^{T} A^{-1} b \neq 0 .} \\ {\text { c) In singular care state a solution } z \in \mathbb{R}^{n+1} \backslash\{0\} \text { of the homogeneously }} \\ {\text { equation } \widehat{A} z=0}\end{array}$$

Could someone give me advice on how to solve that? I have literally no clue how to start that one

For (a), assume $$\hat{U}$$ in $$\hat{A}=\hat{L}\hat{U}$$ of the form $$\hat{U}=\begin{bmatrix}U&u\\0&\upsilon\end{bmatrix}.$$ From $$\begin{bmatrix} A&b\\c^T&d \end{bmatrix} = \begin{bmatrix} L & 0 \\ x^T & 1 \end{bmatrix} \begin{bmatrix}U&u\\0&\upsilon\end{bmatrix} = \begin{bmatrix} LU & Lu \\ x^TU & x^Tu+\upsilon \end{bmatrix},$$ we have $$A=LU, \quad b=Lu, \quad c=U^Tx, \quad d=x^Tu+\upsilon.$$ Since $$A=LU=LR$$, this gives $$U=R$$. Can you go ahead and solve the remaining three equations for $$x$$, $$u$$, and $$\upsilon$$?
For (b), it is clear that $$\hat{A}$$ is singular if and only if $$\upsilon=0$$. When does this happen?
For (c), use the previously obtained LU factorization or, better, directly the definition. The matrix $$\hat{A}$$ is singular if and only if there is a nonzero $$\hat{x}:=[x^T,\xi]^T$$ such that $$\hat{A}\hat{x}=0$$, that is, $$Ax+\xi b=0, \quad c^Tx+d\xi=0.$$ Clearly, $$\xi\neq 0$$. Otherwise, $$A$$ would need to be singular. Given $$\xi\neq 0$$, we can get the corresponding $$x$$ from the first equation because $$A$$ is nonsingular. Obviously, $$\xi=0$$ leads to the zero solution of the homogeneous equation.