Suppose that $M$ is a matrix of order $n$ such that entries of matrix $M$ com from finite field $GF(2^n)$. The matrix $M$ is called MDS (Maximum Distance Separable) matrix if and only if every sub-matrix of $M$ is non-singular over $GF(2^n)$.
For a matrix of order $n$, we should obtain $\sum_{i=1}^n \, {n \choose i }^2$ determinant over $GF(2^n)$, to find out that a matrix is MDS or not. So, when the order of a matrix is less than $10$, we can use the mentioned definition to check that is it MDS matrix or not. But for large order of matrix, this definition is not applicable.
My question:
Is there a probabilistic method to find out a matrix is MDS or not MDS.
I would be appreciate for any suggestions.
Edition1:
With searching, I found one class of MDS matrices over field of real numbers. Consider the following companion matrix in the following form
$$ C_n=\left( \begin{array}{cccccc} 0 &1 &0 &\cdots &\cdots &0 \\ 0 &0 &1 &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &0 \\ 0 &\cdots &\cdots &0&0 &1 \\ 1 &1 &1 &\cdots &1 &1 \end{array} \right)_{n\times n} $$
The $n\times (n-1)$ power of matrix $C_n$ is a MDS matrix and the matrices $C_n^i$, $1\leq i \leq n^2-n-1$ are not MDS matrices. For example, assume the matrix $C_3$ as shown
$$ C_3= \left( \begin {array}{ccc} 0&1&0\\ 0&0&1\\ 1&1&1 \end {array} \right) $$
The matrices $C_3^i$, $1\leq i \leq 5$ are not MDS matrix but the matrix $C_3^6$ as follows
$$ C_3^6= \left( \begin {array}{ccc} 4&6&7\\ 7&11&13\\ 13&20&24 \end {array} \right) $$ is a MDS matrix. It means, the entries of $C_3^6$ are non-zero and the determinant of $C_3^6$ is $1$. In addition all square sub-matrices of order $2$ of matrix $C_3^6$ have non-zero determinant.
Edition2:
As an answer to @Daniel McLaury comment, you can check that the matrices $C_3^j$, $15 \leq j \leq 18$, are not MDS. For example, the matrix $C_3^{17}$ is as follows
$$ C_3^{17}= \left[ \begin {array}{ccc} 3136&4841&5768\\ 5768& 8904&10609\\ 10609&16377&19513 \end {array} \right] $$
the determinant of the following two sub-matrices of $C_3^{17}$ are zero
$$ \begin{array}{ccc} \left[ \begin {array}{cc} 5768&8904\\ 10609&16377 \end {array} \right] &, & \left[ \begin {array}{cc} 3136&5768\\ 5768&10609 \end {array} \right] \end{array} $$
In fact, design of MDS matrix is on the finite field. I just made this example in the field of real numbers to clarify my question. You can see the original form of my question with example, in my Mathover.