# Dodging to do conjugate gradient on the normal equations.

Let us consider the linear equation system $$\bf Ax = b$$

We can formulate it’s normal equations:

$${\bf A}^T{\bf Ax=A}^T{\bf b}$$

but these are often harder to solve, because $${\bf A}^T{\bf A}$$ has worse condition number than $$\bf A$$. Some time ago I stumbled upon this approach to formulate a linear equation system without normal equations:

$$\begin{bmatrix}\bf I&\bf A\{\bf A}^T&\bf 0\end{bmatrix}\begin{bmatrix}\bf r\\bf x\end{bmatrix}=\begin{bmatrix}\bf b\\bf 0\end{bmatrix}$$

Here we can see the constructed matrix is symmetric so we can avoid the normal equations, but at the expense of blowing up the space to dim(r)+dim(x).

How can we prove / realize that this choice will be better/faster?