Given a matrix $A$ with $\operatorname{tr} (A) = 0$, prove that there is a B such that $\forall 1\leq i\leq n :(B^{-1}AB)_{i,i}=0$ I've tried using some matrices $B^{-1}$ that switch the rows, but the $B$ at the end placed the elements back in the diagonal (in different order) so I couldn't find a rule.
 A: Lemma
Given any matrix $A$ of order at least $2$, there exists an invertible matrix $E$ such that $(E^{-1}AE)_{11} = 0$.
Proof: Let $A = [a_{ij}]_{n \times n}$, $n \ge 2$. If $a_{11} = 0$, the result holds with $E = I$, the identity matrix of order $n$. If $a_{12} = 0$, then let $E$ be the permutation matrix obtained by interchanging the first and second rows of $I$. Then $E^{-1}AE$ is the result of interchanging the first and second rows as well as first and second columns of $A$, and therefore has $(1,1)$ entry zero.
Suppose $a_{11}$ and $a_{12}$ are non-zero. Define the $n \times n$ matrix
\begin{equation*}
E = \left[\begin{array}{cc|c}
a_{12} & 0 & \mathbf 0_{1 \times (n-2)}\\
-a_{11} & 1 & \mathbf 0_{1 \times (n-2)}\\
\hline
\mathbf 0_{(n-2) \times 1} & \mathbf 0_{(n-2) \times 1} & I_{n-2}
\end{array}\right].
\end{equation*}
The inverse of $E$ is easily verified to be
\begin{equation*}
E^{-1} = \left[\begin{array}{cc|c}
1/a_{12} & 0 & \mathbf 0_{1 \times (n-2)}\\
-a_{11}/a_{12} & 1 & \mathbf 0_{1 \times (n-2)}\\
\hline
\mathbf 0_{(n-2) \times 1} & \mathbf 0_{(n-2) \times 1} & I_{n-2}
\end{array}\right].
\end{equation*}
Then the $(1,1)$ entry of $AE$ is $a_{11} a_{12} - a_{12} a_{11} = 0$. Multiplication on the left by $E^{-1}$ results in a matrix with the first row elements multiplied by $1/a_{12}$ (and other rows affected in various ways). Therefore, $E^{-1}AE$ also has $(1,1)$ entry zero. $\qquad \square$
Now, we know that similar matrices have the same trace, so $\operatorname{trace}(E^{-1}AE) = \operatorname{trace}(A)$. Thus we have the following corollary.
Corollary
Every square matrix of order at least $2$ is similar to a matrix with the same trace, and having $(1,1)$ entry zero.
Proposition
Every square matrix $A$ is similar to a matrix with the last diagonal entry equal to $\operatorname{trace}(A)$, and all preceding diagonal entries zero.
Proof: We prove by induction on $k$, $1 \le k \le n - 1$, that $A$ is similar to a matrix with the first $k$ diagonal entries $0$, and having the same trace as $A$ due to similarity. Then the result follows by letting $k = n - 1$.
From the above corollary, the result is true for $k = 1$. That is, there is a matrix similar to $A$ and having the same trace as $A$, with its first diagonal entry equal to zero. Suppose the result to be true for $k$. Thus, without loss of generality, assume that the first $k$ diagonal entries of $A$ are all zero. Let $A$ be partitioned as given below (with matrices $X$ and $Y$ of appropriate sizes).
\begin{equation*}
A = \left[\begin{array}{c|c}
Z_{k \times k} & X\\
\hline
Y & B_{(n - k) \times (n - k)}
\end{array}\right]
\end{equation*}
Then $Z$ has a zero diagonal, and $\operatorname{trace}(B) = \operatorname{trace}(A)$.
Now, by the above lemma, we have a matrix $E$ of order $n - k$ such that $E^{-1}BE$ has $(1,1)$ entry zero. Define an $n \times n$ matrix
\begin{equation*}
F = \left[\begin{array}{c|c}
I_k & \mathbf 0'\\
\hline
\mathbf 0 & E
\end{array}\right]
\end{equation*}
with the zero matrices $\mathbf 0$  and $\mathbf 0'$ of sizes same as those of $X$ and $Y$ respectively.
Then
\begin{align*}
F^{-1}AF & = \left[\begin{array}{c|c}
I_k & \mathbf 0'\\
\hline
\mathbf 0 & E^{-1}
\end{array}\right]
\left[\begin{array}{c|c}
Z& X\\
\hline
Y & B
\end{array}\right]
\left[\begin{array}{c|c}
I_k & \mathbf 0'\\
\hline
\mathbf 0 & E
\end{array}\right]
\\
& = \left[\begin{array}{c|c}
I_k & \mathbf 0'\\
\hline
\mathbf 0 & E^{-1}
\end{array}\right]
\left[\begin{array}{c|c}
Z & XE\\
\hline
Y & BE
\end{array}\right]
\\
& = \left[\begin{array}{c|c}
Z & XE\\
\hline
E^{-1}Y & E^{-1}BE
\end{array}\right]
\end{align*}
Thus, $F^{-1}AF$ is a matrix similar to $A$ (and hence with zero trace) with the first $k + 1$ diagonal entries zero (since the first diagonal entry of $E^{-1}BE$ is zero). By induction, the result is true for all $k \le n - 1$. $\qquad \square$
As a special case of the above proposition, if $\operatorname{trace}(A) = 0$, then $A$ is similar to a matrix with the last diagonal entry as well as all preceding diagonal entries zero. Thus we have the main result.
Theorem
Every matrix $A$ with zero trace is similar to a matrix with zero diagonal.
A: Hint: 
For a $2 \times 2$ matrix, consider one with $1$ and $-1$ on the diagonal. (Note that there cannot be any off-diagonal elements here, because the evalues differ). Then picking $B$ to be rotation by $\pi/4$ i.e., the matrix
$$
s\begin{bmatrix}
1 & -1 \\
1 & 1
\end{bmatrix},
$$
where $s = \frac{\sqrt{2}}{2}$, 
produces a matrix of the desired form, and this clearly generalizes to other eigenvalues besides $1$. 
How'd I find this? I looked for a vector $v$ that the original matrix sent to a vector $w$ with $v \cdot w = 0$, since that's what helps produce a 0 on the diagonal. Since the original matrix simply reflects through the $x$-axis, the vector $(1, 1)$ goes to $(1, -1)$, which is perpendicular to it. When I found two such independent vectors (a similar argument applies to $(1, -1)$, for example), I chose them as my columns for $B$ (i.e., I represented the original transform in that basis).  (Along the way, I made them unit vectors so that it'd be easier to compute $B^{-1}$.)
For $3 \times 3$, there are three cases to consider: diagonal with three distinct e-values that sum to zero, diagonal with entries $a, a, -2a$, and the same thing, but with a $1$ in the superdiagonal entry above $a$ and $a$. 
In each case, you need to do a similar analysis/discovery of vectors. 
