# conjugate gradient method for semi definite case

Show for a symmetric, positiv semi definite matrix $$A$$, a vector $$b\in Ran(A)$$ and initial vector $$x_0$$:

(1) All directions $$d_0,d_1,...,d_m$$ of the conjugate gradient method are in the range of $$A$$.
(2) For all $$j\in\{0,...,m\}$$ with $$Ad_j\ne 0$$ we have $$d_j^TAd_j>0$$.

(1) was no problem for me using the update equations for $$d_j$$. (2) says the CG-method is usable in the positive semidefinite case. But I am having trouble getting started with this one.

Edit: Using (1) we have that $$d_j=Ay$$ for some $$y$$. Then $$d_j^TAd_j=(Ay)^TAd_j=yA^TAd_j$$. I don't know if that helps me though.

For any semi-definite $A$, $Ax=0$ iff $x^TAx=0$.
One direction is easy. We just need to show that $x^TAx=0$ implies $Ax=0$ [which is actually what (2) is about]. There are more ways to show that.
Since $A$ is semi-definite, there is a matrix $B$ such that $A=B^TB$. Then we can see that $0=x^TAx=(Bx)^T(Bx)=\|Bx\|_2^2$ means that $Bx=0$ and hence $Ax=B^T(Bx)=0$.
There is a more elementary approach. Consider $f(t):=(tx+Ax)^TA(tx+Ax)$. Assume that $x^TAx=0$ but $Ax\neq 0$ for some nonzero $x$. Then $$f(t)=2t\|Ax\|_2^2+x^TA^3x.$$ If $Ax\neq 0$, $f(t)$ would be smaller than zero for $t<-x^TA^3x/(2\|Ax\|_2^2)$. This however contradicts the fact that $f(t)$ must be nonnegative since $A$ is semi-definite [because $f(t)$ is of the form $y(t)^TAy(t)$].