Given $X\in\mathbb{R}^{n\mathrm{x}n}$ is invertible, $p,q\in\mathbb{R}^{n}$, $x\in\mathbb{R}$, and assuming the $LU$ decomposition without pivoting of $X$ is known, I have to show the LU decomposition of the following block matrix can be computed in $O(n^2)$ operations: $$\begin{bmatrix} X & p \\ q^{T} & x \end{bmatrix}$$
The LU decomposition of this should be the following:
$$\begin{bmatrix} 1 & 0 \\ q^{T}X^{-1} & I \end{bmatrix}\begin{bmatrix} X & p \\ 0 & x -q^{T}X^{-1}p \end{bmatrix}$$
This can be taken further to an LDU decomposition, and I get that the actual decomposition can be computed in $O(n^2)$, but I think this should also include computing $X^{-1}$, and isn't this computed in $O(n^3)$ operations if we know its LU decomposition? I'm really confused about this. Also, are there any conditions for $p, q$ and $x$ for the LU decomposition to exist?
Any tips would be greatly appreciated, thank you.
Your extended LU decomposition is a bit off which increases the operation count to $O(n^3)$.
With $X = LU$, we seek vectors $r, s \in \mathbb{R}^n$, and a scalar $\gamma \in \mathbb{R}$ such that \begin{equation} \begin{pmatrix} X & p \\ q^T & x \end{pmatrix} = \begin{pmatrix} L & 0 \\ r^T & 1 \end{pmatrix} \begin{pmatrix} U & s \\ 0 & \gamma \end{pmatrix} = \begin{pmatrix} LU & Ls \\ r^T U & r^T s + \gamma \end{pmatrix}. \end{equation} We see that $r$ and $s$ can be obtained by solving the linear systems \begin{equation} U^T r = q, \quad Ls = p, \end{equation} at the cost of $O(n^2)$ operations each and that the computation of \begin{equation} \gamma = x - r^Ts \end{equation} requires $O(n)$ operations. It follows, that the $LU$ factorization of the extended matrix can be obtained from the LU factorization of $X$ at the cost of $O(n^2)$ operations.
We notice that there are no special conditions of $p$, $q$, and $x$ unless we want the extended matrix to be nonsingular. If $p$ and $q$ are chosen freely, then we will want to pick $x \not = r^Ts$ so that $\gamma \not = 0$, which implies that the extended matrix is nonsingular.