Operations for LU decomposition 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.
 A: 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.
