Minimalpolynomial of a Matrix without calculating the characterstic polynomial Is there a way calculating the minimal polynomial of a matrix without using the characteristic polynomial?
For example following matrix $$M = \left(
\begin{array}{cccc}
 1 & 0 & -2 & 0 \\
 -2 & -1 & 4 & 2 \\
 0 & 0 & -1 & 0 \\
 0 & 0 & 2 & 1 \\
\end{array}
\right).$$
Calculating the characteristic polynomial I get $\chi_M = (x-1)^2(x+1)^2$ with eigenvalues $-1$ and $1$ with algebraic multiplicity 2. Using the characteristic polynomial I have to check all possibilities for the minimal polynomial $\mu_M$ which are $$(x-1), (x-1)^2, (x+1), (x+1)^2, (x-1)(x+1), (x-1)^2(x+1), (x-1)(x+1)^2, (x-1)^2(x+1)^2.$$
Is there a way to see from the form of the matrix, what the minimal polynomial could be? Since $M$ could be partitioned as follows:
$$M = \left(
\begin{array}{cccc}
 1 & 0 & -2 & 0 \\
 -2 & -1 & 4 & 2 \\
 0 & 0 & -1 & 0 \\
 0 & 0 & 2 & 1 \\
\end{array}
\right)= \left(
\begin{array}{cc}
 A & B \\
 0 & C \\
\end{array}
\right),$$ with $A =\left(
\begin{array}{cc}
 1 & 0 \\
 -2 & -1 \\
\end{array}
\right), B = \left(
\begin{array}{cc}
 -2 & 0 \\
 4 & 2 \\
\end{array}
\right)$ and $C = \left(
\begin{array}{cc}
 -1 & 0 \\
 2 & 1 \\
\end{array}
\right)$.
 A: I'll answer the general question of how to compute a minimal polynomial$~\mu$ of $M$ without using the characteristic polynomial, and only then apply it specifically for this matrix, which has very special features that facilitate computing the minimal polynomial.
The easy  to state (but not so easy to perform) method for finding$~\mu$ is to compute successive powers of your matrix $M^0=I,M,M^2,\ldots$, and check each time whether it is a linear combination of previous powers. This is bound to happen at or before the power $M^n$, where $n$ is the matrix size; if the first relation found is $M^d=c_0I+c_1M+\cdots+c_{d-1}M^{d-1}$, then $\mu=X^d-c_{d-1}X^{d-1}-\cdots-c_1C-c_0$.
Easier in practice is to pick some nonzero vector $v$ (some standard basis vector will do fine) and similarly compute a sequence of vectors $v,Mv,M^2v,\ldots$, and again find the first linear dependence, leading similarly to the minimal degree monic polynomial $P\in K[X]$ such that $P[M]v=0$. This polynomial may not yet be $~\mu$ but is guaranteed to divide $\mu$. However in the (likely) case that $d=\deg P$ equals $n$, this divisibility implies $\mu=P$, and you can stop here. Assuming this did not happen (so $d<n$), it remains to find the quotient$~Q=\mu/P$, which is the minimal degree monic polynomial such that $Q[M]P[M]=0$, in other words such that $Q[M]$ vanishes in the image subspace $P[M](K^n)$; one can compute that subspace, and if it is nonzero continue recursively to compute $Q$ using a nonzero vector of $P[M](K^n)$. Since $P[M]$ is known to kill each of the independent vectors $v,Mv,M^2v,\ldots M^{d-1}v$, one can complete that to a basis of $K^n$ and compute $P[M](K^n)$ using just the added vectors.

So here is how it works for your matrix $M$. With $v=e_1$, the vectors $v$ and $Mv=(1,-2,0,0)$ are linearly independent, but $M^2(v)=(1,0,0,0)$ is dependent on them, in fact $M^2v=v$ so we get $P=X^2-1$ and $d=2$. Since $d<n$ we must continue, so complete $v,Mv$ to a basis of $K^4$, for which $e_3,e_4$ will do fine. On has $P[M](e_3)=M^2e_3-e_3=e_3-e_3=0$ (amazing coincidence) and $P[M](e_4)=M^2e_4-e_4=e_4-e_4=0$ (another amazing coincidence), so one has $P[M](K^4)=0$, which is "annihilated" by $Q=1$, so $\mu=QP=P=X^2-1$ after all. It would have been more fun, and more instructive, if the last two columns had not been so very special.
A: In fact, if we take 
$$
A = \pmatrix{1&-2\\0&-1}, \quad
B = \pmatrix{1&0\\-2&-1}
$$
Then we have
$$
M = \pmatrix{a_{11}B & a_{12}B\\a_{21}B & a_{22}B} = A \otimes B
$$
Where $\otimes$ denotes the Kronecker product. Since both $A$ and $B$ have eigenvalues $\{-1,1\}$, $A \otimes B$ will have the spectrum $\{-1,-1,1,1\}$.
Note also that the Kronecker product of diagonalizable matrices is diagonalizable, so $M$ must have the minimal polynomial $q_M(x) = (x-1)(x+1)$.  
In general, the exponent of a linear term in the minimal polynomial of $A \otimes B$ cannot exceed any of the exponents in the minimal polynomials of $A$ or $B$.
In fact, given the Jordan forms of $A$ and $B$, we can deduce the Jordan form of $A \otimes B$.

Another approach: the characteristic polynomial of a matrix of the form
$$
M = \pmatrix{A&B\\0&C}
$$
with $A,C$ square will be $\chi_M(x) = \chi_A(x)\chi_C(x)$.
