A matrix $M$ of order $n$ is an [MDS](https://en.wikipedia.org/wiki/MDS_matrix)
(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](http://link.springer.com/chapter/10.1007/978-3-642-40588-4_3) 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](https://i.stack.imgur.com/aCpZo.jpg).


The motivation of this edition is the method of construction of [Hadamard matrix](https://en.wikipedia.org/wiki/Hadamard_matrix).



The probabilistic method to find out a matrix is MDS
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.


