Let $A=(a_{ij})$ be an $n\times n$ matrix. Suppose that $A^2$ is diagonal. Must $A$ be diagonal? Let $A=(a_{ij})$ be an $n\times n$ matrix. Suppose that $A^2$ is diagonal? Must $A$ be diagonal. 
In other words, is it true that 
$$A^{2}\;\text{is diagonal}\;\Longrightarrow a_{ij}=0,\;i\neq j\;\;?$$
 A: No, this is already false for $n=2$. Consider
$$
A=\begin{pmatrix} 0 & 1 \cr 1 & 0 \end{pmatrix}
$$
Since $A^2=I$ is diagonal, but $A$ is not, there is a problem. In general, there are always elements of finite order $r$ in $GL_n(K)$ with $A^r=I$ diagonal, but $A$ not diagonal for $n\ge 2$. 
A: As a simplified case, consider $n=2$ and let $$A=\begin{pmatrix}a&b\\c&d\end{pmatrix}\implies A^2=\begin{pmatrix}a^2+bc&b(a+d)\\c(a+d)&d^2+bc\end{pmatrix}$$
so $$A^2\,\,\text{diagonal}\iff b(a+d)=c(a+d)=0\implies\left\{\begin{matrix}
b=c=0 \implies A\,\,\text{diagonal}\\
a+d=0\implies a=-d
\end{matrix}\right.$$
Hence a counterexample would be any matrix of the form $$A=\begin{pmatrix}-d&b\\c&d\end{pmatrix}$$ with $b \ne 0$ or $c \ne 0$ or both.
A: It's probably easier to see the answer to this question if you think of matrices not as arrays of numbers, but as representing linear operators. A diagonal matrix is one that just scales the elements (not necessarily by the same amount), i.e. the eigenvectors are the elementary vectors. So this question can be thought of as "Is there a linear operator that involves interactions between elements of the vector, but when done twice, does not?"
From there, there are several relatively easy-to-understand examples. For instance, swapping two elements is not a "diagonal" operator, but applying it twice is just the identity, which is. Rotating by $90$ degrees is also not a diagonal operator, but applying it twice is a rotation by $180$ degrees, which is. If you treat order $1$ polynomials as vectors, then differentiation is not diagonal, but the second derivative is trivially so (since it sends everything to zero).
These examples have extensions to arbitrary $n$: swapping $n$ elements, rotating by  $\dfrac{\pi}{n}$, and taking the derivative of order $n$ polynomials are all non-diagonal operators, but taking them $n$ times is diagonal.
A: The matrix $A$ with all entries $0$ except for $1$ at position $(1,n)$ is such that $A^2=0$, a diagonal matrix.
For $n=3$, the matrix is
$$\begin{bmatrix}0&0&1\\0&0&0\\0&0&0\end{bmatrix}$$
A: I would like to show why the Dietrich's example is the key of the problem.
Generically (if you randomly choose a diagonal $D$), then $A^2=D$ implies that $A$ is diagonal. Indeed, the elements of $D$ are "always" distinct and $DA=AD$ implies that $A$ is diagonal.
Now, assume that $D$ has non-distinct elements. Using a permutation of the vectors of basis, we may assume that $D=diag(\lambda_1I_{n_1},\cdots,\lambda_k I_{n_k})$ where the $\lambda_i$ are distinct. Then $AD=DA$ implies that $A$ is in the form $A=diag(A_1,\cdots,A_k)$ where $A_i^2=\lambda_i I_{n_i}$ (since $A^2=D$). Thus, at least  over $\mathbb{C}$, the problem for any non-zero $D$, is reduced (equivalent) to find a non-diagonal matrix s.t. $A^2=I$ when $n\geq 2$. Dietrich did that for $n=2$; for $n>2$, it suffices to add "ones" on the diagonal.
