Definition: A matrix A of size $2^n$ is a Hadamard matrix, if has the following form $$ A= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\, , $$ where $U$ and $V$ are also Hadamard matrices.

Example: A Hadamard matrix A of size $2^2$ is as follows $$ A= \left( \begin {array}{cccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}} \\ a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}} \\ a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}} \\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}\end {array} \right)\, , $$ Where $a_i$, $0\leq i \leq 3$ are from any arbitrary field.

Consider B is a $2^n\times 2^n$ matrix such that the $(i,j)$the entry of B, denoted B$[i,j]$, is defined by B$[i,j]=a_{i \oplus j}$ where $i,j \in \{0,1,\cdots , 2^{n}-1\}$ and $i \oplus j$ means Xor between two numbers $i$ and $j$(for example $2 \oplus 3=1$ since $10 \oplus 11=01$).

Example: A matrix B of size $2^3$ is $$ B= \left( \begin {array}{cccccccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}}&a_{{4 }}&a_{{5}}&a_{{6}}&a_{{7}}\\ a_{{1}}&a_{{0}}&a_{{3}} &a_{{2}}&a_{{5}}&a_{{4}}&a_{{7}}&a_{{6}}\\ a_{{2}}&a _{{3}}&a_{{0}}&a_{{1}}&a_{{6}}&a_{{7}}&a_{{4}}&a_{{5}} \\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}&a_{{7}}&a_{{6}}&a _{{5}}&a_{{4}}\\ a_{{4}}&a_{{5}}&a_{{6}}&a_{{7}}&a_{ {0}}&a_{{1}}&a_{{2}}&a_{{3}}\\ a_{{5}}&a_{{4}}&a_{{7 }}&a_{{6}}&a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}}\\a_{{6}} &a_{{7}}&a_{{4}}&a_{{5}}&a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}} \\ a_{{7}}&a_{{6}}&a_{{5}}&a_{{4}}&a_{{3}}&a_{{2}}&a _{{1}}&a_{{0}}\end {array} \right)=a_{i \oplus j}\qquad 0\leq i,j \leq 7 \, . $$

My question: Why the matrix B=$(a_{i \oplus j})$, $0\leq i,j \leq 2^{n}-1$, is an $2^n\times 2^n$ Hadamard matrix?

My Try: I can proof it by induction on $n$, but I would like to see its proof with other method.

Background: When entries of a Hadamard matrix come from the finite field $GF(2^q)$ and be an MDS matrix, then the Hadamard matrix can be used in the diffusion layer of block cipher such as Khazad block cipher


This is evident. Let $B$ be a $2^n \times 2^n$ matrix. We have:

$$a_{i\oplus (j+2^{n-1})}=a_{(2^{n-1}+i)\oplus j},a_{i\oplus j}=a_{(2^{n-1}+i)\oplus (2^{n-1}+j)}.$$

So, $B$ has the following form and therefore is a Hadamard matrix as follows $$B= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\, $$

  • $\begingroup$ Meysam, I suggest to add the condition $i,j \in \{0,1,\cdots, 2^{n-1}-1\}$ in your answer, since in the posted question it is assumed that $i,j \in \{0,1,\cdots, 2^{n}-1\}$. In fact, I wrote the values of $i$ and $j$ incorrectly and after that I edited the question and I modified it. Thanks $\endgroup$ – Amin235 Oct 30 '17 at 19:16
  • $\begingroup$ @kodlu can I ask a math writing question. What is difference of be and is in math writing. I mean, in which situation it's better to use be instead of is. Thanks $\endgroup$ – Amin235 Oct 30 '17 at 19:20
  • 2
    $\begingroup$ this is an English question. In modern English we say " let X be Y" or "assume X is Y", both are essentially the same. $\endgroup$ – kodlu Oct 30 '17 at 19:24

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.