Suppose $k$ is a field, and every square matrix over $k$ has an eigenvalue (in $k$). Does it follow that $k$ is algebraically closed?
(Context: see here. It follows from the result proved there that it's enough to show that every polynomial is a factor of the characteriestic polynomial of some matrix.)
While you can explicitly construct a matrix with given characteristic polynomial, I rather like the following more abstract argument. Suppose $k$ is not algebraically closed. Then it has a nontrivial finite field extension $K$ (you can adjoin a root of any nonlinear irreducible polynomial). Picking a basis for $K$ as a $k$-vector space, for any $a\in K$ we can represent multiplication by $a$ as a matrix $T_a$. If $a\in K\setminus k$, then $T_a-\lambda I=T_{a-\lambda}$ is invertible for any $\lambda\in k$: its inverse is just $T_{(a-\lambda)^{-1}}$. Thus $T_a$ is a matrix with no eigenvalues over $k$.
There are two "answers": The comments about "companion matrices" and the Answer from Eric. I agreed with Eric that his Answer was much nicer than looking at the companion matrix. I'm posting this to point out the possibly interesting fact that the two methods are very closely related.
Say $k$ is a field and $p\in k[x]$ has degree $n$. Let $V= k[x]/I$, where $I=(p)$. Whether $p$ is irreducible or not, $V$ is a finite-dimensional vector space over $k$, with standard basis $1,x,\dots,x^{n-1}$.
Define $T:V\to V$ by multiplication by $x$, which is to say $T(r(x)+I)=xr(x)+I$. Let $M$ be the matrix for $T$ wrt the standard basis for $V$. Then it turns out that $M$ is precisely the companion matrix for $p$! (At least if $p$ happens to be monic.)
This is already interesting, since it answers the question of where the hell that companion matrix thing comes from. If we showed that $p$ was in fact the characteristic polynomial for $M$ that would be interesting. But without doing that much work, and without messing around with matrices at all, we can prove the following, which is sufficient to answer the Question at the top:
If $\lambda\in k$ is an eigenvalue of $T$ then $p(\lambda)=0$.
Proof: Say $r(x)+I\ne0_V=I$ and $xr(x)+I=\lambda r(x)+I$. This says $$(x-\lambda)r(x)\in I,$$so $$(x-\lambda)r(x)=q(x)p(x)$$for some polynomial $q$. So $p(\lambda)=0$ or $q(\lambda)=0$. But if $q(\lambda)=0$ then $$q(x)=(x-\lambda)s(x)$$for some polynomial $s$; hence $r(x)=s(x)p(x)$ so $r\in I$, contradiction.
Come to think of it, the converse is just as simple:
If $\lambda\in k$ and $p(\lambda)=0$ then $\lambda$ is an eigenvalue of $T$.
Proof: $(x-\lambda)r(x)=p(x)\in I$ implies that $T(r(x)+I)=\lambda(r(x)+I)$.
