# What is the branch number of this matrix?

We have the following matrix: $$\begin{pmatrix}0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$

What is the branch number?

Is this a MDS marix?

• Can any matrix with a 0 entry be MDS? – poncho May 4 '16 at 18:02
• @poncho I would not ask, if I would know. But I suspect it can't be. – LightBit May 4 '16 at 18:04
• Hint: what's the definition of MDS? – poncho May 4 '16 at 18:49
• Also, the answer depends on the ring that the matrix is based on. This matrix is singular if the matrix elements are $GF(3)$ – poncho May 4 '16 at 21:44
• @poncho, you're right that a zero in $A$ constrains the rank. Having all nonzero entries over $GF(2)$ (thus all 1's) results in a singular $A$ and a (relatively) bad code. – kodlu May 5 '16 at 0:28

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for crypto.
Note that you just need to take the given matrix, call it $A,$ form $G=[I | A]$ over the relevant field and determine the minimum weight of the resulting code. Magma (and GAP, Pari, Python) can do this for you easily. This code turns out to be a quasi-cyclic code over the fields $GF(2^n)$ with minimum distance 4.
Edit: It seems that 4 is the limit for the minimum distance of this type of code. In particular a $16\times16$ version, still has minimum distance only 4, for the fields $GF(2^n)$ where $n=1,2,\ldots,8.$ I assume $n=8$ is of interest to the OP, since it corresponds to having bytes as code symbols, as in AES.