I was using CVXOPT library to solve one of my quadratic programming problem. I found that, CVXOPT library solves KKT system efficiently by reducing a 3x3 matrox into 2x2 blocks which has the following form:
$$ \begin{equation} \begin{aligned} \begin{bmatrix} P & A^\mathsf{T} & G^\mathsf{T}\\ A & 0 & 0\\ G & 0 & -W^\mathsf{T}W \end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} b_x\\ b_y\\ b_z \end{bmatrix} \end{aligned} \label{eqn:KKT_solution_1} \end{equation} $$
This is transformed into: $$ \begin{equation} \begin{aligned} \begin{bmatrix} P+G^\mathsf{T}W^{-1}W^\mathsf{-T}G & A^\mathsf{T}\\ A & 0\\ \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} b_x+G^\mathsf{T}W^{-1}W^\mathsf{-T}b_z\\ b_y \end{bmatrix} \end{aligned} \end{equation} $$
My question is, in which condition this is true. I have read their Documentation. They have not provided proper reference in this case. Can some please explain how can we write such reduction? Or any reference? Thank you.
It is true as long as $W^{-1}$ exists. Just solve the last equation for $z$ and substitute it into the first one.
P.S. For non-square $W$: it is true when $M=W^TW$ is invertible, but $W^{-1}W^{-T}$ above has to be replaced with $M^{-1}$.
Edit:
With the notation $M=W^TW$, the last equation is $$ Gx-Mz=b_z\quad\Leftrightarrow\quad z=M^{-1}(Gx-b_z). $$ Substitute it into the first one $$ Px+A^Ty+G^Tz=b_x\quad\Leftrightarrow\quad Px+A^Ty+G^TM^{-1}(Gx-b_z)=b_x $$ which after rearranging becomes exactly the new first equation $$ (P+G^TM^{-1}G)x+A^Ty=b_x+G^TM^{-1}b_z. $$
Example:
Assume that you have the system $$ \begin{bmatrix} 1 & 2 & 3\\ 2 & 0 & 0\\ 3 & 0 & 1 \end{bmatrix} \begin{bmatrix} x\\y\\z\end{bmatrix}= \begin{bmatrix} 4\\5\\6 \end{bmatrix}. $$ It is equivalent to three equations $$ \left\{ \begin{array}{lcl} x+2y+3z&=&4\\ 2x&=&5\\ 3x+z&=&6. \end{array} \right. $$ Let us rewrite the last equation as $z=6-3x$ and substitute it into the first one. Then the variable $z$ is eliminated, and we have only two equations left $$ \left\{ \begin{array}{lcl} x+2y+3(6-3x)&=&4\\ 2x&=&5. \end{array} \right. $$ After rearranging the first equation, the system looks like $$ \left\{ \begin{array}{lcl} x-9x+2y+18&=&4\\ 2x&=&5 \end{array} \right.\quad\Leftrightarrow\quad \left\{ \begin{array}{lcl} -8x+2y&=&-14\\ 2x&=&5 \end{array} \right. $$ which corresponds to the $2\times 2$ matrix equation $$ \begin{bmatrix} -8 & 2\\ 2 & 0 \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}= \begin{bmatrix} -14\\5 \end{bmatrix}. $$