# MDS matrix

An MDS matrix (maximum distance separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, an $m\times n$ matrix $A$ over a finite field $K$ is an MDS matrix if it is the transformation matrix of a linear transformation $f(x)=Ax$ from $K^{n}$ to $K^{m}$ such that no two different $(m+n)$ -tuples of the form $(x,f(x))$ coincide in $n$ or more components. Equivalently, the set of all $(m+n)$ -tuples $(x,f(x))$ is an MDS code, i.e., a linear code that reaches the Singleton bound.
Let ${\tilde {A}}={\begin{pmatrix}\mathrm {I} _{n}\\\hline \mathrm {A} \end{pmatrix}}$ be the matrix obtained by joining the identity matrix $\mathrm {I} _{n}$ to $A$ . Then a necessary and sufficient condition for a matrix $A$ to be MDS is that every possible $n\times n$ submatrix obtained by removing $m$ rows from ${\tilde {A}}$ is non-singular. This is also equivalent to the following: all the sub-determinants of the matrix $A$ are non-zero. Then a binary matrix $A$ (namely over the field with two elements) is never MDS unless it has only one row or only one column with all components $1$ .
Serge Vaudenay suggested using MDS matrices in cryptographic primitives to produce what he called multipermutations, not-necessarily linear functions with this same property. These functions have what he called perfect diffusion: changing $t$ of the inputs changes at least $m-t+1$ of the outputs. He showed how to exploit imperfect diffusion to cryptanalyze functions that are not multipermutations.