 Solution

For the quadratic function, write $r_j=b-A{x}_j$ and restrict to the full line $x_j+\alpha p_j$. Symmetry of $A$ givesThe coefficient $p_j^{T}A{p}_j$ is positive by positive definiteness and $p_j\ne 0$. The unique minimizer is thereforeQuadratic minimization along a line also gives the exact changeThus strict decrease holds exactly when $p_j^T{r}_j\ne 0$. The search is over the whole line, so ${\alpha }_j$ can be negative; a positive step size would require the additional descent direction condition $p_j^T{r}_j>0$.