Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof resit / 5 / e / Solution

Let $r=\mathrm{rank}(A)$. If $r=0$, the matrix is zero and the identity is immediate. Otherwise choose the rank factorization $A=BC$ from part b. The column space of $B$ is the image of $A$.

An idempotent matrix acts as the identity on its image: if $u=Av$, then $Au=A^{2}v=Av=u$. Applying this to each column of $B$ gives $AB=B$. Substituting $A=BC$ yields $B(CB-I_r)=0$. Since $B$ has full column rank, the represented map is injective, so each column of $CB-I_r$ is zero. Thus $CB=I_r$.

Now the rectangular cyclic property of the trace givesThis proves that the trace of an idempotent equals its rank using the supplied factorization method. Orthogonality of the projection is unnecessary: the argument applies to every real idempotent matrix.