I want to solve the usual $A x = b$ system. In block form:


$$ \begin{bmatrix} B & c \\ c^{T} & 0 \end{bmatrix} \begin{bmatrix} x' \\ x\_{n+1} \end{bmatrix} = \begin{bmatrix} b' \\ b\_{n+1} \end{bmatrix}$$


where


* $B \in \mathbb{R}^{n \times n} $ is a positive definite matrix
* $c \in \mathbb{R}^{n}$
* $x,b \in \mathbb{R}^{n+1}$, so $x',b' \in \mathbb{R}^{n}$ and $x\_{n+1},b\_{n+1} \in \mathbb{R}$


Matrix $A$ is neither positive definite nor positive semidefinite.


I am not aware of well-known methods such as Cholesky or $LDL^T$ to solve this. Is there an efficient method to tackle this problem?



Solve linear system with bordered positive definite matrix
By combining the useful comments of [Rodrigo](https://mathoverflow.net/users/91764/rodrigo-de-azevedo) and [Todd](https://mathoverflow.net/users/2926/todd-trimble), the methodology to solve this system is shown here below. One caveat is that the method is probably not very efficient, since you need to use the decomposition of $B$ two times to find the final solution.


### 1. Build Equations with Schur Complement


By using [Schur Complement](https://en.wikipedia.org/wiki/Schur_complement) on the original problem, one can obtain the following system:


$$
\left\{\tag{1}
\begin{array}{c}
 B x' = b' - x\_{n+1} c\\ 
 c^T B^{-1} (b' - x\_{n+1} c) = b\_{n+1} \\
\end{array}
\right.
$$


### 2. Compute $\eta^T$


1. Compute $\eta$ using the equation $B \eta = c$. This can be done with Cholesky or similar methods since B is positive definite.
2. Transposing the equation $B \eta = c$ leads to $\eta^T B = c^T$ since $B$ is symmetric. Now it is possible to rewrite the equation as
$$\eta^T = c^T B^{-1} \tag{2}$$.


### 3. Combine


1. Replace $(2)$ in second equation of $(1)$, expand and simplify to compute $x\_{n+1}$:


$$
 x\_{n+1} = \frac{\eta^T b' - b\_{n+1}}{\eta^T c}
$$


2. Replace the value of $x\_{n+1}$ in first equation of $(1)$ to find $x'$ with regular decomposition methods.


