Is there a matrix $A$ such that for every other matrix $B$, we have $\mbox{tr}(AB) = 0$?

Another sensible approach here: let $E_{ij}$ denote the matrix whose $i,j$ entry is $1$ and whose other entries are zeros. Show that $$ \operatorname{tr}(AE_{ji}) = a_{ij} $$ This can only be zero for all $i,j$ if $A$ is the zero matrix.

A nifty trick in proving the above is to note that $E_{ij} = e_ie_j^T$, where $e_i$ denotes the $i$th standard basis vector. In particular, we have $$ \operatorname{tr}(AE_{ji}) = \operatorname{tr}(Ae_je_i^T) = \operatorname{tr}(e_i^TAe_j) = e_i^TAe_j = a_{ij} $$

Let $B=A^t$. Then $\operatorname{trace}(AA^t)$ is the sum of squares of all coefficients of the real matrix $A$. If this is zero then $A=0$. So the zero matrix is the only possibility.

Somebody should have gotten around to pointing out that the underlying fundamental fact is that the Hilbert-Schmidt operator provides a norm on the space of matrices, also known as the Frobenius norm.