2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ +1 because of the good presentation :) $\endgroup$ – Shahrooz Janbaz Jan 1 '17 at 21:09
  • $\begingroup$ I made a MDS example in the field of real numbers in my Mathstack. $\endgroup$ – Amin235 Jan 2 '17 at 7:53
  • $\begingroup$ If the matrix is invertible, a sufficient condition for non-MDS-ness is that the inverse contain at least one zero entry. Matrix inversion costs "only" $O (n^3)$. $\endgroup$ – Rodrigo de Azevedo Feb 15 '17 at 13:50
  • $\begingroup$ You right. In fact, we work on matrices of order 4 and using this fact: 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
3
$\begingroup$

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 field 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 field 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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Janbaz Thanks for useful comment. You know, MDS matrix are limited by the hardware. The first limitation is the polynomial that has to be from degree 4 and 8. In addition, we assume the companion matrix such that the entries of the last row of the companion matrix have to be with less bit(the first element of GF). Because of these limitations, the probability of a matrix be MDS is not 0.9. By the way, thanks again, especially for introducing the book. $\endgroup$ – Amin235 Jan 1 '17 at 21:33
1
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A code implies an alphabet, and it's not clear to me what alphabet you have in mind. I take the original question to be about matrices with entries from the reals, and I dom't see how to square that with a code. $\endgroup$ – Gerry Myerson Jan 1 '17 at 14:27
  • $\begingroup$ @Meysam If you have read the article that I mentioned in the question, you could see on the page 12, the following tip: "One approach of checking if a $d\times d$ matrix $M$ is an MDS is to use $[I\mid M]$ as a generator matrix and check if the code produced is MDS code. Note, if the underlying field is $F_{2^n}$, the number of code words will be $2^{nd}$ and finding the minimum weight non zero code word is NP-complete." First, read the details of question carefully and after that answer it! $\endgroup$ – Amin235 Jan 1 '17 at 16:45
  • $\begingroup$ @Amin235, Yes I saw that. Code words in " the number of code words will be $2^{nd}$" are refer to all code words which are produced by mentioned code and computing them weights. But in my answer, possible code words are refer to code words with weight less than $m+1$. $\endgroup$ – Meysam Ghahramani Jan 1 '17 at 17:05
  • $\begingroup$ For small order of matrix you right, But for large order of matrix, I think the complexity of finding MDS code is equivalent to finding MDS matrix. $\endgroup$ – Amin235 Jan 1 '17 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.