Definition: Let a field $\mathbb{F}$. Consider an $2^n \times 2^n$ matrix $\bf H$ over $\mathbb{F}$. $\bf H$ is called Hadamard over $\mathbb{F}$ if and only if $$ {\bf H}=\left( \begin{array}{cc} {\bf U} & {\bf V} \\ {\bf V} & {\bf U} \end{array} \right) $$
where $\bf U$ and $\bf V$ are $2^{n-1} \times 2^{n-1}$ Hadamard matrices over $\mathbb{F}$.

Consider a circulant matrix ${\bf C}_4$ over $\mathbb{R}$ which is defined by $$ {\bf C}_4= \left( \begin {array}{cccc} 0&1&1&0\\ 0&0&1&1\\ 1&0&0&1\\ 1&1&0&0 \end {array} \right). $$ Let the $m$th power of ${\bf C}_4$ is denoted by ${\bf C}_4^m$ for some $m$. For instance, ${\bf C}_4^4$ and ${\bf C}_4^8$ are as follows

$$ \begin {array}{cc} {\bf C}_4^4=\left( \begin {array}{cccc} 2&4&6&4\\ 4&2&4&6 \\6&4&2&4\\ 4&6&4&2\end {array} \right),& {\bf C}_4^8=\left( \begin {array}{cccc} 72&64&56&64\\ 64&72&64& 56\\ 56&64&72&64\\ 64&56&64&72 \end {array} \right). \end {array} $$

My Question: Let $n$ is a positive integer number. How to prove ${\bf C}_4^{2^n}$,$n>1$, is Hadamard over $\mathbb{R}$.

My try: I numerically checked ${\bf C}_4^m$ in general is a Toeplitz matrix. For instance, ${\bf C}_4^5$ and ${\bf C}_4^{10}$ are:

$$ \begin {array}{cc} {\bf C}_4^5= \left( \begin {array}{cccc} 10&6&6&10\\ 10&10&6&6 \\ 6&10&10&6\\ 6&6&10&10 \end {array} \right), & {\bf C}_4^{10}= \left( \begin {array}{cccc} 256&240&256&272\\ 272&256&240&256\\ 256&272&256&240\\ 240&256&272&256\end {array} \right). \end {array} $$

The Jordan canonical form of ${\bf C}_4$ is in the following form:

$$ \begin {array}{cc} {\bf Q}= \left( \begin {array}{cccc} 1/4&1/4&1/4&1/4\\ -1/4&1/4&-1/4\,i&1/4\,i\\ 1/4&1/4&-1/4&-1/4\\ -1/4&1/4&1/4\,i&-1/4\,i \end {array} \right), & {\bf J}= \left( \begin {array}{cccc} 0&0&0&0\\ 0&2&0&0\\ 0&0&-1-i&0\\ 0&0&0&-1+i \end {array} \right), \end {array} $$ where ${\bf C}_4={\bf Q}\cdot {\bf J} \cdot {\bf Q}^{-1}$ and $i=\sqrt{-1}$. It can be verified that ${\bf J}^{2^n}$ for $n> 2$ is: $$ {\bf J}^{2^n}= \left( \begin {array}{cccc} 0&0&0&0\\ 0&{2}^{2^n}&0&0\\ 0&0&{2}^{2^{n-1}}&0\\ 0&0&0&{2}^{2^{n-1}}\end {array} \right). $$ Now assume that $a=2^{\displaystyle{2^n-2}}$. Then we can checked that ${\bf C}_4^{2^n}$ is: $$ {\bf C}_4^{2^n}= \left( \begin {array}{cccc} a+\sqrt {a}&a&a-\sqrt {a}&a\\ a&a+\sqrt {a}&a&a-\sqrt {a}\\ a-\sqrt {a}&a&a+\sqrt {a}&a\\ a&a-\sqrt {a}&a&a+\sqrt {a} \end {array} \right). $$ Is there another simple proof (especially based on the circulant matrices ) for this question?

Thanks for any suggestions.

  • 1
    $\begingroup$ Notice: $C_4^2$ is not hadamard $\endgroup$ – Exodd Jun 20 '18 at 12:36
  • $\begingroup$ @Exodd The question is edited by your notice. Thanks $\endgroup$ – Amin235 Jun 20 '18 at 13:37

The circulant matrices form an algebra, meaning that given any polynomial $p\in \mathbb C[x]$, then $p(C)$ is still circulant. Notice moreover that a circulant matric is a particular case of Toeplitz matrix.

Let us prove that $C_4^{2^n}$ is symmetric if $n>1$. You already noticed that $S = C_4^4$ is symmetric, but then $S^k$ is symmetric for every $k$, so $C_4^{2^n} = S^{2^{n-2}}$ is symmetric if $n>1$.

You can prove by yourself now that any symmetric circulant matrix is in particular Hadamard.

Notice : With the same proof you prove that $C_4^{n}$ is Hadamard if and only if $n$ is a multiple of 4.

  • $\begingroup$ I know what you mean. In fact, if $a(x)$ be the polynomial that is associated with the first row of an $n \times n$ circulant matrix $A$ then the $i$th row of $A$ is obtained by $x^i\, a(x)\mod{x^n-1}$ for $0 \leq i \leq n-1$. Thanks. $\endgroup$ – Amin235 Jun 20 '18 at 14:14

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.