Finding the Matrix of a Linear Operator Satisfying a Polynomial This question has been doing my head in, as it limits us to not use eigenvalues, diagonalization or anything analogous -- just strictly linear functions.

Given a linear function $f : \mathbb R^3 \to \mathbb R^3$ that satisfies $p(x) = x^2 - x + 1,$ find the matrix $A$ of $f$ with respect to the standard basis of $\mathbb R^3$

 A: I'm not sure how restrictive "diagonalization or anything analogous" is supposed to be, but here's one argument that such a linear transformation cannot exist.
Suppose that $f:\Bbb R^3 \to \Bbb R^3$ satisfies $p(f) = 0$. Because $\Bbb R^3$ is a space of odd dimension, $f$ necessarily has a real eigenvalue. That is, there exists a non-zero $x \in \Bbb R^3$ and a $\lambda \in \Bbb R$ for which $f(x) = \lambda x$.  Now, note that
$$
p(f) = 0 \implies [p(f)](x) = 0 \implies p(\lambda)x = 0 \implies p(\lambda) = 0.
$$
However, the polynomial $p(x)$ has no real roots, so we have a contradiction.
So, no such $f$ exists.

A proof of the existence of a real eigenvalue, from scratch.  We consider the characteristic polynomial of $A$, $p_A(t) = \det(tI - A)$. From the Leibniz formula for the derivative, we see that $p_A(t)$ must have degree $3$ because the sum contains the term $(t-a_{11})(t-a_{22})(t-a_{33})$, and each term in the sum is a product of $3$ terms with degree at most $1$.
Because $p_A(t)$ is a degree $3$ polynomial, it necessarily has a real root. In particular, it suffices to note that $\lim_{t \to -\infty}p_A(t)$ and $\lim_{t \to \infty} p_A(t)$ have opposite signs, so that $p_A$ must have a real root by the intermediate value theorem.  
So, let $\lambda \in \Bbb R$ be such that $p_A(\lambda) = 0$. Because $\det(\lambda I - A) = 0$, the matrix $\lambda I - A$ must have a non-trival nullspace. That is, the exists a non-zero vector $x$ for which 
$$
(\lambda I - A)x = 0 \implies \lambda I x = Ax \implies Ax = \lambda x.
$$
In other words, $A$ necessarily has a real eigenvalue $\lambda$.

An writeup of the proof that makes no use of the terms "characteristic polynomial" or "eigenvalue".
Suppose that $f:\Bbb R^3 \to \Bbb R^3$ satisfies $p(f) = 0$, and let $A$ be its matrix.  We consider the function $q(t) = \det(tI - A)$. From the Leibniz formula for the derivative, we see that $q(t)$ must be a polynomial degree  $3$ because the sum contains the term $(t-a_{11})(t-a_{22})(t-a_{33})$, and each term in the sum is a product of $3$ terms with degree at most $1$.
Because $q(t)$ is a degree $3$ polynomial, it necessarily has a real root. In particular, it suffices to note that $\lim_{t \to -\infty}q(t)$ and $\lim_{t \to \infty} q(t)$ have opposite signs, so that $q$ must have a real root by the intermediate value theorem.  
So, let $\lambda \in \Bbb R$ be such that $q(\lambda) = 0$. Because $\det(\lambda I - A) = 0$, the matrix $\lambda I - A$ must have a non-trival nullspace. That is, the exists a non-zero vector $x$ for which 
$$
(\lambda I - A)x = 0 \implies \lambda I x = Ax \implies Ax = \lambda x.
$$
Now, note that
$$
p(A) = 0 \implies [p(A)](x) = 0 \implies p(\lambda)x = 0 \implies p(\lambda) = 0.
$$
However, the polynomial $p(x)$ has no real roots, so we have a contradiction. So, no such $f$ exists.
