Prove the branch of number of Advanced Encryption Standard In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said   


  " Let F be a linear transformation acting on byte vectors and let the 
  byte weight of a vector be the number of nonzero bytes. The byte weight of a vector is denoted by $W(a)$.  
  
  Definition: The branch number of a linear transformation $F$ is
    $$min_{a\neq0}(W(a) + W(F(a)))$$  
  
  If the branch number is 5, a difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input (or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between input and output bits involves bits from at least 5 different bytes from input and output."


The AES chose polynomial $c(x)=03x^3+01x^2+01x+02$ to construct MixColumn operation , where the coefficients are hexadecimal representation of numbers in $GF_{256} $(e.g. $03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial\,representation}$) The MixColumn operation is done by multiplying $c(x)$ and mod $x^4+1$  

However, the document doest not give a mathematical proof. My questions are  


Prove the maximum branch number is $5$. Besides, AES MixColumn can achieve the maximum value as $5$. 
given a branch number, how to construct the linear transforamtion
$F(\,)$ (in the case of AES, it is $5$) ? 
Reversely, given $F$ (a matrix), how to estimate its branch number?
For example, how should I prove that if the linear transformation is
self-inverse
($\;(c(x))^2\equiv 1 \;mod\,x^4+1$ or $F^2=I$ ), then the
branch number is at most $4$?


I suppose these problems are related to matrix norm, but I do not know where to start to tackle these problems.
The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument. 

We have two definitions for MDS (Maximum Distance Separable) Matrix:

First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular. 

Second definition: A matrix $M_{n\times n}$ is MDS if and only if

$$
Y_{n\times 1}=M_{n \times n}\, X_{n \times 1} \Longrightarrow \mathop{\rm min}_{X\neq 0}(W(Y)+W(X))=n+1
$$

where $X={[x_0,x_1,\cdots , x_{n-1}]}^T$ and $Y={[y_0,y_1,\cdots , y_{n-1}]}^T$ are vectors  in an arbitrary 
 field and $W(X)$ is the number of non-zero elements of $X$. 

Now, suppose that we use a MDS matrix( by first definition) of order $4$ and 
we want to proof by second definition that it's branch number is 5. Consider our MDS matrix be as follows 

$$
 M=\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]
$$
the entries $m_{i,j}$ are non-zero because $M$ by first definition is MDS. Now consider the following equation
$$
MX=Y \Longrightarrow 
\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 where $x_i$'s and $y_i$'s are elements of finite field. By second definition $X$ should be non-zero. For simplicity, consider $x_1\neq0$ and other $x_i$ can be zero or non-zero. 

We should consider some cases to show that for every selection of $x_2$, $x_3$ and $x_4$, at least four elements of $x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are non-zero.

The first case is $x_2=x_3=x_4=0$. in this case we have:

$$
\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\0
\\ 0\\ 0\end {array}
 \right]=
 \left[ \begin {array}{c} x_1\,m_{1,1}\\ x_1\,m_{2,1}
\\ x_1\,m_{3,1}\\ x_1\,m_{4,1}\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 because $m_{i,j}$'s and $x_1$ are nonzero then the elements $y_1,y_2,y_3,y_4$ are nonzero. The next case is that are there non-zero
 values for $x_2,x_3,x_4$ such that 

$$
\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
due to the $M$ matrix is non-singular we can conclude that
$$
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]^{-1}\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]=\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
and it contradict to our assumption that $x_1,x_2,x_3,x_4\neq 0$ and so one of the $y_1,y_2,y_3,y_4$ should be non-zero. 

The next case is that: are there for example $x_1\neq0, x_2\neq0 ,x_3=x_4=0$ that result 
 $y_1\neq0, y_2\neq0 ,y_3=y_4=0$. Consider there was this case as follows

$$
\left[ \begin {array}{cccc} m_{{1,1}}&amp;m_{{1,2}}&amp;m_{{1,3}}&amp;m_{{1,4}}
\\ m_{{2,1}}&amp;m_{{2,2}}&amp;m_{{2,3}}&amp;m_{{2,4}}
\\ m_{{3,1}}&amp;m_{{3,2}}&amp;m_{{3,3}}&amp;m_{{3,4}}
\\ m_{{4,1}}&amp;m_{{4,2}}&amp;m_{{4,3}}&amp;m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_2
\\ 0\\ 0\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ 0\\ 0\end {array}
 \right]
$$
so we have
$$
 \left[ \begin {array}{cc} m_{{3,1}}&amp;m_{{3,2}}\\ m_{
{4,1}}&amp;m_{{4,2}}\end {array} \right]  \left[ \begin {array}{c} x_{{1}}\\ x_{{2}}
\end {array} \right]=
\left[ \begin {array}{c} 0\\ 0\end {array} \right]
$$
from the first definition all sub-matrix of $M$ has non-zero determinant and hence we can conclude from the above equation that the values of $x_1=x_2=0$ and it contradict to our assumption. 

The other cases are similar to mentioned cases and use from this fact that all sub-matrix of $M$ have non-zero determinant. 

I hope you find it useful.