Once upon a less enlightened time, when people were less knowledgeable in the intricacies of algorithmically computing eigenvalues, methods for generating the coefficients of a matrix's eigenpolynomial were quite widespread. One of the more prominent methods for computing the coefficients was a method ascribed to both the Frenchman Leverrier, and the Russian Faddeev (who was an (co-)author of one of the oldest references on the practice of numerical linear algebra).
The (Faddeev-)Leverrier method is a method that will require you to do a number of matrix multiplications to generate the coefficients of the characteristic polynomial. Letting the $n\times n$ matrix $\mathbf A$ have the monic characteristic polynomial $(-1)^n \det(\mathbf A-\lambda\mathbf I)=\lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_0$, the algorithm proceeds like so:
$\mathbf C=\mathbf A;$
$\text{for }k=1,\dots,n$
$\text{if }k>1$
$\qquad \mathbf C=\mathbf A\cdot(\mathbf C+c_{n-k+1}\mathbf I);$
$c_{n-k}=-\dfrac{\mathrm{tr}(\mathbf C)}{k};$
$\text{end for}$
If your computing environment can multiply matrices, or take their trace (sum of the diagonal elements, $\mathrm{tr}(\cdot)$), then you can easily program (Faddeev-)Leverrier. The method works nicely in exact arithmetic, or in hand calculation (assuming you have the stamina to repeatedly multiply matrices), but is piss-poor in inexact arithmetic, as the method tends to greatly magnify rounding errors in the matrix, ever yielding coefficients that become increasingly inaccurate as the iteration proceeds. But, for the simple $3\times 3$ case envisioned by the OP, this should work nicely.
People interested in this old, retired method might want to see this paper.
The minimal polynomial of a square matrix $A$ is the monic polynomial $p$ of lowest degree such that $p(A) = 0$. If $q$ is another polynomial such that $q(A) = 0$, then $p$ is a factor of $q$. In particular, by the Cayley-Hamilton Theorem, the characteristic polynomial of $A$ is such a $q$, so the minimal polynomial divides the characteristic polynomial.
In this case, the characteristic polynomial is $q(x) = x^3$. The only monic polynomials which divide $q$ are $p_0(x) = 1$, $p_1(x) = x$, $p_2(x) = x^2$, and $p_3(x) = x^3$. Clearly, $p_0(A) \neq 0$, so the minimal polynomial is one of $p_1$, $p_2$, $p_3$. You can check which of these satisfy $p_i(A) = 0$. Choosing the polynomial of lowest degree is the minimal polynomial for $A$.
Best Answer
Permuting rows two and three, as well as columns two and three yields the matrix $$ A_2:= \begin{pmatrix} 1275 & 0 & -169 & -208 \\ 0 & 1275 &-208 & -256 \\ -169 & -208 & 1531& -208 \\ -208 & -256& -208 & 1444\\ \end{pmatrix}. $$ Denoting $B:=\pmatrix{-169 & -208\\-208 & -256}$, the matrix can be written in block form $$ A_2 = \pmatrix{ 1275\ I_2 & B \\ B & B + 1700\ I_2} = 1275\ I_4 + \pmatrix{ 0 & B \\ B & B + 425 I_2}. $$ The matrix $B=\pmatrix{-13\cdot 13 & -13\cdot 16\\-13\cdot 16 & -16\cdot 16}$, has eigenvalues $0$ and $-425=-256-169$ with eigenvectors vectors $v_0=\pmatrix{16\\-13}$ and $v_{-425}=\pmatrix{13\\16}$, respectively.
These vectors combined yield the eigenvectors of $A_2$ (pairs eigenvector $\to$ eigenvalue) $$ \pmatrix{v_0\\0} \to 1275, \ \pmatrix{0\\v_0} \to 1700, \ \pmatrix{v_{-425}\\v_{-425}} \to 850, \ \pmatrix{v_{-425}\\-v_{-425}} \to 1700. $$ Thus, the characteristic polynomial is $$ p(\lambda) = (\lambda-1700)^2 (\lambda-1275) (\lambda-850). $$ Expanding the characteristic polynomial the traditional way is no fun, the determinant of the matrix is $\approx 3\cdot 10^{12}$.