Is there any elegant way to find minimal polynomial of a matrix like this:
$$A=\begin{bmatrix} 2 & 6 & -1 & 0 \\ 0 & 1 & 3 & 0 \\ 0 & 3 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$
without having to explicitly find characteristic polynomial first by putting $|A-\lambda I|=0$ (and then estimate by trial and error, the minimal polynomial) ?
For larger matrices it gets really tedious to find minimal polynomial by trial and error.
On
lots of zeroes. Determinant of $A - \lambda I$ is $$ (2 - \lambda) \left( (1- \lambda)^3 - 9 (1-\lambda)\right) \; , $$ $$ (2 - \lambda)(1 - \lambda) \left( (1- \lambda)^2 - 9 \right) $$ $$ (2 - \lambda)(1 - \lambda) \left( \lambda^2 - 2 \lambda - 8 \right) $$ $$ (2 - \lambda)(1 - \lambda)(\lambda - 4)(\lambda + 2) $$
It seems that the question concerns block triangular matrices. $$ A=\begin{bmatrix}B_1&B_2\\0&1\end{bmatrix}\mbox{ with }B_1= \begin{bmatrix} 2 & 6 & -1 \\ 0 & 1 & 3 \\ 0 & 3 & 1 \end{bmatrix},\ \ B_2=\begin{bmatrix}0\\0\\1\end{bmatrix},$$ the "0" in the last row of $A$ actually being a row of 3 zeros. Then $$B_1=\begin{bmatrix}2&C_1\\0&C_2\end{bmatrix}\mbox{ with } C_1=\begin{bmatrix}6&-1\end{bmatrix},C_2=\begin{bmatrix}1&3\\3&1\end{bmatrix}.$$ As a first observation, the characteristic polynomial is easily deduced: $\det(\lambda I-A)=(\lambda-1)\det(\lambda I-B_1)=(\lambda-1)(\lambda-2)\det(\lambda I-C_2)=(\lambda-1)(\lambda-2)((\lambda -1)^2-9)$.
As a consequence, the eigenvalues are $1,2,1\pm3$. Since they are distinct, the matrix A is diagonalisable and the characteristic polynomial is its minimal polynomial.
This seems elegant enough to treat the example presented, but what to do if, for example $C_2=\begin{bmatrix}-1&3\\3&-1\end{bmatrix}$ and hence the eigenvalues are $1,2, -4$, where $2$ has (algebraic) multiplicity 2?
The corresponding $B_1= \begin{bmatrix} 2 & 6 & -1 \\ 0 & -1 & 3 \\ 0 & 3 & -1 \end{bmatrix}$ has an eigenspace of dimension 1 corresponding to the eigenvalue 2 and so its minimal polynomial is $(\lambda-2)^2(\lambda+4)$. As $B_1$ does not have the eigenvalue 1, $A$ is conjugate to $A=\begin{bmatrix}B_1&0\\0&1\end{bmatrix}$ and hence has minimal polynomial $(\lambda-2)^2(\lambda+4)(\lambda-1)$.
As another example, consider $A$ with submatrix $B_1$ replaced by $B_1= \begin{bmatrix} 2 & 1 & -1 \\ 0 & -1 & 3 \\ 0 & 3 & -1 \end{bmatrix}$. Then the eigenspace of the eigenvalue 2 has dimension 2 and the minimal polynomial of $B_1$ is $(\lambda-2)(\lambda+4)$. Proceeding as before, the minimal polynomial of $A$ is then $(\lambda-2)(\lambda+4)(\lambda-1)$.
From the examples, it can be seen how to proceed in general for block triangular matrices such that one diagonal block consists of one element: Consider a matrix $A=\begin{bmatrix}B_1&B_2\\0&a\end{bmatrix}$, $a$ a scalar and suppose that $B_1$ has the minimal polynomial $m(\lambda)$.
If $a$ is not a zero of $m(\lambda)$ then $A$ is conjugate to $\begin{bmatrix}B_1&0\\0&a\end{bmatrix}$ and has minimal polynomial $m(\lambda)(\lambda-a)$.
If $a$ is a zero of $m(\lambda)$, then consider the highest power $(\lambda-a)^m$ of $\lambda-a$ dividing $m(\lambda)$. This means that $m$ is the smallest integer such that the dimension of the kernel of $(B_1-a I)^m$ equals the algebraic multiplicity of $a$ as a zero of the characteristic polynamial of $B_1$. Calculate $$(A-a I)^m=\begin{bmatrix}(B_1-a I)^m&(B_1-a I)^{m-1}B_2\\0&0\end{bmatrix}.$$ If the ranks of $(B_1-a I)^m$ and $\begin{bmatrix}(B_1-a I)^m&(B_1-a I)^{m-1}B_2\end{bmatrix}$ do not agree, then the dimension of the kernel of $(A-a I)^m$ is equal to that of the kernel of $(B_1-a I)^m$, because $ (B_1-a I)^{m-1}B_2$ is not in the image of $(B_1-a I)^m$. Therefore it is smaller than the algebraic multiplicity of $a$ in the characteristic polynomial of $A$ (actually by 1). Hence the minimal polynomial of $A$ is $m(\lambda)(\lambda-a)$.
If the two ranks agree, then the dimension of the kernel of $(A-a I)^m$ equals the multiplicity of $a$ in the characteristic polynomial of $A$ and $m(\lambda)$ is the minimal polynomial of $A$.
Actually, the important information is that the minimal polynomial of $A$ can only be equal to $m(\lambda)$ or $m(\lambda)(\lambda-a)$. Therefore it is also sufficient to check if $m(A)$ is zero or not.
This method of treating block triangular matrices where one block is scalar is maybe not elegant, but I do not know any better.