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}$).
  • $\begingroup$ Seems like a neat question. Why the combinatorics tag? $\endgroup$ Jan 29 '10 at 9:40
  • $\begingroup$ Because there may be a solution of combinatorial nature ... but I agree the tags are bad, feel free to retag $\endgroup$ Jan 29 '10 at 9:58
  • $\begingroup$ Hadamard matrices are a common tool in combinatorial design theory, so co.combinatorics is fine. $\endgroup$ Jan 30 '10 at 6:44
  • $\begingroup$ 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? $\endgroup$
    – Gabe K
    Jan 9 '20 at 20:27
  • 1
    $\begingroup$ @GabeK see for example Tiefeng Jiang, Maxima of entries of Haar distributed matrices, Prob. Th. Rel. Fields 131, 121-144 (2005). $\endgroup$ Jan 10 '20 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.

  • $\begingroup$ It looks OK - That's a very nice solution ! $\endgroup$ Jan 29 '10 at 10:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yemon Choi
    Jan 29 '10 at 10:27
  • $\begingroup$ Nice solution! Now I feel like going from n to n+1 cannot be that simple. $\endgroup$
    – 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).

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

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.