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}$).



Orthogonal matrices with small entries
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.


