# Lp norm of Hadamard matrix

What is the Lp norm of the $$N$$-dimensional Hadamard matrix $$H = ((-1)^{i \cdot j})_{i,j}$$ for $$p > 2$$? I know that $$\|H\|_1 = N$$, $$\|H\|_2 = \sqrt{N}$$, $$\|H\|_\infty = N$$ but I can't figure out what it is for other values of $$p$$. Can we at least give a good upper-bound on it?

Here I consider the induced norm: $$\|H\|_p = \max_{x : \|x\|_p = 1} \|Hx\|_p$$

(a previous version of this question incorrectly said that $$\|H\|_\infty = 1$$)

• Isn't $\|H\|_\infty = N$ (maximal row sum of absolute values)? Commented Sep 17, 2021 at 0:16
• I've updated my question with a definition of the Lp norm. Commented Sep 17, 2021 at 23:26
• Is that a Hadamard matrix? It doesn’t seem like it. Commented Sep 18, 2021 at 1:01
• $i\cdot j$ stands for the inner product of the representation of integers $i,j$ I believe, @ZachTeitler Commented Sep 18, 2021 at 6:43
• I agree with @J.J.Green that the question contains an incorrect statement: since the Hadamard matrix is real-symmetric, by duality we have $\Vert H \Vert_p = \Vert H \Vert_q$ when $p$ and $q$ are conjugate indices. Could you please update the question? Commented Oct 4, 2021 at 18:34

Important Edit: As J.J Green pointed out, the OP contains an incorrectly stated value for $$\|H\|_{\infty}$$, which I copied without checking below. Interpolating between $$(1,\infty)$$ using the corrected version would give the trivial bound $$\|H\|_p \leq N$$. You regain the sharp bound by interpolating instead between $$(1,2)$$ and $$(2,\infty)$$.

I assume $$L^p$$ norm means the operator norm on $$\mathbb{R}^N$$ with the $$\ell_p$$ norm.

Then by Riesz-Thorin-Stein interpolation, you have $$\|H\|_p \leq \|H\|_1^{1/p} \|H\|_\infty^{1-1/p} = \sqrt[p]{N}$$ By testing on the vector $$(1,0,0,\ldots,0) \mapsto (-1,1,-1,1,\ldots)$$ you have $$\|H\|_p \geq \sqrt[p]{N}$$

and hence $$\sqrt[p]{N}$$ is the value.

• See JJ Green's comment above and answer below. Commented Oct 4, 2021 at 18:36
• Oops... in my defense, I assumed that the OP correctly calculated the $\ell_1$ and $\ell_\infty$ operator norms in his question (I took the values from those and didn't double check). Commented Oct 4, 2021 at 19:20
• De nada. Question now corrected, it seems. Commented Oct 5, 2021 at 10:19

I'm reluctant to contradict Professor Wong, but I think the accepted answer is incorrect since it takes $$\left\|H\right\|_\infty$$ as 1, whereas it is in fact $$N$$. But the same argument applies, with Riesz in this case being $$\left\| H \right\|_p \leq \left\| H \right\|^{2/p}_2 \left\| H \right\|^{1-2/p}_\infty = N^{1/p} N^{1 - 2/p} = N^{1 - 1/p} = N^{1/q}$$ with $$q$$ the conjugate index to $$p$$. This inequality is realised by a vector with equal non-zero entries and so gives the equality.

One can confirm this using software such as Matlab or Octave which implement Higham's approximation for $$L^p$$ norms of matrices for non-trivial $$p$$, and that gives a lower bound:

octave:1> format long

• You are right! (In my defense, I took $\|H\|_{\infty}$ from the OP's question without checking whether it was correctly computed.) Commented Oct 4, 2021 at 19:21
• There is a method (by Stephen Drury) which gets the $\ell_p \rightarrow \ell_q$ operator norm of a matrix to arbitrary accurately using a global subdivide-and-reject method, but is exponential in matrix size so $10 \times 10$ is about as far as you can go: His implementation is here: math.mcgill.ca/drury/research/matsaev/matsaev.html and I made a stab at the same algorithm in C soliton.vm.bytemark.co.uk/pub/jjg/en/code/steckin Commented Oct 5, 2021 at 13:55