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.

Any $4\times 4$ matrix over $F_{2^n}$ with all entries non zero is an MDS matrix if and only if it is a full rank matrix with the inverse matrix having all entries non zero and all of its $2\times 2$ sub-matrices are full rank.$\endgroup$ – Amin235 Feb 15 '17 at 18:12