conjugate gradient method for semi definite case

Question

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.

Answer 1

Item (2) follows from the following fact for semi-definite matrices:

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)$].