# The probabilistic method to find out a matrix is MDS

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.

• Given that 100% of matrices have this property, I don't know if probabilistic algorithms are likely to give you any further information. – Daniel McLaury Jan 1 '17 at 23:18
• @DanielMcLaury Please see the new edition. – Amin235 Jan 2 '17 at 7:49
• I see. I think it just confuses things to do everything over $\mathbb{R}$ and then mention that you're actually interested in finite fields at the end. I don't specifically know if it matters, but are you trying to do this over every finite field, or only $\mathbb{F}_p$, or only $\mathbb{F}_{2^n}$ or something? – Daniel McLaury Jan 2 '17 at 14:53
• @DanielMcLaury In cryptography, just $GF(2^n)$ can be used. I made an example in the field of real numbers because your first comment was absolutely wrong. I do not know why do you said "100% of matrices have this property:! – Amin235 Jan 2 '17 at 16:44
• If you want the short answer: because the set of non-MDS $m \times n$ matrices is a union of finitely many hypersurfaces, thus it has dimension $m n - 1$, and a reasonable probability measure on an $mn$-dimensional space shouldn't assign a positive probability to anything with dimension less than $mn$. – Daniel McLaury Jan 2 '17 at 17:21