# MDS Matrix Elements

Can zero be one of the elements used in an MDS matrix (in the context of AES)?

Based on what I have read all entries of an MDS Matrix need to be non-zero. Also, I would appreciate any help in understanding the reason behind this requirement if zero cannot be an element of MDS.

• In any MDS matrix, any square submatrix (subset of rows/columns) must be invertible. This includes 1x1 matrices. – Fractalice Nov 2 '20 at 8:45

No, for MDS codes used in the way it is used in AES there's no other choice, i.e., an MDS code with these dimension must have all entries nonzero in the $$M$$ matrix.

The MDS matrix $$M$$ has to be square, mapping 4 bytes to 4 bytes and must have 4 nonzero entries in each row by MDS property.

It also means changing each input byte affects each output byte, helping in diffusion.

Background: by coding theory the code is generated by the $$k\times n$$ matrix $$G=[I|M]$$ The Matrix converts a length $$k$$ message $$m$$ to the codeword $$c$$ via $$c=mG$$ where $$m,c$$ are row vectors. This code has minimum weight $$n-k+1$$, the maximum possible by singleton bound. Since each row is a codeword the $$M$$ submatrix must have rows of minimum weight $$n-k$$. For AES, $$n=2k=8$$ so $$n-k=4.$$ So the rows of $$M$$ must have 4 nonzero entries.

• Thank you @kodlu, really appreciate your help. – X_Novichok_X Nov 2 '20 at 3:45
• ok, you can upvote the answer :-) – kodlu Nov 2 '20 at 3:49
• I tried doing that but the platform does not allow me unfortunately. Here is the message I keep getting: "Thanks for the feedback! Votes cast by those with less than 15 reputation are recorded, but do not change the publicly displayed post score." – X_Novichok_X Nov 2 '20 at 3:58
• @kodlu what do you mean by "no other choice"? – Fractalice Nov 2 '20 at 8:45
• @kodlu could you take the advantage of the title to write this answer for beginners? – kelalaka Nov 2 '20 at 10:42

After digging deeper here is what I found:

Let M be an MDS matrix, for any square sub-matrix Mi,j of M. From the property of MDS matrices, every sub-matrix should be non-singular.

No Mi,j elements belonging to M can be equal to zero, since this would lead to a singular submatrix of type 1×1 in M and thus would contradict the non-singularity requirement.

Simply put the cofactor matrix cannot be zero for a 1x1 sub-matrix of M if M is MDS since every sub-matrix of M should be non-singular (invertible).

https://www.aimsciences.org/article/doi/10.3934/amc.2019045