How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$ I have been reading about MDS matrices. It is defined as (paraphrased from Section 2.1)

An $n \times n$ matrix $M$ is MDS if and only if $bn(M) = n + 1$
where $bn$ (branch number) is defined as:
$bn(M) = \min_{u\neq0}({hw(u) + hw(Mu)})$ where $hw$ denotes Hamming weight.

It seems the MDS matrices like that of AES are defined over higher order fields like $\operatorname{GF}(2^8)$. It also seems the AES MDS matrix can be written as a matrix over $\operatorname{GF}(2)$. See this for example.
My question is, how does the MDS property translate to a binary matrix? Say, I am given an $n\times n$ binary invertible matrix, how can I understand whether this matrix is MDS or not?
I found some discussion in Section 2.1 about binary MDS matrices though, but could not get the idea.
Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$?
The necessary condition is that $k\mid n$ which means $n=km$ for some integer $m$.
Now Let $\bf A$ be $km \times km$ binary matrix. The first step is that to consider the matrix $\bf A$ as a block binary matrix as follows where ${\bf B}_{i,j}$, $1\leq i,j \leq m$ are $k \times k$ binary matrices.
$$
{\bf A}=
\left(
\begin{array}{c|c|c|c}
{\bf B}_{1,1} &amp; {\bf B}_{1,2} &amp; \cdots &amp; {\bf B}_{1,m} \\ \hline
{\bf B}_{2,1} &amp; {\bf B}_{2,2} &amp; \cdots &amp; {\bf B}_{2,m} \\\hline
\vdots &amp; \vdots &amp; \cdots &amp; \vdots \\\hline
{\bf B}_{m,1} &amp; {\bf B}_{m,2} &amp; \cdots &amp; {\bf B}_{m,m}
\end{array}
\right).
$$
Next, we should consider all square sub-matrices of the block matrix $\bf A$ and check that whether these sub-matrices are non-singular over $\mathbb{F}_2$? For example one of the square sub-matrices of $\bf A$ is as follows. The matrix $\bf C$ is an $2k \times 2k$ binary matrix and we should check its singularity over $\mathbb{F}_2$.
$$
{\bf C}=
\left(
\begin{array}{}
{\bf B}_{1,1} &amp; {\bf B}_{1,2} \\
{\bf B}_{2,1} &amp; {\bf B}_{2,2}.
\end{array}
\right).
$$
Note that if all square sub matrices of the block matrix $\bf A$ are non-singular over $\mathbb{F}_2$, then we say $\bf A$ is an MDS matrix over $k$-bit inputs or $k$-bit words.
Maybe you ask this question: Is $\bf A$ an MDS matrix over $\mathbb{F}_{2^k}$ for some irreducible polynomial of degree $k$ over $\mathbb{F}_2$? The answer is yes when $\bf A$ is obtained from an $m \times m$ matrix such as $\bf M$ provided that the entries of $\bf M$ belong to $\mathbb{F}_{2^k}$. Let me make an example to learn it more clearly.
Consider the following $4\times 4$ matrix where the entries of $\bf M$ belong $\mathbb{F}_{2^8}$ such that this finite field is constructed from the irreducible polynomial $f(x)={x}^{8}+{x}^{4}+{x}^{3}+x+1$  over $\mathbb{F}_2$ (some users of this forum maybe say it is the MDS matrix of AES, but imagine we do not know this fact and we want to check it!).
$$
\scriptsize{
 {\bf M}=
 \left(
 \begin {array}{cccc} 
 \alpha&amp;\alpha+1&amp;1&amp;1\\ 
 1&amp;\alpha&amp;\alpha+1&amp;1\\ 
 1&amp;1&amp;\alpha&amp;\alpha+1\\ 
 \alpha+1&amp;1&amp;1&amp;\alpha
 \end {array}
 \right).}
$$
Now we obtain a $8 \times 8$ binary matrix such that its characteristic polynomial over $\mathbb{F}_2$ is equal to $f(x)$ such as the following one
$$
\scriptsize{
{\bf N}=
 \left(
 \begin {array}{cccccccc} 
 0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0\\ 
 1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0
 \end {array} 
 \right).}
$$
Next, by applying $\bf N$ we transform $\bf M$ to a $32 \times 32$ binary matrix, denoted $\bf A$, as follows. Let the $(i,j)$ entry of $\bf M$ be $\sum_{i=0}^{7}b_i\alpha^i$ where $b_i$'s are binary numbers. Now the $(i,j)$ entry of the block matrix $\bf A$ is equal to $\sum_{i=0}^{7}b_i{\bf N}^i$ in modulo 2. Therefore, the block matrix $\bf A$ is given by
$$
\scriptsize{
\left(
 \begin {array}{cccccccc|cccccccc|cccccccc|cccccccc}
 0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1\\ \hline
 1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1\\ \hline
 1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1\\ \hline
 1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\ 
 0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1\\ 
 0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\ 
 0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0\\ 
 1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;1&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0
\end {array}
\right).}
$$
The final step is that we check the singularity of all square sub-matrices of the block matrix $\bf A$ over $\mathbb{F}_2$ (the number of these sub-matrices are ${2n\choose n}-1$, for example for AES is 69).
Maybe you ask this question what is the advantages of this scenario. One answer is that the computation over $\mathbb{F}_2$ is more faster than the finite fields.
I hope you find this answer helpful.