Prove that for any $A \neq 0$ there is a matrix $B$ such that $A + B$ and $B$ have no eigenvalues in common. I am not sure how to begin thinking about this problem.  Could anyone provide a push in the right direction, or an explanation of what are the first things that go through their head when solving this?
Let $A \neq 0$ be an $n \times n$ complex matrix. Prove there is a matrix $B$ such that $A + B$ and $B$ have no eigenvalues in common.  
 A: If $A$ is a  a multiple of $I_n$, then we may take $B=A$.
So suppose that $A$ is not a multiple of $I_n$. 
Clearly the problem is invariant by conjugation (i.e. for any
invertible matrix $P$, $(A,B)$ satisfies the conditions iff $(P^{-1}AP,P^{-1}BP)$ does).
Lemma. If $A$ is not a multiple of $I_n$, then there is a conjugate
of $A$ whose lower leftmost coefficient is nonzero.
Proof of lemma.  We can assume that $A$ is in Jordan normal form. 
Since $A$ is not a multiple of $I_n$, either $A$ has at least two distinct eigenvalues or the form must have a one at
a nondiagonal position.
In the first case, suppose $Ae_{k}=\lambda_k e_k$ and $Ae_{l}=\lambda_le_l$ with $\lambda_k \neq \lambda_l$. In the initial basis $(e_1,\ldots,e_n)$, replace $e_l$ with $e_k+e_l$, and then reordering so that $e_k$ is put first and $e_k+e_l$ is put last, we are done.
In the second case, suppose there is a $1$ at the intersection of the $i$-th column with the $j$-th row, with $i\neq j$. Reordering the initial basis $(e_1,\ldots,e_n)$ so that $e_i$ is put first and $e_j$ is put last,we are done. 
So we can assume without loss of generality that $A$ has a nonzero
lower leftmost coefficient (let us call it $a$) :
$$
A=\left(\begin{array}{cccc}
\ldots & \ldots & \ldots & \ldots \\
\ldots & \ldots & \ldots & \ldots \\
\ldots & \ldots & \ldots & \ldots \\
a & \ldots & \ldots & \ldots \\ 
\end{array}\right)
$$
Now, consider the matrix all of whose terms are zero except on a pushed diagonal : 
$$
B=\left(\begin{array}{cccc}
0 & b_1 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
0 & 0 & 0 & b_{n-1} \\
0 & 0 & 0 & 0 \\ 
\end{array}\right)
$$
Then $B$ is nilpotent : its only eigenvalue is $0$.
On the other hand, the determinant of $A+B$ is a polynomial in $b_1,\ldots,b_{n-1}$,
and the coefficient in $b_1\ldots b_{n-1}$ is exactly $a$, which is a nonzero 
coefficient. So the polynomial is nonzero, and for a suitable choice
of $(b_1,\ldots,b_{n-1})$ its value will be nonzero. Then $A+B$ will be
invertible, solving your problem.
