The probabilistic method to find out a matrix is MDS A matrix $M$ of order $n$ is an MDS
(Maximum Distance Separable) 
matrix if and only if every sub-matrix of $M$ is non-singular.
For a matrix of order $n$, we should obtain $\sum_{i=1}^n \, {n \choose i }^2$ determinant 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 think, the above question is similar to this question that for a random large number how to find 
if a number is prime or not. When a number is large, the  exhaustive search is not useful to test and there are some probabilistic methods for prime numbers. 
In addition, when a matrix $A$ of order $n$, is not MDS, it means there is at least 
 a sub-matrix of $A$ like $B$ of order $k$, $1\leq k \leq n$, 
such that determinant $B$ is zero. Now, the possibility of $k$ being a small number is larger than that of $k$ being a large number. 
I mean, when I want to start the algorithm of
  exhaustive search, is it better to search form sub-matrices of size $2$ to $n-1$ or inverse?
I think, one of the ways that make optimal the exhaustive search is that we use lookup table method. I mean, we just 
calculate the all determinant of sub-matrix of order $2$ and save it and after that for determinant of 
 sub-matrices of order $3$, we use of our table and update lookup table with  determinant of 
 sub-matrices of order $3$ and repeat this algorithm. This algorithm in math language is easy but It's Implementation is complicated.
My motivation of this question is this paper.  
I would appreciate any suggestions.
Edition:
Assume $A_i$, $1\leq i \leq r$, where $r$ is a natural number, be MDS matrices. Is there a method to obtain a 
 MDS matrix like $B$ that is constructed from $A_i$ matrices. I mean, from MDS matrices of low order, obtain a
 MDS matrix with higher order. For example.
The motivation of this edition is the method of construction of Hadamard matrix.
 A: Since my comment is long, I write it as an answer, but it is not a complete answer and just give some insight.
Firstly, based on the paper you mentioned and based on the applications of MDS matrices in cryptography, I think the elements of the matrix belong to the finite field.
When the size of a randomly chosen matrix increase, the probability of being MDS will drop. for example, the probability of a randomly selected $2\times 2$ matrix with entries from $GF(2^8)$ being MDS is $0.98$. Rough Monte Carlo tests of $1000000$ randomly selected $3\times 3$ matrices over the same ﬁeld shows that the probability of the MDS property drops to about $0.938$, and this drops further to about $0.814$ for $4\times 4$ matrices. The explanation lies in the fact that there are more square submatrices to consider, all of which have to be non-singular; in other words, the larger the matrix, the harsher are the conditions it must satisfy.
On the other hand, working over a larger ﬁeld raises the probability of a randomly selected matrix being MDS: In fact, the probability that a randomly selected $4\times 4$ matrix with entries from $GF(2^{16})$ be MDS is $0.995$.
So, I think the answer to your question for testing sub-matrices (to determine a predefined matrix is MDS or not) depend to the size of the base field and the size of your original matrix. Maybe, you must select randomly a small square sub-matrix and then select randomly a big square sub-matrix! 
anyway, you can find more details and some good information and theorems in the book "Algebra for Cryptologists" by "Alko R. Meijer" which published in 2016.
A: Let $C$ be $[n,k,d]$ code. Codes  with $n-k=d-1$ are called MDS codes.
If a $m\times m$ matrix $M$ is an MDS we can use $[I\mid M]$ as a generator matrix
and check if the code produced is MDS code. In this state, produced code $C$ is $[2m,m,d]$ code. So $d$ must be equal to $m+1$. In worst case, we can check this with all $\sum_{i=1}^{i=m+1}{2m \choose i}$ possible code words. So its implementation is not complicated.
Note that you can easily compute the minimum distance of codes with powerful programs such as MAGMA, for small $m$.
