# Basis of a projection

Show that if $E$ is a projection on a finite dimensional vector space, then there exists a basis $B$ such that the matrix $(e_{ij})$ of $E$ with respect to $B$ has the following special form: $e_{ij}= 0$ or $1$ for all $i$ and $j$, and $e_{ij}=0$ if $i\neq j$.

I seem to be having some difficulty understand this question. I could use a little help in the right direction.

-
You could start writing in full the matrix of the projection along $\{0\}\times\{0\}\times\mathbb R$ on $\mathbb R^2\times\{0\}$ in $E=\mathbb R^3$ and ponder what this tells you on $B$ in this case. –  Did Oct 16 '11 at 21:12
@ Davide. I know that a projection is idempotent. –  Rita Oct 16 '11 at 21:17
@Didier. I that that may be part of my problem. I do not know what the full matric in your example would look like. –  Rita Oct 16 '11 at 21:18
@Rita: Why don't you work it out? Use the standard basis for $\mathbb{R}^3$; the projection sends $(a,b,c)$ to $(a,b,0)$. –  Arturo Magidin Oct 16 '11 at 21:24
@ Arturo. Thanks. The problem is, I hae only seen projections with a vector. I do not know how to work out the projection you mentioned. Do you have any suggestions? –  Rita Oct 16 '11 at 22:30

Added. In the context of linear algebra, a projection is any function $E\colon\mathbf{V}\to\mathbf{V}$ that is a linear transformation, and is such that $E^2=E$ (that is, applying $E$ twice is the same as applying it once.

For example, the map $E\colon\mathbb{R}^3\to\mathbb{R}^3$ that maps $(a,b,c)$ to $(a,b,0)$ is a projection: it is linear (check it), and $E^2(a,b,c) = E(E(a,b,c)) = E(a,b,0) = (a,b,0) = E(a,b,c)$. What does $E$ do to the standard basis? It sends $(1,0,0)$ to itself; it send $(0,1,0)$ to itself; and it sends $(0,0,1)$ to $(0,0,0)$. If we write the matrix of $E$ relative to the standard basis, we obtain $$\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{array}\right),$$ which agrees with the proposition you are being asked to proved.

Here's another example: take the linear transformation $E\colon\mathbb{R}^2\to\mathbb{R}^2$ that sends $(a,b)$ to $(\frac{1}{2}(a+b),\frac{1}{2}(a+b))$. This is a linear transformation (check), and \begin{align*} E^2(a,b) &= E\left(\frac{1}{2}(a+b),\frac{1}{2}(a+b)\right)\\ &= \left(\frac{1}{4}(a+b)+\frac{1}{4}(a+b), \frac{1}{4}(a+b)+\frac{1}{4}(a+b)\right)\\ &= E(a,b),\end{align*} so $E$ is a projection. Now, relative to the standard basis, the matrix of $E$ is not of the form you want: $$\left(\begin{array}{cc} \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} \end{array}\right).$$ However, notice that a vector $(x,y)$ is mapped to itself under $E$ if and only if $(x,y)=(\frac{1}{2}(x+y),\frac{1}{2}(x+y))$, if and only if $\frac{1}{2}x=\frac{1}{2}y$, if and only if $x=y$. So the vectors that are mapped to themselves are all multiples of $(1,1)$. If we take $(1,1)$ as one of the basis vectors that we will put on $B$, then the column corresponding to $(1,1)$ will be all $0$s with a $1$ in the diagonal: exactly the kind we need.

The second vector of $B$ has to be a vector that is mapped either to itself or to $(0,0)$ (since we want the matrix of $E$ relative to $B$ to be all $0$s except perhaps for some $1$s in the diagonal; think about what that means in terms of what $E$ does to the elements of $B$). But if the second vector is mapped to itself, then it will have to be a multiple of $(1,1)$ (because every vector that is mapped to itself is a multiple of $(1,1)$), and then $B$ will not be linearly independent. That means that the second vector in $B$ has to be a vector that is mapped to $(0,0)$ by $E$. A vector $(x,y)$ is mapped to $(0,0)$ if and only if $x+y=0$, if and only if $x=-y$. So if we pick $(1,-1)$ to be the second vector of $B$, that is, if $B=\{(1,1),(1,-1)\}$, then $B$ is a basis for $\mathbb{R}^2$ (check it!) and the matrix of $E$ with respect to $B$ is: $$\left(\begin{array}{cc} 1 & 0\\ 0 & 0 \end{array}\right),$$ which is of the desired form.

Now, in general...

You know that if $E$ is a projection, then $E=E^2$. Let $\mathbf{W}=\mathrm{Im}(E)$. Then how does $E$ act on $\mathbf{W}$? That is, what is $E|_{\mathbf{W}}$ (the restriction of $E$ to $\mathbf{W}$)? So, if you take a basis for $\mathbf{W}$, what does $E$ do to that bases?

That will be our start for $B$. We then need to complete $B$ so that the rest of the matrix for $E$ relative to $B$ is as described. From the description, we are going to need every other element of the basis to satisfy either $E\mathbf{x}=\mathbf{x}$ or $E\mathbf{x}=\mathbf{0}$. The former can't work, because that would mean that $\mathbf{x}\in\mathbf{W}$, which cannot happen (we already have a basis for $\mathbf{W}$ "in" $B$). So we are going to need every other element of the basis to be in the kernel of $E$. (The kernel is another name for the nullspace, in case that is the name you know it by).

Hmmm... Is that even possible? We would need the vector space to equal $\mathrm{W}+\mathrm{ker}(E) = \mathrm{Im}(E) + \mathrm{ker}(E)$. Since $\mathrm{ker}(E)\cap\mathrm{Im}(E)=\{\mathbf{0}\}$ (prove it!) that would mean that the vector space is $\mathrm{Im}(E)\oplus \mathrm{ker}(E)$.

Is this the case? If so, we'll be done! Take a basis for $\mathrm{ker}(E)$, take a basis for $\mathrm{Im}(E)$, put them together to get $B$. If not, then we're going to have to start over.

-
Is it always true that $E^2=E$? I dont think so. I think this is so if and only if $E$ is a projection onto a subspace. In other words the whole vector space and the zero vector space are not the only spaces invariant under $E$. –  smanoos Oct 17 '11 at 0:41
Yes Smanoos, I understand that. Still do not understand how to set this problem up. –  Rita Oct 17 '11 at 1:23
@smanoos: One definition of a projection (in the context of linear algebra) is that $E$ is a projection if and only if $E^2=E$. So I don't understand your question. Also, Rita specifically said that she knows that a projection "is idempotent", i.e., that $E^2=E$. What other notion of "projection" in linear algebra is it that you know? –  Arturo Magidin Oct 17 '11 at 1:36
I obviously cant question your solutions because they are excellent and I have a lot of confidence in you. But I asked this question based on theorem 1 (PG 73) of the book Finite Dimensional vector spaces by Halmos. –  smanoos Oct 17 '11 at 12:26
@smanoos: I still don't understand your comment. Halmos uses the phrase "projection on some subspace", but he never mentions any kind of "projection" that is not a "projection on some subspace". So when you say that it works "if and only if $E$ is a projection onto a subspace" you seem to be saying that there are projections that are not "projections onto a subspace". What other kind of projections are there in linear algebra? Notice that in Theorem 3, pg 74, Halmos already talks about a transformation "being a projection", and not adding "onto a subspace". –  Arturo Magidin Oct 17 '11 at 13:19