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


1 Answer 1


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, 2017 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, 2017 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, 2017 at 19:24
  • $\begingroup$ This answer made me think whether the following cayley table has a Hadamard structure, as seen in this question: crypto.stackexchange.com/questions/71288/… $\endgroup$ Jun 18, 2019 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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