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

3 Answers 3

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

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

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

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.