#linear-algebra

Let $\omega$ be the infimum of all real $c$ such that two $n\times n$ matrices can be multiplied using $\mathcal{O}(n^c)$ arithmetic operations. The schoolbook method shows $\omega \le 3$, and $\omega \ge 2$ because the output has $n^2$ entries. Is $\omega =2$?

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with entries $\pm 1$ whose rows are mutually orthogonal, so that $H{H}^T=nI$. Such a matrix can exist only if $n$ is 1, 2 or a multiple of 4. Prove that a Hadamard matrix exists for every multiple of 4.