I have the following linear system:
$$ \begin{bmatrix} \mathbf{I} & \mathbf{0} & \mathbf{0} & -\mathbf{Z}^{T} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & -\mathbf{Y}^{T} \\ \mathbf{0} & \mathbf{0} & \gamma \mathbf{I} & -\mathbf{I} \\ \mathbf{Z} & \mathbf{Y} & \mathbf{I} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ b \\ \mathbf{e} \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \mathbf{1} \end{bmatrix}$$
I want to eliminate the variables $\mathbf{w}$ and $\mathbf{e}$ from this equation. How can I do this?
The answer is apparently:
$$ \begin{bmatrix} 0 & -\mathbf{Y}^{T} \\ \mathbf{Y} & \mathbf{Z} \mathbf{Z}^{T} + \frac{1}{\gamma} \mathbf{I} \end{bmatrix} \begin{bmatrix} b \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{1} \end{bmatrix} $$
I think there is a formula for 2×2 block matrix variable elimination…but I can't seem to find it anywhere…
Best Answer
$$ \begin{bmatrix} \mathbf{I} & \mathbf{0} & \mathbf{0} & -\mathbf{Z}^{T} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & -\mathbf{Y}^{T} \\ \mathbf{0} & \mathbf{0} & \gamma \mathbf{I} & -\mathbf{I} \\ \mathbf{Z} & \mathbf{Y} & \mathbf{I} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ b \\ \mathbf{e} \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \mathbf{1} \end{bmatrix}$$
What you want is to keep the second row and eliminate $\mathbf{e}$ and $\mathbf{w}$ in the last row. To do that, multiply first row by $\mathbf{Z}$ and subtract it from the last row: $$ \begin{bmatrix} \mathbf{I} & \mathbf{0} & \mathbf{0} & -\mathbf{Z}^{T} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & -\mathbf{Y}^{T} \\ \mathbf{0} & \mathbf{0} & \gamma \mathbf{I} & -\mathbf{I} \\ \mathbf{Z-Z} & \mathbf{Y} & \mathbf{I} & \mathbf{ZZ}^T \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ b \\ \mathbf{e} \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \mathbf{1} \end{bmatrix}$$ The next step is to multiply the third row by $1/\gamma$ and subtract it from the fourth row: $$ \begin{bmatrix} \mathbf{I} & \mathbf{0} & \mathbf{0} & -\mathbf{Z}^{T} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & -\mathbf{Y}^{T} \\ \mathbf{0} & \mathbf{0} & \gamma \mathbf{I} & -\mathbf{I} \\ \mathbf{0} & \mathbf{Y} & \mathbf{I-I} & \mathbf{ZZ}^T+\frac1\gamma\mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ b \\ \mathbf{e} \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \mathbf{1} \end{bmatrix}$$ $$ \begin{bmatrix} \mathbf{I} & \mathbf{0} & \mathbf{0} & -\mathbf{Z}^{T} \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & -\mathbf{Y}^{T} \\ \mathbf{0} & \mathbf{0} & \gamma \mathbf{I} & -\mathbf{I} \\ \mathbf{0} & \mathbf{Y} & \mathbf{0} & \mathbf{ZZ}^T+\frac1\gamma\mathbf{I} \end{bmatrix} \begin{bmatrix} \mathbf{w} \\ b \\ \mathbf{e} \\ \mathbf{\alpha} \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \mathbf{1} \end{bmatrix}$$ Now just take the 2nd and 4th rows, and ignore columns (and variables) where the entire column is $\mathbf{0}$.