# Orthogonal matrices with small entries

Is it true that for any $$n$$, there exists a $$n \times n$$ real orthogonal matrix with all coefficients bounded (in absolute value) by $$C/\sqrt{n}$$, $$C$$ being an absolute constant ?

Some remarks :

• If we want $$C=1$$, the matrix must be a Hadamard matrix.
• The complex analogue has an easy answer: the Fourier matrix $$(\exp(2\pi \imath jk/n)/\sqrt{n})_{(j,k)}$$. Forgetting the complex structure gives a positive answer to the question in the real case when $$n$$ is even.
• A random matrix doesn't work (the largest entry is typically of order $$\sqrt{\log(n)}/\sqrt{n}$$).
• Seems like a neat question. Why the combinatorics tag? – Pete L. Clark Jan 29 '10 at 9:40
• Because there may be a solution of combinatorial nature ... but I agree the tags are bad, feel free to retag – Guillaume Aubrun Jan 29 '10 at 9:58
• Hadamard matrices are a common tool in combinatorial design theory, so co.combinatorics is fine. – Douglas Zare Jan 30 '10 at 6:44
• Do you know of a reference for the fact that an random orthogonal matrix has largest entry approximately $\sqrt{\log(n)}/ \sqrt{n}$? Or more generally for the statistics of a random orthogonal matrix? – Gabe K Jan 9 at 20:27
• @GabeK see for example Tiefeng Jiang, Maxima of entries of Haar distributed matrices, Prob. Th. Rel. Fields 131, 121-144 (2005). – Guillaume Aubrun Jan 10 at 8:05

Here's an idea which I think might be expandable to a solution once some details are filled in. (I am rather tired at the moment, though, so apologies if there is a cretinous error in what follows.)

We'll do the case $n=4m-1$ where $m$ is an integer; the case $n=4m-3$ is similar.

Let $C$ be a $2m\times 2m$ matrix which has the required form. Let $A$ be the $n\times n$ matrix with $C$ in the top left corner, $1$ on the remaning $2m-1$ diagonal entries, and zero elsewhere. Let $B$ be the $n\times n$ matrix with $C$ in the bottom right corner, $1$ on the remaining $2m-1$ diagonal entries, and zero elsewhere.

$A=\left[\begin{matrix} C & 0 \\\\ 0 & I_{2m-1} \end{matrix} \right]\quad,\quad B= \left[\begin{matrix} I_{2m-1} & 0 \\\\ 0 & C \end{matrix} \right]$

Both $A$ and $B$ will be real orthogonal since $C$ is. Consider the matrix $AB$, which being the product of real orthogonal matrices will also be orthogonal. I claim that the entries will all be $O(\sqrt{n})$ as required.

In more detail:

-- If both $i$ and $j$ are $\leq 2m-1$, then $(AB)\_{ij}=A\_{ij}=C\_{ij}$ which is small by our choice of $C$; by symmetry, we can dispose of the case where both $i$ and $j$ are $\geq 2m+1$ in a similar way.

-- If $i\leq 2m-1$ and $j\geq 2m+1$, then on considering $\sum\_r A\_{ir}B\_{rj}$ we see that the only nonzero contribution comes when $r\leq 2m$ and $r\geq 2m$, i.e. when $r=2m$ and so $(AB)\_{ij}=A\_{i,2m}B\_{2m,j}$ is small.

-- If $i=2m$ or $j=2m$ then a similar analysis shows that $(AB)\_{ij}$ can't be bigger than the entries of $C$ (at least up to some constant independent of $m$).

-- If $i\geq 2m+1$ and $j\leq 2m-1$ then $(AB)\_{ij}=0$.

That should handle the case $n=4m-1$. The case $n=4m-3$ can be done in a similar fashion, but this time we will have extra factors of $3$ floating around since we have $3\times n$ and $n\times 3$ regions to consider, rather than just $1\times n$ and $n\times 1$ regions.

• It looks OK - That's a very nice solution ! – Guillaume Aubrun Jan 29 '10 at 10:23
• Thanks, hope it checks out. I still feel one should be able to go from $n$ to $n+1$, by sticking a 1 in the bottom right-hand corner and then multiplying (or conjugating?) by a suitable orthogonal matrix of size $n+1$; but I couldn't quite see how to make the details work. – Yemon Choi Jan 29 '10 at 10:27
• Nice solution! Now I feel like going from n to n+1 cannot be that simple. – domotorp Jan 29 '10 at 12:05

Take $A$ to be the $n\times n$ matrix with $A_{jk}=\sqrt{\frac{2}{n+1}}\sin(\frac{jk\pi}{n+1})$. This is a variant of the answer of jj-joerg-arndt.

For all n you can take the matrix corresponding to the length-n Hartley transform which should give C=sqrt(2).

• Thank you very much (as well as Richard Stanley). I never heard about Hartley transform before, that's very interesting ! – Guillaume Aubrun Aug 30 '10 at 7:58