Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $(a_{ij})_{1 \le i,j \le n}$ be a real orthogonal matrix. Show that $$\left| \sum_{1 \le i,j \le n} a_{ij}\right| \le n.$$

Naively applying the Cauchy-Schwarz inequality only gives $n^{\frac{3}{2}}$ (but only relies on the columns being of norm $1$, and not orthogonality). How do we get the stronger bound $n$?

share|improve this question
2  
The Schwarz of inequality / And lemma too, he has no T. // The "Distribution" Schwartz you see / Is French, and so he has a T. -- R. P. Boas, Spelling Lesson. :) –  t.b. May 24 '11 at 17:26
add comment

3 Answers

up vote 10 down vote accepted

Let the vector $v$ be the sum of the row vectors. Think of this geometrically. Since we are adding $n$ orthonormal vectors, this vector is the diagonal of an $n$-dimensional box, and hence has norm $|v|=\sqrt{n}$.

Let $v_k$ refer to the entries of $v$. Then we have $$\sum_{i,j} a_{ij}=\sum_k v_k\leq \sqrt{n \sum_k v_k^2}=n,$$ by Cauchy Schwarz, and hence the original sum is bounded by $n$.

Hope that helps,

share|improve this answer
    
Yes, it did help. Thank you. –  Joel Cohen May 24 '11 at 15:48
add comment

Use Cauchy-Schwarz on the product $^{\operatorname t}\!UMU$ where $U = ^{\operatorname t}\! \left( \begin{matrix} 1 & 1 & \dots & 1 \end{matrix} \right)$.

share|improve this answer
add comment

Let $A$ be your matrix, and let $u$ be the all ones vector (all its elements are equal to 1). Then the sum can be expressed as

$s = u^t A u$ = $u^t v$

Apply Cauchy-Schwarz to the vectors $u$ and $v$.

share|improve this answer
add comment

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.