Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 contant ?

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}$).
share|improve this question
    
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

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.